home *** CD-ROM | disk | FTP | other *** search
/ ProfitPress Mega CDROM2 …eeware (MSDOS)(1992)(Eng) / ProfitPress-MegaCDROM2.B6I / PROG / MISC / GENALG.ZIP / 900628.GA next >
Encoding:
Text File  |  1990-07-21  |  4.4 KB  |  91 lines
  1.  
  2.  
  3.  
  4.  
  5. Back at the January, 1988 MIND meeting, the topic of genetic algorithms was
  6. broached.  Several speakers gave tutorials or research reports then, and I
  7. was charged up as a result.  I set about writing a program that would
  8. perform an exceedingly simple demonstration of the basics of genetic
  9. algorithms.
  10.  
  11. But I wanted it to have some of my own touches, so I put in procedures not
  12. only for mutation and crossover style effects, but also transcription.  All
  13. of the relevant parameters could then be fed to the program from the
  14. command line.  From there, it was relatively easy to set up a batch file
  15. that would repeatedly call the program with a particular set of parameters.
  16. Over a period of several days, I can collect results from hundreds of
  17. simulations.
  18.  
  19. That's what is presented below.  The simulation operates on a population of
  20. bit strings, 48 bits long, that are interpreted as floating point numbers
  21. and compared to a goal value, that is a simple scalar real number.  This
  22. introduces non-linearity into the evaluation scheme, since there are
  23. varying amounts of importance attached to a bit in the string depedning
  24. upon its placement.
  25.  
  26. The header can be interpreted as follows:
  27. K is the carrying capacity, that is, how many "organisms" are allowed in
  28. the population; "Goal" is the goal value, a real number; "E" is the
  29. reciprocal of the amount of error to tolerate, selected to give a single
  30. test probability of less than one in a million; "M" is the complement of
  31. the probability that a particular organism will undergo mutation; "C" is
  32. the probability that if crossover occurs, it will be straightforwrd
  33. crossover and not inversion; "T" is the complement of the probability of
  34. transcription taking place; "FOM" is the "figure of merit", or the factor
  35. by which to compare the results to the expected random probability of
  36. success; and "Gen" is the number of generations before the success
  37. condition was met.  (If the simulation did not beat out the random
  38. probability, then the message "No better than random search" was printed
  39. out.  So far, this message has never crossed my screen.)
  40.  
  41. No further fuss, here is the set of sample statistics for the data:
  42.  
  43.  
  44.             K    Goal   E     M    C    T    FOM        Gen 
  45.         
  46.     Min    40 3.141592 4096  0.8  0.8  0.8   23.469         9
  47.     Max    40 3.141592 4096  0.8  0.8  0.8 2912.711      1117
  48.     Count 250      250  250  250  250  250      250       250
  49.     Avg    40 3.141592 4096  0.8  0.8  0.8 283.5842   208.752
  50.     sd                                     336.5842  181.5331
  51.  
  52.     Min    50 3.141592 4096  0.8  0.8  0.8   15.686         5
  53.     Max    50 3.141592 4096  0.8  0.8  0.8 4194.304      1337
  54.     Count 476      476  476  476  476  476      476       476
  55.     Avg.   50 3.141592 4096  0.8  0.8  0.8 347.4443  158.1869
  56.     sd                                     476.0098  170.9528
  57.  
  58.     Min   100 3.141592 4096  0.8  0.8  0.8    9.055          3
  59.     Max   100 3.141592 4096  0.8  0.8  0.8 3495.253       1158
  60.     Count 231      231  231  231  231  231      231        231
  61.     Avg   100 3.141592 4096  0.8  0.8  0.8 330.9919   88.46753
  62.     sd                                     383.8358   118.4062
  63.  
  64.     Min   200 3.141592 4096  0.8  0.8  0.8   26.887          5
  65.     Max   200 3.141592 4096  0.8  0.8  0.8 1048.576        195
  66.     Count 226      226  226  226  226  226      226        226
  67.     Avg   200 3.141592 4096  0.8  0.8  0.8 261.0660   35.02212
  68.     sd                                     190.9221   32.58035
  69.  
  70.  
  71.     Min   400 3.141592 4096  0.8  0.8  0.8   23.617          1
  72.     Max   400 3.141592 4096  0.8  0.8  0.8  2621.44        111
  73.     Count 474      474  474  474  474  474      474        474
  74.     Avg   400 3.141592 4096  0.8  0.8  0.8 250.2303   17.34599
  75.     sd                                     245.9702   13.05584
  76.  
  77.  
  78. As one can see, there is a great deal of variability in the speed of
  79. convergence, but empirically the results are much better than could be
  80. expected from a random walk type search.  (The simulation used an
  81. evaluation function which returned a distance measure.  Algorithmic search
  82. methods would have to take the kind of error measure provided into account,
  83. which is not necessary when using the genetic algorithm approach.  For
  84. those of us who are wary of the issue of "programmer omniscience", this
  85. feature provides one more avenue of approach to otherwise intractable
  86. problems.)
  87.  
  88.  
  89. Wesley R. Elsberry
  90. July, 1990
  91.