Algorytmy Genetyczne: Optymalizacja poprzez Symulowaną Naturalną Selekcję

Wyszukiwanie poprzez naśladowanie selekcji, a nie dokładne naśladownictwo biologii

Algorytm genetyczny (AG) traktuje problem optymalizacji jako naturalny dobór przez prymitywy w populacji: zachowuje się pulę kandydatów rozwiązań („populację” „chromosomów”, często po prostu tablicę liczb lub bitów kodujących projekt), ocenia każdą z nich za pomocą funkcji dopasowania, która mierzy jak dobrze jest rozwiązanie, i wielokrotnie buduje nową generację, preferując lepszych rodziców, mieszając ich geny i sporadycznie mutując. John Holland zformalizował ten podbój w latach 70-tych jako sposób na badanie adaptacji obliczeniowo, a algorytm od tego czasu stał się standardowym, ogólnodostępnym narzędziem wszędzie tam, gdzie przestrzeń poszukiwań jest zbyt duża lub zbyt nieregularna dla optymalizacji opartych na kalkulusie.

1. initialise a random population of N candidate solutions
2. evaluate fitness(individual) for every member
3. select parents, biased toward higher fitness
4. crossover: combine pairs of parents into offspring
5. mutate offspring with small probability
6. replace the population with the new generation
7. repeat from step 2 until fitness stops improving (or a target is reached)

Dobór: wybieranie reproduktorów

Dobór turniejowy jest najszerzej stosowaną metodą w praktyce: wybiera się k jednostek losowo z populacji i pozwala najsilniejszym z nich stać się rodzicem, powtarzane tak często, jak potrzeba rodziców. Jest tani, nie wymaga sortowania całej populacji, a wielkość turnieju k bezpośrednio kontroluje presję selekcji – k = 1 odpowiada czysto losowemu wyborowi (bez żadnej presji), podczas gdy duże k zbliża się do zawsze wybierania pojedynczego najlepszego osobnika, co szybko zbiega ku końcowi, ale ryzykuje utraty różnorodności genetycznej na wczesnym etapie. Dobór kołowy (proporcjonalny do fitnessu) jest klasyczną alternatywą, która daje każdej jednostce szansę na wybranie proporcjonalną do jej wyniku fitnessowego, choć jest wrażliwy na skalowanie wyników fitnessowych – jeden dominujący indywidualizm może wypchnąć resztę populacji w ciągu kilku generacji, chyba że wartości fitnessowe są najpierw znormalizowane.

Przejście: łączenie, a nie tylko kopiowanie

Przejście znowu łączy dwie genotypy rodzicielskie w potomstwo, a to rekombinacja – a nie sama mutacja – pozwala algorytmowi genetycznemu (GA) odkrywać kombinacje dobrych podrozwiązań, których ani jeden z rodziców nie posiadał indywidualnie. Crossover punktowy wybiera jedną pozycję cięcia i zamienia wszystko po niej między dwoma rodzicami; crossover dwupunktowy i uniformny wymienia bardziej precyzyjnie, a crossover uniformny niezależnie wybiera każdy gen z jednego lub drugiego rodzica. Który schemat najlepiej działa zależy od tego, czy bliskie geny w kodowaniu mają tendencję do interakcji – właściwość ta nazywana jest linkowaniem – co właśnie dlatego dobór dobrego reprezentacji problemu (jak kandydatowe rozwiązanie jest zakodowane jako chromosom) często stanowi najważniejsze decyzje projektowe przy zastosowaniu GA.

parent A:  1 0 1 1 | 0 0 1
parent B:  0 1 0 0 | 1 1 0
                    ^ crossover point

child:     1 0 1 1 | 1 1 0     (tail swapped from parent B)

Mutacje: źródło genów, które nigdy nie istniały w populacji

Dobór i przemieszczenie mogą jedynie przekształcać materiał genetyczny już obecny w populacji; mutacja – odwrócenie bitu, przesunięcie wartości zmiennoprzecinkowej lub zamiana dwóch elementów – to jedyna operacja, która wprowadza naprawdę nowe wartości, i zapobiega permanentnemu zablokowaniu algorytmu, gdy populacja skupia się wokół jednego obszaru przestrzeni poszukiwań. Współczynnik mutacji jest delikatnym pokrętłem: zbyt niski i populacja wczesnie skonsoliduje się wokół przyzwoitego, lokalnego optimum bez możliwości wyjścia (błąd zwany dryfem genetycznym, gdy zachodzi przypadkowo zamiast pod wpływem presji selekcji); zbyt wysoki i algorytm ulega degradacji do czystego losowego przeszukiwania, niszcząc dobre konstrukcje szybciej, niż może je preferować selekcja.

Obrazowanie krajobrazu przyrostowego i dlaczego GAs dobrze sprawdzają się w niegochanych

Wyobraźcie sobie każdy możliwy genotyp jako punkt w przestrzeni o wysokiej wymiarowości, a fitness zarysowany wysokością nad nim — krajobraz przyrostowy. Optymalizatory oparte na gradientach efektywnie wspinają się po najbliższym lokalnym szczycie, ale permanentnie utkną tam, jeśli krajobraz jest niegośny, z wieloma oddzielnymi szczytami o różnej wysokości. Populacja GAs rozproszona jest na wielu punktów naraz, a presja selekcji jest miękka, zamiast absolutną, więc słabszych, ale różnych jednostek wystarczy, aby przetrwały wystarczająco długo, by czasem przejść przez dolinę i odkryć wyższy szczyt w innym miejscu — to właściwość równowagi między eksploracją a wykorzystaniem. Dlatego właśnie GAs są stosowane na problemach takich jak układ obwodów, harmonogramowanie, poszukiwanie architektury sieci neuronowych i strategie grywalizacji z ewolucją, gdzie krajobraz przyrostowy jest znany jako nieregularny i nie istnieje pojedynczy gładki gradient do śledzenia.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Genetic Evolution i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.