Tiểu luận: Tìm hiểu giải thuật di truyền

Tiểu luận Tìm hiểu giải thuật di truyền phân tích cơ sở lí thuyết; cấu trúc thuật toán di truyền tổng quát; các công thức của thuật giải di truyền và ứng dụng.

Tiểu luận: Tìm hiểu giải thuật di truyền

1. Mở đầu

Hiện nay, thuật toán di truyền cùng với logic mờ được ứng dụng rất rộng rãi trong các lĩnh vực phức tạp. Thuật toán di truyền kết hợp với logic mờ chứng tỏ được hiệu quả của nó trong các vấn đề khó có thể giải quyết bằng các phương pháp thông thường hay các phương pháp cổ điển, nhất là trong các bài toán cần có sự lượng giá, đánh giá sự tối ưu của kết quả thu được. Chính vì vậy, thuật giải di truyền đã trở thành đề tài nghiên cứu thú vị và đem đến nhiều ứng dụng trong thực tiễn. Ngày nay, thuật giải di truyền được ứng dụng khá nhiều trong các lĩnh vực như khoa học, kinh doanh và giải trí. Đầu tiên phải kể đến là các bài toán tối ưu bao gồm tối ưu số và tối ưu tổ hợp đã sử dụng thuật giải di truyền để tìm lời giải như là bài toán người du lịch (Travelling Salesman Problems - TSP). Ứng dụng kế tiếp của thuật giải di truyền là thiết kế và điều khiển robo.

2. Nội dung

2.1 Thuật toán di truyền

Thuật toán di truyền là thuật toán tối ưu ngẫu nhiên dựa trên cơ chế chọn lọc tự nhiên và tiến hóa di truyền. Nguyên lý cơ bản của thuật toán di truyền đã được Holland giới thiệu vào năm 1962. Cơ sở toán học đã được phát triển từ cuối những năm 1960 và đã được giới thiệu trong quyển sách đầu tiên của Holland, Adaptive in Natural and Artificial Systems. Thuật toán di truyền được ứng dụng đầu tiên trong hai lĩnh vực chính: tối ưu hóa và học tập của máy.

Cơ sở lí thuyết

  • Quá trình lai ghép (phép lai)
  • Quá trình đột biến (phép đột biến)
  • Quá trình sinh sản và chọn lọc (phép tái sinh và phép chọn)

Cấu trúc thuật toán di truyền tổng quát

  • Bước 1: Khởi tạo quần thể các nhiễm sắc thể.       
  • Bước 2: Xác định giá trị thích nghi của từng nhiễm sắc thể.                  
  • Bước 3: Sao chép lại các nhiễm sắc thể dựa vào giá trị thích nghi của chúng và tạo ra những nhiễm sắc thể mới bằng các phép toán di truyền.   
  • Bước 4: Loại bỏ những thành viên không thích nghi trong quần thể.    
  • Bước 5: Chèn những nhiễm sắc thể mới vào quần thể để hình thành một quần thể mới. 
  • Bước 6: Nếu mục tiêu tìm kiếm đạt được thì dừng lại, nếu không trở lại bước 3. 

Các công thức của thuật giải di truyền

2.2 Ứng dụng

Ứng dụng: Tìm đáp số cho phương trình X  = 64. Đây là một bài toán đơn giản để giúp ta có thể hiểu rõ hơn các bước của thuật toán di truyền. 

Chương trình: Các đoạn code

3. Kết luận

Tiểu luận trình bày và giới thiệu những khái niệm cơ bản, cơ sở lý thuyết về thuật giải di truyền. Trên cơ sở lý thuyết, đề tài đã cài đặt các phép toán cơ bản của thuật giải di truyền nhằm phục vụ cho việc thực hiện các ứng dụng. Sử dụng các phép toán của thuật giải di truyền để xây dựng ứng dụng cho bài toán người du lịch và bài toán vạch lộ trình đường đi cho robo. Đề tài chỉ giới thiệu những kiến thức chung nhất về thuật giải di truyền, chưa đi sâu vào các vấn đề nghiên cứu tối ưu khác. Phần ứng dụng vạch lộ trình đường đi cho robo chưa hoàn hảo. Đặc biệt là chưa giải quyết tốt việc robo tránh vật chắn và kích thước quần thể thay đổi. 

--- Nhấn nút TẢI VỀ hoặc XEM ONLINE để tham khảo đầy đủ nội dung Tiểu luận trên ---

Ngày:24/08/2020 Chia sẻ bởi:Oanh

CÓ THỂ BẠN QUAN TÂM