Wyszukiwanie lokalne z przewodnikiem

Wyszukiwanie lokalne z przewodnikiem jest metaheurystyczną metodą wyszukiwania. Metoda metaheurystyczna to metoda, która znajduje się na szczycie lokalnego algorytmu wyszukiwania w celu zmiany jego zachowania.

Wyszukiwanie lokalne z przewodnikiem powoduje naliczanie kar podczas przeszukiwania. Wykorzystuje kary, aby pomóc lokalnym algorytmom wyszukiwania uciec od lokalnych minimów i płaskowyżów. Gdy dany algorytm wyszukiwania lokalnego osiągnie lokalne optimum, GLS modyfikuje funkcję celu za pomocą określonego schematu (wyjaśnionego poniżej). Wtedy wyszukiwanie lokalne będzie działać z wykorzystaniem funkcji rozszerzonego celu, która ma na celu wyprowadzenie wyszukiwania z lokalnego optimum. Kluczem jest sposób modyfikacji funkcji celu.

Przegląd

Cechy rozwiązania

Aby zastosować GLS, należy zdefiniować cechy rozwiązania dla danego problemu. Cechy rozwiązania są definiowane w celu rozróżnienia rozwiązań o różnych cechach, tak aby można było rozpoznać i unikać regionów podobieństwa wokół lokalnych optimów. Wybór cech rozwiązania zależy od rodzaju problemu, a także w pewnym stopniu od lokalnego algorytmu wyszukiwania. $displaystyle$ każdej funkcji zdefiniowana funkcja kosztu $c_ {i}} .$

Każda cecha jest również powiązana z karą $),$ aby zarejestrować liczbę wystąpień cechy w lokalnych minimach

Cechy i koszty często wynikają bezpośrednio z funkcji celu. Na przykład w problemie komiwojażera „czy trasa prowadzi bezpośrednio z miasta X do miasta Y” można zdefiniować jako cechę. Odległość między X i Y można zdefiniować jako koszt. W problemach SAT i ważonych MAX-SAT cechami mogą być „czy klauzula C jest spełniona przez bieżące przypisania”.

$nie$ definiujemy dla każdej funkcji funkcję wskaźnika wskazującą , czy $obecna$ w bieżącym rozwiązaniu, czy ${\ displaystyle I_ {i}}$ wynosi 1, gdy rozwiązanie $wykazuje$ właściwość $razie$ , 0 otherwise.

Selektywne modyfikacje kar

GLS oblicza użyteczność karania każdej cechy. Kiedy lokalny algorytm wyszukiwania zwraca $(x,i)}$ minimum $poprzez$ przyrosty do kary za funkcje) obecne w tym rozwiązaniu, które mają , jak zdefiniowano poniżej.

{\ Displaystyle \ operatorname {util} (x, i) = I_ {i} (x) {\ Frac {c_ {i} (x)} {1 + p_ {i}}}.}

Chodzi o to, aby karać funkcje, które mają wysokie koszty, chociaż użyteczność takiego postępowania maleje, ponieważ funkcja jest coraz częściej karana.

Przeszukiwanie funkcji kosztów rozszerzonych

GLS wykorzystuje funkcję zwiększonego kosztu (zdefiniowaną poniżej), aby umożliwić lokalnemu algorytmowi wyszukiwania wyjście z lokalnego minimum poprzez karanie funkcji obecnych w tym lokalnym minimum. Chodzi o to, aby lokalne minimum było bardziej kosztowne niż otaczająca przestrzeń wyszukiwania, w której te cechy nie są obecne.

{\ Displaystyle g (x) = f (x) + \ lambda a \ suma _ {1 \ równoważnik ja \ leq m}I_{i}(x)p_{i}}

Parametr λ może być wykorzystany do zmiany intensywności poszukiwania rozwiązań. Wyższa wartość λ spowoduje bardziej zróżnicowane wyszukiwanie, w którym płaskowyże i baseny są przeszukiwane bardziej zgrubnie; niska wartość spowoduje bardziej intensywne poszukiwanie rozwiązania, w którym płaskowyże i baseny w krajobrazie poszukiwań są przeszukiwane z większą szczegółowością. Współczynnik $.$ do zrównoważenia części kary funkcji celu w stosunku do zmian funkcji celu i jest specyficzny dla problemu Prosta heurystyka do ustawiania ${\ displaystyle a}$ polega po prostu na zarejestrowaniu średniej zmiany funkcji celu aż do pierwszego lokalnego minimum, a następnie ustawieniu $wartości$ podzielonej przez liczbę cech GLS w instancji problemu.

Rozszerzenia wyszukiwania lokalnego z przewodnikiem

Mills (2002) opisał rozszerzone wyszukiwanie lokalne z przewodnikiem (EGLS), które wykorzystuje losowe ruchy i kryterium aspiracji zaprojektowane specjalnie dla programów opartych na karach. Powstały algorytm poprawił niezawodność GLS w zakresie ustawień parametrów, szczególnie w przypadku problemu przypisania kwadratowego . Ogólna wersja algorytmu GLS, wykorzystująca wspinaczkę górską opartą na minimalnych konfliktach (Minton i in. 1992) i częściowo oparta na GENET do spełniania ograniczeń i optymalizacji, została również zaimplementowana w projekcie Computer-Aided Constraint Programming .

Alsheddy (2011) rozszerzył wyszukiwanie lokalne z przewodnikiem na optymalizację wielocelową i zademonstrował jego zastosowanie we wzmacnianiu pozycji personelu w planowaniu ^{[ potrzebne źródło ]} .

Powiązana praca

GLS został zbudowany na GENET, który został opracowany przez Changa Wanga, Edwarda Tsanga i Andrew Davenporta.

Metoda breakout jest bardzo podobna do metody GENET. Został zaprojektowany z myślą o spełnianiu ograniczeń .

Wyszukiwanie tabu to klasa metod wyszukiwania, które można tworzyć w określonych metodach. GLS można postrzegać jako szczególny przypadek wyszukiwania Tabu .

Umieszczając GLS na algorytmie genetycznym , Tung-leng Lau wprowadził algorytm kierowanego programowania genetycznego (GGA). Został z powodzeniem zastosowany do ogólnego problemu przydziału (w szeregowaniu), problemu konfiguracji procesorów (w projektowaniu elektronicznym) oraz zestawu problemów przydziału częstotliwości łącza radiowego (abstrakcyjna aplikacja wojskowa).

Choi i in. rzuć GENET jako przeszukiwanie Lagrange'a.

Bibliografia

Alsheddy, A., Empowerment scheduling: a multi-obiektywne podejście optymalizacyjne przy użyciu lokalnego wyszukiwania z przewodnikiem, praca doktorska, Szkoła Informatyki i Inżynierii Elektronicznej, University of Essex, 2011 [1 ]
Choi, KMF, Lee, JHM & Stuckey, PJ, Lagrangian Reconstruction of GENET, Artificial Intelligence, 2000, 123 (1-2), 1-39
Davenport A., Tsang EPK, Kangmin Zhu & CJ Wang, GENET: Architektura koneksjonistyczna do rozwiązywania problemów z spełnianiem ograniczeń przez iteracyjne doskonalenie, Proc., AAAI, 1994, s.325-330 [2 ]
Lau, TL & Tsang, EPK, Rozwiązywanie problemu z konfiguracją procesora za pomocą algorytmu genetycznego opartego na mutacjach , International Journal on Artificial Intelligence Tools (IJAIT), World Scientific, tom 6, nr 4, grudzień 1997, 567-585
Lau, TL & Tsang, EPK, Algorytm genetyczny z przewodnikiem i jego zastosowanie do problemów przydziału częstotliwości łączy radiowych, Constraints, tom 6, nr 4, 2001, 373-398 [3]
Lau, TL & Tsang, EPK, Kierowany algorytm genetyczny i jego zastosowanie do ogólnych problemów przypisania , IEEE 10th International Conference on Tools with Artificial Intelligence (ICTAI'98), Tajwan, listopad 1998
Mills, P. & Tsang, EPK, Lokalne wyszukiwanie z przewodnikiem rozwiązywania problemów SAT i ważonych MAX-SAT, Journal of Automated Reasoning, Special Issue on Satisfiability Problems, Kluwer, Vol.24, 2000, 205-223 [4 ]
Mills, P. & Tsang, EPK & Ford, J., Zastosowanie rozszerzonego wyszukiwania lokalnego z przewodnikiem w problemie zadania kwadratowego, Annals of Operations Research, Kluwer Academic Publishers, Vol.118, 2003, 121-135 [5 ]
Minton, S., Johnston, M., Philips, AB & Laird, P., Minimalizowanie konfliktów: heurystyczna metoda naprawy dla spełnienia ograniczeń i problemów z planowaniem , Sztuczna inteligencja (specjalny tom dotyczący rozumowania opartego na ograniczeniach), tom 58, nr. 1-3 1992, 161-205
Tsang, EPK & Voudouris, C., Szybkie wyszukiwanie lokalne i wyszukiwanie lokalne z przewodnikiem oraz ich zastosowanie do problemu planowania siły roboczej British Telecom, Operations Research Letters, Elsevier Science Publishers, Amsterdam, tom 20, nr 3, marzec 1997, 119-127 [6]
Voudouris, C, Wyszukiwanie lokalne z przewodnikiem dla problemów optymalizacji kombinatorycznej, rozprawa doktorska, Wydział Informatyki, University of Essex, Colchester, Wielka Brytania, lipiec 1997 [7 ]
Voudouris, C., Wyszukiwanie lokalne z przewodnikiem — ilustracyjny przykład optymalizacji funkcji, BT Technology Journal, tom 16, nr 3, lipiec 1998, 46-50 [8]
Voudouris, C. & Tsang, EPK, Wyszukiwanie lokalne z przewodnikiem i jego zastosowanie do problemu komiwojażera, European Journal of Operational Research, Anbar Publishing, tom 113, wydanie 2, marzec 1999, 469-499 [9 ]
Voudouris, C. & Tsang, EPK, Wyszukiwanie lokalne z przewodnikiem dołącza do elity w optymalizacji dyskretnej , Seria DIMACS w matematyce dyskretnej i informatyce teoretycznej, tom 57, 2001, 29-39 [10 ]
Voudouris, C. & Tsang, EPK, Wyszukiwanie lokalne z przewodnikiem, w: F. Glover (red.), Handbook of metaheuristics, Kluwer, 2003, 185-218 [ 11]
Voudouris, C., Tsang, EPK i Alsheddy, A., Wyszukiwanie lokalne z przewodnikiem, rozdział 11, w M. Gendreau i JY Potvin (red.), Handbook of Metaheuristics, Springer, 2010, 321-361

Linki zewnętrzne

Strona główna wyszukiwania lokalnego z przewodnikiem