Hiper-heurística

Em ciência da computação e programação, uma hiper-heurística é um método de busca heurística que visa automatizar, muitas vezes, pela incorporação de técnicas de aprendizado de máquina, o processo de seleção, combinação, geração ou adaptação de várias heurística mais simples (ou os componentes de tais heurísticas) para resolver de forma eficiente problemas de pesquisa computacional. Uma das motivações para o estudo de hiper-heurística é construir sistemas que possam lidar com classes de problemas em vez de resolver apenas um problema.

Existem várias heurísticas a serem escolhidas para resolver um problema específico, e cada heurística tem seus pontos fortes e pontos fracos. A ideia é criar algoritmos de forma automática combinando os pontos fortes e compensando os pontos fracos de heurísticas já conhecidas. Em um típico framework de hiper-heurística existe uma metodologia de alto nível e um conjunto de heurísticas de baixo nível (heurísticas construtivas ou perturbativas). Dado um problema exemplo, o método de alto nível seleciona quais heurísticas de baixo nível deveriam ser aplicadas em um dado momento, dependendo do estado atual do problema ou fase da busca.

Hiper-heurística versus meta-heurística

A fundamental diferença entre meta-heurística e hiper-heurísticas é que a maioria das implementações de meta-heurísticas realizam busca dentro do espaço de busca de soluções de problemas, enquanto hiper-heurísticas sempre buscam dentro do espaço de busca de heurísticas em uma situação específica ao invés de tentar resolver o problema diretamente. Além disso, é realizada uma busca por uma metodologia de aplicação geral em vez de resolver uma única instância do problema.

A hiper-heurística pretende ser um método genérico, que deve produzir soluções de qualidade aceitável, com base em um conjunto de heurísticas de baixo nível fáceis de implementar.

Motivação

Apesar do progresso significativo na construção de metodologias de pesquisa para uma ampla variedade de áreas de aplicação, até agora, essas abordagens ainda necessitam de especialistas para integrar seus conhecimentos em um determinado domínio de problema. Muitos pesquisadores de ciência da computação, inteligência artificial e pesquisa operacional, já reconheceram a necessidade de desenvolvimento de sistemas automatizados para substituir o papel de um humano especialista em tais situações. Uma das principais ideias para automatizar o o desenvolvimento de uma heurística requer a utilização de técnicas de aprendizado de máquina em algoritmos para auxiliar a busca de forma adaptativa. Aprendizagem e processos de adaptação podem ser realizados on-line ou off-line, e baseiam-se em heurísticas construtivas ou perturbativas.

A hiper-heurística geralmente visa reduzir a quantidade de conhecimento de domínio na metodologia de pesquisa. A abordagem escolhida pela hiper-heurística deve ter baixo custo computacional e ter execução rápida, exigindo menos conhecimento tanto do domínio do problema ou dos métodos heurísticos. O objetivo é elevar o nível de generalidade da metodologia de apoio à decisão, talvez à custa da redução, mas ainda aceitável, da qualidade da solução quando comparado com abordagens meta-heurísticas.

Origens

O termo "hiper-heurística" foi citado pela primeira vez em uma publicação de Cowling e Soubeiga em 2000, usado para descrever a ideia de "heurísticas para escolher heurísticas". Eles utilizaram uma abordagem de aprendizado de máquina chamada de "choice selection" na escolha da próxima heurística a ser utilizada na solução de um determinado problema. Cowling, Soubeiga, Kendall, Han, Ross, entre outros autores através de novas pesquisas estenderam a ideia em novas áreas como algoritmos evolutivos por exemplo. O primeiro artigo em uma revista científica a usar o termo surgiu em 2003. A origem da ideia (embora não do termo) surge no início dos anos 60. e foi redescoberta e estendida várias vezes durante os anos 90. O trabalho sobre Escalonamento de Processos realizado por Fisher e Thompson provou de forma experimental, usando aprendizado probabilístico, que a combinação de regras de escalonamento foi superior do que qualquer uma das regras separadamente. Embora o termo não existia até o momento, este foi o primeiro artigo sobre "hiper-heurística". Outra ideia que também inspirou o conceito de hiper-heurísticas vem do campo da inteligência artificial. Mais especificamente, se trata do trabalho sobre planejamento automatizado de sistemas, e seu foco para o problema de conhecimento da aprendizagem de controle. O sistema chamado COMPOSER, desenvolvido por Gratch, foi utilizado para controlar horários de comunicação por satélite, envolvendo uma série de satélites em órbita e três estações terrestres. O sistema pode ser caracterizado como uma busca do tipo hill-climbing no espaço de possíveis estratégias de controle.

Classificações e abordagens

As abordagens de hiper-heurística até o momento podem ser classificadas em duas categorias principais. A primeira, baseada na frase heurísticas para escolher heurísticas, o framework da hiper-heurística é se utiliza de um conjunto preexistente de heurísticas geralmente amplamente conhecidos para resolver o problema. A tarefa é descobrir uma boa sequência de aplicação destas heurísticas para resolver o problema de forma eficaz. A segunda, heurísticas para gerar heurísticas, a ideia é "desenvolver novas heurísticas, fazendo uso dos componentes de heurísticas conhecidas." O processo requer, como na primeira categoria de hiper-heurísticas, a seleção de um conjunto adequado de heurísticas conhecidas para ser útilizado na resolução do problema. No entanto, ao invés de fornecer estes diretamente para o framework, as heurísticas são primeiro decompostas em seus componentes básicos.

Estes dois tipos principais podem ainda ser baseados em pesquisa construtiva ou perturbativa. Uma classificação ortogonal adicional de hiper-heurísticas considera a fonte que fornece feedback durante o processo de aprendizagem, que pode ser tanto uma instância (aprendizagem on-line ) ou muitas instâncias do problema subjacente estudado ( aprendizagem off-line ).

Metodologias para escolher heurísticas

Descobre boas combinações de, heurística conhecidas de baixo nível.

• Com base em heurísticas construtivas
• Com base em heurísticas perturbativas

Metodologias para gerar heurísticas

Gera novos métodos heurísticos que utilizam componentes básicos de métodos heurísticos previamente existentes.

• Com base em componentes básicos de heurísticas construtivas
• Com base em componentes básicos de heurísticas perturbativas

Hiper-heurísticas de aprendizagem on-line

A aprendizagem ocorre enquanto o algoritmo está resolvendo uma instância de um problema, portanto, propriedades locais dependentes de tarefas podem ser usadas pela estratégia de alto nível para determinar a heurística de baixo nível mais adequada. Os exemplos de abordagens de aprendizagem on-line dentro de hiper-heurísticas são: o uso de aprendizagem por reforço para a seleção heurística, e geralmente o uso de meta-heurísticas como estratégias de pesquisa de alto nível ao longo de um espaço de busca de heurísticas.

Hiper-heurísticas de aprendizagem off-line

A ideia é acumular o conhecimento na forma de regras ou programas que, a partir de um conjunto de instâncias, que poderia vir a generalizar para o processo de resolução de casos não vistos até o momento. Os exemplos de abordagens de aprendizagem off-line dentro de hiper-heurísticas são: learning classifier system, raciocínio baseado em casos e programação genética.

Aplicações

Hiper-heurísticas têm sido aplicadas em diversos tipos de problemas. Uma das principais motivações de hiper-heurísticas é ser capaz de operar em diferentes tipos de problemas. A lista a seguir é uma seleção não exaustiva de alguns dos problemas e campos em que hiper-heurísticas foram exploradas:

• Problema do Empacotamento
• Problema de Satisfazibilidade Booleana
• Problema de Escalonamento de Enfermeiras
• Problema do Caixeiro Viajante
• Problema de Roteamento de Veículos
• Problema do Quadro de Horários
• Problema de Escalonamento de Processos

Áreas relacionadas

Hiper-heurística não é a única abordagem a ser investigado na busca de metodologias de pesquisa mais gerais e aplicáveis. Muitos pesquisadores de ciência da computação, inteligência artificial e pesquisa operacional já reconheceram a necessidade de desenvolver sistemas automatizados para substituir o papel de um especialista humano no processo de ajuste e adaptação de metodologias de busca. A lista a seguir descreve algumas áreas de pesquisa relacionadas:

• adaptation and self-adaptation of algorithm parameters
• adaptive memetic algorithm
• adaptive large neighborhood search
• algorithm configuration
• algorithm control
• algorithm portfolios
• autonomous search
• genetic programming
• indirect encodings in evolutionary algorithms
• variable neighborhood search
• reactive search

Ver também

• Heurística construtiva
• Meta-otimização está intimamente relacionado com a hiper-heurística.
• Algoritmos genéticos
• Programação genética
• Algoritmos evolutivos
• Pesquisa local (otimização)
• Aprendizado de máquina
• Meta-heuristica
• Otimização de enxame de partículas

Ligações externas

Bibliografia

• http://goo.gl/Rczo2N
• http://www.cs.nott.ac.uk/~gxo/hhbibliography.html

Grupos de pesquisa

• Artificial Intelligence (ART+I) Laboratory, Yeditepe University, Turkey
• Automated Scheduling, Optimisation and Planning (ASAP) Research Group, University of Nottingham, UK
• Combinatorial Optimisation and Decision Support (CODeS) Research Group, KU Leuven - KAHO Sint-Lieven, Belgium
• Computational-Heuristics, Operations Research and Decision-Support (CHORDS) Research Group, University of Stirling, UK
• Intelligent Systems Lab, Heriot-Watt University, UK
• Modelling Optimisation Scheduling and Intelligent Control (MOSAIC) Research Group, University of Bradford, UK
• Optimising Software by Computation from ARtificial intelligence (OSCAR) Research Group, Dalian University of Technology, P.R.China

Atividades recentes

• The 1st AISB Symposium on Meta-Optimisation: Hyper-heuristics and Beyond @ AISB Convention 2013
• Modern Hyperheuristics for Large Scale Optimization Problems @ META2012
• Tutorial on Hyper-heuristics and Cross-domain Optimization @ GECCO2012
• Self-* Search Track @ GECCO2012
• Special Session on Evolutionary Based Hyperheuristics and Their Applications @ IEEE CEC2012 (WCCI2012)
• Special Session on Cross-domain Heuristic Search (LION-CHESC) @ LION2012
• Cross-domain Heuristic Search Challenge 2011 (CHeSC 2011)
• Special Session on Systems to Build Systems @ MISTA2011
• Tutorial on Automated Heuristic Design @ GECCO2011
• Special Session on Hybrid Evolutionary Algorithms, Hyper-heuristics and Memetic Computation @ IEEE CEC2010 (WCCI2010)
• Workshop on Self-tuning, self-configuring and self-generating search heuristics (Self* 2010) @ PPSN2010
• Workshop on Hyper-heuristics, to be held in conjunction with PPSN X, 10th International Conference on Parallel Problem Solving From Nature, Dortmund, Germany

Outros

• Task Force on Hyper-heuristics in the Technical Committee of Intelligent Systems and Applications at the IEEE Computational Intelligence Society.