Transcript chap4b

Iterative Improvement
Algorithms



For some problems, path to solution is
irrelevant: just want solution
Start with initial state, and change it
iteratively to improve it (find a “best”, or
“minimum” value
Examples:



Finding the optimal way of assigning dates within
n people (match.com problem)
Traveling salesperson problem
Knapsack problem
Calculus approach


If you know the function, can take
derivative: solve derivative = 0
Example: Given fencing of length 100
feet, find dimensions to get maximum
area
Hill-climbing search
(or gradient descent)

Example: Given 20 people, find the optimal
way to distribute $1000 to them to maximize
# of dates they can get




Too much money to one person: that person
might run out of time
Money to other people might not be worthwhile
Goal: Maximize # of dates
For a given allocation of money, try it, then
measure # of dates in 1 day period

Start at a guess, then start hill climbing from there
Hill-climbing in general

Move in direction of increasing value


Drawbacks:



Useful when path to solution is irrelevant
Local maxima
Plateaux
Can get around this some with randomrestart hill climbing
Simulated Annealing


Technique inspired by engineering practice of
cooling liquid
At each iteration make a random move



If position is better than current, do it
Over time, slowly drop “temperature” T
If position is worse, do it with probability P




P becomes smaller as T drops
P = exp(change in value / T)
Eventually, algorithm reverts to hill climbing
Popular in VLSI layout
Genetic Algorithms
(Evolutionary Computing)

Genetic Algorithms used to try to “evolve” the
solution to a problem


Generate prototype solutions called chromosomes
(individuals)
Knapsack problem as example:






http://home.ksp.or.jp/csd/english/ga/gatrial/Ch9_A2_4.ht
ml
All individuals form the population
Generate new individuals by reproduction
Use fitness function to evaluate individuals
Survival of the fittest: population has a fixed size
Individuals with higher fitness are more likely to
reproduce
Reproduction Methods

Mutation



Cross-over




Alter a single gene in the chromosome randomly
to create a new chromosome
Example
Pick a random location within chromosome
New chromosome receives first set of genes from
parent 1, second set from parent 2
Example
Inversion

Reverse the chromsome
Interpretation




Genetic algorithms try to solve a hill
climbing problem
Method is parallelizable
The trick is in how you represent the
chromosome
Tries to avoid local maxima by keeping
many chromosomes at a time
Another Example:
Traveling Sales Person Problem


How to represent a chromosome?
What effects does this have on
crossover and mutation?
TSP

Chromosome: Ordering of city numbers




What can go wrong with crossover?
To fix, use order crossover technique
Take two chromosomes, and take two
random locations to cut



(1 9 2 4 6 5 7 8 3)
p1 = (1 9 2 | 4 6 5 7 | 8 3)
p2 = (4 5 9 | 1 8 7 6 | 2 3)
Goal: preserve as much as possible of the
orderings in the chromosomes
Order Crossover



New p1 will look like:


23918
Drop them into c1 in order


c1 = (x x x | 4 6 5 7 | x x)
To fill in c1, first produce ordered list of cities
from p2, starting after cut, eliminating cities
in c1


p1 = (1 9 2 | 4 6 5 7 | 8 3)
p2 = (4 5 9 | 1 8 7 6 | 2 3)
c1 = (2 3 9 4 6 5 7 1 8)
Do similarly in reverse to obtain

c2 = (3 9 2 1 8 7 6 4 5)
Mutation & Inversion


What can go wrong with mutation?
What is wrong with inversion?
Mutation & Inversion

Redefine mutation as picking two
random spots in path, and swapping



p1 = (1 9 2 4 6 5 7 8 3)
c1 = (1 9 8 4 6 5 7 2 3)
Redefine inversion as picking a random
middle section and reversing:


p1 = (1 9 2 | 4 6 5 7 8 | 3)
c1 = (1 9 2 | 8 7 5 6 4 | 3)