�ݺ�ߣ

Evolving Solutions
Machine Learning
Programs that Search for Solutions
Searching Random Points
Recursive Descent / Ascent
Sub-Optimization

Faulty Analogies
Fitness
Genetic Algorithms
Particle Swarm Optimization
Simulated Annealing

Monday, January 14, 13 1

Basic Concepts


Learning ==> Improvement

Some quality is being improved.
There is some measure of good / bad.
There is some way to move toward good.
Change position
Change behavior


Learning ==>
Some quality is being improved.

Implies / Assumes:

There is consensus about good versus bad.

There is some way to measure good / bad.

Give that measure a name: “Fitness”

Analogy to nature and evolution concept.


Searching for Better
Random Search

Randomize values in degrees of freedom.

Compare resulting ﬁtness.

Pick the best results.

And then what?

Recursive Descent / Ascent

Assumes that solution space has a gradient.

Assumes there are minima / maxima.

Seeker:
When do you quit searching?
Inﬁnite Loop versus “Stopping Condition”

Eventually we run out of time / resource / energy.

Complications:

Sometimes “Best” is not well-deﬁned.

The solution space is continuously changing.

The shape (gradient qualities) of space is unknown.

Faulty
Analogs

Evolution
There is some way to measure “fitness”

Fitness is a function of a set of objects
that can vary over individual instances.

Call the objects “genes” to use genetic analogy.

Mutation ==> Changing the values of “genes”.

Sexual Reproduction
==> Merging gene “sequences.”

Next Generation <== keep most fit, cull least fit.

Genetic Algorithm
Define degrees of freedom ==> genes.

Produce first generation with randomized genes.

Evaluate fitness of each individual

Calculate / Run a simulation of environment.

Keep most fit <==> Cull least fit.

Populate the next generation. ( mutate and/or splice )

Repeat until “done”

Note: Real environments change over time.

Main Loop In Smalltalk


Next Generation


Mutation


Degrees Of Freedom


See Also: Java Example
for
Traveling Salesman

http://code.google.com/p/java-traveling-salesman/
source/checkout


Insect (Swarm) Behavior

Swarms search for “food” / Encounter “intruders”
-- mostly random search.

Insects communicate with their buddies.

Their buddies re-direct their paths to gather / ﬁght.


Particle Swarm Optimization
Mixed Analogy: Particle <==> Flying insect.

Particles have “position” in multi-dimensional space.

Assign each particle to a group “swarm” (at random).

After fitness is evaluated, particles move toward the
most fit particle in their swarm.

The most fit particle in the swarm
can stay where it is, ascend, or dither (random move).

Recursive ascent / descent may guide moves
if the space is believed to be reasonably continuous.

http://vimeo.com/17407010


Stopping Conditions
How good is good enough?

Genetic Algorithms and Particle Swarm Optimization
can provide multiple solutions.

Stop when best ﬁtness is no longer improving.

Stop when move method is no longer moving anything.

Stop at some arbitrary limit:

Number of generations.

Time limit.


Simulated Annealing
Concept: Temperature ==> Energy Available.

Energy ==> speed of movement.

Speed == How much change from step to step?

Annealing == Cooling at controlled rate ==>
The allowed change decreases from step to step.

Stopping Condition:

Temperature (Change/Step) goes to zero.

Other stopping conditions may also apply.


�Ҵǳٳ��’s
Experts refuse to say “optimum / optimal / optimized”

No way to verify solution is best possible.

Parameters selected may not cover everything.

Say “sub-optimal” or “satisﬁces” (good enough)

Solution is only good inside your simulation.

Real world is certainly different.

Don’t over-train: Solution may lack ﬂexibility.

Visualization
How do you visualize position in hyperspace?

Assign each degree of freedom to some geometry.

3 degrees (x,y,z) ==> position

2 degrees (angle, angle) ==> orientation of “axis”

additional degrees ==> shape dimensions

Example: Torus (donut) Shape -- 9 shape dimensions

Radius, Eccentricity, Angle (?), r, e, a

frequency of: twist, wave, bulge

http://megaswf.com/serve/


Lessons Learned
I did not and do not expect this to work.
It is just something I always wanted to tinker.

Best ﬁtness for 2007-2008: Stay out of the market!

“When-to-buy” was competing with “when-to-sell”
and producing counter-productive results.
==> Need more complex strategy ==> more parameters.

Very compute intensive (generation takes way too long)
==> Need faster data structure ==> Refactor database.
==> Squeak VM is single-thread ==> Port to Erlang ???
==> Potential GPU application.


�ݺ�ߣ

Genetic algorithms

Recommended

More Related Content

Recently uploaded (20)

Featured (20)

Genetic algorithms