Optymalizacja, algorytmy genetyczne a „No Free Lunch”. PDF Drukuj Email

Wykładowca: Stefan Kotowski

W końcu XX wieku (1997) zostało opublikowane nowe twierdzenie o „ niemożności” nazwane „No Free Lunch”theorem. Ustala ono , że nie istnieje najlepszy uniwersalny algorytm optymalizacyjny (dla wszystkich zadań). Niezależnie od miary jakości algorytmu optymalizacyjnego, dowolne dwa różne algorytmy optymalizacyjne zachowują się „średnio” tak samo dla wszystkich zadań optymalizacyjnych. Twierdzenie to natychmiast stało się przedmiotem sporów i dociekań, a jego rozumienie i interpretacja jest dalej tematem badań i dyskusji. Powstało szereg kolejnych wyników uściślających jego tezy, a najciekawszym jest warunek domkniętości względem permutacji funkcji, oraz koewolucyjne „FreeLunches”, a także wyznaczenie klas zadań dla których nie jest ono spełnione.
Jednym ze sposobów i prób obejścia „No Free lunch” jest konstrukcja algorytmów optymalizacyjnych naśladujących naturę. Zaowocowało to powstaniem algorytmów ewolucyjnych, których operatory mutacji, krzyżowania i selekcji działają na populacjach (multizbiorach). Jednym z pierwszych algorytmów ewolucyjnych są algorytmy genetyczne. Ich cechą charakterystyczną jest binarne kodowanie argumentów funkcji (osobników). Są one zapisywane w postaci ciągu binarnego o określonej długości. Mechanizm działania algorytmów genetycznych możemy opisać jako łańcuch Markowa z operatorem Markowa w postaci macierzy działającej na wektorze prawdopodobieństwa populacji. Taki łańcuch markowa jest asymptotycznie stabilny i ma stacjonarny rozkład prawdopodobieństwa, oraz jest on jedyny. Możemy przyjąć, że rozkład stacjonarny jest osiągany przez algorytm genetyczny po nieskończonej liczbie kroków (pokoleń).
Istnieją wyniki pozwalające na opisanie operatora granicznego algorytmu genetycznego. Operator taki w jednym kroku generuje rozkład graniczny (stacjonarny) niezależnie od rozkładu początkowego. Byłby więc on optymalny ze względu na ilość operacji.
Na tej podstawie możemy sformułować twierdzenie komplementarne do tw. „No Free Lunch” w postaci: Tw. Dla każdego zadania optymalizacyjnego istnieje najlepszy algorytm genetyczny w sensie probabilistycznym. Algorytm ten w jednym kroku generuje rozkład stacjonarny.
Operator graniczny algorytmu genetycznego jest izomorficzny z przesunięciem Bernoulliego, a zatem i algorytmy genetyczne są izomorficzne z przesunięciem Bernoulliego. Pozwala to na klasyfikowanie algorytmów genetycznych na podstawie entropii, tak jak to jest możliwe dla przesunięć Bernoulliego.Ponieważ entropia przesunięcia Bernoulliego jest równa jego wymiarowi Hausdorffa, więc możemy klasyfikować algorytmy za pomocą tego wymiaru lub jego przybliżeń.

 
© 2010 Politechnika Białostocka