Exploitation of Linkage Learning in Evolutionary Algorithms (eBook)

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

"Protein Structure Prediction Based on HP Model Using an Improved Hybrid EDA (p. 193-194)

Benhui Chen and Jinglu Hu

Abstract. Protein structure prediction (PSP) is one of the most important problems in computational biology. This chapter introduces a novel hybrid Estimation of Distribution Algorithm (EDA) to solve the PSP problem on HP model. Firstly, a composite fitness function containing the information of folding structure core (H-Core) is introduced to replace the traditional fitness function of HP model. The new fitness function is expected to select better individuals for probabilistic model of EDA. Secondly, local search with guided operators is utilized to refine found solutions for improving efficiency of EDA. Thirdly, an improved backtracking-based repairing method is introduced to repair invalid individuals sampled by the probabilistic model of EDA. It can significantly reduce the number of backtracking searching operation and the computational cost for long sequence protein. Experimental results demonstrate that the new method outperforms the basic EDAs method. At the same time, it is very competitive with other existing algorithms for the PSP problem on lattice HP models.

1 Introduction

Protein structure prediction (PSP) is one of the most important problems in computational biology. A protein is a chain of amino acids (also called as residues) that folds into a specific native tertiary structure under certain physiological conditions. Understanding protein structures is vital to determining the function of a protein and its interaction with DNA, RNA and enzyme. The information about its conformation can provide essential information for drug design and protein engineering.

While there are over a million known protein sequences, only a limited number of protein structures are experimentally determined. Hence, prediction of protein structures from protein sequences using computer programs is an important step to unveil proteins’ three dimensional conformation and functions. Because of the complexity of the PSP problem, simplified models like Dill’s HPlattice [17] model have become the major tools for investigating general properties of protein folding. In HP model, 20-letter alphabet of residues is simplified to a two-letter alphabet, namely H (hydrophobic) and P (polar).

Experiments on small protein suggest that the native state of a protein corresponds to a free energy minimum. This hypothesis is widely accepted, and forms the basis for computational prediction of a protein’s conformation from its residue sequence. The problem of finding such a minimum energy configuration has been proved to be NP-complete for the bi-dimensional (2-D) [8] and tri-dimensional (3-D) lattices [4]. Therefore, a deterministic approaches is always not practical for this problem."