Algorytmy genetyczne

Tutorial
Na 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 (1) Schemat blokowy algorytmu genetycznego
REKLAMA

Pragmatyczny programista. Od czeladnika do mistrza. Wydanie II
−30%53,90 zł
Algorytmy. Ćwiczenia
34,90 zł

Algorytm genetycznymetaheurystyka inspirowana biologiczną ewolucją.

Pojęcie algorytmu genetycznego nie jest powiązane z żadnym konkretnym problemem obliczeniowym, algorytm ten może być 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).

Sposób kodowania rozwiązania (osobnika) nie jest określony, zależy on od konkretnego problemu do rozwiązania. Klasycznym podejściem jest kodonie binarne, czyli przedstawienie osobnika za pomocą ciągu zer i jedynek. Wówczas wartość 1 może oznaczać obecność jakiegoś elementu w rozwiązaniu, a 0 jej brak. Innym popularnym rozwiązaniem jest ciąg liczb naturalnych. Takie rozwiązanie znajduje zastosowanie między innymi w przypadku problemu komiwojażera, gdzie kolejność liczb oznacza kolejność odwiedzania punktów na trasie.

Ocena jakości

Algorytm genetyczny musi mieć funkcję oceny jakości rozwiązania pozwalającą określić, które rozwiązanie jest lepsze. Funkcja ta jest określana jako funkcja oceny lub funkcja przystosowania.

Krzyżowanie

Operacja krzyżowania polega na utworzeniu potomka (lub potomków) na podstawie dwóch wybranych elementów populacji. Potomek zawiera w sobie część cech jednego rodzica, a część drugiego. W przypadku kodowania binarnego najprostszym rozwiązaniem jest skopiowanie części ciągu z jednogo rodzica, a pozostałej części z drugiego. Jeśli osobniki zakodowane są za pomocą ciągu liczb, można stosować następującą metodę krzyżowania: część rozwiązania jest kopiowana z jednego rodzica, a następnie brakujące liczby są wstawiane w takiej kolejności, w jakiej wystąpowały w drugim rodzicu.

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). W kodowaniu binarnym mutacją możę być zamiana losowego bitu na przeciwny, a w kodowaniu za pomocą ciągu liczb np. zamiana miejscami dwóch elementów.

Selekcja

Celem selekcji jest usunięcie z populacji rozwiązań słabych, a pozostawienie dobrych, które będą podlegały krzyżowaniu. W trywialnym przypadku może być zrealizowane po prostu przez pozostawienie określonej liczby najlepszych rozwiązań (osobników) i usunięcie pozostałych. Zazwyczaj selekcja jest bardziej złożona – prawdopodobieństwo zostania rodzicem zależy od oceny jakości osobnika, jednak nawet w przypadku słabych osobników nie jest ono 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. Warunkiem stopu może być również ocena jakości najlepszego osobnika w populacji.

Zobacz też

Bibliografia

  • A. Debudaj-Grabysz, S. Deorowicz, J. Widuch, Algorytmy i struktury danych. Wybór zaawansowanych metod, Wydawnictwo Politechniki Śląskiej, Gliwice, 2012, ISBN 9788373359383.
Ocena: 0 Tak Nie
Liczba głosów: 0.

Dodano: 1 maja 2017 18:57, ostatnia edycja: 30 stycznia 2019 15:40.

REKLAMA

Zobacz też

Sortowanie – zagadnienie polegające na uporządkowaniu elementów zbioru rosnąco lub malejąco według pewnego klucza. Zagadnienie to, ze względu na częstość występowania, jest bardzo istotne dla informatyki. Istnieje wiele różnych algorytmów realizujących sortowanie.

→ Czytaj całość

Matroid – struktura matematyczna składająca się z niepustego zbioru elementów E i takiej rodziny jego podzbiorów I, że spełnione są następujące warunki:

  1. Jeśli jakiś zbiór należy do I, to wszystkie jego podzbiory także należą do I.
  2. Jeśli weźmiemy dowolne dwa zbiory należące do I o różnej liczbie elementów, to jesteśmy w stanie dodać do mniejszego z nich taki element z większego (spośród tych, które nie należą do mniejszego), że utworzony w ten sposób zbiór także będzie należał do I.

Drugi warunek, zwany własnością wymiany, formalnie może być zapisany jako:

$$⋀↙{A,B∊I}↙{ |A|>|B| }⋁↙{t∊(A-B)} B∪\{t\} ∈ I$$

Co istotne, rodzina zbiorów I nie musi zawierać wszystkich możliwych podzbiorów zbioru E. Ważne tylko, aby była spełniona własność wymiany. Przykładowo, dla E={a,b,c,d} prawidłową rodziną I, może być zarówno { {a,b}, {b,c}, {a}, {b}, {c}, ∅}, jak i { {a}, {b}, {c}, {d}, ∅}. Trywialnym przypadkiem poprawnego matroidu jest taki, w którym rodzina I zawiera jedynie zbiór pusty.

→ Czytaj całość

Algorytm Dijkstry – algorytm służący do wyznaczania najkrótszych ścieżek w grafie. Wyznacza najkrótsze ścieżki z jednego wierzchołka (zwanego wierzchołkiem źródłowym) do pozostałych wierzchołków. Algorytm wymaga, aby wagi krawędzi grafu nie były ujemne. Autorem algorytmu jest holenderski naukowiec Edsger Dijkstra.

Algorytm realizuje podejście zachłanne. W każdej iteracji wybierany jest ten spośród nieodwiedzonych wierzchołków, do którego można dotrzeć najmniejszym kosztem. Po wyznaczeniu ścieżki do konkretnego wierzchołka nie zostanie ona zmodyfikowana w trakcie wykonywania dalszej części algorytmu.

→ Czytaj całość
Polityka prywatnościKontakt