Use este identificador para citar ou linkar para este item: http://www.monografias.ufop.br/handle/35400000/3719
Título: Operador adaptativo de memória para metaheurísticas de busca local.
Autor(es): Toledo, Paula Franca
Orientador(es): Coelho, Dayanne Gouveia
Membros da banca: Ribeiro, Rodrigo Geraldo
Silva, Pedro Henrique Lopes
Palavras-chave: Metaheurística de busca local
Operadores adaptativos
Estratégias de memória
Data do documento: 2021
Referência: TOLEDO, Paula Franca. Operador adaptativo de memória para metaheurísticas de busca local. 2021. 59 f. Monografia (Graduação em Ciência da Computação), - Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto, Ouro Preto, 2021.
Resumo: 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.
Resumo em outra língua: This work aims to study and propose an adaptive neighborhood operator based on the memory idea for local search metaheuristics, in order to apply this technique developed to solve combinatorial optimization problems. The main idea of this operator is to use the memory structure to avoid revisiting solutions and direct the algorithm, based on the stored information, to carry out a more adequate exploration of the search space. The described operator will be tested in the Simulated Annealing heuristic and the \textit{Variable Neighborhood Search} (VNS) metaheuristic. To investigate the efficiency of the methodology, the Problem of Scheduling Tasks with a Common Delivery Date in a Single Machine and the Traveling Salesman Problem were used. In Task Scheduling Problem with Common Due Date VNS-Oadp got better solutions for eight instances while VNS-MH had better solutions for seven instances. For the Traveling Salesman problem, VNS-Oadp obtained better results for ten instances and VNS-MH for only five instances. Overall, the proposed operator improved the quality of the solutions obtained when compared to the classic version of VNS. Regarding the \textit{Simulated Annealing} variations, the best version indicated by the tests for the Task Scheduling with Delivery Date problem in common was SA-Oadp, which presented seven better solutions when compared to SA-MH and proved to be better than the classic SA in ten problems. For the traveling salesman problem, the best version indicated by the tests was the SA-Oadp, which obtained seven better solutions than the other two methods. In the tests performed, the proposed method showed a more efficient behavior than the original versions of the algorithms, since it was possible to obtain better average solutions for some instances of the test problem with a relatively short computational time. However, it is worth noting that it is still necessary to carry out more elaborate statistical experimentation to better understand the results achieved and invest in a more efficient and significant improvement of the proposed operator.
URI: http://www.monografias.ufop.br/handle/35400000/3719
Aparece nas coleções:Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
MONOGRAFIA_OperadorAdaptativoMemória.pdf628,74 kBAdobe PDFVisualizar/Abrir


Este item está licenciado sob uma Licença Creative Commons Creative Commons