Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Optimization with Meta-HeuristicsQuestion: Can you ever prove that a solution generated using a meta-heuristic is optimal?Answer: Yes, for a minimization problem, if the value of the solution equals a lower bound. Question: If the solution of a meta-heuristic for a minimization problem does not equal the lower bound, does that mean the solution is not optimal?Answer: Not necessarily, you just don’t know.Observation: Developing a good lower bound just as important as developing a good meta-heuristic algorithm.DOE for Meta-HeuristicsQuestion: With all the seeming randomness, and choices of neighborhoods and algorithm parameters, how do you know you have developed a good approach or not?Answer: Design of ExperimentsDOE for Meta-HeuristicsRecall the classic Johnson, et al. simulated annealing algorithm:1. Get an initial solution S.2. Get an initial temperature T > 0.3. While not yet frozen do the following:3.1 Perform the following loop l time.3.1.1 Pick a random neighbor S’ of S.3.1.2 Let = cost(S’) – cost(S)3.1.3 If  <= 0 (downhill move), Set S = S’.3.1.4 If  > 0 (uphill move), Set S = S’ with probability e-/T.3.2 Set T = rT (reduce temperature).4. Return S.What are potential experimental parameters?DOE for Meta-HeuristicsDesign parameters for simulated annealing algorithm include:•Problem instances•Cooling approach•Starting temperature•Number of iterations at temperature•Temperature reduction rate•Termination condition•Variance from Johnson’s classic algorithm•Neighborhoods•Acceptance probability functionDOE for Meta-HeuristicsObtaining Problem Instances:oBenchmark problems•www.palette.ecn.purdue.edu/~uzsoy2/spssm.html•http://w.cba.neu.edu/~msolomon/problems.htm•many othersoProblem generator•How many problems•Size of problem•Problem characteristics (unique for different problem types)Shop Scheduling Benchmark Problems•General Information •C Programs For Problem Generation •Parameter Values For Problem Generation •J//Cmax Problems •J//Lmax Problems •J/2SETS/Cmax Problems •J/2SETS/Lmax Problems •F//Cmax Problems •F//Lmax Problems www.palette.ecn.purdue.edu/~uzsoy2/spssm.htmlDOE for Meta-HeuristicsHow to report results:•Must evaluate to something (solution value – lower bound)•Compare solution versus run time•Compare over some problem generation parameter (due date range)250 Jobs / 50 Machines / 7 Operations0501001502002503001 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45Due Date Range (x103)Lmax - LBVF1min - SA5min - SA10min - SADOE for Meta-HeuristicsHow to report results: different sized problem instances250 Jobs / 50 Machines / 7 Operations0501001502002503001 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45Due Date Range (x103)Lmax - LBVF1min - SA5min - SA10min - SA1000 Jobs / 100 Machines / 7 Operations0501001502002503001 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73Due Date Range (x103)Lm ax - LBVF1min - SA5min - SA10min - SADOE for Meta-HeuristicsHow to report results: Comparison to benchmark problemsVFSA: K=4,S=1.5,B=0.8 Problem Name LB Previous UB (from Uzsoy) UB (best known from Balas)BalasCPU sec.After 5 minAfter 30 minAfter 60 minAfter 120 minBest VFSA r_20_15_1_1_2 1140 1464 1263 175 1299 1275 1275 1244 1244 r_20_15_1_1_3 1182 1501 1304 98 1271 1268 1268 1266 1258 r_20_15_1_1_4 1160 1492 1396 127 1367 1332 1332 1332 1326 r_20_15_1_1_6 1027 1448 1271 145 1229 1229 1229 1222 1208 r_20_15_1_1_8 1127 1552 1459 135 1449 1417 1388 1388 1388 r_20_15_1_2_1 1721 2090 1817 85 1818 1817 1817 1817 1817 r_20_15_1_2_10 1775 2092 1873 39 1873 1873 1873 1873 1873 r_20_15_1_2_5 1925 2181 1949 37 1930 1930 1930 1930 1930 r_20_15_1_2_8 1599 1785 1636 15 1636 1636 1636 1636 1636 r_20_15_1_2_9 1956 2246 2020 37 2020 2020 2020 2020 2020 r_20_15_2_1_1 1785 2165 2000 11 2014 1972 1970 1963 1960 r_20_15_2_1_3 1727 2100 1976 131 1971 1918 1901 1900 1898 r_20_15_2_1_5 1521 1839 1726 121 1697 1690 1684 1684 1683 r_20_15_2_1_7 1575 1957 1908 118 1846 1830 1824 1824 1824 r_20_15_2_1_9 1858 2143 1968 110 1955 1929 1914 1914 1913DOE for Meta-HeuristicsHow to report results:Run Time Performance8 Families0204060801001200 200 400 600Number of JobsRun Time (cpu seconds)ABCSetup ClassDOE for Meta-HeuristicsHow to report results:3 Machines Uncorrelated0.00%5.00%10.00%15.00%20.00%0 0.5 1 1.5 2Server LoadP ercentag e D eviation0123456N um ber of In stan ces SA From Optimum SA From LBTTH From Optimum TTH From LBM-GSS-A2 From LB Solved Optimally4 Machines Uncorrelated0.00%5.00%10.00%15.00%20.00%0 0.5 1 1.5 2Server LoadP e rc e n tag e D e v iatio n0123456N u m b e r o f In sta n c e s SA From Optimum SA From LBTTH From Optimum TTH From LBM-GSS-A2 From LB Solved OptimallyDOE for Meta-HeuristicsIn class assignment: Develop a DOE for the traveling salesman