0.25
0.5
0.75
1.25
1.5
1.75
2
Visualisation of Cost Landscapes in Combinatorial Optimisation Problems
Published on Feb 25, 20074567 Views
Understanding the structure of the cost landscape of optimisation problems is important for algorithm design. In this talk, I discuss one approach based on Barrier Trees which captures the structure o
Related categories
Chapter list
Visualisation of Cost Landscapes00:01
Visualisation of Cost Landscapes00:48
Outline01:02
Complex objects02:29
Complex Objects02:40
Complex Objects03:08
Combinatorial Optimisation Problems03:50
Example: Max-Sat05:33
Max-Sat Problems06:59
Machine Learning Example08:37
Separating Plane09:26
Ising Perceptron09:50
Outline11:39
Neighbourhood11:50
Humming Neighbourhood13:24
Hypercube Topology14:52
Other Neighbourhoods15:28
Cost Landscape17:14
Cost Landscape18:00
Costs in the Ising Perceptron18:47
Correctly Classified Region19:35
Increasing the Problem Difficulty20:21
Schematic representation of low a22:06
Schematic representation at higher a23:15
Replica Symmetry Breaking24:06
Schematic representation at higher a24:34
Replica Symmetry Breaking24:45
Easy Phase25:42
Hard Phase26:14
Is this an Accurate Picture?27:02
Outline27:48
Barrier Trees28:10
Example28:41
Discrete Search Spaces30:42
Level Connected Sets31:15
Limitation of Level Connectedness32:05
Level Accessible33:33
Level Accessible Sets35:00
Barrier Trees35:33
Computing Barrier Trees37:12
Outline38:44
MAX-3-SAT a = M/N = 5 N = 1038:49
MAX-3-SAT a = M/N = 5 N = 2040:02
MAX-3-SAT a = M/N = 5 N = 3040:14
MAX-3-SAT a = M/N = 5 N = 4040:25
MAX-3-SAT N = 40 a = M/N = 440:43
MAX-3-SAT N = 40 a = M/N = 640:56
MAX-3-SAT N = 40 a = M/N = 840:59
MAX-3-SAT N = 40 a = M/N = 1041:02
Phase Transition in Number Partitioning41:47
Outline43:46
Mappings Configurations44:00
Mapping Configurations45:02
Max-3-Sat N = 40 a = M/N = 845:46
Statistics46:01
Simulated Annealing 40 Variables47:22
Simulated Annealing 40 Va47:54
Simulated Annealing 40 Variables47:56
Simulated Annealing 40 Variables47:56
Simulated Annealing 40 Variables47:58
Simulated Annealing 40 Variables47:59
Simulated Annealing 40 Variables48:00
Simulated Annealing 40 Variables48:00
Genetic Algorithms 30 Variables48:27
Genetic Algorithms 30 Variables48:30
Genetic Algorithms 30 Variables48:34
Genetic Algorithms 30 Variables48:37
Genetic Algorithms 30 Variables48:41
Outline48:46
Genetic Algorithms 30 Variables48:52
Modelling Optimisation Problems49:27
Schematic of Model Problem50:24
Schematic of Model Problem51:00
Descent: Max-3-Sat51:31
Comparison with True Problem51:59
Frequency of Visiting Configurations53:09
Markov Models53:49
Optimal Schedules54:16
Max-Sat: Annealing Schedules with Where-You-Are55:05
Max-Sat: Annealing Schedules with Best-So-Far56:01
Max-Sat: Mutation Schedule with Where-You-Are56:06
Conclusions56:18
Any Questions?57:00