Metaheurystyka

Metaheurystyka – ogólny algorytm (heurystyka) do rozwiązywania problemów obliczeniowych. Algorytmu metaheurystycznego można używać do rozwiązywania dowolnego problemu, który można opisać za pomocą pewnych definiowanych przez ten algorytm pojęć. Najczęściej wykorzystywany jest jednak do rozwiązywania problemów optymalizacyjnych. Określenie powstało z połączenia słowa „meta” („nad”, tutaj w znaczeniu „wyższego poziomu”) oraz słowa „heurystyka” (gr. heuriskein – szukać), co wynika z faktu, że algorytmy tego typu nie rozwiązują bezpośrednio żadnego problemu, a jedynie podają sposób na utworzenie odpowiedniego algorytmu. Termin „metaheurystyka” po raz pierwszy został użyty przez Freda Glovera w 1986 roku.

Opis

Algorytm metaheurystyczny opisuje zwykle sposób przechodzenia między możliwymi rozwiązaniami w celu rozwiązania problemu. Mianowicie, mając dany problem $P,$ niech zbiór możliwych jego rozwiązań, będzie zbiorem wszystkich zdań $L(P),$ które można zapisać w języku problemu $P.$ Rozwiązaniem problemu jest dowolne $x\in S,$ gdzie $S$ jest pewnym podzbiorem zbioru $L(P).$ A zatem rozwiązanie problemu polega na znalezieniu zbioru $S$ – zależnie od definicji problemu wystarczającym może być znalezienie jednego elementu zbioru $S.$ Algorytm metaheurystyczny opisuje w jaki sposób mając dowolny element zbioru $L(P)$ „przejść” do innego elementu z tego zbioru, dając potencjalnie największą szanse na znalezienie rozwiązania problemu $P.$ „Przejście” to nie jest jednak dokładnie zdefiniowane, gdyż jest zależne od problemu $P.$ Są to więc jedynie pewne wskazówki, a konkretne implementacje algorytmu mogą się różnić. Sposób „przejścia” między elementami zbioru $L(P)$ oraz pewne inne niezbędne do działania algorytmu funkcje wpływają w istotny sposób na skuteczność algorytmu metaheurystycznego. Funkcje te mogą, wykorzystywać pewne właściwości problemu $P,$ których nie można opisać ogólnie dla dowolnego problemu, przez co nie mogą być elementem metaheurystyki na poziomie jej projektowania. Zwykle przestrzeń poszukiwań można również zawęzić do pewnego podzbioru zbioru $L(P).$

Mankamentem algorytmów metaheurystycznych jest fakt, iż nie gwarantują one znalezienia rozwiązania, a ponadto zwykle nie można podać czasu ich działania. Skuteczność metaheurystyk zależy również w dużej mierze od parametrów, które pojawiają się w tego typu algorytmach. Niestety nie istnieją uniwersalne wartości tych parametrów, które zachowują się najlepiej dla wszystkich możliwych danych wejściowych. Z tego też powodu metaheurystyki nadają się jedynie do rozwiązywania problemów dla których nie istnieją (bądź nie są znane) wydajne algorytmy, dające pewność znalezienia rozwiązania (np. problemy należące do klasy NP).

Algorytmy metaheurystyczne

Niektóre z algorytmów metaheurystycznych:

• algorytm genetyczny
• algorytm mrówkowy
• algorytm zachłanny
• lokalne przeszukiwanie
• PeSOA: Penguins Search Optimization Algorithm
• symulowane wyżarzanie
• Tabu Search

Zobacz też

• heurystyka

Bibliografia

• Sean Luke: Essentials of Metaheuristics. [dostęp 2010-02-04]. (ang.).brak strony w książce