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 pewne 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.

Elementy analityczne można również wprowadzić do generowania populacji początkowej. Oprócz rozwiązań zupełnie losowych, mogą się tam znaleźć rozwiązania wyznaczone za pomocą prostego algorytmu heurystycznego, jak np. algorytm najbliższego sąsiada.

Bibliografia

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

Dodano: 3 czerwca 2017 11:15, ostatnia edycja: 1 maja 2020 16:13.

REKLAMA

Zobacz też

Algorytm Zhanga-Suena – algorytm służący do szkieletyzacji obrazu binarnego. Szkieletyzacja polega na wyborze z obrazu binarnego tych pikseli, które są równo odległe od krawędzi obiektu.

→ Czytaj całość

Metoda z zastosowaniem przepływu blokującego – algorytm wyznaczający maksymalny przepływ w sieci przepływowej. W algorytmie tym przepływ zwiększany jest iteracyjnie, w każdej iteracji wyznaczony przepływ jest powiększany o przepływ blokujący w warstwowej sieci residualnej.

→ Czytaj całość

Ten artykuł opisuje algorytm zachłanny rozwiązujący problem wydawania reszty. Algorytm ten polega na wybieraniu zawsze największej dostępnej monety, tzn. takiej, która nie jest większa od kwoty pozostałej do wydania.

Algorytm nie zawsze znajduje rozwiązanie optymalne. Przykładowo, dla zbioru nominałów {1, 3, 4} i kwoty 6 algorytm użyje najpierw monety o nominale 4 (pozostaje do wydania kwota 2), potem monety o nominale 1 (pozostaje kwota 1) i jeszcze raz monety o nominale 1. Łącznie algorytm użyje więc trzech monet, podczas gdy rozwiązanie optymalne wymaga użycia tylko dwóch (dwie monety o nominale 3).

→ Czytaj całość
Polityka prywatnościKontakt