Designing Evolutionary Algorithms For Dynamic Environments

by Morrison, Ronald W.

• ISBN13: 9783540212317
• ISBN10: 3540212310
• Format: Hardcover
• Copyright: 2004-08-30
• Publisher: Springer-Verlag New York Inc

Summary

The robust capability of Evolutionary Algorithms (EAs) to find solutions to difficult problems has permitted them to become the optimization and search techniques of choice for many practical static problems. Despite this success in many different environments, EAs are often prone to failure when subjected to even small changes in the problem. Effective solutions for many real-world engineering and economic problems require systems that adapt to changes over time. This book addresses the issues involved in the design of EAs that successfully operate in dynamic environments without human intervention, and provides a method for creating EAs for these environments.

Author Biography

Dr. Morrison has been at Mitretek Systems for four years as a Senior Manager and Fellow. He currently serves as an advisor to U.S. government officials regarding advanced software development projects. Previously, Dr. Morrison was Chief Scientist for the SWL division at GRC International, where he was responsible for product development and innovation involving new techniques and applications in the areas of data visualization, computational intelligence, machine learning, and high-speed decision support systems. His accomplishments at GRCI include the creation of a novel genetic-algorithm based decision-support system for commodity traders, development of a method for integrating quantitative and qualitative information for a U.S. government agency, and the framework design for a commercial software-based intelligent agent for use by the Defense Advanced Research Projects Agency. Before joining GRCI, Dr. Morrison was Director of Software Engineering at Hughes Training, Inc., developing high-fidelity, real-time flight simulators for U.S. and foreign military customers. Dr. Morrison has presented multiple papers at major internatinal conferences on Evolutionary Compuation, has served as the Technical Director for the Software Program Manager's Network and is a past member of the Airlie Software Council. He was an invited speaker at the initial meeting of the Narional Software Alliance in 1998 and at the AIE-sponsored Annual Conference on Software Metrics. He holds a B.S. in Aeronautical and Astronautical Engineering from Purdue University, an M.B.A. from Southern Illinois University, and a Ph.D. in Information Technology from George Mason University.

Table of Contents

1 Introduction	1	(12)
1.1 Overview and Background	1	(5)
1.1.1 Overview	1	(1)
1.1.2 EAs Described	2	(4)
1.2 Previous Research	6	(3)
1.2.1 Diversity Introduction and Maintenance	7	(1)
1.2.2 Addition of Memory	8	(1)
1.2.3 Importance of the Characteristics of the Landscape	9	(1)
1.3 Open Research Issues	9	(1)
1.4 Importance and Relevance	10	(1)
1.5 Book Structure	11	(2)
2 Problem Analysis	13	(6)
2.1 Overview	13	(1)
2.2 Non-stationary Problems	13	(1)
2.3 EA Performance in Dynamic Environments	14	(1)
2.4 Algorithm Attributes	15	(2)
2.4.1 Change Detection	15	(2)
2.4.2 Response to Change	17	(1)
2.5 Summary	17	(2)
3 Solutions from Nature and Engineering	19	(6)
3.1 Overview	19	(1)
3.2 Biological Systems	19	(2)
3.2.1 Immunology Background	20	(1)
3.2.2 Application of Immune System Techniques	21	(1)
3.3 Engineering Control Systems	21	(2)
3.3.1 Sliding Mode Control Systems	22	(1)
3.4 Summary	23	(2)
4 Diversity Measurement	25	(28)
4.1 Efficient Diversity Measurement	25	(17)
4.1.1 Overview	25	(1)
4.1.2 Background	26	(3)
4.1.3 Concept Review	29	(1)
4.1.4 A New Method of Computing Population Diversity	30	(1)
4.1.5 Relationship to Diversity Measures in Genotypic Space	31	(3)
4.1.6 Explanation and Example	34	(1)
4.1.7 Computational Efficiency	35	(1)
4.1.8 An Alternative Diversity Computation Method for Binary Genotypic Space	35	(1)
4.1.9 Computing Diversity Measures in Phenotypic Space	36	(1)
4.1.10 Measuring Genotypic Diversity of Non-binary Populations	37	(4)
4.1.11 Section Summary	41	(1)
4.2 Improved Diversity Measurement for Dynamic Problems	42	(10)
4.2.1 Limitations of Current Diversity Measurement Methods	42	(1)
4.2.2 Measurement of Search-Space Coverage	43	(2)
4.2.3 Dispersion Index, Δ Defined	45	(6)
4.2.4 Demonstration and Interpretation of the Dispersion Index	51	(1)
4.3 Summary	52	(1)
5 A New EA for Dynamic Problems	53	(16)
5.1 Overview	53	(1)
5.2 New EA Design Goals	53	(1)
5.2.1 Automatic Detection of and Response to Fitness Landscape Changes	54	(1)
5.2.2 Dispersion Control	54	(1)
5.2.3 Growth Capability for Adaptive Information Exploitation	54	(1)
5.3 New EA Architecture	54	(3)
5.3.1 Combined Change Detection and Dispersion Maintenance	55	(1)
5.3.2 Reduction in Maximum Error	56	(1)
5.3.3 Potential for Adaptive Change Response Using Sentinels	56	(1)
5.4 Sentinel Placement	57	(11)
5.4.1 Overview	57	(1)
5.4.2 Desired Features of a Sentinel Placement Algorithm	58	(1)
5.4.3 The Placement Problem	59	(1)
5.4.4 Heuristic Sentinel Placement	60	(5)
5.4.5 Placement Quality	65	(1)
5.4.6 Sentinel Placement Algorithm in High-Dimension Search Spaces	65	(2)
5.4.7 Recommended Prime Multiplier Values for Dimensions 1 Through 12	67	(1)
5.4.8 Sentinel Placement in Asymmetric Search Spaces	68	(1)
5.5 Summary	68	(1)
6 Experimental Methods	69	(16)
6.1 Overview	69	(1)
6.2 Problem Generator Background	69	(1)
6.3 Generator Requirements	70	(2)
6.3.1 Changing Fitness Peak Heights	70	(1)
6.3.2 Changing Fitness Peak Shapes	70	(1)
6.3.3 Changing Fitness Peak Locations	71	(1)
6.3.4 The Dynamics of Change	71	(1)
6.3.5 Problem Generator Requirements Summary	71	(1)
6.4 Problem Generator Description and Features	72	(6)
6.4.1 Specifying the Morphology	72	(1)
6.4.2 Specifying the Dynamics	73	(3)
6.4.3 Examples	76	(1)
6.4.4 Linear Motion	76	(2)
6.4.5 Changing Cone Shapes	78	(1)
6.4.6 Changing Peak Heights	78	(1)
6.4.7 DF1 Summary	78	(1)
6.5 Test Problem Description	78	(5)
6.5.1 Test Problem Overview	78	(3)
6.5.2 Static Landscape Structures	81	(1)
6.5.3 Dynamic Behavior Applied	81	(2)
6.5.4 Number of Sentinels	83	(1)
6.6 Comparison Experiments	83	(1)
6.7 Special Static Problems	84	(1)
6.8 Summary	84	(1)
7 Performance Measurement	85	(8)
7.1 Overview	85	(1)
7.2 Issues in Performance Measurement	85	(2)
7.3 Requirements for Performance Measurement	87	(1)
7.4 Performance Measurement: Collective Mean Fitness	87	(3)
7.5 Alternative Performance Metrics	90	(1)
7.6 Additional Summary Dynamic Information	91	(1)
7.7 Summary	92	(1)
8 Analysis and Interpretation of Experimental Results	93	(30)
8.1 Introduction	93	(1)
8.2 Overview of the Effect of Sentinels	93	(3)
8.3 Comprehensive Experimental Results	96	(5)
8.3.1 Summary of Collective Fitness Results Using Sentinels	101	(1)
8.4 Overview of Comparison to Other Techniques	101	(3)
8.5 Comparison Analysis and Combined Techniques	104	(3)
8.6 Summary of Top-Performing Techniques	107	(5)
8.7 Relationship Between Collective Fitness and Collective Dispersion	112	(8)
8.8 Important Dispersion Levels for Different Movement Periods	120	(1)
8.9 Summary of Experimental Results	121	(2)
9 Experimental Results for Population Initialization	123	(10)
9.1 Overview	123	(1)
9.2 Background	123	(1)
9.3 Experiment	124	(1)
9.4 Experimental Results	125	(5)
9.5 Analysis	130	(1)
9.6 Summary	130	(3)
10 Summary and Conclusion	133	(6)
10.1 Summary and Review	133	(1)
10.2 Research Results	133	(2)
10.3 Open Issues and Suggested Areas for Future Research	135	(2)
10.3.1 Examination of More Problems	135	(1)
10.3.2 Variable Fitness Landscape Change Periods	135	(1)
10.3.3 Additional Capabilities of Sentinels	135	(1)
10.3.4 Additional Combinations of Techniques	136	(1)
10.3.5 Selection as a Dispersion Mechanism	136	(1)
10.4 Conclusion	137	(2)
Notation	139	(2)
References	141
Index	117