Adaptive Differential Evolution | springerprofessional.de

Springer Professional

nach oben

2009 | Buch

Kapitel lesen Erstes Kapitel lesen

Adaptive Differential Evolution

A Robust Approach to Multimodal Problem Optimization

verfasst von: Jingqiao Zhang, Arthur C. Sanderson

Verlag: Springer Berlin Heidelberg

Buchreihe : Adaptation, Learning, and Optimization

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

Einloggen, um Zugang zu erhalten

Anzeige

Inhaltsverzeichnis

Frontmatter

Introduction

Abstract

Optimization problems are ubiquitous in academic research and real-world applications such as in engineering, finance, and scientific areas. What coefficients of a neural network minimize classification errors? What combination of bids maximizes the outcome in an auction? What variable- and check-node distributions optimize a low-density parity-check code design? In general, optimization problems arise wherever such resources as space, time and cost are limited. With no doubt, researchers and practitioners need an efficient and robust optimization approach to solve problems of different characteristics that are fundamental to their daily work.

Jingqiao Zhang, Arthur C. Sanderson

Related Work and Background

Abstract

This chapter introduces background information on several topics. First, the basic concepts of evolutionary algorithms are overviewed in Sect. 2.1. The procedure of classic differential evolution is then described in Sect. 2.2 to serve as a basis for theoretical analysis and algorithm development in later chapters. Different parameter control mechanisms are summarized in Sect. 2.3.Multi-objective optimization is introduced in Sect. 2.4 as an application domain of parameter adaptive differential evolution. Finally, the no-free lunch theory and domain knowledge utilization are briefly discussed in Sect. 2.5.

Jingqiao Zhang, Arthur C. Sanderson

Theoretical Analysis of Differential Evolution

Abstract

Differential evolution has proven to be a simple yet efficient optimization approach since its invention by Storn and Price in 1995 [1], [2]. Despite its success in various practical applications, only a few theoretical results [2], [13], [14], [15] have been obtained concerning its stochastic behavior and most of them focus on the mutation and crossover operations while omitting detailed analysis of selection that is immediately related to objective function values and characteristics. The control parameters of DE, both the mutation factor and the crossover probability, are sensitive to the characteristics of different problems and the varied landscapes of a single problem at different evolutionary search stages. Thus, it is necessary to consider the selection operation in investigating the effect of control parameters on the stochastic convergence behavior of differential evolution.

Jingqiao Zhang, Arthur C. Sanderson

Parameter Adaptive Differential Evolution

Abstract

The performance of differential evolution is affected by its control parameters which in turn are dependent on the landscape characteristics of the objective function.As is clear from extensive experimental studies and theoretical analysis of simple spherical functions, inappropriate control parameter settings may lead to false or slow convergence and therefore degrade the optimization performance of the algorithm. To address this problem, one method is to automatically update control parameters based on the feedback from the evolutionary search. As better parameter values tend to generate offspring that are more likely to survive, parameter adaptation schemes usually follow the principle of propagating parameter values that have produced successful offspring solutions.

Jingqiao Zhang, Arthur C. Sanderson

Surrogate Model-Based Differential Evolution

Abstract

In many practical applications, optimization problems have a demanding limitation on the number of function evaluations that are expensive in terms of time, cost and/or other limited resources. Adaptive differential evolution such as JADE is capable of speeding up the evolutionary search by automatically evolving control parameters to appropriate values. However, as a population-based method by nature, adaptive differential evolution still typically requires a great number of function evaluations, which is a challenge for the increasing computational cost of today’s applications. In general, computational cost increases with the size, complexity and fidelity of the problem model and the large number of function evaluations involved in the optimization process may be cost prohibitive or impractical without high performance computing resources. One promising way to significantly relieve this problem is to utilize computationally cheap surrogate models (i.e., approximate models to the original function) in the evolutionary computation.

In this chapter, JADE is extended to address optimization problems with expensive function evaluations by incorporating computationally inexpensive surrogate models and adaptively controlling the level of incorporation according to model accuracy. Radial basis function networks are used to create the surrogate models for the sake of good balance between computational complexity and model accuracy. Experimental results have shown the efficiency of adaptive incorporation of surrogate models in avoiding potential false or premature convergence while significantly reducing the number of original expensive function evaluations.

Jingqiao Zhang, Arthur C. Sanderson

Adaptive Multi-objective Differential Evolution

Abstract

Multi-objective optimization exists everywhere in real-world applications such as engineering, financial, and scientific applications, because the outcome is directly linked to cost, profit and/or many other criteria that have heavy impacts on performance, safety, environment, etc. It is difficult to provide an ultimate comparison among different outcomes via only one dimension, as the involved multiple criteria/ objectives are generally competing and non-commensurable. For example, a financial manager needs to take both return and risk into consideration when making an investment decision; an air traffic controller needs to consider both the reduction of system-level airspace congestion and the satisfaction of different stakeholders’ preferences.

In this chapter, we investigate the application of parameter adaptive differential evolution to multi-objective optimization problems. To address the challenges in multi-objective optimization, we create an archive to store recently explored inferior solutions whose difference with the current population is utilized as direction information about the optimum, and consider a fairness measure in calculating crowding distances to prefer the solutions whose distances to the nearest neighbors are large and close to be uniform. As a result, the obtained solutions can spread well over the computed non-dominated front and the front can be moved fast toward the Paretooptimal front. The control parameters of the algorithm are adjusted in an adaptive manner, avoiding parameter tuning for problems of different characteristics.

Jingqiao Zhang, Arthur C. Sanderson

Application to Winner Determination Problems in Combinatorial Auctions

Abstract

The crucial idea behind DE is the scheme of generating mutant vectors using the weighted difference of other vectors randomly chosen from the population. This mutation operation relies on arithmetic operations (add, subtract, multiply, etc.) rather than general data manipulation operations (sort, swap, permute, etc.). It cannot be directly extended to the discrete combinatorial space.

In this chapter, we apply parameter adaptive differential evolution to a seminal combinatorial optimization problem of winner determination in Combinatorial Auctions (CAs). To adapt JADE to this problem, we use a rank-based representation scheme that produces only feasible solutions and a regeneration operation that constricts the search space. It is shown that JADE compares favorably to the classic DE algorithm, a local stochastic search algorithm Casanova, and a genetic algorithm based approach SGA.

Jingqiao Zhang, Arthur C. Sanderson

Application to Flight Planning in Air Traffic Control Systems

Abstract

Multi-objective optimization arises commonly in real-world applications such as automation controls, financial and scientific applications. In such an application, the outcome may be directly linked to cost, profit and/or many other inevitably conflicting criteria that have heavy impacts on the overall performance. An air traffic control system is such an example. In flight planning, air traffic controllers need to take into account different performance metrics or optimization objectives such as total flight distances, departure and arrival delays, system-level airspace congestion, stakeholders’ preferences, etc.

In this chapter, we formulate the flight planning in air traffic control systems as a multi-objective optimization problem. While the original problem usually involves hundreds and thousands of decision variables, domain knowledge can be leveraged to remarkably reduce the dimension and therefore the complexity of the problem. The parameter adaptive differential evolution algorithm is then applied to the optimization problem and its performance is compared to other state-of-the-art algorithm.

Jingqiao Zhang, Arthur C. Sanderson

Application to the TPM Optimization in Credit Decision Making

Abstract

Statistical transition probability matrices (TPMs), which indicate the likelihood of obligor’s credit rating migrating from one state to another over a given time horizon, have been used in various credit decision-making applications. Empirical TPMs calculated from historical data generally do not satisfy desired properties. An alternative method is to formulate the problem into an optimization framework [165], i.e., to find an optimized TPM that, when projected into the future based on Markov and time-homogeneity assumptions, can minimize the discrepancy from empirical TPMs. The desired properties can be explicitly modeled as the constraints of the optimization problem.

This TPM optimization problem is high dimensional, non-convex, and nonseparable and is not effectively solved by nonlinear programming methods. It however can be well addressed by the proposed parameter adaptive DE algorithm where domain knowledge can be efficiently utilized to improve performance. In this chapter, we apply the proposed algorithm to this TPM optimization problem and compare its performance to a set of competitive algorithms.

Jingqiao Zhang, Arthur C. Sanderson

Conclusions and Future Work

Abstract

This final chapter presents a summary of conclusions and directions for future research.

Jingqiao Zhang, Arthur C. Sanderson

Backmatter

Titel: Adaptive Differential Evolution
verfasst von: Jingqiao Zhang
Arthur C. Sanderson
Copyright-Jahr: 2009
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-01527-4
Print ISBN: 978-3-642-01526-7
DOI: https://doi.org/10.1007/978-3-642-01527-4

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

Weitere Formate
Fachgebiete
Bücher
Zeitschriften
Themenseiten
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024