Operador adaptativo de memória para metaheurísticas de busca local.

Abstract

Este trabalho tem por objetivo estudar e propor um operador de vizinhança adaptativo baseado na ideia de memória para metaheurísticas de busca local, com o intuito de aplicar esta técnica desenvolvida na resolução de problemas de otimização combinatória. A ideia principal deste operador é usar a estrutura de memória para evitar revisitações de soluções e direcionar o algoritmo, com base nas informações armazenadas, na realização de uma exploração mais adequada do espaço de busca. O operador descrito será testado na heurística \textit{Simulated Annealing} e na metaheurística \textit{Variable Neighbourhood Search} (VNS). Para investigar a eficiência da metodologia, utilizou-se o Problema de Agendamento de Tarefas com Data de Entrega Comum em uma Única Máquina e o Problema do Caixeiro Viajante. No Problema de Agendamento de Tarefas com Data de Entrega em Comum o VNS-Oadp obteve soluções melhores para a oito instâncias enquanto o VNS-MH apresentou soluções melhores para sete instâncias. Para o problema do Caixeiro Viajante o VNS-Oadp obteve resultados melhores para dez instâncias e o VNS-MH para apenas cinco instâncias. No geral, o operador proposto, melhorou a qualidade das soluções obtidas quando comparados a versão clássica do VNS. Em relação as variações do \textit{Simulated Annealing}, a melhor versão indicada pelos testes para o problema Agendamento de Tarefas com Data de Entrega em Comum foi a SA-Oadp que apresentou sete soluções melhores quando comparado ao SA-MH e se mostrou melhor que o SA clássico em dez problemas. Para o problema do Caixeiro Viajante, a melhor versão indicada pelos testes foi o SA-Oadp que obteve sete soluções melhores que os outros dois métodos. Nos testes realizados, o método proposto se mostrou com um comportamento mais eficiente que as versões originais dos algoritmos, uma vez que foi possível obter melhores soluções médias para algumas instâncias do problema teste com um tempo computacional relativamente curto. Porém, vale destacar que é ainda é necessário fazer uma experimentação estatística mais elaborada para compreender melhor os resultados alcançados e investir numa melhoria mais eficiente e significativa do operador proposto.