Thuật toán di truyền - Chủ đề nâng cao
Trong phần này, chúng tôi giới thiệu một số chủ đề nâng cao trong Giải thuật di truyền. Một người đọc chỉ tìm kiếm phần giới thiệu về GAs có thể chọn bỏ qua phần này.
Các vấn đề về tối ưu hóa hạn chế
Các vấn đề tối ưu hóa bị ràng buộc là những vấn đề tối ưu hóa trong đó chúng ta phải tối đa hóa hoặc giảm thiểu một giá trị hàm mục tiêu nhất định phải tuân theo các ràng buộc nhất định. Do đó, không phải tất cả các kết quả trong không gian giải pháp đều khả thi, và không gian giải pháp chứa các vùng khả thi như thể hiện trong hình sau.
Trong trường hợp như vậy, các toán tử giao nhau và đột biến có thể cung cấp cho chúng ta các giải pháp không khả thi. Do đó, các cơ chế bổ sung phải được sử dụng trong GA khi giải quyết các Vấn đề về tối ưu hóa bị hạn chế.
Một số phương pháp phổ biến nhất là -
Sử dụng penalty functions điều này làm giảm tính phù hợp của các giải pháp không khả thi, tốt nhất là để tính phù hợp bị giảm tương ứng với số lượng các ràng buộc bị vi phạm hoặc khoảng cách so với vùng khả thi.
Sử dụng repair functions đưa ra một giải pháp không khả thi và sửa đổi nó để các ràng buộc bị vi phạm được thỏa mãn.
Not allowing infeasible solutions để nhập vào dân số ở tất cả.
Sử dụng một special representation or decoder functions đảm bảo tính khả thi của các giải pháp.
Cơ sở lý thuyết cơ bản
Trong phần này, chúng ta sẽ thảo luận về giản đồ và định lý NFL cùng với giả thuyết khối xây dựng.
Định lý giản đồ
Các nhà nghiên cứu đã cố gắng tìm ra toán học đằng sau hoạt động của các thuật toán di truyền, và Định lý Lược đồ Holland là một bước đi theo hướng đó. Trong nhiều năm, nhiều cải tiến và đề xuất đã được thực hiện đối với Định lý Lược đồ để làm cho nó trở nên tổng quát hơn.
Trong phần này, chúng tôi không đi sâu vào toán học của Định lý Lược đồ, thay vào đó chúng tôi cố gắng phát triển sự hiểu biết cơ bản về Định lý Lược đồ là gì. Các thuật ngữ cơ bản cần biết như sau:
A Schemalà một "mẫu". Về mặt hình thức, nó là một chuỗi trên bảng chữ cái = {0,1, *},
trong đó * không được quan tâm và có thể nhận bất kỳ giá trị nào.
Do đó, * 10 * 1 có thể có nghĩa là 01001, 01011, 11001 hoặc 11011
Về mặt hình học, một lược đồ là một siêu phẳng trong không gian tìm kiếm lời giải.
Order của một giản đồ là số vị trí cố định xác định trong một gen.
Defining length là khoảng cách giữa hai kí hiệu xa nhất cố định trong gen.
Định lý lược đồ cho biết rằng lược đồ này với mức độ phù hợp trên trung bình, độ dài xác định ngắn và bậc thấp hơn có nhiều khả năng tồn tại sự giao nhau và đột biến hơn.
Giả thuyết về khối xây dựng
Các Khối xây dựng là các khối có thứ tự thấp, schemata có độ dài xác định thấp với thể lực trung bình đã cho ở trên. Giả thuyết khối xây dựng nói rằng các khối xây dựng như vậy đóng vai trò là nền tảng cho sự thành công và thích ứng của GAs trong GAs khi nó tiến triển bằng cách xác định và kết hợp liên tiếp các “khối xây dựng” như vậy.
Định lý Không có Bữa trưa Miễn phí (NFL)
Wolpert và Macready vào năm 1997 đã xuất bản một bài báo có tiêu đề "Không có định lý bữa trưa miễn phí để tối ưu hóa." Về cơ bản, nó nói rằng nếu chúng ta tính trung bình trên không gian của tất cả các vấn đề có thể xảy ra, thì tất cả các thuật toán hộp đen không truy cập lại sẽ thể hiện cùng một hiệu suất.
Có nghĩa là chúng ta càng hiểu nhiều vấn đề, GA của chúng ta càng trở nên cụ thể hơn về vấn đề và mang lại hiệu suất tốt hơn, nhưng nó bù đắp lại điều đó bằng cách hoạt động kém hơn đối với các vấn đề khác.
Học máy dựa trên GA
Thuật toán di truyền cũng tìm thấy ứng dụng trong Học máy. Classifier systems là một dạng của genetics-based machine learning(GBML) hệ thống thường được sử dụng trong lĩnh vực máy học. Các phương pháp GBML là một cách tiếp cận thích hợp để học máy.
Có hai loại hệ thống GBML -
The Pittsburg Approach - Trong cách tiếp cận này, một nhiễm sắc thể mã hóa một giải pháp, và do đó tính phù hợp được chỉ định cho các giải pháp.
The Michigan Approach - một giải pháp thường được đại diện bởi nhiều nhiễm sắc thể và do đó sự phù hợp được chỉ định cho các giải pháp từng phần.
Cần lưu ý rằng các vấn đề tiêu chuẩn như giao nhau, đột biến, Lamarckian hoặc Darwin, v.v. cũng có trong hệ thống GBML.