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

2004 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

Designing Evolutionary Algorithms for Dynamic Environments

verfasst von: Ronald W. Morrison

Verlag: Springer Berlin Heidelberg

Buchreihe : Natural Computing Series

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

The robust capability of evolutionary algorithms (EAs) to find solutions to difficult problems has permitted them to become popular as optimization and search techniques for many industries. Despite the success of EAs, the resultant solutions are often fragile and prone to failure when the problem changes, usually requiring human intervention to keep the EA on track. Since many optimization problems in engineering, finance, and information technology require systems that can adapt to changes over time, it is desirable that EAs be able to respond to changes in the environment on their own. This book provides an analysis of what an EA needs to do to automatically and continuously solve dynamic problems, focusing on detecting changes in the problem environment and responding to those changes. In this book we identify and quantify a key attribute needed to improve the detection and response performance of EAs in dynamic environments. We then create an enhanced EA, designed explicitly to exploit this new understanding. This enhanced EA is shown to have superior performance on some types of problems. Our experiments evaluating this enhanced EA indicate some pre­ viously unknown relationships between performance and diversity that may lead to general methods for improving EAs in dynamic environments. Along the way, several other important design issues are addressed involving com­ putational efficiency, performance measurement, and the testing of EAs in dynamic environments.

Inhaltsverzeichnis

Frontmatter
1. Introduction
Abstract
Evolutionary algorithms (EAs) are heuristic, stochastic search algorithms often used for optimization of complex, multi-dimensional, multi-modal functions, where the actual functional form is not known. EAs are adaptive algorithms in the sense that they accumulate and use information to progressively improve their ability to solve some problem of interest. EAs operate by creating a population of potential solutions to a particular problem and evaluating those solutions directly. The mechanism by which an EA accumulates information regarding the problem of interest is an exact evaluation of the quality of each of the potential solutions, using a problem-specific evaluation method, referred to as the fitness function. Various iterative operations, called genetic operators, then improve the quality of the solution by: (1) successive refinement of the best solutions found, and (2) searching the unexplored solution space to identify promising areas containing solutions better than those found so far. Identification of the appropriate balance of exploitation of the best solutions and further exploration of the solution space have been the focus of much research in the EA community.
Ronald W. Morrison
2. Problem Analysis
Abstract
This chapter will examine the subject of non-stationary problems in general, and help focus the remainder of the book on the problems of interest. Specifically, this chapter will examine the types of non-stationary landscapes and the attributes needed by an EA to be successful in these dynamic environments.
Ronald W. Morrison
3. Solutions from Nature and Engineering
Overview
With an understanding of the problem at hand from the previous chapter, we will now explore a few of the methods used to deal with this type of problem in nature and in engineering. Biological systems include mechanisms for adapting to changing environments. In engineering, control systems must often be designed to respond properly to unexpected control inputs. This chapter explores a few dynamic adaptation techniques used in biological systems and control engineering to examine opportunities for incorporation of their techniques into EA models and theory.
Ronald W. Morrison
4. Diversity Measurement
Abstract
Chapter 1 identified previous EA research in dynamic fitness landscapes where the researchers applied several diversity-increasing techniques, largely following the intuition that a mostly converged population needs to increase its explorative capability to identify a moved optimum. Chapter 2 identified how diversity improves EA performance in dynamic fitness landscapes. Chapter 3 identified examples from biology and engineering where diversity plays a key role in providing satisfactory solutions to dynamic problems. Having established the importance of diversity to the operation of an EA in a dynamic environment, this chapter will address the measurement of population diversity. One of the problems with diversity measurement is that, historically, it has been computationally expensive. The first section of this chapter will address historical methods of measuring diversity, and introduce a mathematical innovation that provides an efficient method for computing the most common population diversity measures. The second section of this chapter will address the shortcomings of the historical measures of diversity as applied to EAs in dynamic fitness landscapes, and will extend the techniques developed in the first section to derive and present a more useful measure of population diversity for dynamic environments called the “dispersion index.”
Ronald W. Morrison
5. A New EA for Dynamic Problems
Overview
Chapter 3 identified possible EA enhancements from nature and engineering that could improve the performance of EAs in dynamic environments. Key to these techniques was the management of diversity. Diversity management was identified as a method for ensuring continued exploration of the search space to identify possible changes. Chapter 4 provided the basis for an improved method for measuring the diversity that is more appropriate to dynamic fitness landscapes: the dispersion index. As discussed in Chap. 1, diversity maintenance has undergone initial investigations in the context of dynamic fitness landscapes; however, the quantification of the amount of diversity needed remains largely unexplored. In this chapter we provide the design details for an enhanced EA that permits us to exploit our new understanding of diversity and dispersion, and quantify the need for dispersion in dynamic fitness landscapes. This new EA is very flexible in controlling the amount of population dispersion at any time in an EA run, and addresses the problem of detecting changes in the fitness landscape. These features permit us to conduct experiments to quantitatively identify diversity needs for different types of dynamic problems.
Ronald W. Morrison
6. Experimental Methods
Overview
In this chapter we will provide the details of the experimental methodology used in this research. The second section of this chapter will provide background regarding dynamic fitness landscape test problem generators. The third section will identify the requirements for a test problem generator in dynamic environments. The fourth section will provide the details of a test problem generator that was developed as part of this research to address the issues identified in the second section and the requirements identified in the third section. The fifth section will describe the details of the test problems examined in this study. The next section will describe experiments used to compare the results of our new technique to previous EA techniques used for dynamic environments. Finally, the last section of this chapter will describe the specific experiments conducted to examine the usefulness of our sentinel placement algorithm for population initialization in EAs working in static environments.
Ronald W. Morrison
7. Performance Measurement
Abstract
To properly report results of the experiments described in Chap. 6, we must first resolve some issues related to EA performance measurement in dynamic environments. In this chapter we will address these problems. First we will describe previously used techniques and examine some problems associated with their use. Next we will describe the desired characteristics of performance measurement metrics for dynamic environments. The next section will present our recommended performance evaluation reporting methods and identify how performance will be reported for our experiments. Then we will provide some alternative metrics for standardized reporting of EA performance in dynamic environments, and, finally, we will provide a method for collecting additional dynamic information about EA performance.
Ronald W. Morrison
8. Analysis and Interpretation of Experimental Results
Abstract
This chapter will present the results of testing the sentinel-based EA described in Chap. 5, along with other techniques, on the dynamic fitness landscape experiments described in Chap. 6. The results of these experiments provide a basis for establishing the effect of the presence of sentinels on the performance of EAs in dynamic environments. Analysis of these experimental results will assist in identification of the attributes of the sentinel-based EA that alter the performance of the EA, and suggest general methods for improving EA performance in dynamic landscapes.
Ronald W. Morrison
9. Experimental Results for Population Initialization
Abstract
In Chap. 5 we suggested that the sentinel placement algorithm that we have developed for our dynamic environment EA might also be useful for population initialization for EAs in static environments. In this chapter, and also in [43], we examine that suggestion by testing a standard EA in a variety of static landscapes using random population initialization and population initialization using the sentinel placement algorithm (referred to as “placed initialization”).
Ronald W. Morrison
10. Summary and Conclusion
Abstract
The goal of this book was to provide an improved understanding of the design of EAs for dynamic environments as a step towards making EAs capable of satisfactory performance on changing problems without the need for human intervention. As such, this research has served to provide a basis for improving the performance of EAs in dynamic environments, first through derivation of a more meaningful measure of diversity for dynamic environments, called dispersion; second through development and implementation of an extension to EAs, based on concepts from biology and other engineering systems, that allows introduction and maintenance of desired population dispersion levels; and finally through experimental demonstration of the relationship between dispersion levels and EA performance in dynamic environments, over a variety of landscape morphologies and dynamics.
Ronald W. Morrison
Backmatter
Metadaten
Titel
Designing Evolutionary Algorithms for Dynamic Environments
verfasst von
Ronald W. Morrison
Copyright-Jahr
2004
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-662-06560-0
Print ISBN
978-3-642-05952-0
DOI
https://doi.org/10.1007/978-3-662-06560-0