Co to są hiper-heurystyki?

Chciałem wiedzieć, jakie są różnice między hiper-heurystykami i meta-heurystykami oraz jakie są ich główne zastosowania. Jakie problemy można rozwiązać za pomocą funkcji Hyper-heurystyki?

TL: DR : Hiperheurystyka to metaheurystyka, odpowiednia do rozwiązywania tego samego rodzaju problemów optymalizacyjnych, ale (w zasadzie) zapewniająca podejście „szybkiego prototypowania” dla osób niebędących ekspertami. W praktyce występują problemy z dominującym podejściem, motywujące pojawiającą się perspektywę hiperheurystyki „białej skrzynki” .

Bardziej szczegółowo:

Metaheurystyki to metody poszukiwania niewyobrażalnie dużej przestrzeni możliwych rozwiązań w celu znalezienia rozwiązania „wysokiej jakości”. Popularne metaheurystyki obejmują symulowane wyżarzanie, wyszukiwanie Tabu, algorytmy genetyczne itp.

Zasadniczą różnicą między metaheurystykami i hiperheurystykami jest dodanie poziomu pośredniego wyszukiwania: nieformalnie hiperheurystykę można opisać jako „heurystykę przeszukiwania przestrzeni heurystycznej”. Można zatem zastosować dowolny metaheurystyczny jako hiperheurystyczny, pod warunkiem, że natura „przestrzeni heurystycznej” do przeszukiwania jest odpowiednio zdefiniowana.

Obszar zastosowania hiperheurystyki jest zatem taki sam, jak metaheurystyki. Ich zastosowanie (w odniesieniu do metaheurystyk) jest „narzędziem szybkiego prototypowania”: pierwotną motywacją było umożliwienie osobom niebędącym ekspertami stosowania metaheurystyk do ich specyficznego problemu optymalizacji (np. „Traveling-Salesman (TSP) plus okna czasowe plus bin- pakowanie ”) bez konieczności posiadania specjalistycznej wiedzy w wysoce specyficznej dziedzinie problemów. Pomysł polegał na tym, że można to zrobić poprzez:

1. Umożliwiając praktykom wdrażanie tylko bardzo prostych (skutecznie, losowych) heurystyk do przekształcania potencjalnych rozwiązań. Na przykład w przypadku TSP: „zamień dwa losowe miasta” zamiast (powiedzmy) bardziej złożonej heurystyki Lin-Kernighana .
2. Osiągaj efektywne wyniki (pomimo stosowania tych prostych heurystyk) poprzez łączenie / sekwencjonowanie ich w inteligentny sposób, zwykle poprzez zastosowanie jakiejś formy mechanizmu uczenia się.

Hiper-heurystykę można opisać jako „selektywną” lub „generatywną” w zależności od tego, czy heurystyka jest (odpowiednio) sekwencjonowana czy łączona. Generatywna hiperheurystyka często wykorzystuje zatem metody takie jak programowanie genetyczne do łączenia prymitywnej heurystyki i dlatego są one zazwyczaj dostosowywane przez specjalistę w celu rozwiązania konkretnego problemu. Na przykład w oryginalnym artykule na temat generatywnej hiper-heurystyki wykorzystano uczący się system klasyfikacyjny do połączenia heurystyki z pakowaniem bin. Ponieważ podejścia generatywne są specyficzne dla problemu, poniższe komentarze ich nie dotyczą.

Natomiast pierwotnym czynnikiem motywującym do selektywnej hiper-heurystyki było to, że badacze byliby w stanie stworzyć hiper-heurystyczny solver, który wówczas prawdopodobnie działałby dobrze w niewidzialnej dziedzinie problemów, wykorzystując jedynie prostą randomizowaną heurystykę.

Tradycyjnie realizowano to poprzez wprowadzenie „hiper-heurystycznej bariery domen” (patrz rysunek poniżej), w której twierdzi się, że ogólność w domenach problemowych jest osiągalna poprzez uniemożliwienie solverowi znajomości dziedziny, w której działa. Zamiast tego rozwiązałby problem, operując tylko nieprzezroczystymi indeksami liczb całkowitych na liście dostępnych heurystyk (np. W stylu „problemu uzbrojonego bandyty” ).

W praktyce to podejście „ślepe na domeny” nie doprowadziło do rozwiązań o wystarczającej jakości. Aby osiągnąć wyniki porównywalne z metaheurystykami problemowymi, badacze hiperheurystyczni musieli wdrożyć złożone heurystyki specyficzne dla problemu, tym samym nie osiągając celu szybkiego prototypowania.

Nadal możliwe jest w zasadzie stworzyć selektywną hiper-heurystyczny solver, która jest zdolna do uogólniania do nowych domen problemowych, ale zostało to utrudnione, ponieważ powyższym pojęciem domen środków barierowych, że tylko bardzo ograniczony zestaw funkcji jest dostępny na krzyż - uczenie się w domenie (np. na przykładzie popularnej selektywnej hiperheurystycznej struktury ).

Nowsza perspektywa badawcza w kierunku hiper-heurystyki „białej skrzynki” opowiada się za deklaratywnym, bogatym w funkcje podejściem do opisywania domen problemowych. Takie podejście ma wiele deklarowanych zalet:

1. Praktycy nie muszą już wdrażać heurystyki, ale po prostu określają dziedzinę problemów.
2. Eliminuje barierę domenową, umieszczając hiper-heurystykę na tym samym „poinformowanym” statusie problemu, co metaheurystyki specyficzne dla problemu.
3. Przy opisie problemu z białą skrzynką niesławne twierdzenie „No Free Lunch” (które zasadniczo stwierdza, że ​​biorąc pod uwagę wszystkie problemy z czarnymi skrzynkami , Symulowane wyżarzanie z nieskończonym harmonogramem wyżarzania jest średnio tak dobre, jak każde inne podejście) nie dłużej obowiązuje.

WYŁĄCZENIE ODPOWIEDZIALNOŚCI: Pracuję w tym obszarze badawczym, dlatego niemożliwe jest usunięcie wszystkich osobistych uprzedzeń z odpowiedzi.