Table of contents for Hierarchical Bayesian optimization algorithm : toward a new generation of evolutionary algorithms / Martin Pelikan.


Bibliographic record and links to related information available from the Library of Congress catalog. Note: Electronic data is machine generated. May be incomplete or contain other coding.


Counter





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 BOA ...............  . ..................... 31
    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 vs. GA 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 Theory ................ 51
         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 Methodology ................................... 124
         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 Methodology .................................    . 132
         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 Methodology ................................... 139
         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





Library of Congress Subject Headings for this publication: Genetic programming (Computer science)Evolutionary programming (Computer science)Genetic algorithms