August 1999
Evolver 4.0Genetic algorithm super solver can be applied successfully to many classes of problems
By Paul K. Bergey and Cliff T. Ragsdale
For many readers of OR/MS Today, the 1990s will be remembered as a revolutionary decade in which the tools of OR/MS were made accessible to the masses via the power of spreadsheets. The Palisade Corporation of Newfield, N.Y., will undoubtedly be remembered as one of the driving forces behind this revolution, having brought us @RISK for spreadsheet simulation, PrecisionTree for spreadsheet-based decision analysis, and several other related products.
The latest offering from Palisade is Evolver 4.0, an add-in that gives Microsoft Excel the ability to solve constrained optimization problems using genetic algorithms (GAs). GAs represent a powerful, general-purpose optimization paradigm where the computational process mimics the theory of biological evolution [1] [2]. In a nutshell, GAs start with a set of chromosomes (numeric vectors) representing possible solutions to a problem. The individual components (numeric values) within a chromosome are referred to as genes. New chromosomes are created by crossover (the probabilistic exchange of values between vectors) or mutation (the random replacement of values in a vector). Chromosomes are then evaluated according to a fitness (or objective) function with the fittest surviving into the next generation. The result is a gene pool that evolves over time to produce better and better solutions to a problem.
To a certain extent, Evolver picks up where Excel's built-in Solver leaves off. Solver uses a deterministic, hill-climbing type of algorithm that works optimally on linear problems and quite well on nonlinear problems with smooth landscapes. However, for nonlinear problems, the solution Solver generates depends on the starting point and may be a local rather than global optimum. Also, Solver tends to have difficulty solving problems with discontinuities and unsmooth landscapes which are typical of spreadsheet models employing logical If-Then statements and/or Lookup tables. While Evolver cannot completely avoid the possibility of becoming trapped at a local optimal solution, its use of a randomized initial gene pool and probabilistic crossover and mutation operators make this occurrence less likely. Moreover, Evolver can optimize virtually any spreadsheet model — even those containing If-Then statements, Lookup tables and custom macro functions.
Operational Overview
Evolver's interface exploits the general purpose modeling capabilities of spreadsheets to enhance the problem-solving capabilities of GAs. Those familiar with Solver will recognize similarities with the Evolver interface. Figure 1 shows Palisade's implementation of a traveling salesman problem.
Figure 1: The Primary Evolver Interface.
To use Evolver, one first builds a complete model within a spreadsheet, using all of the built in functionality of Excel to define an appropriate fitness function. The next step is to tell Evolver the location of the target cell which contains the fitness function and specify the improving direction (maximize or minimize). The fitness values provide feedback to the evolutionary engine used to drive the pool of possible solutions in a maximizing or minimizing direction. The next step requires the user to specify the location of the input values (adjustable cells). Evolver will manipulate these cells in an attempt to create better solutions. The final step involves defining the constraints of the model. Evolver allows for three types of constraints: soft, hard and range. Evolver Watcher (see Figure 2) is a feature that monitors all activity during the solution of a model. It provides a real-time view of the optimization process and allows the user to alter parameter settings that control the progress of evolution.
Figure 2: Evolver Watcher.
Evolver Watcher provides four visual representations of an optimization run. The Progress Chart indicates the best solution found so far along with the average solution in the current population. The Color Table represents the different values of the genes within each dimension of the current population using a different color. For example, a column of solid colors would indicate that all of the gene values in the given dimension (or decision variable) are the same, while many different colors represent differing gene values. This is an indication of the amount of diversity within the current population. The Bar graph shows the fitness function values of the chromosomes in the current population from best to worst. Finally, the population Grid chart shows the values of each gene in the population, allowing the user to capture a "snapshot" of the data.
At the completion of an optimization run, summary information can be collected easily with the Evolver optimization log in the main program, or with the Evolver Watcher report-generating feature. Both logs contain a report on the best solution found, the optimization settings, and various other relevant statistics about the run.
Potential for use in the OR/MS community
Evolver 4.0 would make a great addition to any OR/MS professional's toolkit. Equipped with a variety of crossover and mutation operators that can be combined to satisfy the characteristics of each problem, Evolver can readily model and solve problems in scheduling, resource allocation, product mix, engineering design, and a variety of other traditional OR/MS problems. Evolver also provides the following solving methods, each designed to handle adjustable cells with certain characteristics.
- RECIPE - The Recipe method allows variables to be changed independently of each other, like combining ingredients in a recipe. It can be used for things like portfolio optimization or determining the most profitable product mix.
- ORDER - An order is a permutation of a list of items, where you are trying to find the best way to arrange a set of given values. This method can be used to assign workers to tasks or optimize other sorting problems with an ordered list of elements.
- GROUPING - The Grouping method assigns variables into sets. This method can be used to select elements for a collection such as in portfolio balancing and bin packing problems.
- BUDGET - The Budget method is similar to Recipe except that all of the variables' values must total a number. This method is designed to run budget calculations or assign resource allocations with a Recipe solution in which the total is kept constant.
- PROJECT - The Project method is similar to Order except that some elements must precede others. This method can be used in project management to rearrange the order in which tasks are carried out, but the order will always meet the precedence constraints.
- SCHEDULE - The Schedule method is similar to Grouping except that it assigns elements to blocks of times while meeting certain constraints. This can be used to assign workers or courses to time periods or schedule meetings.
Quality of documentation and support
The Evolver User's Guide provides a comprehensive explanation of all of the dialog boxes and toolbar commands necessary to run the program as well as a general overview of optimization and GAs. It also includes a fully indexed reference guide describing examples of how the various solving methods can be applied.
Unfortunately, we encountered a few errors and omissions in the documentation that proved to be quite frustrating. However, we found the technical support personnel at Palisade to be professional, competent and responsive to our questions.
Quality of implementation
The Industrial version of Evolver 4.0 was provided for this review. We found it to be a top-quality package from both a performance and usability point of view. The Evolver installation process is smooth and simple. Evolver can also be integrated with the other packages in the Palisade DecisionTools Suite during installation.
The developers of Evolver have given significant consideration to the multitude of alternatives available in constructing a genetic representation of a complex problem. They have organized the dialogs as a series of wizards that follow the standard Microsoft programming conventions. Users with a cursory understanding of the GA modeling paradigm are likely to find the dialogs friendly and intuitive.
Other features
Some problems that an analyst may wish to solve may be too large to model with a spreadsheet. Also, programmers may wish to design Evolver models that are completely hidden from the user's view with a custom interface. The Professional and Industrial versions of Evolver include the Evolver Developer's Kit (EDK), which comes with its own diskette and manual. It allows analysts to access Evolver from other applications and develop stand-alone applications that do not involve Excel. The EDK can be used with any Windows program or programming environment that can access Dynamic Link Libraries (DLLs). This includes languages such as Visual Basic, C++ and Delphi. This enables owners of the Professional or Industrial versions of Evolver to develop and distribute custom programs that use the Evolver engine. EDK users who develop and distribute applications using Evolver DLL files should contact Palisade about licensing fee agreements to fit their needs.
Technical soundness
To evaluate the technical soundness of Evolver, we exposed the system to a variety of problems that should provide insight regarding the general performance capabilities of the package. As described below, we implemented performance testing in the continuous domain using a modified DeJong test suite. To test Evolver in the discrete domain, we used the Traveling Salesman Problem (TSP). All reported testing was conducted on a Dell 2100 Power Edge Server running Windows NT Server 4.0 with a Pentium-200 processor, 128 MB of RAM and SCSI components.
The DeJong Test Suite
The DeJong test suite is a classic set of continuous functions that is considered by many to be the minimum standard for performance comparisons of evolutionary algorithms. DeJong selected a set of five functions that isolate the common difficulties found in many optimization problems. These functions are described briefly below and in greater detail in Figure 3.
1. The Sphere Function. This three-dimensional function is a simple, non-linear, convex, unimodal, symmetric function that poses very little difficulty for most optimization methods. The sphere is intended to be a performance measure of the general efficiency of an algorithm.
2. Rosenbrock's Saddle. This two-dimensional function can be quite difficult for algorithms that are unable to identify promising search directions with little information. The difficulty lies in transiting a sharp, narrow ridge that runs along the top of the saddle in the shape of a parabola.
3. The Step Function. This five-dimensional function consists of many flat plateaus with uniform, steep ridges. This function poses considerable difficulty for algorithms that require gradient information to determine a search direction.
4. The Quartic Function. This 30-dimensional function includes a random noise variable that ensures the function never evaluates to exactly the same value for the same solution vector. Thus, the quartic function tests an algorithm's ability to locate the global optimum for a simple unimodal function that is padded heavily with noise.
5. Shekel's Foxholes. This two-dimensional function contains many (i.e., 25) foxholes of varying depth surrounded by a relatively flat surface. Many algorithms will become stuck in the first foxhole they fall into.
In Figure 3, we report the average number of function evaluations and average cpu time required to find solutions for 20 replications of each DeJong function. In each test case, Evolver was able to locate the global optimum. It is significant to note, however, that we found it necessary to utilize Evolver's auto-mutation feature and the auto-select operator feature in order to optimize most of the test functions. Because these features are only included with the Professional and Industrial versions, users of the Standard version may find their system to be less robust for optimizing complex functions.
DeJong Function |
|||||
| Performance Criteria | 1 | 2 | 3 | 4 | 5 |
| Avg. # of function evaluations | 33,897 | 20,859 | 147 | 17,113 | 3,772 |
| % of runs where global was found | 100% | 100% | 100% | 100% | 100% |
| Avg. time to global solution (mm:ss) | 02:06 | 01:03 | 00:01 | 04:57 | 00:38 |
Figure 3: DeJong test suite results.
It is also interesting to note that, on average, Evolver required over two minutes of cpu time to locate the minimum value for the sphere functions. In contrast, Solver can locate the optimal solution to these simple, convex problems in a matter of seconds. This illustrates the point that Evolver is not a replacement for Solver but rather an additional tool whose power and worth becomes evident in problems with discontinuities and unsmooth landscapes.
Figure 4 reports the relevant Evolver control settings used in this experiment. A population size of 50 was selected because it is the default value provided by Evolver and thus the most likely first choice to be tried by a new user. As a general rule of thumb, problems of higher dimension benefit from larger population sizes. Evolver does not include an automated feature for varying population size during an optimization (though this can be adjusted manually during a run using Evolver Watcher). Such an enhancement would likely improve the overall efficiency and effectiveness of the package.
| Control Parameter | Setting |
| Population Size | 50 |
| Solution Method | Recipe |
| Crossover Rate | .5 |
| Mutation Rate | auto-mutation |
| Optional Operators | Select all operators available (auto-select) |
| Stopping Criteria | Global solution found within the specified tolerance |
| Screen Updating | Off |
Figure 4: Evolver settings for the DeJong test suite.
The Traveling Salesman Problem
We tested Evolver's optimization capability in the discrete domain by solving a series of symmetric TSPs. Because TSPs are NP-complete, most algorithms have difficulty finding global optimal solutions for medium- or large-size problems in a reasonable amount of time. Thus, from a practical point of view, we are interested in determining how close Evolver can come to the global optimal solution in a reasonable amount of time.
In Figure 5 we report the average results from 20 trial runs for each TSP tested. Each run terminated due to one of the following stopping criteria: 1) the optimal solution was found, or 2) convergence occurred. Here, the population size and the convergence criteria were varied with the number of cities in each model by factors of 10 and 100, respectively. In all test cases, convergence is defined as less than 1 percent improvement in the objective function value in the last 10 generations. Figure 6 reports the relevant Evolver control settings used in these experiments.
Number of Cities |
||||||||
| Performance Criteria | 5 | 10 | 15 | 20 | 29 | 48 | 76 | 100 |
| Avg. # of function evaluations | 9 | 518 | 1,732 | 2,774 | 6,175 | 24,192 | 43,900 | 56,340 |
| % of runs where global was found | 100% | 35% | 20% | 0% | 0% | 0% | 0% | 0% |
| Avg, time to best solution (mm:ss) | 0:01 | 0:02 | 0:07 | 0:12 | 0:36 | 3:00 | 7:24 | 12:38 |
| Avg. % deviation from optimal | 0% | 3% | 3% | 6% | 11% | 12% | 15% | 17% |
Figure 5: TSP test results.
| Control Parameter | Setting |
| Population Size | 10* Number of Cities |
| Solution Method | Order |
| Crossover Rate | .5 |
| Mutation Rate | auto-mutation |
| Optional Operators | Select all operators available (auto-select) |
| Stopping Criteria | 1. Global solution found or 2. Less than 1% improvement in last 100* Number of Cities trials. |
| Screen Updating | Off |
Figure 6: Evolver settings for the TSP testing.
For TSPs with up to 29 cities, Evolver was able to locate an optimal or near optimal solution fairly quickly. For larger TSPs, the run-times began to increase while solution quality decreased. Thus, Evolver (and GAs in general) are not a panacea for the problem of local optima. However, it may be possible to improve the results reported here by optimizing the control parameters for each individual problem or perhaps by implementing the models in a different manner.
Concluding Remarks
Although GAs have been around for over three decades they are used by practitioners far less than conventional approaches to problem-solving. One reason for this is that GAs typically require the user to have specialized knowledge of optimization as well as strong computer programming skills. Perhaps the most significant benefit of Evolver is that it eliminates the need for any coding by the user at all. It only requires the user to build a spreadsheet model, enter parameters into the Evolver wizard and then create a suitable fitness function using the Excel spreadsheet interface.
It is significant to note, however, that regardless of the simplicity of Evolver's interface, the value of the solution produced is directly related to the user's understanding of the GA modeling paradigm and Excel's functional capabilities. In the hands of a skilled operator, Evolver can be applied successfully to many classes of problems.
While Evolver has made tremendous strides in reducing the burden of problem-solving via the GA paradigm, it has also opened the door for fast-followers within the software industry to extend the notion of GAs in spreadsheets. Given the small number of competing products that implement this concept and the tremendous flexibility of the spreadsheet interface, it is unlikely that Evolver or similar products have fully explored all of the potential value that can be gleaned from this concept. This bodes well for both practitioners and researchers who can expect to see exciting developments in this area in the future. Paul K. Bergey is a doctoral candidate in the Department of Management Science & Information Technology at Virginia Tech. He holds an M.B.A. from the College of William and Mary and a B.S. from the United States Merchant Marine Academy. Cliff T. Ragsdale is an associate professor in the same department at Virginia Tech and is author of "Spreadsheet Modeling & Decision Analysis: A Practical Introduction to Management Science" published by South-Western College Publishing.
References
- Davis, L. (ed.), "Handbook of Genetic Algorithms," Van Nostrand Reinhold, New York, NY, 1991.
- Holland, J.H., 1992, "Genetic Algorithms," Scientific American, Vol. 267, No. 1, pp. 66-72.
- Storn, R. and K. Price, 1997, "Differential Evolution - A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces," Journal of Global Optimization, Vol. 11, pp. 341-359.
Address: 31 Decker Road, Newfield, NY 14867 Phone: (607) 277-8000 or (800) 432-7475 Fax: (607) 277-8001 E-Mail: sales@palisade.com Web: http://www.palisade.com |
| Editor's note: It is the policy of OR/MS Today to allow developers of reviewed software an opportunity to clarify or comment on the review article. Following are comments from Randy Heffernan, sales manager of Palisade Corporation. For 15 years, Palisade Corporation has been the industry leader in risk and decision-analysis software tools. We are continually enhancing and expanding our product line to meet customer needs. Customer feedback is an important element in determining new features and enhancements to future versions. Other products developed by Palisade include @RISK (Monte Carlo simulation for spreadsheets), BestFit (distribution fitting), RISKview (distribution viewing), PrecisionTree (decision trees for spreadsheets), TopRank (what-if analysis for spreadsheets), the DecisionTools Suite (includes all of the above), @RISK for Project (Monte Carlo simulation for MS Project) and RISKOptimizer (optimization with Monte Carlo simulation for spreadsheets). |
Paul K. Bergey is a doctoral candidate in the Department of Management Science & Information Technology at Virginia Tech. He holds an M.B.A. from the College of William and Mary and a B.S. from the United States Merchant Marine Academy. Cliff T. Ragsdale is an associate professor in the same department at Virginia Tech and is author of "Spreadsheet Modeling & Decision Analysis: A Practical Introduction to Management Science" published by South-Western College Publishing.
OR/MS Today copyright © 1999 by the Institute for Operations Research and the Management Sciences. All rights reserved.
Lionheart Publishing, Inc.
506 Roswell Street, Suite 220, Marietta, GA 30060, USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com
URL: http://www.lionhrtpub.com
Web Site © Copyright 1999 by Lionheart Publishing, Inc. All rights reserved.