Genetic Algorithm Optimization for MS Excel

Description

GA Optimization for MS ExcelThis software 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.

Please Note: With Office 2010, Excel’s Solver add-on actually includes a genetic algorithm (evolutionary) solver. You can read more about it here.

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

Quick Start Tutorial – 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” – This document shows some verification calculations (also provided in the download) and explains parameters and settings a bit more in detail.

This project is also now open-source on GitHub.

Screenshots

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.
  • GA in Excel – Blog post announcing the new Excel 2010 functionality
  • 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.

Links & Ads: