Optimization Through Simulated Annealing And Genetic .

Optimization Through Simulated Annealing AndGenetic AlgorithmsBy Dan Tardiff (With Charles Parker)

My Directed Reading Program Random Number Generation Techniques for simulating distributions Random Walks and their applications Optimization by Monte Carlo Methods(Specifically Simulated Annealing (SA) and GeneticAlgorithms (GA))

Formal Optimization: Given some ”Objective Function” ! " , " Ω Maximize or minimize ! " over admissible or feasible "’s Monte Carlo Methods are often useful for problems of a combinatorial nature, with exponentially large domain. with many local optima, such that even if you can easily find one, finding the global optimum ischallenging.

Example: Traveling Salesman Problem One of the most famous difficult combinatorics problems Find the shortest “tour” of the cities (! 1)! different tours Unsolved Analytically

Background: Markov Chains A sequence of RV’s !" , ! , Ω Such that((!* " - !" /" , ! / , X1 /* ) ((!* " - X1 /* ) 345 Markov Chains which are irreducible and aperiodic will converge over time(regardless of initial distribution) to some unique Stationary Distribution 6, with 4 8 6 / 345 6(-), 4 8 6 / 1

Background: The Metropolis Algorithm Algorithm for simulating some target distribution ! over Ω. Core idea: create a Markov chain whose stationary distribution # is !. Thenwe can sample from ! by running the Markov chain. To do this, make use of rejection sampling. Design a symmetric proposal1(')matrix % (%&' %'& ) and let your acceptance discipline ℎ ,-(1, 1(&)). At each step, starting at 23 Ω, propose some 5 Ω by %. Let 2367 5 withprobability ℎ, and otherwise propose some 5 Ω by % again.

Simulated Annealing Adapted from annealing thermal systems to achieve minimal energy states. To minimize the objective function !, Use the metropolis algorithm to samplefrom the Boltzmann distribution with ! as our energy function:# %&'( * ,- .) By using some symmetric proposal matrix and the acceptance discipline:! 5 ! &67 8 Over time, slowly decrease T. At high temperatures, differences in objectivefunction hardly matter. At low temperatures you tend to move downhill only. Keep track of best result.ℎ 123 1, %&'

Tackling Traveling Salesman: Use metropolis algorithm to simulate Boltzmann distribution over possiblepaths, using the distance of the tour as our energy function. Symmetric Proposal Matrix: PPR: Select two cities in the tour at random, andreverse the path between them.{1,4,2,5,6,3,1}{1,4,3,6,5,2,1} Over time as temperature T decreases, theprobability that the markov chain is in a low energystate increases.!"# %( ( )* ,)

Genetic Algorithms Motivated by populations in nature, basically simulating natural selection Each generation !" is a population over Ω. Each Ω is a “chromosome” representing the genetic makeup of anindividual. The objective function & that we are trying to optimize is interpreted as the“fitness” of an individual. Goal is for the population to become more fit over time.

Parts of a Genetic Algorithm:Genetic Algorithms vary Widely, but generally rely on 3 basic stochasticoperations defined on Ω: Mutation Recombination SelectionOne loop of a genetic algorithm will consist of some applications of these threeoperations.

A Simple Example For GA: “The Knapsack Problem” You are presented with a set of items. Each item has a value and a weight orcost. You have a knapsack that can only hold items totaling less than or equal to acertain weight or cost. What set of items do you put in your knapsack to maximize the value you getto take with you?

Applying GA What is a “Chromosome” in this situation?The set of items you put in your sack. Easily represented as a 01 stringof length 18. What is the ”fitness” of a given chromosome?The sum of the values of the items you put in your sack. (The dot productof the chromosome and the respective values)

How will we define our operations? Mutation: For a single chromosome, flip some bit at random (equivalent torandomly taking an item or putting an item back) to make a mutated version,making sure you don’t exceed the maximum cost. Recombination: Given two chromosomes, create a third by “one pointcrossover.” (again making sure you don’t exceed the maximum cost) e.g.Parent 1: 100110101101000110Parent 2: 010101110010101110Child:100110110010101110 Selection: Remove chromosomes from the population until it to the originalsize. Remove those with lower fitness with a higher probability.

Outline of one possible algorithm: Randomly generate a starting population of admissible 01 strings Loop through N generations. For each generation: Mutate some of the more successful individuals. Add these to the population. Recombine some of the more successful individuals with others. Add their childrento the population. Delete some individuals from the population. Deleting less fit individuals with ahigher probability.

Solved it! (Maybe?) What if you run your algorithm twice and get two different answers? Niching Cooling Schedules Allowing inadmissible states and “Wrong Side of Tracks” algorithms.

Summary:If you encounter challenging optimization problems, with a large domain or manylocal optima, SA and GA1. Are easy to code.2. Are relatively quick to run.3. Give pretty good results.Consider Trying Them!

Simulated Annealing Adapted from annealing thermal systems to achieve minimal energy states. To minimize the objective function !,Use the metropolis algorithm to sample from the Boltzmann distribution with !as our energy function: . “The Knapsack Problem” .