Genetic algorithms
0 likes1,292 views
The document discusses various machine learning optimization techniques, including genetic algorithms and particle swarm optimization, emphasizing the importance of fitness measures in guiding solutions toward optimal outcomes. It highlights complications in defining 'best' solutions due to changing environments, the need for stopping conditions in algorithms, and the significance of mutations and genetic principles. Additionally, it touches on visualization techniques for representing complex solution spaces and shares lessons learned from practical applications.
Genetic algorithms
- 1. 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
- 2. Basic Concepts Monday, January 14, 13 2
- 3. 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 Monday, January 14, 13 3
- 4. 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. Monday, January 14, 13 4
- 5. 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. Monday, January 14, 13 5
- 6. 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. Monday, January 14, 13 6
- 7. Faulty Analogs Monday, January 14, 13 7
- 8. Evolution There is some way to measure 鍖tness 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 鍖t, cull least 鍖t. Monday, January 14, 13 8
- 9. Genetic Algorithm De鍖ne degrees of freedom ==> genes. Produce 鍖rst generation with randomized genes. Evaluate 鍖tness of each individual Calculate / Run a simulation of environment. Keep most 鍖t <==> Cull least 鍖t. Populate the next generation. ( mutate and/or splice ) Repeat until done Note: Real environments change over time. Monday, January 14, 13 9
- 10. Main Loop In Smalltalk Monday, January 14, 13 10
- 11. Next Generation Monday, January 14, 13 11
- 12. Mutation Monday, January 14, 13 12
- 13. Degrees Of Freedom Monday, January 14, 13 13
- 14. See Also: Java Example for Traveling Salesman http://code.google.com/p/java-traveling-salesman/ source/checkout Monday, January 14, 13 14
- 15. 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. Monday, January 14, 13 15
- 16. 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 鍖tness is evaluated, particles move toward the most 鍖t particle in their swarm. The most 鍖t 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. Monday, January 14, 13 16
- 18. 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. Monday, January 14, 13 18
- 19. 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. Monday, January 14, 13 19
- 20. 赫看岳界鞄温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. Dont over-train: Solution may lack 鍖exibility. Monday, January 14, 13 20
- 21. 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 Monday, January 14, 13 21
- 23. 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. Monday, January 14, 13 23