Meta-heurística
# Meta-heurística

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 software