Thesis (Ph.D.(Computer Science))--University of Pretoria, 2009. / Abstract in English. Includes bibliographical references.

In the last decades there has been a lot of interest in computational models and metaheuristics algorithms capable to solve combinatorial optimization problems. The recent trend is to define these algorithms taking inspiration by the observation of natural systems. In this thesis the Ant Colony System (ACS) is presented which has been inspired by the observation of real ant colonies. ACS is initially proposed to solve the symmetric and asymmetric travelling salesman problems where it is shown to be competitive with other metaheuristics. Although this is an interesting and promising result, it was immediately clear that ACS, as well as other metaheuristics, in many cases cannot compete with specialized local search methods. An interesting trend is therefore to couple metaheuristics with a local optimizer, giving birth to so-called hybrid methods. Along this line, the thesis investigates MACS-VRPTW (Multiple ACS for the Vehicle Routing Problem with Time Windows) and HAS-SOP: Hybrid Ant System for the Sequential Ordering Problem (SOP). In the second part the thesis introduces some modifications of the original ACS algorithm. These modifications are able to speed up the method and to make it more competitive in case of large problem instances. The resulting framework, called Enhanced Ant Colony System is tested for the SOP. Finally the thesis presents the application of ACS to solve real-life vehicle routing problems where additional constraints and stochastic information are included. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

Orientador: Akebo Yamakami / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-08T23:52:00Z (GMT). No. of bitstreams: 1 Carvalho_MarciaBragade_M.pdf: 2154346 bytes, checksum: caafd847980349294a73d2ad38d6414c (MD5) Previous issue date: 2007 / Resumo: Dentre as várias técnicas heurísticas e exatas existentes para a resolução de problemas combinatórios, os algoritmos populacionais de otimização por colônia de formigas e genéticos têm se destacado devido à sua boa performance. Em especial os algoritmos de colônia de formigas são considerados atualmente como uma das técnicas mais bem sucedidas para a resolução de vários problemas combinatórios, dentre eles o problema do caixeiro viajante. Neste trabalho é apresentado um algoritmo híbrido que trabalha com as meta-heurísticas de sistema de colônia de formigas e genético conjuntamente aplicados no problema do caixeiro viajante simétrico. Além disso, apresentamos uma proposta para o algoritmo de formigas quando temos incertezas associadas aos parâmetros do problema. Os resultados obtidos com as metodologias propostas apresentam resultados satisfatórios para todas as instâncias utilizadas / Abstract: Amongst the several existing heuristical and accurate techniques for the resolution of combinatorial problems, the population algorithms ant colony optimization and genetic have been detached due to their good performance. In special the ant colony algorithms are considered currently as one of the techniques most succeeded for the resolution of some combinatorial problems, amongst them the travelling salesman problem. In this work is presented a hybrid algorithm which works with the ant colony system and genetic metaheuristics jointly applied in the symmetric travelling salesman problem. Moreover, we presented a proposal for the ant algorithm when we have uncertainties associated to problem parameters. The results gotten with the methodology proposals present resulted satisfactory for all the used instances / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientador: Neucimar Jeronimo Leite / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-11T00:51:01Z (GMT). No. of bitstreams: 1 Souza_RafaelHenriqueCastanheirade_M.pdf: 1199945 bytes, checksum: 9b1286893d0b1751f7fce2dd2117cdbb (MD5) Previous issue date: 2008 / Resumo: O rastreamento automático de animais permite um estudo comportamental mais consistente e rápido do que o feito normalmente utilizando-se registro manual dos parâmetros de experimentos em biologia. O registro automático é realizado por um sistema analisador de imagens que, a partir de uma sequência contínua de quadros de um vídeo, calcula uma série de descritores associados ao movimento das cobaias. O objetivo deste trabalho é criar um sistema de rastreamento para experimentos de laboratório, levando em conta múltiplas cobaias que podem vir a sofrer oclusão. Além disso, pretende-se que o modelo de rastreamento proposto seja robusto a baixa qualidade do vídeo, além de ser geral o suficiente para ser adaptado a outros experimentos com poucas modificações / Abstract: The automatic tracking of animals allows a quicker and more consistent analysis of behaviour than the usual manual method for registering experimental parameters in biology. The automatic register of parameters is performed by a system that analyses a sequence of images and computes a number of descriptors that characterizes the behaviour of each target. Our objective is to create a framework for tracking in biology experiments, with multiple targets that may suffer occlusion. Besides, we intend to create a framework that can deal with low-quality videos and capable of being adapted to other classes of tracking / Mestrado / Processamento de Imagens / Mestre em Ciência da Computação

Orientadores: Antonio Carlos Moretti, Luis Leduino de Salles Neto / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-15T18:13:59Z (GMT). No. of bitstreams: 1 Marciniuk_FernandaLedo_M.pdf: 1221484 bytes, checksum: b1408936331c027b4c3cc1129bc0105a (MD5) Previous issue date: 2010 / Resumo: O problema de corte de estoque ordenado, um problema relativamente novo na literatura, e uma adaptação do problema de corte de estoque tradicional onde algumas restrições quanto a limitação do numero de ordens de produção em processamento são adicionadas. Esta dissertação tem como objetivo estudar uma nova abordagem deste problema utilizando uma aplicação da metaheurística colônia de formigas. Esta metaheurística utiliza os princípios de auto-organização de uma população de formigas visando a resolução de problemas de otimização combinatorial / Abstract: The Ordered Cutting Stock Problem (OCSP), a relatively recent problem in technical literarture, is a variant of the more well-known Cutting Stock Problem (CSP). This variant includes some new constraints in the mathematical formulation, regarding the number of production orders being processed simultaneously. This work studies a new approach to solve the OCSP, applying the Ant Colony Optimization (ACO) metaheurisitic. This metaheuristic is based in the self-organizing principles that govern ant population's behaviour, solving combinatorial optimization problems / Mestrado / Pesquisa Operacional / Mestre em Matemática Aplicada