Repositório Digital

A- A A+

Multi-point search for combinatorial optimization problems

.

Multi-point search for combinatorial optimization problems

Mostrar registro completo

Estatísticas

Título Multi-point search for combinatorial optimization problems
Outro título Busca multi-ponto para problemas de otimização combinatória
Autor Zubaran, Tadeu Knewitz
Orientador Ritt, Marcus Rolf Peter
Data 2013
Nível Graduação
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Curso de Ciência da Computação: Ênfase em Ciência da Computação: Bacharelado.
Assunto Algorítmo
Inteligência artificial
Otimizacao combinatoria
[en] Combinatorial optimization
[en] Go with the winners
[en] Heuristics
[en] UFRGS
Resumo Neste trabalho propomos e testamos maneiras de aplicar os princípios por traz do go with the winners, em problemas de otimização combinatória. Go with the winners foi proposto como um algorítimo para mover partículas em árvores abstratas, e é comprado com um algorítimo, simple restart, onde diversas partículas são soltas na raiz da árvore e deixadas à descender sem interagirem umas com as outras. O técnica go with the winners permite que as partículas utilizem informação das outras de forma a aumentar a chance delas chegarem em níveis mais baixos da árvore. Nós desenvolvemos um algorítimo que utiliza as idéias chave do go with the winners para três problemas distintos. Primeiramente desenvolvemos um problema artificial para testes preliminares do algorítimo para verificarmos como as previsões teóricas são traduzidas para um ponto intermediário entre um verdadeiro problema de otimização e o framework abstrato. Nós então implementamos e testamos o go with the winners no clássico problema de otimização do caixeiro viajante e por último no moderno machine reassignment. Para cada uma de nossas implementações nós fazemos uma bateria completa de testes e comparamos com a performance contra o simple restart e as meta-heurísticas comumente utilizadas GRASP e simulated annealing.
Abstract In this work we propose and test ways to apply the principles of go with the winners in combinatorial optimization problems. Go with the winners was proposed as an algorithm to move particles in abstract trees, and is compared with an algorithm, the simple restart, where several particles are released at the root of the tree and let to descend the tree without interacting with one another. The go with the winners approach lets particles use information from other particles in order to increase the chance that they will reach deeper levels of the tree. We develop an algorithm that use the core ideas of the go with the winners in three distinct problems. First we define an artificial optimization problem to test a preliminary algorithm and see how the theoretical predictions are translated in a mid point between an actual optimization problem and the abstract framework. We proceed, then, to implement and test the go with the winners in a classic optimization problem, the travelling salesperson problem, and finally in the modern problem machine reassignment. For each of our implementations we perform a comprehensive set of benchmark tests and compare the performance against the simple restart and the commonly used metaheuristics GRASP and simulated annealing.
Tipo Trabalho de conclusão de graduação
URI http://hdl.handle.net/10183/70140
Arquivos Descrição Formato
000876242.pdf (619.4Kb) Texto completo (inglês) Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.