Transcript AUXILIARY-2007-0003.GeneticProgramming.

Genetic
Programming
Genetic Algorithms
• 1. Randomly initialize a population of
chromosomes.
• 2. While the terminating criteria have not been
satisfied:
– a. Evaluate the fitness of each chromosome:
• i. Construct the phenotype (e.g. simulated robot)
corresponding to the encoded genotype (chromosome).
• ii. Evaluate the phenotype (e.g. measure the simulated
robot’s walking abilities), in order to determine its fitness.
– b. Remove chromosomes with low fitness.
– c. Generate new chromosomes, using certain
selection schemes and genetic operators.
Genetic Algorithms
• Fitness function
• Selection scheme
• Genetic operators
– Crossover
– Mutation
Crossover and mutation.
Agenda
•
•
•
•
•
•
What is Genetic Programming?
Background/History.
Why Genetic Programming?
How Genetic Principles are Applied.
Examples of Genetic Programs.
Future of Genetic Programming.
Genetic Programming
• John Koza, 1992
Please review about
Behavioral systems, Genetic
Algorithms and Genetic
Programming from the book.
Chapters 20, 21, 22, 23.
• Evolve program instead of bitstring
• Lisp program structure is best suited
– Genetic operators can do simple replacements of
sub-trees
– All generated programs can be treated as legal (no
syntax errors)
What is Genetic
Programming(GP)?
ROBOTICS
Machine learning
evolutionary
GP
EP GA
Artificial
Intelligence
ES
Artificial
Intelligence
Genetic
Algorithms
• Most widely used
• Robust
• uses 2 separate spaces
– search space - coded solution (genotype)
– solution space - actual solutions (phenotypes)
Genotypes must
be mapped to
phenotypes
before the
quality or fitness
of each solution
can be evaluated
Evolutionary Strategies
• Like GP no distinction between search and
solution space
• Individuals are represented as real-valued
vectors.
• Simple ES
– one parent and one child
– Child solution generated by randomly mutating
the problem parameters of the parent.
• Susceptible to stagnation at local optima
Evolutionary Strategies
(cont’d)
• Slow to converge to optimal solution
• More advanced ES
– have pools of parents and children
• Unlike GA and GP, ES
– Separates parent individuals from child
individuals
– Selects its parent solutions
deterministically
Evolutionary
Programming
• Resembles ES, developed independently
• Early versions of EP applied to the evolution of transition
table of finite state machines
• One population of solutions, reproduction is by mutation
only
• Like ES operates on the decision variable of the problem
directly (ie Genotype = Phenotype)
• Tournament selection of parents
– better fitness more likely a parent
– children generated until population doubled in size
– everyone evaluated and the half of population with lowest fitness
deleted.
General
Architecture
of
Evolutionary
Algorithms
Genetic Programming
• Specialized form of GA
• Manipulates a very specific type of
solution using modified genetic
operators
• Original application was to design
computer program
• Now applied in alternative areas eg.
Analog Circuits
• Does not make distinction between
search and solution space.
• Solution represented in very specific
hierarchical manner.
Background/History
• By John R. Koza, Stanford
University.
• 1992, Genetic Programming Treatise
- “Genetic Programming. On the
Programming of Computers by
Means of Natural Selection.” - Origin
of GP.
• Combining the idea of machine
learning and evolved tree structures.
Why Genetic
Programming?
• It saves time by freeing the
human from having to design
complex algorithms.
• Not only designing the
algorithms but creating ones that
give optimal solutions.
• Again, Artificial Intelligence.
What Constitutes a Genetic
Program?
• Starts with "What needs to be done"
• Agent figures out "How to do it"
• Produces a computer program - “Breeding Programs”
•
•
•
•
Fitness Test
Code reuse
Architecture Design - Hierarchies
Produce results that are competitive with
human produced results
How are Genetic Principles
Applied?
•
•
•
•
“Breeding” computer programs.
Crossovers.
Mutations.
Fitness testing.
Computer Programs as
Trees
• Infix/Postfix
• (2 + a)*(4 - num)
*
-
+
2
a
4
num
“Breeding” Computer
Programs
Hmm hmm heh.
Hey butthead. Do
computer programs
actually score?
“Breeding” Computer
Programs
• Start off with a large “pool” of random
computer programs.
• Need a way of coming up with the best
solution to the problem using the programs
in the “pool”
• Based on the definition of the problem and
criteria specified in the fitness test,
mutations and crossovers are used to come
up with new programs which will solve the
problem.
The Fitness Test
• Identifying the way of evaluating how
good a given computer program is at
solving the problem at hand.
• How good can a program cope with
its environment.
• Can be measured in many ways, i.e.
error, distance, time, etc…
Fitness Test Criteria
• Time complexity a good criteria.
– i.e. n2 vs. nlogn.
• Accuracy - Values of variables.
• Combinations of criteria may
also be tested.
Mutations in Nature
Properties of mutations
• Ultimate source of genetic variation.
• Radiation, chemicals change genetic
information.
• Causes new genes to be created.
Before:
• One chromosome.
acgtactggctaa
• Asexual.
After:
• Very rare.
acatactggctaa
Genetic Programming
• 1. Randomly generate a combinatorial set of computer programs.
• 2. Perform the following steps iteratively until a termination criterion
is satisfied
– a. Execute each program and assign a fitness value to each individual.
– b. Create a new population with the following steps:
• i. Reproduction: Copy the selected program unchanged to the new
population.
• ii. Crossover: Create a new program by recombining two selected programs
at a random crossover point.
• iii. Mutation: Create a new program by randomly changing a selected
program.
• 3. The best sets of individuals are deemed the optimal solution upon
termination
Mutations in Programs
• Single parental program is probabilistically selected
from the population based on fitness.
• Mutation point randomly chosen.
– the subtree rooted at that point is deleted, and
– a new subtree is grown there using the same random growth
process that was used to generate the initial population.
• Asexual operations (mutation) are typically performed
sparingly:
– with a low probability of,
– probabilistically selected from the population based on fitness.
Crossovers in Nature
•
•
•
Two parental chromosomes exchange
part of their genetic information to create
new hybrid combinations (recombinant).
No loss of genes, but an exchange of
genes between two previous
chromosomes.
No new genes created, preexisting old
ones mixed together.
Crossovers in Programs
• Two parental programs are selected from the population
based on fitness.
• A crossover point is randomly chosen in the first and second
parent.
– The first parent is called receiving
– The second parent is called contributing
• The subtree rooted at the crossover point of the first parent is
deleted
• It is replaced by the subtree from the second parent.
• Crossover is the predominant operation in genetic
programming (and genetic algorithm) research
• It is performed with a high probability (say, 85% to 90%).
Applications of GP in robotics
• Wall-following robot – Koza
– Behaviors of subsumption architecture of Brooks. Evolved a new
behavior.
• Box-moving robot – Mahadevon
• Evolving behavior primitives and arbitrators
– for subsumption architecture
• Motion planning for hexapod – Fukuda, Hoshino, Levy
PSU.
• Evolving communication agents Iba, Ueda.
• Mobile robot motion control – Walker.
– for object tracking
• Soccer
• Car racing
Population sizes
from 100 to 2000
This is a very very small subset of
Lisp
• More functions
• Atom, list, cons, car, cdr, numberp,
arithmetic, relations. Cond.
• Copying example
A very important concept – Lisp does not
distinguish data and programs
Programs in Lisp are trees that are
evaluated (calculated)
Tree-reduction semantics
Lisp allows to define special
languages in itself
• This subset of Lisp was defined for a mobile robot
• You can define similar subsets for a humanoid robot,
robot hand, robot head or robot theatre
As an exercise, you can think about behaviors of all Braitenberg Vehicles
described by such programs
• You can define much more sophisticated
mutations that are based on constraints and in
general on your knowledge and good guesses
(heuristics)
EyeSim simulator allows to simulate robots,
environments and learning strategies together with
no real robot
Evolution here takes
feedback from
simulated environment
(simulated)
In our project with teens
the feedback is from
humans who evaluate the
robot theatre performance
(subjective)
In our previous project
with hexapod the
feedback was from real
measurement in
environment (objective)
Evolution principles are the same
for all evolutionary algorithms.
• Each individual
(Lisp program)
is executed on
the EyeSim
simulator for a
limited number
of program
steps.
• The program
performance is
rated
continually or
when finished.
Sample Problem: Ball Tracking
A single robot is placed at a random position
and orientation in a rectangular driving area
closed by walls.
A colored ball is also placed at a random
position.
Using its camera, the robot has to detect the
ball, drive towards it, and stop close to it.
The robot camera is positioned at an angle
so the robot can see the wall ahead from
any position in the field.
However, the ball is not always visible.
Similar other tasks that we solved:
• Collect cans
• Shoot goal in soccer
• Robot sumo
• Robot fencing
• Find ball in environment
• Drive towards it
• Stop when close to ball
Idea for solving
• In the loop, grab an image and analyze it as
follows:
– Convert the image from RGB to HSV.
– Use the histogram ball detection routine from section
8.6 of the book (this returns a ball position in the range
[0..79] (left.. Right) or no ball and a ball size in pixels
[0..60])
– If the ball height is 20 pixels or more, then stop and
terminate (the robot is close enough to the ball)
– Otherwise
• If no ball is detected or the ball position is less than 20, turn
slowly left.
• If the ball position is between 20 and 40, drive slowly straight
• If the ball position is greater than 40, turn slowly right.
• ColSearch returns the x-position of the ball or -1 if not detected and the ball
height in pixels.
• The statement VWDriveWait following either VWDriveTurn or a
VWDriveStraight command suspends execution driving or rotation of the
requested distance or angle has finished.
The evolution can start from random data or from
good hand-coded solutions from humans
Bear in mind that obj_size and
obj_pose are in fact calls to the
image processing subroutine.
Evolution of tracking behavior
• Koza suggests the following steps for setting up a
genetic programming system:
• 1. Establish an objective.
• 2. Identify the terminals and functions used in the
inductive programs
• 3. Establish the selection scheme and its evolutionary
operations
• 4. Finalize the number of fitness cases
• 5. Determine the fitness function and hence the range of
raw fitness values
• 6. Establish the generation gap G, and the population M
• 7. Finalize all control parameters.
• 8. Execute the Genetic Paradigm.
EyeSim simulator allows to simulate robots,
environments and learning strategies together with no
real robot
Evolution here takes
feedback from
simulated environment
(simulated)
In our project with teens
the feedback is from
humans who evaluate the
robot theatre performance
(subjective)
In our previous project
with hexapod the
feedback was from real
measurement in
environment (objective)
Summary on GP
• Field of study in Machine Learning.
• Created by John Koza in 1992.
• Save time while creating better
programs.
• Based on the principles of genetics.
• Symbolic Regression/Circuit Design.
• Example of using
Genetic Programming
in Robotics
• Use of simulation
Robot’s view and driving path in
EyeSim simulator
Robot
trajectory
You want to
maximize this
fitness function
Fitness grows in next populations
(in general)
Highest
fitness
What are the evolved trajectories of
the robot to meet the ball?
The best trajectory
•
•
•
•
Use of improved GP
Use of parallel processing
Use of FPGA and evolvable hardware
Use of quantum computers in future.
Behavior-Based Systems
• Rodney Brooks, 1986
– Ronald Arkin, 1998
• Instead of single, monolithic program, use a
number of behaviors ( parallel processes)
– Improve changeability
– Utililize emergence
• Each behavior has access to all sensors and
actuators
• Problem: behavior selection
There are now many
variants of behavior-based
robots.
Braitenberg is just one of
them.
Good old-fashioned hierarchical
software architecture for a robot
Modern behavioral software
architecture for a robot
Behavior Selection
• Clearly, we cannot have two different behaviors
in control of actuators
– (e.g. obstacle-avoidance wants to drive left, balldetection wants to drive right)
• Solution 1: Always select one behavior as
active
• Solution 2: Add actuator output of all behaviors,
multiplied with certain coefficients
Behavior Selection
• Remaining problem:
– How to determine which behavior to select or
which coefficients to use
• Solution: ??
• How about using GA to evolve a solution!
Behavior Selection
Parameters
Evolution of
controller
parameters
Direct inputs
camera
Ball
detection
Processed
sensor input
Schema
weighting
Move
to ball
Avoid
obstacles
schemas
Schemas using direct
and processed inputs
Trial result
Single
chromosome
Actuator
output
• Many tools of this type are created
• In this class the projects are about animatronix editor and state
based editor
• Another possibility is to use Artificial Neural Network
• This slide shows hierarchical editor for
subsumption-type architecture
Sample Problem: Ball Tracking
• Problem:
– Find ball in environment
– Drive towards it
– [Stop when close to ball]
• Behavior selection:
– Use NN
– Evolve NN weights using GA
Behavior Selection with NN
and GA
• Fitness function:
fitness = initDist - b_distance();
if (fitness < 0.0) fitness = 0.0;
Both approaches can provide increase in
Fitness function. The problem is how good?
Trajectories found by behavioral
approaches
AI in robotics (first summary)
• Neural Networks
– Learning requires complete test set with correct
results
• Genetic Algorithms
– Evolving solutions based on fitness function can be
used in real robot or in simulation (often easier/faster)
• Genetic Programming
– Requires algorithm coding/interpretation (e.g. Lisp)
• Behavior-Based Systems
– Combining parallel processing approach with
intelligent selection scheme
Other areas - Examples
of Genetic Programs
• 1. Symbolic Regression – the process of discovering:
• the functional form of a target function
• and all of its necessary coefficients,
• or at least an approximation to these.
• 2. Analog circuit design
– Embryo circuit is an initial circuit which is
modified to create a new circuit according
to functionality criteria.
Genetic Programming in the
Future
•
•
•
•
Speculative.
Only been around for 10 years.
Is very successful.
Discovery of new algorithms in
existing projects.
• Can be combined with constructive
induction, LISP-based systems,
evolutionary hardware, neural
networks, fuzzy logic, quantum
logic and many other ideas and
methods.
Mr.
Roboto
End of Show
Hey Butthead.
That kicked ass.
Oh yeah. Hm hm yeah yeah hm.
It sucked.
Shut up Buttmunch.
That sucked.
Sources
•
•
•
•
•
Braunl
Dan Kiely
Ran Shoham
Brent Heigold
CPSC 533, Artificial
Intelligence