Wikipédia

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.[1][2][3]

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.[4] 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.[2]

Hiper-heurística versus meta-heurística editar

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 editar

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.[5]

Origens editar

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".[6] 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.[7] 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.[8] A origem da ideia (embora não do termo) surge no início dos anos 60.[9][10] e foi redescoberta e estendida várias vezes durante os anos 90.[11][12][13] O trabalho sobre Escalonamento de Processos realizado por Fisher e Thompson[9][10] 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,[14][15] 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 editar

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." [16] 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 editar

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 editar

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 editar

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 editar

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 editar

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:

Áreas relacionadas editar

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:

Referências

  1. ↑ E. K. Burke, E. Hart, G. Kendall, J. Newall, P. Ross, and S. Schulenburg, Hyper-heuristics: An emerging direction in modern search technology, Handbook of Metaheuristics (F. Glover and G. Kochenberger, eds.
  2. ↑ a b P. Ross, Hyper-heuristics, Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques (E. K. Burke and G. Kendall, eds.
  3. ↑ E. Ozcan, B. Bilgin, E. E. Korkmaz, A Comprehensive Analysis of Hyper-heuristics, Intelligent Data Analysis, 12:1, pp. 3-23, 2008.
  4. ↑ E. Ozcan, B. Bilgin, E. E. Korkmaz, Hill Climbers and Mutational Heuristics in Hyperheuristics, Lecture Notes in Computer Science, Springer-Verlag, The 9th International Conference on Parallel Problem Solving From Nature, 2006, pp. 202-211.
  5. ↑ Burke E.K., Landa Silva J.D., Soubeiga E.: Multi-objective Hyper-heuristic Approaches for Space Allocation and Timetabling, In Meta-heuristics: Progress as Real Problem Solvers, Selected Papers from the 5th Metaheuristics International Conference (MIC 2003), pp 129-158, 2005.
  6. ↑ Cowling P. and Soubeiga E. Neighborhood Structures for Personnel Scheduling: A Summit Meeting Scheduling Problem (abstract), in proceedings of the 3rd International Conference on the Practice and Theory of Automated Timetabling, Burke E.K. and Erben W. (eds), 16-18 Aug 2000, Constance, Germany
  7. ↑ Cowling P., Kendall G. and Soubeiga E., A Hyperheuristic Approach to Scheduling a Sales Summit, 2001, Lecture Notes in Computer Science 2079, Springer-Verlag, pp. 176–190, 2001, ISBN 3540424210, (doi:10.1007/3-540-44629-X
  8. ↑ Burke E. K., Kendall G., and Soubeiga E. (2003) A Tabu-Search Hyper-Heuristic for Timetabling and Rostering. Journal of Heuristics, 9(6):451-470. (doi:10.1023/B:HEUR.0000012446.94732.b6 [1])
  9. ↑ a b H. Fisher and G. L. Thompson, Probabilistic learning combinations of local job-shop scheduling rules, Factory Scheduling Conference (Carnegie Institute of Technology), 1961.
  10. ↑ a b * H. Fisher and G. L. Thompson, Probabilistic learning combinations of local job-shop scheduling rules,Industrial Scheduling (New Jersey) (J. F. Muth and G. L. Thompson, eds.), Prentice-Hall, Inc, 1963, pp. 225–251.
  11. ↑ R. H. Storer, S. D. Wu, and R. Vaccari, New search spaces for sequencing problems with application to job shop scheduling, Management Science, 38 (10), 1992, 1495–1509.
  12. ↑ H. L. Fang, P. Ross, and D. Corne, A promising genetic algorithm approach to job shop scheduling, rescheduling, and open-shop scheduling problems, Fifth International Conference on Genetic Algorithms (San Mateo) (S. Forrest, ed.), Morgan Kaufmann, 1993, pp. 375–382.
  13. ↑ U. Dorndorf and E. Pesch, Evolution based learning in a job shop scheduling environment, Computers and Operations Research, 22(1), 1995, 25–40.
  14. ↑ J. Gratch, S. Chien, e G. DeJong, Learning search control knowledge for deep space network scheduling, Proceedings of the Tenth International Conference on Machine Learning (Amherst, MA), 1993, pp. 135–142.
  15. ↑ J. Gratch and S. Chien, Adaptive problem-solving for large-scale scheduling problems: a case study, Journal of Artificial Intelligence Research, 4, 1996, 365–396.
  16. ↑ M. Bader-El-Den and R. Poli, Generating sat local-search heuristics using a GP hyper-heuristic framework, Artificial Evolution, 8th International Conference, Evolution Artificielle, EA 2007, Tours, France, October 29–31, 2007, Revised Selected Papers. Lecture Notes in Computer Science 4926 Springer, 2008, pp. 37-49.

Ver também editar

Referências e notas editar

Ligações externas editar

Bibliografia editar

Grupos de pesquisa editar

Atividades recentes editar

Outros editar

Obtida de "https://pt.wikipedia.org/w/index.php?title=Hiper-heurística&oldid=67191425"