Sign up Sign in
video 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 2007-02-254574 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 VisualisationData Visualisation

Presentation

Visualisation of Cost Landscapes00:01
Outline01:02
Complex objects02:29
Complex Objects02:40
Combinatorial Optimisation Problems03:50
Example: Max-Sat05:33
Max-Sat Problems06:59
Machine Learning Example08:37
Separating Plane09:26
Ising Perceptron09:50
Neighbourhood11:50
Humming Neighbourhood13:24
Hypercube Topology14:52
Other Neighbourhoods15:28
Cost Landscape17:14
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
Easy Phase25:42
Hard Phase26:14
Is this an Accurate Picture?27:02
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
Computing Barrier Trees37:12
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
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
Genetic Algorithms 30 Variables48:27
Modelling Optimisation Problems49:27
Schematic of Model Problem50:24
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