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.
Przeszukiwanie wszerz (ang. breadth-first search, w skrócie BFS) – jeden z dwóch podstawowych algorytmów przeszukiwania grafu. Polega na przeglądaniu wierzchołków grafu według ich odległości od wierzchołka źródłowego (wyrażanej w liczbie krawędzi).
Wyznaczanie maksymalnego przepływu – problem obliczeniowy polegający na wyznaczeniu maksymalnego przepływu w sieci przepływowej.
Sieć przepływowa jest skierowanym grafem prostym. Każdy łuk (krawędź skierowana w grafie) ma swoją nieujemną wagę, która oznacza maksymalny dopuszczalny przepływ w tym łuku. Na potrzeby tego artykułu nazwijmy rzeczy przepływające przez sieć danymi. Jeden z wierzchołków sieci jest źródłem, z którego wypływają przesyłane dane. Inny z wierzchołków to ujście, do którego te dane wpływają. Zakłada się ponadto, że dla każdego z pozostałych wierzchołków istnieje ścieżka ze źródła do ujścia przechodząca przez ten wierzchołek.
Przepływem w sieci nazywamy przyporządkowanie każdemu łukowi pewnej wartości, która oznacza liczbę danych aktualnie przesyłanych przez ten łuk. Wartości te muszą spełniać następujące warunki:
Omawiany problem polega na dobraniu takiego przepływu, aby liczba danych wypływających ze źródła (i zarazem wpływających do ujścia) była jak największa.