Hiperheurystyka — Hyper-heuristic
Hiper-heurystyczny jest heurystyczne metody wyszukiwania, które ma na celu automatyzację, często poprzez włączenie uczenia maszynowego technik, proces wyboru, łączenie, generujących lub dostosowujących kilka prostszych heurystyki (lub części składowych takich heurystyki), aby skutecznie rozwiązać problemów obliczeniowych wyszukiwania. Jedną z motywacji do studiowania hiperheurystyki jest budowanie systemów, które mogą poradzić sobie z klasami problemów, a nie rozwiązywać tylko jeden problem.
Może istnieć wiele heurystyk, z których można wybrać rozwiązanie problemu, a każda heurystyka ma swoje mocne i słabe strony. Chodzi o to, aby automatycznie opracowywać algorytmy, łącząc siłę i kompensując słabość znanych heurystyk. W typowych ramach hiperheurystycznych istnieje metodologia wysokiego poziomu i zestaw heurystyk niskiego poziomu (heurystyki konstruktywne lub perturbacyjne). Biorąc pod uwagę wystąpienie problemu, metoda wysokiego poziomu wybiera, która heurystyka niskiego poziomu powinna być zastosowana w danym momencie, w zależności od bieżącego stanu problemu (lub etapu wyszukiwania) określonego przez cechy.
Hiperheurystyka kontra metaheurystyka
Podstawowa różnica między metaheurystyką a hiperheurystyką polega na tym, że większość implementacji metaheurystyki przeszukuje przestrzeń poszukiwań rozwiązań problemów, podczas gdy hiperheurystyki zawsze przeszukują przestrzeń poszukiwań heurystycznych. Tak więc, używając hiperheurystyk, staramy się znaleźć właściwą metodę lub sekwencję heurystyk w danej sytuacji, zamiast próbować bezpośrednio rozwiązać problem. Ponadto poszukujemy ogólnie stosowanej metodologii, a nie rozwiązania pojedynczej instancji problemu.
Hiperheurystyki można by uznać za metody „gotowe”, w przeciwieństwie do metaheurystyk „szytych na miarę”. Mają być metodami generycznymi, które powinny dawać rozwiązania o akceptowalnej jakości, oparte na zestawie łatwych do wdrożenia heurystyk niskiego poziomu.
Motywacja
Pomimo znacznego postępu w budowaniu metodologii wyszukiwania dla szerokiej gamy obszarów zastosowań do tej pory, takie podejścia nadal wymagają od specjalistów zintegrowania swojej wiedzy specjalistycznej w danej dziedzinie problemowej. . Wielu badaczy z dziedziny informatyki , sztucznej inteligencji i badań operacyjnych dostrzegło już potrzebę opracowania zautomatyzowanych systemów, które zastąpiłyby rolę człowieka-eksperta w takich sytuacjach. Jeden z głównych pomysłów na automatyzację projektowania heurystyk wymaga włączenia mechanizmów uczenia maszynowego do algorytmów w celu adaptacyjnego kierowania wyszukiwaniem. Zarówno procesy uczenia się, jak i adaptacji mogą być realizowane w trybie on-line lub off-line i opierać się na heurystyce konstruktywnej lub perturbacyjnej.
Hiperheurystyka zwykle ma na celu zmniejszenie ilości wiedzy dziedzinowej w metodologii wyszukiwania. Wynikowe podejście powinno być tanie i szybkie do wdrożenia, wymagające mniejszej wiedzy w dziedzinie problemowej lub metod heurystycznych, a także (idealnie) wystarczająco solidne, aby skutecznie obsługiwać szereg przypadków problemów z różnych dziedzin. Celem jest podniesienie poziomu ogólności metodologii wspomagania decyzji, być może kosztem obniżonej - ale wciąż akceptowalnej - jakości rozwiązania w porównaniu z szytymi na miarę podejściami metaheurystycznymi. W celu zmniejszenia luki między schematami szytymi na miarę a strategiami opartymi na hiperheurystyce, zaproponowano równoległe hiperheurystyki.
Początki
Termin „hiperheurystyka” został po raz pierwszy ukuty w publikacji z 2000 roku autorstwa Cowlinga i Soubeigi, którzy użyli go do opisania idei „heurystyk do wyboru heurystyk”. Użyli podejścia do uczenia maszynowego „funkcji wyboru”, które godzi eksploatację i eksplorację przy wyborze następnej heurystyki do użycia. Następnie Cowling, Soubeiga, Kendall, Han, Ross i inni autorzy zbadali i rozszerzyli tę ideę w obszarach takich jak algorytmy ewolucyjne i patologiczne heurystyki niskiego poziomu. Pierwszy artykuł w czasopiśmie, w którym użyto tego terminu, pojawił się w 2003 roku. Pochodzenie pomysłu (choć nie samego terminu) sięga wczesnych lat 60. XX wieku i zostało niezależnie odkryte na nowo i kilka razy rozszerzone w latach 90. XX wieku. W domenie Job Shop Scheduling pionierska praca Fishera i Thompsona wysunęła hipotezę i udowodniła eksperymentalnie, wykorzystując uczenie probabilistyczne, że łączenie reguł harmonogramowania (znanych również jako reguły priorytetowe lub dyspozytorskie) jest lepsze niż którekolwiek z reguł rozpatrywanych oddzielnie. Chociaż termin ten nie był wtedy używany, był to pierwszy artykuł „hiperheurystyczny”. Kolejny korzeń inspirujący koncepcję hiperheurystyki pochodzi z dziedziny sztucznej inteligencji . Mówiąc dokładniej, pochodzi z pracy nad zautomatyzowanymi systemami planowania i jej ostatecznego skupienia się na problemie uczenia się wiedzy o sterowaniu. Tak zwany system COMPOSER, opracowany przez Gratch et al., został wykorzystany do kontrolowania harmonogramów komunikacji satelitarnej obejmującej szereg satelitów krążących wokół Ziemi i trzy stacje naziemne. System można scharakteryzować jako poszukiwanie pokonywania wzniesień w przestrzeni możliwych strategii sterowania.
Klasyfikacja podejść
Dotychczasowe podejścia hiperheurystyczne można podzielić na dwie główne kategorie. W pierwszej klasie, uchwyconej przez frazę heurystyka do wyboru heurystyk , schemat hiperheurystyczny jest wyposażony w zestaw wcześniej istniejących, powszechnie znanych heurystyk do rozwiązania docelowego problemu. Zadanie polega na odkryciu odpowiedniej sekwencji zastosowań tych heurystyk (znanych również jako heurystyki niskiego poziomu w dziedzinie hiperheurystyk) w celu efektywnego rozwiązania problemu. Na każdym etapie podejmowania decyzji heurystyka jest wybierana za pomocą komponentu zwanego mechanizmem selekcji i stosowana do istniejącego rozwiązania. Nowe rozwiązanie powstałe z zastosowania wybranej heurystyki jest akceptowane/odrzucane na podstawie innego komponentu zwanego kryterium akceptacji. Odrzucenie rozwiązania oznacza, że jest ono po prostu odrzucane, podczas gdy akceptacja prowadzi do zastąpienia dotychczasowego rozwiązania. W drugiej klasie, heurystyki do generowania heurystyk , kluczową ideą jest „rozwijanie nowej heurystyki poprzez wykorzystanie składników znanych heurystyk”. Proces ten wymaga, podobnie jak w przypadku pierwszej klasy hiperheurystyk, wyboru odpowiedniego zestawu heurystyk, o których wiadomo, że są przydatne w rozwiązaniu docelowego problemu. Jednak zamiast dostarczać je bezpośrednio do frameworka, heurystyki są najpierw rozkładane na ich podstawowe składniki.
Te dwa główne typy można dalej skategoryzować w zależności od tego, czy opierają się na poszukiwaniach konstruktywnych, czy perturbacyjnych. Dodatkowa ortogonalna klasyfikacja hiperheurystyk uwzględnia źródło dostarczające informacji zwrotnej podczas procesu uczenia się, którym może być jeden przypadek ( uczenie się on-line ) lub wiele przykładów badanego problemu podstawowego ( uczenie się off-line ).
Metodologie wyboru heurystyk
Odkryj dobre kombinacje stałych, zaprojektowanych przez człowieka, dobrze znanych heurystyk niskiego poziomu.
- Oparte na konstruktywnych heurystykach
- W oparciu o perturbacyjne heurystyki
Metodologie generowania heurystyk
Generuj nowe metody heurystyczne, korzystając z podstawowych komponentów wcześniej istniejących metod heurystycznych.
- W oparciu o podstawowe elementy heurystyki konstruktywnej
- W oparciu o podstawowe elementy heurystyk perturbacyjnych
Hiperheurystyka uczenia się online
Uczenie ma miejsce, gdy algorytm rozwiązuje instancję problemu, dlatego zależne od zadania właściwości lokalne mogą być wykorzystywane przez strategię wysokiego poziomu do określenia odpowiedniej heurystyki niskiego poziomu do zastosowania. Przykładami podejść do uczenia się on-line w ramach hiperheurystyk są: wykorzystanie uczenia wzmacniającego do selekcji heurystycznej i ogólnie wykorzystanie metaheurystyk jako strategii wyszukiwania wysokiego poziomu w przestrzeni wyszukiwania heurystyki.
Hiperheurystyka uczenia się offline
Chodzi o to, aby zebrać wiedzę w postaci reguł lub programów ze zbioru instancji szkoleniowych, które, miejmy nadzieję, uogólniłyby proces rozwiązywania niewidzialnych instancji. Przykładami podejść do uczenia się off-line w ramach hiperheurystyk są: uczenie się systemów klasyfikatorów , wnioskowanie oparte na przypadku i programowanie genetyczne .
W 2020 r. przedstawiono rozszerzoną klasyfikację hiperheurystyk selekcji , aby zapewnić bardziej wszechstronną kategoryzację współczesnych metod hiperheurystyki selekcji.
Aplikacje
Hiperheurystyka została zastosowana w wielu różnych problemach. Rzeczywiście, jedną z motywacji hiperheurystyk jest możliwość operowania różnymi typami problemów. Poniższa lista jest niewyczerpującym wyborem niektórych problemów i dziedzin, w których zbadano hiperheurystykę:
- problem z pakowaniem do kosza
- problem spełnialności logicznej
- edukacyjny plan lekcji
- planowanie warsztatów
- wielocelowe rozwiązywanie problemów i alokacja przestrzeni
- dyżur pielęgniarek
- planowanie personelu
- problem komiwojażera
- problem z wyznaczaniem trasy pojazdu
- wielowymiarowy problem z plecakiem
- 0-1 problem z plecakiem
- maksymalny problem cięcia cut
- kwadratowy problem przypisania
- układ farmy wiatrowej
Powiązane obszary
Hiperheurystyka nie jest jedynym podejściem badanym w poszukiwaniu bardziej ogólnych i odpowiednich metodologii wyszukiwania. Wielu badaczy informatyki, sztucznej inteligencji i badań operacyjnych dostrzegło już potrzebę opracowania zautomatyzowanych systemów, które zastąpiłyby rolę człowieka-eksperta w procesie dostrajania i adaptacji metodologii wyszukiwania. Poniższa lista przedstawia niektóre powiązane obszary badań:
- adaptacja i samoadaptacja parametrów algorytmu,
- adaptacyjny algorytm memetyczny
- adaptacyjne przeszukiwanie dużej okolicy
- konfiguracja algorytmu
- kontrola algorytmu
- portfele algorytmów
- wyszukiwanie autonomiczne
- programowanie genetyczne
- kodowania pośrednie w algorytmach ewolucyjnych
- wyszukiwanie zmiennych sąsiedztwa
- wyszukiwanie reaktywne
Zobacz też
- Konstruktywna heurystyka
- Metaoptymalizacja jest ściśle związana z hiperheurystyką.
- algorytmy genetyczne
- programowanie genetyczne
- algorytmy ewolucyjne
- wyszukiwanie lokalne (optymalizacja)
- nauczanie maszynowe
- algorytmy memetyczne
- metaheurystyka
- brak darmowego lunchu w wyszukiwaniu i optymalizacji
- optymalizacja roju cząstek
- wyszukiwanie reaktywne
Referencje i uwagi
Linki zewnętrzne
Bibliografie hiperheurystyczne
Grupy badawcze
- Laboratorium Sztucznej Inteligencji (ART+I) , Uniwersytet Yeditepe , Turcja
- Grupa badawcza zautomatyzowanego planowania, optymalizacji i planowania (ASAP) , University of Nottingham , Wielka Brytania
- Grupa Badawcza ds. Optymalizacji Kombinatorycznej i Wspomagania Decyzji (CODeS) , KU Leuven , Belgia
- Computational-Heuristics, Operations Research and Decision-Support (CHORDS) Research Group , University of Stirling , Wielka Brytania
- Grupa Badawcza Obliczeń Ewolucyjnych , Victoria University of Wellington , Nowa Zelandia
- Laboratorium systemów inteligentnych , Uniwersytet Heriot-Watt , Wielka Brytania
- Grupa Badawcza Inteligentnych Systemów , Tecnologico de Monterrey , Meksyk .
- Machine Learning i Badań Operacyjnych (pamięć) Lab , Nanjing University of Aeronautyki i Astronautyki , PRChina
- Modeling Optimization Scheduling and Intelligent Control (MOSAIC) Research Group , University of Bradford , Wielka Brytania
- Grupa Badań Operacyjnych (OR) , Queen Mary University of London , Wielka Brytania,
- Optymalizacja oprogramowania za pomocą obliczeń z grupy badawczej ARtificial intelligence (OSCAR) , Dalian University of Technology , PRChina
Ostatnie aktywności
- Streamuj z Hyper-heuristics @ EURO 2019
- Zaproszenie na sesję na temat zautomatyzowanego projektowania algorytmów dla problemów optymalizacji wielokryterialnej @ MCDM 2019
- 8. warsztaty nt. obliczeń ewolucyjnych w zautomatyzowanym projektowaniu algorytmów (ECADA) @ GECCO 2018
- Streamuj z Hyper-heurystyki na EURO 2018
- Sesja specjalna na temat Automated Algorithm Design as Ensemble Techniques @ IEEE CIEL / SSCI 2017
- Samouczek dotyczący wyboru algorytmu: techniki offline + online @ SEAL 2017
- I Sympozjum AISB nt. Metaoptymalizacji: Hiperheurystyka i nie tylko @ AISB Convention 2013
- Współczesna hiperheurystyka dla problemów optymalizacji na dużą skalę @ META2012
- Samouczek dotyczący hiperheurystyki i optymalizacji międzydomenowej @ GECCO 2012
- Własny* utwór wyszukiwania @ GECCO 2012
- Sesja specjalna na temat hiperheurystyki opartej na ewolucji i ich zastosowaniach @ IEEE CEC2012 (WCCI2012)
- Sesja specjalna dotycząca międzydomenowego wyszukiwania heurystycznego (LION-CHESC) @ LION2012
- Wyzwanie międzydomenowego wyszukiwania heurystycznego 2011 (CHESC 2011)
- Sesja specjalna na temat systemów do budowania systemów @ MISTA 2011
- Samouczek dotyczący zautomatyzowanego projektowania heurystycznego @ GECCO 2011
- Sesja specjalna na temat hybrydowych algorytmów ewolucyjnych, hiperheurystyki i obliczeń memetycznych @ IEEE CEC2010 (WCCI 2010)
- Warsztaty na temat samodostrajania, samokonfiguracji i samogenerujących heurystyk wyszukiwania (Self* 2010) @ PPSN 2010
- Warsztaty o hiperheurystyce @ PPSN 2008