Exploitation of Linkage Learning in Evolutionary Algorithms (Adaptation, Learning, and Optimization (3))

Optimization problems are ubiquitous in academic research and real-world applications wherever such resources as space, time and cost are limited. Researchers and practitioners need to solve problems fundamental to their daily work which, however, may show a variety of challenging characteristics such as discontinuity, nonlinearity, nonconvexity, and multimodality. It is expected that solving a complex optimization problem itself should easy to use, reliable and efficient to achieve satisfactory solutions. Differential evolution is a recent branch of evolutionary algorithms that is capable of addressing a wide set of complex optimization problems in a relatively uniform and conceptually simple manner. For better performance, the control parameters of differential evolution need to be set appropriately as they have different effects on evolutionary search behaviours for various problems or at different optimization stages of a single problem. The fundamental theme of the book is theoretical study of differential evolution and algorithmic analysis of parameter adaptive schemes. Topics covered in this book include: Theoretical analysis of differential evolution and its control parameters Algorithmic design and comparative analysis of parameter adaptive schemes Scalability analysis of adaptive differential evolution Adaptive differential evolution for multi-objective optimization Incorporation of surrogate model for computationally expensive optimization Application to winner determination in combinatorial auctions of E-Commerce Application to flight route planning in Air Traffic Management Application to transition probability matrix optimization in credit-decision making Cover Page Adaptation, Learning, and Optimization,Volume 3 Title: Exploitation of Linkage Learning in Evolutionary Algorithms ISBN 9783642128332 Preface Contents Part I Linkage and Problem Structures Linkage Structure and Genetic Evolutionary Algorithms Introduction Test Problems Structure Modularity Degree Distribution Hill Climbing and Genetic Algorithm Compositional Gea Joins and Exchanges Mutation and Inter-level Conflict The $\mathcal{J}$ Algorithm Results Specificity Conclusion References Fragment as a Small Evidence of the Building Blocks Existence Introduction Fragment: A Simplified Definition of BBs Fragments and BBs Fragments and Linkage Operations on Fragments Fragment Identification Fragment Composition Experimental Settings and Results Test Problems Measurement Results Discussion and Conclusions References Structure Learning and Optimisation in a Markov Network Based Estimation of Distribution Algorithm Background EDAs and Approaches to Probabilistic Modelling Structure Learning in the DEUM Markov Network EDA How Good Is the Structure? Distribution Estimation Using Markov Networks General Model Fitness Prediction Correlation The Ising Problem and EDAs DEUM LDA Fitness Model Optimisation DEUM-$\mathcal{X}^2$ The Algorithm Fitness Model Optimisation Results EVDEUM Fitness Model Optimisation Results Conclusion References DEUM – A Fully Multivariate EDA Based on Markov Networks Introduction Probabilistic Graphical Models in EDA Bayesian Networks Markov Networks Markov Network Based EDAs Global Markov Property Based EDAs Local Markov Property Based EDAs Fitness Modelling and DEUM Algorithms Fitness Modelling Univariate MFM in DEUM$_pv$ and DEUM$_d$ Multivariate MFM in Is-DEUM Estimating MRF Parameters Sampling Markov Networks A Fully Multivariate General DEUM Algorithm Estimation of Undirected Structure Finding Cliques and Assigning Potentials Sampling New Solution Experimental Results Experimental Setup Results Analysis Conclusion References Part II Model Building and Exploiting Pairwise Interactions Induced Probabilistic Model Building Introduction Predicting Information Gain from Pairwise Interactions Information Gain on Binary Data General Measurement of Module-Wise Interactions Examples Case Study on eCGA Hybridization of eCGA Guided Linear Model Building Test Suite Performance of the Modified eCGA Extended Bayesian Model Building Multi-parent Search Test Samples Model Building Performance Conclusions References ClusterMI: Building Probabilistic Models Using Hierarchical Clustering and Mutual Information Introduction Background ClusterMI: A New Approach to Model Building in EDAs Results Future Work Conclusion References Estimation of Distribution Algorithm Based on Copula Theory Introduction A Brief Introduction to Copula Theory Definitions and Basic Properties Random Variable Generation Motivation Two-Dimensional Copula-EDAs Gaussion Copula-EDAs Archimedean Copula-EDAs High-Dimensional Copula-EDAs High-Dimensional Copula Constructions Copula-EDA Based on Empirical Copula Conclusion References Analyzing the k Most Probable Solutions in EDAs Based on Bayesian Networks Introduction Background Bayesian Networks Learning Bayesian Networks from Data Estimation of Distribution Algorithms Based on Bayesian Networks Abductive Inference and Most Probable Configurations Experimental Framework Problems Measurements Parameter Configuration Analyzing the k MPSs in Trap5 Trap5 Description Experimental Results Analyzing the $k$ MPSs in Gaussian Ising 2D Ising Spin Glass Description Experimental Results Analyzing $k$ MPSs in $\pm J$ Ising $\pm J$ Ising Description Experimental Results Analyzing $k$ MPSs in Max-SAT Max-SAT Description Experimental Results Related Works Conclusions References Part III Applications Protein Structure Prediction Based on HP Model Using an Improved Hybrid EDA Introduction Protein HP Model and EDAs Protein Folding and HP Model Estimation of Distribution Algorithms New Hybrid EDA for Protein Folding Based on HP Model Problem Representation for EDA The Probabilistic Model of EDA The Composite Fitness Function Local Search with Guided Operators Improved Backtracking-Based Repairing Method Backtracking Method Disadvantage of Traditional Backtracking-Based Method The Improved Method Experiments Problem Benchmark Results of the Hybrid EDA for HP Model Results of Comparing Computational Cost Conclusions and Further Work References Sensible Initialization of a Computational Evolution System Using Expert Knowledge for Epistasis Analysis in Human Genetics Introduction Computational Evolution System Solution Representation, Evaluation, and Selection Solution Operators Mutation Operators Population Initialization Data Simulation Experimental Design Results and Discussion Concluding Remarks References Estimating Optimal Stopping Rules in the Multiple Best Choice Problem with Minimal Summarized Rank via the Cross-Entropy Method Introduction The Multiple Best Choice Problem with Minimal Summarized Rank Cross-Entropy Method The Cross-Entropy Method for the Problem Numeric Results Genetic Algorithm Numeric Results of GA Process Conclusions References Author Index Index 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. One major branch of enhancing the performance of evolutionary algorithms is the exploitation of linkage learning. This monograph aims to capture the recent progress of linkage learning, by compiling a series of focused technical chapters to keep abreast of the developments and trends in the area of linkage. In evolutionary algorithms, linkage models the relation between decision variables with the genetic linkage observed in biological systems, and linkage learning connects computational optimization methodologies and natural evolution mechanisms. Exploitation of linkage learning can enable us to design better evolutionary algorithms as well as to potentially gain insight into biological systems. Linkage learning has the potential to become one of the dominant aspects of evolutionary algorithms; research in this area can potentially yield promising results in addressing the scalability issues. The Fundamental Theme Of This Book Is Theoretical Study Of Differential Evolution And Algorithmic Analysis Of Parameter Adaptive Schemes. The Book Offers Real-world Insights Into A Variety Of Large-scale Complex Industrial Applications. pt. 1. Linkage and problem structures pt. 2. Model building and exploiting pt. 3. Applications.