Standardowy algorytm genetyczny, optymalizacja funkcji 1 zmiennej

Witam,
Piszę program do optymalizacji funkcji 1 zmiennej jako wprowadzenie do algorytmów genetycznych.

Najpierw generuje populację, następnie oceniam ją, krzyżuje i dokonuje mutacji. To mam już zaimplementowane. Po tym etapie należy ponownie ocenić populację.

Należy zapamiętać najlepszego osobnika. Jak go rozpoznać? Moim zdaniem najlepszy osobnik będzie to ten, który ma największą wartość funkcji fitness, czyli funkcji, którą optymalizuję.

Aby go szybko znaleźć posortuje malejąco wartość nowej populacji po wartości fitness. Zgadza się?

Pozdrawiam.

Tak, najlepszy osobnik to taki który ma najlepszy fitness. Nie musisz sortować populacji żeby znaleźć tam maksa. Szukanie maksa to O(n) a sortowanie O(nlogn).

Ok, dzięki.

Zastanawia mnie jeszcze, dlaczego algorytm genetyczny bywa rozbieżny dla małych populacji. Im większa populacja, tym jest stabilniejszy.

Są dwa wyjścia:
a) bug
b) jest to porównanie z genetyką, krzyżowanie osobników spokrewnionych powoduje, że gorsze geny się dostają do puli rozwiązań (są losowane), stąd algorytm stanie się rozbieżny

Jak masz małą populację to masz przecież bardzo słabe przeczesywanie terenu, logiczne więc że mogą nie znaleźć tego czego szukasz.
Mutacja służy do tego żeby osobniki eksplorowały "nowe tereny", a rozmiar populacji służy do tego żeby osobniki dobrze przeczesywały teren na którym są.
Oczywiście jak dasz za dużą populację to klops, bo wtedy mutant ma problem żeby "wyciągnać" populację z ekstremum lokalnego w swoim kierunku ;]

Dość fajnie działa to dla 1 zmiennej, ale do końca nie rozumiem dlaczego miałbym używać algorytmu genetycznego.

Temat jest ciekawy, ale wydaje się mało praktyczny.

Jaka jest główna idea?
Moim zdaniem główna idea to skonstruować fitness tak, aby wartość była największa/najmniejsza. I tak dostosowuje ogólny algorytm genetyczny pod dowolny problem.

Myślę sobie po co miałbym to robić skoro mam normalne algorytmy, które gwarantują rozwiązanie w tym samym czasie.

@PewienStudent WTF?
Cel algorytmu genetycznego, jak i każdego innego optymalizacyjnego, to znalezienie maksimum globalnego albo przynajmniej jakiegoś dobrego ekstremum lokalnego. Szukasz nie fitnessu tylko argumentów (osobnika w tym przypadku) dla których fitness jest największy.
Co do drugiego pytania: bo tych algorytmów nie używa się do szukania ekstremów funkcji 1 zmiennej. Używa się ich jak metod "ostatniej szansy" dla problemów dla których nie ma szybkich algorytmów ;] Klasyczna sprawa - szukanie ekstremów funkcji np. 50 czy 100 wymiarowych.

Tu masz 2 wymiarową funkcję Rastrigina:
http://upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Rastrigin_function.png/300px-Rastrigin_function.png
Ma ona ogólny wzór dla n-wymiarów i często na jej przykładzie testuje się algorytmy genetyczne. To jest funkcja dla której ekstremum jest znane, ale jest fajna bo ma całą masę ekstremów lokalnych.

Przykłady problemów których nie da się rozwiązywać szybkimi metodami dokładnymi? Zasadniczo wszystkie NP-trudne problemy. Na przykład:
http://en.wikipedia.org/wiki/Job_shop_scheduling

Dziękuje za Twoją wyczerpującą wypowiedź.

Pisząc: "Moim zdaniem główna idea to skonstruować fitness tak, aby wartość była największa/najmniejsza" miałem na myśli fitness tak, aby zagadnienie modelowało nasz problem optymalizacyjny.

Napisałeś:
"Szukasz nie fitnessu tylko argumentów (osobnika w tym przypadku) dla których fitness jest największy."
Wiem, że optymalizacja. Ale najpierw chyba muszę wiedzieć co optymalizuję, czyli znaleźć wzór funkcji (to miałem na myśli pisząc szukam fitnessu).

Czy mi się tylko wydaje, czy optymalizowanie funkcji wielowymiarowych jest podobnie proste jak jednowymiarowych, ponieważ można je łatwo przedstawić jako chromosomy binarne.

Jak to w życiu, w praktyce pewnie nie jest to takie łatwe. Już wiem na jakiej funkcji będę testował. Na co powinienem uważać przechodząc na większą ilość wymiarów? Nową populację wyznaczam metodą ruletki. Operator mutacji zostawiłbym taki sam (po prostu zmieniam losowy bit). Intuicja podpowiada, że wystarczy zmodyfikować operator krzyżowania (wedle kreatywności tak, aby nie wpadał w ekstrema lokalne) i fitness tak, aby liczyło funkcję wielu zmiennych, a nie jednej.

No tak, fitness musi odpowiadać twojemu problemowi, to raczej oczywiste :) Tylko że w realnych przypadkach to nie jest żaden prosty "wzór funkcji".

Czy mi się tylko wydaje, czy optymalizowanie funkcji wielowymiarowych jest podobnie proste jak jednowymiarowych, ponieważ można je łatwo przedstawić jako chromosomy binarne.

W sensie implementacji tak, niewiele się to różni. Ale w sensie obliczania wcale nie jest to takie "proste" ;]
Poza tym o ile mutacja to może być zmiana jednego bitu, o tyle krzyżowanie przez "sklejanie" przeciętych osobników jest już słabe. Często stosuje się przy krzyżowaniu np. obliczanie "średniej" z osobnika. Bo chodzi o to że krzyżowanie zakłada że jak łączymy dwa dobre osobniki to powinniśmy dostać dobrego osobnika "pomiędzy nimi". Gdybyśmy sklejali przecięte binarne reprezentacje to właściwie efekt byłby random ;)
Fitness trzeba tak wymyślić żeby liczył się szybko, bo będzie obliczany tysiące / miliony razy.

PewienStudent napisał(a):

Czy mi się tylko wydaje, czy optymalizowanie funkcji wielowymiarowych jest podobnie proste jak jednowymiarowych, ponieważ można je łatwo przedstawić jako chromosomy binarne.

Jeśli chcesz trochę trudniejsze zadanie to weź na warsztat optymalizację więcej niż jednej funkcji NARAZ, całkiem ciekawe (MOGA).

Zastanawia mnie jeszcze, dlaczego algorytm genetyczny bywa rozbieżny dla małych populacji. Im większa populacja, tym jest stabilniejszy.

Użyj strategii elitarnej. To Ci pomoże w "rozbieganiu" się populacji.
Ale przy małej populacji i tak ewolucja będzie prawdopodobnie wolna - w zależności od problemu.