Metaheurystyka jest algorytm z optymalizacją do rozwiązywania problemów trudnych optymalizacji (często z dziedziny badań operacyjnych , w inżynierii lub AI ), dla którego nie ma znanego klasycznego najbardziej skuteczną metodę.
Metaheurystyk generalnie iteracyjne stochastyczne algorytmy , które postęp w kierunku globalnego optymalny, to znaczy globalnego ekstremum funkcji przez próbkowanie się funkcję celu . Zachowują się jak algorytmy wyszukiwania, próbując poznać charakterystykę problemu w celu znalezienia przybliżenia najlepszego rozwiązania (w sposób podobny do algorytmów aproksymacyjnych ).
Istnieje wiele różnych metaheurystyk, od prostego wyszukiwania lokalnego po złożone algorytmy wyszukiwania globalnego. Metody te wykorzystują jednak wysoki poziom abstrakcji, dzięki czemu można je dostosować do wielu różnych problemów.
Mówimy o meta , z greckiego μετά „poza” (rozumieć tutaj „na wyższym poziomie”), heurystycznej , z greckiego εὑρίσκειν / heuriskein , co oznacza „znaleźć”. W rzeczywistości te algorytmy mają być metodami ogólnymi, które mogą optymalizować szeroki zakres różnych problemów, bez konieczności głębokich zmian w używanym algorytmie.
Nieco inna terminologia traktuje metaheurystykę jako formę algorytmów optymalizacji stochastycznej, zhybrydyzowanych z wyszukiwaniem lokalnym. Termin meta jest zatem rozumiany w tym sensie, że algorytmy mogą grupować kilka heurystyk . Definicja ta znajduje się głównie w literaturze dotyczącej algorytmów ewolucyjnych, gdzie jest używana do określenia specjalizacji. W kontekście pierwszej terminologii algorytm ewolucyjny zhybrydyzowany z wyszukiwaniem lokalnym będzie raczej nazywany algorytmem memetycznym .
Metaheurystyk często inspirowany systemów naturalnych, są brane pod fizyki (przypadek symulowanym odprężaniu ) w biologii w ewolucji (przypadku algorytmów genetycznych ) lub etologii (przypadek algorytmów mrówek kolonii lub optymalizacji roju cząstek ).
Celem metaheurystyki jest rozwiązanie danego problemu optymalizacji : szuka obiektu matematycznego ( permutacji , wektora itp.) , Który minimalizuje (lub maksymalizuje) funkcję celu , która opisuje jakość rozwiązania problemu. .
Przestrzeń badawczą tworzy zbiór możliwych rozwiązań . Przestrzeń poszukiwań jest co najmniej ograniczona, ale może być również ograniczona zestawem ograniczeń .
Metaheurystyka manipuluje jednym lub kilkoma rozwiązaniami w poszukiwaniu optymalnego , najlepszego rozwiązania problemu. Kolejne iteracje powinny umożliwić przejście od rozwiązania złej jakości do rozwiązania optymalnego. Algorytm zatrzymuje się po osiągnięciu kryterium zatrzymania , zwykle polegającego na osiągnięciu wyznaczonego czasu wykonania lub żądanej precyzji.
Roztwór lub zbiorem rozwiązań jest czasem zwany stan że metaheurystyka ewolucji poprzez do przejścia lub przepływu . Jeśli nowe rozwiązanie jest budowane z istniejącego rozwiązania, jest jego sąsiadem . Wybór otoczenia i reprezentującej je struktury danych może mieć kluczowe znaczenie.
Kiedy rozwiązanie jest powiązane z pojedynczą wartością, mówi się o problemie z jednym celem , gdy jest powiązane z kilkoma wartościami, o problemie wielocelowym (lub wielokryterialnym ). W tym drugim przypadku szukamy zestawu niedominowanych rozwiązań („ front Pareto ”), wśród których nie możemy zdecydować, czy jedno rozwiązanie jest lepsze od drugiego, a żadne z nich nie jest systematycznie gorsze od innych we wszystkich Celach.
W niektórych przypadkach pożądanym celem jest jednoznaczne znalezienie zbioru „zadowalających” optimum. Algorytm musi wtedy znaleźć wszystkie rozwiązania dobrej jakości, niekoniecznie ograniczając się do jedynego optimum: mówimy o metodach multimodalnych .
Metaheurystyka nie wymaga specjalnej wiedzy o problemie zoptymalizowanym do działania, jedyną potrzebną informacją jest możliwość skojarzenia jednej (lub więcej) wartości z rozwiązaniem.
W praktyce powinny być stosowane tylko w przypadku problemów, których nie można zoptymalizować metodami matematycznymi. Używane zamiast specjalistycznej heurystyki , generalnie wykazują gorszą wydajność.
Metaheurystyki są często używane w optymalizacji kombinatorycznej , ale spotykamy się z nimi również w przypadku problemów ciągłych lub mieszanych (problemy ze zmiennymi dyskretnymi i ciągłymi).
Pewne metaheurystyki są teoretycznie „ zbieżne ” w pewnych warunkach. Gwarantuje się wtedy, że optymalne globalne zostanie znalezione w określonym czasie, a prawdopodobieństwo tego będzie rosło asymptotycznie w czasie. Ta gwarancja sprowadza się do uznania, że algorytm zachowuje się w najgorszym przypadku jak czysto losowe wyszukiwanie (prawdopodobieństwo wypróbowania wszystkich rozwiązań zmierzających do 1). Jednak niezbędne warunki rzadko są weryfikowane w rzeczywistych zastosowaniach. W praktyce głównym warunkiem zbieżności jest założenie, że algorytm jest ergodyczny (że może osiągnąć dowolne rozwiązanie z każdym ruchem), ale często zadowalają nas quasi- ergodyczność (jeśli metaheurystyka może osiągnąć dowolne rozwiązanie w liczbie skończonej) ruchów).
Ogólnie rzecz biorąc, metaheurystyka obraca się wokół kilku pojęć:
Sąsiedztwo rozwiązania to podzbiór rozwiązań, do których można dojść poprzez serię danych przekształceń. W związku z tym termin „sąsiedztwo” czasami określa zestaw rozważanych przekształceń.
Prostym sąsiedztwem dla problemu komiwojażera będzie np. Zestaw rozwiązań, które można zbudować poprzez permutację dwóch miast w danym rozwiązaniu.
Pojęcie sąsiedztwa jest niewątpliwie ogólną zasadą najczęściej używaną przy projektowaniu heurystyk. W przypadku problemów kombinatorycznych sąsiedztwo ma istotny wpływ na zachowanie metaheurystyki, natomiast w przypadku problemów ciągłych samo pojęcie sąsiedztwa jest trudniejsze do zdefiniowania.
Chociaż istnieje bardzo niewiele teoretycznych wyników dotyczących dopasowania sąsiedztwa do danego dyskretnego problemu, może być możliwe obliczenie wskaźników empirycznych, takich jak szorstkość . Najbardziej klasyczne techniki definiowania sąsiedztwa opierają się na pojęciach permutacji , łańcuchów wyrzutu i częściowych optymalizacji.
Intensyfikacja, dywersyfikacja, uczenie sięDywersyfikacji (lub rozpoznawania synonimem stosowane niemal wymiennie w literaturze algorytmów ewolucyjnych) oznacza proces gromadzenia informacji o zoptymalizowanym problemu. Do intensyfikacji (lub eksploatacji) ma na celu wykorzystać informacje zebrane już definiować i przeglądać interesujące obszary przestrzeni badawczej . Pamięć jest medium nauki, która pozwala algorytm do rozważenia tylko obszary, w których globalne optimum może być odnaleziony, unikając w ten sposób lokalne optima.
Metaheurystyka postępuje iteracyjnie, naprzemiennie fazami intensyfikacji, dywersyfikacji i uczenia się lub przez ściślejsze mieszanie tych pojęć. Stan początkowy jest często wybierany losowo, a następnie algorytm działa aż do osiągnięcia kryterium zatrzymania.
Pojęcia intensyfikacji i dywersyfikacji dominują w koncepcji metaheurystyki, która musi zachować delikatną równowagę między tymi dwiema dynamikami badawczymi. Te dwie koncepcje nie są zatem sprzeczne, ale uzupełniają się i istnieje wiele strategii łączących oba aspekty.
Najbardziej klasyczne metaheurystyki to oczywiście te oparte na tym pojęciu. W tej perspektywie algorytm powoduje ewolucję pojedynczego rozwiązania w przestrzeni wyszukiwania w każdej iteracji. Dlatego też pojęcie sąsiedztwa ma zasadnicze znaczenie.
Najbardziej znane z tej klasy to symulowane wyżarzanie , wyszukiwanie z tabu , wyszukiwanie w zmiennym sąsiedztwie , metoda GRASP czy nawet efekty dźwiękowe . Metody te można porównać z klasyczną metodą wspinaczki górskiej.
W tej klasyfikacji drugie podejście wykorzystuje pojęcie populacji. Metaheurystyka manipuluje zestawem rozwiązań równolegle, w każdej iteracji.
Możemy przytoczyć algorytmy genetyczne , optymalizację przez roje cząstek , algorytmy kolonii mrówek .
Czasami granica między tymi dwiema klasami jest zatarta. Możemy zatem uznać, że symulowane wyżarzanie, w którym temperatura spada etapami, ma strukturę populacji. W rzeczywistości w tym przypadku na każdym poziomie obsługiwany jest zbiór punktów, jest to po prostu kwestia określonej metody pobierania próbek.
Metaheurystyka wykorzystuje historię wyszukiwania do kierowania optymalizacją w kolejnych iteracjach.
W najprostszym przypadku ograniczają się do rozważenia stanu poszukiwań w danej iteracji w celu określenia kolejnej iteracji: jest to wtedy proces decyzyjny Markowa i będziemy mówić o metodzie bez pamięci . Tak jest w przypadku większości lokalnych metod wyszukiwania.
Wiele metaheurystyk wykorzystuje bardziej rozwiniętą pamięć, czy to krótkookresową (np. Ostatnio odwiedzane rozwiązania), czy też długoterminową (zapamiętywanie zestawu syntetycznych parametrów opisujących badania).
Większość metaheurystyk używa funkcji celu w takiej postaci, w jakiej jest, i zmienia swoje optymalne zachowanie podczas wyszukiwania. Jednak niektóre algorytmy, takie jak kierowane wyszukiwanie lokalne , modyfikują reprezentację problemu, włączając informacje zebrane podczas wyszukiwania, bezpośrednio do funkcji celu.
Można zatem sklasyfikować metaheurystyki według tego, czy używają statycznej funkcji celu (która pozostaje niezmieniona w trakcie optymalizacji), czy dynamicznej (gdy funkcja celu jest modyfikowana podczas wyszukiwania).
Większość metaheurystyk stosowanych w kontekście kombinatorycznych problemów optymalizacji wykorzystuje strukturę pojedynczego sąsiedztwa. Jednak metody takie jak wyszukiwanie w zmiennym sąsiedztwie pozwalają na zmianę struktury podczas wyszukiwania.
Rozważając metaheurystykę jako metody iteracyjne, wykorzystujące próbkowanie funkcji celu jako podstawy uczenia się (definicja bardziej odpowiednia dla metaheurystyki populacyjnej) pojawia się problem wyboru próbkowania.
W zdecydowanej większości przypadków to próbkowanie odbywa się losowo i dlatego można je opisać za pomocą rozkładu prawdopodobieństwa . Istnieją zatem trzy klasy metaheurystyki, w zależności od podejścia zastosowanego do manipulowania tym rozkładem.
Pierwsza klasa to metody niejawne , w których rozkład prawdopodobieństwa nie jest znany a priori . Tak jest na przykład w przypadku algorytmów genetycznych, gdzie wybór próbkowania między dwiema iteracjami nie jest zgodny z określonym prawem, ale jest funkcją lokalnych reguł.
W przeciwieństwie do tego, możemy zatem sklasyfikować metody jawne , które wykorzystują rozkład prawdopodobieństwa wybrany w każdej iteracji. Tak jest w przypadku algorytmów szacowania rozkładu.
W tej klasyfikacji symulowane wyżarzanie zajmuje szczególne miejsce, ponieważ można uznać, że próbkuje funkcję celu, wykorzystując ją bezpośrednio jako rozkład prawdopodobieństwa (najlepsze rozwiązania mają większe prawdopodobieństwo rysowania). Nie jest zatem ani wyraźna, ani domniemana, ale raczej „bezpośrednia”.
Czasami znajdujemy klasyfikację przedstawiającą algorytmy optymalizacji stochastycznych jako „ ewolucyjne ” (lub „ewolucyjne”) lub nie. Algorytm będzie uważane za część klasy algorytmów ewolucyjnych manipuluje ludność za pośrednictwem tych podmiotów , zgodnie z pewnym ogólnym algorytmem.
Ten sposób prezentacji metaheurystyki ma dostosowaną nomenklaturę: będziemy mówić o operatorach dla każdej akcji modyfikującej stan jednego lub więcej rozwiązań. Operator budujący nowe rozwiązanie będzie nazywany generatorem , a operator modyfikujący istniejące rozwiązanie - mutatorem .
W tej perspektywie ogólna struktura algorytmów ewolucyjnych łączy etapy selekcji , rozmnażania (lub krzyżowania ), mutacji i ostatecznie zastępowania . Każdy krok używa mniej lub bardziej określonych operatorów.
O hybrydyzacji mówimy wtedy, gdy na rozważanie metaheurystyczne składa się kilka metod dzielących zadania badawcze. Taksonomia hybrydowych metaheurystyk dzieli się na dwie części: klasyfikację hierarchiczną i klasyfikację płaską . Klasyfikacja ma zastosowanie zarówno do metod deterministycznych, jak i metaheurystycznych.
Klasyfikacja hierarchiczna jest oparta na poziomie (niskim lub wysokim) hybrydyzacji i jej zastosowaniu (w przekaźniku lub równoczesnym). W hybrydyzacji niskiego poziomu dana funkcja metaheurystyki (np. Mutacja w algorytmie ewolucyjnym) zostaje zastąpiona inną metaheurystyczną (np. Wyszukiwanie z tabu). W przypadku poziomu wysokiego „normalne” wewnętrzne funkcjonowanie metaheurystyki nie ulega zmianie. W hybrydyzacji przekaźników metaheurystyki są uruchamiane jedna po drugiej, a każda z nich przyjmuje jako dane wejściowe dane wyjściowe wytworzone przez poprzednią. We współbieżności (lub koewolucji ) każdy algorytm wykorzystuje szereg współpracujących ze sobą agentów.
Ta pierwsza klasyfikacja wyróżnia cztery ogólne klasy:
Druga część identyfikuje kilka kryteriów, które mogą charakteryzować hybrydyzacje:
Te różne kategorie można łączyć, przy czym klasyfikacja hierarchiczna jest najbardziej ogólna.
Metaheurystyki są często używane ze względu na łatwość programowania i manipulacji. Rzeczywiście można je łatwo dostosować do każdego rodzaju problemu optymalizacji. Jednak najbardziej rozsądnie są one stosowane w trudnych problemach optymalizacyjnych , w których bardziej klasyczne metody optymalizacji (w szczególności metody deterministyczne) pokazują swoje ograniczenia.
Ogólnie można uznać, że zastosowanie metaheurystyki dość sprzyja problemom o następujących cechach:
Aby przetestować metaheurystykę, pierwszym krokiem jest użycie specjalnie zaprojektowanych funkcji matematycznych. Algorytmy są oceniane na podstawie zestawu funkcji, mniej lub bardziej trudnych, a następnie porównywane ze sobą.
Ponieważ metaheurystyki są generalnie stochastyczne, testy muszą w zasadzie być powtarzane bardzo wiele razy, a następnie wykorzystywane metodami statystycznymi . Jednak praktyka ta pozostaje stosunkowo rzadka w literaturze specjalistycznej.
W specjalnym numerze czasopisma naukowego European Journal of Operational Research , poświęconym zastosowaniom metaheurystyki, redaktorzy zauważyli, że większość z 20 opublikowanych artykułów dotyczy dwóch obszarów: harmonogramowania i logistyki . Najczęściej używane metody należą do rodziny algorytmów ewolucyjnych , często hybrydyzowanych z lokalnymi metodami wyszukiwania .
Kilka przykładów konkretnych problemów zoptymalizowanych za pomocą metaheurystyki:
Ponieważ metaheurystyki są bardzo ogólne, można je dostosować do każdego rodzaju problemu optymalizacji, który można zredukować do „czarnej skrzynki”. Często są mniej wydajne niż dokładne metody w przypadku niektórych typów problemów. Nie gwarantują też odkrycia globalnego optimum w skończonym czasie. Jednak wielu rzeczywistych problemów nie można skutecznie zoptymalizować za pomocą podejść czysto matematycznych , więc metaheurystyki można stosować z zyskiem.
Pojęcie efektywności generalnie odnosi się do dwóch sprzecznych celów: szybkości i precyzji . Szybkość jest często mierzona liczbą ocen funkcji celu, która jest przez większość czasu częścią najbardziej wymagającą obliczeń. Precyzja odnosi się do odległości między optimum znalezionym przez metaheurystykę a optymem rzeczywistym, albo z punktu widzenia rozwiązania, albo z punktu widzenia wartości. Bardzo często szybki algorytm jest nieprecyzyjny i odwrotnie.
Ogólnie rzecz biorąc, należy dokonać wyboru odpowiedniego kryterium zatrzymania. Często stosuje się szereg ocen lub wyznaczony czas, ale można też wybrać osiągnięcie określonej wartości funkcji celu (celem jest wówczas znalezienie powiązanego rozwiązania). Istnieje również możliwość doboru kryteriów w zależności od zachowania algorytmu, np. Minimalnego rozrzutu populacji punktów czy odpowiedniego parametru wewnętrznego. W każdym razie wybór kryterium zatrzymania wpłynie na jakość optymalizacji.
Zastosowanie metaheurystyki na pierwszy rzut oka może wydawać się stosunkowo proste, ale często konieczne jest dostosowanie algorytmu do zoptymalizowanego problemu. Przede wszystkim, głównie w kontekście optymalizacji kombinatorycznej , kluczowy może być wybór reprezentacji zmanipulowanych rozwiązań. Wówczas większość metaheurystyk ma parametry, których regulacja niekoniecznie jest banalna. Wreszcie, uzyskanie dobrej wydajności zazwyczaj obejmuje etap dostosowania różnych etapów algorytmu (w szczególności inicjalizacji). W praktyce tylko wiedza i doświadczenie użytkownika może zarządzać tymi problemami.
Przyjmuje się, że z bardzo ogólnego punktu widzenia żadna metaheurystyka nie jest naprawdę lepsza od innej. Rzeczywiście, metaheurysta nie może twierdzić, że jest bardziej skuteczny we wszystkich problemach, chociaż niektóre przykłady (tj. Sam algorytm, ale także wybór parametrów i dana implementacja) mogą być bardziej odpowiednie niż inne w przypadku pewnych klas problemów. To odkrycie jest opisane przez twierdzenie o braku darmowego lunchu .
W ostatecznym rozrachunku czasami jest możliwe, że wybór reprezentacji rozwiązań lub bardziej ogólnie metod związanych z metaheurystyką ma większy wpływ na wydajność niż sam typ algorytmu. W praktyce jednak metaheurystyki okazują się potężniejsze niż wyszukiwanie wyczerpujące lub metody wyszukiwania czysto losowe.
Najbardziej znane metaheurystyki to:
Istnieje bardzo wiele innych metaheurystyk, mniej lub bardziej znanych:
Ponieważ badania w tej dziedzinie są bardzo aktywne, niemożliwe jest stworzenie wyczerpującej listy różnych metaheurystyk optymalizacji. Literatura specjalistyczna wskazuje na dużą liczbę wariantów i hybrydyzacji między metodami, szczególnie w przypadku algorytmów ewolucyjnych.
Metaheurystyki, ze względu na swój elastyczny charakter, nadają się szczególnie do rozszerzeń. W ten sposób możemy znaleźć adaptacje dla bardziej złożonych problemów niż optymalizacja pojedynczej soczewki:
Ogólne strony internetowe
Oprogramowanie i frameworki