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 Programowanie w języku C. Ćwiczenia praktyczne. Wydanie II
−40%11,94 zł
Czysta architektura. Struktura i design oprogramowania. Przewodnik dla profesjonalistów
−40%40,20 zł
Spring w akcji. Wydanie V
−30%62,30 zł
Młodzi giganci programowania. Scratch
−39%20,94 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ż

Graf – struktura składająca się ze zbioru wierzchołków oraz zbioru krawędzi. Grafy mają szerokie zastosowanie w informatyce, można za ich pomocą przedstawić wiele zagadnień.

Wyróżniamy grafy nieskierowane oraz grafy skierowane. W grafie nieskierowanym relacja sąsiedztwa jest symetryczna, tzn. krawędź łączy wierzchołki „w obie strony”. W grafie skierowanym krawędzie są „jednokierunkowe”. Krawędź grafu skierowanego zazwyczaj jest określana jako łuk.

Graf ważony (inaczej graf z wagami) to taki graf, w którym każdej krawędzi przypisana jest pewna wartość liczbowa. Wartość ta może oznaczać np. długość krawędzi lub jej przepustowość.

→ Czytaj całość

Algorytm Kruskala – algorytm wyznaczający minimalne drzewo rozpinające. Algorytm ten wykorzystuje strategię zachłanną.

→ Czytaj całość

Algorytmy zachłanne (ang. greedy algorithms) – algorytmy podejmujące w każdym kroku taką decyzję, która w danej chwili wydaje się najkorzystniejsza. Inaczej mówiąc, algorytmy zachłanne dokonują zawsze wyborów lokalnie optymalnych licząc, że doprowadzi to do znalezienia rozwiązania globalnie optymalnego. W ogólnym przypadku algorytmy zachłanne nie zawsze znajdują rozwiązanie optymalne. Są one zatem podzbiorem algorytmów heurystycznych. Jednocześnie są to algorytmy deterministyczne – nie ma w nich losowości.

Bardzo prostym przykładem algorytmu zachłannego może być szukanie najwyższego punktu na określonym obszarze poprzez przesuwanie się zawsze w kierunku największego nachylenia (nigdy się nie cofając ani nie rozpatrując kilku wariantów drogi). Jak widać, w ten sposób prawdopodobnie dojdziemy do wierzchołka położonego najbliżej od punktu początkowego, który niekoniecznie będzie najwyższym.

→ Czytaj całość
Polityka prywatnościKontakt