Em ciência da computação e otimização combinatória, uma meta-heurística é um procedimento de alto nível ou heurística projetada para encontrar, gerar ou selecionar uma heurística (algoritmo de busca parcial) que pode fornecer uma solução suficientemente boa para um problema de otimização, especialmente com informações incompletas ou imperfeitas ou capacidade de computação limitada. Meta-heurística toma uma amostra de um subconjunto de soluções que, de outra forma, é muito grande para ser completamente enumerado ou explorado de outra forma. A meta-heurística pode fazer relativamente poucas suposições sobre o problema de otimização que está sendo resolvido e, portanto, pode ser usada para uma variedade de problemas.
Meta-heurísticas são geralmente aplicadas a problemas para os quais não se conhece algoritmo eficiente (como os problemas NP-completos).
Utilizam combinação de escolhas aleatórias e conhecimento histórico dos resultados anteriores adquiridos pelo método para se guiarem e realizar suas buscas pelo espaço de pesquisa em vizinhanças dentro do espaço de pesquisa, o que evita paradas prematuras em ótimos locais.
Meta-heurísticas comuns Algumas meta-heurísticas bem conhecidas são:
Algoritmo genético Simulated annealing (ou Recozimento simulado) GRASP Busca tabu Colônia de formigas (otimização) Colônia de abelhas (otimização) Lichtenberg Algorithm
Inumeráveis variações e combinações destas técnicas são propostas na literatura (veja sistemas híbridos).
Problemas resolvidos por meta-heurísticas Problema de Roteamento de Veículos Problema de satisfatibilidade booleana (SAT) Problema da mochila Problema do ciclo hamiltoniano Problema do caixeiro viajante Problema de coloração de grafos Problema da clique Problema de conjuntos independentes PeSOA: Penguins Search Optimization Algorithm Otimização em engenharia de softwareFREITAS, F.G., MAIA, C.L.B., COUTINHO, D.P., CAMPOS, G.A.L., SOUZA, J.T., Aplicação de Metaheurísticas em Problemas da Engenharia de Software: Revisão de Literatura, II Congresso Tecnológico Infobrasil, 2009, http://issuu.com/fabriciogf/docs/otimizacaoemengenhariadesoftware_surveypt.
Ver também Otimização Combinatória
Bibliografia C. Blum and A. Roli (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys 35(3) 268–308. Goldbarg, Marco; Luna, Henrique. Otimização Combinatória e Metaheurísticas: Algoritmos e Apliacações. Elsevier, 2017. Talbi,El-Ghazali. Metaheuristics: From Design to Implementation. John Wiley & Sons,2009.
Ligações externas
Definição: O que são Meta-Heurísticas
Categoria:Otimização Categoria:Pesquisa operacional