Algorytm genetyczny

ZębatkaNa ten temat mamy również tutorial „Problem komiwojażera, algorytm genetyczny”, który ilustruje działanie algorytmu krok po kroku. Zapraszamy do zapoznania się z nim!
Algorytm genetyczny, schemat blokowy Schemat blokowy algorytmu genetycznego

Algorytm genetyczny – algorytm heurystyczny inspirowany biologiczną ewolucją.

Pojęcie algorytmu genetycznego nie jest powiązane z żadnym konkretnym problemem obliczeniowym, algorytm ten może być on wykorzystywany do rozwiązywania różnych problemów. Algorytm genetyczny nie próbuje rozwiązywać problemu w sposób analityczny, ale próbuje uzyskać jak najlepsze rozwiązania poprzez wybieranie jak najlepszych cech rozwiązań z określonej puli. Implementując algorytm genetyczny należy przedstawić potencjalne rozwiązanie problemu w postaci jakiejś struktury danych, a następnie zdefiniować operacje krzyżowania, mutacji i selekcji. Zakładamy, że z każdym kolejnym pokoleniem rozwiązania występujące w populacji będą coraz lepsze.

Operacje

Utworzenie populacji początkowej

Na początku działania algorytmu trzeba utworzyć populację początkową. Najczęściej polega to na utworzeniu pewnej liczby zupełnie losowych rozwiązań (określanych jako osobniki).

Ocena jakości

Algorytm genetyczny musi mieć funkcję oceny jakości rozwiązania. Pozwala ona określić, które rozwiązanie jest lepsze.

Krzyżowanie

Operacja krzyżowania polega na wylosowaniu dwóch rozwiązań (osobników) z populacji, a następnie na utworzeniu ich potomka (lub potomków). Potomek zawiera w sobie część cech jednego rodzica, a część drugiego.

Mutacja

Operacja mutacji polega na dokonaniu losowej zmiany w którymś z osobników. Operacja ta powinna być stosowana stosunkowo rzadko (mutacji powinno podlegać znacznie mniej osobników, niż krzyżowaniu).

Selekcja

Celem selekcji jest usunięcie z populacji rozwiązań słabych, a pozostawienie dobrych. Może być zrealizowane po prostu przez pozostawienie określonej liczby najlepszych rozwiązań (osobników) i usunięcie pozostałych. Selekcja może być też bardziej złożona – wówczas prawdopodobieństwo pozostania osobnika zależy od jego jakości, jednak nawet w przypadku słabych osobników nie jest zerowe.

Warunek stopu

Algorytm musi mieć zdefiniowany moment, w którym ma zakończyć swoje działanie. Najprostszym rozwiązaniem jest określenie liczby iteracji (pokoleń). Po zakończeniu działania algorytmu najlepszy osobnik z populacji jest zwracany jako wynik.

Dodano: 1 maja 2017 18:57