Meta-heurística
Origem: Wikipédia, a enciclopédia livre.
Uma meta-heurística é um método heurístico para resolver de forma genérica problemas de otimização (normalmente da área de otimização combinatória).
Metaheurísticas são geralmente aplicadas a problemas que não se conhece algoritmo eficiente (veja 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.
Índice |
Meta-heurísticas comuns [editar]
Algumas meta-heurísticas bem conhecidas são:
- Algoritmo genético
- Simulated annealing (Arrefecimento Simulado em pt-Br)
- GRASP
- Busca tabu
- Colônia de formigas (otimização)
- Colônia de abelhas (otimização)
Inumeráveis variações e combinações destas técnicas são propostas na literatura (veja sistemas híbridos).
Problemas resolvidos por metaheurísticas [editar]
- Problema de Roteamento de Veículos
- Problema de satisfatibilidade booleana (SAT)
- Problema da mochila
- Problema do ciclo hamiltoniano
- Problema do caixeiro viajante
- Problema da clique
- Problema de conjuntos independentes
- Otimização em engenharia de software1
Referências [editar]
- C. Blum and A. Roli (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys 35(3) 268–308.
Referências
- ↑ FREITAS, 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.
Ligações externas [editar]
- EU/ME forum for researchers in the field.
- MetaHeur - Aplicação em Excel para o estudo de Meta-Heurísticas
