Metaheurystyka

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Metaheurystyka - ogólny algorytm (heurystyka) do rozwiązywania problemów obliczeniowych. Algorytm metaheurystyczny można używać do rozwiązywania dowolnego problemu, który można opisać za pomocą pewnych definiowaych 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[1].

Opis[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Niektóre z algorytmów metaheurystycznych:

Zobacz też[edytuj | edytuj kod]

Przypisy

  1. Fred Glover. Future Paths for Integer Programming and Links to Artificial Intelligence. „Computers and Operations Research”. 13 (5), s. 533-549, 1986-05. ISSN 0305-0548. 

Bibliografia[edytuj | edytuj kod]

  1. Sean Luke: Essentials of Metaheuristics. [dostęp 2010-02-04]. (ang.)