Was sind Hyperheuristiken?

Ich wollte wissen, was die Unterschiede zwischen Hyperheuristik und Metaheuristik sind und welche Hauptanwendungen sie haben. Welche Probleme eignen sich zur Lösung durch Hyperheuristik?

TL: DR : Hyperheuristiken sind Metaheuristiken, die zur Lösung der gleichen Art von Optimierungsproblemen geeignet sind , aber (im Prinzip) einen "Rapid Prototyping" -Ansatz für Nichtfachleute bieten. In der Praxis gibt es Probleme mit dem vorherrschenden Ansatz, die eine neue Perspektive auf die White-Box-Hyperheuristik motivieren .

Genauer:

Metaheuristiken sind Methoden zur Suche in einem unlösbar großen Raum möglicher Lösungen, um eine qualitativ hochwertige Lösung zu finden. Beliebte Metaheuristiken umfassen simuliertes Tempern, Tabu-Suche, genetische Algorithmen usw.

Der wesentliche Unterschied zwischen Metaheuristik und Hyperheuristik besteht in der Hinzufügung einer Ebene der Suchindirektion: Informell kann Hyperheuristik als "Heuristik zur Suche im Raum der Heuristik" bezeichnet werden. Man kann daher jede Metaheuristik als Hyperheuristik verwenden, vorausgesetzt, die Art des zu durchsuchenden "Raums der Heuristik" ist angemessen definiert.

Der Anwendungsbereich für Hyperheuristiken ist daher der gleiche wie für Metaheuristiken. Ihre Anwendbarkeit (in Bezug auf Metaheuristiken) ist ein "Rapid Prototyping Tool": Die ursprüngliche Motivation bestand darin, nicht fachkundigen Praktikern die Anwendung von Metaheuristiken auf ihr spezifisches Optimierungsproblem zu ermöglichen (z. B. "Travelling-Salesman (TSP) plus Zeitfenster plus Bin-"). Verpackung ") ohne Fachkenntnisse im hochspezifischen Problembereich. Die Idee war, dass dies getan werden könnte durch:

1. Ermöglichen, dass Praktiker nur sehr einfache (effektiv, randomisierte) Heuristiken implementieren, um mögliche Lösungen zu transformieren. Zum Beispiel für den TSP: "Zwei zufällige Städte tauschen" anstatt (sagen wir) die komplexere Lin-Kernighan- Heuristik.
2. Erzielen Sie effektive Ergebnisse (trotz Verwendung dieser einfachen Heuristiken), indem Sie sie auf intelligente Weise kombinieren / sequenzieren, in der Regel mithilfe eines Lernmechanismus.

Hyperheuristiken können als "selektiv" oder "generativ" beschrieben werden, je nachdem, ob die Heuristiken (jeweils) sequenziert oder kombiniert sind. Generative Hyperheuristiken verwenden daher häufig Methoden wie die genetische Programmierung, um primitive Heuristiken zu kombinieren, und werden daher typischerweise vom Praktiker angepasst, um ein bestimmtes Problem zu lösen. In der Originalarbeit über generative Hyperheuristiken wurde beispielsweise ein Learning Classifier System verwendet, um Heuristiken für das Verpacken von Behältern zu kombinieren. Da generative Ansätze problemspezifisch sind, gelten die folgenden Kommentare nicht für sie.

Im Gegensatz dazu war der ursprüngliche Motivator für selektive Hyperheuristiken, dass Forscher in der Lage sein würden, einen hyperheuristischen Löser zu erstellen, der dann wahrscheinlich in einem unsichtbaren Problembereich gut funktioniert, wenn nur einfache randomisierte Heuristiken verwendet werden.

Die Art und Weise, wie dies traditionell implementiert wurde, erfolgte über die Einführung der "hyperheuristischen Domänenbarriere" (siehe Abbildung unten), wobei behauptet wird, dass die Allgemeinheit über Problemdomänen hinweg erreichbar ist, indem verhindert wird, dass der Löser Kenntnis von der Domäne hat, auf der er sich befindet es funktioniert. Stattdessen würde es das Problem lösen, indem nur undurchsichtige ganzzahlige Indizes in eine Liste verfügbarer Heuristiken aufgenommen werden (z. B. nach Art des "Multi-Armed Bandit Problem" ).

In der Praxis hat dieser "Domain Blind" -Ansatz nicht zu Lösungen von ausreichender Qualität geführt. Um überall Ergebnisse zu erzielen, die mit problemspezifischen Metaheuristiken vergleichbar sind, mussten hyperheuristische Forscher komplexe problemspezifische Heuristiken implementieren, wodurch das Ziel des Rapid Prototyping verfehlt wurde.

Grundsätzlich ist es immer noch möglich , einen selektiven hyperheuristischen Löser zu erstellen, der in der Lage ist, auf neue Problemdomänen zu verallgemeinern. Dies wurde jedoch erschwert, da der obige Begriff der Domänenbarriere bedeutet, dass nur ein sehr begrenzter Funktionsumfang für Cross verfügbar ist -Domänenlernen (z. B. am Beispiel eines beliebten selektiven hyperheuristischen Rahmens ).

Eine neuere Forschungsperspektive zur 'Whitebox'-Hyperheuristik befürwortet einen deklarativen, funktionsreichen Ansatz zur Beschreibung von Problembereichen. Dieser Ansatz hat eine Reihe von behaupteten Vorteilen:

1. Praktiker müssen jetzt keine Heuristiken mehr implementieren , sondern einfach die Problemdomäne angeben .
2. Es beseitigt die Domänenbarriere und versetzt Hyperheuristiken in den gleichen "informierten" Status über das Problem wie problemspezifische Metaheuristiken.
3. Mit einer Whitebox-Problembeschreibung ist das berüchtigte Theorem „No Free Lunch“ (das im Wesentlichen besagt, dass simuliertes Glühen mit einem unendlichen Glühplan über den Raum aller Black-Box- Probleme im Durchschnitt so gut ist wie jeder andere Ansatz) Nr länger gilt.

HAFTUNGSAUSSCHLUSS: Ich arbeite in diesem Forschungsbereich und es ist daher unmöglich, alle persönlichen Vorurteile aus der Antwort zu entfernen.