Contents

1 From Genetic Variation to Probabilistic Modeling 1

1.1 Black-Box Optimization 1

1.2 Genetic Algorithms 2

1.3 Simulation: Onemax and Population-Wise Uniform Crossover 5

1.4 Population-Wise Uniform Crossover as a Probabilistic Model 7

1.5 Additively Separable Traps and Probabilistic Building-Block Crossover 9

1.6 Building Blocks and Decomposable Problems 11

2 Probabilistic Model-Building Genetic Algorithms 13

2.1 General PMBGA Procedure 13

2.2 Discrete Variables 15

2.2.1 No Interactions 15

2.2.2 Pairwise Interactions 17

2.2.3 Multivariate Interactions 19

2.3 Other Representations 21

2.3.1 Real-Valued Variables 22

2.3.2 Computer Programs 28

3 Bayesian Optimization Algorithm 31

3.1 Description of BOA31

3.2 Bayesian Networks 32

3.3 Learning Bayesian Networks 35

3.3.1 Scoring Metric 36

3.3.2 Search Procedure 38

3.4 Sampling Bayesian Networks 40

3.5 Initial Experiments 42

3.5.1 Test Functions 42

3.5.2 Experimental Methodology 43

3.5.3 BOA Performance 43

3.5.4 BOA vsGA and Hill Climber 46

3.5.5 Discussion 47

4 Scalability Analysis 49

4.1 Time Complexity and the Number of Evaluations 50

4.2 Background of GA Population-Sizing Theory51

4.2.1 Having an Adequate Initial Supply of BBs 51

4.2.2 Deciding Well Between BBs and Their Competitors 52

4.2.3 Genetic Drift 53

4.3 Population Sizing in BOA 56

4.3.1 Road Map to BOA Population-Sizing Model 57

4.3.2 Finding a Proper Model: The Good, the Bad, and the Ugly 57

4.3.3 Assumptions and Notation 59

4.3.4 Edge Additions and the Critical Population Size 60

4.3.5 Block Probabilities After Binary Tournament 63

4.3.6 General Two-Bit Case 65

4.3.7 General Case: Multiple Parents of X1 Exist 72

4.3.8 Getting the Frequencies Right 74

4.3.9 Critical Population Size: Empirical Results 76

4.3.10 Summary of Population Sizing in BOA 78

4.4 Background of GA Time-to-Convergence Theory 79

4.5 Time to Convergence in BOA 80

4.5.1 Uniform Scaling 80

4.5.2 Exponential Scaling 82

4.6 How does BOA Scale Up? 82

4.7 Empirical Verification of BOA Scalability 84

4.7.1 Uniform Scaling 84

4.7.2 Exponential Scaling 87

5 The Challenge of Hierarchical Difficulty 89

5.1 Hierarchical Decomposition 90

5.2 Computer Design, von Neumann, and Three Keys to Hierarchy Success 90

5.3 The Design of Challenging Hierarchical Problems 93

5.3.1 Example: Tobacco Road 93

5.3.2 Hierarchically Decomposable Functions 96

5.3.3 Another Example: Royal Road 97

5.3.4 Yet Another Example: Hierarchical if-and-only-if (HIFF) 99

5.3.5 Hierarchical Traps: The Ultimate Challenge 100

6 Hierarchical Bayesian Optimization Algorithm 105

6.1 Proper Decomposition and Chunking 105

6.1.1 Chunking Revisited 106

6.1.2 Local Structures in Bayesian Networks 107

6.1.3 Default Tables 109

6.1.4 Decision Trees 110

6.1.5 Decision Graphs 111

6.1.6 Bayesian Network with Decision Graphs 112

6.1.7 Bayesian Score for Networks with Decision Graphs 113

6.1.8 BIC for Bayesian Networks with Decision Graphs 114

6.1.9 Decision Graph Construction: Operators on Decision Graphs 114

6.1.10 Constructing Bayesian Networks with Decision Graphs 115

6.2 Preservation of Alternative Candidate Solutions 116

6.2.1 Background of Niching 117

6.2.2 The Method of Choice: Restricted Tournament Replacement 121

6.3 Hierarchical BOA 122

6.4 Experiments 124

6.4.1 Methodology124

6.4.2 Results 124

6.5 Scalability of hBOA on Hierarchical Problems 126

6.6 How Would Other Methods Scale Up? 127

7 Hierarchical BOA in the Real World 131

7.1 Ising Spin Glasses 131

7.1.1 Methodology132

7.1.2 Results 134

7.1.3 Comparison with Other Black-Box Optimizers 135

7.1.4 Comparison with Problem-Specific Methods 136

7.1.5 From 2D to 3D 137

7.2 Maximum Satisfiability (MAXSAT) 139

7.2.1 Methodology139

7.2.2 Other MAXSAT Solvers Included in Comparison 140

7.2.3 Tested Instances 141

7.2.4 Results on Random 3-CNF Satisfiable Instances 142

7.2.5 Results on Combined-Graph Coloring 144

7.2.6 Discussion 144

8 Summary and Conclusions 147

8.1 What Has Been Done 147

8.2 Main Conclusions 149

References 151

Index 163