home *** CD-ROM | disk | FTP | other *** search
/ Shareware Overload / ShartewareOverload.cdr / virus / ddj0491.zip / MORROW.ZIP / POPL.C < prev    next >
C/C++ Source or Header  |  1989-09-03  |  6KB  |  304 lines
  1. /***
  2. *       GASystem
  3. *       Mike Morrow
  4. *       September 1989
  5. ***/
  6.  
  7.  
  8. /**
  9. *    Routines to deal with the population of genes
  10. **/
  11.  
  12.  
  13.  
  14. #include "ga.h"
  15. #include "param.h"
  16. #include "gene.h"
  17. #include "util.h"
  18.  
  19. extern void *calloc();
  20.  
  21. #if __STDC__
  22. static int cmpints(GENE **g1, GENE **g2);
  23. #else
  24. static int cmpints();
  25. #endif
  26.  
  27.  
  28. #ifndef TRUE
  29. # define TRUE 1
  30. # define FALSE 0
  31. #endif
  32.  
  33.  
  34. /**
  35. *
  36. *
  37. **/
  38. static GENE **population, **newpopl;
  39.  
  40. /**
  41. *    poplstart is FALSE until somebody calls poplopen().  The population
  42. *    manipulation functions won't do anything until poplstart is TRUE.
  43. *    This allows various parameters to be set without continually regenerating
  44. *    populations.
  45. **/
  46. static short int poplstart = FALSE;
  47.  
  48.  
  49. /**
  50. *    These variables hold parameters that the user may set by interacting with the
  51. *    symbol table.  The default values are hardwired here.
  52. **/
  53. static int  param_popl_size = 100;        /* population size */
  54. static FIT_TYPE param_popl_fitness = 0;    /* sum of fitnesses */
  55. static int param_popl_mu = 1000;        /* inverse of prob. of mutation */
  56. static int param_popl_nmu = 0;            /* number of mutations so far */
  57.  
  58.  
  59. static CONST PARAMSPEC poplparams[] =
  60. {
  61.     {"POP",         (void *) ¶m_popl_size,         MODEINT,    FLAG_INIT},
  62.     {"FIT",            (void *) ¶m_popl_fitness,    MODEFIT,    FLAG_RO},
  63.     {"MU",            (void *) ¶m_popl_mu,        MODEINT,            },
  64.     {"NMU",            (void *) ¶m_popl_nmu,        MODEINT,    FLAG_RO    },
  65.  
  66.  
  67.     {(char *) 0,     (void *) 0,                     (MODE) 0,    0    }
  68. };
  69.  
  70.  
  71. /**
  72. *    This routine inserts information about the parameter vars
  73. *    into the symbol table.
  74. **/
  75. poplpinit()
  76. {
  77.     CONST PARAMSPEC *p;
  78.     
  79.     for(p = poplparams; p->param_name; p++)
  80.         paramins(p, SYMVAR);
  81. }
  82.  
  83.  
  84. /**
  85. *       Free old population.
  86. **/
  87. poplfree()
  88. {
  89.     unsigned int i;
  90.  
  91.     if(population)
  92.     {
  93.         warning("Destroying old population...");
  94.         for(i = 0; i < param_popl_size; i++)
  95.         {
  96.             free(population[i]);
  97.             free(newpopl[i]);
  98.         }
  99.     }
  100.     population = newpopl = (GENE **) 0;
  101.     param_popl_nmu = 0;
  102. }
  103.  
  104. poplopen()
  105. {
  106.     poplstart = TRUE;
  107.     poplinit();
  108.     popleval();
  109. }
  110.  
  111. /**
  112. *    Initialize the population of genes
  113. **/
  114. poplinit()
  115. {
  116.     unsigned int i;
  117.  
  118.     if(! poplstart)
  119.         return ;
  120.         
  121.     population = calloc(param_popl_size, sizeof(GENE *));
  122.     newpopl = calloc(param_popl_size, sizeof(GENE *));
  123.  
  124.     if(! population || ! newpopl)
  125.     {
  126.         fatal("No memory for population");
  127.     }
  128.  
  129.     
  130.     
  131.     for(i = 0; i < param_popl_size; i++)
  132.         if(! (population[i] = genenew()) || ! (newpopl[i] = genenew()))
  133.         {
  134.             char buff[80];
  135.             
  136.             sprintf(buff, "No memory to generate population of size %d\n",
  137.                 param_popl_size);
  138.             fatal(buff);
  139.         }
  140. }
  141.  
  142.  
  143.  
  144. /**
  145. *    Pass each member of the population through the objective function.
  146. *    This function also accumulates a new value for param_popl_fitness.
  147. **/
  148. popleval()
  149. {
  150.     unsigned int i;
  151.     
  152.     if(! poplstart)
  153.         return ;
  154.         
  155.     param_popl_fitness = 0;
  156.     for(i = 0; i < param_popl_size; i++)
  157.         param_popl_fitness += genefitness(population[i]);
  158. }
  159.  
  160.  
  161.  
  162. /**
  163. *    Show the top n members of the population
  164. **/
  165. void popldump(n)
  166. int n;
  167. {
  168.     unsigned int i;
  169.     
  170.     qsort(population, param_popl_size, sizeof(GENE *), genecomp);
  171.     
  172.     if(! n)
  173.         n = param_popl_size;
  174.         
  175.     for(i = 0; i < n; i++)
  176.         geneshow(population[i]);
  177.         
  178.     objdumpdone();
  179. }
  180.  
  181.  
  182. /**
  183. *    Do reproduction
  184. **/
  185. void poplrepro()
  186. {
  187.     register FIT_TYPE ave_fit;
  188.     register unsigned int oldindex, newindex;
  189.     GENE **temp;
  190.     
  191. #define SCALE (FIT_TYPE) 128
  192.  
  193.  
  194.     /**
  195.     * ave_fit gets a value that represents the average fitness of all
  196.     * the genes.  ave_fit is actually scaled to be (ave_fitness * SCALE).
  197.     **/
  198.     ave_fit = SCALE * param_popl_fitness;
  199.     ave_fit /= param_popl_size;
  200.  
  201.     newindex = oldindex = 0;
  202.     
  203.     if(ave_fit > 0)        /* don't do reproduction in degenerate case */
  204.     {
  205.         /**
  206.         *    Keep selecting genes for replication until we've filled up the
  207.         *    newpopl[] population.
  208.         **/
  209.         while(newindex < param_popl_size)
  210.         {
  211.             FIT_TYPE chance;
  212.         
  213.             /**
  214.             *    chance gets a value that represents how this gene's fitness
  215.             *    compares to the average fitness.  chance is scaled so that
  216.             *    an a gene with average fitness will have chance = SCALE.
  217.             **/
  218.             chance = SCALE * SCALE * population[oldindex]->gene_fit;
  219.             chance /= ave_fit;
  220.             
  221.     
  222.             /**
  223.             *    Generate a random number in [0, 2 * SCALE].  If the gene is
  224.             *    of average fitness, it will have a 50-50 chance
  225.             *    of duplicating.
  226.             **/
  227.             if(chance >= randnum((int)SCALE * 2))
  228.             {
  229.                 genedupl(newpopl[newindex++], population[oldindex]);
  230.             }
  231.             
  232.             /**
  233.             *    Go to the next candidate in the old population.  We may have
  234.             *    to wrap back to the beginning.
  235.             **/
  236.             oldindex++;
  237.             if(oldindex == param_popl_size)
  238.                 oldindex = 0;
  239.         }
  240.     }
  241.  
  242.     /**
  243.     *    Switch around -- the new population becomes the current population.
  244.     **/
  245.     temp = population;
  246.     population = newpopl;
  247.     newpopl = temp;
  248. }
  249.  
  250.  
  251. /**
  252. *    Do mutation
  253. **/
  254. poplmutate()
  255. {
  256.     unsigned int i;
  257.  
  258.     for(i = 0; i < param_popl_size; i++)
  259.         if(! randnum(param_popl_mu))
  260.         {
  261.             param_popl_nmu++;
  262.             genemutate(population[i]);
  263.         }
  264. }
  265.  
  266. /**
  267. *    Do crossover
  268. **/
  269. void poplcross()
  270. {
  271.     unsigned int i;
  272.  
  273.     /**
  274.     *    First, put the poplulation into random order.
  275.     **/
  276.     for(i = 0; i < param_popl_size; i++)
  277.         population[i]->gene_tag = rand();
  278.         
  279.     qsort(population, param_popl_size, sizeof(GENE *), cmpints);
  280.  
  281.     /**
  282.     *    Then pair up the genes for crossover.
  283.     **/
  284.     for(i = 0; i + 1 < param_popl_size; i += 2)
  285.     {
  286.         genecross(population[i], population[i+1]);
  287.     }
  288. }
  289.  
  290.  
  291.  
  292.  
  293.  
  294. /**
  295. *    Used by poplcross() in the call to qsort().
  296. **/
  297. static int cmpints(g1, g2)
  298. GENE **g1, **g2;
  299. {
  300.     return (*g2)->gene_tag - (*g1)->gene_tag;
  301. }
  302.  
  303.  
  304.