Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2013 | Buch

Evolutionary Dynamic Optimization: Test and Evaluation Environments Kapitel lesen Erstes Kapitel lesen

Evolutionary Computation for Dynamic Optimization Problems

herausgegeben von: Shengxiang Yang, Xin Yao

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
insite
SUCHEN

Über dieses Buch

This book provides a compilation on the state-of-the-art and recent advances of evolutionary computation for dynamic optimization problems. The motivation for this book arises from the fact that many real-world optimization problems and engineering systems are subject to dynamic environments, where changes occur over time.

Key issues for addressing dynamic optimization problems in evolutionary computation, including fundamentals, algorithm design, theoretical analysis, and real-world applications, are presented. "Evolutionary Computation for Dynamic Optimization Problems" is a valuable reference to scientists, researchers, professionals and students in the field of engineering and science, particularly in the areas of computational intelligence, nature- and bio-inspired computing, and evolutionary computation.

Inhaltsverzeichnis

Frontmatter

Fundamentals

Frontmatter
Evolutionary Dynamic Optimization: Test and Evaluation Environments
Abstract
In the last two decades, dynamic optimization problems (DOPs) have drawn a lot of research studies from the evolutionary computation (EC) community due to the importance in real-world applications. A variety of evolutionary computation approaches have been developed to address DOPs. In parallel with developing new approaches, many benchmark and real-world DOPs have been constructed and used to compare them under different performance measures. In this chapter, we describe the concept of DOPs and review existing dynamic test problems that are commonly used by researchers to investigate their EC approaches in the literature. Some discussions regarding the major features of existing dynamic test environments are presented. Typical dynamic benchmark problems and real-world DOPs are described in detail. We also review the performance measures that are widely used by researchers to evaluate and compare their developed EC approaches for DOPs. Suggestions are also given for potential improvement regarding dynamic test and evaluation environments for the EC community.
Shengxiang Yang, Trung Thanh Nguyen, Changhe Li
Evolutionary Dynamic Optimization: Methodologies
Abstract
In recent years, Evolutionary Dynamic Optimization (EDO) has attracted a lot of research effort and has become one of the most active research areas in evolutionary computation (EC) in terms of the number of activities and publications. This chapter provides a summary of main EDO approaches in solving DOPs. The strength and weakness of each approach and their suitability for different types of DOPs are discussed. Current gaps, challenging issues and future directions regarding EDO methodolgies are also presented.
Trung Thanh Nguyen, Shengxiang Yang, Juergen Branke, Xin Yao
Evolutionary Dynamic Optimization: Challenges and Perspectives
Abstract
The field of evolutionary dynamic optimization is concerned with the study and application of evolutionary algorithms to dynamic optimization problems. In this chapter we highlight some of the challenges associated with the time-variant nature of these problems.We focus particularly on the different problem definitions that have been proposed, the modelling of dynamic optimization problems in terms of benchmark suites and the way the performance of an algorithm is assessed. Amid significant developments in the last decade, several practitioners have highlighted shortcomings with all of these fundamental issues. In this chapter we review the work done in each of these areas, evaluate the criticism and subsequently identify some perspectives for the future of the field.
Philipp Rohlfshagen, Xin Yao
Dynamic Multi-objective Optimization: A Survey of the State-of-the-Art
Abstract
Many optimization problems involve multiple objectives, constraints and parameters that change over time. These problems are called dynamic multiobjective optimization problems (DMOPs) and have recently attracted a lot of research. In this chapter, we provide a survey of the state-of-the-art on the field of dynamic multi-objective optimization with regards to the definition and classification of DMOPS, test problems, performance measures and optimization approaches. We provide a comprehensive definition of DMOPs and identify gaps, challenges and future works in dynamic multi-objective optimization.
Carlo Raquel, Xin Yao

Algorithm Design

Frontmatter
A Comparative Study on Particle Swarm Optimization in Dynamic Environments
Abstract
Particle swarm optimization (PSO) has been shown an effective optimization tool since it was proposed. Due to the efficiency of locating optima, it has been widely applied to solve dynamic optimization problems (DOPs) with variant enhancements, e.g., diversity maintaining schemes, memory schemes, multipopulation schemes, adaptive schemes, and hybrid schemes. In this chapter, we categorize and review approaches proposed based on PSO for DOPs. Weaknesses and strengths of those approaches are also discussed in this chapter. In order to investigate the performance of those approaches, a set of typical algorithms based on PSO are chosen to compare their performance on the moving peaks problem (MPB). According to the comparison results, suggestions are also given regarding future algorithms development for DOPs.
Changhe Li, Shengxiang Yang
Memetic Algorithms for Dynamic Optimization Problems
Abstract
Dynamic optimization problems challenge traditional evolutionary algorithms seriously since they, once converged, cannot adapt quickly to environmental changes. This chapter investigates the application of memetic algorithms, a class of hybrid evolutionary algorithms, for dynamic optimization problems. An adaptive hill climbing method is proposed as the local search technique in the framework of memetic algorithms, which combines the features of greedy crossover-based hill climbing and steepest mutation-based hill climbing. In order to address the convergence problem, a new immigrants scheme, where the immigrant individuals can be generated from mutating an elite individual adaptively, is also introduced into the proposed memetic algorithm for dynamic optimization problems. Based on a series of dynamic problems generated from several stationary benchmark problems, experiments are carried out to investigate the performance of the proposed memetic algorithm in comparison with some peer algorithms. The experimental results show the efficiency of the proposed memetic algorithm in dynamic environments.
Hongfeng Wang, Shengxiang Yang
BIPOP: A New Algorithm with Explicit Exploration/Exploitation Control for Dynamic Optimization Problems
Abstract
Dynamic optimization problems (DOPs) have proven to be a realistic model of dynamic environments where the fitness function, problem parameters, and/or problem constraints are subject to changes. Evolutionary algorithms (EAs) are getting pride of place in solving DOPs due to their ability to match with Nature evolution processes. Several approaches have been presented over the years to enhance the performance of EAs to locate the moving optima in the landscape and avoid premature convergence. We address in this chapter a new bi-population EA augmented by a memory of past solutions and validate it with the dynamic knapsack problem (DKP). We suggest, through the use of two populations, to conduct the search to different directions in the problem space: the first population takes in charge exploring while the second population is responsible for exploiting. Once an environment change is detected, knowledge acquired from the old environment is stored in order to recall it whenever the same state reappears. We illustrate our study by presenting several experiments and compare our results to those of standard algorithms.
Enrique Alba, Hajer Ben-Romdhane, Saoussen Krichen, Briseida Sarasola
Evolutionary Optimization on Continuous Dynamic Constrained Problems - An Analysis
Abstract
Many real-world dynamic problems have constraints, and in certain cases not only the objective function changes over time, but also the constraints. However, there is little research on whether current algorithms work well on continuous dynamic constrained optimization problems (DCOPs). This chapter investigates this issue. The chapter will present some studies on the characteristics that can make DCOPs difficult to solve by some existing dynamic optimization (DO) algorithms. We will then introduce a set of benchmark problems with these characteristics and test several representative DO strategies on these problems. The results confirm that DCOPs do have special characteristics that can significantly affect algorithm performance. Based on the analyses of the results, a list of potential requirements that an algorithm should meet to solve DCOPs effectively will be proposed.
Trung Thanh Nguyen, Xin Yao

Theoretical Analysis

Frontmatter
Theoretical Advances in Evolutionary Dynamic Optimization
Abstract
The field of evolutionary dynamic optimization is concerned with the study and application of evolutionary algorithms to dynamic optimization problems: a significant number of new algorithms have been proposed in recent years that are designed specifically to overcome the limitations faced by traditional algorithms in the dynamic domain. Subsequently, a wealth of empirical studies have been published that evaluate the performance of these algorithms on a variety of benchmark problems. However, very few theoretical results have been obtained during this time. This relative lack of theoretical findings makes it difficult to fully assess the strengths and weaknesses of the individual algorithms. In this chapter we provide a review of theoretical advances in evolutionary dynamic optimization. In particular, we argue the importance of theoretical results, highlight the challenges faced by theoreticians and summarise the work that has been done to date. We subsequently identify relevant directions for future research.
Philipp Rohlfshagen, Per Kristian Lehre, Xin Yao
Analyzing Evolutionary Algorithms for Dynamic Optimization Problems Based on the Dynamical Systems Approach
Abstract
The study of evolutionary algorithms for dynamic optimization problems (DOPs) has attracted a rapidly growing interest in recent years. However, few work has addressed the theory in this domain. In this chapter, we use the exact model (or dynamical systems approach) to describe the standard genetic algorithm as a discrete dynamical system for DOPs. Based on this dynamical system model, we define some properties and classes of DOPs and analyze some DOPs used by researchers in the dynamic evolutionary optimization area. The analysis of DOPs via the dynamical systems approach allows explaining some behaviors observed in experimental results. The theoretical analysis of the properties of well-known DOPs is important to understand the results obtained in experiments and to analyze the similarity of such problems to other DOPs.
Renato Tinós, Shengxiang Yang
Dynamic Fitness Landscape Analysis
Abstract
Solving optimization problems with time varying objective functions by methods of evolutionary computation can be grounded on the theoretical framework of dynamic fitness landscapes. In this chapter, we define such dynamic fitness landscapes and discuss their properties. To this end, analyzing tools for measuring topological and dynamical landscape properties are studied. Based on these landscape measures we obtain an approach for drawing conclusion regarding characteristic features of a given optimization problem. This may allow to address the question of how difficult the problem is for an evolutionary search, and what type of algorithm is most likely to solve it successfully. The methodology is illustrated using a well-known example, the moving peaks.
Hendrik Richter
Dynamics in the Multi-objective Subset Sum: Analysing the Behavior of Population Based Algorithms
Abstract
Real-world problems often present two characteristics that are challenging to examine theoretically: 1) they are dynamic (they change over time), and 2) they have multiple objectives. However, current research in the field of dynamic multi-objective optimization (DMO) is relatively sparse. In this chapter, we review recent work in this field and present our analysis of the subset sum problem in the DMO variant. Our approach uses a genetic algorithm with an external archive and a combination of Pareto dominance and aggregated fitness function.We show that the algorithm performs better on a smaller number of objectives, on type III dynamicity problems, and sometimes, counter-intuitively, on a larger data set.
Iulia Maria Comsa, Crina Grosan, Shengxiang Yang

Applications

Frontmatter
Ant Colony Optimization Algorithms with Immigrants Schemes for the Dynamic Travelling Salesman Problem
Abstract
Ant colony optimization (ACO) algorithms have proved to be powerful methods to address dynamic optimization problems (DOPs). However, once the population converges to a solution and a dynamic change occurs, it is difficult for the population to adapt to the new environment since high levels of pheromone will be generated to a single trail and force the ants to follow it even after a dynamic change. A good solution is to maintain the diversity via transferring knowledge from previous environments to the pheromone trails using immigrants. In this chapter, we investigate ACO algorithms with different immigrants schemes for two types of dynamic travelling salesman problems (DTSPs) with traffic factor, i.e., under random and cyclic dynamic changes. The experimental results based on different DTSP test cases show that the investigated algorithms outperform other peer ACO algorithms and that different immigrants schemes are beneficial on different environmental cases.
Michalis Mavrovouniotis, Shengxiang Yang
Genetic Algorithms for Dynamic Routing Problems in Mobile Ad Hoc Networks
Abstract
Routing plays an important role in various types of networks. There are two main ways to route the packets, i.e., unicast and multicast. In most cases, the unicast routing problem is to find the shortest path between two nodes in the network and the multicast routing problem is to find an optimal tree spanning the source and all the destinations. In recent years, both the shortest path routing and the multicast routing have been well addressed using intelligent optimization techniques. With the advancement in wireless communications, more and more mobile wireless networks appear, e.g., mobile ad hoc networks (MANETs). One of the most important characteristics in MANETs is the topology dynamics, that is, the network topology changes over time due to energy conservation or node mobility. Therefore, both routing problems turn out to be dynamic optimization problems inMANETs. In this chapter, we investigate a series of dynamic genetic algorithms to solve both the dynamic shortest path routing problem and the dynamic multicast routing problem in MANETs. The experimental results show that these specifically designed dynamic genetic algorithms can quickly adapt to environmental changes (i.e., the network topology changes) and produce high quality solutions after each change.
Hui Cheng, Shengxiang Yang
Evolutionary Computation for Dynamic Capacitated Arc Routing Problem
Abstract
In this chapter, a new dynamic capacitated arc routing problem (CARP) is defined and investigated. Compared with the static CARP and other dynamic CARP investigated by the existing researches, the new dynamic CARP is more general and closer to reality, and thus is more worthwhile to be solved. Due to the stochastic factors included in the dynamic CARP, the objective is not to obtain the optimal solution in a specific environment, but to find a robust solution that shows good performance in all the possible environments. For the dynamic CARP, a robustness measure based on repair operator is defined. The corresponding repair operator is designed according to the real-world considerations. Then, the benchmark instances of the dynamic CARP are generated by extending from the static counterparts to facilitate evaluating potential approaches. After that, the preliminary analysis for the fitness landscape of the dynamic CARP is conducted by experimental studies.
Yi Mei, Ke Tang, Xin Yao
Evolutionary Algorithms for the Multiple Unmanned Aerial Combat Vehicles Anti-ground Attack Problem in Dynamic Environments
Abstract
This chapter aims to solve the online path planning (OPP) and dynamic target assignment problems for the multiple unmanned aerial combat vehicles (UCAVs) anti-ground attack task using evolutionary algorithms (EAs). For the OPP problem, a model predictive control framework is adopted to continuously update the environmental information for the planner. A dynamic multi-objective EA with historical Pareto set linkage and prediction is proposed to optimize in the planning horizon. In addition, Bayesian network and fuzzy logic are used to quantify the bias value to each optimization objective so as to intelligently select an executive solution from the Pareto set. For dynamic target assignment, a weapon target assignment model that considers the inner dependence among the targets and the expected damage type is built up. For solving the involved dynamic optimization problems, an environment identification based memory scheme is proposed to enhance the performance of estimation of distribution algorithms. The proposed approaches are validated via simulation with a scenario of suppression of enemy air defense mission.
Xingguang Peng, Shengxiang Yang, Demin Xu, Xiaoguang Gao
Advanced Planning in Vertically Integrated Wine Supply Chains
Abstract
This chapter gives detailed insights into a project for transitioning a wine manufacturing company from a mostly spreadsheet driven business with isolated silo-operated planning units into one that makes use of integrated and optimised decision making by use of modern heuristics. We present a piece of the puzzle - the modelling of business entities and their silo operations and optimizations, and pave the path for a further holistic integration to obtain company-wide globally optimised decisions. We argue that the use of “Computational Intelligence” methods is essential to cater for dynamic, time-variant and non-linear constraints and solve today’s real-world problems exemplified by the given wine supply chain.
Maksud Ibrahimov, Arvind Mohais, Maris Ozols, Sven Schellenberg, Zbigniew Michalewicz
Backmatter
Metadaten
Titel
Evolutionary Computation for Dynamic Optimization Problems
herausgegeben von
Shengxiang Yang
Xin Yao
Copyright-Jahr
2013
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-38416-5
Print ISBN
978-3-642-38415-8
DOI
https://doi.org/10.1007/978-3-642-38416-5

Premium Partner

    Bildnachweise