This thesis discusses clustering related works with emphasis on Particle Swarm Optimization (PSO) principles. Specifically, we review in detail the PSO clustering algorithm proposed by Van Der Merwe & Engelbrecht, the particle swarm clustering (PSC) algorithm proposed by Cohen & de Castro, Szabo’s modified PSC (mPSC), and Georgieva & Engelbrecht’s Cooperative-Multi-Population PSO (CMPSO). In this thesis, an improvement over Van Der Merwe & Engelbrecht’s PSO clustering has been proposed and tested for standard datasets. The improvements observed in those experiments vary from slight to moderate, both in terms of minimizing the cost function, and in terms of run time.

Submitted by Rosivalda Pereira (mrs.pereira@ufma.br) on 2017-07-25T17:21:34Z No. of bitstreams: 1 RaphaelSantos.pdf: 3718930 bytes, checksum: df335fd5562e8156000972c282fe9724 (MD5) / Made available in DSpace on 2017-07-25T17:21:34Z (GMT). No. of bitstreams: 1 RaphaelSantos.pdf: 3718930 bytes, checksum: df335fd5562e8156000972c282fe9724 (MD5) Previous issue date: 2016-08-17 / Autonomous exploration, in robotics, can be defined as the act of moving into an unknown environment, at priori, while building up a map of the environment. A great deal of literature describes several problems that are relate to the strategy exploration: perception, location, trajectory control and mapping. This work aims to present an autonomous exploration algorithm based on metaheuristics. Therefore, the problem of autonomous exploration of mobile robots is formulated as an optimization problem, providing data for metaheuristics that are able to search points in the space of solutions that represent positions on the map under construction that best meet the objectives of the exploration. Metaheuristics are approximate methods that guarantee sufficiently good solutions to optimization problems. The proposal was implemented and incorporated as an optimization module in a simultaneous location and mapping system that was run on the Robot Operating System environment and proved to be able to guide a simulated robot without human intervention. Two optimization metaheuristics were implemented to guide target to simulated robot: Genetic Algorithm and Firefly Algorithm. Both algorithms have achieved good results, however the second one was able to guide robot by best trajectories. / Exploração autônoma, em robótica, pode ser definida como o ato de mover-se em um ambiente, a princípio desconhecido, enquanto constrói-se um mapa deste ambiente. Uma grande parte da literatura relata vários problemas que se relacionam com a estratégia de exploração: percepção, localização, trajetória, controle e mapeamento. Este trabalho visa apresentar um algoritmo de exploração autonoma baseado em metaheurísticas. Para tanto, o problema de exploração autônoma de robôs móveis é formulado como um problema de otimização, fornecendo dados para que metaheurísticas sejam capazes de buscar pontos no espaço de soluções que representam posições no mapa em construção que melhor satisfaçam os objetivos da exploração. Metaheuristicas são metodos aproximados que garantem soluções suficientemente boas para problemas de otimização. A proposta foi implementada e incorporada como um módulo de otimização em um sistema de localização e mapeamento simultâneos que foi executado em ambiente Robot Operating System e mostrou-se capaz de guiar um robô simulado sem intervenção humana. As metaheurísticas usadas foram o Algoritmo Genético e o Algoritmo de Vagalumes. Ambos os algoritmos obtiveram bons resultados, no entanto o Algoritmo de Vagalumes guiou o robô por trajetórias melhores.

We propose an interactive preference-based evolutionary algorithm for the clustering problem. The problem is highly combinatorial and referred to as NP-Hard in the literature. The goal of the problem is putting similar items in the same cluster and dissimilar items into different clusters according to a certain similarity measure, while maintaining some internal objectives such as compactness, connectivity or spatial separation. However, using one of these objectives is often not sufficient to detect different underlying structures in different data sets with clusters having arbitrary shapes and density variations. Thus, the current trend in the clustering literature is growing into the use of multiple objectives as the inadequacy of using a single objective is understood better. The problem is also difficult because the optimal solution is not well defined. To the best of our knowledge, all the multiobjective evolutionary algorithms for the clustering problem try to generate the whole Pareto optimal set. This may not be very useful since majority of the solutions in this set may be uninteresting when presented to the decision maker. In this study, we incorporate the preferences of the decision maker into a well known multiobjective evolutionary algorithm, namely SPEA-2, in the optimization process using reference points and achievement scalarizing functions to find the target clusters.

Submitted by Rosivalda Pereira (mrs.pereira@ufma.br) on 2017-10-31T20:55:43Z No. of bitstreams: 1 eggo_pinheiro.pdf: 1913399 bytes, checksum: d95298cbe73fd1e96bc181f116178ffa (MD5) / Made available in DSpace on 2017-10-31T20:55:43Z (GMT). No. of bitstreams: 1 eggo_pinheiro.pdf: 1913399 bytes, checksum: d95298cbe73fd1e96bc181f116178ffa (MD5) Previous issue date: 2017-07-19 / Freight railways are the major means of transportation of bulk material, such as iron ore from the origin to the destination. Usually for heavy haul railways, the destination is a port. For the last few years there has been a fast growing demand. However, railway infrastructure capacity increasing is very expensive and require a lot of investiment budget. Therefore, an improvement of train scheduling process is needed to ensure the best and efficient use of the current railway. Nevertheless, in some situations it is overwhelmingly complex to solve, an NP-hard problem. Since all the previous work provided on the Train Timetable Problem is usually only applied locally to a single railway, this work provides a public base benchmark of test railways built by heuristcs. Moreover, this work deals with the train timetabling problem applied to mixed traffic railways with both cargo trains and passenger trains sharing the same resources with different priorities. It is proposed a new mathematical model extended from literature previous work intended to avoid infeasible solutions instead reparing or discarding on these cases. This model contains additional support for parallel multi-track for several railway’s signaling system approaches context as well as overtaking on it without deadlocks possibility. This model considers trains in current position and future departure planned. To achieve an improved train scheduling is applied the Evolutionary Clustering Search (ECS) with multi heuristics approaches and a modified mutation operator of Genetic Algorithm as component of ECS. The experiments shows ECS outperforms almost all tests scenario and the modified mutation operator strongly improve the results / Ferrovias de trens de carga são os principais meios de transporte de materiais, tais como minério de ferro, da sua origem até o seu destino. Geralmente para ferrovias de transporte pesado, o destino é o porto. Nos últimos anos, a demanda de produção tem aumentado assim como o uso da ferrovia para transportá-la, no entanto, a expansão da sua infraestrutura requer um grande investimento. Assim, um planejamento de circulação de trens mais efetivo que maximize a capacidade de tráfego se faz necessária. No entanto, em algumas situações a sua otimização é bastante complexa para ser executada, um problema NP-Difícil. Embora todo trabalho elaborado nesse tema é geralmente aplicado localmente em uma única ferrovia, este trabalho provê uma base genérica de ferrovias gerado por heurísticas. Além disso, esta dissertação lida com o problema de circulação de trens aplicado a ferrovias mistas envolvendo trens de carga assim como trens de passageiros compartilhando o mesmo recurso e com diferentes prioridades. É proposto um novo modelo matemático estendido de um trabalho existente na literatura que procura evitar conflitos ao invés de permitir soluções inviáveis, sendo necessário reparação delas ou descarte. Este modelo lida com uma quantidade variável de linhas em locais de parada compatível com várias abordagens de sistema de sinalização disponíveis, assim como considera ultrapassagens de forma a evitar deadlocks, da mesma forma que trata contextos de trens em circulação como planejados para realizar a otimização. Para encontrar boas soluções, ao planejamento de circulação de trens é aplicado uma abordagem do Evolutionary Clustering Search (ECS) com múltiplas heurísticas, e um operador de mutação modificado do Algoritmo Genético como componente do ECS. Os experimentos computacionais mostraram que o ECS superou quase todos os cenários de teste e o operador de mutação modificado melhorou significativamente os resultados finais.

This thesis considers the Two-Stage Vehicle Routing Problem (VRP) with Profits and Buffers, which generalizes various optimization problems that are relevant for practical applications, such as the Two-Machine Flow Shop with Buffers and the Orienteering Problem. Two optimization problems are considered for the Two-Stage VRP with Profits and Buffers, namely the minimization of total time while respecting a profit constraint and the maximization of total profit under a budget constraint. The former generalizes the makespan minimization problem for the Two-Machine Flow Shop with Buffers, whereas the latter is comparable to the problem of maximizing score in the Orienteering Problem. For the three problems, a theoretical analysis is performed regarding computational complexity, existence of optimal permutation schedules (where all vehicles traverse the same nodes in the same order) and potential gaps in attainable solution quality between permutation schedules and non-permutation schedules. The obtained theoretical results are visualized in a table that gives an overview of various subproblems belonging to the Two-Stage VRP with Profits and Buffers, their theoretical properties and how they are connected. For the Two-Machine Flow Shop with Buffers and the Orienteering Problem, two metaheuristics 2BF-ILS and VNSOP are presented that obtain favorable results in computational experiments when compared to other state-of-the-art algorithms. For the Two-Stage VRP with Profits and Buffers, an algorithmic framework for Iterative Search Algorithms with Variable Neighborhoods (ISAVaN) is proposed that generalizes aspects from 2BF-ILS as well as VNSOP. Various algorithms derived from that framework are evaluated in an experimental study. The evaluation methodology used for all computational experiments in this thesis takes the performance during the run time into account and demonstrates that algorithms for structurally different problems, which are encompassed by the Two-Stage VRP with Profits and Buffers, can be evaluated with similar methods. The results show that the most suitable choice for the components in these algorithms is dependent on the properties of the problem and the considered evaluation criteria. However, a number of similarities to algorithms that perform well for the Two-Machine Flow Shop with Buffers and the Orienteering Problem can be identified. The framework unifies these characteristics, providing a spectrum of algorithms that can be adapted to the specifics of the considered Vehicle Routing Problem.:1 Introduction 2 Background 2.1 Problem Motivation 2.2 Formal Definition of the Two-Stage VRP with Profits and Buffers 2.3 Review of Literature on Related Vehicle Routing Problems 2.3.1 Two-Stage Vehicle Routing Problems 2.3.2 Vehicle Routing Problems with Profits 2.3.3 Vehicle Routing Problems with Capacity- or Resource-based Restrictions 2.4 Preliminary Remarks on Subsequent Chapters 3 The Two-Machine Flow Shop Problem with Buffers 3.1 Review of Literature on Flow Shop Problems with Buffers 3.1.1 Algorithms and Metaheuristics for Flow Shops with Buffers 3.1.2 Two-Machine Flow Shop Problems with Buffers 3.1.3 Blocking Flow Shops 3.1.4 Non-Permutation Schedules 3.1.5 Other Extensions and Variations of Flow Shop Problems 3.2 Theoretical Properties 3.2.1 Computational Complexity 3.2.2 The Existence of Optimal Permutation Schedules 3.2.3 The Gap Between Permutation Schedules an Non-Permutation 3.3 A Modification of the NEH Heuristic 3.4 An Iterated Local Search for the Two-Machine Flow Shop Problem with Buffers 3.5 Computational Evaluation 3.5.1 Algorithms for Comparison 3.5.2 Generation of Problem Instances 3.5.3 Parameter Values 3.5.4 Comparison of 2BF-ILS with other Metaheuristics 3.5.5 Comparison of 2BF-OPT with NEH 3.6 Summary 4 The Orienteering Problem 4.1 Review of Literature on Orienteering Problems 4.2 Theoretical Properties 4.3 A Variable Neighborhood Search for the Orienteering Problem 4.4 Computational Evaluation 4.4.1 Measurement of Algorithm Performance 4.4.2 Choice of Algorithms for Comparison 4.4.3 Problem Instances 4.4.4 Parameter Values 4.4.5 Experimental Setup 4.4.6 Comparison of VNSOP with other Metaheuristics 4.5 Summary 5 The Two-Stage Vehicle Routing Problem with Profits and Buffers 5.1 Theoretical Properties of the Two-Stage VRP with Profits and Buffers 5.1.1 Computational Complexity of the General Problem 5.1.2 Existence of Permutation Schedules in the Set of Optimal Solutions 5.1.3 The Gap Between Permutation Schedules an Non-Permutation Schedules 5.1.4 Remarks on Restricted Cases 5.1.5 Overview of Theoretical Results 5.2 A Metaheuristic Framework for the Two-Stage VRP with Profits and Buffers 5.3 Experimental Results 5.3.1 Problem Instances 5.3.2 Experimental Results for O_{max R, Cmax≤B} 5.3.3 Experimental Results for O_{min Cmax, R≥Q} 5.4 Summary Bibliography List of Figures List of Tables List of Algorithms