Made available in DSpace on 2014-12-17T14:55:03Z (GMT). No. of bitstreams: 1 IloneideCOR.pdf: 1010601 bytes, checksum: 76bbc04aa0a456f079121fb0d750ea74 (MD5) Previous issue date: 2005-03-03 / The problems of combinatory optimization have involved a large number of researchers in search of approximative solutions for them, since it is generally accepted that they are unsolvable in polynomial time. Initially, these solutions were focused on heuristics. Currently, metaheuristics are used more for this task, especially those based on evolutionary algorithms. The two main contributions of this work are: the creation of what is called an -Operon- heuristic, for the construction of the information chains necessary for the implementation of transgenetic (evolutionary) algorithms, mainly using statistical methodology - the Cluster Analysis and the Principal Component Analysis; and the utilization of statistical analyses that are adequate for the evaluation of the performance of the algorithms that are developed to solve these problems. The aim of the Operon is to construct good quality dynamic information chains to promote an -intelligent- search in the space of solutions. The Traveling Salesman Problem (TSP) is intended for applications based on a transgenetic algorithmic known as ProtoG. A strategy is also proposed for the renovation of part of the chromosome population indicated by adopting a minimum limit in the coefficient of variation of the adequation function of the individuals, with calculations based on the population. Statistical methodology is used for the evaluation of the performance of four algorithms, as follows: the proposed ProtoG, two memetic algorithms and a Simulated Annealing algorithm. Three performance analyses of these algorithms are proposed. The first is accomplished through the Logistic Regression, based on the probability of finding an optimal solution for a TSP instance by the algorithm being tested. The second is accomplished through Survival Analysis, based on a probability of the time observed for its execution until an optimal solution is achieved. The third is accomplished by means of a non-parametric Analysis of Variance, considering the Percent Error of the Solution (PES) obtained by the percentage in which the solution found exceeds the best solution available in the literature. Six experiments have been conducted applied to sixty-one instances of Euclidean TSP with sizes of up to 1,655 cities. The first two experiments deal with the adjustments of four parameters used in the ProtoG algorithm in an attempt to improve its performance. The last four have been undertaken to evaluate the performance of the ProtoG in comparison to the three algorithms adopted. For these sixty-one instances, it has been concluded on the grounds of statistical tests that there is evidence that the ProtoG performs better than these three algorithms in fifty instances. In addition, for the thirty-six instances considered in the last three trials in which the performance of the algorithms was evaluated through PES, it was observed that the PES average obtained with the ProtoG was less than 1% in almost half of these instances, having reached the greatest average for one instance of 1,173 cities, with an PES average equal to 3.52%. Therefore, the ProtoG can be considered a competitive algorithm for solving the TSP, since it is not rare in the literature find PESs averages greater than 10% to be reported for instances of this size. / Os problemas de otimiza??o combinat?ria t?m envolvido um grande n?mero de pesquisadores na busca por solu??es aproximativas para aqueles, desde a aceita??o de que eles s?o considerados insol?veis em tempo polinomial. Inicialmente, essas solu??es eram focalizadas por meio de heur?sticas. Atualmente, as metaheur?sticas s?o mais utilizadas para essa tarefa, especialmente aquelas baseadas em algoritmos evolucion?rios. As duas principais contribui??es deste trabalho s?o: a cria??o de uma heur?stica, denominada Operon, para a constru??o de cadeias de informa??es necess?rias ? implementa??o de algoritmos transgen?ticos (evolucion?rios) utilizando, principalmente, a metodologia estat?stica - An?lise de Agrupamentos e An?lise de Componentes Principais -; e a utiliza??o de an?lises estat?sticas adequadas ? avalia??o da performance de algoritmos destinados ? solu??o desses problemas. O Operon visa construir, de forma din?mica e de boa qualidade, cadeias de informa??es a fim de promover uma busca -inteligente- no espa?o de solu??es. O Problema do Caixeiro Viajante (PCV) ? focalizado para as aplica??es que s?o realizadas com base num algoritmo transgen?tico, denominado ProtoG. Prop?e-se, tamb?m, uma estrat?gia de renova??o de parte da popula??o de cromossomos indicada pela ado??o de um limite m?nimo no coeficiente de varia??o da fun??o de adequa??o dos indiv?duos, calculado com base na popula??o. S?o propostas tr?s an?lises estat?sticas para avaliar a performance de algoritmos. A primeira ? realizada atrav?s da An?lise de Regress?o Log?stica, com base na probabilidade de obten??o da solu??o ?tima de uma inst?ncia do PCV pelo algoritmo em teste. A segunda ? realizada atrav?s da An?lise de Sobreviv?ncia, com base numa probabilidade envolvendo o tempo de execu??o observado at? que a solu??o ?tima seja obtida. A terceira ? realizada por meio da An?lise de Vari?ncia n?o param?trica, considerando o Erro Percentual da Solu??o (EPS) obtido pela percentagem em que a solu??o encontrada excede a melhor solu??o dispon?vel na literatura. Utiliza-se essa metodologia para a avalia??o da performance de quatro algoritmos, a saber: o ProtoG proposto, dois algoritmos mem?ticos e um algoritmo Simulated Annealing. Foram realizados seis experimentos, aplicados a sessenta e uma inst?ncias do PCV euclidiano, com tamanhos de at? 1.655 cidades. Os dois primeiros experimentos tratam do ajuste de quatro par?metros utilizados no algoritmo ProtoG, visando melhorar a performance do mesmo. Os quatro ?ltimos s?o utilizados para avaliar a performance do ProtoG em compara??o aos tr?s algoritmos adotados. Para essas sessenta e uma inst?ncias, conclui-se, sob testes estat?sticos, que h? evid?ncias de que o ProtoG ? superior a esses tr?s algoritmos em cinq?enta inst?ncias. Al?m disso, para as trinta e seis inst?ncias consideradas nos tr?s ?ltimos experimentos, nos quais a avalia??o da performance dos algoritmos foi realizada com base no EPS, observou-se que o ProtoG obteve EPSs m?dios menores que 1% em quase metade das inst?ncias, tendo atingido a maior m?dia para uma inst?ncia composta por 1.173 cidades, com EPS m?dio igual a 3,52%. Logo, o ProtoG pode ser considerado um algoritmo competitivo para solucionar o PCV, pois n?o ? raro serem reportados, na literatura, EPSs m?dios maiores que 10% para inst?ncias desse porte.

Made available in DSpace on 2016-08-17T14:53:07Z (GMT). No. of bitstreams: 1 Alex_Oliveira_Barradas_Filho.pdf: 1833807 bytes, checksum: f4a31a4d5e0c90f7f20cbb33ab6b1176 (MD5) Previous issue date: 2009-12-19 / FUNDAÇÃO DE AMPARO À PESQUISA E AO DESENVOLVIMENTO CIENTIFICO E TECNOLÓGICO DO MARANHÃO / The commercialization of petroleum derivates, natural gas and biofuel is an activity that needs constant monitoring and tracking. The ANP (National Agency of Petroleum, Natural Gas and Biofuel) is responsible for ensuring the products quality generated by the oil industry. However, to act effectively, ANP has established an agreement authorizing LAPQAP / UFMA (Laboratory of Analysis and Research in Analytical Chemistry of Petroleum from UFMA) to be ANP representative in the State of Maranhão. It is proposed in this work to semiautomate part of the Fuels Sample Collection process, aiming to simplify the tasks currently performed by the laboratory analysts and increase the number of stations surveyed, in order to decrease the incidence of irregularities present in fuels comertialized in Maranhão. For this, it was developed a prototype called S-Rota responsible of drawing lines between the starting point, UFMA, and the gasoline, using concepts related to Graph Theory, Traveling Salesman Problem, Ant Colony and WebSIG. / A comercialização de derivados de petróleo, gás natural e biocombustível é uma atividade que necessita, constantemente, de fiscalização e monitoramento. A ANP (Agência Nacional do Petróleo, Gás Natural e Biocombustível) é responsável em garantir a qualidade dos produtos gerados pela indústria do petróleo. No entanto, para atuar com eficiência, a ANP estabeleceu um convênio que autoriza ao LAPQAP / UFMA (Laboratório de Análise e Pesquisa em Química Analítica do Petróleo da UFMA) representá-la no Estado do Maranhão. Propõe-se, neste trabalho, semiautomatizar parte do processo de Coleta das Amostras de Combustíveis almejando simplificar as tarefas, atualmente, executadas pelos analistas do laboratório e ampliar a quantidade de postos vistoriados visando diminuir o índice de irregularidades presentes nos combustíveis comercializados no Maranhão. Para tanto, se desenvolveu um protótipo denominado S-Rota responsável em elaborar circuitos entre o ponto de partida, a UFMA, e os postos de combustíveis revendedores que aborda conceitos relacionados à Teoria dos Grafos, Problema do Caixeiro Viajante, Colônias de Formigas e WebSIG.

This thesis presents two new routing problems, both with objective functions focused on relative positioning of teams during the routing horizon. The relative positioning results in temporal and spatial dependencies among routes and is quantified with a nonlinear dispersion metric, designed to evaluate the instantaneous distances among teams over a time interval. This metric allows the design of objective functions to approximate teams during routes execution, when minimized, or disperse them, when maximized. Both approximation and dispersion are important routing characteristics in some practical applications, and two new optimization problems are proposed with these opposite objectives. The first one is a variation of the Multiple Traveling Salesman Problem, and its goal is to find a set of tours where the salesmen travel close to each other, minimizing dispersion. A Local Search Genetic Algorithm is proposed to solve the problem. It includes specialized genetic operators and neighborhoods. A new set of benchmark instances is proposed, adapted for the new problem from literature instances. Computational results show that the proposed approach provides solutions with the desired characteristics of minimal dispersion. The second problem is a bi-objective arc routing problem in which routes must be constructed in order to maximize collected profit and dispersion of teams. The maximization of the dispersion metric fosters the scattering of the teams during routing procedure. Usually, profit and dispersion objectives are conflicting, and by using a bi-objective approach the decision maker is able to choose a trade-off between collecting profits and scattering teams. Two solution methods are proposed, a Multi-objective Genetic Algorithm and a Multi-objective Genetic Local Search Algorithm, both specialized in order to exploit the characteristics of the problem. It is demonstrated, by means of computational experiments on a new set of benchmark instances, that the proposed approach provides approximation sets with the desired characteristics. / Esta tese apresenta dois novos problemas de roteamento, ambos com funções objetivo voltadas para o posicionamento relativo das equipes durante o horizonte de roteamento. O posicionamento relativo resulta em uma dependência temporal e espacial entre rotas e é quantificado com uma métrica de dispersão não-linear, projetada para avaliar as distâncias instantâneas entre as equipes ao longo de um intervalo de tempo. Esta métrica permite a concepção de funções objetivo para aproximar as equipes durante a execução das rotas, quando minimizada, ou para dispersá-las, quando maximizada. Tanto a aproximação quanto a dispersão são características importantes de roteamento em algumas aplicações práticas, e dois novos problemas de otimização são propostos com esses objetivos opostos. O primeiro é uma variação do Problema de Múltiplos Caixeiros Viajantes, e seu objetivo é encontrar um conjunto de rotas em que os caixeiros viajam próximos uns dos outros, minimizando a dispersão. Um Algoritmo Genético com Busca Local é proposto para resolver o problema. Ele inclui operadores genéticos e vizinhanças especializados. Um novo conjunto de instâncias é proposto, adaptado para o novo problema de instâncias da literatura. Resultados computacionais mostram que a abordagem proposta proporciona soluções com as características desejadas de dispersão mínima. O segundo problema é um problema de roteamento de arcos biobjetivo em que as rotas devem ser construídas de modo a maximizar o lucro recolhido e o distanciamento entre as equipes. A maximização da métrica promove a dispersão das equipes durante a execução das rotas. Normalmente, os objetivos de lucro e dispersão são conflitantes, e com uma abordagem biobjetivo o tomador de decisão é capaz de avaliar a troca entre a coleta de lucros e a dispersão de equipes. Dois métodos de solução são propostos, um Algoritmo Genético Multiobjetivo e um Algoritmo Genético Multiobjetivo com Busca Local, ambos especializados para explorar as características do problema. É demonstrado, por meio de experimentos computacionais sobre um novo conjunto de instâncias, que a abordagem proposta fornece conjuntos de aproximação com as características desejadas.

This master's thesis is focused on modern methods and tools to support managerial decision-making. The first part of this thesis introduces the basic characteristics related to the management and managerial decision-making that are subsequently extended to the area of modeling, simulation, optimization and multi-criteria decision making. It also outlines the relationship between the managerial decision-making tasks. The second part introduces practical examples which show the connection of these areas. Specifically, they are a colony of ants, traveling salesman problem, a tool AnyLogic, analytic hierarchy process and simulation HealthBound. The thesis is further supplemented by an appropriate software tools to support multi-criteria decision making.

First part of the thesis is about literature research of optimization algorithms. Three of the algorithms were implemented and tested, concretely the ant colony algorithm, tabu search and simulated annealing. All three algorithms were implemented to solve the traveling salesman problem. In second part of the thesis the algorithms were tested and compared. In last part the influence of the ant colony parameters was evaluated.

We meet with solving of optimization problems every day, when we try to do our tasks in the best way. An Ant Colony Optimization is an algorithm inspired by behavior of ants seeking a source of food. The Ant Colony Optimization is successfuly using on optimization tasks, on which is not possible to use a classical optimization methods. A Genetic Algorithm is inspired by transmision of a genetic information during crossover. The Genetic Algorithm is used for solving optimization tasks like the ACO algorithm. The result of my master's thesis is created simulator for solving choosen optimization tasks by the ACO algorithm and the Genetic Algorithm and a comparison of gained results on implemented tasks.

La planification temporelle constitue conceptuellement une partie du raisonnement temporelle et il appartient au domaine de recherche de l'intelligence artificielle. La planification temporelle peut être considérée comme une extension de la planification classique par les aspects temporels de l'action. La planification temporelle est généralement complété par des préférences ou des types différents decontraintes imposées à l'exécution des actiones. Il existe de nombreuses approches à ce problème. D'une part, il existe différents paradigmes pour la planification temporelle, par example: la planification par un recherche d'une solution optimale dans des graphes de planification (STRIPS), la planification via la satisfiabilité ou la planification pardes processus de Markov. Ces approches sont mutuellement incompatibles. D'autre part, la planification temporelle exige une sujet-spécification – comme il est défini d'une manière méthodologique. Selon cette situation, cette thèse vise à proposer une analyse approfondi de la planification avec des contraintes floues qui contient quelques remèdes à ces difficultés. À savoir, deux approches à la représentation et la modélisation de ces questions sont mises.Dans la première (chapitre 2, chapitre 3) - les relations floues d'Allen en tant que contraintes temporelles floues sont représentés par des normes de convolutions dans un espace de Banach des fonctions intégrables de Lebesgue. Cela nous permet de nous immergerles relations d'Allen dans les contextes computationnels de la planification temporelle (basée sur STRIPS et sur la procedure de Davis-Putnam) et d'élucider leur nature quantitative. Cette approche est développée dans un contexte des problèmes par systèmes multi-agents comme un sujet de cette approche. Dans les chapitres 4 et 5 les contraintes temporelles floues avec flou – introduit par préférences - sont représentées en termes logiques de la logique préférentielle de Halpern-Shoham. Cela nous permet d'adopter ces resultats dans une construction du contrôleur du plan. Cette approche est développée dans un contexte du problème du voyageur de commerce. Enfin, une tentative de réconcilier ces deux lignes de représentation des contraintes temporelles floues a été proposée dans le dernier chapitre. / Temporal planning forms conceptually a part of temporal reasoning and it belongs to research area of Artificial Intelligence and it may be seen as an extension of classical planning by temporal aspects of acting. Temporal planing is usually complemented by considering preferences or different types of temporal constraints imposed on execution of actions. There exist many approaches to this issue. One one hand, there are different paradigms to temporal planning, such as: planning via search in graphs (STRIPS), planning via satisfiability or planning in terms of Markov processes. These approaches are mutually incompatible. In addition, temporal planning requires a subject-specification as it is rather defined in a methodological way. On the other hand, temporal constraints are represented and modeled in different ways dependently on their quantitative or qualitative nature. In particular, Allen’s relations between temporal intervals – an important class of temporal constraints – do not have any quantitative aspects and cannot be considered in computational contexts. According to this situation, this PhD-thesis is aimed at the proposing a depth-analysis of temporal planning with fuzzy constraints which contains some remedies on these difficulties. Namely, two approaches to the representation and modeling of these issues are put forward. In the first one (chapter 2, chapter 3) – fuzzy Allen’s relations as fuzzy temporal constraints are represented by norms of convolutions in a Banach space of Lebesgue integrable functions. It allows us immerse Allen’s relations in the computational contexts of temporal planning (based on STRIPS and on DavisPutnam procedure) and to elucidate their quantitative nature. This approach is developed in a context of Multi-Agent Problem as a subject basis of this approach. In the second one (chapter 4, chapter 5) – fuzzy temporal constrains with fuzziness introduced by preferences are represented in a logical terms of Preferential Halpern-Shoham Logic. It allows us to adopt these result in a construction of the plan controller. This approach is developed in a context of Temporal Traveling Salesman Problem as a subject basis of this approach. Finally, an attempt to reconcile these two lines of representation of fuzzy temporal constraints was also proposed.

De nombreux problèmes d'optimisation combinatoire considèrent plusieurs objectifs, souvent conflictuels. Cette thèse s'intéresse à l'utilisation de méthodes de recherche locale, de structures de données et de recherche Monte-Carlo pour la recherche de l'ensemble des solutions efficaces de tels problèmes, représentant l'ensemble des meilleurs compromis pouvant être réalisés en considération de tous les objectifs.Nous proposons une nouvelle méthode d'approximation appelée 2-Phase Iterated Pareto Local Search based on Decomposition (2PIPLS/D) combinant les concepts de recherche locale Pareto (PLS) et de décomposition. La PLS est une descente de recherche locale adaptée au multi-objectif, et la décomposition consiste en la subdivision du problème multi-objectif en plusieurs problèmes mono-objectif. Deux méthodes d'optimisation mono-objectif sont considérées: la recherche locale itérée et la recherche Monte-Carlo imbriquée. Deux modules principaux sont intégrés à 2PIPLS/D. Le premier généralise et améliore une méthode existante et génère un ensemble initial de solutions. Le second réduit efficacement l'espace de recherche et permet d'accélérer la PLS sans négliger la qualité de l'approximation générée. Nous introduisons aussi deux nouvelles structures de données gérant dynamiquement un ensemble de solutions incomparables, la première est spécialisée pour le cas bi-objectif et la seconde pour le cas général.2PIPLS/D est appliquée au Problème du Voyageur de Commerce bi-objectif et tri-objectif et surpasse ses concurrents sur les instances testées. Ensuite, 2PIPLS/D est appliquée à un nouveau problème avec cinq objectifs en lien avec la récente réforme territoriale d'agrandissement des régions françaises. / Many Combinatorial Optimization problems consider several, often conflicting, objectives. This thesis deals with Local Search, data structures and Monte Carlo Search methods for finding the set of efficient solutions of such problems, which is the set of all best possible trade-offs given all the objectives.We propose a new approximation method called 2-Phase Iterated Pareto Local Search based on Decomposition (2PIPLS/D) combining the notions of Pareto Local Search (PLS) and Decomposition. PLS is a local search descent adapted to Multi-Objective spaces, and Decomposition consists in the subdivision of the Multi-Objective problem into a number of Single-Objective problems. Two Single-Objective methods are considered: Iterated Local Search and Nested Monte Carlo Search. Two main components are embedded within the 2PIPLS/D framework. The first one generalizes and improves an existing method generating an initial set of solutions. The second one reduces efficiently the search space and accelerates PLS without notable impact on the quality of the generated approximation. We also introduce two new data structures for dynamically managing a set of incomparable solutions. The first one is specialized for the bi-objective case, while the second one is general.2PIPLS/D is applied to the bi-objective and tri-objective Traveling Salesman Problem and outperforms its competitors on tested instances. Then, 2PIPLS/D is instantiated on a new five-objective problem related to the recent territorial reform of French regions which resulted in the reassignment of departments to new larger regions.

<p>Машинско учење и неуронске мреже су алати који налазе све већу<br />примену у решавању практичних проблема. За креирање неуронске<br />мреже потребан је скуп података, који може бити прикупљен на<br />различите начине. У овој тези је показано да се подаци за тренинг<br />неуронске мреже могу успешно прикупити креирањем веб игре.<br />Сакупљени скуп података садржи стратегије решавања проблема<br />трговачког путника и проблема рутирања возила.</p> / <p>Mašinsko učenje i neuronske mreže su alati koji nalaze sve veću<br />primenu u rešavanju praktičnih problema. Za kreiranje neuronske<br />mreže potreban je skup podataka, koji može biti prikupljen na<br />različite načine. U ovoj tezi je pokazano da se podaci za trening<br />neuronske mreže mogu uspešno prikupiti kreiranjem veb igre.<br />Sakupljeni skup podataka sadrži strategije rešavanja problema<br />trgovačkog putnika i problema rutiranja vozila.</p> / <p>Machine learning and neural networks are the tools that are finding more and<br />more fields of application in solving practical problems. For the creation of<br />the neural networks, data can be successfully collected by creating a web<br />game. The data collected in this manner has strategic solutions for the<br />problems of Travel salesperson problem and vehicle routing problem.</p>

No description available.