GA Optimization for MS Excel

Description:

This program allows the user to take an Excel spreadsheet with any type of calculation data (no matter how complex) and optimize a calculation outcome (e.g. total cost). This is based on the selection of up to five design variables and up to five constraints. The optimization can be performed as a maximization, minimization or the attempt to reach a target value. Applications for this technique lie in every field of work. If the problem can be modeled in Excel, it can be optimized using this program. The main advantage of this program over the Solver, which is supplied with Excel is that it can solve highly nonlinear problems or problems that feature discontinuous functions. Both of these can be problematic for the gradient-based optimization routine that Solver is based on. The software available here is the result of a term project in a class on engineering design optimization. It was written for research and should only be used for that purpose since it may contain bugs (please report any bugs to me using the contact form). It has sufficient capability for small projects and study examples. See below for the specs. This software is provided free of charge. Two working examples have been included with the installer. Please read the terms of the license that is provided with the software before using it. This current version (v. 1.2) replaces the earlier one that was available from this site.

Introduction:

Genetic algorithms (GAs) are based on biological principles of evolution and provide an interesting alternative to "classic" gradient-based optimization methods. They are particularly useful for highly nonlinear problems and models, whose computation time is not a primary concern. Continuity of functions is not required. Similar to other methods such as Simulated Annealing, they perform better than gradient-based methods in finding a global optimum if a problem is highly nonlinear and features multiple local minima. In general, GAs approach the entire design space randomly and then improve the found design points by applying genetics-based principles and probabilistic selection criteria. Although a large number of modified algorithms are available, a GA typically proceeds in the following order:

1. Start with a finite population of randomly chosen chromosomes ("design points") in the design space. This population constitutes the first generation ("iteration").
2. Evaluate their fitness ("function value").
3. Rank the chromosomes by their fitness.
4. Apply genetic operators (mating): reproduction (reproduce chromosomes with a high fitness), cross-over (swap parts of two chromosomes, chosen based on their fitness to create their offspring) and mutation (apply a random perturbation to parts of a chromosome). All of these operators are assigned a probability of occurrence.
5. Assemble the new generation from these chromosomes and evaluate their fitness.
6. Apply genetic mating as before and iterate until convergence is achieved or the process is stopped.

A Windows user interface was created for the GA routine, which allows the user to easily use the GA model without much prior knowledge. As can be seen in the screen shots, an Excel file, which contains the calculation model, can be selected and cell references for the function value, all design variables and all constraints can be specified. On another tab, the user can modify the given GA parameters and then on a third tab, the user can run the GA algorithm and capture its output. Optionally, the user can save all GA and model parameters to a text file and restore them from there later.

Downloads:

GA Optimization for Excel v.1.2 (Build 1018) (1404 kB) Windows The program and two sample Excel files have been included in this Windows installer. NOTE: The software has only been tested with Excel XP on a Win XP Professional machine. See HELP>ABOUT for details and license information.

Quick Start Tutorial (228 kB). This document will get you going with the software. It will be included in the next revision as a help file. Paper: "Thermal and Structural Stud-Wall Optimization in Excel using Genetic Algorithms" (333 kB). This document shows some verification calculations (also provided in the download) and explains parameters and settings a bit more in detail.

Screen Shots:

Revision History:

v. 1.2 (Build 1018) (August 16, 2005):

• Accepts now 5 design variables
• Variables can be integer or real (on a per-variable basis)
• Expanded cross-over type selection dialog
• Nicer About dialog
• Added Windows installer and uninstaller
• Fixed bugs: - Implementation of decimal precision improved - Routine was only doing 1pt cross-over before, fixed now - Fixed problem with large negative values (caused hangups) - Fixed rounding problems (now scientific, not bank) - Improved constraint handling (precision-based comparison)

v. 1.0.0.10 (May 16, 2005):

• 1 Target function [minimize, maximize, target]
• 3 Variables [real only, lower / upper bounds]
• 5 Constraints ["< =", ">=", "="]
• Excel file selection
• Load / save model in text file
• Plot each chromosome in every generation option
• Application of fixed value constraint penalty
• Option to define: - Number of chromosomes - Cross-over probability - Cross-over type [1P, 2P, uniform] - Mutation probability - Random selection probability - Max. # of generations - # of preliminary runs - Max. # of generations in preliminary run - Convergence tolerance - Constraint tolerance - Numeric precision
• Installation from ZIP archive

Miscellaneous:

• Genetic Algorithm - Wikipedia page on the general topic.
• Microsoft Excel Solver - Help document.
• Related commercial software (I don't have the time to make mine commercial, so check these out for supported software):
  • Solver - From the makers of the original Excel plugin. has a hybrid evolutionary/classical solver.
  • GeneHunter - Comes in many flavors but also has an Excel interface.
  • OptWorks Excel - Also implements Simulated Annealing, Coordinate Pattern Search, Grid Search and other methods.
  • Evolver - And another one...
• UMass, MIE 616 Class, "Engineering Design Optimization"

Comments