Friday, 2020-02-28 BioInfo Pakistan
Section categories
 Related Subjects [38]This category includes brief overview of all related subjects. Defining BioInformatics [7]In this section we tried to briefly explain what bioinformatics is ? Unviersities [30]This contains information about universities that are offering bioinformatics degree programs. Resources [24]Contains information about bioinformatics resources including databases, tools and techniques. Algorithms [31]This category includes some of the basic algorithms that are usually used by bioinformaticians.
 Our poll Pakistani Student Yes No Total of answers: 0
 Chat Box Only authorized users can post messages
 Statistics Total online: 1 Guests: 1 Users: 0
Home » 2011 » August » 23 » Simulated Annealing
2:43 PM
Simulated Annealing

 Simulated Annealing1. Description:   Simulated annealing is a generalization of a Monte Carlo method for examining the equations of state and frozen states of n-body systems [Metropolis et al. 1953]. The concept is based on the manner in which liquids freeze or metals recrystallize in the process of annealing. In an annealing process a melt, initially at high temperature and disordered, is slowly cooled so that the system at any time is approximately in thermodynamic equilibrium. As cooling proceeds, the system becomes more ordered and approaches a "frozen" ground state at T=0. Hence the process can be thought of as an adiabatic approach to the lowest energy state. If the initial temperature of the system is too low or cooling is done insufficiently slowly the system may become quenched forming defects or freezing out in meta-stable states (ie. trapped in a local minimum energy state).   The original Metropolis scheme was that an initial state of a thermodynamic system was chosen at energy E and temperature T, holding T constant the initial configuration is perturbed and the change in energy dE is computed. If the change in energy is negative the new configuration is accepted. If the change in energy is positive it is accepted with a probability given by the Boltzmann factor exp -(dE/T). This processes is then repeated sufficient times to give good sampling statistics for the current temperature, and then the temperature is decremented and the entire process repeated until a frozen state is achieved at T=0.   By analogy the generalization of this Monte Carlo approach to combinatorial problems is straight forward [Kirkpatrick et al. 1983, Cerny 1985]. The current state of the thermodynamic system is analogous to the current solution to the combinatorial problem, the energy equation for the thermodynamic system is analogous to at the objective function, and ground state is analogous to the global minimum. The major difficulty (art) in implementation of the algorithm is that there is no obvious analogy for the temperature T with respect to a free parameter in the combinatorial problem. Furthermore, avoidance of entrainment in local minima (quenching) is dependent on the "annealing schedule", the choice of initial temperature, how many iterations are performed at each temperature, and how much the temperature is decremented at each step as cooling proceeds.2. Key Points: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 ßà ProblemEnergy State ßà Cost FunctionTemperature ßà Control ParameterA completely ordered crystalline structure ßà the optimal solution for the problemGlobal optimal solution can be achieved as long as the cooling process is slow enough. Metropolis Loop: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:LetX be the current solution and X’ be the new solutionC(x) (C(x’))be the energy state (cost) of x (x’) Probability Paccept  = exp [(C(x)-C(x’))/ T]Let N=Random(0,1)Unconditional accepted ifC(x’) < C(x), the new solution is betterProbably accepted if C(x’) >= C(x), the new solution is worse . Accepted only when N < Paccept3.  Algorithm Structure:4.  Algorithm:Initialize initial solution x , highest temperature Th, and coolest temperature TlT= ThWhen the temperature is higher than Tl    While not in equilibrium  Search for the new solution X’       Accept or reject X’ according to Metropolis Criterion   End   Decrease the temperature TEndDefinition of solutionSearch mechanism, i.e. the definition of a neighborhoodCost-function 5. Control Parameters:Definition of equilibriumCannot yield any significant improvement after certain number of loopsA constant number of loopsAnnealing schedule (i.e. How to reduce the temperature)A constant value, T’ = T - TdA constant scale factor, T’= T * RdA scale factor usually can achieve better performanceTemperature determinationArtificial, without physical significantInitial temperature80-90% acceptance rateFinal temperatureA constant value, i.e., based on the total number of solutions searchedNo improvement during the entire Metropolis loopAcceptance rate falling below a given (small) valueProblem specific and may need to be tuned6. Example:Traveling Salesman Problem (TSP)Given 6 cities and the traveling cost between any two citiesA salesman need to start from city 1 and travel all other cities then back to city 1Minimize the total traveling costSolution RepresentationAn integer list, i.e., (1,4,2,3,6,5)Search MechanismSwap any two integers (except for the first one)(1,4,2,3,6,5) ßà (1,4,3,2,6,5)Cost FunctionTemperatureInitial temperature determinationAround 80% acceptation rate for "bad move”Determine acceptable (Cnew – Cold)  Final temperature determinationStop criteriaSolution space coverage rateAnnealing scheduleConstant number (90% for example)Depending on solution space coverage rate7. Others:Global optimal is possible, but near optimal is practicalParameter TuningAarts, E. and Korst, J. (1989). Simulated Annealing and Boltzmann Machines. John Wiley & Sons. Not easy for parallel implementationRandomly generator
Category: Algorithms | Views: 28516 | Added by: Ansari | Rating: 0.0/0