Genetic algorithm help
BlitzPlus Forums/BlitzPlus Programming/Genetic algorithm help
| ||
A while ago, I got interested in advanced artificial intelligence. I read a tutorial on neural networks, and that tutorial told me to learn genetic algorithms first. So I looked up the same guy's tutorial on genetic algorithms, and wrote this.AppTitle "Genetic algorithm test" Const NUMGENES=100 Const ANSWER=42 Const MUTATIONRATE=50 Const DEATHFITNESS=100 Const DEATHAGE=1000 Type gene Field number1 Field operator1 Field number2 Field operator2 Field number3 Field operator3 Field number4 Field fitness Field age End Type SeedRnd MilliSecs() For t=1 To NUMGENES phenotype.gene=New gene phenotype\number1=Rnd(1,100) phenotype\operator1=Rnd(1,4) phenotype\number2=Rnd(1,100) phenotype\operator2=Rnd(1,4) phenotype\number3=Rnd(1,100) phenotype\operator3=Rnd(1,4) phenotype\number4=Rnd(1,100) phenotype\fitness=0 phenotype\age=0 Next While Not KeyDown(1) For phenotype.gene=Each gene Select phenotype\operator1 Case 1 newnumber1=phenotype\number1+phenotype\number2 Case 2 newnumber1=phenotype\number1-phenotype\number2 Case 3 newnumber1=phenotype\number1*phenotype\number2 Case 4 If phenotype\number1>0 And phenotype\number2>0 Then newnumber1=phenotype\number1/phenotype\number2 EndIf End Select Select phenotype\operator2 Case 1 newnumber2=newumber1+phenotype\number3 Case 2 newnumber2=newnumber1-phenotype\number3 Case 3 newnumber2=newnumber1*phenotype\number3 Case 4 If newnumber1>0 And phenotype\number3>0 Then newnumber2=newnumber1/phenotype\number3 EndIf End Select Select phenotype\operator3 Case 1 newnumber3=newumber2+phenotype\number4 Case 2 newnumber3=newnumber2-phenotype\number4 Case 3 newnumber3=newnumber2*phenotype\number4 Case 4 If newnumber2>0 And phenotype\number4>0 Then newnumber3=newnumber2/phenotype\number4 EndIf End Select phenotype\fitness=ANSWER-newnumber3 phenotype\age=phenotype\age+1 If phenotype\fitness=0 Then Exit EndIf If Abs(phenotype\fitness) > DEATHFITNESS Then Delete phenotype.gene ElseIf phenotype\age > DEATHAGE Then Delete phenotype.gene EndIf Next For phenotype.gene=Each gene If Rnd(1,Abs(phenotype\fitness))=1 Then geneA.gene=phenotype.gene Exit EndIf Next For phenotype.gene=Each gene If Rnd(1,Abs(phenotype\fitness))=1 Then geneB.gene=phenotype.gene Exit EndIf Next If geneA <> Null And geneB <> Null Then phenotype.gene=New gene If Rand(1,2)=1 Then phenotype\number1=geneA\number1 Else phenotype\number1=geneB\number1 EndIf If Rand(1,2)=1 Then phenotype\operator1=geneA\operator1 Else phenotype\operator1=geneB\operator1 EndIf If Rand(1,2)=1 Then phenotype\number2=geneA\number2 Else phenotype\number2=geneB\number2 EndIf If Rand(1,2)=1 Then phenotype\operator2=geneA\operator2 Else phenotype\operator2=geneB\operator2 EndIf If Rand(1,2)=1 Then phenotype\number3=geneA\number3 Else phenotype\number3=geneB\number3 EndIf If Rand(1,2)=1 Then phenotype\operator3=geneA\operator3 Else phenotype\operator3=geneB\operator3 EndIf If Rand(1,2)=1 Then phenotype\number4=geneA\number4 Else phenotype\number4=geneB\number4 EndIf If Rand(1,MUTATIONRATE)=1 Then If Rand(1,2)=1 Then phenotype\number1=phenotype\number1+Rand(1,20) Else phenotype\number1=phenotype\number1-Rand(1,20) EndIf EndIf If Rand(1,MUTATIONRATE)=1 Then phenotype\operator1=Rand(1,4) EndIf If Rand(1,MUTATIONRATE)=1 Then If Rand(1,2)=1 Then phenotype\number2=phenotype\number2+Rand(1,20) Else phenotype\number2=phenotype\number2-Rand(1,20) EndIf EndIf If Rand(1,MUTATIONRATE)=1 Then phenotype\operator2=Rand(1,4) EndIf If Rand(1,MUTATIONRATE)=1 Then If Rand(1,2)=1 Then phenotype\number3=phenotype\number3+Rand(1,20) Else phenotype\number3=phenotype\number3-Rand(1,20) EndIf EndIf If Rand(1,MUTATIONRATE)=1 Then phenotype\operator3=Rand(1,4) EndIf If Rand(1,MUTATIONRATE)=1 Then If Rand(1,2)=1 Then phenotype\number4=phenotype\number4+Rand(1,20) Else phenotype\number4=phenotype\number4-Rand(1,20) EndIf EndIf EndIf Wend If phenotype\fitness <> 0 Then End EndIf Print "Solution found!" stri$=stri$+phenotype\number1 Select phenotype\operator1 Case 1 stri$=stri$+"+" Case 2 stri$=stri$+"-" Case 3 stri$=stri$+"*" Case 4 stri$=stri$+"/" End Select stri$=stri$+phenotype\number2 Select phenotype\operator2 Case 1 stri$=stri$+"+" Case 2 stri$=stri$+"-" Case 3 stri$=stri$+"*" Case 4 stri$=stri$+"/" End Select stri$=stri$+phenotype\number3 Select phenotype\operator3 Case 1 stri$=stri$+"+" Case 2 stri$=stri$+"-" Case 3 stri$=stri$+"*" Case 4 stri$=stri$+"/" End Select stri$=stri$+phenotype\number4 stri$=stri$+"="+ANSWER+"!" WaitKey End (I know waitkey won't work unless I set the graphics mode, I just have it in there so I can read my stuff and click the close button, habit probably has something to do with it too.) It compiles and goes about its job, but I always end up with either of two end results, both undesirable. Either A: All "genes" die (which I can fix, but B is more important) or B: I end up with a couple of "genes" that are one digit away from being right and never go any farther (which I can't seem to fix). The goal is to find four numbers and operators that when combined make up the number ANSWER, in my code 42. It never gets to 42, it just stays one digit away until the "genes" get too old (DEATHAGE, 1000 computations) and die and I am left with nothing. The tutorial only explained the mathematical principles behind a genetic algorithm (and some C code). The code I have here is completely written by scratch from me. Does anyone know what is wrong with it? |
| ||
| I don't know anything about this sort of algorithm, but I'll do a little research myself and get back to you if I find an answer. Never hurts to learn something new. EDIT: Can you supply a link to the tutorial you were working from? I'm struggling to see a relationship between thing's I'm seeing on the internet and your code. Something you might want to try is printing out values of each phenotype on each iteration of the loop, and slow it down or pause it for each iteration. You might find that some of the values are not what you'd expect them to be. When it comes to debugging, print statements are your best friends. That is, unless you're writing shaders, where they don't exist ;) |
| ||
| Excuse me for saying this, but if you couldn't find this tutorial, you weren't looking very hard :P. It is the first google result on the subject. http://www.ai-junkie.com/ga/intro/gat1.html I wrote the code about a year ago, I did some very extensive debugging but I don't remember it all. I'll try working on it some more and see what I get. EDIT: Hmm... Weird crap is happening. I ran the program, waited a few seconds, and clicked the stop button. My computer can theoretically do 2.7 billion computations in a second, so I considered this a relatively long time in computer math terms. I saw the usual pattern of a couple genes with a fitness of one. But then, I let it go for a few seconds more and clicked stop again. This time, there were genes with a fitness of 0. A bug in the mutation code seems to have frozen the program at that point (it kept doing rand(0,1) and waited for it to return 1...) but when I computed the gene myself, they were way, way off. Usually around positive or negative 200. I'll try fixing the bug that stops the program, but I don't know how they got fitnesses of 0 when they were more than 100 degrees off... EDIT: Solution found! 56-75*99+42=42! Huh. It turns out that the code that detects a fitness value of 0 didn't actually do anything after detecting it except exit(), which merely skipped over the code that increments age and kills off genes that are too old or unfit. However, fixing this problem results in the above result, which is quite obviously incorrect. I'll work on it some more... EDIT: I see a pattern. It either reaches extinction or finds an answer ending in 42. I guess I forgot an operation or something. EDIT: Okay, I fixed all bugs mentioned up till now, including extinction. Now it always produces an answer. However, the answer is only right around 1/4 of the time. 66-40/99+42=107.59595959595959595959595959596 58+56-86/75=112.85333333333333333333333333333 32-79/55+28=58.563636363636363636363636363636 79-46-29+38=42 71-44/8*14=-6 2-68+23+85=42 11*3-16+25=42 37*91-30/79=3366.6202531645569620253164556962 80+21+25/3=109.33333333333333333333333333333 72+28/48*21=84.25 Those are the numbers it gives me (checked with windows calc, it turns out you can actually copy and paste right from the program into calc). AppTitle "Genetic algorithm test" Const NUMGENES=100 Const ANSWER=42 Const MUTATIONRATE=50 Const DEATHFITNESS=100 Const DEATHAGE=1000 Type gene Field number1 Field operator1 Field number2 Field operator2 Field number3 Field operator3 Field number4 Field fitness Field age End Type SeedRnd MilliSecs() While Not SolutionFound If extinction Then For t=1 To NUMGENES phenotype.gene=New gene phenotype\number1=Rnd(1,100) phenotype\operator1=Rnd(1,4) phenotype\number2=Rnd(1,100) phenotype\operator2=Rnd(1,4) phenotype\number3=Rnd(1,100) phenotype\operator3=Rnd(1,4) phenotype\number4=Rnd(1,100) phenotype\fitness=0 phenotype\age=0 Next extinction=1 EndIf For phenotype.gene=Each gene Select phenotype\operator1 Case 1 newnumber1=phenotype\number1+phenotype\number2 Case 2 newnumber1=phenotype\number1-phenotype\number2 Case 3 newnumber1=phenotype\number1*phenotype\number2 Case 4 If phenotype\number1>0 And phenotype\number2>0 Then newnumber1=phenotype\number1/phenotype\number2 EndIf End Select Select phenotype\operator2 Case 1 newnumber2=newnumber1+phenotype\number3 Case 2 newnumber2=newnumber1-phenotype\number3 Case 3 newnumber2=newnumber1*phenotype\number3 Case 4 If newnumber1>0 And phenotype\number3>0 Then newnumber2=newnumber1/phenotype\number3 EndIf End Select Select phenotype\operator3 Case 1 newnumber3=newnumber2+phenotype\number4 Case 2 newnumber3=newnumber2-phenotype\number4 Case 3 newnumber3=newnumber2*phenotype\number4 Case 4 If newnumber2>0 And phenotype\number4>0 Then newnumber3=newnumber2/phenotype\number4 EndIf End Select phenotype\fitness=ANSWER-newnumber3 phenotype\age=phenotype\age+1 If phenotype\fitness=0 Then ;Goto SolutionFound SolutionFound=True EndIf If Abs(phenotype\fitness) > DEATHFITNESS Then Delete phenotype.gene ElseIf phenotype\age > DEATHAGE Then Delete phenotype.gene EndIf Next For phenotype.gene=Each gene If Rnd(0,Abs(phenotype\fitness))=0 Then geneA.gene=phenotype.gene Exit EndIf Next For phenotype.gene=Each gene If Rnd(0,Abs(phenotype\fitness))=0 Then geneB.gene=phenotype.gene Exit EndIf Next If geneA <> Null And geneB <> Null Then phenotype.gene=New gene If Rand(1,2)=1 Then phenotype\number1=geneA\number1 Else phenotype\number1=geneB\number1 EndIf If Rand(1,2)=1 Then phenotype\operator1=geneA\operator1 Else phenotype\operator1=geneB\operator1 EndIf If Rand(1,2)=1 Then phenotype\number2=geneA\number2 Else phenotype\number2=geneB\number2 EndIf If Rand(1,2)=1 Then phenotype\operator2=geneA\operator2 Else phenotype\operator2=geneB\operator2 EndIf If Rand(1,2)=1 Then phenotype\number3=geneA\number3 Else phenotype\number3=geneB\number3 EndIf If Rand(1,2)=1 Then phenotype\operator3=geneA\operator3 Else phenotype\operator3=geneB\operator3 EndIf If Rand(1,2)=1 Then phenotype\number4=geneA\number4 Else phenotype\number4=geneB\number4 EndIf If Rand(1,MUTATIONRATE)=1 Then If Rand(1,2)=1 Then phenotype\number1=phenotype\number1+Rand(1,20) Else phenotype\number1=phenotype\number1-Rand(1,20) EndIf EndIf If Rand(1,MUTATIONRATE)=1 Then phenotype\operator1=Rand(1,4) EndIf If Rand(1,MUTATIONRATE)=1 Then If Rand(1,2)=1 Then phenotype\number2=phenotype\number2+Rand(1,20) Else phenotype\number2=phenotype\number2-Rand(1,20) EndIf EndIf If Rand(1,MUTATIONRATE)=1 Then phenotype\operator2=Rand(1,4) EndIf If Rand(1,MUTATIONRATE)=1 Then If Rand(1,2)=1 Then phenotype\number3=phenotype\number3+Rand(1,20) Else phenotype\number3=phenotype\number3-Rand(1,20) EndIf EndIf If Rand(1,MUTATIONRATE)=1 Then phenotype\operator3=Rand(1,4) EndIf If Rand(1,MUTATIONRATE)=1 Then If Rand(1,2)=1 Then phenotype\number4=phenotype\number4+Rand(1,20) Else phenotype\number4=phenotype\number4-Rand(1,20) EndIf EndIf EndIf If phenotype=Null Then extinction=1 EndIf Wend .SolutionFound If phenotype\fitness <> 0 Then End EndIf Print "Solution found!" stri$=stri$+phenotype\number1 Select phenotype\operator1 Case 1 stri$=stri$+"+" Case 2 stri$=stri$+"-" Case 3 stri$=stri$+"*" Case 4 stri$=stri$+"/" End Select stri$=stri$+phenotype\number2 Select phenotype\operator2 Case 1 stri$=stri$+"+" Case 2 stri$=stri$+"-" Case 3 stri$=stri$+"*" Case 4 stri$=stri$+"/" End Select stri$=stri$+phenotype\number3 Select phenotype\operator3 Case 1 stri$=stri$+"+" Case 2 stri$=stri$+"-" Case 3 stri$=stri$+"*" Case 4 stri$=stri$+"/" End Select stri$=stri$+phenotype\number4 stri$=stri$+"="+ANSWER+"!" Print Stri$ WaitKey End |
| ||
| Excuse me for saying this, but if you couldn't find this tutorial, you weren't looking very hard :P. It is the first google result on the subject. Well, since I don't know the exact keywords you used in your search, it's difficult to make that accusation. It appears third when searching "genetic algorithm" on Google. It seems you're well on your way, keep at it. |
| ||
| Schilcote won the battle! Schilcote gained 1337 EXP Schilcote leveled up! Schilcote learned a new skill: Genetic Algorithms! Yay, I actually learned something new from debugging this program. When you're dividing two uncontrolled numbers, use a float. There's still the occasional wrong answer, but it occurs very rarely now. It seems to find the answer pretty fast. Now I'm going to try changing the answer value and see how it performs. |
   |