Spelling suggestions: "subject:"aptimization metaheuristic"" "subject:"foptimization metaheuristic""
1 |
Improving a Particle Swarm Optimization-based Clustering MethodShahadat, Sharif 19 May 2017 (has links)
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.
|
2 |
Metaheurísticas para geração de alvos para robôs exploratórios autônomos / Metaheuristics for generating targets for autonomous exploratory robotsSantos, Raphael Gomes 17 August 2016 (has links)
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.
|
3 |
An Interactive Preference Based Multiobjective Evolutionary Algorithm For The Clustering ProblemDemirtas, Kerem 01 May 2011 (has links) (PDF)
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.
|
4 |
Evolutionary Clustering Search para Planejamento de Circulação de Trens de Carga / Evolutionary Clustering Search for Freight Train Circulation PlanningPINHEIRO, Eggo Henrique Freire 19 July 2017 (has links)
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.
|
5 |
Two-Stage Vehicle Routing Problems with Profits and Buffers: Analysis and Metaheuristic Optimization AlgorithmsLe, Hoang Thanh 09 June 2023 (has links)
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
|
Page generated in 0.3297 seconds