Algorytmy memetyczne

Algorytm memetyczny, schemat blokowy (1) Schemat blokowy algorytmu memetycznego
2-opt przykład (2) 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

Ocena: 0 Tak Nie
Liczba głosów: 0.

Dodano: 3 czerwca 2017 11:15, ostatnia edycja: 30 stycznia 2019 15:47.

REKLAMA

Zobacz też

Minimalne drzewo rozpinające (ang. minimum spanning tree, w skrócie MST), inaczej drzewo rozpinające o minimalnej wadze – drzewo łączące wszystkie wierzchołki pewnego grafu spójnego mające najmniejszą możliwą sumę wag krawędzi.

Jeśli graf ma v wierzchołków, to jego drzewo rozpinające zawsze będzie miało v-1 krawędzi. Jeśli ten graf ma e krawędzi, aby utworzyć drzewo rozpinające, trzeba usunąć z grafu e-v+1 krawędzi. Liczba ta jest określana jako liczba cyklomatryczna.

→ Czytaj całość

Algorytm Helda-Karpa (czasami określany jako algorytm Bellmana-Helda-Karpa) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm dokładny oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n22n) i złożoność pamięciową O(n2n). Jest to co prawda złożoność gorsza od wielomianowej, ale algorytm ten jest znacznie lepszy od algorytmu sprawdzającego wszystkie warianty (złożoność czasowa O(n!)).

→ Czytaj całość

Metoda Forda-Fulkersona – algorytm służący do wyznaczania maksymalnego przepływu. Jest to algorytm bardzo ogólny, dlatego często nie jest nazywany algorytmem, a metodą. Popularną implementacją tej metody jest algorytm Edmondsa-Karpa. Algorytm można opisać następująco:

  1. Wyznacz sieć residualną (opis sieci residualnej znajduje się w dalszej części artykułu).
  2. Znajdź w sieci residualnej dowolną ścieżkę powiększającą.
  3. Jeśli nie udało się wyznaczyć żadnej ścieżki powiększającej, zakończ działanie algorytmu.
  4. W przeciwnym razie zwiększ przepływ w sieci (w sposób opisany w dalszej części artukułu) i wróć do punktu 1.
→ Czytaj całość
Polityka prywatnościKontakt