Qu'est-ce que l'hyper-heuristique?

Je voulais savoir quelles sont les différences entre l'hyper-heuristique et la méta-heuristique, et quelles sont leurs principales applications. Quels problèmes peuvent être résolus par l'hyper-heuristique?

TL: DR : Les hyper-heuristiques sont des métaheuristiques, adaptées pour résoudre le même type de problèmes d'optimisation, mais offrant (en principe) une approche de "prototypage rapide" pour les praticiens non experts. Dans la pratique, il y a des problèmes avec l'approche dominante, motivant une perspective émergente sur l'hyper-heuristique «whitebox» .

Plus en détail:

Les métaheuristiques sont des méthodes permettant de rechercher un espace insurmontablement vaste de solutions possibles afin de trouver une solution de «haute qualité». Les métaheuristiques populaires incluent le recuit simulé, la recherche Tabu, les algorithmes génétiques, etc.

La différence essentielle entre la métaheuristique et l'hyper-heuristique est l'ajout d'un niveau d'indirection de recherche: de manière informelle, l'hyper-heuristique peut être décrite comme une «heuristique pour rechercher l'espace de l'heuristique». On peut donc utiliser n'importe quelle métaheuristique comme une hyper-heuristique, à condition que la nature de «l'espace d'heuristique» à rechercher soit correctement définie.

Le domaine d'application de l'hyper-heuristique est donc le même que celui de la métaheuristique. Leur applicabilité (par rapport aux métaheuristiques) est comme un «outil de prototypage rapide»: la motivation initiale était de permettre aux praticiens non experts d'appliquer des métaheuristiques à leur problème d'optimisation spécifique (par exemple «Travelling-Salesman (TSP) plus des fenêtres de temps plus bin- ") sans nécessiter d’expertise dans le domaine hautement spécifique du problème. L'idée était que cela pourrait être fait par:

1. Permettre aux praticiens de ne mettre en œuvre que des heuristiques très simples (efficaces et randomisées) pour transformer des solutions potentielles. Par exemple, pour le TSP: «permutez deux villes aléatoires» plutôt que (disons) l' heuristique plus complexe de Lin-Kernighan .
2. Obtenez des résultats efficaces (malgré l'utilisation de ces heuristiques simples) en les combinant / les séquençant de manière intelligente, généralement en utilisant une certaine forme de mécanisme d'apprentissage.

L'hyper-heuristique peut être décrite comme «sélective» ou «générative» selon que les heuristiques sont (respectivement) séquencées ou combinées. L'hyper-heuristique générative utilise donc souvent des méthodes telles que la programmation génétique pour combiner l'heuristique primitive et est donc généralement personnalisée par le praticien pour résoudre un problème spécifique. Par exemple, l' article original sur l'hyper-heuristique générative utilisait un système de classificateur d'apprentissage pour combiner l'heuristique pour le bin-packing. Étant donné que les approches génératives sont spécifiques au problème, les commentaires ci-dessous ne s'appliquent pas à eux.

En revanche, la motivation initiale de l'hyper-heuristique sélective était que les chercheurs seraient en mesure de créer un solveur hyper-heuristique qui serait alors susceptible de bien fonctionner dans un domaine de problème invisible, en utilisant uniquement des heuristiques aléatoires simples.

La manière dont cela a été traditionnellement mis en œuvre a été l'introduction de la `` barrière de domaine hyper-heuristique '' (voir la figure ci-dessous), selon laquelle la généralité entre les domaines problématiques serait réalisable en empêchant le solveur de connaître le domaine sur lequel il fonctionne. Au lieu de cela, il résoudrait le problème en fonctionnant uniquement sur des indices entiers opaques dans une liste d'heuristiques disponibles (par exemple à la manière du «problème des bandits multi-armés» ).

Dans la pratique, cette approche «aveugle du domaine» n'a pas abouti à des solutions de qualité suffisante. Afin d'obtenir des résultats comparables à ceux des métaheuristiques spécifiques aux problèmes, les chercheurs en hyper-heuristique ont dû mettre en œuvre des heuristiques complexes spécifiques aux problèmes, échouant ainsi dans l'objectif du prototypage rapide.

Il est toujours possible en principe de créer un solveur hyper-heuristique sélectif capable de généraliser à de nouveaux domaines problématiques, mais cela a été rendu plus difficile car la notion ci-dessus de barrière de domaine signifie que seul un ensemble de fonctionnalités très limité est disponible pour -apprentissage de domaine (par exemple comme illustré par un cadre hyper-heuristique sélectif populaire ).

Une perspective de recherche plus récente sur l'hyper-heuristique «boîte blanche» préconise une approche déclarative et riche en fonctionnalités pour décrire les domaines problématiques. Cette approche présente un certain nombre d'avantages revendiqués:

1. Les praticiens n'ont plus besoin d' implémenter l' heuristique, mais spécifient simplement le domaine problématique.
2. Il élimine la barrière de domaine, plaçant l'hyper-heuristique sur le même statut «informé» du problème que les métaheuristiques spécifiques au problème.
3. Avec une description de problème de boîte blanche, le fameux théorème `` Pas de déjeuner gratuit '' (qui énonce essentiellement que, considéré sur l'espace de tous les problèmes de boîte noire , le recuit simulé avec un calendrier de recuit infini est, en moyenne, aussi bon que toute autre approche) non s'applique plus.

AVERTISSEMENT: Je travaille dans ce domaine de recherche, et il est donc impossible de supprimer tout parti pris personnel de la réponse.