Czy zdefiniowanie punktu zatrzymania algorytmu genetycznego przeczy celowi algorytmu?

Wikipedia określa punkt końcowy GA na ten temat:

Zwykle algorytm kończy się, gdy wyprodukowano maksymalną liczbę pokoleń lub osiągnięto zadowalający poziom sprawności dla populacji. Jeśli algorytm zakończył się z powodu maksymalnej liczby pokoleń, możliwe jest osiągnięcie zadowalającego rozwiązania.

Teraz, jeśli kończy się, gdy osiągnięty zostanie zadowalający poziom sprawności, a Ty definiujesz ten poziom sprawności, dlaczego nie miałbyś po prostu samodzielnie stworzyć „doskonałego” genomu, skoro już znasz cechy tego idealnego genomu?

Chyba jestem tu trochę zdezorientowany. Myślałem, że celem GA jest ciągła ewolucja i pokazanie nam prawdopodobnie jeszcze lepszego rozwiązania niż to, o czym myśleliśmy, a nasza funkcja fitness była po prostu czymś, co pomogło jej po drodze, a nie czymś, co postawiliśmy na postumencie jako zakończenie ” stan idealny. Czy to nie niszczy sensu?

Funkcja fitness ocenia wynik działania algorytmu. Jest całkiem możliwe, aby rozpoznać idealny wynik, gdy go widzisz, ale nie znasz kroków, aby uzyskać taki wynik z dowolnego określonego wejścia. Tam właśnie najbardziej przydatne są algorytmy genetyczne.

Na przykład jedną z popularnych zabawnych aplikacji GA jest tworzenie animacji, która może skutecznie poruszać wirtualnym stworzeniem. Łatwo jest stwierdzić, czy stworzenie porusza się z pewną prędkością w stosunkowo prostej linii. To twoja funkcja fitness. O wiele trudniej jest powiedzieć dokładną sekwencję ruchów „mięśniowych”, aby to zrobić.

Często zdarza się, że można określić przydatność rozwiązania, ale nie można bezpośrednio określić samego rozwiązania. Powiedzmy, że próbujesz ewoluować szybkie króliki, a istnieje garść genów, które wpływają na szybkość królika. Możesz przetestować szybkość królika, ale wyliczenie wszystkich kombinacji genów związanych z prędkością byłoby niepraktyczne. W takim przypadku możesz mieć GA, który ściga króliki i hoduje te najszybsze. Możesz to zrobić wiecznie, ale prawdopodobnie wolisz przestać, gdy:

• znalazłeś królika, który jest szybszy niż X, lub
• przyrostowa poprawa w ciągu n pokoleń spadła poniżej pewnego progu, lub
• hodowałeś króliki przez wiele pokoleń

Cały sens GA to rozwiązanie problemu, który ma ten poziom sprawności. To rozwiązanie byłoby bardzo trudne do znalezienia przy użyciu innych, bardziej konwencjonalnych algorytmów wyszukiwania, dlatego zwykle używasz GA w pierwszej kolejności.

Lub zamiast limitu wartości sprawności możesz zdecydować, ile pokoleń chcesz uruchomić (im więcej pokoleń biegniesz, tym większa szansa na znalezienie coraz wyższych wartości sprawności). Na przykład w przypadku problemu sprzedawcy podróżującego uzyskanie ścieżki o najniższych kosztach między miastami, które należy pokonać.

To, czy stanem zatrzymania jest określony poziom sprawności, który jest akceptowalny, czy też pewne ograniczenie czasowe (uruchamianie GA przez maksymalny okres czasu lub ograniczoną liczbę generacji dla aplikacji o krytycznym czasie, takich jak wyszukiwanie ścieżek lub aplikacje AI), zależy zwykle od problemu domena.

Intuicyjnie celem algorytmu genetycznego jest sformułowanie algorytmicznego rozwiązania problemu, który nie poddaje się prostej analizie logicznej. Po osiągnięciu tego celu GA nie musi już dążyć do celu.

Oczywiście, jeśli pożądana jest lepsza „sprawność”, algorytm genetyczny można uruchomić, aby sprawdzić, czy można znaleźć bardziej zoptymalizowane rozwiązanie, lub sam algorytm genetyczny można dostosować, aby sprawdzić, czy będzie zbierał się na lepszym rozwiązaniu.

Algorytm genetyczny wymaga jakiegoś sposobu na nagrodzenie dobrych genów większą propagacją. Jeśli nie potrafiłeś odróżnić dobrych genów od złych genów, w ogóle nie mógłbyś użyć algorytmu genetycznego.

Aby algorytm genetyczny zadziałał, musisz pozwolić na reprodukcję rozwiązań bardziej dopasowanych niż na mniej dopasowanych. W przeciwnym razie po prostu próbujesz losowych rozwiązań.

Oto typowy przykład z mojego własnego doświadczenia: Opracowując jeden z pierwszych systemów wybierania głosowego, mieliśmy trudności ze znalezieniem algorytmu dopasowującego nazwę mówioną do przechowywanej kopii o tej samej nazwie. Powiedziano nam, że 95% dokładność wybrania jednej nazwy z 25 jest wystarczająca. Mieliśmy zgromadzony korpus ludzi, którzy wypowiadali po 25 nazwisk po 10 razy.

Najpierw opracowaliśmy system wprowadzania, który mierzył długość wypowiadanego słowa i energię częstotliwości w kilku znormalizowanych częściach. Następnie opracowaliśmy algorytm, który przypisywał wagi do dopasowań tych parametrów i porównywał dwa zestawy parametrów na podstawie tych wag.

Teraz mieliśmy ostatni krok - jaka powinna być wartość tych wag?

Stworzyliśmy 1000 losowych zestawów wag i przetestowaliśmy je na ciele. Wyrzuciliśmy 500, którzy spisali się najgorzej. Dla pozostałych 500 powtórzyliśmy każdy z nich, aw jednym z nich losowo podnosiliśmy lub obniżaliśmy jeden z obciążników.

Powtarzaliśmy ten proces na komputerze przez około dwa tygodnie, aż w końcu miał zestaw wag, które spełniały kryterium dokładności 95%. Następnie przetestowaliśmy go na danych nie w korpusie. Dokładność była około 92%. Pobiegliśmy więc dłużej, aby uzyskać 98% dokładność na korpusie, a ten zestaw wag wytworzył 95% dokładności na danych nie w korpusie.

Chodzi o to, że musisz mieć funkcję fitness, aby uruchomić algorytm genetyczny. Jeśli nie możesz odróżnić dobrych genów od złych genów, jak możesz się upewnić, że dobre geny się rozmnażają, a złe geny nie?

Iteruj, aż rozwiązanie nie różni się tak bardzo od poprzedniej wersji iteracji. Za bardzo proszę zrozumieć stałą tolerancję.

Solution in iteration n-6: 600
Solution in iteration n-5: 800
Solution in iteration n-4: 768
Solution in iteration n-3: 780 
Solution in iteration n-2: 778
Solution in iteration n-1: 778.23
Solution in iteration n: 780.18
Solution in iteration n+1: 780.1815

W tym przykładzie, jeśli twoja ustalona tolerancja wynosiła 0,01, to (n + 1) każe ci przestać, ponieważ abs (roztwór (n + 1) - rozwiązanie (n)) <0,01.

Wracając, wtedy twój algorytm może powiedzieć: nie będzie nic lepszego!

Szybka odpowiedź na główne pytanie: Istnieje duża różnica między wiedzą, co chcesz osiągnąć, a wiedzą, jak się tam dostać.

Bardziej szczegółowo, na przykład z jednym z najpopularniejszych problemów rozwiązanych za pomocą algorytmów genetycznych / ewolucyjnych, zwykle studium przypadku w klasie, znajdowanie optymalnej trasy na wykresie. Jest to często używane w sieci, aby znaleźć najtańszą trasę z jednego końca na drugi. Podczas definiowania kosztów (liczba przeskoków, koszt każdego przeskoku itp.) Określasz również koszt docelowy (poziom sprawności), przy którym jesteś zadowolony z wyniku. Twój algorytm może nie znaleźć najlepszego, ale znajdzie optymalne algorytm. Rozumiem przez to, że stosunek kosztów do korzyści znalezienia lepszej odpowiedzi jest zabroniony.

W GA / EA przekonasz się, że normalnym zachowaniem jest bardzo szybkie znalezienie optymalnej odpowiedzi na poziomie 95% +, ale zawężenie ostatnich 5% jest wykładniczo droższe. Zatem teoria polega na tym, że określasz akceptowalne optimum, aby osiągnąć najlepszy wynik w jak najkrótszym czasie. Ponieważ koszt znalezienia, powiedzmy, najwyższy 1%, może przewyższać jego zalety w stosunku do górnych 5%, określasz akceptowalne optymalne.

Podsumowując, nie jesteś teraz odpowiedzią na żaden konkretny problem, po prostu określasz, dla każdego problemu, akceptowalne optimum, punkt, w którym znalezienie lepszej odpowiedzi nie jest praktyczne.

Istnieją badania nad naprawą błędów w C za pomocą algorytmów genetycznych poprzez dostarczenie negatywnych i pozytywnych przypadków testowych jako funkcji fitness, a także złamanego kodu jako danych wejściowych. Jest to przykład problemu, który może rozwiązać człowiek, ale algorytm genetyczny jest łatwiejszy do zrobienia. Ważne jest, aby pamiętać:

Chociaż metody opisane w tym artykule nie rozwijają nowych programów od zera, pokazują, jak ewoluować starsze oprogramowanie do naprawy istniejących błędów.

Jednak nowe programy nie zostały ewoluowały od zera, po prostu nie w C. kilka nietrywialnych programów napisanych w malbolge ezoteryczny język programowania mieć wszystko (do mojej wiedzy) został ewoluowała, nie jest napisane. Język jest zbyt skomplikowany, aby mógł go używać programista, i zbyt skomplikowany, aby skutecznie wydedukować programy z samej logiki, więc większość programów w nim napisanych została stworzona przez algorytmy genetyczne. Funkcja fitness to ogólnie odległość edycji do oczekiwanego wyniku.

W pewnym sensie jest to ładnie okrągłe. Obserwując, że złożony kod genetyczny jest zapisywany przez procesy ewolucyjne, możemy symulować procesy ewolucyjne w celu wytworzenia kodu w innym złożonym języku, nawet nie wiedząc, jak działa kod!