Orientador: Luziane Ferreira de Mendonça / Dissertação ( mestrado profissional) - Universidade Estadual de Campionas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-17T15:32:08Z (GMT). No. of bitstreams: 1 Tavora_RogerioCarvalhoMendes_M.pdf: 4616708 bytes, checksum: 3a393a830c9e1127f5694b0a56d9fcd9 (MD5) Previous issue date: 2011 / Resumo: Comemorando os 200 anos de Academia Militar no Brasil a partir de março de 2011, estão previstas várias implementações e melhorias na estrutura de visitação da AMAN que, consequentemente, vão gerar um aumento substancial no número de grupos visitantes no ano de seu bicentenário. Diante dos fatos percebe-se a necessidade de um modelo matemático eficiente cuja finalidade seja permitir aos grupos visitantes percorrerem trajetos otimizados, ou seja, que passem pelos pontos principais de visitação no menor tempo e distância possíveis. O modelo matemático a ser adotado neste trabalho é o Problema do Caixeiro Viajante (Traveling Salesman Problem - TSP), um clássico da Otimização Combinatória pertencente 'a classe de problemas NP - difícil, que já possui eficientes algoritmos desenvolvidos. Serão utilizadas heurísticas próprias para a resolução do TSP com o intuito de se obter numericamente itinerários ótimos de visitação, considerando os diferentes grupos visitantes e suas dificuldades de acesso, dentre outras particularidades. / Abstract: Celebrating 200 years of the Military Academy in Brazil from March 2011, provides a lot of implementations and improvements in the structure of visitation of AMAN, consequently, will generate substantial growth in the number of visiting groups in the year of its bicentennial. Given the facts we see the need for an efficient mathematical model whose purpose is to allow visitors to wander paths optimized groups, ie passing through the main points of visitation in the shortest possible time and distance. The mathematical model to be adopted in this work is TSP (Traveling Salesman Problem - TSP), a classic combinatorial optimization class of problems NP - hard, that have already efficient algorithms. We will use own heuristics for solving the TSP in order to obtain numerically optimal routes for visitors, considering the various visiting groups and their difficulties of access, among other features. / Mestrado / Mestre em Matemática

Orientadores: Fernando Jose Von Zuben, Leandro Nunes de Castro / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-15T01:42:44Z (GMT). No. of bitstreams: 1 Gomes_LalinkadeCamposTeixeira_D.pdf: 3303378 bytes, checksum: 65adc8d5ec20cd1f431eaca2fe3765cc (MD5) Previous issue date: 2006 / Resumo: Problemas de otimização combinatória apresentam grande relevância prática e surgem em uma ampla gama de aplicações. Em geral, a otimização combinatória está associada a uma explosão de candidatos à solução, inviabilizando a aplicação de métodos exatos. Frente à intratabilidade desta classe de problemas via métodos exatos, nos últimos anos tem havido um crescente interesse por métodos heurísticos capazes de encontrar soluções de alta qualidade, não necessariamente ótimas. Considerando o notório sucesso empírico de meta-heurísticas concebidas através da inspiração biológica e na natureza, essas abordagens vêm ganhando cada vez mais atenção por parte de pesquisadores. É fato conhecido que não existe uma única metodologia capaz de sempre produzir os melhores resultados para todas as classes de problemas, ou mesmo para todas as instâncias de uma mesma classe. Assim, a busca de solução para problemas de natureza combinatória constitui uma linha de pesquisa desafiadora. Nesta tese são considerados problemas de otimização combinatória multicritério e multimodal. Como principal contribuição, destaca-se a concepção de novas meta-heurísticas para a solução de problemas combinatórios de elevada complexidade, tendo sido propostas duas classes de ferramentas computacionais. A primeira envolve um método híbrido fundamentado em mapas auto-organizáveis de Kohonen e inferência nebulosa, em que um conjunto de regras guia o processo de treinamento do mapa de modo a permitir o tratamento de problemas com restrições e múltiplos objetivos. A segunda abordagem baseia-se em sistemas imunológicos artificiais. Em particular, a abordagem imunológica levou à proposição de meta-heurísticas capazes de encontrar e manter diversas soluções de alta qualidade, viabilizando o tratamento de problemas multimodais. Como casos de estudo, foram consideradas duas classes de problemas de otimização combinatória multimodal: o problema de roteamento de veículos capacitados e o problema do caixeiro viajante simétrico. As técnicas propostas foram também adaptadas para a solução de problemas de bioinformática, em particular ao problema de análise de dados de expressão gênica, produzindo resultados diferenciados e indicando um elevado potencial para aplicações práticas. / Abstract: Combinatorial optimization problems possess a high practical relevance and emerge on a wide range of applications. Usually, combinatorial optimization is associated with an explosion of candidates to the solution, making exact methods unfeasible. Before the unfeasibility of exact methods when dealing with this class of problems, lately there has been an increasing interest in heuristic methods capable of finding high-quality solutions, not necessarily the optimal one. Considering the widely known empirical success of metaheuristics conceived with inspiration on biological systems and on the nature itself, such approaches are receiving more and more attention from the scientific community. Evidently, there is no single methodology able to always produce the best results for all classes of problems, or even for all instances of one specific class. That is why the search for solutions to combinatorial problems remains a challenging task. This thesis considers multicriteria and multimodal combinatorial optimization problems. As the main contribution, one can emphasize the conception of new metaheuristics designed to the solution of high-complexity combinatorial optimization problems, and two classes of computational tools have been proposed. The first one involves hybrid method based on Kohonen self-organizing maps and fuzzy inference, in which a set of rules guides the training of the self-organizing maps in order to allow the handling of problems with constraints and multiple objectives. The second approach is based on artificial immune systems. Particularly, the immune-inspired approach leads to the proposal of metaheuristics capable of finding out and maintaining multiple high-quality solutions, making it possible to deal with multimodal problems. As case studies, the capacitated vehicle routing problem and the symmetric traveling salesman problem are considered, giving rise to combinatorial and multimodal problems. The proposed techniques were also adapted to the solution of problems in the field of bioinformatics, specifically the analysis of gene expression data, leading to distinguished results and indicating a high potential for practical applications. / Doutorado / Engenharia de Computação / Doutor em Engenharia Elétrica

Orientador: Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-12T02:08:09Z (GMT). No. of bitstreams: 1 Buriol_LucianaSalete_M.pdf: 8595148 bytes, checksum: 8048854c00a24631aefeb449304ce2bd (MD5) Previous issue date: 2000 / Resumo: Dentre a gama de técnicas heurísticas e exatas existentes para a resolução de problemas combinatórios, os algoritmos populacionais genéticos e meméticos têm se destacado devido a sua boa performance. Em especial, os algoritmos meméticos podem ser considerados atualmente como uma das técnicas melhores sucedidas para a resolução de vários problemas combinatórios, dentre eles, o problema do caixeiro viajante. Nesta dissertação será apresentado um algoritmo memético aplicado ao problema do caixeiro viajante assimétrico, com a proposta de uma nova busca local: Recursive Arc Insertion. Os resultados computacionais considerando as 27 instâncias assimétricas da TSPLIB são apresentados, analisados e comparados com resultados obtidos por outros métodos propostos para o problema. O mesmo algoritmo é também aplicado a 32 outras instâncias assimétricas e a 30 instâncias reduzidas do problema de ciclos hamiltonianos não direcionados. Um framework para algoritmos evolutivos é apresentado, já incluindo o algoritmo memético implementado e a redução de instâncias do problema de ciclos hamiltonianos não direcionados para o problema do caixeiro viajante simétrico. Além disso, dois geradores portáveis de instâncias com solução ótima conhecida são descritos: um para o problema do caixeiro viajante assimétrico e outro para o problema de ciclos hamiltonianos / Abstract: Among the range of heuristic and exact techniques for solving combinatorial problems, the genetic and memetic populational algorithms play an important role due to their good performance. In special, the memetic algorithms can be considered current1y as one of the best techniques to solve several combinatorial problems, especially, the traveling salesman problem. In this dissertation a memetic algorithm applied to the asymmetric traveling salesman problem is developed, and a new local search is proposed: Recursive Are Insertion. The computational results considering the 27 asymmetric instances from TSPLIB are presented, analyzed and compared with results attained by other methods recent1y published. The same algorithm is also applied to 32 other asymmetric instances and to 30 reduced instances from undirect hamiltonian cycle problem. A framework for evolutionary algorithms is also presented, including the memetic algorithm implemented and the codes which performs a reduction from the undirect hamiltonian cycle problem to the symmetric traveling salesman problem. Besides, two portable instances generators with a known optimal solution are described: one for asymmetric traveling salesman problem and other for hamiltonian cycle problem / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientador : Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T14:28:12Z (GMT). No. of bitstreams: 1 Carvalho_RodrigoMoreira_M.pdf: 6710938 bytes, checksum: 15412b36523f97788649863056960796 (MD5) Previous issue date: 2002 / Resumo: A área de otimização combinatória multiobjetivo tem despertado crescente interesse pela sua importância prática e pela necessidade de desenvolver métodos eficientes que forneçam uma boa aproximação das soluções ótimas de Pareto. Neste trabalho é abordado o problema de seqüenciamento de tarefas em uma máquina com tempos de processamento dependentes da seqüência, datas de entrega e duas medidas de desempenho: soma do atrasos das tarefas e tempo total para processar todas as tarefas, também chamado de makespan. A minimização do makespan é equivalente à minimização do comprimento da rota no problema do caixeiro viajante assimétrico. Diversas heurísticas construtivas para cada critério propostas na literatura foram adaptadas para gerar um conjunto inicial de soluções não dominadas. Este conjunto é utilizado como partida em um método de busca em vizinhança com múltiplos recomeços. Vários tipos de vizinhanças foram testados, bem como diferentes estratégias de implementação de uma busca local multiobjetivo. Uma versão do método é testada em problemas pequenos, onde as soluções ótimas de Pareto são obtidas por enumeração completa. Para problemas grandes testa-se o desempenho relativo de diversas versões do método, e compara-se a qualidade das soluções que minimizam cada objetivo individualmente com a qualidade das soluções geradas por algoritmos mono-objetivos propostos recentemente na literatura / Abstract: The area of multio~ve combinatorial optimization has attracted the attention of researchers due to its practical importance and the need to develop efficient methods that yield a good approximation of the Pareto optimal solutions. This work addresses the sequencing of jobs in a single machine with sequence dependent setup times, due dates and two performance measures: the sum of job tardiness and the total time to process all jobs, also known as makespan. The minimization of the makespan is equivalent to the minimization of the tour length for the asymmetric traveling salesman problem. Several constructive heuristics proposed for each criterion in the literature were adapted to generate an initial set of nondominated solutions. This set is used to start a neighborhood search method with multiple restarts. Various neighborhood types were tested, as well as different strategies of implementing a multiobjective local search. A version of the method is tested for small problems, where the optimal Pareto solutions are obtained by complete enumeration. For larger problems, the relative performance of versions of the method is evaluated, and the quality of the solutions that minimize each objective is compared with the solutions generated by single-objective algorithms recently proposed in the literature / Mestrado / Automação / Mestre em Engenharia Elétrica

The work proposed in this dissertation is the field of combinatorial optimization, which aims to find a solution to these types of problems at a low computational time and effectively. The combinatorial optimization studies a set of discrete solutions, which have a finite number of elements, to find the best viable solution to the problems of this magnitude. One of the main approaches that area is the Traveling Salesman Problem (TSP), mainly due to the size of possible solutions to the problem, so that is intractable computation by exhaustive search methods. Given all these features, this work is to study and develop evolutionary strategies for the resolution of the Problem of Traveling Salesman with Heterogeneous Demands (TSPHD), a variation of the classic TSP. The evolutionary strategies belong to the class of evolutionary computation, and methods of search based on the theory of the evolution of species, where the best individuals compete for survival. The evolutionary strategies differ from other optimization techniques, as the search is conducted in a population of solutions, not a single point. To solve the problem are proposed four evolutionary algorithms, using heuristics techniques and metaheurísticas for its implementation. The results were obtained from tests using instances of low density (low connection), and compared with the exact solution (optimal solution) and other progressive methods in the literature. These results are evaluated on the basis of their quality and time for its implementation. / O trabalho proposto nessa dissertação pertence à área de otimização combinatória, a qual visa encontrar uma solução para esses tipos de problema em um tempo computacional baixo e de forma eficaz. A otimização combinatória estuda um conjunto discreto de soluções, os quais possuem um número finito de elementos, para se poder encontrar a melhor solução viável para os problemas dessa grandeza. Uma das principais abordagens dessa área é o Problema do Caixeiro Viajante (PCV), principalmente devido à dimensão de possíveis soluções para o problema, fazendo com que seja intratável computacionalmente por métodos de buscas exaustivas. Face a todas essas características, este trabalho tem por objetivo estudar e desenvolver estratégias evolutivas para a resolução do Problema do Caixeiro Viajante com Demandas Heterogêneas (PCVDH), uma variação do PCV clássico. As estratégias evolutivas pertencem à classe da computação evolutiva, sendo métodos de busca inspirados na teoria da evolução das espécies, onde os melhores indivíduos competem pela sobrevivência. As estratégias evolutivas diferem das demais técnicas de otimização, pois a busca é realizada em uma população de soluções, não em um único ponto. Para a resolução do problema são propostos quatro algoritmos evolutivos, utilizando técnicas heurísticas e metaheurísticas para sua aplicação. Os resultados foram obtidos com testes utilizando instâncias de baixa densidade (baixa conexão), e comparados com a sua solução exata (solução ótima) e com outros métodos evolutivos encontrados na literatura. Esses resultados são avaliados com base na sua qualidade e tempo decorrido para sua execução.

Made available in DSpace on 2014-06-11T19:23:39Z (GMT). No. of bitstreams: 0 Previous issue date: 2007-09-06Bitstream added on 2014-06-13T18:51:01Z : No. of bitstreams: 1 ferreira_ab_me_ilha.pdf: 5542320 bytes, checksum: ac4ab4f7279192ce563639cce31eb895 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Desenvolveu-se neste trabalho a implementação computacional de um algoritmo genético. Este se constituiu de uma população inicial sobre a qual agem quatro operadores fundamentais: seleção, “crossover”, substituição e mutação, e produz uma nova população. Sobre a qual agem novamente os operadores genéticos, e assim sucessivamente produzindo uma seqüência de populações. O operador seleção foi implementado em três algoritmos básicos: roda da roleta, amostragem estatística universal e torneio. O “crossover” também foi desenvolvido em algumas opções: um ponto, dois pontos, múltiplos pontos, e uniforme. A substituição de indivíduos da população pelos filhos ocorre de três maneiras básicas: dos pais, dos menos aptos, e dos indivíduos sorteados aleatoriamente. A mutação ocorre de apenas uma maneira. Inicialmente, o algoritmo genético foi executado em computador de maneira seqüencial. Resolveu-se um conjunto de problemas de otimização multidimensional e também o Problema do Caixeiro Viajante (TSP – Traveler Salesman Problem). Fez-se um estudo paramétrico dos vários parâmetros que aparecem no algoritmo genético, tais como: tamanho da população, número de gerações, taxa de seleção, probabilidade de mutação, e taxa de elitismo. No caso de problemas de otimização multidimensional a representação do cromossomo de cada indivíduo é binária, já no caso do TSP a representação é inteira decimal. Em ambos os casos da otimização multidimensional e do TSP também foi utilizada a técnica de hill-climbing visando aumentar a taxa de convergência da solução. A técnica de janelamento foi utilizada somente no caso de otimização multidimensional, também visando aumentar a taxa de convergência. Posteriormente, o algoritmo genético foi executado também em processamento computacional paralelo,... / It was developed in this work the computational implementation of a genetic algorithm. That is constituted of an initial population upon which act four basic operators: selection, crossover, substitution and mutation, producing a new population. Upon which act again the genetic operators, and thus, successively, producing a sequence of populations. The operator selection was implemented in three basic algorithms: roulette wheel, stochastic universal sampling, and tournament. The crossover also was developed in some options: one point, two points, several points, and uniform. Substitution of individuals from the population by the newborns happens in three basic ways: the fathers, the less apt, and the individuals sorted randomly. Mutation happens in only one manner. Initially, the genetic algorithm was processed sequentially in the computer. It was solved a set of multidimensional optimization problems and also the Traveler Salesman Problem - TSP. It was done a parametric study of the several parameters that appear in the genetic algorithm, such as: population size, number of generations, selection rate, mutation probability, and elitism rate. In the case of multidimensional optimization problems the chromosome representation of each individual is binary, but in the case of TSP the representation is integer decimal. In both cases of multidimensional optimization and TSP also it were used the hill-climbing technique aiming to increase the solution convergence rate. The windowing technique was used just for the multidimensional optimization case, also aiming to increase the convergence rate. Lately, the genetic algorithm was also performed in a computational parallel processing mode, using several computers linked by a net. In each computer it was executed one genetic algorithm upon a local population. The interaction among several populations was done through the migration ...(Complete abstract, click electronic access below)

Made available in DSpace on 2014-12-17T14:52:47Z (GMT). No. of bitstreams: 1 ThalesLS.pdf: 825402 bytes, checksum: 8e0d2b64fc7287a7921fa605343a8bb6 (MD5) Previous issue date: 2008-12-23 / Particle Swarm Optimization is a metaheuristic that arose in order to simulate the behavior of a number of birds in flight, with its random movement locally, but globally determined. This technique has been widely used to address non-liner continuous problems and yet little explored in discrete problems. This paper presents the operation of this metaheuristic, and propose strategies for implementation of optimization discret problems as form of execution parallel as sequential. The computational experiments were performed to instances of the TSP, selected in the library TSPLIB contenct to 3038 nodes, showing the improvement of performance of parallel methods for their sequential versions, in executation time and results / Otimiza??o por Enxame de Part?culas ou Particle Swarm Optimization (PSO) ? uma metaheur?stica que surgiu na inten??o de simular o comportamento de um conjunto de p?ssaros em v?o, com seu movimento localmente aleat?rio, mas globalmente determinado. Esta t?cnica tem sido muito utilizada na resolu??o de problemas cont?nuos n?o-lineares e ainda pouco explorada em problemas discretos. Este trabalho apresenta o funcionamento desta metaheur?stica, al?m de propor estrat?gias para sua aplica??o em problemas de otimiza??o discreta tanto na sua forma de execu??o seq?encial quanto paralela. Os experimentos computacionais foram realizados para inst?ncias do problema do caixeiro viajante, selecionados na biblioteca TSPLIB contendo at? 1002 n?s, mostrando a melhoria de desempenho dos m?todos paralelos em rela??o as suas vers?es seq?enciais, em tempo de execu??o e resultados

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-06-02T19:19:17Z No. of bitstreams: 1 RanmsesEmanuelMartinsBastos_DISSERT.pdf: 3544164 bytes, checksum: 0be0a21709a7526cbbea13cf73f55d8e (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-06-05T19:52:50Z (GMT) No. of bitstreams: 1 RanmsesEmanuelMartinsBastos_DISSERT.pdf: 3544164 bytes, checksum: 0be0a21709a7526cbbea13cf73f55d8e (MD5) / Made available in DSpace on 2017-06-05T19:52:51Z (GMT). No. of bitstreams: 1 RanmsesEmanuelMartinsBastos_DISSERT.pdf: 3544164 bytes, checksum: 0be0a21709a7526cbbea13cf73f55d8e (MD5) Previous issue date: 2017-02-17 / O Problema do Caixeiro Viajante com Passageiros e Lota??o ? uma vers?o do PCV cl?ssico onde o caixeiro ? o motorista de um ve?culo que compartilha os custos de viagem com passageiros. Al?m de dividir os custos do percurso, o caixeiro pode se valer, tamb?m, dos descontos das high-occupancy vehicle lanes, que s?o faixas de tr?nsito que isentam ve?culos lotados do pagamento de ped?gio. A adi??o de passageiros ao PCV, um problema restrito ao roteamento, cria um vi?s colaborativo que ? intensificado pela considera??o das faixas especiais. Tal cen?rio confere ao problema estudado um aspecto ecol?gico, uma vez que seu estudo tem consequ?ncias diretas sobre o uso eficiente do espa?o urbano e a diminui??o da emiss?o de gases poluentes, contribuindo sobremaneira para o incremento da qualidade de vida. A pesquisa compreendeu desde a correla??o entre esse novo problema e outros constantes na literatura at? a concep??o de um conjunto de seiscentas inst?ncias artificiais e a cria??o de diversos m?todos de solu??o. Para a determina??o de ?timos, ? proposto um modelo matem?tico que suportou as solu??es por Programa??o Matem?tica e por Restri??es. Adicionalmente, ? apresentado um algoritmo branch-and-bound especificamente desenvolvido para o problema. Visando a busca por solu??es de qualidade em curto espa?o de tempo, s?o expostos cinco algoritmos experimentais com base nas abordagens heur?sticas Simulated Annealing, Variable Neighborhood Search, Coloniza??o de Abelhas e Algoritmos Gen?ticos. Diversos procedimentos auxiliares para constru??o de solu??es e execu??o de buscas locais s?o tamb?m expostos. Um experimento computacional ? realizado para compara??o entre os m?todos de solu??o. Uma amostra de cem casos teste ? utilizada para o processo estat?stico de ajuste de par?metros dos algoritmos heur?sticos, enquanto o restante das inst?ncias ? extensivamente abordado pelos m?todos. S?o determinados os ?timos para cento e cinquenta e cinco casos com tamanhos 10 e 20 cidades. Dentre os m?todos experimentais, cabe destacar a superioridade do algoritmo heur?stico que une as meta-heur?sticas Simulated Annealing e Variable Neighborhood Search. / The Traveling Salesman with Passengers and High Occupancy Problem is a version of the classic TSP where the salesman is the driver of a vehicle who shares travels? expenses with passengers. Besides shared expenses, the driver also benefits from discounts of the highoccupancy vehicle lanes, i.e. traffic lanes in which high occupancy vehicles are exempted from tolls. The addition of passengers to the TSP, a routing-only problem, creates a sharing view which is intensified by the consideration of special lanes. This scenario grants to the problem an ecological feature, since its study have direct consequences for the efficient use of urban space and the greenhouse gas emissions reduction, greatly contributing for quality of life improvement. This work addresses the study of this novel combinatorial optimization problem, going from the relationship it draws with other ones in the literature until the conception of a six hundred set of artificial test cases and the creation of many solution methods. To find optimal solutions, a mathematical model is proposed. This model supported the search for exact solutions by Mathematical and Constraint Programming. Additionally, is presented a branchand- bound algorithm specifically developed for the problem. Aiming the search for good quality solutions in short time period, five experimental algorithms based on the heuristics approaches Simulated Annealing, Variable Neighborhood Search, Bees Colony and Genetic Algorithms are introduced. Several auxiliary procedures for solutions generations and local search execution are revealed as well. A computational experiment is fulfilled to comparison between the solution methods. A sample of a hundred test cases is used for the heuristics algorithms? parameter tuning statistical process, while the rest of them are extensively addressed by the methods. The optimal solution for a hundred and fifty five test cases with sizes of 10 and 20 cities are determined. Among the experimental methods, one has to highlight the advantage of the heuristic algorithm that unites the metaheuristics Simulated Annealing and Variable Neighborhood Search.

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

O problema do caixeiro viajante (PCV) é um problema clássico de otimização que possui diversas variações, aplicações e instâncias. Encontrar a solução ótima para muitas instâncias desse problema é geralmente muito difícil devido o alto custo computacional. Vários métodos de otimização, conhecidos como meta-heurísticas (MHs), são capazes de encontrar boas soluções para o PCV. Muitos algoritmos baseados em diversas MHs têm sido propostos e investigados para diferentes variações do PCV. Como não existe um algoritmo universal que encontre a melhor solução para todas as instâncias de um problema, diferentes MHs podem prover a melhor solução para diferentes instâncias do PCV. Desse modo, a seleção a priori da MH que produza a melhor solução para uma dada instância é uma tarefa difícil. A pesquisa desenvolvida nesta tese investiga o uso de abordagens de meta-aprendizado para selecionar as MHs mais promissoras para novas instâncias de PCV. Essas abordagens induzem meta-modelos preditivos a partir do treinamento das técnicas de aprendizado de máquina em um conjunto de meta-dados. Cada meta-exemplo, em nosso conjunto de meta-dados, representa uma instância de PCV descrita por características (meta-atributos) do PCV e pelo desempenho das MHs (meta-atributo alvo) para essa instância. Os meta-modelos induzidos são usados para indicar os valores do meta-atributo alvo para novas instâncias do PCV. Vários experimentos foram realizados durante a investigação desta pesquisa e resultados importantes foram obtidos / The traveling salesman problem (TSP) is a classical optimization problem that has several variations, applications and instances. To find the optimal solution for many instances of this problem is usually a very hard task due to high computational cost. Various optimization methods, known as metaheuristics (MHs), are capable to generate good solutions for the TSP. Many algorithms based on different MHs have been proposed and investigated for different variations of the TSP. Different MHs can provide the best optimization solution for different TSP instances, since there is no a universal algorithm able to find the best solution for all instances. Thus, a priori selection of the MH that produces the best solution for a given instance is a hard task. The research developed in this thesis investigates the use of meta-learning approaches to select the most promising MHs for new TSP instances. These approaches induce predictive meta-models from the training of machine learning techniques on a set of meta-data. In our meta-data, each meta-example is a TSP instance described by problem characteristics (meta-features) and performance of MHs (target meta-features) for this instance. The induced meta-models are used to indicate the values of the target meta-feature for new TSP instances. During the investigation of this research, several experiments were performed and important results were obtained