Algorytmy memetyczne
Schemat blokowy algorytmu memetycznego
Przykład optymalizacji lokalnej z użyciem algorytmu 2-optymalnego
Algorytm memetyczny – algorytm będący połączeniem algorytmu genetycznego i metod lokalnej optymalizacji. Czasami określany również jako hybrydowy algorytm ewolucyjny.
Różnice między algorytmem genetycznym a memetycznym
W algorytmie genetycznym zadanie w ogóle nie jest rozwiązywane w sposób analityczny – liczymy, że mechanizmy ewolucji same znajdą dobre rozwiązanie. W przypadku algorytmów memetycznych wzbogacamy to podejście o elementy analityczne.
Algorytm memetyczny oprócz operacji krzyżowania, mutacji i selekcji ma również operację lokalnej optymalizacji. Celem tej operacji jest zmodyfikowanie osobnika populacji tak, aby osiągnąć lepsze rozwiązanie. Do modyfikacji tej wykorzystuje się wiedzę specjalistyczną dla danego zagadnienia.
Przykład
Załóżmy, że mamy algorytm genetyczny służący do rozwiązywania problemu komiwojażera (możemy przyjąć, że został zaimplementowany tak, jak w samouczku zamieszczonym na naszej stronie). Aby zrobić na jego podstawie algorytm memetyczny, musimy zaimplementować operację lokalnej optymalizacji. Operacja ta będzie umieszczona między krzyżowaniem a selekcją.
Jako operację lokalnej optymalizacji możemy przyjąć algorytm 2-optymalny. Algorytm ten polega na usunięciu z cyklu dwóch krawędzi i zastąpieniu ich innymi krawędziami (tak, aby nadal był prawidłowy cykl). Dla n wierzchołków mamy złożoność obliczeniową o(n2). Po sprawdzeniu wszystkich par krawędzi wybieramy tę zamianę, która powoduje największe skrócenie trasy. Jeśli żadna z modyfikacji nie spowodowała skrócenia trasy, zostawiamy rozwiązanie pierwotne.
Istnieją również algorytmy 3-optymalne i większe. W ogólnym przypadku tego typu algorytm lokalnej optymalizacji jest określany jako algorytm k-optymalny.
Bibliografia
- Yew-Soon Ong, Meng-Hiot Lim, Ning Zhu, Kok-Wai Wong, Classification of Adaptive Memetic Algorithms: A Comparative Study.
- D.S. Johnson, L.A. McGeoch, The Traveling Salesman Problem: A Case Study in Local Optimization (link) [dostęp: 3 czerwca 2017].
Liczba głosów: 0.
- Algorytmy genetyczne
- Algorytmy memetyczne
- Algorytmy zachłanne
Dodano: 3 czerwca 2017 11:15, ostatnia edycja: 26 czerwca 2017 18:50.
Zobacz też
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.
Algorytm Floyda-Warshalla – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Jest to algorytm oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n3) i złożoność pamięciową O(n2), gdzie n jest liczbą wierzchołków.
Algorytm dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli. Algorytm może być również wykorzystywany do wyszukiwania ujemnych cykli w grafie.
Przeszukiwanie w głąb (ang. depth-first search, w skrócie DFS) – jeden z dwóch podstawowych algorytmów przeszukiwania grafu. Polega na przechodzeniu zawsze do kolejnego nieodwiedzonego wierzchołka. Jeśli dany wierzchołek nie ma nieodwiedzonych sąsiadów, wracamy do poprzedniego wierzchołka i sprawdzamy jego sąsiadów. Mówiąc obrazowo, w algorytmie tym wchodzimy tak głęboko, jak to możliwe (przechodzimy dalej, dopóki się da).
Algorytm można zapisać w sposób rekurencyjny. Wywoływana rekurencyjnie procedura działa następująco: oznacz wierzchołek jako odwiedzony, a następnie wywołaj tę procedurę dla każdego sąsiada danego wierzchołka, jeśli nie został on wcześniej odwiedzony. Na początku wywołujemy procedurę dla wierzchołka początkowego.