Adaptive Differential Evolution: A Robust Approach to Multimodal Problem Optimization

✍ Scribed by Zhang, Jingqiao;Zhang, Jingqiao

• Publisher: Springer
• Year: 2009
• Tongue: English
• Leaves: 245
• Category: Library

✦ Synopsis

I ?rst met Jingqiao when he had just commenced his PhD research in evolutionary algorithms with Arthur Sanderson at Rensselaer. Jingqiao's goals then were the investigation and development of a novel class of se- adaptivedi?erentialevolutionalgorithms, later calledJADE. I had remarked to Jingqiao then that Arthur always appreciated strong theoretical foun- tions in his research, so Jingqiao's prior mathematically rigorous work in communications systems would be very useful experience. Later in 2007, whenJingqiaohadcompletedmostofthetheoreticalandinitialexperimental work on JADE, I invited him to spend a year at GE Global Research where he applied his developments to several interesting and important real-world problems. Most evolutionary algorithm conferences usually have their share of in- vative algorithm oriented papers which seek to best the state of the art - gorithms. The best algorithms of a time-frame create a foundation for a new generationof innovativealgorithms, and so on, fostering a meta-evolutionary search for superior evolutionary algorithms. In the past two decades, during whichinterest andresearchin evolutionaryalgorithmshavegrownworldwide by leaps and bounds, engaging the curiosity of researchers and practitioners frommanydiversescienceandtechnologycommunities, developingstand-out algorithms is getting progressively harder.

✦ Table of Contents

Title Page......Page 2
Preface......Page 6
Contents......Page 8
Part I Linkage and Problem Structures......Page 10
Introduction......Page 11
Test Problems......Page 12
Degree Distribution......Page 15
Hill Climbing and Genetic Algorithm......Page 16
Compositional Gea......Page 19
Joins and Exchanges......Page 20
Mutation and Inter-level Conflict......Page 21
The J Algorithm......Page 23
Results......Page 25
Specificity......Page 27
References......Page 29
Introduction......Page 32
Fragment: A Simplified Definition of BBs......Page 34
Fragment Identification......Page 36
Fragment Composition......Page 38
Experimental Settings and Results......Page 39
Test Problems......Page 40
Measurement......Page 41
Results......Page 42
Discussion and Conclusions......Page 47
References......Page 50
Background......Page 52
EDAs and Approaches to Probabilistic Modelling......Page 55
Structure Learning in the DEUM Markov Network EDA......Page 57
How Good Is the Structure?......Page 58
General Model......Page 60
Fitness Prediction Correlation......Page 61
DEUM LDA......Page 62
Fitness Model......Page 63
Optimisation......Page 64
The Algorithm......Page 65
Fitness Model......Page 66
Optimisation Results......Page 67
Fitness Model......Page 69
Optimisation Results......Page 71
Conclusion......Page 72
References......Page 73
DEUM – A Fully Multivariate EDA Based on Markov Networks......Page 77
Introduction......Page 78
Bayesian Networks......Page 79
Markov Networks......Page 80
Global Markov Property Based EDAs......Page 82
Fitness Modelling......Page 83
Univariate MFM in DEUM$_pv$ and DEUM$_d$......Page 84
Multivariate MFM in Is-DEUM......Page 85
A Fully Multivariate General DEUM Algorithm......Page 86
Estimation of Undirected Structure......Page 87
Finding Cliques and Assigning Potentials......Page 88
Sampling New Solution......Page 89
Experimental Results......Page 91
Results......Page 92
Analysis......Page 93
Conclusion......Page 95
References......Page 96
Part II Model Building and Exploiting......Page 100
Introduction......Page 101
Predicting Information Gain from Pairwise Interactions......Page 103
Information Gain on Binary Data......Page 104
General Measurement of Module-Wise Interactions......Page 107
Examples......Page 108
Case Study on eCGA......Page 109
Hybridization of eCGA......Page 111
Guided Linear Model Building......Page 112
Test Suite......Page 113
Performance of the Modified eCGA......Page 115
Extended Bayesian Model Building......Page 116
Multi-parent Search......Page 117
Test Samples......Page 118
Model Building Performance......Page 120
References......Page 124
Introduction......Page 127
Background......Page 128
ClusterMI: A New Approach to Model Building in EDAs......Page 131
Results......Page 133
Future Work......Page 138
Conclusion......Page 139
References......Page 140
Introduction......Page 142
Definitions and Basic Properties......Page 145
Random Variable Generation......Page 146
Motivation......Page 147
Two-Dimensional Copula-EDAs......Page 148
Gaussion Copula-EDAs......Page 149
Archimedean Copula-EDAs......Page 154
High-Dimensional Copula Constructions......Page 156
Copula-EDA Based on Empirical Copula......Page 159
Conclusion......Page 162
References......Page 163
Analyzing the $k$ Most Probable Solutions in EDAs Based on Bayesian Networks......Page 166
Introduction......Page 167
Learning Bayesian Networks from Data......Page 168
Estimation of Distribution Algorithms Based on Bayesian Networks......Page 169
Experimental Framework......Page 170
Measurements......Page 171
Trap5 Description......Page 172
Experimental Results......Page 173
2D Ising Spin Glass Description......Page 177
Experimental Results......Page 178
$\pm J$ Ising Description......Page 180
Experimental Results......Page 181
Max-SAT Description......Page 183
Experimental Results......Page 184
Related Works......Page 186
Conclusions......Page 187
References......Page 189
Part III Applications......Page 193
Introduction......Page 194
Protein Folding and HP Model......Page 196
Estimation of Distribution Algorithms......Page 198
Problem Representation for EDA......Page 200
The Probabilistic Model of EDA......Page 201
The Composite Fitness Function......Page 202
Local Search with Guided Operators......Page 204
Disadvantage of Traditional Backtracking-Based Method......Page 205
The Improved Method......Page 207
Problem Benchmark......Page 208
Results of the Hybrid EDA for HP Model......Page 209
Results of Comparing Computational Cost......Page 211
References......Page 214
Introduction......Page 216
Solution Representation, Evaluation, and Selection......Page 218
Mutation Operators......Page 220
Population Initialization......Page 221
Results and Discussion......Page 222
Concluding Remarks......Page 225
References......Page 226
Introduction......Page 228
The Multiple Best Choice Problem with Minimal Summarized Rank......Page 229
Cross-Entropy Method......Page 231
The Cross-Entropy Method for the Problem......Page 233
Numeric Results......Page 234
Genetic Algorithm......Page 238
Numeric Results of GA Process......Page 240
References......Page 241
Author Index......Page 243
Index......Page 244