Simulated Annealing Petru Eles Department of Computer and Information Science (IDA) Linköpings universitet http://www.ida.liu.se/~petel/ Heuristic Algorithms for Combinatorial Optimization Problems 1 Petru Eles, 2010 Outline ■ Neighborhood Search ■ Greedy Heuristics ■ Simulated Annealing: the Physical Analogy ■ Simulated Annealing Algorithm ■ Theoretical Foundation ■ Simulated Annealing Parameters ■ Generic and Problem Specific Decisions ■ Simulated annealing Examples ❚ Traveling Salesman problem ❚ Hardware/Software Partitioning Heuristic Algorithms for Combinatorial Optimization Problems 2 Simulated Annealing Petru Eles, 2010 Neighborhood Search Move Neighbour Solution Heuristic Algorithms for Combinatorial Optimization Problems 3 Simulated Annealing Petru Eles, 2010 Neighborhood Search ■ Problems: ❚ Moves - How do I get from one Solution to another? ❚ Exploration strategy (you cannot try all alternatives!) - How many neighbors to try out? Move Neighbour - Which neighbor to select? - What sequence of moves to follow? ❚ When to stop? Solution Heuristic Algorithms for Combinatorial Optimization Problems 4 Simulated Annealing Petru Eles, 2010 General Neighborhood Search Strategy ■ neighborhood N(x) of a solution x is a set of solutions that can be reached from x by a simple operation (move). now construct initial solution x ; x = x 0 0 repeat ′ ∈ now Select new, acceptable solution x N(x ) now ′ x = x until stopping criterion met return solution corresponding to the minimum cost function Heuristic Algorithms for Combinatorial Optimization Problems 5 Simulated Annealing Petru Eles, 2010 Greedy Heuristics When is a solution acceptable? now construct initial solution x ; x = x 0 0 repeat ′ ∈ now Select new, acceptable solution x N(x ) now ′ x = x until stopping criterion met return solution corresponding to the minimum cost function Heuristic Algorithms for Combinatorial Optimization Problems 6 Simulated Annealing Petru Eles, 2010 Greedy Heuristics When is a solution acceptable? now construct initial solution x ; x = x 0 0 repeat ′ ∈ now Select new, acceptable solution x N(x ) now ′ x = x until stopping criterion met return solution corresponding to the minimum cost function ■ Greedy heuristics always move from the current solution to the best neighboring solution. Heuristic Algorithms for Combinatorial Optimization Problems 7 Simulated Annealing Petru Eles, 2010 Greedy Heuristics Local optimum Heuristic Algorithms for Combinatorial Optimization Problems 8 Simulated Annealing Petru Eles, 2010 Hill Climbing Local optimum ❚ In order to escape local minima you Global optimum have to allow uphill moves! Heuristic Algorithms for Combinatorial Optimization Problems 9 Simulated Annealing Petru Eles, 2010 Simulated Annealing Strategy ■ SA is based on neighborhood search ■ SA is a strategy which occasionally allows uphill moves. ❚ Uphill moves in SA are applied in a controlled manner Heuristic Algorithms for Combinatorial Optimization Problems 10 Simulated Annealing Petru Eles, 2010