nach oben

2010 | Buch

Kapitel lesen Erstes Kapitel lesen

Advances in Multi-Objective Nature Inspired Computing

herausgegeben von: Carlos A. Coello Coello, Clarisse Dhaenens, Laetitia Jourdan

Verlag: Springer Berlin Heidelberg

Buchreihe : Studies in Computational Intelligence

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

The purpose of this book is to collect contributions that deal with the use of nature inspired metaheuristics for solving multi-objective combinatorial optimization problems. Such a collection intends to provide an overview of the state-of-the-art developments in this field, with the aim of motivating more researchers in operations research, engineering, and computer science, to do research in this area. As such, this book is expected to become a valuable reference for those wishing to do research on the use of nature inspired metaheuristics for solving multi-objective combinatorial optimization problems.

Inhaltsverzeichnis

Frontmatter

Multi-Objective Combinatorial Optimization: Problematic and Context

Summary

The present chapter aims to serve as a brief introduction for the rest of the chapters in this volume. The main goal is to provide a general overview of multi-objective combinatorial optimization, including its main basic definitions and some notions regarding the incorporation of user’s preferences. Additionally, we also present short descriptions of some of the most popular multi-objective evolutionary algorithms in current use. Since performance assessment is a critical task in multi-objective optimization, we also present some performance indicators, as well as some discussion on statistical validation in a multi-objective optimization context. The aim of this chapter is not to be comprehensive, but simply to touch on the main fundamental topics that are required to understand the material that is presented in the rest of the book.

Carlos A. Coello Coello, Clarisse Dhaenens, Laetitia Jourdan

Approximating Pareto-Optimal Sets Using Diversity Strategies in Evolutionary Multi-Objective Optimization

Summary

Often the Pareto front of a multi-objective optimization problem grows exponentially with the problem size. In this case, it is not possible to compute the whole Pareto front efficiently and one is interested in good approximations. We consider how evolutionary algorithms can achieve such an approximation by using different diversity mechanisms. We discuss some well-known approaches such as the density estimator and the ε -dominance approach and point out when and how such mechanisms provably help to obtain a good approximation of the Pareto-optimal set.

Christian Horoba, Frank Neumann

On the Velocity Update in Multi-Objective Particle Swarm Optimizers

Summary

Since its appearance, Particle Swarm Optimization (PSO) has become a very popular technique for solving optimization problems because of both its simplicity and its fast convergence properties. In the last few years there has been a variety of proposals for extending it to handle with multiples objectives. Although many of them keep the same properties of the original algorithm, they face difficulties when tackling the optimization of some multi-modal problems, i.e., those having more than one suboptimal front of solutions. Recent studies have shown that this disadvantage could be related to the velocity of the particles: uncontrolled high velocities may have no effect in particles movements. While many of the contributions on the specialized literature have focused on the selection of the leaders of the swarm, studies about different schemes for controlling the velocity of the particles are scarce in the multi-objective domain. In this work, we study different mechanisms in order to update the velocity of each particle with the idea of enhancing the search capabilities of multi-objective PSO algorithms. Our experiments show that some modifications help to overcoming the difficulties observed in previous proposals when dealing with hard optimization problems.

Juan J. Durillo, Antonio J. Nebro, José García-Nieto, Enrique Alba

Approaching Dynamic Multi-Objective Optimization Problems by Using Parallel Evolutionary Algorithms

Summary

Many real world optimization problems are dynamic. On the other hand, there are many optimization problems whose solutions must optimize several objectives that are in conflict. In these dynamic multi-objective problems the concept of optimum must be redefined, because instead of providing only one optimal solution, the procedures applied to these multi-objective optimization problems should obtain a set of non-dominated solutions (known as Pareto optimal solutions) that change with time. As evolutionary algorithms steer a population of solutions in a concurrent way by making use of cooperative searching techniques, it could be relatively direct to adapt these algorithms to obtain sets of Pareto optimal solutions. This contribution deals with parallel evolutionary algorithms on dynamic multi-objective optimization (DMO) problems. In this kind of problems, the speed of the reaction to changes is a quite important topic in the context of dynamic optimization, and high-performance computing approaches, such as parallel processing, should be applied to meet the given solution constraints and quality requirements.

Mario Cámara, Julio Ortega, Francisco de Toro

ParadisEO-MOEO: A Software Framework for Evolutionary Multi-Objective Optimization

Summary

This chapter presents ParadisEO-MOEO, a white-box object-oriented software framework dedicated to the flexible design of metaheuristics for multi-objective optimization. This paradigm-free software proposes a unified view for major evolutionary multi-objective metaheuristics. It embeds some features and techniques for multi-objective resolution and aims to provide a set of classes allowing to ease and speed up the development of computationally efficient programs. It is based on a clear conceptual distinction between the solution methods and the problems they are intended to solve. This separation confers a maximum design and code reuse. This general-purpose framework provides a broad range of fitness assignment strategies, the most common diversity preservation mechanisms, some elitistrelated features as well as statistical tools. Furthermore, a number of state-of-the-art search methods, including NSGA-II, SPEA2 and IBEA, have been implemented in a user-friendly way, based on the fine-grained ParadisEO-MOEO components.

Arnaud Liefooghe, Laetitia Jourdan, Thomas Legrand, Jérémie Humeau, El-Ghazali Talbi

The Multiobjective Traveling Salesman Problem: A Survey and a New Approach

Summary

The traveling salesman problem (TSP) is a challenging problem in combinatorial optimization. In this paper we consider the multiobjective TSP for which the aim is to obtain or to approximate the set of efficient solutions. In a first step, we classify and describe briefly the existing works, that are essentially based on the use of metaheuristics. In a second step, we propose a new method, called two-phase Pareto local search. In the first phase of this method, an initial population composed of an approximation to the extreme supported efficient solutions is generated. The second phase is a Pareto local search applied to all solutions of the initial population. The method does not use any numerical parameter. We show that using the combination of these two techniques—good initial population generation and Pareto local search—gives, on the majority of the instances tested, better results than state-of-the-art algorithms.

Thibaut Lust, Jacques Teghem

On the Performance of Local Search for the Biobjective Traveling Salesman Problem

Summary

In this chapter we investigate experimentally the performance of multiobjective local search approaches that are based on the component-wise acceptance criterion search model. This model gives a framework for many well-known evolutionary and local search algorithms. Using the biobjective traveling salesman problem as an example application, we analyse the impact of three important algorithmic components on the performance of a simple local search algorithm that follows this search model: initialization strategy, neighborhood structure and archive bounding. By following principles of experimental design, we study the effects of each component, both in terms of solution quality and computation time. The experimental analysis indicates the existence of several complex trade-offs between solution quality and run-time for many of the choices available for each component.

Luís Paquete, Thomas Stützle

A Bi-objective Metaheuristic for Disaster Relief Operation Planning

Summary

In this chapter we consider a multi-objective problem arising in a post-natural-disaster situation. It is assumed that the infrastructure in the affected region has been partly destroyed by an earthquake, flood or tsunami. The problem treated in the following concerns survival help which means the supply of aliment, shelter and medicine to the population living in the affected area, compensating for the destroyed facilities. Therefore a multi-objective covering tour problem has to be faced, that aims at distributing the mentioned items among the population. We developed a hybrid method based on genetic algorithms, variable neighborhood search and path relinking to solve the real-world motivated problem. The algorithm is tested on real world data from the province Manabí in Ecuador. The results on small instances are compared to an epsilon constraint method. Also results for medium- and large-size real-world instances are presented.

Pamela C. Nolz, Karl F. Doerner, Walter J. Gutjahr, Richard F. Hartl

Backmatter

Titel: Advances in Multi-Objective Nature Inspired Computing
herausgegeben von: Carlos A. Coello Coello
Clarisse Dhaenens
Laetitia Jourdan
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-11218-8
Print ISBN: 978-3-642-11217-1
DOI: https://doi.org/10.1007/978-3-642-11218-8

Premium Partner

Marktübersichten

Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen.

Zur Marktübersicht