CIS 123 - Genetic Algorithms

For this example, I created a program that starts with a bunch of random strings and tries to evolve them to create a string that reads "Management Information Systems".

The program creates a population of 1000 strings. These are strings of random characters at first. Then the program creates generation after generation using the following rules:

1. The fitness of each string is evaluated. Fitness is a measure of how closely the string matches the target string. A perfect match has a fitness score of 0. The higher the number, the worse the match.
2. A select few (50) of the best performing members of the population are kept alive for the next generation. The rest of the population is replaced by children of the current population.
3. The children are created by breeding. Two parents are selected from the original population and the child gets some of its characters from one parent, and the rest of its characters from the other parent. Strings with very good (low) fitness scores are more likely to breed than strings with poor (high) fitness scores.
4. After breeding, all of the new children are subject to random mutations. There is a small chance that any one of their characters may change into a different character.

This process continues until the program hits 1000 generations or one of the members of the population achieves a perfect fitness score (which is 0). The printout below shows one sample run of the program. To save space, the program only displays information for generations where the most fit member of the population has changed.

The printout shows the generation number, the average fitness score for the population as a whole, the fitness score for the most fit member of that generation, and the string of the most fit member of that generation.

Notice how poorly the initial random choices perform and how quickly the fitness scores improve. Almost every generation at the beginning shows amazing improvement. By generation 33, the overall fitness of the population has stagnated, but a better top performer is being produced once in a while. Finally, the 124th generation produces a perfect match.

Gen Average Best Most fit phrase --- -------- ----- ------------------------------ 0 49153.09 20483 )bp\}l[9:R+^lil@iefSjj2Q[Rb=<F 1 41676.80 17859 YyY_Z\ktLQ.QkI.evXrMqu5ew6Dva} 2 34902.85 14065 /?{coZ^I_m%_nu|7di[aOn;KXJkxmh 3 28959.94 8780 *MnVcmoZCW$:vxlzxNfJfs#2rmb[kj 4 24010.69 6705 CEclySaaoe(GrthldLsrwa/DvlU<yl 5 20366.96 5918 5erRZQaiol66~H~_xZsbla/Dvz^^xg 6 16969.03 4264 5eyRZoaioo66pi}zwZ~bla/Ivz^Vx{ 8 12629.99 3241 Gdc~nSq^ot(GYi~ld[soja+Qvsuvy} 9 11377.53 2785 YSmltlahkn$DYhusk\kku}/Kt]wbtg 10 10264.89 2275 CN}l[hlamj(Griu}kUrnwm0K|s|i_} 12 8992.08 1989 N^kjnjazdt$5rXuno[xouu#Upsybng 13 8377.56 1571 GdvXnlkaej(Ckeuedgxxja+Qvst]lw 14 7846.55 1246 Ydrgclqqmj1Gkhuldisssu"Svrsbnt 16 7081.52 1004 L^rknojahx$GrXuwdixdkh#Ntmtbnw 17 6800.38 724 Gdkgn_uaor$Gnhhrk[sokm#Gvrwbi} 18 6574.70 709 Gdr_gouaol$Gohuzngsklm#Xtr}^iw 19 6416.52 637 Gdu_ejuhor$GljuznZsrkm#Xvrw^ix 20 6102.55 588 D^k_jlk_ms$Mnhunoisllm+Qtsybmx 21 5866.16 421 L^kjjjqhor$Dkhusocslem#Uvstbmo 22 5735.92 419 Pdk]jjkhms$Gliuldisllm#Uvrtbmx 23 5670.15 325 L^kjjjqhmr$Mkhusocsllm#Qvqtbmo 25 5533.85 273 L^rgheqhmr$Grhorkisllm"Qvsxbnp 26 5375.36 265 Pdk_jjkhor$Gliqlk[slnq#Uvrtbqt 27 5446.73 223 Ldrbhekhms$Gjhorkisllm"Qvsxbnp 29 5237.32 175 Ldkbjbqhos$Gneonkcsllm#Qvqtbnp 31 5383.51 139 M^kbhekims$Glhorkcslln#Uvssbnp 32 5303.14 135 Ldrbeejhos$Gneorkcsglm#Uvstbmp 33 5191.23 127 M^kbhelhms$Glhorkcslln#Qvstbmp 34 5367.77 113 M^kbhelhms$Gleoskasllm#Tvrsbmt 37 5367.82 109 L^kbjelhms$Gnhosmcsglm#Uvstfmt 38 5118.45 105 Ldkbhbkhor!Gneoroasllm"Uvstbmt 40 5120.13 90 Ldkbhekhor!Gleoskaslnm!Uvstbmt 41 5155.01 85 Mdk_hemhos Gneprkbsklm!Svqtbnt 43 5260.46 71 M^kbhemhms Gnhorkashnm!Qvstbmt 46 5254.52 70 M^kbhelhos!Gneoroasgnm!Tvstbmt 47 5303.64 57 M^kbheldos!Gneorkasgpm!Uvstfmt 49 5262.79 52 Mdkbhekdms Gneorkasjpn!Tvstfmt 50 5190.95 51 Ldnbhemhms Gneormashnn!Svstbmt 51 5148.92 48 M^nbheldms!Gneormbsjnm!Uvstcmq 52 5296.55 47 M^nbheldor Gneormbshnm"Qvstfmt 53 5250.86 40 Mam_hemdos Gneormbshnm!Tvstbmt 54 5190.77 32 M_mbhemdms Gneprmashnn!Tvstfmt 57 5173.61 28 Lbnbheldms Gneormashnn!Svstfmt 59 5127.58 27 L_nbheldos!Gnepsmashnn!Txstfmt 60 5249.05 24 Mbnbhemdos Jneormashnn!Tvstfmt 61 5404.03 23 L_nbheldos!Jneprmashnn!Txstfmt 62 5278.54 20 Lbnbhemdms!Gneormashnn!Tystfmt 63 5153.78 15 Manbhemdos Jneormashnn!Txstfmt 67 5172.29 14 Manbhemdos Jneormashnn!Tystfmt 70 5260.93 13 Manahemdos Jneormashnn!Sxstfmt 71 5215.59 12 Manbhemdms Jnformashnn!Systfmt 74 5036.43 11 Manbhemdot Jnformashnn!Systfmt 78 5310.74 10 Manahemdos Jnformasjnn!Systfms 79 5191.19 9 Manahemdot Jnformashon!Systfmt 82 5145.58 8 Manahemdot Jnformatjon!Systfmt 85 5176.75 7 Manahemdot Jnformatjon!Systfms 86 5091.63 6 Manahemdot Jnformatjon!Systems 90 5155.70 5 Managemdmt Jnformathon!Systems 94 5153.44 4 Managemdmt Informathon!Systems 100 5093.61 3 Managemdot Informatjon Systems 104 5284.69 2 Managememt Informatjon Systems 109 5131.90 1 Managememt Information Systems 124 5098.10 0 Management Information Systems