Abordagens adaptativas de metaheuristicas tabu
AUTOR(ES)
Vitoria Pureza
DATA DE PUBLICAÇÃO
1996
RESUMO
A Busca Tabu é um procedimento heurístico de orientação da busca com vistas à obtenção de boas soluções em problemas de dificil tratamento. Fundamentalmente, ela é caracterizada por mecanismos que promovem a superação da otimalidade local. Esses mecanismos geralmente tomam a forma de parâmetros que impõem restrições à seleção de movimentos. Como a calibragem desses elementos restritivos tem um impacto fundamental no desempenho do algoritmo, algumas implementações utilizam estratégias que provocam alterações sistemáticas nos valores de determinados parâmetros. Estas estratégias procuram intensificar a exploração de regiões promissoras e o abandono de regiões onde possibilidades de melhoria parecem mínimas. As alterações nos valores dos parâmetros são normalmente acionadas por fases de busca caracterizadas pela ausência de movimentos de atualização da solução incumbente. O objetivo principal deste trabalho é o de propor uma nova abordagem adaptativa de metaheurísticas Tabu. A abordagem HTA, aqui considerada, propõe que a alteração de parâmetros seja determinada a partir da identificação de padrões da trajetória de busca recentemente traçada. Estes padrões fornecem indicações, ainda que limitadas, acerca da topologia do espaço de soluções. Para cada padrão, são aplicadas perturbações nos valores de parâmetros tabu selecionados, como forma de adaptar a busca às diferentes condições encontradas. A abordagem HTA foi desenvolvida a partir de extensos experimentos com o Problema do Caixeiro Viajante Simétrico e Euclideano (PCV). Testes envolveram 12 instâncias clássicas e verificaram ganhos significativos em relação à versão não-adaptativa, mesmo sob condições operacionais estressantes impostas por parâmetros mantidos fora de controle. A seguir, a mesma abordagem foi aplicada ao Problema de Roteamento de Veículos (PRV). Neste trabalho, apresentamos os resultados obtidos com 14 instâncias clássicas caracterizadas por diferentes restrições. Os resultados foram comparados com os de três algoritmos altamente competitivos e indicaram que HTA produz soluções de qualidade comparável aos demais. São também apresentados os resultados obtidos com uma implementação adaptativa HTA para o Problema de Agrupamento Capacitado (PAC). Os resultados, mais uma vez, sugerem que a introdução de mecanismos adaptativos baseados em padrões da trajetória da busca é uma estratégia robusta e promissora
ASSUNTO(S)
heuristica problema do caixeiro viajante otimização combinatoria
