Types of Heuristics Heuristics Often Incorporate Randomization 2 Special Cases of Heuristics Construction methods Must first find a feasible solution and then improve it Improvement Methods Start with a feasible solution and just try to improve it 3 Most Common Heuristic Techniques Genetic Algorithms Simulated Annealing Tabu search New Methods: Particle Swarm optimization etc
Types of Heuristics • Heuristics Often Incorporate Randomization • 2 Special Cases of Heuristics – Construction Methods • Must first find a feasible solution and then improve it. – Improvement Methods • Start with a feasible solution and just try to improve it. • 3 Most Common Heuristic Techniques – Genetic Algorithms – Simulated Annealing – Tabu Search – New Methods: Particle Swarm Optimization, etc…
Origin of Simulated Annealing (SA) Definition: A heuristic technique that mathematically mirrors the cooling of a set of atoms to a state of minimum energy Origin applying the field of statistical mechanics to the field of Combinatorial Optimization (1983) Draws an analogy between the cooling of a material (search for minimum energy state)and the solving of an optimization problem Original Paper Introducing the concept Kirkpatrick, S, Gelatt, C D, and vecchi, M.P., "optimization by simulated Annealing, Science, Volume 220, Number 4598, 13 May 1983, pp 671 680
Origin of Simulated Annealing (SA) • Definition: A heuristic technique that mathematically mirrors the cooling of a set of atoms to a state of minimum energy. • Origin: Applying the field of Statistical Mechanics to the field of Combinatorial Optimization (1983) • Draws an analogy between the cooling of a material (search for minimum energy state) and the solving of an optimization problem. • Original Paper Introducing the Concept – Kirkpatrick, S., Gelatt, C.D., and Vecchi, M.P., “Optimization by Simulated Annealing,” Science, Volume 220, Number 4598, 13 May 1983, pp. 671 680
Statistical mechanics
Statistical Mechanics
The analogy Statistical Mechanics: The behavior of systems with many degrees of freedom in thermal equilibrium at a finite temperature Combinatorial Optimization: Finding the minimum of a given function depending on many variables Analogy: If a liquid material cools and anneals too quickly, then the material will solidify into a sub-optimal configuration. If the liquid material cools slowly, the crystals within the material will solidify optimally into a state of minimum energy (i.e. ground state This ground state corresponds to the minimum of the cost function in an optimization problem
The Analogy • Statistical Mechanics: The behavior of systems with many degrees of freedom in thermal equilibrium at a finite temperature. • Combinatorial Optimization: Finding the minimum of a given function depending on many variables. • Analogy: If a liquid material cools and anneals too quickly, then the material will solidify into a sub-optimal configuration. If the liquid material cools slowly, the crystals within the material will solidify optimally into a state of minimum energy (i.e. ground state). – This ground state corresponds to the minimum of the cost function in an optimization problem
Sample atom Configuration Original Configuration Perturbed Configuration Atom Configuration - Sample Problem Atom Configuration- Sample Problem 5 632 E=13367 E=10904 Energy of original(configuration Perturbing= move a random atom to a new random(unoccupied) slot
Sample Atom Configuration Original Configuration Perturbed Configuration Atom Configuration - Sample Problem Atom Configuration - Sample Problem 7 6 5 4 3 2 1 0 -1 1 2 3 4 -1 0 1 2 3 4 5 6 7 1 3 2 4 -1 0 1 2 3 4 5 6 7 -1 0 1 2 3 4 5 6 7 E=133.67 E=109.04 Energy of original (configuration) Perturbing = move a random atom to a new random (unoccupied) slot