Thuật toán di truyền - Giới thiệu
Thuật toán di truyền (GA) là một kỹ thuật tối ưu hóa dựa trên tìm kiếm dựa trên các nguyên tắc của Genetics and Natural Selection. Nó thường được sử dụng để tìm giải pháp tối ưu hoặc gần tối ưu cho các vấn đề khó khăn mà nếu không sẽ mất cả đời để giải quyết. Nó thường được sử dụng để giải quyết các vấn đề tối ưu hóa, trong nghiên cứu và học máy.
Giới thiệu về Tối ưu hóa
Tối ưu hóa là quá trình making something better. Trong bất kỳ quá trình nào, chúng ta có một tập hợp các đầu vào và một tập hợp các đầu ra như trong hình sau.
Tối ưu hóa đề cập đến việc tìm kiếm các giá trị của đầu vào theo cách mà chúng tôi nhận được giá trị đầu ra "tốt nhất". Định nghĩa "tốt nhất" thay đổi theo từng vấn đề, nhưng trong thuật ngữ toán học, nó đề cập đến việc tối đa hóa hoặc tối thiểu hóa một hoặc nhiều hàm mục tiêu, bằng cách thay đổi các tham số đầu vào.
Tập hợp tất cả các giải pháp hoặc giá trị có thể có mà đầu vào có thể chiếm không gian tìm kiếm. Trong không gian tìm kiếm này, nằm một điểm hoặc một tập hợp các điểm đưa ra giải pháp tối ưu. Mục đích của việc tối ưu hóa là tìm điểm đó hoặc tập hợp các điểm trong không gian tìm kiếm.
Thuật toán di truyền là gì?
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.
GA đượ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ó pool or a population of possible solutionscho 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 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à sinh ra 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 đạ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, nhưng 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 và cả 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ó một số lượng lớn các 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 các thuật toán di truyền trở nên hấp dẫn để sử dụng trong việc giải các bài toá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 có một vấn đề rất phức tạp được gọi là cảnh quan, được tạo thành từ nhiều đỉnh và nhiều thung lũng, khiến các phương pháp như vậy không thành công, vì chúng có xu hướng cố hữu là mắc kẹt ở hệ tối ưu cục bộ. như 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 Nhân viên 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à phải mất 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 đó giải pháp “đủ tốt”, được cung cấp “nhanh chóng” là điều cần thiết.