Hide Notes 

Slide 1: Motivation Outline hBOA Problems Biasing Experiments Conclusions Using Previous Models to Bias Structural Learning in the Hierarchical BOA M. Hauschild1 1 Missouri M. Pelikan1 K. Sastry2 D.E. Goldberg2 Estimation of Distribution Algorithms Laboratory (MEDAL) Department of Mathematics and Computer Science University of Missouri - St. Louis 2 Illinois Genetic Algorithms Laboratory (ILLiGAL) Department of Industrial and Enterprise Systems Engineering University of Illinois at Urbana-Champaign Genetic and Evolutionary Computation Conference, 2008 M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 2: Motivation Outline hBOA Problems Biasing Experiments Conclusions Motivation In optimization, always looking to solve harder problems hBOA can solve a broad class of problems robustly and fast Scalability isn’t always enough Much work has been done in speeding up hBOA Sporadic Model-Building Parallelization Others M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 3: Motivation Outline hBOA Problems Biasing Experiments Conclusions Motivation Each run of hBOA leaves us with a tremendous amount of information The algorithm decomposes the problem for us This information we get “for free” Use this knowledge to bias our model-building on similar problems Exploit this free information Focus our model-based search to promising regions M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 4: Motivation Outline hBOA Problems Biasing Experiments Conclusions Outline hBOA Test Problems Biasing Model-Building Experiments Probability Coincidence Matrix (PCM) Distance-based bias Conclusions M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 5: Motivation Outline hBOA Problems Biasing Experiments Conclusions hierarchical Bayesian Optimization Algorithm (hBOA) Pelikan, Goldberg, and Cantú-Paz; 2001 Uses Bayesian network with local structures to model solutions Acyclic directed Graph String positions are the nodes Edges represent conditional dependencies Where there is no edge, implicit independence Niching to maintain diversity M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 6: Motivation Outline hBOA Problems Biasing Experiments Conclusions hBOA Two Components Structure Edges determine dependencies Majority of time spent here Parameters Conditional probabilities depending on parents Example - p(Accident|Wet Road, Speed) Network built greedily, one edge at a time Metric punishes complexity M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 7: Motivation Outline hBOA Problems Biasing Experiments Conclusions Test Problems Test Problems Concatenated Trap of Order 5 2D Ising Spin Glass MAXSAT Experiments Biasing using PCM Biasing using Distance metric M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 8: Motivation Outline hBOA Problems Biasing Experiments Conclusions Trap-5 Partition binary string into disjoint groups of 5 bits trap5 (ones) = 5 4 − ones if ones = 5 , otherwise (1) Total fitness is sum of single traps Optimum: String 1111...1 M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 9: Motivation Outline hBOA Problems Biasing Experiments Conclusions 2D Ising Spin Glass Origin in physics Spins arranged on a 2D grid Each spin sj can have two values: +1 or -1 Each connection i, j has a weight Jij . Set of weights specifies one instance. M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 10: Motivation Outline hBOA Problems Biasing Experiments Conclusions 2D Ising Spin Glass Energy is given by... E (C) = i,j si Ji,j sj , (2) Problem is to find the values of the spins so energy is minimized Very hard for most optimization techniques Extremely large number of local optima Decomposition of bounded order is insufficient Solvable in polynomial time by analytical techniques hBOA solves it in polynomial time A deterministic hill-climber(DHC) is used to improve the quality of evaluated solutions M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 11: Motivation Outline hBOA Problems Biasing Experiments Conclusions MAXSAT Find the maximum satisfiable clauses in a propositional logic formula Usually expressed in k-CNF form Logical and of clauses Logical or of literals Clauses of at most length k Example of a 3-CNF with 4 propositions (X4 ∨ X3 ) ∧ (X1 ∨ ¬X2 ) ∧ (¬X4 ∨ X2 ∨ X3 ) (3) M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 12: Motivation Outline hBOA Problems Biasing Experiments Conclusions MAXSAT Can be mapped to many other problems NP-Complete when k > 1 Not much structure in general case Combined graph-coloring Combined depending on parameter p Regular ring lattice (1-p edges) Random graph (p edges) Test under various amounts of structure M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 13: Motivation Outline hBOA Problems Biasing Experiments Conclusions Biasing Model Building Exploit information from previous runs to simplify MB Two approaches Bias MB using a Probability Coincidence Matrix (PCM) Directly gathered from previous runs Bias MB using a distance threshold Prior knowledge of the problem M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 14: Motivation Outline hBOA Problems Biasing Experiments Conclusions Biasing using PCM When hBOA solves a problem, left with a series of models Compute a PCM from these models Pij is probability of an edge between i and j If Pij =.25, 25% of models contain an edge between i and j Do not consider when an edge occurs Some runs more strongly represented Good and bad We can now use PCM to restrict Pij < pmin M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 15: Motivation Outline hBOA Problems Biasing Experiments Conclusions Biasing using PCM Trap-5 1 10 node j 20 30 40 50 10 20 30 node i 40 50 0 2 4 6 8 10 12 10x10 Ising spin glass 0.6 20 2 4 6 8 10 12 2 4 6 8 10 12 node j 40 60 80 100 20 0.4 2 4 6 8 10 12 0.5 0.2 0 40 60 node i 80 100 M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 16: Motivation Outline hBOA Problems Biasing Experiments Conclusions Biasing using distance metric On other problems, define a distance metric Vector Q such that Qi is proportion of dependencies at i distance or shorter Qmax = 1 Corresponds to strength of dependency between variables MAXSAT, MVC, Ising Can now use Q to restrict Qd < qmin M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 17: Motivation Outline hBOA Problems Biasing Experiments Conclusions Biasing Model Building Benefits (of good bias) Model-building becomes faster Less dependencies to examine Increase effectiveness of search Less spurious dependencies Negatives (of poor bias) Slower convergence Larger population Failure to solve the problem M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 18: Motivation Outline hBOA Problems Biasing Experiments Conclusions PCM on Ising Spin Glass Need to learn PCM from sample Show for some pmin , the effects 100 instances of 4 different sizes Cross-validation PCM built from 90 instances, used to solve remaining 10 Repeated 10 times Varied pmin from 0 to maximum value based on computational time M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 19: Motivation Outline hBOA Problems Biasing Experiments Conclusions PCM on Ising Spin Glass 20x20 5 24x24 5 Execution Time Speedup 4 3 2 1 0 0 Execution Time Speedup 4 3 2 1 0 0 5 10 Minimum edge percentage allowed 1 2 Minimum edge percentage allowed 3 28x28 5 Execution Time Speedup 4 3 2 1 0 0 Execution Time Speedup 5 4 3 2 1 0 0 32x32 0.5 1 1.5 Minimum edge percentage allowed 2 0.5 1 1.5 Minimum edge percentage allowed 2 M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 20: Motivation Outline hBOA Problems Biasing Experiments Conclusions PCM on Ising Spin Glass 20x20 35 30 Reduction Factor 24x24 35 30 Reduction Factor 25 20 15 10 5 25 20 15 10 5 0 0 5 Minimum edge percent allowed 10 0 0 1 2 Minimum edge percent allowed 3 28x28 35 30 Reduction Factor 25 20 15 10 5 0 0 0.5 1 1.5 Minimum edge percent allowed 2 Reduction Factor 35 30 25 20 15 10 5 0 0 32x32 0.5 1 1.5 Minimum edge percent allowed 2 M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 21: Motivation Outline hBOA Problems Biasing Experiments Conclusions Distance Bias on Ising Spin Glass 100 instances of 4 different sizes Restrict dependencies by maximum distance allowed From 1 to half the maximum Omitted results for too severe restrictions M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 22: Motivation Outline hBOA Problems Biasing Experiments Conclusions Distance Bias on Ising Spin Glass 16x16 6 Execution Time Speedup Execution Time Speedup 5 4 3 2 1 0 0.2 ←1 ←2 ←3 ←4 ←5 ←6 ←7 ←8 16 → 20x20 6 5 4 3 2 1 0 0.2 ←1 ←3 ←2 ←4 ←5 ←6 ←7 ←8 ←9 ← 10 20 → 0.4 0.6 0.8 1 Original Ratio of Total Dependencies 0.4 0.6 0.8 1 Original Ratio of Total Dependencies 24x24 6 Execution Time Speedup 5 4 3 2 1 0 0.2 ←2 28x28 6 Execution Time Speedup 5 4 3 ←2 ←3 ← ←4 5 ←6 ←7 ←8 ←9 ← 10 ← 11 ← 13 ← 12 ← 14 28 → ←3 ←4 ←5 ←6 ←7 ←8 ←9 ← 10 ← 11 ← 12 24 → 2 1 0 0.2 0.4 0.6 0.8 1 Original Ratio of Total Dependencies 0.4 0.6 0.8 1 Original Ratio of Total Dependencies M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 23: Motivation Outline hBOA Problems Biasing Experiments Conclusions Distance Bias on Ising Spin Glass 16x16 35 30 Reduction Factor Reduction Factor 25 20 15 10 5 0 0.2 ←1 ←2 20x20 35 30 25 20 15 10 5 ← 16 ←4 ←1 ←5 ←6 ←7 ←8 ← 9 ← 10 ←3 ←2 ←3 ←4 ←5 ←6 ←7 8 ← 0.4 0.6 0.8 1 Original Ratio of Total Dependencies 0 0.2 ← 20 0.4 0.6 0.8 1 Original Ratio of Total Dependencies 24x24 35 30 Reduction Factor 25 20 15 10 5 0 0.2 ←4 ←5 ←6 ←7 ←8 ←← 10 9 ←← 12 11 ←2 28x28 35 30 Reduction Factor ←2 ←3 ←4 ←5 ←6 ←7 ←8 ←9 ← 10 ← 11 13 ←←← 14 12 ←3 25 20 15 10 5 ← 24 0.4 0.6 0.8 1 Original Ratio of Total Dependencies 0 0.2 ← 28 0.4 0.6 0.8 1 Original Ratio of Total Dependencies M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 24: Motivation Outline hBOA Problems Biasing Experiments Conclusions Distance Bias on MAXSAT Must define a distance metric Create a graph for each MAXSAT instance Propositions in same clause are connected Distance between any other propositions is shortest path in this graph Combined graph-coloring, 3 levels of structure p = 1, 2−4 , 2−8 100 instances of each type 500 propositions, 3100 clauses Distances from 1 to the maximum M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 25: Motivation Outline hBOA Problems Biasing Experiments Conclusions Distance Bias on MAXSAT p=1 2 Execution Time Speedup Execution Time Speedup 4→ p=2−4 3 2.5 2 1.5 1 0.5 0 0.7 0.8 0.9 1 Original Ratio of Total Dependencies ←5 All → ←3 ←4 1.5 1 5→ All → 0.5 0 0.98 0.99 1 Original Ratio of Total Dependencies p=2−8 3 Execution Time Speedup 2.5 2 1.5 1 0.5 0 0.4 0.6 0.8 1 Original Ratio of Total Dependencies ←3 ←4 ←5 ←6 ←7 All → M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 26: Motivation Outline hBOA Problems Biasing Experiments Conclusions Distance Bias on MAXSAT p=1 2 4→ p=2−4 10 8 6 4 2 ←4 ←3 Reduction Factor 1 5→ All → 0.5 Reduction Factor 1.5 ←5 All → 0 0.98 0.99 1 Original Ratio of Total Dependencies 0 0.7 0.8 0.9 1 Original Ratio of Total Dependencies p=2−8 10 8 6 4 2 0 0.4 ←3 Reduction Factor ←4 ←5 ←6 ←7 All → 0.6 0.8 1 Original Ratio of Total Dependencies M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 27: Motivation Outline hBOA Problems Biasing Experiments Conclusions Conclusions We took some first steps in exploiting previous runs to speed up new runs Leads to speedups from 4-5 on Ising spin glasses to 1.5-2.5 on MAXSAT Can be extended to many other problems Next step is to try and automate process Efficiency enhancements work together Parallelization Hybridization Learning from past runs Evaluation Relaxation Total M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA 50 2 2 1.1 220 Universities of Missouri - St. Louis and Illinois at Urbana-Champaign
Slide 28: Motivation Outline hBOA Problems Biasing Experiments Conclusions Any Questions? M. Hauschild, M. Pelikan, K. Sastry and D. E. Goldberg Using Previous Models to Bias hBOA Universities of Missouri - St. Louis and Illinois at Urbana-Champaign