Các thuật toán di truyền có phù hợp với các vấn đề như vấn đề Knuth không?
Chúng ta đều biết rằng Giải thuật di truyền có thể đưa ra một giải pháp tối ưu hoặc gần tối ưu. Vì vậy, trong một số vấn đề như bài toán khó NP, với sự cân bằng giữa thời gian và giải pháp tối ưu, giải pháp gần tối ưu là đủ tốt.
Vì không có gì đảm bảo để tìm ra giải pháp tối ưu, GA có được coi là lựa chọn tốt để giải quyết vấn đề Knuth không?
Theo Trí tuệ nhân tạo: Một cách tiếp cận hiện đại (ấn bản thứ ba), phần 3.2 (trang 73):
Knuth phỏng đoán rằng, bắt đầu với số 4, một chuỗi các phép toán giai thừa, căn bậc hai và tầng sẽ đạt đến bất kỳ số nguyên dương nào mong muốn.
Ví dụ: 5 có thể đạt được từ 4:
tầng (sqrt (sqrt (sqrt (sqrt (sqrt ((4!)!))))))
Vì vậy, nếu chúng ta có một số (5) và chúng ta muốn biết trình tự các phép toán của 3 phép toán đã nêu để đạt đến số đã cho, mỗi gen của nhiễm sắc thể sẽ là một số đại diện cho một phép toán nào đó với một số bổ sung cho (không có phép toán) và hàm thể dục sẽ là sự khác biệt tuyệt đối giữa số đã cho và số mà chúng ta nhận được khi áp dụng các phép toán theo một thứ tự nhất định cho mỗi nhiễm sắc thể (đến min). Hãy coi rằng số lần lặp lại (thế hệ) được thực hiện mà không có giải pháp tối ưu và số gần nhất chúng ta có là 4 (với thể dục 1), vấn đề là chúng ta có thể nhận được 4 từ việc áp dụng không có phép toán nào trên 4 trong khi đối với 5 chúng ta cần nhiều phép toán, vì vậy giải pháp gần tối ưu thậm chí không gần với giải pháp.
Vì vậy, có phải GA không thích hợp cho loại vấn đề này? Hoặc sự biểu diễn của nhiễm sắc thể được đề xuất và chức năng thể dục không đủ tốt?
Trả lời
Trước khi cố gắng trả lời câu hỏi của bạn trực tiếp hơn, hãy để tôi làm rõ điều gì đó.
Mọi người thường sử dụng thuật ngữ di truyền (GA), nhưng trong nhiều trường hợp, ý nghĩa thực sự của chúng là thuật toán tiến hóa (EA), là một tập hợp các thuật toán tối ưu hóa dựa trên dân số (tức là nhiều giải pháp được duy trì cùng một lúc) và các phương pháp tiếp cận lấy cảm hứng từ học thuyết Darwin và sự sống còn của những người khỏe mạnh nhất . GAs là một trong những cách tiếp cận này, trong đó các nhiễm sắc thể là dạng nhị phân và bạn có cả hoạt động đột biến và giao chéo. Có những cách tiếp cận khác, chẳng hạn như chiến lược tiến hóa hoặc lập trình di truyền .
Như bạn cũng đã nhận thấy, EA là siêu kinh nghiệm và, mặc dù có một số nghiên cứu về các thuộc tính hội tụ của chúng [ 1 ], trên thực tế, chúng có thể không hội tụ. Tuy nhiên, khi bất kỳ cách tiếp cận tiềm năng nào khác không thành công, EA chắc chắn có thể hữu ích.
Trong trường hợp của bạn, vấn đề thực sự là để tìm một hình thức đóng (hoặc phân tích ) biểu hiện của một hàm, trong đó bao gồm các chức năng nhỏ khác. Đây thực sự là thứ mà lập trình di truyền (đặc biệt là GP dựa trên cây) được tạo ra. Trên thực tế, bài toán Knuth là một ví dụ cụ thể của bài toán hồi quy tượng trưng , đây là một bài toán điển hình mà GP được áp dụng. Vì vậy, GP có lẽ là cách tiếp cận đầu tiên bạn nên thử.
Trong khi đó, tôi đã triển khai một chương trình đơn giản trong DEAP để cố gắng giải quyết vấn đề Knuth. Kiểm tra nó ở đây . Mức độ phù hợp của giải pháp tốt nhất mà nó đã tìm thấy cho đến nay (với một số hạt giống) là 4 và giải pháp là floor(sqrt(float(sqrt(4))))(ở đây floatchỉ chuyển đổi đầu vào thành một số dấu phẩy động, để đảm bảo an toàn cho kiểu). Tôi đã sử dụng sự khác biệt làm hàm thể dục và chạy thuật toán GP cho 100 thế hệ với 100 cá thể cho mỗi thế hệ (con số này không nhiều!). Tôi đã không tinh chỉnh nhiều thông số siêu, vì vậy, có thể, với hạt giống và siêu thông số phù hợp, bạn có thể tìm ra giải pháp phù hợp.
Về nguyên tắc, để giải quyết các mối quan tâm của bạn, bạn có thể sử dụng mã hóa đó, nhưng như bạn lưu ý, GA thực sự có thể trả về $4$ như là giải pháp tốt nhất (thực ra không phải là cách xa $5$), mà bạn có thể tránh được sự giết hại của tôi, ở mọi thế hệ, bất kỳ cá nhân nào có giá trị đó.
Tôi đã không dành quá nhiều thời gian cho việc thực hiện và suy nghĩ về vấn đề này, nhưng, như tôi đã nói ở trên, ngay cả với lập trình di truyền và chỉ sử dụng các hoạt động của Knuth, nó có thể bị mắc kẹt trong optima cục bộ. Bạn có thể thử tăng cường việc triển khai của tôi (hoặc của bạn) với các phép toán khác, chẳng hạn như phép nhân và phép cộng, và xem liệu điều gì đó có cải thiện hay không.