Mạng nơron nhân tạo - Thuật toán di truyền
Thiên nhiên luôn là nguồn cảm hứng dồi dào cho cả nhân loại. Thuật toán di truyền (GA) là thuật toán tìm kiếm dựa trên các khái niệm về chọn lọc tự nhiên và di truyền. GA là một tập con của một nhánh tính toán lớn hơn nhiều, được gọi làEvolutionary Computation.
GAs được phát triển bởi John Holland cùng các sinh viên và đồng nghiệp của ông tại Đại học Michigan, nổi bật nhất là David E. Goldberg và kể từ đó đã được thử nghiệm trên các vấn đề tối ưu hóa khác nhau với mức độ thành công cao.
Trong GAs, chúng tôi có một nhóm hoặc một tập hợp các giải pháp khả thi cho vấn đề đã cho. Các giải pháp này sau đó trải qua quá trình tái tổ hợp và đột biến (giống như trong di truyền tự nhiên), tạo ra những đứa trẻ mới và quá trình này được lặp lại qua nhiều thế hệ khác nhau. Mỗi cá thể (hoặc giải pháp ứng cử viên) được chỉ định một giá trị phù hợp (dựa trên giá trị hàm mục tiêu của nó) và các cá thể phù hợp có cơ hội giao phối cao hơn và mang lại nhiều cá thể “hợp lứa” hơn. Điều này phù hợp với Lý thuyết của Darwin về “Sự sống sót của những người khỏe mạnh nhất”.
Bằng cách này, chúng tôi tiếp tục “phát triển” các cá nhân hoặc giải pháp tốt hơn qua nhiều thế hệ, cho đến khi chúng tôi đạt được tiêu chí dừng.
Các thuật toán di truyền về bản chất là đủ ngẫu nhiên, tuy nhiên chúng hoạt động tốt hơn nhiều so với tìm kiếm cục bộ ngẫu nhiên (trong đó chúng tôi chỉ thử các giải pháp ngẫu nhiên khác nhau, theo dõi các giải pháp tốt nhất cho đến nay), vì chúng cũng khai thác thông tin lịch sử.
Ưu điểm của GAs
GA có nhiều lợi thế khác nhau đã làm cho chúng trở nên vô cùng phổ biến. Chúng bao gồm -
Không yêu cầu bất kỳ thông tin phái sinh nào (có thể không có sẵn cho nhiều vấn đề trong thế giới thực).
Nhanh hơn và hiệu quả hơn so với các phương pháp truyền thống.
Có khả năng song song rất tốt.
Tối ưu hóa cả các chức năng liên tục và rời rạc cũng như các bài toán đa mục tiêu.
Cung cấp danh sách các giải pháp “tốt” chứ không chỉ là một giải pháp duy nhất.
Luôn nhận được câu trả lời cho vấn đề, vấn đề này sẽ tốt hơn theo thời gian.
Hữu ích khi không gian tìm kiếm rất lớn và có nhiều tham số liên quan.
Hạn chế của GAs
Giống như bất kỳ kỹ thuật nào, GAs cũng gặp phải một số hạn chế. Chúng bao gồm -
GAs không phù hợp cho tất cả các vấn đề, đặc biệt là các vấn đề đơn giản và có sẵn thông tin phái sinh.
Giá trị thể chất được tính toán nhiều lần, có thể tốn kém về mặt tính toán đối với một số vấn đề.
Là ngẫu nhiên, không có gì đảm bảo về tính tối ưu hoặc chất lượng của giải pháp.
Nếu không được triển khai đúng cách, GA có thể không hội tụ thành giải pháp tối ưu.
GA - Động lực
Thuật toán di truyền có khả năng cung cấp một giải pháp “đủ tốt” “đủ nhanh”. Điều này làm cho Gas trở nên hấp dẫn để sử dụng trong việc giải quyết các vấn đề tối ưu hóa. Các lý do tại sao GAs là cần thiết như sau:
Giải quyết các vấn đề khó khăn
Trong khoa học máy tính, có một loạt các vấn đề, đó là NP-Hard. Điều này về cơ bản có nghĩa là, ngay cả những hệ thống máy tính mạnh nhất cũng phải mất một thời gian rất dài (thậm chí hàng năm!) Để giải quyết vấn đề đó. Trong trường hợp như vậy, GAs chứng tỏ là một công cụ hiệu quả để cung cấpusable near-optimal solutions trong một khoảng thời gian ngắn.
Thất bại của các phương pháp dựa trên Gradient
Các phương pháp dựa trên giải tích truyền thống hoạt động bằng cách bắt đầu tại một điểm ngẫu nhiên và bằng cách di chuyển theo hướng của gradient, cho đến khi chúng ta lên đến đỉnh đồi. Kỹ thuật này hiệu quả và hoạt động rất tốt cho các hàm mục tiêu một đỉnh như hàm chi phí trong hồi quy tuyến tính. Tuy nhiên, trong hầu hết các tình huống thực tế, chúng ta gặp một vấn đề rất phức tạp được gọi là cảnh quan, được tạo bởi nhiều đỉnh và nhiều thung lũng, khiến các phương pháp này không thành công, vì chúng có xu hướng cố hữu là bị mắc kẹt tại optima cục bộ như được hiển thị trong hình sau.
Nhận giải pháp tốt nhanh chóng
Một số bài toán khó như Bài toán Người bán hàng Đi du lịch (TSP), có các ứng dụng trong thế giới thực như tìm đường và Thiết kế VLSI. Bây giờ, hãy tưởng tượng rằng bạn đang sử dụng hệ thống Định vị GPS của mình và mất vài phút (hoặc thậm chí vài giờ) để tính toán đường đi “tối ưu” từ nguồn đến đích. Sự chậm trễ trong các ứng dụng trong thế giới thực như vậy là không thể chấp nhận được và do đó, một giải pháp “đủ tốt”, được cung cấp “nhanh chóng” là điều cần thiết.
Cách sử dụng GA cho các vấn đề về tối ưu hóa?
Chúng ta đã biết rằng tối ưu hóa là một hành động làm cho một cái gì đó như thiết kế, tình huống, tài nguyên và hệ thống hiệu quả nhất có thể. Quá trình tối ưu hóa được hiển thị trong sơ đồ sau.
Các giai đoạn của Cơ chế GA cho quá trình tối ưu hóa
Tiếp theo là các giai đoạn của cơ chế GA khi được sử dụng để tối ưu hóa các vấn đề.
Tạo quần thể ban đầu một cách ngẫu nhiên.
Chọn giải pháp ban đầu với các giá trị phù hợp nhất.
Kết hợp lại các giải pháp đã chọn bằng cách sử dụng các toán tử đột biến và chéo.
Đưa con lai vào quần thể.
Bây giờ nếu điều kiện dừng được đáp ứng, sau đó trả lại giải pháp với giá trị thể lực tốt nhất của họ. Nếu không, hãy chuyển sang bước 2.