The Age of Spiritual Machines: When Computers Exceed Human Intelligence (48 page)

EVOLUTIONARY ALGORITHMS

 

If biologists have ignored self-organization, it is not because self-ordering is not pervasive and profound. It is because we biologists have yet to understand how to think about systems governed simultaneously by two sources of order. Yet who seeing the snowflake, who seeing simple lipid molecules cast adrift in water forming themselves into cell-like hollow lipid vesicles, who seeing the potential for the crystallization of life in swarms of reacting molecules, who seeing the stunning order in networks linking tens upon tens of thousands of variables, can fail to entertain a central thought: if ever we are to attain a final theory in biology, we will surely have to understand the commingling of self-organization and selection. We will have to see that we are the natural expressions of a deeper order. Ultimately, we will discover in our creation myth that we are expected after all.

—Stuart Kauffman

 

“PSEUDO CODE” FOR THE EVOLUTIONARY ALGORITHM

 

Here is the basic schema for an evolutionary algorithm. Many variations are possible, and the designer of the system needs to provide certain critical lparameters and methods, detailed below.

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 creatures by:

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

(ii) create additional solution creatures by combining parts of the genetic code (using “sexual” reproduction, or otherwise combining portions 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

 

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

Key Design Decisions

In the simple schema above, the designer of thi is 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 worthwhile 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.

Happy Evolving!