Hello Everyone
I am a final year student at Manukau Institute of Technology.I am doing
my honours research project on Evolvable Harwdware. Xilinx has
developed GeneticFPGA toolkit. On one of the FPGA newsgroups I read
that it is free for download once you send a request email to the
address [email protected]. I couldn't find it on the Xilinx website.Also
I did send an email on this jbits address a few times but did not get
any reply.
I would be really grateful if you could send me the link to download
GeneticFPGA toolkit.
Thank you
Ankit Parikh

<[email protected]> schrieb im Newsbeitrag
news:[email protected] oups.com...
> Hello Everyone
> I am a final year student at Manukau Institute of Technology.I am doing
> my honours research project on Evolvable Harwdware. Xilinx has
> developed GeneticFPGA toolkit. On one of the FPGA newsgroups I read
> that it is free for download once you send a request email to the
> address [email protected]. I couldn't find it on the Xilinx website.Also
> I did send an email on this jbits address a few times but did not get
> any reply.
> I would be really grateful if you could send me the link to download
> GeneticFPGA toolkit.
> Thank you
> Ankit Parikh
>

NOWHERE.

if you search with Google you only find references to year 1999 !
so its possible as dead as JBits and no chanc to get hold on it.

Ankit,
click on http://en.wikipedia.org/wiki/Evolvable_hardware
and google Adrian Thompson.
The Xilinx devices he used, the 6200 family, is dead. No hardware, no
software.
The family dies for lack of commercial interest.
My feeling is that some smart academics have explored this field
already, and I have seen no progress over the past 5 years.
I would pick another subject...
Peter Alfke

Hi Peter
I am half way through this topic.So I have to finish it up.
Have you read Adrian Thompson's PHD thesis.I guess it would contain
some valuable information.Do you know where I could get it.Or do you
have any other suggestions for me.
Thanks
Ankit

Peter Alfke wrote:
> Ankit,
> click on
> http://en.wikipedia.org/wiki/Evolvable_hardware
> and google Adrian Thompson.
> The Xilinx devices he used, the 6200 family, is dead. No hardware, no
> software.
> The family dies for lack of commercial interest.
> My feeling is that some smart academics have explored this field
> already, and I have seen no progress over the past 5 years.
> I would pick another subject...
> Peter Alfke

During my Masters program a friend and I wrote a piece of software that
would take a logic circuit and generate a set of test vectors that
would give you the best fault coverage.

The program did this using a "Genetic Algorithm" approach.
First a random set of test vectors were created. Then the set of
vectors were repopulated based on a fitness function. (Basically if the
test vector had a high % of fault coverage it was more likely to be
selected back in the set of vectors) After that there is a
mutation/cross over phase which adds more variants to the population.
These 3 steps are repeated until a certain % of fault coverage is
completed by a set of the vectors.

The upside to this approach is it can be a lot faster than an
exhaustive approach, especially if the circuit is large. The downside
is every time you run the program you get a different answer. The
whole value of this and other evolutionary methods are how good is the
fitness function.

I'm not sure how you would use evolutionary methods in an FPGA.
Unless you wanted a hardware version of what my program does... create
a set of test vectors to test your ASIC every time it boots up. But I
probably need to read Adrian's paper aswell.

It is an interesting topic even if it might only academic merit at the
present.

Here are the references for the paper I wrote on this program.

1) Rudnick, E. , "Application of Simple Genetic Algorithms to
Sequential Circuit Test
Generation", Center for Reliable and High-Performance Computing,
University of
Illinois, Urbana, Il 61801
2) Rudnick, E., "Sequential Circuit Test Generation in a Genetic
Algorithm Framework",
Center for Reliable and High-Performance Computing, University of

Illinois, Urbana, Il 61801
3) Corno, F., "A Parallel Genetic Algorithm for Automatic Generation
of Test Sequences
for Digital Circuits", Dip. Automatica e Informatica -
Politecnico di Torino, Torino
Italy
4) Prinetto, P., "An Automatic Test Pattern Generator for Large
Sequential Circuits
based on Genetic Algorithms", Dip. Automatica e Informatica -
Politecnico di Torino,
Torino Italy

I should have been more specific:
I can imagine creative and useful ways to write software, and test
vectors, i.e. zeros and ones in an evolutionary way.
I just have a hard time with evolutionary hardware, where Adrian
created a frequency discriminator that worked, but defied any method of
circuit analysis (and repeatability, and stability over temperature).
Peter Alfke (just my personal opnion).

Hello Everyone
Thanks Eric for the suggestions.Since you have been working in the area
of evolutionary algorithms, can you suggest where I could find some
examples of code that use evolutionary algorithms for electronic or
logic circuit.This would give me an idea to start with my own code.I
haven't actually seen an evolutionary algorithm being implemented in a
code.So I have absolutely no idea how it looks like.Its like learning
programming for the first time.You need to look at some programs to get
started with your own code.
Ankit

Eric wrote:
> Evolutionary Algorithms do have their place.
>
> During my Masters program a friend and I wrote a piece of software that
> would take a logic circuit and generate a set of test vectors that
> would give you the best fault coverage.
>
> The program did this using a "Genetic Algorithm" approach.
> First a random set of test vectors were created. Then the set of
> vectors were repopulated based on a fitness function. (Basically if the
> test vector had a high % of fault coverage it was more likely to be
> selected back in the set of vectors) After that there is a
> mutation/cross over phase which adds more variants to the population.
> These 3 steps are repeated until a certain % of fault coverage is
> completed by a set of the vectors.
>
> The upside to this approach is it can be a lot faster than an
> exhaustive approach, especially if the circuit is large. The downside
> is every time you run the program you get a different answer. The
> whole value of this and other evolutionary methods are how good is the
> fitness function.
>
> I'm not sure how you would use evolutionary methods in an FPGA.
> Unless you wanted a hardware version of what my program does... create
> a set of test vectors to test your ASIC every time it boots up. But I
> probably need to read Adrian's paper aswell.
>
> It is an interesting topic even if it might only academic merit at the
> present.
>
> Here are the references for the paper I wrote on this program.
>
> 1) Rudnick, E. , "Application of Simple Genetic Algorithms to
> Sequential Circuit Test
> Generation", Center for Reliable and High-Performance Computing,
> University of
> Illinois, Urbana, Il 61801
> 2) Rudnick, E., "Sequential Circuit Test Generation in a Genetic
> Algorithm Framework",
> Center for Reliable and High-Performance Computing, University of
>
> Illinois, Urbana, Il 61801
> 3) Corno, F., "A Parallel Genetic Algorithm for Automatic Generation
> of Test Sequences
> for Digital Circuits", Dip. Automatica e Informatica -
> Politecnico di Torino, Torino
> Italy
> 4) Prinetto, P., "An Automatic Test Pattern Generator for Large
> Sequential Circuits
> based on Genetic Algorithms", Dip. Automatica e Informatica -
> Politecnico di Torino,
> Torino Italy
>
> Eric Holland

The number with the smallest Error is closest to the answer. (Still
with me?)

Step #3 Repopulate your population based on your fitness function
results. This is the tough part to grasp. We need to normalize all of
the errors so we can get a repopulation percentage. This will help us
get the new population of numbers.

Take the total of the error 0.57 + 0.86 + 1.43 + 0.29 = 3.15

Take the total of the normalized error = 5.53 + 3.66 + 2.20 + 10.86
=22.25

Repopulation percentage for 1 = 5.53/22.25 = 25%
Repopulation percentage for 6 = 3.66/22.25 = 16%
Repopulation percentage for 8 = 2.20/22.25 = 10%
Repopulation percentage for 4 = 10.86/22.25 = 49 %

So now you repopulation your population, this means if you were
generating a random number from 0-100,
if the number was 0-24 the answer would be 1.
if the number was 25-41(25+16) the answer would be 6
if the number was 42-52(42+10) the answer would be 8
if the number was 53-100 the answer would be 4

So you can see the smaller the Error the greater chance the new
population will include that number

New Repopulation = 4, 4, 4, 1
So if you kept on repeating step 2 eventually you would have a
population of all 4's, but 4 is not the answer. So how do we get the
answer in our population if we don't have 3 in the initial
population?

The answer is step #4.

Step #4 mutation / crossover. In this example we'll just do mutation.
Just generate a random number and replace it in the population.

New population after mutation 4, 4, 4, 9

Step #5 repeat steps 2 - 4 until total Error is acceptable. In this
case until you get an Error of 0.

The number with the smallest Error is closest to the answer. (Still
with me?)

Step #3 Repopulate your population based on your fitness function
results. This is the tough part to grasp. We need to normalize all of
the errors so we can get a repopulation percentage. This will help us
get the new population of numbers.

Take the total of the error 0.57 + 0.86 + 1.43 + 0.29 = 3.15

Take the total of the normalized error = 5.53 + 3.66 + 2.20 + 10.86
=22.25

Repopulation percentage for 1 = 5.53/22.25 = 25%
Repopulation percentage for 6 = 3.66/22.25 = 16%
Repopulation percentage for 8 = 2.20/22.25 = 10%
Repopulation percentage for 4 = 10.86/22.25 = 49 %

So now you repopulation your population, this means if you were
generating a random number from 0-100,
if the number was 0-24 the answer would be 1.
if the number was 25-41(25+16) the answer would be 6
if the number was 42-52(42+10) the answer would be 8
if the number was 53-100 the answer would be 4

So you can see the smaller the Error the greater chance the new
population will include that number

New Repopulation = 4, 4, 4, 1
So if you kept on repeating step 2 eventually you would have a
population of all 4's, but 4 is not the answer. So how do we get the
answer in our population if we don't have 3 in the initial
population?

The answer is step #4.

Step #4 mutation / crossover. In this example we'll just do mutation.
Just generate a random number and replace it in the population.

New population after mutation 4, 4, 4, 9

Step #5 repeat steps 2 - 4 until total Error is acceptable. In this
case until you get an Error of 0.

Kind of make sense???

I can give you sample code but it won't make sense unless you
understand the concept of evolutionary codes.

Hello Eric
Thanks for the psuedo code.It does help to understand the concept of
evolutionary algorithms.Now can you also give the code.I am very eager
to implement it.
Thanks again
Ankit

Hi Eric
Thanks for the code. It is quite complicated as compared to the psuedo
code. I tried making my own application in C#.It works sometimes but
sometimes it just enters an idefinite loop.This is when my population
values go beyond the right hand side constant value(ax + b = c
'value of constant c').I have a few questions for you:
1. What if you get the answer in the first population, the
corresponding normalised value would be infinite?
2.Are there any special conditions you need to check before populating
the list?

Here is my code which is based on your psuedo code.see if it makes
sense to you.
I really appreciate your help.
private void ImplementGA()
{
Random rnd = new Random();
int popsize=6;
int[] population = new int[popsize];
int i;
bool Found=false;
DateTime dt= new DateTime();
double a,b,c;
a=double.Parse(CoefficientTextBox.Text);
b=double.Parse(Constant1TextBox.Text);
c=double.Parse(Constant2TextBox.Text);

//Step 1
//Generate a random population
listBox1.Items.Add("Initial Population");
for(i=0;i<popsize;i++)
{
population.SetValue((int)(rnd.NextDouble()*10),i);
listBox1.Items.Add(population[i]);
}
listBox1.Items.Add("");
listBox1.Items.Add("");

//Step 2
//Fitness Function
listBox1.Items.Add("Corresponding Fitness Values");
double[] fitness = new double[popsize];
//(ax + b = c)
int x;
for(i=0;i<popsize;i++)
{
//fitness = ABS(1 - ((ax + b)/c))
x=population[i];
fitness[i] = Math.Abs(1 - ((a*x + b)/c));
listBox1.Items.Add(fitness[i]);
}
listBox1.Items.Add("");
listBox1.Items.Add("");

//My idea to check before repopulating
//Check for the end condition
for(i=0;i<popsize;i++)
{
if(fitness[i] == 0)
{
Result=population[i];
Found=true;
}
//else
//Found=false;
}

while(Found == false)
{
//Step 3
//Repopulate the population based on the fitness function
double ErrorTotal=0, NormalisedError=0;
double[] normalised = new double[popsize];
int[] RepopulationPercentage = new int[popsize];
for(i=0;i<popsize;i++)
{
ErrorTotal = ErrorTotal + fitness[i];

//Elitism - copy the best solution to the next generation
int Best=100;
for(i=0;i<popsize;i++)
{
if(Flag==false)
{
if(Best>=RepopulationPercentage[i])
{
Best=population[i];
}
}
else if(fitness[i] == 0)
{
Best=population[i];
}

}
listBox1.Items.Add("Best = "+Best);

//Step 4
//Repopulate - Only mutation is being used
population[0]=Best;

listBox1.Items.Add("Above list is the final population");

//Calculate the fitness of the new population
listBox1.Items.Add("New population fitness");
for(i=0;i<popsize;i++)
{
//fitness = ABS(1 - ((ax + b)/c))
x=population[i];
fitness[i] = Math.Abs(1 - ((a*x + b)/c));
listBox1.Items.Add(fitness[i]);
}

//Check for the end condition
for(i=0;i<popsize;i++)
{
if(fitness[i] == 0)
{
Result=population[i];
Found=true;
}
//else
// Found=false;
}
}

//Display the answer
AnswerTextBox.Text = Result.ToString();
}

To answer your first question: If your answer is found in the first
population you just got lucky and you're done! Your correct in the
way you check for if the Error == 0 you stop, or the normalized value
would be infinite.

I have had similar issues with the answer diverging on some iterations.
What you need to do is have a fixed number of iterations like 100, That
way it won't ever be in an infinite loop. Another thing to try would be
use a larger population 6 is pretty small.

Another thing to do is keep track of you populations total error, if it
is not going down, maybe introduce more mutations. There are a bunch of
ways to try and get your population to evolve into the answer faster.

Since your know in this particular problem ax + b can not be greater
than c, you can use this to evaluate each random number in your
population. If you number violates this property, then just throw out
that number and get a new random number. This is kind of cheating,
since the repopulating should naturally weed out these answers. One
other option would be to give numbers that violate the ax+b = c a very
large Error, that way they just won't get repopulated.

One other thing to check is make sure you repopulation function is
running correctly. It is very easy to make a mistake in that function.

Hi Eric
You can download the .exe file fom the following link: http://rapidshare.de/files/3899362/E...Solve.exe.html
I have limited the iterations to 1000 , so that it can solve equations
like 13x + 4 = 615.
It does it successfully.
Once agains thanks
Ankit

> Genetic Algorithm pseudo code:
>
> Problem: Solve 2x+1 = 7 (we know the answer is 3, but work with me)
>
> Step #1 Generate a Random population of numbers:
>
> Population = 1, 6, 8, 4
>
> Step #2 Chose a fitness function. Ours will be Error = ABS(1-(2x +
> 1)/7)
>
> Error(1) = ABS(1-(2x1+1/7)) = 0.57
> Error(6) = ABS(1-(2x6+1/7)) = 0.86
> Error(8) = ABS(1-(2x8+1/7)) = 1.43
> Error(4) = ABS(1-(2x4+1/7)) = 0.29
>
> The number with the smallest Error is closest to the answer.
> (Still
> with me?)
>
> Step #3 Repopulate your population based on your fitness function
> results. This is the tough part to grasp. We need to normalize all of
> the errors so we can get a repopulation percentage. This will help us
> get the new population of numbers.
>
> Take the total of the error 0.57 + 0.86 + 1.43 + 0.29 = 3.15
>
> 3.15/0.57 = 5.53
> 3.15/0.86 = 3.66
> 3.15/1.43 = 2.20
> 3.15/0.29 = 10.86
************** Bunch of quoted text trimmed *********************
>
>
> Kind of make sense???
>
>
> Eric
>

Good lord, that will just confuse them!...
Of course you realize that your example algorithm converges a
little slower than just guessing until you've guessed the right
answer. I say a little slower because what you've described
essentially IS just guessing until you happen upon the right answer,
with a few extra operations to slow everything down! The magic in a
genetic algorithm comes from the ***, which happens in the crossover
that you omitted in step 4 above. You HAVE to come up with a way to
combine two 'pretty good' solutions to get another 'pretty good,
maybe a bit better' solution. Without that combination step
(analogous to *** in the world of biology), you don't have a genetic
algorithm at all! Now finding a way to combine two 'pretty good'
solutions to come up with a new 'pretty good' solution is sometimes
difficult. In your example it would be easy; simply average (or
perhaps a randomly weighted mean) the parents to get the offspring.
Now that would actually converge to a solution in your example.
The mutation part is less important than the *** part, but still
needed. But i don't think i've EVER seen mutation implemented as
simply making up a wholy new, randomly generated member of the
population. That would be no better than (and roughly equivilent to)
having a larger initial population. The mutation must be a
relatively small change to an existing member of the population. The
idea is that your population will, after a few generations, be much
better adapted than a randomly generated individual and a small
change will have a decent chance of being 'pretty good' too.

I don't mean to be insulting or belittle the contribution to the
newsgroup, but genetic algorithms are important and your example
could easily confuse people.

Hi Rob
I undertsand why you are making a point about crossover.I have done
exactly the same thing. I use a special class to compare and sort the
population based on their fitness. Keeping in mind 'elitism',I also
copy the best solution to the new population. Then from a population of
six, I select 4 best values and average out consequent numbers.
Mutation- to randomise mutation process ,I select 4 members after
crossover and either add 1 0r subtract 1 depending on computer clock
ticks.This process is completely random.
Here's a piece of code for the above:

//Elitism - copy the best solution to the next generation
Array.Sort(RepopulationPercentage);
Best = RepopulationPercentage[popsize-1].accessElement;
listBox1.Items.Add("Best = "+Best);