This work presents a general vision about the main concepts of combinatorial multi-objective optimization, where we present the more used technique for the resolution of problems of this nature. To the speech of the techniques we will also argue important aspects how much to the involved parameters in each technique, swing the main used boardings. Initially we implement and test the Multiple Objective Genetic Algorithm MOGA to generate a set of dominant solutions near to the Pareto optimal set for the biobjective Traveling Salesman Problems. In a second phase, we will go to implement the Strength Pareto Evolutionary Algorithm (SPEA) applied to biobjective Traveling Salesman Problems / Este trabalho apresenta uma visão geral sobre os principais conceitos da otimização combinatória multiobjetivo, onde apresentamos as técnicas mais utilizadas para a resolução de problemas desta natureza. Ao falarmos das técnicas, discutiremos também aspectos importantes quanto aos parâmetros envolvidos em cada técnica, mostrando as principais abordagens utilizadas. Inicialmente, implementamos e testamos o Multiple Objective Genetic Algorithm (MOGA) para gerar um conjunto de soluções dominantes próximo ao conjunto de Pareto ótimo para o problema do caixeiro viajante biobjetivo. Em uma segunda fase, implementamos o Strength Pareto Evolutionary Algorithm (SPEA) aplicado ao caixeiro viajante biobjetivo

Made available in DSpace on 2015-05-08T14:53:38Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 7900350 bytes, checksum: fbca2db827307d8c3ed2a1c15067d0da (MD5) Previous issue date: 2014-02-13 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This research deals with the Close-Enough Traveling Salesman Problem, a variant of the Traveling Salesman Problem wich has several applicatios in logistics. In the Close-Enough Traveling Salesman Problem, rather than visiting the vertex (customer) itself, the salesman must visit a specific region containing such vertex. To solve this problem, we propose a simple yet effective exact algorithm, based on Branch-and-Bound and Second Order Cone Programming. The proposed algorithm was tested in 824 instances suggested in the literature. Optimal solutions are obtained for open problems with up to a thousand vertices. We consider both instances in the two- and three-dimensional space. / Esta pesquisa trata do Problema do Caixeiro Viajante Suficientemente Próximo, uma variante do Problema do Caixeiro Viajante que possui diversas aplicações em logística. No Problema do Caixeiro Viajante Suficientemente Próximo, ao invés de visitar o próprio vértice (cliente), o caixeiro deve visitar uma região especifica contendo este vértice. Para resolver este problema, é proposto um algoritmo exato, simples e efetivo, baseado em branch-and-bound e Programação Cônica de Segunda Ordem. O algoritmo proposto foi testado em 824 instâncias sugeridas na literatura. Soluções ótimas foram obtidas para instâncias com até mil vértices. Foram consideradas instâncias nos espaços bi e tridimensional.

Orientador: João Batista Aparecido / Banca: Emanuel Rocha Woiski / Banca: Luis Carlos de Castro Santos / Resumo: 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, ...(Resumo completo, clicar acesso eletrônico abaixo) / Abstract: 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) / Mestre

Made available in DSpace on 2014-12-17T14:54:52Z (GMT). No. of bitstreams: 1 FranciscoCLJ.pdf: 1181019 bytes, checksum: b3894e0c93f85d3cf920c7015daef964 (MD5) Previous issue date: 2009-03-20 / Techniques of optimization known as metaheuristics have achieved success in the resolution of many problems classified as NP-Hard. These methods use non deterministic approaches that reach very good solutions which, however, don t guarantee the determination of the global optimum. Beyond the inherent difficulties related to the complexity that characterizes the optimization problems, the metaheuristics still face the dilemma of xploration/exploitation, which consists of choosing between a greedy search and a wider exploration of the solution space. A way to guide such algorithms during the searching of better solutions is supplying them with more knowledge of the problem through the use of a intelligent agent, able to recognize promising regions and also identify when they should diversify the direction of the search. This way, this work proposes the use of Reinforcement Learning technique - Q-learning Algorithm - as exploration/exploitation strategy for the metaheuristics GRASP (Greedy Randomized Adaptive Search Procedure) and Genetic Algorithm. The GRASP metaheuristic uses Q-learning instead of the traditional greedy-random algorithm in the construction phase. This replacement has the purpose of improving the quality of the initial solutions that are used in the local search phase of the GRASP, and also provides for the metaheuristic an adaptive memory mechanism that allows the reuse of good previous decisions and also avoids the repetition of bad decisions. In the Genetic Algorithm, the Q-learning algorithm was used to generate an initial population of high fitness, and after a determined number of generations, where the rate of diversity of the population is less than a certain limit L, it also was applied to supply one of the parents to be used in the genetic crossover operator. Another significant change in the hybrid genetic algorithm is the proposal of a mutually interactive cooperation process between the genetic operators and the Q-learning algorithm. In this interactive/cooperative process, the Q-learning algorithm receives an additional update in the matrix of Q-values based on the current best solution of the Genetic Algorithm. The computational experiments presented in this thesis compares the results obtained with the implementation of traditional versions of GRASP metaheuristic and Genetic Algorithm, with those obtained using the proposed hybrid methods. Both algorithms had been applied successfully to the symmetrical Traveling Salesman Problem, which was modeled as a Markov decision process / T?cnicas de otimiza??o conhecidas como metaheur?sticas t?m obtido sucesso na resolu??o de problemas classificados como NP - ?rduos. Estes m?todos utilizam abordagens n?o determin?sticas que geram solu??es pr?ximas do ?timo sem, no entanto, garantir a determina??o do ?timo global. Al?m das dificuldades inerentes ? complexidade que caracteriza os problemas NP-?rduos, as metaheur?sticas enfrentam ainda o dilema de explora??o/explota??o, que consiste em escolher entre intensifica??o da busca em uma regi?o espec?fica e a explora??o mais ampla do espa?o de solu??es. Uma forma de orientar tais algoritmos em busca de melhores solu??es ? supri-los de maior conhecimento do problema atrav?s da utiliza??o de um agente inteligente, capaz de reconhecer regi?es promissoras e/ou identificar em que momento dever? diversificar a dire??o de busca, isto pode ser feito atrav?s da aplica??o de Aprendizagem por Refor?o. Neste contexto, este trabalho prop?e o uso de uma t?cnica de Aprendizagem por Refor?o - especificamente o Algoritmo Q-learning - como uma estrat?gia de explora??o/explota??o para as metaheur?sticas GRASP (Greedy Randomized Adaptive Search Procedure) e Algoritmo Gen?tico. Na implementa??o da metaheur?stica GRASP proposta, utilizou-se o Q-learning em substitui??o ao algoritmo guloso-aleat?rio tradicionalmente usado na fase de constru??o. Tal substitui??o teve como objetivo melhorar a qualidade das solu??es iniciais que ser?o utilizadas na fase de busca local do GRASP, e, ao mesmo tempo, suprir esta metaheur?sticas de um mecanismo de mem?ria adaptativa que permita a reutiliza??o de boas decis?es tomadas em itera??es passadas e que evite a repeti??o de decis?es n?o promissoras. No Algoritmo Gen?tico, o algoritmo Q-learning foi utilizado para gerar uma popula??o inicial de alta aptid?o, e ap?s um determinado n?mero de gera??es, caso a taxa de diversidade da popula??o seja menor do que um determinado limite L, ele ? tamb?m utilizado em uma forma alternativa de operador de cruzamento. Outra modifica??o importante no algoritmo gen?tico h?brido ? a proposta de um processo de intera??o mutuamente cooperativa entre o os operadores gen?ticos e o Algoritmo Q-learning. Neste processo interativo/cooperativo o algoritmo Q-learning recebe uma atualiza??o adicional na matriz dos Q-valores com base na solu??o elite da popula??o corrente. Os experimentos computacionais apresentados neste trabalho consistem em comparar os resultados obtidos com a implementa??o de vers?es tradicionais das metaheur?sticas citadas, com aqueles obtidos utilizando os m?todos h?bridos propostos. Ambos os algoritmos foram aplicados com sucesso ao problema do caixeiro viajante sim?trico, que por sua vez, foi modelado como um processo de decis?o de Markov

nÃo hà / The planning of preventive maintenance is key role in the performance and quality of service of a power utility. The control of vegetation in the process of the electricity distribution network maintenance is of great importance to and continuous improvement of quality indicators of electricity supply, accompanied by the National Electric Energy Agency (ANEEL). The degree of criticality of pruning and productivity of teams are critical in this process. To resolve this issue it proposed a routing algorithm, in order to meet all the anomalies detected in previews, ensuring priority execution of critical cases within the period of maturity of the anomalies and before the occurrence of the failure. A genetic algorithm was developed and applied in solving this problem. The proposed technique has been adapted to a practical case of an electric utility and contributed a good economy and gains in productivity compared the current situation. / O planejamento da manutenÃÃo preventiva à papel fundamental para o bom desempenho e qualidade dos serviÃos prestados de uma concessionÃria de energia. O controle da vegetaÃÃo no processo de manutenÃÃo da rede de distribuiÃÃo de energia elÃtrica à de grande importÃncia para e melhoria contÃnua dos indicadores de qualidade do fornecimento de energia elÃtrica, acompanhado pela AgÃncia Nacional de Energia ElÃtrica (ANEEL). O grau de criticidade da poda e produtividade das equipes sÃo fatores crÃticos neste processo. Para resolver este problema foi proposto um algoritmo de roteirizaÃÃo, com o objetivo de atender todas as anomalias detectadas em inspeÃÃes prÃvias, garantindo a execuÃÃo prioritÃria dos casos mais crÃticos, dentro do prazo do vencimento das anomalias e antes da ocorrÃncia da falha. Um Algoritmo GenÃtico foi desenvolvido e aplicado na resoluÃÃo deste problema. A tÃcnica proposta foi adaptada a um caso prÃtico de uma concessionÃria de energia elÃtrica e contribuiu com uma boa economia e ganhos em produtividade, quando comparada a situaÃÃo atual.

Made available in DSpace on 2016-03-15T19:37:31Z (GMT). No. of bitstreams: 1 Ricardo Fabio Sato.pdf: 2268590 bytes, checksum: 40455266ba2f27af16965ee2b98d813a (MD5) Previous issue date: 2010-08-04 / Algorithms for solving the classical optimization problem called traveling salesman problem are proposed. These algorithms are inspired on the fact that synapses connecting biological neurons can be altered as the time passes in function of the neuronal activity. Thus, analogies between neurons and cities to be visited by the salesman and between roads and synapses coupling neurons are made. The performances of the proposed algorithms are evaluated by comparing the lengths of the paths produced by them with the length of the optimal solution. The results obtained in experiments performed by using randomly-generated instances and ten instances from a public database suggest that this is a promising approach. / Propõem-se algoritmos para solucionar o clássico problema de otimização chamado de o problema do caixeiro viajante. Esses algoritmos são inspirados no fato de que sinapses que conectam neurônios biológicos podem se alterar com o passar do tempo em função da atividade desses neurônios. Assim, fazem-se analogias entre neurônios e cidades a serem visitadas pelo caixeiro, e entre estradas e sinapses que conectam os neurônios. Os desempenhos dos algoritmos propostos são avaliados comparando-se os comprimentos dos caminhos gerados por eles com o comprimento do caminho ótimo. Os resultados obtidos em testes realizados em instâncias geradas aleatoriamente e em dez instâncias de base de dados pública indicam que essa é uma abordagem promissora.

Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T18:16:55Z (GMT). No. of bitstreams: 1 Hokama_PedroHenriqueDelBianco_M.pdf: 1340789 bytes, checksum: b5cc3f26e41b90afabdfac5c7a33bf05 (MD5) Previous issue date: 2011 / Resumo: Nesta dissertação de mestrado apresentamos um método exato para o Problema do Caixeiro Viajante com Restrições de Empacotamento Tridimensional, que combina o Problema do Caixeiro Viajante o Problema de Empacotamento Tridimensional com Restrição de Ordem. Neste problema, um veículo deve partir carregado de um depósito e entregar caixas em pontos pré-definidos para seus clientes. Cada cliente tem um conjunto de caixas que deve receber e o objetivo é minimizar o custo de deslocamento do veículo. As caixas devem ser retiradas a partir da porta do contêiner do veículo e a remoção das caixas de um cliente não podem ser obstruídas pelas caixas a serem descarregadas posteriormente. Propomos uma abordagem exata baseada em branch-and-cut para buscar uma rota de custo mínimo. Apresentamos algumas adaptações de algoritmos da literatura e uma formulação em Programação por Restrições para encontrar um empacotamento que obedece restrições de ordem. Realizamos testes computacionais em instâncias geradas aleatoriamente e comparamos resultados com os algoritmos adaptados da literatura. Os resultados foram bastante satisfatórios resolvendo instâncias de tamanho médio em tempo computacional aceitável na prática / Abstract: We present an exact method for the Traveling Salesman Problem with Three-dimensional Loading Constraints. This problem combines the Traveling Salesman Problem, and the Three- Dimensional Packing Problem With Loading Constraints. In this problem, a vehicle must be loaded at the depot and deliver boxes to the customers. Every customer has a set of boxes that should receive and our goal is to minimize the travel cost of the vehicle. Unloading is done through a single side of the container and items from an unloading customer must not be blocked by items to be delivered later. We propose exact and heuristic branch-and-cut algorithm to find a minimum cost route. Adaptations of algorithms from the literature and a Constraint Programming formulation is presented to find a packing that consider unloading contraints. We performed computational tests on instances randomly generated and compared results with the algorithms adapted from literature. The results were quite satisfactory resolving several instances in reasonable computational time / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Pedro José Catuogno / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-26T10:58:39Z (GMT). No. of bitstreams: 1 Fonte_CarlaCristina_M.pdf: 29679078 bytes, checksum: 0009a52938b1cb16c79bdc47af10d323 (MD5) Previous issue date: 2014 / Resumo: Neste trabalho, exploram-se os conceitos iniciais e aplicações importantes da teoria de grafos. Acentuam-se, nas aplicações, alguns problemas clássicos, como o das sete pontes de Königsberg, o do caixeiro viajante e o problema dos casamentos estáveis. Com o intuito de servir como material de apoio para a introdução de grafos ao ensino médio, expõe-se uma sugestão para plano de aula, cuja exploração sinaliza diversas propriedades matemáticas interessantes, além de estimular o raciocínio e o estudo / Abstract: This work focuses on the initial concepts and important applications of the graph theory. Detailing, in the applications, some classic problems such as the seven bridges of Königsberg problem, the travelling salesman problem and the stable marriage problem. In order to provide a supporting material for the introduction to graphs in high school, it is shown a suggestion to the lesson plan, which exploration indicates various interesting mathematical properties beyond stimulating the reasoning and the deep study in the field / Mestrado / Matemática em Rede Nacional / Mestra em Matemática em Rede Nacional

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

Máquinas insersoras de componentes são utilizadas na indústria eletrônica moderna para a montagem automática de placas de circuito impresso. Com a competição acirrada, há necessidade de se buscar todas as oportunidades para diminuir custos e aumentar a produtividade na exploração desses equipamentos. Neste trabalho, foi proposto um procedimento de otimização do processo de inserção da máquina insersora AVK da Panasonic, implementado em um sistema baseado na técnica de times assíncronos (A-Teams). Foram realizados testes com exemplos de placas de circuito impresso empregadas por uma indústria do ramo e problemas sintéticos para avaliar o desempenho do sistema. / Component inserting machines are employed in the modern electronics industry for the automatic assembly of printed circuit boards. Due the fierce competition, there is a need to search for all opportunities to reduce costs and increase the productivity in the exploitation of these equipment. In this work we propose an optimization procedure for the insertion process of the AVK Panasonic inserting machine, implemented in a system based on asynchronous teams (A-Teams). Tests were conducted using as examples both printed circuit boards used by a particular industry of the realm and synthetic problems for the evaluation of the system.