|
Operators and Their Properties
Here is a list of all of the standard operators that Galapagos has
built-in. Keep this around when working on your algorithm to make sure
you understand what each operator does and what each property is.
This documentation is essentially a less verbose (and possibly more
helpful) form of the Javadoc. If
you're very confused about the syntax for the runner, consult Runner
Documentation or one of the examples.
Contents
 Note:
these are all JavaBeans, so they all have getX()
and setX(..) methods for each property X
and are Serializable.
Note: The return type Genome
technically means the generic type T extends Genome
See also
LEGEND
Operator Type
Description
Methods
|
| Operator Name
Comments
- type Property
- type Property
- ...
Runner's XML Example
Example
Runner XML Tag <exampleXML>
Another Operator Name
Comments
- type Property
- type Property
- ...
Runner's XML Example
Example Runner XML Tag
<exampleXML> |
top
Mating
Combines a Marriage of two genomes and
returns a new, combined genome
Common Methods
- Genome mate( Genome,
Genome, GAGenerator)
Properties
Example Runner XML Tag<mate>
... </mate> |
| Single Point
Choose one point and swap the tails.
E.g. the two binary genomes: 11111111
and 00000000 might
mate to: 11000000
The "first" genome will always get the head and the
"second" genome will always have the tail
No extra properties
Example Runner XML Tag<singlePoint
children="2" />
Double Point
Chooses two points and swaps the
middle section.
E.g. the two binary genomes: 11111111
and 00000000 might
mate to: 11000111
The "second" genome will always contribute the middle
section
No extra properties
Example Runner XML Tag<doublePoint
children="2"/>
Interlace
Does a coin-flip, then alternates each integer in the genome.
The two possibilities for the two binary genomes
11111111
and 00000000 are
10101010
or 01010101
No extra properties.
Example Runner XML Tag<interlace
children="2"/> |
top
Mutating
Modifies a Population
to create new "ideas"
Common Method
- Genome mutate(Genome,
GAGenerator) (protected - implemented
by children)
- Genome mutate(Population,
GAGenerator) (public - algorithm calls
this)
Example Runner XML Tag
<mutate> ... </mutate> |
Flip
Takes two integers and flips them, does this numFlips
number of times.
ProbPerGen is the probability that
one random, non-elite genome will be mutated each generation.
E.g. This digit-based genome: 123456
might mutate to 153426
after
one flip.
- Integer
numFlips
- Double probPerGen
Example Runner XML Tag
<flip numFlips="6" probPerGen="1.0"/>
Replace
Chooses slot and puts a new number into it (formatted by the
Factory, if needed), does this numReplace
number of times.
ProbPerGen is the probability that
one random, non-elite genome will be mutated each generation.
E.g. This digit-based genome: 123456
might mutate to 123956
after
one flip.
- Integer
numReplace
- Double
probPerGen
Example Runner XML Tag
<replace numReplace="6" probPerGen="1.0"/> |
top
Selection
Pairs up Genomes
for mating randomly with bias toward their fitness. Polygamy is
not practiced - so each genome is involved in one and only one marriage
(helps promote diversity).
Common Method
- List<Marriage> runSelection(Population,
GAGenerator)
Example Runner XML Tag
<select> ... </select> |
Roulette
The probability of a genome being chosen by Roulette
is fitness/SUM, so the higher the fitness, the more of the "roulette
wheel" is taken up. This process is repeated for each family,
so the two highest genomes are most likely to be paired together.
Probabilistically speaking, most marriages
are going to be close to equal in fitness.
Note: forces the user to extend a QuantifiableGenome,
not just a Genome.
- Integer numFamilies (another name
for this could be numMarriages - and this number needs to be
less than half of the population's size, otherwise there aren't
enough genomes).
- FitnessScaler scaler (see below)
Example Runner XML Tag
<roulette numFamilies="5">
<scaler>
...
</scaler>
</roulette>
Scaling
These operators only apply to QuanitifiableGenomes,
and are used to change the fitness based on the rest of
the population or some mathematical formula. A scaling operator
is encouraged, for example, with a Roulette
selection operator because sometimes all genomes need
to be differentiated if they all have similar fitnesses.
No Scaling
Simply returns the same value as before.
Example Runner XML Tag:
<noScale/>
Note: if the <scaler>..</scaler>
tag is omitted, then this operator is the default.
Log Scaling
Take the logarithm of each data point and multiplies them
by the multiplier. The motivation
behind the multiplier is to possibly use the result's decimal
places (which get truncated since fitness is expressed as
a BigInteger). Another way of
thinking about it is that the multiplier changes the base
of the logarithm.
Example Runner XML Tag:
<logScale multiplier="10"/>
Rank Scaling
Sorts the genomes by their fitness, highest first, then
multiplies each one according to a list of constants.
Note: The sorting is done using the Comparator, so
it'd better be transitive.
- List<Integer> coefficients
(optional)
Runner Note: the runner does not currently support
the list of coefficients for RankScale
Example Runner XML Tag:<rankScale
/>
Square Root Scaling
Takes the square root of each fitness, then multiplies
each one by a the multiplier.
The motivation behind the multiplier is to use more significant
digits which are truncated since fitness is expressed by
a BigInteger.
Example Runner XML Tag: <sqrtScale
multiplier="10"/>
Window Scaling
Finds the population's lowest fitness and subtracts that
value (minus 1) from the population. This sets the least
fit genome to a fitness of 1 so that it still has a possibility
of being selected.
Example Runner XML Tag:
<windowScale/> |
Tournament
Tournament selector will take 2tiers random genomes
and use a single-elimination style tournament to eliminate them
using the given Comparator. The tournament uses this for both
parents (so you can think of the two "finalists" being
the parents). Generally speaking, you don't want more than 3 tiers.
Note: Even on the last parent selection, there needs to be a
full pool, therefore the number of families needs to be population's
size/2 - 2tiers
- Integer numFamilies
- Integer numTiers
Example Runner XML Tag:
<tournament numFamilies="6" numTiers="2"
/> |
top
Survival
Determines which Genomes
survive to the next generation. The parameters are the lists of
marriages, children, and the unmarried Genomes.
Common Methods
- List<Genome> runReplace(List<Marriage>
marriages, List<Genome> children,
List<Genome> unMated)
|
Culling
This operator takes all of the genomes from all of the lists
and puts them in one list, sorts that list by Comparator
and returns the top n genomes,
where n = marriages.size() *2 + unMated.size().
In other words, it returns the best fit of the population without
changing the size.
No added properties.
Example Runner XML Tag: <culling/>
Nuclear
The nuclear survival operator looks at all of the "families",
that is all of the marriages and their children. Only the best
two candidates from each family will surivive. So if the children
aren't any better than their parents, the parents just survive.
The unmated automatically survive.
The assumption on the input here is that each of the children
are lined up with the marriages, so that if there are 3 children
per family, then the first 3 children are considered to be part
of the first marriage.
Example Runner XML Tag: <nuclear/> |
top
Merging
Takes two Populations
and combines them into one population
Abstract Methods
- Population merge(Population,
Population, GAGenerator)
Not supported by the Runner. |
Intersect
Takes two populations and lumps them together, sorts the list
, and takes the best. The new population is the average of the
two input populations.
Not supported by the Runner. |
top
| Page last updated:
April 12, 2006 |
|