Report

Elements of the Heuristic Approach • Representation of the solution space – Vector of Binary values – 0/1 Knapsack, 0/1 IP problems – Vector of discrete values- Location , and assignment problems – Vector of continuous values on a real line – continuous, parameter optimization – Permutation – sequencing, scheduling, TSP • Defining the neighborhood and the neighbors – Flip operator – binary or over a range of numbers (+1 or -1 as in knapsack) – Permutation operator • • • • pair-wise exchange operator Insertion operator 12345 14235 Exchange operator 12345 14325 Inversion operator 123456 154326 1 Elements of the Heuristic Approach • Defining the initial solution – Random or greedy • Choosing the method (algorithm for iterative search) – Off-the shelf or tailor made heuristic – Single-start or multistart (still single but several independent singles) or population (solutions interact with one another) – Strategies for escaping local optima – Balance diversification and intensification of search • Objective function evaluation – Full or partial evaluation – At every iteration or after a set of iterations • Stopping criteria – Number of iterations – Time – Counting the number of non-improving solutions in consecutive iterations. Remember: there is a lot of flexibility in setting up the above. Optimality cannot be proved. All you are looking for is a good solution given the resource (time, money and computing power) 2 constraints Escaping local optimas • Accept nonimproving neighbors – Tabu search and simulated annealing • Iterating with different initial solutions – Multistart local search, greedy randomized adaptive search procedure (GRASP), iterative local search • Changing the neighborhood – Variable neighborhood search • Changing the objective function or the input to the problem in a effort to solve the original problem more effectively. – Guided local search 3 Tabu search – Job-shop Scheduling problems • Single machine, n jobs, minimize total weighted tardiness, a job when started must be completed, N-P hard problem, n! solutions • Completion time Cj • Due date dj • Processing time pj • Weight wj • Release date rj • Tardiness Tj = max (Cj-dj, 0) • Total weighted tardiness = ∑ wj . Tj • The value of the best schedule is also called aspiration criterion • Tabu list = list the swaps for a fixed number of previous moves (usually between 5 and 9 swaps for large problems), too few will result in cycling and too many may be unduly constrained. • Tabu tenure of a move= number of iterations for which a move is forbidden. 4 Problems- Parallel machine flow shop • m machines and n jobs – Machines are in parallel, identical and can process all types of jobs – Ex. 2 machines, 4 jobs Jobs j pj 1 9 2 9 3 12 4 3 dj 10 8 5 28 wj 14 12 1 12 Initial solution 3142 Weighted tardiness 163 =7*1+13*12= 163 3 2 12 1 21 4 9 12 5 Problems- Parallel machine flow shop • m machines and n jobs – Machines are in parallel, identical and can process all types of jobs – Ex. 2 machines, 4 jobs – Each job must flow first on machine 1 then on machine 2 Jobs j pj 1 9 2 9 3 12 4 3 dj 10 8 5 28 wj 14 12 1 12 Initial solution 3142 Weighted tardiness 881 =19*1+23*14+8*12+37*12 3 1 12 2 21 3 12 4 24 33 1 24 4 33 2 36 45 6 Set-covering problems • Applications – – – – – – Airline crew scheduling: Allocate crews to flight segments Political districting Airline scheduling Truck routing Location of warehouses Location of a fire station – Example with Tabu search 7 Simulated Annealing • Based on material science and physics • Annealing: For structural strength of objects made from iron, annealing is a process of heating and then slow cooling to form a strong crystalline structure. • The strength depends on the cooling rate • If the initial temperature is not sufficiently high or the cooling is too fast then imperfections are obtained • SA is an analogous process to the annealing process 8 SA • The objective of SA is to escape local optima and to delay convergence. • SA is a memoryless heuristic approach • Start with an initial solution • At each iteration obtain a neighbor in a random or organized way • Moves that improve the solution are always accepted • Moves that do not improve the solution are accepted using a probability. – By the law of thermodynamics at temperature t, the probability of an increase in energy of magnitude dE is given by P(dE,t)= exp(-dE/kt) Where k is the Boltzmann’s constant For min problems dE = f(current move)-f(last move) For max problem dE = f(lastmove)- f(current move) Keep dE positive 9 SA • The acceptance probability of a non-improving solution is – P(dE,t) > R – Where R is a uniform random number between 0 and 1 – Sometimes R can be fixed at 0.5 • At a given temperature many trials can be explored • As the temperature cools the acceptance probability of a nonimproving solution decreases. • In solving optimization problems let kt = T • In summary, other than the standard design parameters such as neighborhood and initial solution, the two main design parameters are – Cooling schedule – Acceptance probability of non-improving solutions which depends on the initial temperature 10 SA – acceptance probability of non-improving solutions • • • • At high temperature, the acceptance probability is high When T = ∞ all moves are accepted When T ~ 0 no non-improving moves are accepted Note the above decrease in accepting non-improving moves is exponential. • Setting initial temperature – Set very high – accept all moves- high computation cost – Using standard deviation s of the difference between objective function values obtained from preliminary experimentation. • T= cs – c= -3/ln(p) – p= acceptance probability 11 SA – Cooling schedules • Linear – Ti= T0 – ib where i is the iteration number and b is a constant • Geometric – Ti= aTi-1 where a is a constant • Logarithmic – Ti= T0/ln(i) – The cooling rate is very slow but can help to reach global optimum. Computationally intensive • Nonmonotonic – Temp is increased again during the search to encourage diversification. • Adaptive – Dynamic cooling schedule. Adjust based on characteristics of the search landscape • A large number of iterations at low temp and a small number of iterations at high temp 12 SA – stopping criteria • Reaching the final temperature • Achieving a pre-determined number of iterations • Keeping a counter on the number of times a certain percentage of neighbors at each temperature is accepted. 13