0.25
0.5
0.75
1.25
1.5
1.75
2
Optimisation
Published on Feb 25, 20074731 Views
It has been a century and a half since Darwin provided the first mechanistic explanation for the complexity of the living things we see around us. Only in the last 30 years or so have computational sy
Related categories
Chapter list
Optimisation00:01
Outline01:20
Evolution and Optimisation01:56
Unintended Consequences03:29
Optimisation05:32
Combinatorial Optimisation Problems08:56
Outline10:18
Travelling Salesperson Problem10:34
Example of Distance Table11:01
Example Tour11:13
Brute Force11:28
How Many Possible Tours Are There?12:24
Counting Tours12:53
Counting Tours12:59
Counting Tours13:13
Counting Tours13:20
How Long Does It Take?13:29
How Big is 99 Factorial?14:02
How Long Does It Take?14:45
Answer15:48
Record TSP Solved—15 112 and 24 978 Cities16:14
Can We Parallelise the Search17:18
Variety of Life18:47
Outline20:36
The Nature of Optimisation Problems20:46
Continuous Search Spaces22:10
Discrete Search Spaces24:23
Shortest Path: Dijkstra’s Algorithm24:45
Polynomial Time Algorithms25:56
NP-Hard Problems26:27
Decision Problems28:33
Class NP30:10
Class NP-complete31:32
Other Examples of NP-complete38:21
Structure of Decision Problems39:04
NP-Hard40:42
Not All Hard Problems are NP-Hard42:04
Not All NP-Hard Problems are Hard43:35
Outline46:48
Heuristic Methods46:54
Heuristics47:59
General Purpose Heuristic Algorithms49:21
Hill-Climbing 50:28
Why is Optimisation Hard?51:19
Local Optima52:55
Multi-Start Hill-Climbers53:52
Simulated Annealing55:10
Stochastic Descent55:40
Simulated Annealing56:22
Cooling Schedule56:54
Convergence Theorem57:34
Conclusions59:30