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ż

Drzewo decyzyjne – metoda graficzna wspierająca podejmowanie decyzji, jak również model stosowany w uczeniu maszynowym do klasyfikacji lub regresji.

Podejmowanie decyzji z wykorzystaniem drzewa decyzyjnego odbywa się poprzez odpowiadanie na kolejne pytania. Pojedyncze pytanie musi być proste i dotyczyć jednego konkretnego atrybutu. Pytania ułożone są w strukturę hierarchiczną – wybór następnego pytania (lub końcowej decyzji) zależy od odpowiedzi udzielonej na poprzednie.

Proste drzewo decyzyjne może być w pełni zaprojektowane już przy tworzeniu programu i zaimplementowane w kodzie np. za pomocą instrukcji warunkowych. W uczeniu maszynowym drzewo jest generowane automatycznie na podstawie próbek ze zbioru uczącego.

→ Czytaj całość

Sortowanie przez wstawianie (ang. insertion sort) – prosty algorytm sortowania polegający na wstawianiu kolejnych elementów ciągu we właściwe miejsca. Złożoności czasowa algorytmu wynosi O(n2). Jest to algorytm realizujący metodę przyrostową.

→ Czytaj całość

Bogosort – bardzo słaby algorytm sortowania oparty na metodzie prób i błędów. Polega na ustawianiu elementów w losowej kolejności i sprawdzaniu, czy są posortowane. Średnia złożoność tego algorytmu jest rzędu silnia, a w przypadku pesymistycznym algorytm będzie działał w nieskończoność.

Algorytm występuje też w nieco ulepszonej wersji, w której nie sprawdza się wielokrotnie tego samego ustawienia. Wówczas algorytm daje gwarancję znalezienia rozwiązania, jednak jego złożoność czasowa nadal jest rzędu silnia (w przypadku pesymistycznym trzeba sprawdzić wszystkie permutacje zbioru).

Ze względu na bardzo dużą złożoność czasową bogosort nie nadaje się do praktycznych zastosowań. Istnieją proste w implementacji, a znacznie wydajniejsze algorytmy sortujące, np. sortowanie przez wstawianie.

→ Czytaj całość
Polityka prywatnościKontakt