The Birds and the Bees
Evolutionary Programming for Analysis and Control
After receiving his first patent in 1868 at the age of 21 for an electric voting machine (hanging chads, anyone?), Thomas Alva Edison continued his prolific career as an inventor, ultimately securing 1,093 U.S. patents; the last awarded two years after his death in 1931 at age 84. At its peek during World War I, Edison’s West Orange, NJ, laboratory and manufacturing facility employed 10,000 scientists, engineers and factory workers at the 22-acre industrial complex. Among his many contributions to modern technology, including the phonograph, motion pictures, alkaline batteries and artificial rubber, he may be most famous for the first practical light bulb. He also is known for his iterative application of the scientific process: hypothesis, testing, evaluation and generation of new hypotheses. Throughout his quest for an appropriate light bulb filament, he tested many candidate materials, including over 6,000 different carbonized plant fibers sampled from North America and the tropics, before settling on strands of cotton. He considered tungsten, but the technology needed to process the hard metal was still 30 years in the future.
The sometimes-disparaging epithet of an “Edisonian approach” encapsulates Edison’s penchant for testing a large number of possible solutions in the laboratory rather than the methodical analytical approach that expends the most effort decomposing problems into independent, linear variables. Moreover, the inherently parallel Edisonian approach evaluates the performance of a system as a whole while analytical decomposition is based on the serial optimization of components. Perhaps prejudice develops from the Edisonian search for an “available” solution, while the deterministic analytical types search for the absolute “best” solution. However, as with Edison’s difficulty with tungsten, the evolving environment of resources, time and knowledge limits the practical solution of any problem to the “best available.”
Starting in the mid 1960s, Professor John H. Holland sought to model problems bound by an evolving environment after the natural process of adaptation and natural selection. His resulting “genetic algorithm” (GA) defines a procedure used to discover the identity of the best available inputs that yield the desired output. One common application of the GA is the traveling salesman problem (TSP) wherein the desired output is the shortest round-trip route through a large number of cities. The distance between each leg of the trip is not independent of other legs, as each city can only be visited once. This type of problem is classified as a non-deterministic polynomial-time (NP) problem as the exact number of steps required to obtain the optimum answer cannot be predicted algorithmically. Fortunately, NP problems exhibit the characteristic of knowing when an appropriate solution has been found, as in ranking the total trip time of different routes taken in the TSP. While the exact interactions between variables “inside the box” remain unknown, the preferred output is readily observable.
The basic procedure of Holland’s GA is to first classify the problem variables as an array of inputs. As this array is analogous to a strand of biological genes, it is considered a “chromosome” of the GA. In the case of the TSP, the variables are an array of city locations whose order can be arranged to represent each possible route. Secondly, a population of chromosomes is generated randomly and the round-trip distance or “fitness” of each is calculated. Then the population undergoes a process of selection. As in nature, chromosomes consisting of gene orders producing more fit solutions have greater chances to survive and pass along their characteristics to subsequent generations, thereby retaining good portions of their solutions among the population and rejecting poor ones.
After selection, the actual process of producing the next generation of solutions involves the recombination or crossover of genes between two “parent” chromosomes followed by mutation. In the TSP, a crossover location in the chromosome array is randomly selected. The cities in the array before can be referred to as the “head,” and those after as the “tail.” One “child” chromosome is created by attaching the head of the first parent to the tail of the second. Appending the tail of the first parent to the head of the first generates a second “sibling” chromosome. In keeping with TSP rules, this process is modified to insure that each city appears only once in each chromosome. The algorithm also is commonly modified to facilitate multiple crossover locations.
To mimic the naturally occurring transcription errors resulting in revolutionary advances to better solutions, the children chromosomes are then “mutated” by changing the values at random locations in the array or, as with the TSP, swapping the values between two random locations. After which this new generation of solutions is evaluated for fitness, and the GA can continue to iterate, i.e. “evolve” or conclude if the best available solution is deemed appropriate. As the number and quantity of simulation tools continues to increase, the GA permits software to discover best available solutions to complex analysis and control problems using a very Edisonian approach.
This material originally appeared as a Contributed Editorial in Scientific Computing and Instrumentation 21:3 February 2004, pg. 16.
William L. Weaver is an Associate Professor in the Department of Integrated Science, Business, and Technology at La Salle University in Philadelphia, PA USA. He holds a B.S. Degree with Double Majors in Chemistry and Physics and earned his Ph.D. in Analytical Chemistry with expertise in Ultrafast LASER Spectroscopy. He teaches, writes, and speaks on the application of Systems Thinking to the development of New Products and Innovation.
