EVSOLVE: an evolutionary algorithm

EVSOLVE uses an evolutionary algorithm to look for the global minimum, or maximum of a mathematical function of n variables, F(X), where X=(x0, x1,..., xn-1). It can also look for a root within a given range.  EVSOLVE views the numbers, x0, x1,..., xn-1, as if they were genes in a strand, X, of DNA.  A population of random strands evolves through crossover between pairs of strands, random mutation, and survival of the fittest over a number of generations. The value of F(X) is used as the measure of fitness. The trick is to evolve to a solution in as few function evaluations as possible.

Variables may be constrained to lie within a user-specified range or to take on only integer values. Guidelines for implementing more complex constraints are given in the EVSOLVE Users Guide.

EVSOLVE requires no extra software (such as Visual C++ or EXCEL). You simply present your function as a C source file, answer a few questions, and EVSOLVE does the rest.

Population Size

You specify the population size. The progeny of this population will eventually evolve to a solution. If the size is too large, the program takes needlessly long to evolve. If the size is too small, there is insufficient genetic diversity to evolve to a valid solution, despite the presence of mutations. Moreover, too small a population might produce a local, rather than global, optimum.

Convergence

After a number of generations, strands start to look increasingly alike due to inbreeding. When the best function value is sufficiently close to the worst within a generation, and their strands are similarly close, the process is said to have converged to a solution. As convergence occurs, genetic diversity diminishes and improvement finally stops.


Specifying Accuracy

When looking for a root, EVSOLVE ends when |F(X)| is less than a user-specified accuracy (e.g. .00001), or when no more improvement occurs. But when looking for a minimum or maximum, EVSOLVE must infer when to end. How close should the best and worst be? We have tried to err on the side of too much accuracy, but occasionally answers are less accurate than requested. Among the reasons for inaccurate results are:

  • The requested accuracy is impossible to attain given that a floating point number contains only 7 significant digits (15 for double precision).

  • Tiny errors in the variables can sometimes be magnified into larger inaccuracies in the function value obtained.

  • One or more genes are restricted to integer values, and this somehow precludes reaching the chosen degree of accuracy.

Part of the EVSOLVE algorithm extends and enhances a method developed by Kenneth Price, which was described by him and Rainer Storn in their article "Differential Evolution," Dr. Dobb’s Journal, April 1997. EVSOLVE was written by Bill Becker, Steve Hug and Ken Price with help from JJ Henricksen, Jim Howey and Dave Olsen.

EVSOLVE, itself, is continually evolving into a more efficient and useful program. We solicit your input. Please write, call, or email us with your questions, advice or criticisms, so that we can better meet the needs of the scientific community.