Temat: Wydajność algorytmów genetycznych

Chciałem znaleźć minimum funkcji kilku zmiennych. Interesowały mnie metody bezgradientowe.I dla takiego zadania postanowiłem sprawdzić to algorytmem genetycznym. Skończyło się porażką. Zainicjowałem pierwsze pokolenie losowymi punktami, rozmnażały się te osobniki dla których wartość funkcji była mniejsza. Okazało się że osobniki dążyły do jednego punktu, ale nie rozwiązania ale najlepszego początkowego osobnika. No tak, nie miałem jeszcze zaimplementowanej mutacji ale co to by dało?
Z tego przykładu wydaje mi się że algorytmy genetyczne to nic innego jak losowe błądzenie,taki bogosearch. Zamiast kolejnych pokoleń mogli byśmy próbkować w kilku miejscach, potem wybrać najlepsze miejsce, losowo próbkować w pobliżu itd. w dosyć wielu miejscach odległych blisko i daleko aby się przybliżyć (co jest czasochłonne). Gdybyśmy szukali tylko blisko, wymagałoby to dużo kroków a gdy daleko to przeskoczylibyśmy. Nie ma czegoś takiego jak dostosowanie kroków, najpierw idziemy w dobrym kierunku dużymi, potem coraz mniejszymi krokami. Algorytm genetyczny to raczej bardzo nieefektywne losowe błądzenie.
Czy jest jakaś implementacja lub rodzaj problemu dla którego algorytmy genetyczne się sprawdzają?

Temat: Wydajność algorytmów genetycznych

Algorytmy genetyczne i ewolucyjne znajdują praktyczne zastosowanie w wielu dziedzinach jednak nie ma i nie będzie szablonowego rozwiązania dla wszystkich problemów .. czasami trzeba kombinować. Polecam zapoznać się z niektórymi pozycjami literaturowymi na amazon.com.

Dla każdego problemu należy określić kodowanie, operatory genetyczne, mechanizm selekcji, itd. To wymaga pewnego doświadczenia, ale nie jest znowu tak skomplikowane :) Poza tym stosuje się dodatkowe techniki takie jak niszowanie, wielokryterialność, zmienna liczebność populacji, etc

Z Twojego opisu wynika jasno, że osobniki zbiegają się w pewnym maksimum lokalnym. Prawdopodobnie odnalezienie maksimum lokalnego jest znacznie prostsze od maksimum globalnego. Kiedy cała populacja zbiegnie się w jednym "punkcie" heurystyka wpada w pułapkę, ponieważ większość mutacji prowadzi do powstania osobników gorszych, które w końcu zostaną odrzucone w procesie selekcji.

Możliwe rozwiązania przedstawionego problemu to zastosowanie niszowania, unikanie odnalezionych wcześniej ekstremów oraz przekształcenie funkcji bazowej funkcją nieliniową.

"Nie ma czegoś takiego jak dostosowanie kroków, najpierw idziemy w dobrym kierunku dużymi, potem coraz mniejszymi krokami."

Tutaj oczywiście się nie zgodzę :) Algorytmy genetyczne i ewolucyjne świetnie radzą sobie z "dostosowaniem wielkości kroku" pod warunkiem doboru odpowiedniego kodowania (polecem kodowanie rzeczywisto-liczbowe bądź logarytmiczne), operatorów krzyżowania, operatorów mutacji oraz prawdopodobieństw mutacji i krzyżowania.

Algorytmy genetyczne i ewolucyjne są jedną z ciekawszych dziedzin informatyki dlatego warto czytać, eksperymentować i korzystać z wyobraźni.

Temat: Wydajność algorytmów genetycznych

Tak - zdecydowanie jest to kwestia swoistego 'wyczucia genetycznego'. Sterowanie krokiem zbieżności algorytmu nie jest może o tyle dobrym posyłem, że w przyrodzie taki mechanizm nie występuje ex-plicite, więc wkraczamy tu na grunt pseud-genetycznych algorytmów. Może nie taki znowu grząski, z uwagi na kilka poważnych opracować z nim związanych, ale na pewno nie do końca 'naturalny'. Zazwyczaj wystarczy dobór odpowiednich współczynników krzyżowania (dość dużego) i mutacji (względnie niskiego) oraz dobór odpowiedniego algorytmu selekcji.
Ja często znajduję algorytm turniejowy lepszym niż oparty na 'ruletce'; spróbuj - może dla Twojego zadania także okaże się bardziej przydatny.

Co do losowości algorytmów genetycznych:
Rzeczywiście przy pewnych ustawieniach parametrów algorytmy genetyczne stają się bardziej błądzeniem losowym niż przy innych. Głownie jeśli przesadzimy ze współczynnikiem mutacji. Przetestuj swój algorytm przy niskim prawdopodobieństwie mutacji (1/100 dla pojedynczej loci) oraz dość dużego wsp. krzyżowania (ok. 1/2 dla pary genów).