Transcript Final year project

Investigation of the Effect of
Neutrality on the Evolution
of Digital Circuits.
Eoin O’Grady
Final year Electronic and
Computer Engineering
Project.
Project Goals




Design and create a Genetic Algorithm capable of
implementing Cartesian Genetic Programming
(evolution of Digital Logic Circuits).
To study and analyse the concept of Neutrality in Genetic
Algorithms.
To develop an explicit Neutral Mutation Operator.
To implement this Neutral Mutation Operator with
Cartesian Genetic Programming to evolve complex
Digital Logic Circuits.
Genetic Algorithms and Evolution




Genetic Algorithms are search algorithms based on the mechanics of
natural selection and natural genetics.
They combine survival of the fittest among string structures and with a
structured yet randomized information exchange to form a search
algorithm.
In every generation a new set of artificial creatures (strings) is created
using the parts of the fittest members of the previous generation, with an
occasional new part (mutation) thrown in to ensure the population doesn't
become homogenized.
There are four basic operations within Genetic Algorithms they are
evaluation, selection, crossover and mutation.
Genetic Algorithms and Evolution
Evaluation

When every new population is created each member is evaluated for it’s
fitness by testing for some attribute.
Member[0]
fitness=4
1 0 0 1 1 0 0 1
Member[1]
fitness=7
1 0 1 1 1 1 1 1
Selection

Individuals are selected at random in groups after they are evaluated for
their fitness and the individuals with the highest fitness within these
groups are used to populate the new generation.
Member[2] fitness=7
Member[7] fitness=5
Member[8] fitness=6
Member[5] fitness=4
Member[2] fitness=7
Member[7] fitness=5
Genetic Algorithms and Evolution
Crossover

Crossover is used to produce the new members of a population a point is
chosen at random on a chromosome where it will be split and joined with
the other half of another chromosome split at the same point.
Member[2]
fitness=7
1 1 1 1 1 1 0 1
Member[1]
fitness=5
0 0 0 1 1 1 1 1
NewMember[0]
fitness=8
1 1 1 1 1 1 1 1
Mutation

Mutation occurs to some of the genes in the new population. A point is
picked at random within a chromosome and the mutation that occurs is
random.
NewMember[0]
fitness=8
1 1 1 1 1 1 1 1
NewMember[0]
fitness=8
1 1 1 1 0 1 1 1
Cartesian Genetic Programming


CGP is an advanced implementation of Genetic algorithms created by
Julian miller and allows solutions to more complicated problems to be
evolved (usually digital logical problems).
In CGP the individual genes of a genotype (chromosome) consist of more
than a single integer value. Typically they have multiple values that
represent inputs and a single value that represents an operation.
The Genotype

The genotype is made up of many genes which all together represent a
system.
A C -3
Genes
AC0
B D -3
BD0
B10
D10
3 4 -1
000
1 2 -3
5 6 -1
Cartesian Genetic Programming
The Phenotype
When the data contained in the genotype is converted to simulate the system
described within it becomes known as the phenotype and the genes within are known
as cells.

A C -3
A
B
C
D
AC0
B D -3
BD0
B10
D10
3 4 -1
000
1 2 -3
5 6 -1
Cartesian Genetic Programming
Evolving the Genotype



A population of genotype is evolved in exactly the same way as a normal
genetic algorithm with evaluation, selection, crossover and mutation.
When evaluating each genotype it must be first mapped to it’s phenotype.
Then all permutations of the inputs are applied and then each cell output
is tested against a truth table of the desired outputs. The most suitable
cells for output are used to define the genotype’s fitness.
Neutrality

Neutrality is the concept that when trying achieve a better solution of any
classification that by first pursuing a change in the solution which does not
make the solution better that eventually this will help the solution to find a
change that will increase it’s fitness.
For any Search Algorithm, in particular Genetic Algorithms, that relies on a
cost function, i.e. calculation of fitness, to determine it’s next area of
search on a fitness landscape there are areas where there will be no local
path along which the search algorithm will find an area of higher fitness.
Fitness

Solution Spectrum
The Fitness Landscape


The term Fitness Landscape is used when describing any evolutionary
process, be it biological, technological or digital, to describe a landscape
which is drawn along the spectrum of possible “solutions” for a given
problem.
In GA the landscape is arranged such that each neighbouring solution is
just one mutation different from it’s neighbour and the height of this
landscape corresponds to the suitability i.e. the fitness level for a given
solution.
The horizontal distance between two points is an inverse measure of
probability of mutation
1.2
Fitness landscape for Sinc(x) where
x=5-bit signed binary String
1
Fitness level

0.8
0.6
0.4
0.2
0
-0.2
-0.4
Solution spectrum
Neutrality on a Fitness Landscape


Neutrality in the context of fitness landscapes and genetic algorithms
refers to effect of changing a solution’s description or chromosome in
some way so that it’s fitness level is unchanged by the change in the
chromosome.
A neutral mutation is the implementation of neutrality on a fitness
landscape.
If a genetic algorithm is stuck on a peak which is not the global maximum
of fitness landscape then a neutral mutation (a mutation which is intended
to mutate the current solution so that we get another with equal or
greater fitness).
Neutral Mutation
Fitness

Solution Spectrum
The N-K Model





In the N-K model there are N distinct processes (cardinality of a gene)
that exist in S amount of different states (length of chromosome).
Therefore there are S to the power of N possible solutions.
In the NK–model each process makes a contribution to the overall
performance of the solution that depends on it’s own type and the types of
K other solutions. Therefore K<=N-1.
K determines the correlation of the landscape that is when K=0 the
correlation is high and the fitness landscape has a single smooth sided
peak.
As K increases the ruggedness also increases and when K=N-1 the fitness
landscape is at it’s most rugged.
The correlation coefficient is calculated by (Weinberger, 1990; Fontana et
al., 1993):
ρ(d)=[1-d/N][1-K/(N-1)]^d
and thus for d=1 and large N, K=0 implies ρ(1)≈1 and K=N-1 has ρ(N)=0
Neutrality using the N-K Model

To investigate further the effect of neutrality on the N-k model we must
now impose a new operator M which will split the fitness landscape into M
number of layers through which a population will be allowed to freely and
randomly travel
Intrinsic Neutral Mutation in
Genetic Algorithms


Neutral Mutation occurs ‘naturally’ in Genetic Algorithms.
Example:
3,1,0;0,2,-2;1,3,-3;4,1,0;0,2,0;1,8,-2;8,6,-3;4,0,-1;4,8,-1;2,0,3;
47.0
13;10;12;
(From generation 70)
3,1,0;4,2,-3;1,3,-3;2,1,0;0,2,0;6,8,-3;7,6,-3;1,7,0;4,8,-1;2,0,3;
47.0
13;9;12;
(From generation 81)
3,1,0;1,2,-3;1,3,-3;6,1,-3;0,2,0;6,8,-3;8,6,0;10,4,-1;4,8,1;2,0,-3;
48.0
13;9;11;
(From generation 83)
F
I
t
n
e
s
s
Possible
Mutations
The effects of intrinsic neutral
mutation

Problems arise for intrinsic neutral mutations when a population has
converged on a large neutral plateau.
Fitness
Possible Mutations
After many
generations
Fitness
Possible Mutations
The effects of Explicit Neutral
Mutation

For the scenario that a population has evolved on a peak:
Fitness
Possible Mutations
The effects of Explicit Neutral
Mutation

For the scenario that a population has converged on a plateau:
Fit
ne
ss
Fit
ne
ss
Possible Mutations
Possible Mutations
After several neutral
mutations
Fit
ne
ss
Fit
ne
ss
Possible Mutations
Possible Mutations
Neutral Mutation on a Known
Fitness Landscape


In order to properly develop and implement a neutral mutation operator
for use on a fitness landscape that was complex, extremely rugged,
incredibly large and above all unknown, it was necessary to first develop a
method of implementing it on a landscape that was known.
A GA was programmed to find the global maximum for the mathematical
function Sinc(x+y).
Neutral Mutation on a Known
Fitness Landscape




The GA used a Neutral Mutation Operator which kicked in whenever the
population was converged on a peak/plateau.
The gene structure took the form of binary values with a total
chromosome length of 18, 9 genes each for x and y.
One gene was for the sign of the integer four made up the values greater
than zero and four were values less than zero (i.e. down to 2-4 which
gave a total range of -15.9375 to 15.9375).
These integer values were then used to calculate the fitness by the
equation:
Fitness=Sin(√(x^2 +y^2)
√(x^2 +y^2)

1.

2.

3.

4.

5.

6.

7.

8.

9.
Project Milestones
Research Genetic Algorithms and Cartesian Genetic Programming
particularly the work of Julian Miller.
Start working with basic GA software (in the form of Java classes)
and set conditions to solve basic one max GA once classes are
compiled and evolve successfully
Design and implement a CGP simulator which when passed a genetic
algorithm will synthesis a basic logic operator circuit and produce
outputs for each genotype.
Create a suitable method for displaying a CGP Genotype as a basic
logic circuit (the CGP grid with Cells).
Use this simulator with the Genetic Algorithm software to evolve a 2bit adder and other simple circuits.
Research Neutrality and then experiment with different methods to
design and implement a neutral mutation operator.
Evolve a more complicated circuit such as a 3-bit multiplier using the
neutral mutation operator with the GA software and CGP simulator.
Using JBits (a Java API) design a new evolvable circuit to instantiate
the CGP model of a basic logical circuit on an FPGA.
Design fault injection method and determine methods to handle
these faults i.e. To be able to pull the outputs from different nodes
on the FPGA board in order to get an output of similar fitness.