Where can i find GeneticFPGA toolkit

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 snipped-for-privacy@xilinx.com. 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

Reply to
apsolar
Loading thread data ...

schrieb im Newsbeitrag news: snipped-for-privacy@g49g2000cwa.googlegroups.com...

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.

Antti

Reply to
Antti Lukats

Ankit, click on

formatting link
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

Reply to
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:

Reply to
apsolar

Ankit, I am the wrong person to ask, for I, personally, find the whole subject bogus. But that's my problem... Peter Alfke

Reply to
Peter Alfke

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

Reply to
Eric

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).

Reply to
Peter Alfke

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:

Reply to
apsolar

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

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???

Eric

Reply to
Eric

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

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.

Eric

Reply to
Eric

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

Reply to
apsolar

//-------Creates Initial Population

------------------------------------------------- for (int k=0; k < Popsize; k++) { for(int h=0; h < max; h++) { Population[k].SingleVector[h]=rand() % 2; } StoreCover[k]=evaluate(Faults, Population[k].SingleVector);

} //--- Genetic Algorithm Iterations

------------------------------------------------------- for (int y=0; y < 10; y++) //---- 10 itertions { total=0; //------Repopulation Based on Coverage Criterian

------------------------------------- posistion=1; value1=0; value2=0; value3=0; for (k=0; k < max; k++) Population[0].repopulation[k]=Population[0].SingleVector[k]; // ---- Makes sure non of the values repeat in repopulation for (k=1; k < Popsize; k++) { for (int h=0; h

Reply to
Eric

I found this Masters Thesis on how one person use Genetic Algorithms to create a FPGA netlist.

formatting link

Pretty Good Masters project.

Reply to
Eric

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

Reply to
apsolar

Your code looks pretty good.

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.

Good Luck

Eric

Reply to
Eric

Another thing to try is make your fitness function non-linear.

Error = (1-(ax+b)/c)^4

This will make the Error huge on values that are far away from the answer.

Eric

Reply to
Eric

"Eric" wrote in news: snipped-for-privacy@g49g2000cwa.googlegroups.com:

************** Bunch of quoted text trimmed *********************

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 SEX, 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 sex 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 sex 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.

-Rob Ryland

Reply to
Rob Ryland

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);

//Crossover int m=popsize-1; listBox1.Items.Add("After Crossover"); listBox1.Items.Add(population[0]); for(i=1;i

Reply to
apsolar

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.