Uma Breve Introdução à Meta-Heurísticas e suas Principais Técnicas



Resumo — Com o avanço da capacidade do hardware no mundo tecnológico, é fácil pensar que quaisquer tipos de problemas poderão ser solucionados por um computador, porém isto não é verdade. A classe dos problemas NP-Completo contém problemas que não possuem solução em tempo polinomial, porém para certas instâncias do problema é possível se criar um método heurístico que apresenta uma solução ótima em tempo hábil. A dificuldade de se trabalhar com o método heurístico vem do fato que a modelagem do método, que já é um trabalho árduo, é particular de cada problema. Devido a esta dificuldade a meta-heurística recebeu grande atenção, pois ela visa criar um método heurístico para resolver de forma genérica os problemas de otimização. Neste trabalho são estudadas as principais técnicas de meta-heurísticas afim de entender melhor o seu funcionamento e apresentar algumas aplicações práticas conhecidas em que elas são utilizadas.
I. INTrodução
Atualmente, com o rápido desenvolvimento da tecnologia no mundo principalmente no que se diz a respeito da capacidade do hardware, é fácil acreditar que qualquer problema pode ser solucionado em tempo hábil através de um computador. Porém, isto não é verdade. Existe uma classe de problemas que não podem ser solucionados em tempo polinomial por nenhuma máquina do mundo. Esta classe de problemas é chamada de NP-Completo.
Os problemas NP-Completos são caracterizados por não possuírem solução definitiva em tempo polinomial, ou seja, o algoritmo de resolução pode até encontrar uma solução, porém este tomará um tempo inviável do uso de uma máquina. Neste caso, é possível criar uma heurística que será capaz de solucionar tal problema para pequenas instâncias. A ideia de uma heurística é sempre tentar apresentar uma solução ótima para determinada instância de um problema. Para se apresentar uma solução ótima, era necessário criar uma heurística própria para cada problema específico. O que era bastante cansativo, visto que tudo o que