Category: Machine Learning

Population of individuals
Mutation – local search
Cross over – population holds information
Generations – iterations of improvement

GA Skeleton
P0 = initial population of size K
repeat until converged
compute fitness of all exP+
select “most fit” individuals (top half, weighted prab)
pair up individuals, replacing “least fit” individuals
vra crossover/mutiation

Randomized Optimization: mimic
– only points, no structure
– unclear probability distribution

minic: estimating distinations
p(x) = p(x1|x2…xn)p(x2|x3…xn)…p(xn)
x=[x1, x2, x3…xn]

x = {1,…, 100}
f(x) = (x mod 6)2 mod 7 – sin(x)
x = 11

X = R
f(x) = -x4 + 1000×3 – 20×2 + 4x -6

optimization approaches
– generate & test: small input space, complex function
– calculus: function has derivative
– Newtons method
what if assumptions don’t hold?

big input space, complex function, no derivative (or hard to find)
possibly many local oftimg

Randomize optimization

Hill climbing
Guess xe x
repeat
let n = argmax f(n)
Un N(x)
if f(x) > f(x):x = n
else: stop

Thinking of a 5-bit sequence
f(x) = #correct bit
x: 5-bit sequences

PZTTMNIIAOOI
(Randomized optimization)

optimization
input space x
objective function(fitness function) f:x -> r
goal: find xeX s.t. f(x*) = max f(x)
Find the best:

-factory, chemical, process control
-route finding
-root finding
-neural networks
x is weights
minimize error
-decision trees