*Ken holds a BS in physics from Rensselear Polytechnic Institute. He is currently engaged in research on artificial intelligence and system modeling. Ken can be reached at kprice@solano.community.net.*

How do you determine the best machine for a job?

**Step #1.** Express all the parameters of your machine using some kind of coding machine. Each particular machine will then be expressed as a list of these parameters.

**Step #2.** Generate some machines with random parameters.

**Step #3.** Test the machines against each other and select the few best ones.

**Step #4.** Generate new machines by combining parameters from the ones selected in Step #3, occasionally making random modifications in some of the parameters.

**Step #5.** Repeat Steps #3 and #4 until you're tired of watching the show.

What I've just described is a genetic algorithm, and it's done a pretty good job with life on this planet. Generation after generation of iterations, selecting the best few to reproduce and occasionally throwing in the odd mutation, has resulted in millions of different species. The end result is that there are lifeforms suited for every niche in every environment.

Genetic algorithms might not be the fastest way to generate the "best" machine for a job (it would be a lot easier to design a sentient lifeform from scratch than to wait for evolution to stumble across a human), but their main advantage is that they require no knowledge about the system. For instance, the traditional way of generating an aircraft wing is to study aerodynamics and spend months calculating airflows, lifts, stresses, and the like. Alternatively, you could just express a generic wing as a string of parameters (size, shape, weight, and so on), create some random wings, test them against each other, and let the fittest reproduce. A weekend of iteration on a supercomputer would probably yield a pretty good design.

Solving problems such as these falls into the category of "combinatorial" or "global" optimization. Other approaches to finding the "best" (according to some predefined criteria) configuration involve simulated annealing, a stochastic-search technique familiar to chip designers, who must determine the best geometrical arrangement for millions of circuits on microprocessors.

*DDJ* has examined both genetic algorithms and simulated annealing before (see "Genetic Algorithms" by Mike Morrow, April 1991 and "Simulated Annealing" by Michael P. McLaughlin, September 1989). In this month's column, however, Kenneth Price combines the two techniques, resulting in an approach called "genetic annealing" which takes the best from both the genetic and annealing worlds.

Genetic annealing is a hybrid, random-search technique that fuses simulated annealing and genetic methodologies into a more efficient algorithm. Like its genetic counterpart, the genetic-annealing algorithm creates new solutions by exchanging genetic material between members of a population. Instead of using a competitive tournament to decide which members will survive into the next generation, however, genetic annealing uses an adaptive, thermodynamic criterion based on a simple feedback scheme. With this strategy, the genetic-annealing algorithm can outperform the algorithms whose principles it embodies even though it is hardly more complex than running a suite of greedy algorithms in parallel.

The particular graph used in this example is commonly called a "necklace" because of its obvious resemblance to neckwear; see Figure 1(a). An [M,2] necklace is a ring of M vertices ("beads") each of which is connected radially to a companion vertex for a total of 2M vertices. As Figure 1(b) illustrates, any diameter across the necklace constitutes a bipartition since it divides the necklace into two sets, each of which contains M vertices. The bipartition generated by a diameter is optimal because only two edges cross the diameter to connect opposing sides. Because of its rotational symmetry, an [M,2] necklace has M optimal bipartitions in all.

For the purposes of computation, you can represent an [M,2] necklace as a string of 2M bits. Bits at even positions are the beads on the ring itself, and bits at odd positions represent the dangling beads; see Figure 2. The actual binary value assigned to a bead indicates the set to which it belongs.

To count the number of edges that span sets, perform an XOR operation on every pair of bits that represent connected vertices and sum the results. When the vertices at the ends of an edge belong to the same set, the bits they contain will be identical, and the XOR operation will return a 0. Conversely, a pair of connected vertices with different binary values represents an edge with a vertex in each set. The XOR operation counts these spans by returning a 1.

To simulate a heat bath, you will need an entire population of bit strings. The number of bit strings depends on the problem: for this example a population of 20 strings is adequate. For convenience, you can arrange the bit strings into a two-dimensional array so that one coordinate locates a string within the population while the other coordinate gives you the position of a bit within a string.

Next, you initialize the bit strings by filling each one with an equal number of 1s and 0s. In a genetic-annealing experiment, you must randomly select the initial population to ensure that the system starts out like a "white-hot" thermodynamic ensemble. Starting from this condition makes it less likely that the population will prematurely cool to a suboptimal minimum. To randomize a bit string while keeping its populations of 1s and 0s equal, try swapping each bit with another bit from a randomly selected location within the same string.

The number of edges having a vertex in each set measures the quality of a bipartition as a solution. In the context of a genetic algorithm, this number reflects the "fitness" of a bit string to survive as a "gene" in a competitive selection procedure. By contrast, simulated annealing uses the fitness of a configuration-like energy in order to exploit the laws of statistical mechanics. Genetic annealing adopts the annealing metaphor, treating a configuration's fitness-like energy, even though the annealing process itself is driven by population dynamics.

To relax the bit strings into their optimal condition, they must be cooled very slowly. In a genetic-annealing program, you control the rate of cooling with the cooling constant, C--a real number in the closed interval [0,1] that represents the fraction of DE that is returned to the population. For example, C=1 holds the population at a constant "temperature" by using 100 percent of the energy stored in DE to reheat thresholds. By contrast, C=0 releases all of DE's stored energy from the system and leaves thresholds unaltered. In effect, C=0 sets up a suite of greedy algorithms since each threshold is always equal to the energy of the bit string to which it's assigned. Most problems of consequence require very slow cooling. Typically, C ranges from 0.9 to 0.99 and beyond, although for a given problem, the optimal choice of C depends on a variety of factors. Pseudo-code for the genetic-annealing algorithm is shown in Figure 4.

You can also use the genetic-annealing algorithm to "cool" a population of configurations to a condition of maximum energy. All you need to do is replace the "greater than" symbol with a "less than" symbol in the portion of code that determines whether or not a mutant is acceptable. This has the effect of reversing the sign of the spontaneous energy so that during the reheating cycle each threshold is lowered by the amount dE=C*DE/N. This feature lets you use a problem's natural measure of fitness without having to invert it. Figure 3 shows what the maximum energy solution to the necklace problem looks like for M=8.

This energy bank approach to simulated annealing can substantially reduce the time you need to design and execute difficult combinatorial optimizations. Traditional annealing methods invoke the venerable Metropolis algorithm to forge a link between the laws of statistical mechanics and combinatorial optimization. Despite its great utility, the Metropolis algorithm is computationally expensive because the decision of whether or not to accept a mutant usually requires that you generate a random number and compare it to an exponential term. Configurations that are not much worse than their progenitors may be rejected depending on the random number generated. The genetic-annealing algorithm accepts every configuration that is not much worse than its progenitor based on the result of a simple comparison that requires neither a random-number generator nor the use of acceptance probabilities.

Traditional annealing methods also rely on an empirically derived "annealing schedule" to control the rate at which the Metropolis temperature should be lowered. The advantage of using thresholds to track the time-averaged loss of spontaneous energy from individual configurations is that you can maintain equilibrium at any temperature without using an annealing schedule just by restoring energy to each threshold at the same average rate that the ensemble loses it. In most cases, this reduces the researcher's challenge to finding the smallest value of C that will allow the population to maintain equilibrium as it anneals.

Perhaps the greatest advantage that cooling a population in parallel affords you is the opportunity to employ crossbreeding as a form of mutation. Actually, instead of mating pairs of bit strings in a separate cross-breeding procedure (as you do in the genetic algorithm), the genetic-annealing algorithm transfers genetic information between bit strings by "splicing" it. Splicing tentatively replaces a portion of the target string with the corresponding section from another bit string chosen at random from the population. In the splicing scenario, the randomly chosen string remains unaltered while it donates a copy of a segment of its "genetic material" for the target string to use as a trial mutation; see Figure 5. By drawing upon the success of other configurations in the population, splicing brings to the genetic-annealing algorithm all of the problem-solving power that crossbreeding imparts to the genetic algorithm.

You must be careful when implementing a splicing procedure for the bipartitioning problem because the number of 1s in the substring being donated must be the same as the number of 1s in the target substring. To ensure that 1s are conserved, the size of the donated substring is allowed to grow until the number of 1s it contains equals the number of 1s in the corresponding target substring and until the two substrings differ in at least one bit position, or until the whole string is used.

The mutation scheme in GENNEAL.C (described later) includes all three forms of mutation: random bit swapping, a reflection operation, and splicing. PS, PR, and PX are the probabilities that a mutation will swap random bits, reflect a substring, or splice a substring, respectively. Of course, PS+PR+PX=1. The size of a swap mutation is controlled by EXS, while EXR determines the size of a reflection mutation.

Figure 2 Bits at even positions are the beads on the ring itself; bits at odd positions represent the dangling beads.

Figure 3 Maximum-energy solution to the necklace problem for M=8.

1. Randomly select an initial population of N configurations. 2. For i=1 to N: Initialize the iththreshold, Th[i], with the energy of the ithconfiguration. 3. DE=0 /* Empty the energy bank */. 4. For i=1 to N: /* Begin cooling loop */. 5. Splice or randomly mutate the ithconfiguration. 6. Compute the energy, E, of the resulting mutant. 7. If E>Th[i] then restore the old configuration. 8. If E <= Th[i] then: a.DE=DE+Th[i]--E /* Add energy difference to DE */. b.Th[i]=E /* Reset threshold */. c. Replace old configuration with successful mutant. 9. Mutate next configuration or end cooling loop. 10.dE=DE*C/N /* Compute reheating increment, dE. 0<C<1 */ 11.For i=1 to N: /* Begin reheating loop */. 12.Th[i]+dE /* Add dE to each threshold */. 13.Return to step 3 once all thresholds have been reheated.

Copyright © 1994, *Dr. Dobb's Journal*