Adaptation

During the lifetime of an individual in the natural world, its fitness may increase, either through "physical adaptation" (e.g. bigger muscles resulting from exercise) or through "learnt adaptations" (e.g. learning how to find plentiful food supplies). In GAUL, there is no distinction between the two types of adaptation, it simply provides a mechanism with which the programmer may reevaluate solutions. (Of course, the programmer may consider the two mechanisms for adaptation seperately if they wish.)

Additionally, in our computational optimisation procedures we are not resticted to following the exact procedure from nature, whatever that may be. This provides us with the flexibility to produce, so-called, hybrid-GA algorithms.

For reference, the source code for this section of the tutorial is struggle2.c.

"The Baldwin Effect"

If learning helps survival or procreation, then the individuals which are best able to learn will have the most offspring. Therefore, the genes responsible for learning will be more frequent in future generations.

"The Lamarkian Hypothesis"

The (largely discredited, but well-known) Lamarckian hypothesis states that traits aquired during the lifetime of an organism may be genetically transmitted to its offspring. Although the required mechanism for "reverse transcription" of aquired traits into the individual's genes does not exist in nature, computationally it may form the basis of very powerful optimisation procedures.

Example Implementation

We use the same objective function as in struggle.c from the previous section, but this time we apply a Lamarkian GA and a Baldwinian GA in addition to the original Darwinian GA. This requires us to define a new function which will perform the equivalent role to the process of adaptation or learning in nature. GAUL provides a number of built-in adaptation functions, but none of those is considered appropriate for this particular example. Our adaptation function simply performs a single hill-climbing step on one, randomly selected, allele:

entity *struggle_adaptation(population *pop, entity *child)
  {
  entity        *adult;         /* Adapted solution. */
  int           allele;         /* Randomly selected allele. */

/*
 * We must generate a new solution by copying the original solution.
 * This function copys all genomic, and if appropriate, phenomic data.
 * It is never safe to adapt the solution in place.
 */
  adult = ga_entity_clone(pop, child);

/* Make point mutation. */
  allele = random_int(strlen(target_text));
  ((char *)adult->chromosome[0])[allele]++;
  struggle_score(pop, adult);

  if (adult->fitness > child->fitness)
    return adult;

/* Searching in that previous direction didn't help. */
  ((char *)adult->chromosome[0])[allele]-=2;
  struggle_score(pop, adult);

  if (adult->fitness > child->fitness)
    return adult;

/* We must already be at a maxima. */
  ((char *)adult->chromosome[0])[allele]++;
  adult->fitness = child->fitness;

  return adult;
  }

Finally, we extend the example's "main()" function to create three identical populations which are seperately evolved using each of the available evolutionary schemes. This allows comparison between them those evolutionary schemes.

int main(int argc, char **argv)
  {
  population    *popd=NULL;     /* Population for Darwinian evolution. */
  population    *popb=NULL;     /* Population for Baldwinian evolution. */
  population    *popl=NULL;     /* Population for Lamarckian evolution. */
  char          *beststring=NULL;       /* Human readable form of best solution. */
  size_t        beststrlen=0;           /* Length of beststring. */

  random_seed(23091975);

  popd = ga_genesis_char(
     80,                        /* const int              population_size */
     1,                         /* const int              num_chromo */
     strlen(target_text),       /* const int              len_chromo */
     NULL,                      /* GAgeneration_hook      generation_hook */
     NULL,                      /* GAiteration_hook       iteration_hook */
     NULL,                      /* GAdata_destructor      data_destructor */
     NULL,                      /* GAdata_ref_incrementor data_ref_incrementor */
     struggle_score,            /* GAevaluate             evaluate */
     ga_seed_printable_random,  /* GAseed                 seed */
     struggle_adaptation,       /* GAadapt                adapt */
     ga_select_one_roulette,    /* GAselect_one           select_one */
     ga_select_two_roulette,    /* GAselect_two           select_two */
     ga_mutate_printable_singlepoint_drift, /* GAmutate   mutate */
     ga_crossover_char_allele_mixing, /* GAcrossover      crossover */
     NULL,                      /* GAreplace              replace */
     NULL                       /* void *                 userdata */
            );

  ga_population_set_parameters(
     popd,                       /* population   *pop */
     GA_SCHEME_DARWIN,           /* const ga_scheme_type scheme */
     GA_ELITISM_PARENTS_SURVIVE, /* const ga_elitism_type   elitism */
     0.9,                        /* double       crossover */
     0.1,                        /* double       mutation */
     0.0                         /* double       migration */
                            );

/*
 * Make exact copies of the populations, except modify
 * their evolutionary schemes.
 */
  popb = ga_population_clone(popd);
  ga_population_set_scheme(popb, GA_SCHEME_BALDWIN_CHILDREN);
  popl = ga_population_clone(popd);
  ga_population_set_scheme(popl, GA_SCHEME_LAMARCK_CHILDREN);

The "ga_population_clone()" function makes an exact replica of a population, including its defined callbacks and any individuals which it contains. To avoid another call to "ga_population_set_parameters()" (which would also be valid), we use "ga_population_set_scheme()" to override the previous evolutionary mode.

/*
 * Evolve each population in turn.
 */
  ga_evolution(
    popd,                       /* population          *pop */
    600                         /* const int           max_generations */
         );

  printf( "The final solution with Darwinian evolution with score %f was:\n",
          ga_get_entity_from_rank(popd,0)->fitness );
  beststring = ga_chromosome_char_to_string(popd, ga_get_entity_from_rank(popd,0), beststring, &beststrlen);
  printf("%s\n", beststring);

  ga_evolution(
    popb,                       /* population          *pop */
    300                         /* const int           max_generations */
                  );

  printf( "The final solution with Baldwinian evolution with score %f was:\n",
  ga_get_entity_from_rank(popb,0)->fitness );
  beststring = ga_chromosome_char_to_string(popb, ga_get_entity_from_rank(popb,0), beststring, &beststrlen);
  printf("%s\n", beststring);

  ga_evolution(
    popl,                       /* population          *pop */
    300                         /* const int           max_generations */
                 );

  printf( "The final solution with Lamarckian evolution with score %f was:\n",
          ga_get_entity_from_rank(popl,0)->fitness );
  beststring = ga_chromosome_char_to_string(popl, ga_get_entity_from_rank(popl,0), beststring, &beststrlen);
  printf("%s\n", beststring);

  /* Deallocate population structures. */
  ga_extinction(popd);
  ga_extinction(popb);
  ga_extinction(popl);

  /* Deallocate string buffer. */
  s_free(beststring);

  exit(2);
  }

Note that we only perform 200 generations of the Lamarckian/Baldwinian optimisation but 600 generations of Darwinian optimisation so that the total number of fitness evaluations in each run will be approximately equal. In many practical cases, a full reevaluation of the fitness is not required, and therefore these non-Darwinian versions of the GA can be very efficient.

Alternative ga_scheme_type choices are GA_CLASS_BALDWIN_ALL and GA_CLASS_LAMARCK_ALL which adapt every individual in the population at every generation instead of just the new individuals. These allow ongoing adaptation or learning, rather than just a single chance immediately after "birth".