Palisade EVOLVER 5.5 User Manual
Guide to Using
Evolver
The Genetic Algorithm Solver
for Microsoft Excel
Version 5.5
March, 2009
Palisade Corporation
798 Cascadilla St.
Ithaca, NY USA 14850
(607) 277-8000
(607) 277-8001 (fax)
http://www.palisade.com (website)
sales@palisade.com (e-mail)
Copyright Notice
Copyright © 2009, Palisade Corporation.
Trademark Acknowledgments
Microsoft, Excel and Windows are registered trademarks of Microsoft,
Inc.
IBM is a registered trademark of International Business Machines, Inc.
Palisade, Evolver, TopRank, BestFit and RISKview are registered
trademarks of Palisade Corporation.
RISK is a trademark of Parker Brothers, Division of Tonka
Corporation and is used under license.
Table of Contents
Chapter 1: Introduction 1
Introduction.........................................................................................3
Installation Instructions.....................................................................7
Chapter 2: Background 11
What Is Evolver?...............................................................................13
Chapter 3: Evolver: Step-by-Step 19
Introduction.......................................................................................21
The Evolver Tour ..............................................................................23
Chapter 4: Example Applications 41
Introduction.......................................................................................43
Advertising Selection.......................................................................45
Alphabetize........................................................................................47
Assignment of Tasks........................................................................49
Bakery................................................................................................51
Budget Allocation.............................................................................53
Chemical Equilibrium.......................................................................55
Class Scheduler................................................................................57
Code Segmenter...............................................................................59
Dakota: Routing With Constraints..................................................63
Chapter 1: Introduction i
Job Shop Scheduling.......................................................................65
Radio Tower Location...................................................................... 67
Portfolio Balancing .......................................................................... 69
Portfolio Mix......................................................................................71
Power Stations .................................................................................73
Purchasing........................................................................................75
Salesman Problem...........................................................................77
Space Navigator............................................................................... 79
Trader ................................................................................................ 81
Transformer......................................................................................83
Transportation..................................................................................85
Chapter 5: Evolver Reference Guide 87
Model Definition Command............................................................. 89
Optimization Settings Command..................................................113
Start Optimization Command........................................................121
Utilities Commands........................................................................ 123
Evolver Watcher............................................................................. 127
Chapter 6: Optimization 137
Optimization Methods.................................................................... 139
Excel Solver....................................................................................145
Types of Problems......................................................................... 149
Chapter 7: Genetic Algorithms 153
Introduction ....................................................................................155
ii
History..............................................................................................155
A Biological Example.....................................................................158
A Digital Example ...........................................................................159
Chapter 8: Evolver Extras 163
Adding Constraints ........................................................................165
Improving Speed.............................................................................175
How Evolver's Optimization is Implemented...............................177
Appendix A: Automating Evolver 181
Appendix B: Troubleshooting / Q&A 183
Troubleshooting / Q&A ..................................................................185
Appendix C: Additional Resources 187
Glossary 195
Index 205
Chapter 1: Introduction iii
iv
Chapter 1: Introduction
Introduction.........................................................................................3
Before You Begin......................................................................................3
What the Package Includes.....................................................................3
About This Version .................................................................................3
Working with your Operating Environment ......................................4
If You Need Help .....................................................................................4
Before Calling .............................................................................4
Contacting Palisade....................................................................5
Student Versions ........................................................................6
Evolver System Requirements...............................................................6
Installation Instructions.....................................................................7
General Installation Instructions..........................................................7
Removing Evolver from Your Computer ...............................7
The DecisionTools Suite.........................................................................8
Setting Up the Evolver Icons or Shortcuts...........................................9
Macro Security Warning Message on Startup ....................................9
Other Evolver Information...................................................................10
Evolver Readme ........................................................................10
Evolver Tutorial ........................................................................10
Learning Evolver ....................................................................................10
Chapter 1: Introduction 1
Chapter 1: Introduction 2
Introduction
Evolver represents the fastest, most advanced commercial genetic
algorithm-based optimizer ever available. Evolver, through the
application of powerful genetic algorithm-based optimization
techniques, can find optimal solutions to problems which are
"unsolvable" for standard linear and non-linear optimizers. Evolver
is offered in two versions - professional and industrial - to allow you
to select the optimizer with the capacity you need
The Evolver User’s Guide
introduction to Evolver and the principles behind it, then goes on to
show several example applications of Evolver’s unique genetic
algorithm technology. This complete manual may also be used as a
fully-indexed reference guide, with a description and illustration of
each Evolver feature.
, which you are reading now, offers an
Before You Begin
Before you install and begin working with Evolver, make sure that
your Evolver package contains all the required items, and check that
your computer meets the minimum requirements for proper use.
What the Package Includes|contextid=9000
Evolver may be purchased on its own and also ships with the
DecisionTools Suite Professional and Industrial versions. The Evolver
CD-ROM contains the Evolver Excel add-in, several Evolver
examples, and a fully-indexed Evolver on-line help system. The
DecisionTools Suite Professional and Industrial versions contain all of
the above plus additional applications.
About This Version
This version of Evolver can be installed as a 32-bit program for
Microsoft Excel 2000 or higher.
Chapter 1: Introduction 3
Working with your Operating Environment
This User’s Guide assumes that you have a general knowledge of the
Windows operating system and Excel. In particular:
♦ You are familiar with your computer and using the mouse.
♦ You are familiar with terms such as icons, click, double-click, menu,
window, command and object.
♦ You understand basic concepts such as directory structures and file
naming.
If You Need Help
Technical support is provided free of charge for all registered users of
Evolver with a current maintenance plan, or is available on a per
incident charge. To ensure that you are a registered user of Evolver,
please register online at
http://www.palisade.com/support/register.asp.
If you contact us by telephone, please have your serial number and
User’s Guide ready. We can offer better technical support if you are
in front of your computer and ready to work.
Before Calling
4 Introduction
Before contacting technical support, please review the following
checklist:
• Have you referred to the on-line help?
• Have you checked this User's Guide and reviewed the on-line
multimedia tutorial?
• Have you read the README.WRI file? It contains current information
on Evolver that may not be included in the manual.
• Can you duplicate the problem consistently? Can you duplicate the
problem on a different computer or with a different model?
• Have you looked at our site on the World Wide Web? It can be found at
http://www.palisade.com. Our Web site also contains the latest FAQ
(a searchable database of tech support questions and answers) and
Evolver patches in our Technical Support section. We recommend
visiting our Web site regularly for all the latest information on Evolver
and other Palisade software.
Contacting Palisade
Palisade Corporation welcomes your questions, comments or
suggestions regarding Evolver. Contact our technical support staff
using any of the following methods:
• Email us at support@palisade.com.
• Telephone us at (607) 277-8000 any weekday from 9:00 AM to 5:00 PM,
EST. Follow the prompt to reach technical support.
• Fax us at (607) 277-8001.
• Mail us a letter at:
Technical Support
Palisade Corporation
798 Cascadilla St.
Ithaca, NY 14850 USA
If you want to contact Palisade Europe:
• Email us at support@palisade-europe.com.
• Telephone us at +44 1895425050 (UK).
• Fax us at +441895425051 (UK).
• Mail us a letter at:
Palisade Europe
31 The Green
West Drayton
Middlesex
UB7 7PN
United Kingdom
If you want to contact Palisade Asia-Pacific:
• Email us at support@palisade.com.au.
• Telephone us at +61 2 9929 9799 (AU).
• Fax us at +61 2 9954 3882 (AU).
• Mail us a letter at:
Palisade Asia-Pacific Pty Limited
Suite 101, Level 1
8 Cliff Street
Milsons Point NSW 2061
Australia
Regardless of how you contact us, please include the product name,
version and serial number. The exact version can be found by
selecting the Help About command on the Evolver menu in Excel.
Chapter 1: Introduction 5
Student Versions
Telephone support is not available with the student version of
Evolver. If you need help, we recommend the following alternatives:
♦ Consult with your professor or teaching assistant.
♦ Log on to http://www.palisade.com for answers to frequently asked
questions.
♦ Contact our technical support department via e-mail or fax.
Evolver System Requirements
System requirements for Evolver include:
• Pentium PC or faster with a hard disk.
• Microsoft Windows 2000 SP4 or higher.
• Microsoft Excel Version 2000 or higher.
6 Introduction
Installation Instructions
Evolver is an add-in program to Microsoft Excel. By adding
additional commands to the Excel menu bars, Evolver enhances the
functionality of the spreadsheet program.
General Installation Instructions
The Setup program copies the Evolver system files into a directory
you specify on your hard disk. To run the Setup program in
Windows 2000 or higher:
1) Insert the Evolver or DecisionTools Suite Professional or Industrial
version CD-ROM in your CD-ROM drive
2) Click the Start button, click Settings and then click Control Panel
3) Double-click the Add/Remove Programs icon
4) On the Install/Uninstall tab, click the Install button
5) Follow the Setup instructions on the screen
If you encounter problems while installing Evolver, verify that there
is adequate space on the drive to which you’re trying to install. After
you’ve freed up adequate space, try rerunning the installation.
Removing Evolver from Your Computer
Chapter 1: Introduction 7
If you wish to remove Evolver (along with Evolver or the
DecisionTools Suite Professional or Industrial versions) from your
computer, use the Control Panel’s Add/Remove Programs utility and
select the entry for @RISK or the DecisionTools Suite.
The DecisionTools Suite
Evolver can be used with the DecisionTools Suite, a set of products for
risk and decision analysis available from Palisade Corporation. The
default installation procedure of Evolver puts Evolver in a
subdirectory of a main “Program Files\Palisade” directory. This is
quite similar to how Excel is often installed into a subdirectory of a
“Microsoft Office” directory.
One subdirectory of the Program Files\Palisade directory will be the
Evolver directory (by default called Evolver5). This directory
contains the Evolver add-in program file (EVOLVER.XLA) plus
example models and other files necessary for Evolver to run. Another
subdirectory of Program Files\Palisade is the SYSTEM directory
which contains files needed by every program in the DecisionTools
Suite, including common help files and program libraries.
8 Installation Instructions
Setting Up the Evolver Icons or Shortcuts
In Windows, setup automatically creates a Evolver command in the
Programs menu of the Taskbar. However, if problems are
encountered during Setup, or if you wish to do this manually another
time, follow these directions:
1) Click the Start button, and then point to Settings.
2) Click Taskbar, and then click the Start Menu Programs tab.
3) Click Add, and then click Browse.
4) Locate the file EVOLVER.EXE and double click it.
5) Click Next, and then double-click the menu on which you want the
program to appear.
6) Type the name “Evolver”, and then click Finish.
Macro Security Warning Message on Startup
Microsoft Office provides several security settings (under
Tools>Macro>Security) to keep unwanted or malicious macros from
being run in Office applications. A warning message appears each
time you attempt to load a file with macros, unless you use the lowest
security setting. To keep this message from appearing every time you
run a Palisade add-in, Palisade digitally signs their add-in files. Thus,
once you have specified Palisade Corporation as a trusted source,
you can open any Palisade add-in without warning messages. To do
this:
• Click Always trust macros from this source when a Security
Warning dialog (such as the one below) is displayed when
starting Evolver.
Chapter 1: Introduction 9
Other Evolver Information
Additional information on Evolver can be found in the following
sources:
Evolver Readme
Evolver Tutorial
This file contains a quick summary of Evolver, as well as any latebreaking news or information on the latest version of your software.
View the Readme file by selecting the Windows Start Menu/
Programs/ Palisade DecisionTools/ Readmes and clicking on Evolver
5.0 – Readme. It is a good idea to read this file before using Evolver.
The Evolver on-line tutorial provides first-time users with a quick
introduction of Evolver and genetic algorithms. The presentation
takes only a few minutes to view. See the Learning Evolver section
below for information on how to access the tutorial.
Learning Evolver
The quickest way to become familiar with Evolver is by using the online Evolver Tutorial, where experts guide you through sample
models in movie format. This tutorial is a multi-media presentation
on the main features of Evolver.
The tutorial can be run by selecting the Evolver Help menu Getting
Started Tutorial command.
10 Installation Instructions
Chapter 2: Background
What Is Evolver?...............................................................................13
How does Evolver work?......................................................................14
Genetic Algorithms..................................................................14
What Is Optimization? ..........................................................................15
Why Build Excel Models?.....................................................................16
Why Use Evolver? ..................................................................................16
No More Guessing ...................................................................16
More Accurate, More Meaningful.........................................17
More Flexible.............................................................................17
More Powerful ..........................................................................17
Easier to Use ..............................................................................18
Cost Effective.............................................................................18
Chapter 2: Background 11
Chapter 2: Background 12
What Is Evolver?
The Evolver software package provides users with an easy way to
find optimal solutions to virtually any type of problem. Simply put,
Evolver finds the best inputs that produce a desired output. You can
use Evolver to find the right mix, order, or grouping of variables that
produces the highest profits, the lowest risk, or the most goods from
the least amount of materials. Evolver is most often used as an add-in
to the Microsoft Excel spreadsheet program; users set up a model of
their problem in Excel, then call up Evolver to solve it.
You must first model your problem in Excel, then describe it to the Evolver add-in.
Excel provides all of the formulas, functions, graphs, and macro
capabilities that most users need to create realistic models of their
problems. Evolver
in your model and what you are looking for, and provides the engines
that will find it. Together, they can find optimal solutions to virtually
any problem that can be modeled.
Chapter 2: Background 13
provides the interface to describe the uncertainty
How does Evolver work?
Evolver uses a proprietary set of genetic algorithms to search for
optimum solutions to a problem, along with probability distributions
and simulation to handle the uncertainty present in your model.
Genetic Algorithms
Genetic algorithms are used in Evolver to find the best solution for
your model. Genetic algorithms mimic Darwinian principles of
natural selection by creating an environment where hundreds of
possible solutions to a problem can compete with one another, and
only the “fittest” survive. Just as in biological evolution, each solution
can pass along its good “genes” through “offspring” solutions so that
the entire population of solutions will continue to evolve better
solutions.
As you may already realize, the terminology used when working with
genetic algorithms is often similar to that of its inspiration. We talk
about how “crossover” functions help focus the search for solutions,
“mutation” rates help diversify the “gene pool”, and we evaluate the
entire “population” of solutions or “organisms”. To learn more about
how Evolver’s genetic algorithm works, see Chapter 7 - Genetic
Algorithms.
14 What Is Evolver?
What Is Optimization?
Optimization is the process of trying to find the best solution to a
problem that may have many possible solutions. Most problems
involve many variables that interact based on given formulas and
constraints. For example, a company may have three manufacturing
plants, each manufacturing different quantities of different goods.
Given the cost for each plant to produce each good, the costs for each
plant to ship to each store, and the limitations of each plant, what is
the optimal way to adequately meet the demand of local retail stores
while minimizing the transportation costs? This is the sort of question
that optimization tools are designed to answer.
Optimization often deals with searching for the
combination that yields the most from given resources.
In the example above, each proposed solution would consist of a
complete list of what goods made by what manufacturing plant get
shipped in what truck to what retail store. Other examples of
optimization problems include finding out how to produce the
highest profit, the lowest cost, the most lives saved, the least noise in a
circuit, the shortest route between a set of cities, or the most effective
mix of advertising media purchases. An important subset of
optimization problems involves scheduling, where the goals may
include maximizing efficiency during a work shift or minimizing
schedule conflicts of groups meeting at different times. To learn more
about optimization, see Chapter 6 - Optimization
Chapter 2: Background 15
.
Why Build Excel Models?
To increase the efficiency of any system, we must first understand
how it behaves. This is why we construct a working model of the
system. Models are necessary abstractions when studying complex
systems, yet in order for the results to be applicable to the “realworld,” the model must not oversimplify the cause-and-effect
relationships between variables. Better software and increasingly
powerful computers allow economists to build more realistic models
of the economy, scientists to improve predictions of chemical
reactions, and business people to increase the sensitivity of their
corporate models.
In the last few years computer hardware and software programs such
as Microsoft Excel, have advanced so dramatically that virtually
anyone with a personal computer can create realistic models of
complex systems. Excel’s built-in functions, macro capabilities and
clean, intuitive interface allow beginners to model and analyze
sophisticated problems. To learn more about building a model, see
Chapter 9 - Evolver Extras
.
Why Use Evolver?
Evolver’s unique technology allows anyone with a PC and Excel for
Windows to enjoy the benefits of optimization. Before Evolver, those
who wished to increase efficiency or search for optimum solutions
had three choices: guess, use low-powered problem-solving software,
or hire experts in the optimization consulting field to design and
build customized software. Here are a few of the most important
advantages to using Evolver:
No More Guessing
16 What Is Evolver?
When you are dealing with large numbers of interacting variables,
and you are trying to find the best mix, the right order, the optimum
grouping of those variables, you may be tempted to just take an
“educated guess”. A surprising number of people assume that any
kind of modeling and analysis beyond guessing will require
complicated programming, or confusing statistical or mathematical
algorithms. A good optimized solution might save millions of
dollars, thousands of gallons of scarce fuel, months of wasted time,
etc. Now that powerful desktop computers are increasingly
affordable, and software like Excel and Evolver are readily available,
there is little reason to guess at solutions, or waste valuable time
trying out many scenarios by hand.
More Accurate, More Meaningful
More Flexible
Evolver allows you to use the entire range of Excel formulas and even
macros to build more realistic models of any system. When you use
Evolver, you do not have to “compromise” the accuracy of your
model because the algorithm you are using can not handle real world
complexities. Traditional “baby” solvers (statistical and linear
programming tools) force the user to make assumptions about the
way the variables in their problem interact, thereby forcing users to
build over-simplified, unrealistic models of their problem. By the
time the user has simplified a system enough that these solvers can be
used, the resulting solution is often too abstract to be practical. Any
problems involving large amounts of variables, non-linear functions,
lookup tables, if-then statements, database queries, or stochastic
(random) elements cannot be solved by these methods, no matter how
simply you try to design your model.
There are many solving algorithms which do a good job at solving
small, simple linear and non-linear types of problems, including hillclimbing, baby-solvers, and other mathematical methods. Even when
offered as spreadsheet add-ins, these general-purpose optimization
tools can only perform numerical optimization. For larger or more
complex problems, you may be able to write specific, customized
algorithms to get good results, but this may require a lot of research
and development. Even then, the resulting program would require
modification each time your model changed.
Not only can Evolver handle numerical problems, it is the only
commercial program in the world that can solve most combinatorial
problems. These are problems where the variables must be shuffled
around (permuted) or combined with each other. For example,
choosing the batting order for a baseball team is a combinatorial
problem; it is a question of swapping players’ positions in the lineup.
Complex scheduling problems are also combinatorial. The same
Evolver can solve all these types of problems, and many more that
nothing else can solve. Evolver’s unique genetic algorithm technology
allows it to optimize virtually any type of model; any size and any
complexity.
More Powerful
Evolver finds better solutions. Most software derives optimum
solutions mathematically and systematically. Too often these
methods are limited to taking an existing solution and searching for
the closest answer that is better. This “local” solution may be far from
the optimal solution. Evolver intelligently samples the entire realm of
possibilities, resulting in a much better “global” solution.
Chapter 2: Background 17
Easier to Use
Cost Effective
In spite of its obvious power and flexibility advantages, Evolver
remains easy to use because an understanding of the complex genetic
algorithm techniques it uses is completely unnecessary. Evolver
doesn’t care about the “nuts and bolts” of your problem; it just needs
a spreadsheet model that can evaluate how good different scenarios
are. Just select the spreadsheet cells that contain the variables and tell
Evolver what you are looking for. Evolver intelligently hides the
difficult technology, automating the “what-if” process of analyzing a
problem.
Although there have been many commercial programs developed for
mathematical programming and model-building, spreadsheets are by
far the most popular, with literally millions being sold each month.
With their intuitive row and column format, spreadsheets are easier
to set up and maintain than other dedicated packages. They are also
more compatible with other programs such as word processors and
databases, and offer more built-in formulas, formatting options,
graphing, and macro capabilities than any of the stand-alone
packages. Because Evolver is an add-in to Microsoft Excel, users have
access to the entire range of functions and development tools to easily
build more realistic models of their system.
Many companies have hired trained consultants to provide
customized optimization systems. Such systems will often perform
quite well, but may require many months and a large investment to
develop and implement. These systems are also difficult to learn, and
therefore require costly training and constant maintenance. If your
system must be altered, you may need to develop a whole new
algorithm to find optimal solutions. For a considerably smaller
investment, Evolver supplies the most powerful genetic algorithms
available and allows for quick and accurate solutions to a wide
variety of problems. Because it works in an intuitive and familiar
environment, there is virtually no costly training and maintenance.
You may even wish to add Evolver’s optimization power to your own
custom programs. In just a few days, you could use Visual Basic to
develop your own scheduling, distribution, manufacturing or
financial management system. See the Evolver Developer Kit for
details on developing an Evolver-based application.
18 What Is Evolver?
Chapter 3: Evolver: Step-by-Step
Introduction.......................................................................................21
The Evolver Tour ..............................................................................23
Starting Evolver......................................................................................23
The Evolver Toolbar.................................................................23
Opening an Example Model...................................................23
The Evolver Model Dialog ...................................................................24
Selecting the Target Cell.......................................................................25
Adding Adjustable Cell Ranges..........................................................25
Selecting a Solving Method....................................................27
Constraints ..............................................................................................28
Adding a Constraint.................................................................29
Simple Range of Values and Formula Constraints............29
Other Evolver Options ..........................................................................32
Stopping Conditions................................................................32
View Options ............................................................................34
Running the Optimization...................................................................35
The Evolver Watcher................................................................36
Stopping the Optimization.....................................................37
Summary Report.......................................................................38
Placing the Results in Your Model........................................39
Chapter 3: Evolver: Step-by-Step 19
20
Introduction
In this chapter, we will take you through an entire Evolver
optimization one step at a time. If you do not have Evolver installed
on your hard drive, please refer to the installation section of Chapter
1: Introduction and install Evolver before you begin this tutorial.
We will start by opening a pre-made spreadsheet model, and then we
will define the problem to Evolver using probability distributions and
the Evolver dialogs. Finally we will oversee Evolver’s progress as it is
searching for solutions, and explore some of the many options in the
Evolver Watcher. For additional information about any specific topic,
see the index at the back of this manual, or refer to Chapter 5: Evolver
Reference.
NOTE: The screens shown below are from Excel 2007. If you are using
other versions of Excel, your windows may appear slightly different
from the pictures.
The problem-solving process begins with a model that accurately
represents your problem. Your model must be able to evaluate a
given set of input values (adjustable cells) and produce a numerical
rating of how well those inputs solve the problem (the evaluation or
“fitness” function). As Evolver searches for solutions, this fitness
function provides feedback, telling Evolver how good or bad each
guess is, thereby allowing Evolver to breed increasingly better
guesses. When you create a model of your problem you must pay
close attention to the fitness function, because Evolver will be doing
everything it can to maximize (or minimize) this cell.
Chapter 3: Evolver: Step-by-Step 21
22 Introduction
The Evolver Tour
Starting Evolver
To start Evolver, either: 1) click the Evolver icon in your Windows
desktop, or 2) select Palisade DecisionTools then Evolver 5.0 in the
Windows Start menu Programs entries. Each of these methods starts
both Microsoft Excel and Evolver.
The Evolver Toolbar
Opening an Example Model
When Evolver is loaded, a new Evolver ribbon or toolbar is visible in
Excel. This toolbar contains buttons which can be used to specify
Evolver settings and start, pause, and stop optimizations.
To review the features of Evolver, you'll examine an example model
that was installed when you installed Evolver. To do this:
1) Open the Bakery–TutorialWalkthrough.XLS worksheet using
the Help menu Example Spreadsheets command.
Chapter 3: Evolver: Step-by-Step 23
This example sheet contains a simple profit maximization problem for
a bakery business. Your bakery produces 6 bread products. You are
the bakery manager and track revenues, costs, and profits from
production. You are to determine the number of cases for each type
of bread that maximizes total profit while satisfying production limit
guidelines. The guidelines you face include 1) meeting the production
quota for low calorie bread, 2) maintaining an acceptable ratio of high fiber
to low calorie, 3) maintaining an acceptable ratio of 5 grain to low calorie,
and 4) keeping production time within limits for person hours used.
The Evolver Model Dialog
To set the Evolver options for this worksheet:
1) Click the Evolver Model icon on the Evolver toolbar (the one on
the far left).
This displays the following Evolver Model dialog box:
The Evolver Model Dialog is designed so users can describe their
problem in a simple, straightforward way. In our tutorial example, we
are trying to find the number of cases to produce for the different
bread products in order to maximize overall total profit.
24 The Evolver Tour
Loading...