# Optimization Techniques Van Laarhoven, Aarts

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

• ## What

• Exploits an analogy between the annealing process and the search for the optimum in a more general system.

• ## 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 re-arrange the crystalline structure.
• Cooling down slowly, the atoms have a lower and lower energy state and a smaller and smaller possibility to re-arrange the crystalline structure.

• ## Analogy

• Metal  Problem
• Energy State  Cost Function
• Temperature  Control Parameter
• A completely ordered crystalline structure  the optimal solution for the problem

• ## Parameter Tuning

• Aarts, E. and Korst, J. (1989). Simulated Annealing and Boltzmann Machines. John Wiley & Sons.

• ## Determining how to:

• randomly explore new solution,
• reject or accept the new solution at a constant temperature T.

• ## 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’

• ## 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

• ## Initialize:

• initial solution x ,
• highest temperature Th,
• and coolest temperature Tl

• ## 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

• ## Temperature determination:

• Artificial, without physical significant
• Initial temperature
• Selected so high that leads to 80-90% 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

• ## 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

• ## 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)

• ## 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

• ## Alternative is the inhomogeneous variant:

• There is only one loop;
• c is decreased each time in the loop,
• but only very slightly

• ## What

• Neighborhood search + memory
• Neighborhood search
• Memory
• Record the search history – the “tabu list”
• Forbid cycling 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 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 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

• ## A hybrid approach for graph coloring problem

• R. Dorne and J.K. Hao, A New Genetic Local Search Algorithm for Graph Coloring, 1998

• ## Given an undirected graph G=(V,E)

• V={v1,v2,…,vn}
• E={eij}

• ## Genetic Algorithm + Tabu Search

• Meaningful crossover
• Using Tabu search for efficient local search

• ## Individual

• (Ci1, Ci2, …, Cik)
• ## 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
• ## Cost evaluation

• Special data structures and techniques to improve the efficiency

• Random

• ## Crossover Operator

• Unify independent set (UIS) crossover
• Independent set
• Conflict-free nodes set with the same color
• Try to increase the size of the independent set to improve the performance of the solutions

• ## Mutation

• With Probability Pw, randomly pick neighbor
• With Probability 1 – Pw, Tabu search
• Tabu search
• Tabu list
• List of {Vi, cj}
• Tabu tenure (the length of the tabu list)
• L = a * Nc + Random(g)
• Nc: Number of conflicted nodes
• a,g: empirical parameters

• ## Sequential

Yüklə 182 Kb.

Dostları ilə paylaş:

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2022
rəhbərliyinə müraciət

Ana səhifə