
Optimization Techniques Van Laarhoven, Aarts

tarix  30.10.2018  ölçüsü  182 Kb.   #76094 

Scheduling using Simulated Annealing Reference: Devadas, S.; Newton, A.R. Algorithms for hardware allocation in data path synthesis. IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, July 1989, Vol.8, (no.7):76881.
Iterative Improvement 1 General method to solve combinatorial optimization problems Principles: Start with initial configuration Repeatedly search neighborhood and select a neighbor as candidate Evaluate some cost function (or fitness function) and accept candidate if "better"; if not, select another neighbor Stop if quality is sufficiently high, if no improvement can be found or after some fixed time
Iterative Improvement 2 Needed are: A method to generate initial configuration A transition or generation function to find a neighbor as next candidate A cost function An Evaluation Criterion A Stop Criterion
Iterative Improvement 3 Simple Iterative Improvement or Hill Climbing: Candidate is always and only accepted if cost is lower (or fitness is higher) than current configuration Stop when no neighbor with lower cost (higher fitness) can be found Disadvantages: Local optimum as best result Local optimum depends on initial configuration Generally, no upper bound can be established on the number of iterations
Hill climbing
Simulated Annealing
How to cope with disadvantages Repeat algorithm many times with different initial configurations Use information gathered in previous runs Use a more complex Evaluation Criterion that accepts sometimes (randomly) also solutions away from the (local) optimum
Simulated Annealing Use a more complex Evaluation Function: Do sometimes accept candidates with higher cost to escape from local optimum Adapt the parameters of this Evaluation Function during execution Based upon the analogy with the simulation of the annealing of solids
Simulated Annealing
Other Names Monte Carlo Annealing Statistical Cooling Probabilistic Hill Climbing Stochastic Relaxation Probabilistic Exchange Algorithm
Optimization Techniques Mathematical Programming Network Analysis Branch & Bound Genetic Algorithm Simulated Annealing Algorithm Tabu Search
Simulated Annealing What  Exploits an analogy between the annealing process and the search for the optimum in a more general system.
Annealing Process Annealing Process  Raising the temperature up to a very high level (melting temperature, for example), the atoms have a higher energy state and a high possibility to rearrange the crystalline structure.
 Cooling down slowly, the atoms have a lower and lower energy state and a smaller and smaller possibility to rearrange the crystalline structure.
Statistical Mechanics Combinatorial Optimization State {r:} (configuration  a set of atomic position ) weight eE({r:])/K BT  Boltzmann distribution E({r:]): energy of configuration KB: Boltzmann constant T: temperature Low temperature limit ??
Analogy
Simulated Annealing Analogy  Metal Problem
 Energy State Cost Function
 Temperature Control Parameter
 A completely ordered crystalline structure the optimal solution for the problem
Other issues related to simulated annealing Global optimal solution is possible, but near optimal is practical Parameter Tuning  Aarts, E. and Korst, J. (1989). Simulated Annealing and Boltzmann Machines. John Wiley & Sons.
Not easy for parallel implementation, but was implemented. Random generator quality is important
Analogy Slowly cool down a heated solid, so that all particles arrange in the ground energy state At each temperature wait until the solid reaches its thermal equilibrium Probability of being in a state with energy E : Pr { E = E } = 1 / Z(T) . exp (E / kB.T)
E Energy T Temperature kB Boltzmann constant Z(T) Normalization factor (temperature dependant)
Simulation of cooling (Metropolis 1953) At a fixed temperature T : Perturb (randomly) the current state to a new state E is the difference in energy between current and new state If E < 0 (new state is lower), accept new state as current state If E 0 , accept new state with probability Pr (accepted) = exp ( E / kB.T)
Eventually the systems evolves into thermal equilibrium at temperature T ; then the formula mentioned before holds When equilibrium is reached, temperature T can be lowered and the process can be repeated
Simulated Annealing Same algorithm can be used for combinatorial optimization problems: Energy E corresponds to the Cost function C Temperature T corresponds to control parameter c
Pr { configuration = i } = 1/Q(c) . exp (C(i) / c) C Cost c Control parameter Q(c) Normalization factor (not important)
Metropolis Loop Metropolis Loop is the essential characteristic of simulated annealing Determining how to:  randomly explore new solution,
 reject or accept the new solution at a constant temperature T.
Finished until equilibrium is achieved.
Metropolis Criterion Let :  X be the current solution and X’ be the new solution
 C(x) be the energy state (cost) of x
 C(x’) be the energy state of x’
Probability Paccept = exp [(C(x)C(x’))/ T] Let N = Random(0,1) Unconditional accepted if  C(x’) < C(x), the new solution is better
Probably accepted if  C(x’) >= C(x), the new solution is worse .
 Accepted only when N < Paccept
Simulated Annealing Algorithm Initialize:  initial solution x ,
 highest temperature Th,
 and coolest temperature Tl
T= Th When the temperature is higher than Tl Search for the new solution X’ Accept or reject X’ according to Metropolis Criterion End Decrease the temperature T End
Components of Simulated Annealing Definition of solution Search mechanism, i.e. the definition of a neighborhood Costfunction
Control Parameters Definition of equilibrium  Definition is reached when we cannot yield any significant improvement after certain number of loops
 A constant number of loops is assumed to reach the equilibrium
Annealing schedule (i.e. How to reduce the temperature)  A constant value is subtracted to get new temperature, T’ = T  Td
 A constant scale factor is used to get new temperature, T’= T * Rd
 A scale factor usually can achieve better performance
Control Parameters: Temperature Temperature determination:  Artificial, without physical significant
 Initial temperature
 Selected so high that leads to 8090% acceptance rate
 Final temperature
 Final temperature is a constant value, i.e., based on the total number of solutions searched. No improvement during the entire Metropolis loop
 Final temperature when acceptance rate is falling below a given (small) value
Problem specific and may need to be tuned
Example of Simulated Annealing Traveling Salesman Problem (TSP)  Given 6 cities and the traveling cost between any two cities
 A salesman need to start from city 1 and travel all other cities then back to city 1
 Minimize the total traveling cost
Example: SA for traveling salesman Solution representation  An integer list, i.e., (1,4,2,3,6,5)
Search mechanism  Swap any two integers (except for the first one)
 (1,4,2,3,6,5) (1,4,3,2,6,5)
Cost function
Temperature Temperature  Initial temperature determination
 Initial temperature is set at such value that there is around 80% acceptation rate for “bad move”
 Determine acceptable value for (Cnew – Cold)
 Final temperature determination
 Stop criteria
 Solution space coverage rate
Homogeneous Algorithm of Simulated Annealing initialize; REPEAT REPEAT perturb ( config.i config.j, Cij); IF Cij < 0 THEN accept ELSE IF exp(Cij/c) > random[0,1) THEN accept; IF accept THEN update(config.j); UNTIL equilibrium is approached sufficient closely; c := next_lower(c); UNTIL system is frozen or stop criterion is reached
Inhomogeneous Algorithm Previous algorithm is the homogeneous variant: c is kept constant in the inner loop and is only decreased in the outer loop Alternative is the inhomogeneous variant:  There is only one loop;
 c is decreased each time in the loop,
 but only very slightly
Selection of Parameters for Inhomogeneous variants Choose the start value of c so that in the beginning nearly all perturbations are accepted (exploration), but not too big to avoid long run times The function next_lower in the homogeneous variant is generally a simple function to decrease c, e.g. a fixed part (80%) of current c At the end c is so small that only a very small number of the perturbations is accepted (exploitation) If possible, always try to remember explicitly the best solution found so far; the algorithm itself can leave its best solution and not find it again
Markov Chains for use in Simulation Annealing Markov Chain: Sequence of trials where the outcome of each trial depends only on the outcome of the previous one Markov Chain is a set of conditional probabilities: Pij (k1,k) Probability that the outcome of the kth trial is j, when trial k1 is i
Markov Chains for use in Simulation Annealing Markov Chain: Sequence of trials where the outcome of each trial depends only on the outcome of the previous one Markov Chain is a set of conditional probabilities: Pij (k1,k) Probability that the outcome of the kth trial is j, when trial k1 is i Markov Chain is homogeneous when the probabilities do not depend on k
Homogeneous and inhomogeneous Markov Chains in Simulated Annealing When c is kept constant (homogeneous variant), the probabilities do not depend on k and for each c there is one homogeneous Markov Chain When c is not constant (inhomogeneous variant), the probabilities do depend on k and there is one inhomogeneous Markov Chain
Performance of Simulated Annealing SA is a general solution method that is easily applicable to a large number of problems "Tuning" of the parameters (initial c, decrement of c, stop criterion) is relatively easy Generally the quality of the results of SA is good, although it can take a lot of time
Performance of Simulated Annealing Results are generally not reproducible: another run can give a different result SA can leave an optimal solution and not find it again (so try to remember the best solution found so far) Proven to find the optimum under certain conditions; one of these conditions is that you must run forever
Basic Ingredients for S.A. Solution space Neighborhood Structure Cost function Annealing Schedule
Optimization Techniques Mathematical Programming Network Analysis Branch & Bond Genetic Algorithm Simulated Annealing Tabu Search
Tabu Search
Tabu Search What  Neighborhood search + memory
 Neighborhood search
 Memory
 Record the search history – the “tabu list”
 Forbid cycling search
Algorithm of Tabu Search Choose an initial solution X
Find a subset of N(x) the neighbors of X which are not in the tabu list. Find the best one (x’) in set N(x).
If F(x’) > F(x) then set x=x’. Modify the tabu list. If a stopping condition is met then stop, else go to the second step.
Effective Tabu Search Effective Modeling  Neighborhood structure
 Objective function (fitness or cost)
 Example:
 Graph coloring problem:
 Find the minimum number of colors needed such that no two connected nodes share the same color.
Aspiration criteria  The criteria for overruling the tabu constraints and differentiating the preference of among the neighbors
Effective Tabu Search Effective Computing  “Move” may be easier to be stored and computed than a completed solution
 move: the process of constructing of x’ from x
 Computing and storing the fitness difference may be easier than that of the fitness function.
Effective Tabu Search Effective Memory Use  Variable tabu list size
 For a constant size tabu list
 Too long: deteriorate the search results
 Too short: cannot effectively prevent from cycling
 Intensification of the search
 Decrease the tabu list size
 Diversification of the search
 Increase the tabu list size
 Penalize the frequent move or unsatisfied constraints
Eample of Tabu Search A hybrid approach for graph coloring problem  R. Dorne and J.K. Hao, A New Genetic Local Search Algorithm for Graph Coloring, 1998
Problem Given an undirected graph G=(V,E) Determine a partition of V in a minimum number of color classes C1,C2,…,Ck such that for each edge eij, vi and vj are not in the same color class. NPhard
General Approach Transform an optimization problem into a decision problem Genetic Algorithm + Tabu Search  Meaningful crossover
 Using Tabu search for efficient local search
Encoding Individual Cost function  Number of total conflicting nodes
 Conflicting node
 having same color with at least one of its adjacent nodes
Neighborhood (move) definition  Changing the color of a conflicting node
 Special data structures and techniques to improve the efficiency
Implementation Parent Selection Reproduction/Survivor Crossover Operator  Unify independent set (UIS) crossover
 Independent set
 Conflictfree nodes set with the same color
 Try to increase the size of the independent set to improve the performance of the solutions
Unify independent set (UIS) crossover
Implementation of Tabu Search Mutation  With Probability Pw, randomly pick neighbor
 With Probability 1 – Pw, Tabu search
 Tabu search
 Tabu list
 Tabu tenure (the length of the tabu list)
 L = a * Nc + Random(g)
 Nc: Number of conflicted nodes
 a,g: empirical parameters
Summary on Tabu Search Neighbor Search TS prevent being trapped in the local minimum with tabu list TS directs the selection of neighbor TS cannot guarantee the optimal result Sequential Adaptive
Dostları ilə paylaş: 

