Show simple item record

dc.contributor.advisorRitt, Marcus Rolf Peterpt_BR
dc.contributor.authorZubaran, Tadeu Knewitzpt_BR
dc.date.accessioned2013-04-10T01:42:11Zpt_BR
dc.date.issued2013pt_BR
dc.identifier.urihttp://hdl.handle.net/10183/70140pt_BR
dc.description.abstractNeste 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.pt_BR
dc.description.abstractIn 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.en
dc.format.mimetypeapplication/pdf
dc.language.isoengpt_BR
dc.rightsOpen Accessen
dc.subjectCombinatorial optimizationen
dc.subjectInteligência artificialpt_BR
dc.subjectAlgorítmopt_BR
dc.subjectHeuristicsen
dc.subjectUFRGSen
dc.subjectOtimizacao combinatoriapt_BR
dc.subjectGo with the winnersen
dc.titleMulti-point search for combinatorial optimization problemspt_BR
dc.title.alternativeBusca multi-ponto para problemas de otimização combinatória pt_BR
dc.typeTrabalho de conclusão de graduaçãopt_BR
dc.identifier.nrb000876242pt_BR
dc.degree.grantorUniversidade Federal do Rio Grande do Sulpt_BR
dc.degree.departmentInstituto de Informáticapt_BR
dc.degree.localPorto Alegre, BR-RSpt_BR
dc.degree.date2013pt_BR
dc.degree.graduationCiência da Computação: Ênfase em Ciência da Computação: Bachareladopt_BR
dc.degree.levelgraduaçãopt_BR


Files in this item

Thumbnail
   

This item is licensed under a Creative Commons License

Show simple item record