Algorytm genetyczny – jedna z metaheurystyk inspirowanych 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.
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 kodowanie 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.
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.
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.
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.
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.
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.
Dodano: 1 maja 2017 18:57, ostatnia edycja: 7 czerwca 2023 18:41.
Algorytm Bellmana-Forda – 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. W odróżnieniu od algorytmu Dijkstry, algorytm Bellmana-Forda dopuszcza krawędzie o ujemnych wagach, nie mogą istnieć jednak ujemne cykle osiągalne z wierzchołka źródłowego. Algorytm może być również wykorzystywany do sprawdzania, czy w grafie występują ujemne cykle.
Algorytm występuje również pod nazwą algorytm Bellmana-Forda-Moore’a.
Problem wydawania reszty (ang. change-making problem) – problem obliczeniowy polegający na tym, aby mając określony zbiór nominałów wyrazić daną kwotę za pomocą jak najmniejszej liczby monet. Jest to szczególny przypadek problemu plecakowego.