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.[1][2] 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.[3]
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 editar
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[4]
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 editar
- 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[5]
Ver também editar
Referências
- ↑ Balamurugan, R.; Natarajan, A. M.; Premalatha, K. (21 de abril de 2015). «Stellar-Mass Black Hole Optimization for Biclustering Microarray Gene Expression Data». Applied Artificial Intelligence (em inglês) (4): 353–381. ISSN 0883-9514. doi:10.1080/08839514.2015.1016391. Consultado em 22 de setembro de 2022
- ↑ Bianchi, Leonora; Dorigo, Marco; Gambardella, Luca Maria; Gutjahr, Walter J. (1 de junho de 2009). «A survey on metaheuristics for stochastic combinatorial optimization». Natural Computing (em inglês) (2): 239–287. ISSN 1572-9796. doi:10.1007/s11047-008-9098-4. Consultado em 22 de setembro de 2022
- ↑ Blum, C.; Roli, A. (2003). «Metaheuristics in combinatorial optimization: Overview and conceptual comparison». ACM Computing Surveys (em inglês). 35 (3): 268–308. Consultado em 22 de setembro de 2022
- ↑ «Lichtenberg Optimization Algorithm». www.mathworks.com (em inglês). Consultado em 24 de julho de 2020
- ↑ 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.
Bibliografia editar
- 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 editar
- «EU/ME». forum for researchers in the field.
- «MetaHeur - Aplicação em Excel para o estudo de Meta-Heurísticas»
