O que são hiper-heurísticas?

Eu queria saber quais são as diferenças entre hiper-heurísticas e meta-heurísticas e quais são suas principais aplicações. Quais problemas são adequados para serem resolvidos pelas hiper-heurísticas?

TL: DR : As hiper-heurísticas são meta -heurísticas , adequadas para resolver o mesmo tipo de problemas de otimização, mas (em princípio) que proporcionam uma abordagem de "prototipagem rápida" para profissionais não especialistas. Na prática, existem problemas com a abordagem predominante, motivando uma perspectiva emergente sobre as hiper-heurísticas da 'caixa branca' .

Em mais detalhes:

Metaheurísticas são métodos para pesquisar um espaço intratávelmente grande de possíveis soluções, a fim de encontrar uma solução de 'alta qualidade'. As metaheurísticas populares incluem Recozimento Simulado, Pesquisa de Tabu, Algoritmos Genéticos etc.

A diferença essencial entre meta-heurísticas e hiper-heurísticas é a adição de um nível de indireção de pesquisa: informalmente, as hiper-heurísticas podem ser descritas como 'heurísticas para pesquisar no espaço das heurísticas'. Pode-se, portanto, usar qualquer meta-heurística como uma hiper-heurística, desde que a natureza do 'espaço das heurísticas' a serem pesquisadas seja definida adequadamente.

A área de aplicação para hiper-heurísticas é, portanto, a mesma que as meta-heurísticas. Sua aplicabilidade (em relação às metaheurísticas) é como uma 'ferramenta de prototipagem rápida': a motivação original era permitir que profissionais não especialistas aplicassem metaheurísticas ao seu problema específico de otimização (por exemplo, "Traveller-Salesman (TSP) mais janelas de tempo mais binários"). embalagem ") sem exigir experiência no domínio do problema altamente específico. A ideia era que isso pudesse ser feito por:

1. Permitir que os profissionais implementem apenas heurísticas muito simples (efetivamente, randomizadas) para transformar possíveis soluções. Por exemplo, para o TSP: "troque duas cidades aleatórias" em vez de (digamos) a heurística Lin-Kernighan mais complexa .
2. Obtenha resultados efetivos (apesar de usar essas heurísticas simples) combinando / sequenciando-os de maneira inteligente, geralmente empregando alguma forma de mecanismo de aprendizado.

As hiper-heurísticas podem ser descritas como 'seletivas' ou 'generativas', dependendo se as heurísticas são (respectivamente) sequenciadas ou combinadas. Portanto, as hiper-heurísticas generativas usam métodos como Programação Genética para combinar heurísticas primitivas e, portanto, são geralmente customizadas pelo profissional para resolver um problema específico. Por exemplo, o artigo original sobre hiper-heurísticas generativas usava um sistema classificador de aprendizado para combinar heurísticas para empacotar caixas. Como as abordagens generativas são específicas do problema, os comentários abaixo não se aplicam a elas.

Por outro lado, o motivador original para hiper-heurísticas seletivas era que os pesquisadores seriam capazes de criar um solucionador hiper-heurístico que provavelmente funcionaria bem em um domínio de problemas invisíveis, usando apenas heurísticas aleatórias simples.

A maneira como isso é tradicionalmente implementado é através da introdução da 'barreira do domínio hiper-heurístico' (veja a figura abaixo), segundo a qual se afirma que a generalidade entre os domínios do problema é alcançável, impedindo que o solucionador tenha conhecimento do domínio no qual está funcionando. Em vez disso, ele resolveria o problema operando apenas em índices inteiros opacos em uma lista de heurísticas disponíveis (por exemplo, da maneira do 'Problema do Bandido Multi-armado' ).

Na prática, essa abordagem de "domínio cego" não resultou em soluções de qualidade suficiente. Para alcançar resultados comparáveis ​​às metaheurísticas específicas de problemas, os pesquisadores hiper-heurísticos tiveram que implementar heurísticas complexas específicas de problemas, falhando no objetivo da prototipagem rápida.

Ainda é possível, em princípio, criar um solucionador hiper-heurístico seletivo que seja capaz de generalizar para novos domínios de problemas, mas isso foi dificultado, pois a noção acima de barreira de domínio significa que apenas um conjunto de recursos muito limitado está disponível para aprendizagem por domínio (por exemplo, como exemplificado por uma estrutura hiper-heurística seletiva popular ).

Uma perspectiva de pesquisa mais recente em relação às hiper-heurísticas da 'caixa branca' defende uma abordagem declarativa e rica em recursos para descrever domínios de problemas. Essa abordagem possui várias vantagens reivindicadas:

1. Os profissionais agora não precisam mais implementar heurísticas, mas simplesmente especificar o domínio do problema.
2. Elimina a barreira do domínio, colocando as hiper-heurísticas no mesmo status "informado" sobre o problema que as meta-heurísticas específicas do problema.
3. Com uma descrição do problema da caixa branca, o infame teorema 'Sem almoço grátis' (que afirma essencialmente que, considerado no espaço de todos os problemas da caixa preta , o recozimento simulado com um cronograma infinito de recozimento é, em média, tão bom quanto qualquer outra abordagem) se aplica mais.

AVISO LEGAL: Eu trabalho nesta área de pesquisa e, portanto, é impossível remover todos os preconceitos pessoais da resposta.