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: -1 Tak Nie
Liczba głosów: 1.

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

REKLAMA

Zobacz też

Algorytm memetyczny – algorytm będący połączeniem algorytmu genetycznego i metod lokalnej optymalizacji. Czasami określany również jako hybrydowy algorytm ewolucyjny.

→ Czytaj całość

Symulowane wyżarzanie – jedna z technik projektowania algorytmów heurystycznych (metaheurystyka). Cechą charakterystyczną tej metody jest występowanie parametru sterującego zwanego temperaturą, który maleje w trakcie wykonywania algorytmu. Im wyższą wartość ma ten parametr, tym bardziej chaotyczne mogą być zmiany. Podejście to jest inspirowane zjawiskami obserwowanymi w metalurgii – im większa temperatura metalu, tym bardziej jest on plastyczny.

Jest to metoda iteracyjna: najpierw losowane jest pewne rozwiązanie, a następnie jest ono w kolejnych krokach modyfikowane. Jeśli w danym kroku uzyskamy rozwiązanie lepsze, wybieramy je zawsze. Istotną cechą symulowanego wyżarzania jest jednak to, że z pewnym prawdopodobieństwem może być również zaakceptowane rozwiązanie gorsze (ma to na celu umożliwienie wyjście z maksimum lokalnego).

Prawdopodobieństwo przyjęcia gorszego rozwiązania wyrażone jest wzorem e(f(X)−f(X'))/T (rozkład Boltzmanna), gdzie X jest poprzednim rozwiązaniem, X' nowym rozwiązaniem, a f funkcją oceny jakości – im wyższa wartość f(X), tym lepsze rozwiązanie. Ze wzoru można zauważyć, że prawdopodobieństwo przyjęcia gorszego rozwiązania spada wraz ze spadkiem temperatury i wzrostem różnicy jakości obu rozwiązań.

→ Czytaj całość

Rekurencja (inaczej rekursja) – odwołanie się funkcji lub definicji do samej siebie. Mówiąc inaczej, podejście rekurencyjne polega na tym, że rozwiązanie problemu wyraża się za pomocą rozwiązania tego samego problemu dla mniejszych danych wejściowych. Stosowanie rekurencji jest charakterystyczne dla algorytmów projektowanych metodą dziel i zwyciężaj.

Typowym problemem, dla którego można zastosować rekurencję, jest obliczanie silni. Przypomnijmy, że silnia z n jest zdefiniowana jako n!=1×2×…×n. Funkcja ta może być równoważnie zapisana jako:

n!=(n−1)!×n, dla n>0,
n!=1, dla n=0.

W powyższym przykładzie górny wiersz jest ogólnym równaniem rekurencji, zaś dolny wiersz jest wartością brzegową. W języku C++ powyższa funkcja byłaby zapisana w poniższy sposób.

int silnia(int n)
{
    if (n > 0)
    {
        return n * silnia(n-1);
    }
    else
    {
        return 1;
    }
};

Przekształcenie postaci rekurencyjnej funkcji do postaci zwartej (tzn. takiej, która nie zawiera odwołania do samej siebie) jest określane jako rozwiązanie rekurencji. Metody rozwiązywania rekurencji są dostępne między innymi w książkach podanych w bibliografii.

Algorytmy stosujące rekurencję są zazwyczaj proste w implementacji. Jednocześnie wiążą się one z pewnymi problemami. Przy podejściu rekurencyjnym ta sama funkcja jest wywoływana wielokrotnie, co zużywa pamięć operacyjną (w skrajnych przypadkach może to spowodować przepełnienie stosu).

→ Czytaj całość
Polityka prywatnościKontakt