The Evolutionary Algorithm

Create N solution "creatures.' Each one has:

A genetic code-a sequence of numbers that characterizes a possible solution to the problem. The numbers can represent critical parameters, steps to a solution, rules, etc.

For each generation of evolution, do the following:

- Do the following for each of the N solution creatures:

(i) Apply this solution creature's solution (as represented by its genetic code) to the problem, or simulated environment.

(ii) Rate the solution.

Pick the L solution creatures with the highest ratings to survive into the next generation.

Eliminate the (N - L) nonsurviving solution creatures.

Create (N - L) new solution creatures from the L surviving solution crea- tures by:

(i) making copies of the L surviving creatures. Introduce small random variations into each copy; or

(ii) create additional solution creatures by combining parts of the ge- netic code (using 'sexual' reproduction, or otherwise combining por- tions of the chromosomes) from the L surviving creatures; or

(iii) doing a combination of (i) and (ii) above.

- Determine whether or not to continue evolving:

Improvement = (highest rating in this generation) - (highest rating in the previous generation)

If Improvement < Improvement Threshold, then we're done

- The Solution Creature with the highest rating from the last generation of evolution has the best solution. Apply the solution de- fined by its genetic code to the problem.

Key Design Decisions

In the simple schema above, the designer of this evolutionary algorithm needs to determine at the outset:

- Key parameters:

N L Improvement Threshold

What the numbers in the genetic code represent and how the solution is computed from the genetic code.

A method for determining the N solution creatures in the first generation. In general, these need only be "reasonable' attempts at a solution. If these first-generation solutions are too far afield, the evolutionary algorithm may have difficulty converging on a good solution. It is often worth- while to create the initial solution creatures in such a way that they are reasonably diverse. This will help prevent the evolutionary process from just finding a 'locally' optimal solution.

How the solutions are rated.

How the surviving solution creatures reproduce.

Variations

Many variations of the above are feasible. Some variations include:

There does not need to be a fixed number of surviving solution creatures (i.e., "L") from each generation. The survival rule(s) can allow for a variable number of survivors.

There does not need to be a fixed number of new solution creatures created in each generation (i.e., [N - L]). The procreation rules can be independent of the size of the population. Procreation. can be related to survival, thereby allowing the fittest solution creatures to procreate the most.

The decision as to whether or not to continue evolving can be varied. It can consider more than just the highest-rated solution creature from the most recent generation (s). It can also consider a trend that goes beyond just the last two generations.