Sign inSign up
Visualisation of Cost Landscapes in Combinatorial Optimisation Problems thumbnail
Pause
Mute
Subtitles
Playback speed
0.25
0.5
0.75
1
1.25
1.5
1.75
2
Full screen

Visualisation of Cost Landscapes in Combinatorial Optimisation Problems

Published on Feb 25, 20074568 Views

Adam Prügel-Bennett

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

Complex Objects Visualization Workshop 2005 - Koper

Related categories

Data Visualisation

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