Trong lĩnh vực trí tuệ nhân tạo, thuật toán tiến hóa (EA) là một tập hợp con của các phép tính tổng dân số dựa trên tối ưu hóa metaheuristic. EA sử dụng các cơ chế lấy cảm hứng từ sự phát triển sinh học như sinh sản, đột biến, tái tổ hợp và chọn lọc. Giải pháp ứng viên trong vấn đề thuật toán tối ưu hóa tiến hóa đóng vai trò của các cá thể trong quần thể. Và chức năng thể dục cũng quyết định chất lượng của các câu trả lời.
Các thuật toán tiến hóa thường gần đúng các giải pháp cho tất cả các dạng bài toán. Bởi vì lý tưởng nhất là họ không đưa ra bất kỳ giả định nào về bối cảnh thể dục tiềm ẩn. Các phương pháp được sử dụng để mô hình hóa tiến hóa và thuật toán di truyền thường được giới hạn trong các nghiên cứu về các quá trình vi cách mạng và lập kế hoạch mô hình dựa trên các giai đoạn tế bào. Trong hầu hết các ứng dụng EA thực, độ phức tạp tính toán là một yếu tố nghiêm trọng.
Thực ravấn đề này liên quan đến ước tính chức năng thể dục. Tính gần đúng thể lực là một trong những giải pháp để khắc phục khó khăn này. Tuy nhiên, một EA có vẻ đơn giản có thể giải quyết các vấn đề thường phức tạp. Do đó, không thể có mối quan hệ trực tiếp giữa mức độ phức tạp của trình tự và vấn đề. Bạn có thể tìm thêm thông tin chi tiết trong sách "Thuật toán tiến hóa".
Thực hiện
Bước một là tạo ngẫu nhiên một quần thể cá thể ban đầu.
Bước hai là đánh giá mức độ phù hợp của từng cá nhân trong nhóm này (thời hạn, sự chuẩn bị đầy đủ, v.v.).
Bước ba - lặp lại các bước tái tạo sau để hoàn thành:
- Chọn những người phù hợp nhất để lai tạo (bố mẹ).
- Mang lại những cá thể mới đã vượt qua thuật toán tiến hóa bằng cách sử dụng trao đổi chéo và đột biến để tạo ra thế hệ con cái.
- Đánh giá thể lực cá nhân của những người mới.
- Thay thế nhóm ít phù hợp nhất bằng họ.
Loại
Thuật toán Di truyền là một trình tự tiến hóa, là loại Cố vấn Chuyên gia phổ biến nhất. Giải pháp cho vấn đề được tìm kiếm dưới dạng chuỗi số (theo truyền thống là hệ nhị phân, mặc dù các biểu diễn tốt nhất thường là những biểu diễn phản ánh nhiều hơn vấn đề đang được giải quyết) bằng cách áp dụng các toán tử như tái tổ hợp và đột biến (đôi khi là một, trong một số trường hợp là cả hai). Loại Cố vấn Chuyên gia này thường được sử dụng trong các bài toán tối ưu hóa. Một tên khác của nó là fetura (từ tiếng Latinh có nghĩa là "sinh"):
- Lập trình di truyền. Nó trình bày các giải pháp dưới dạng mã máy tính và tính phù hợp của chúng được xác định bởi khả năng thực hiện các tác vụ tính toán của chúng.
- Lập trình tiến hóa. Tương tự như thuật toán di truyền tiến hóa, nhưng cấu trúc là cố định và các thông số số của nó có thể thay đổi.
- Lập trình biểu hiện gen. Phát triển các ứng dụng máy tính, nhưng khám phá hệ thống kiểu gen-kiểu hình, nơi các dự án có kích thước khác nhau được mã hóa trên nhiễm sắc thể tuyến tính có chiều dài cố định.
- Chiến lược. Làm việc với các vectơ của số thực như là biểu diễn của các nghiệm. Thường sử dụng các thuật toán tỷ lệ đột biến tiến hóa tự thích nghi.
- Phát triển khác biệt. Dựa trên sự khác biệt về vectơ và do đó chủ yếu phù hợp cho các bài toán tối ưu hóa số.
- Neuroevolution. Tương tự như lập trình tiến hóa và thuật toán di truyền. Nhưng sau đó là các mạng nơ-ron nhân tạo, mô tả cấu trúc và trọng lượng của các kết nối. Mã hóa bộ gen có thể trực tiếp hoặc gián tiếp.
So sánh với các quá trình sinh học
Một hạn chế có thể có của nhiều thuật toán tiến hóa là thiếu sự phân biệt rõ ràng giữa kiểu gen và kiểu hình. Trong tự nhiên, một quả trứng được thụ tinh sẽ trải qua một quá trình phức tạp được gọi là quá trình hình thành phôi để trở nên trưởng thành. Việc mã hóa gián tiếp này được cho là giúp các tìm kiếm di truyền đáng tin cậy hơn (tức là ít có khả năng gây ra đột biến chết người hơn) và cũng có thể cải thiện khả năng phát triển của sinh vật. Như vậy là gián tiếp (nói cách khác,mã hóa sinh hoặc phát triển) cũng cho phép quá trình tiến hóa khai thác tính ổn định trong môi trường.
Công việc gần đây trong hệ thống phát triển hoặc hình thành phôi nhân tạo tìm cách giải quyết những vấn đề này. Khi lập trình biểu hiện gen, vùng kiểu gen-kiểu hình được khám phá thành công, trong đó vùng đầu tiên bao gồm các nhiễm sắc thể đa gen tuyến tính có chiều dài cố định và vùng thứ hai gồm nhiều cây biểu hiện hoặc chương trình máy tính có kích thước và hình dạng khác nhau.
Kỹ thuật liên quan
Thuật toán bao gồm:
- Tối ưu hóa đàn kiến. Nó dựa trên ý tưởng rằng côn trùng tìm kiếm thức ăn bằng cách kết nối với pheromone để tạo thành đường dẫn. Chủ yếu thích hợp cho các bài toán tối ưu hóa tổ hợp và đồ thị.
- Thuật toán thanh trượt gốc. Người sáng tạo đã lấy cảm hứng từ chức năng của rễ cây trong tự nhiên.
- Thuật toán cho đàn ong nhân tạo. Dựa vào tập tính của ong mật. Nó chủ yếu được đề xuất để tối ưu hóa số và được mở rộng để giải các bài toán tổ hợp, giới hạn và đa mục tiêu. Thuật toán ong dựa trên hành vi kiếm ăn của côn trùng. Nó đã được áp dụng trong nhiều ứng dụng như định tuyến và lập lịch.
- Tối ưu hóa bầy đàn - dựa trên ý tưởng về hành vi của đàn động vật. Và cũng chủ yếu thích hợp cho các tác vụ quy trình số.
Các phương pháp metaheuristic phổ biến khác
- Săn tìm. Một phương pháp dựa trên việc bắt nhóm một số động vật nhất định, chẳng hạn như chó sói, chẳng hạnphân phối nhiệm vụ của chúng để bao vây con mồi. Mỗi thành viên của thuật toán tiến hóa liên quan đến những người khác theo một cách nào đó. Điều này đặc biệt đúng đối với người lãnh đạo. Đây là một phương pháp tối ưu hóa liên tục được điều chỉnh như một phương pháp quy trình tổ hợp.
- Tìm kiếm theo số đo. Không giống như các phương pháp metaheuristic dựa trên bản chất, thuật toán quy trình thích ứng không sử dụng phép ẩn dụ làm nguyên tắc chính của nó. Thay vào đó, nó sử dụng một phương pháp hướng hiệu suất đơn giản dựa trên việc cập nhật tham số tỷ lệ thứ nguyên tìm kiếm ở mỗi lần lặp. Thuật toán Firefly được lấy cảm hứng từ cách các con đom đóm thu hút nhau bằng ánh sáng nhấp nháy của chúng. Điều này đặc biệt hữu ích cho việc tối ưu hóa đa phương thức.
- Tìm kiếm sự đồng điệu. Dựa trên những ý tưởng về hành vi của các nhạc sĩ. Trong trường hợp này, các thuật toán tiến hóa là cách để tối ưu hóa tổ hợp.
- Gaussian thích ứng. Dựa trên lý thuyết thông tin. Được sử dụng để tối đa hóa hiệu suất và tính khả dụng trung bình. Một ví dụ về các thuật toán tiến hóa trong tình huống này: entropy trong nhiệt động lực học và lý thuyết thông tin.
Memetic
Một phương pháp lai dựa trên ý tưởng về meme của Richard Dawkins. Nó thường có dạng một thuật toán dựa trên tập hợp kết hợp với các quy trình học tập riêng lẻ có khả năng thực hiện các sàng lọc cục bộ. Nhấn mạnh việc sử dụng kiến thức về vấn đề cụ thể và nỗ lực tổ chức các tìm kiếm chi tiết và toàn cầu theo cách tổng hợp.
Tiến hóathuật toán là một phương pháp tiếp cận theo phương pháp heuristic đối với các vấn đề không thể dễ dàng giải quyết trong thời gian đa thức, chẳng hạn như các bài toán khó NP cổ điển và bất kỳ vấn đề nào khác sẽ mất quá nhiều thời gian để xử lý một cách thấu đáo. Khi được sử dụng độc lập, chúng thường được sử dụng cho các bài toán tổ hợp. Tuy nhiên, các thuật toán di truyền thường được sử dụng song song với các phương pháp khác, hoạt động như một cách nhanh chóng để tìm ra nhiều điểm khởi đầu tối ưu để làm việc.
Tiền đề của thuật toán tiến hóa (được gọi là một cố vấn) khá đơn giản vì bạn đã quen thuộc với quá trình chọn lọc tự nhiên. Nó bao gồm bốn bước chính:
- khởi tạo;
- lựa chọn;
- toán tử di truyền;
- kết thúc.
Mỗi bước này gần như tương ứng với một khía cạnh nhất định của chọn lọc tự nhiên và cung cấp những cách dễ dàng để mô-đun hóa danh mục thuật toán đó. Nói một cách đơn giản, trong EA, những thành viên khỏe mạnh nhất sẽ sống sót và sinh sản, trong khi những thành viên không phù hợp sẽ chết và không đóng góp vào nguồn gen của thế hệ tiếp theo.
Khởi tạo
Để bắt đầu thuật toán, trước tiên bạn phải tạo một tập hợp các giải pháp. Tập hợp sẽ chứa một số lượng tùy ý các câu lệnh vấn đề có thể xảy ra, thường được gọi là các thành viên. Chúng thường được tạo ra một cách ngẫu nhiên (trong những ràng buộc của nhiệm vụ) hoặc, nếu một số kiến thức trước đó đã được biết đến, chủ yếu tập trung vào những gì được coi là lý tưởng. Điều quan trọng là dân số bao gồm nhiều giải pháp,vì bản chất nó là một vốn gen. Do đó, nếu muốn khám phá nhiều khả năng khác nhau trong một thuật toán, người ta nên cố gắng có nhiều gen khác nhau.
Lựa chọn
Khi quần thể đã được tạo, các thành viên của nó bây giờ phải được đánh giá theo chức năng thể dục. Hàm thể dục lấy các đặc điểm của một thành viên và đưa ra một đại diện bằng số về mức độ phù hợp của thành viên đó. Tạo chúng thường có thể rất khó khăn. Điều quan trọng là phải tìm một hệ thống tốt thể hiện chính xác dữ liệu. Điều này là rất cụ thể cho vấn đề. Bây giờ cần phải tính toán mức độ phù hợp của tất cả những người tham gia và chọn một số thành viên tốt nhất.
Nhiều chức năng mục tiêu
EAs cũng có thể được mở rộng để sử dụng các hệ thống này. Điều này làm phức tạp quá trình một chút, bởi vì thay vì xác định một điểm tối ưu, một tập hợp sẽ thu được khi sử dụng chúng. Tập hợp các giải pháp được gọi là biên giới Pareto và chứa các yếu tố phù hợp như nhau theo nghĩa không cái nào vượt trội cái nào.
Toán tử di truyền
Bước này bao gồm hai bước phụ: trao đổi chéo và đột biến. Sau khi chọn các cụm từ tốt nhất (thường là 2 cụm từ hàng đầu, nhưng con số này có thể thay đổi), chúng hiện được sử dụng để tạo thế hệ tiếp theo trong thuật toán. Bằng cách áp dụng những đặc điểm của những bậc cha mẹ đã chọn, những đứa trẻ mới được tạo ra là một hỗn hợp các phẩm chất. Điều này thường có thể khó khăn tùy thuộc vào loại dữ liệu, nhưng thường là trong các bài toán tổ hợphoàn toàn có thể trộn và xuất các kết hợp hợp lệ.
Bây giờ nó là cần thiết để đưa vật liệu di truyền mới vào thế hệ. Nếu không thực hiện bước quan trọng này, nhà khoa học sẽ rất nhanh chóng bị mắc kẹt trong các cực trị cục bộ và không thu được kết quả tối ưu. Bước này là một đột biến, và nó được thực hiện khá đơn giản, thay đổi một phần nhỏ của con cái theo cách mà chúng chủ yếu không phản ánh tập hợp con của các gen của cha mẹ. Sự đột biến thường xảy ra theo xác suất, vì xác suất mà một đứa trẻ sẽ mắc phải nó, cũng như mức độ nghiêm trọng của nó, được xác định bởi phân phối.
Chấm dứt
Cuối cùng thì thuật toán cũng phải kết thúc. Điều này thường xảy ra trong hai trường hợp: hoặc đã đạt đến một số thời gian thực thi tối đa hoặc đã đạt đến ngưỡng hiệu suất. Tại thời điểm này, giải pháp cuối cùng được chọn và trả về.
Ví dụ về các thuật toán tiến hóa
Bây giờ, để minh họa kết quả của quá trình này, bạn cần phải gặp cố vấn thực hiện. Để làm được điều này, chúng ta có thể nhớ lại cách nhiều thế hệ khủng long đã học cách đi bộ (dần dần làm chủ đất), tối ưu hóa cấu trúc của cơ thể và vận dụng sức mạnh cơ bắp. Mặc dù những loài bò sát thế hệ đầu không thể đi lại, nhưng cố vấn đã có thể tiến hóa chúng theo thời gian thông qua đột biến và giao thoa thành một dạng có thể đi lại.
Các thuật toán này ngày càng trở nên phù hợp trong thế giới hiện đại, khi các giải pháp dựa trên chúng ngày càng được sử dụng nhiều hơn trong các ngành như tiếp thị kỹ thuật số, tài chính vàchăm sóc sức khỏe.
Địa bàn được sử dụng ở đâu?
Rộng hơn, các thuật toán tiến hóa được sử dụng trong nhiều ứng dụng như xử lý hình ảnh, định tuyến phương tiện, tối ưu hóa thông tin di động, phát triển phần mềm và thậm chí cả đào tạo mạng nơ-ron nhân tạo. Những công cụ này là trung tâm của nhiều ứng dụng và trang web mà mọi người sử dụng hàng ngày, bao gồm Google Maps và thậm chí cả các trò chơi như The Sims. Ngoài ra, lĩnh vực y tế sử dụng EA để giúp đưa ra các quyết định lâm sàng liên quan đến điều trị ung thư. Trên thực tế, các thuật toán tiến hóa rất mạnh mẽ đến mức chúng có thể được sử dụng để giải quyết hầu hết mọi vấn đề về tối ưu hóa.
Định luật Moore
Sự phổ biến ngày càng tăng của EO được thúc đẩy bởi hai yếu tố chính: khả năng tính toán sẵn có và sự tích lũy các bộ dữ liệu lớn. Điều đầu tiên có thể được mô tả bằng Định luật Moore, về cơ bản nói rằng lượng sức mạnh tính toán trong một máy tính tăng gấp đôi khoảng hai năm một lần. Dự đoán này đã được tổ chức trong nhiều thập kỷ. Yếu tố thứ hai liên quan đến sự phụ thuộc ngày càng lớn vào công nghệ, cho phép các tổ chức thu thập một lượng lớn dữ liệu đáng kinh ngạc, cho phép họ phân tích xu hướng và tối ưu hóa sản phẩm.
Các thuật toán tiến hóa có thể giúp gì cho các nhà tiếp thị?
Điều kiện thị trường đang thay đổi nhanh chóng và rất cạnh tranh. Điều này đã buộc các nhà quản lý tiếp thị phải cạnh tranh để đưa ra quyết định tốt hơn. Tăng sẵn cósức mạnh tính toán đã khiến người lao động sử dụng EA để giải quyết vấn đề.
Tối ưu hóa chuyển đổi
Một trong những mục tiêu chính là tăng tỷ lệ người truy cập vào trang web. Vấn đề này tập trung vào việc tối ưu hóa số lượng người dùng làm những gì nhà tiếp thị muốn. Ví dụ: nếu một công ty bán máy tính xách tay, lý tưởng nhất là tăng số lượng khách truy cập trang web cuối cùng mua sản phẩm. Đây là bản chất của việc tối ưu hóa tỷ lệ chuyển đổi.
Một trong những khía cạnh quan trọng đáng ngạc nhiên là sự lựa chọn giao diện người dùng. Nếu thiết kế web không thân thiện với người dùng, sẽ có những người cuối cùng không mua sản phẩm vì lý do này hay lý do khác. Mục tiêu sau đó là giảm số lượng người dùng cuối cùng không chuyển đổi, điều này làm tăng lợi nhuận tổng thể.
