O que são hiper-heurísticas?

10

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?

bmwalide
fonte
4
Acho que essa pergunta pode ser realmente interessante se você compartilhar sua pesquisa (por exemplo, links para coisas interessantes que você encontrou até agora). Depois de vermos um pouco da sua pergunta, podemos fornecer uma resposta melhor para você.
Ben N

Respostas:

8

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' ).

Noção tradicional de Hiper-heurística Seletiva

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.

NietzscheanAI
fonte