Transcript Genetic Programming

Genetic Algorithms
Learning Machines for
knowledge discovery
Finding Patterns in Data

Data mining is the task of
digging through this data
looking for patterns,
associations or
predictions and which
transform that raw
material into useful
information.

Evolutionary algorithms
evolve the patterns which
fit the data using
Darwinian principles to
weed out the patterns
which don't work in favor
of those that do. Survival
of the fittest ensures that
over time it is the patterns
which best fit the raw data
that are delivered as
solutions.
Concept Hierarchy





All Knowledge
Computer Science
Artificial Intelligence
Evolutionary Computation
Evolutionary Algorithms

Genetic Algorithms
 Genetic Programming
Human Knowledge
Math
Logic
Language
Physics
Biology
Computer Science
Graphics
Artificial Intelligence
Natural Language
Evolutionary Computation
Evolutionary Algorithms
Genetic Algorithms
Databases
Networking
Expert Systems
Swarm Intelligence
Genetic Programming
Terminology

Algorithm


Evolution


A finite set of rules (a procedure) that solves a
problem
A series of changes in a population over time affected
by biological, chemical, environmental, and technical
factors
Evolutionary Algorithm

An algorithm that uses selection, crossover and
mutation to produce better and better results
Genetic Algorithms





The Genetic Algorithm is a model of machine learning
Based on the theory of evolution (Darwin)
Accomplished by creating a population of individuals
represented by “chromosomes” within a computer
Chromosomes can be just character strings that are analogous
to the base-4 chromosomes that we see in our own DNA
The individuals in the population then go through a process of
evolution (sexual reproduction followed by survival pressure
on offspring)
Evolutionary Forces

Selection


Crossover


A survival process
A sexual process
Mutation

A random process
Selection


Fitness to perform
Mechanisms for Selection

Survival
 Quantitative function
 Human intervention
Crossover
Mutation
Biomorphs

Visualizing and controlling mutations
http://www.phy.syr.edu/courses/mirror/biomorph/
Genetic Programming


Genetic programming is the application of
genetic algorithms to computer programs
themselves
Proposed byJohn Koza (Stanford)
Genetic Programming Process







Start with a collection of functions
randomly combine them into programs
run the programs and see which gives the best
results
keep the best programs (natural selection)
mutate some of the others
test the new generation
repeat this process until a clear best program
emerges
Genetic Programming Example


Data (-1,1,3,5,7,9,11,13,15,17)
Input function elements

x (can equal any digit 0..9)
 +,-,*,/

Starting functions (x,x+0,x*2,1+3,4/2)
Function Tree
x
*
3
+
*
x
2
Many more functions
-
x
1
*
2
1
*
x
2
x
-1,1,3,5,7,9,11,13,15,17
0,3,5,7,9,11,13,15,17,19
0,2,4,6,8,10,12,14,16,18
0,3,6,8,12,15,18,21,24,27
0,1,2,3,4,5,6,7,8,9
Functional Values
Truth x
-1
1
3
5
7
9
11
13
15
17
3*x
0
1
2
3
4
5
6
7
8
9
2*x
0
3
6
9
12
15
18
21
24
27
0
2
4
6
8
10
12
14
16
18
2*x+1 2*x-1
1
-1
3
1
5
3
7
5
9
7
11
9
13
11
15
13
17
15
19
17
Fitness
SUM
Fitness Fitness Fitness Fitness Fitness
0
2
1
1
1
0
2
1
2
0
0
2
1
3
-1
0
2
1
4
-2
0
2
1
5
-3
0
2
1
6
-4
0
2
1
7
-5
0
2
1
8
-6
0
2
1
9
-7
0
2
1
10
-8
0
20
10
55
-35
Genetic Algorithms are Flexible




Can solve hard problems quickly and
reliably.
Can be easily adapted to data
(simulations, models)
Can be extended (scalable)
Can be hybridized
GA Software

Evolver (for Excel)
http://www.jurikres.com/catalog/ms_evol.htm
Palisade Corp