(thing) by Mithrandur Wed Dec 19 2001 at 20:09:06

GESA (Guided Evolutionary Simulated Annealing) is a genetic algorithm. Unlike other genetic algorithms, it does not make use of crossover but uses mutation exclusively.

GESA also makes use of the concept of simulated annealing. The algorithm is as follows:

  1. Decide on parameters N, population size; and M number of "clans".
  2. Somehow (usually randomly) generate M individuals to be the parents of each clan.
  3. divide the population equally between the clans, giving each a clan population P.
  4. Make P copies of each parent. Mutate each copy, with probability of mutation related to t3, one of the temperature parameters. The resulting individuals are the children of the clan.
  5. For each clan, decide who the parent of the next generation will be:
    1. Evaluate the fitness function for each child in the clan. If the most fit is more fit than the clan's parent, he becomes the new parent.
    2. otherwise, the most fit child becomes the new parent if: e^((fit(c) - fit(p))/t1) > rand(0,1) where p is the parent, c is the child, and t1 is the first temperature parameter.
    3. if best child fails this test, then the old parent remains the parent for another generation
  6. Now, assign population to the clans in the next generation in proportion to the "credits" that each clan has. Clans get "credits" as follows:
    1. Let b be the best of the parents for the next generation.
    2. Each time e^((fit(c) - fit(b))/t2) > rand(0,1) is true, the clan gets a credit. Do this for all children c in the clan.
  7. The population must remain constant over time, so for each clan c, newpop(c) = credits(c)/totalCredits. Make sure that something sensible gets done with any remainders, as you cannot have fractional individuals.
  8. Check the termination condition (usually when there is only one clan left, or some maximum number of epochs have been reached). Goto step 4 if you don't terminate.
Note that the math here assumes that the fitness function increases for increased fitness. I have found that hyperbolic tangent works well as a cooling function for the annealing parameters.

I like it!