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ę:

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ń:

Zobacz też

Referencje i uwagi

Linki zewnętrzne

Bibliografie hiperheurystyczne

Grupy badawcze

Ostatnie aktywności

Inne