Lecture 15: Heuristic Methods

15.093: Optimization Methods Lecture 15: Heuristic Methods 1 Outline Slide 1 � Approximation algorithms � Local search methods � Simulated annealing 2 Approximation algorithms � Algorithm H is an �-approximation algorithm for a minimization prob lem with optimal cost Z � , if H runs in polynomial time, and returns a feasible solution with cost ZH : ZH � (1 + �)Z � Slide 2 � For a maximization problem ZH � (1 � �)Z � 2.1 TSP 2.1.1 MST-heuristic � Triangle inequality Slide 3 cij � cik + ckj ; 8 i; k; j � Find a minimum spanning tree with cost ZT � Construct a closed walk that starts at some node, visits all nodes, returns to the original node, and never uses an arc outside the minimal spanning tree � Each arc of the spanning tree is used exactly twice � Total cost of this walk is 2ZT � Because of triangle inequality ZH � 2ZT � But ZT � Z � , hence ZH � 2ZT � 2Z � 1-approximation algorithm 1 Slide 4 2.1.2 Matching heuristic � Find a minimum spanning tree. Let ZT be its cost � Find the set of odd degree nodes. There is an even number of them. Why� � Find the minimum matching among those nodes with cost ZM � Adding spanning tree and minimum matching creates a Eulerian graph, i.e., each node has even degree. Construct a closed walk � Performance ZH � ZT + ZM � Z � + 1�2Z � � 3�2Z � 3 Local search methods � Local Search: replaces current solution with a better solution by slight Slide 5 Slide 6 Slide 7 modi�cation (searching in some neighbourhood) until a local optimal so lution is obtained � Recall the Simplex method 3.1 TSP-2OPT � Two tours are neighbours if one can be obtained from the other by remov Slide 8 ing two edges and introducing two new edges � Each tour has O(n2) neighbours. Search for better solution among its neighbourhood. � Performance of 2-OPT on random Euclidean instances Size N 100 1000 10000 100000 1000000 � Matching 9.5 9.7 9.9 9.9 2OPT 4.5 4.9 5 4.9 2 4.9 Slide 9 3.2 Extensions 4 Extensions � � � � � Iterated Local Search Large neighbourhoods (example 3-OPT) Simulated Annealing Tabu Search Genetic Algorithms 4.1 Large Neighbourhoods � Within a small neighbourhood, the solution may be locally optimal. Maybe by looking at a bigger neighbourhood, we can �nd a better solution. � Increase in computational complexity 4.1.1 TSP Again 3-OPT: Two tours are neighbour if one can be obtained from the other by removing three edges and introducing three new edges Slide 10 Slide 11 Slide 12 3-OPT improves on 2-OPT performance, with corresponding increase in exe cution time. Improvement from 4-OPT turns out to be not that substantial compared to 3-OPT. 5 Simulated Annealing � Allow the possibility of moving to an inferior solution, to avoid being trapped at local optimum � Idea: Use of randomization 3 Slide 13 5.1 Algorithm � Starting at x, select a random neighbour y in the neighbourhood structure with probability qxy X qxy � 0; y2N (x) Slide 14 qxy � 1 � Move to y if c(y) � c(x). � If c(y) � c(x), move to y with probability e�(c(y)�c(x))�T ; stay in x otherwise � T is a positive constant, called temperature 5.2 Convergence � We de�ne a Markov chain. � Under natural conditions, the long run probability of �nding the chain at state x is given by e�c(x)�T A P � c (z )�T with A � z e � If T ! 0, then almost all of the steady state probability is concentrated on states at which c(x) is minimum � But if T is too small, it takes longer to escape from local optimal (accept an inferior move with probability e�(c(y)�c(x))�T ). Hence it takes much Slide 15 longer for the markov chain to converge to the steady state distribution 5.3 Cooling schedules � T (t) � R� log(t). Convergence guaranteed, but known to be slow empiri cally. � Exponential Schedule: T (t) � T (0)an with a � 1 and very close to 1 (a�0.95 or 0.99) commonly used. 4 Slide 16 5.4 Knapsack Problem X X max c x : a x � b; n i�1 i i n i�1 i i xi 2 f0; 1g Let X � (x1; :::; xn) 2 f0; 1gn � Neighbourhood Structure: N (X ) � fY 2 f0; 1gn : d(X; Y ) � 1g. Exactly one entry has been changed Generate random Y � (y1 ; :::; yn): � Choose j uniformly from 1; 2; :::; n. � yi � xi if i 6� j . yj � 1 � xj . � Accept if Pi ai yi � b. 5.4.1 Example � c�(135, � a�(70, � b � X 139, 149, 150, 156, 163, 173, 184, 192, 201, 210, 214, 221, 229, 240) Slide 17 Slide 18 Slide 19 73, 77, 80,82, 87, 90,94, 98, 106, 110, 113, 115, 118, 120) � 750 � � (1; 0; 1; 0; 1; 0; 1; 1; 1; 0; 0; 0; 0; 1; 1), with value 1458 Cooling Schedule: � T0 � 1000 � probability of accepting a downward move is between 0.787 (ci � 240) and 0.874 (ci � 135). � Cooling Schedule: T (t) � �T (t � 1), � � 0:999 � Number of iterations: 1000, 5000 Performance: � 1000 iterations: best solutions obtained in 10 runs vary from 1441 to 1454 � 5000 iterations: best solutions obtained in 10 runs vary from 1448 to 1456. 5 Slide 20 Slide 21