Inductive Solutions, Inc.
380 Rector Place, Suite 4A, New York, New York 10280

Email  Telephone: +1 (212)945.0630   Fax: +1 (212)945.0367

 

Home

Products and Services
Software Products
Recommended Books

Bibliography and White Papers
Free Downloads

Links

 

GenSheet

Genetic Algorithm FAQ
GenSheet implements genetic algorithms as fast C-coded dynamic link libraries. GenSheet supports genetic operations for binary, integer, and real, and permutation representations, and includes special commands for constrained nonlinear optimization (integer and non-linear programming), genetic classifiers, job-shop scheduling, and minimum variance portfolio computation.

Using Microsoft Excel as the user interface, all GenSheet commands are configured in an easy-to-use Excel menubar that is integrated with all standard Excel commands and charting utilities. GenSheet provides an interactive help and a tutorial that takes you through the process of building applications using genetic algorithms.

System Requirements

GenSheet requires Microsoft Excel.

Input/Output

Genetic algorithm inputs consist of your specification of an objective function to be maximized, and parameters that determine how the genetic algorithm is to "breed" improved solutions from a population of parent solutions. In GenSheet, you specify the initial population, parameters (such as number of generations and mutation rate), and other inputs directly as spreadsheet regions. GenSheet output is the display of the population after computation.

Size and Speed

GenSheet limits the population size to a maximum of 1000 individuals, having at most 256 fields. Run-time speed depends on the hardware support for floating point computation.

GenSheet supports the following algorithms and utilities:

  • Binary
    The basic genetic algorithm, representing genes as arrays of bits.
  • Integer
    Genes as arrays of integers. Useful for integer programming problems.
  • Real
    Genes as arrays of real numbers. Useful for non-linear programming.
  • Permutation
    Genes as arrays of integers, where order is significant.
  • Optimum Portfolio
    A genetic algorithm for computing a minimum variance portfolio that maximizes return.
  • Genetic Scheduler
    A genetic algorithm for sequencing a set of tasks whose order minimizes costs.
  • Genetic Classifier
    A genetic algorithm for discovering rules, based on a set of sample cases.
  • AutoScale
    Normalizes inputs to values between 0 and 1.
  • Text To Binary
    Maps text to bit vectors.
  • Numbers to Binary
    Maps numbers to bit vectors.

Licenses

The basic single-user license includes the genetic algorithm development tools integrated with the Microsoft Excel user inteface macros and dynamic link libraries; an on-line tutorial; a 100 Page Manual; function optimization templates; and sample Applications. It comes with EMail Technical Support.

Genetic Algorithms and GenSheet FAQ

What Are Genetic Algorithms?

Genetic algorithms are a set of mathematical optimization techniques that are inspired by biological evolution. They work by breeding a population of new answers from old answers with a methodology based on survival of the fittest. Over time, an initial population of answers will improve and converge to a population of optimal answers.

How Do Genetic Algorithms Differ From Other Optimization Techniques?

Mathematical optimization is concerned with the following problem: Given a complicated function f(x), find a vector M, subject to constraints C(x), such that f(M) is a Maximum. This formal statement is similar to the problem of finding the highest mountain peak in a mountain range, while hiking with a blindfold.

Conventional optimization techniques start with an initial answer -- a single guess for M -- and a way to generate new answers from old answers, based on gradient search rules. This rule is: to find a peak, keep taking steps in the direction of the steepest ascent.

Genetic algorithm techniques start with an initial population of answers -- a set of different guesses for M -- and a way to generate new answers from old answers based on rules that are inspired by genetics and evolutionary biology.

Are Genetic Algorithms Better Than Conventional Optimization Methods?

One problem with conventional gradient search rules is that they are local: since you start with a single guess, you may find a peak, but you are not guaranteed that it is the highest in the entire mountain range. Genetic search procedures are global: since you start with a population of guesses, the likelihood of finding the highest peak also depends on the size and variety of the population. The basic idea is that when two potential answers are mated in a probabilistic way, the best properties of both parents are preserved in the population. In the terminology of genetic algorithms, vector x is a chromosome and the components of x are genes. The height of the mountains is described by a fitness function: the optimal answer M corresponds to the fittest survivor of all the possible values of x. At every generation, the fittest answers are mated: the crossover operations combines different genes of both solutions into a new solution, and the mutation operations introduce a random element on genes. Hill-climbing becomes survival of the fittest.

What Is GenSheet?

GenSheet implements genetic algorithms as C programs dynamically linked to Microsoft Excel spreadsheets. In GenSheet, a gene is a spreadsheet cell, a chromosome (vector x) is range of spreadsheet cells, and a population is a rectangular region of spreadsheet cells (an array of chromosomes). GenSheet runs under all implementations of Microsoft Excel (version 4.0 or higher), including Windows, Macintosh, and Sun under Solaris. GenSheet macros interface with all Excel spreadsheet commands for charting, for spreadsheet formatting and for reporting and printing.

What Kinds of Genetic Operations are Supported by GenSheet?

GenSheet supports a comprehensive set of genetic representations, operations, and utilities, all packaged in an easy-to-use system based on Excel Menus and dialogs:
  • Numerical Representations
    Binary, Integer, Real, Permutation
  • Genetic Operations
    Uniform, Partially Matched Crossovers, Average, Coarse, Fine Crossovers, Ordinal/Positional Mutations
  • Data Preprocessing Utilities
    Representing Text and Numbers as Binary, Scaling

What Kinds of Sample Applications are Included in GenSheet?

  • Optimum Portfolio Application.
    How do you allocate the proportions in a portfolio of stocks in a way that maximizes the portfolio return and minimizes the portfolio risk? Input to GenSheet includes a vector of expected returns for the individual stocks and a covariance matrix relating the returns to each other (used to compute portfolio risk). This is a quadratic programming problem.
  • Task Scheduling Application.
    How do you schedule a sequence of tasks in a way that minimizes the total cost of the schedule? Input to GenSheet includes a vector of costs for each task, and a dependency matrix that shows if one task can be performed before the other, and if tasks can be executed concurrently. This application is a combinatorial problem related to the classic Traveling Salesman Problem.
  • Genetic Classifier Application.
    How can you learn rules from a set of examples? Input to GenSheet includes a region of cases; output shows the induced rules, listed by strength.

    How do you use GenSheet to Solve a Problem?

    If you are familiar with using a spreadsheet, then you will very quickly recognize GenSheet's ability to solve your most difficult optimization problems efficiently. Three steps to solving a problem with a genetic algorithm process:
    1. Represent the problem in terms of maximizing a Fitness Function.
      Create a fitness function based any spreadsheet formulas. Function arguments can be either bits, integers, real numbers, or integer orderings (permutations). The representation you select for the fitness function specifies the type of genetic algorithm. Define bounds for each argument. Incorporate complex constraints in the fitness function. If you are using one of the predefined GenSheet applications, the fitness function is already specified for you.
    2. Set the Parameters for the Genetic Algorithm on the Spreadsheet.
      Set the parameters in the Parameter Region on the spreadsheet. All GenSheet algorithms and applications have defaults for all parameters displayed in a Parameter Region.
    3. Iterate.
      If you have designed your own fitness function, set the number of generations to the number of iterations in the Excel Calculation... menu. If you are using a predefined GenSheet application, set the generations to the #Runs parameter in the spreadsheet Parameter Region.

Purchase Student Version

 

 

 

(c) 2006 Inductive Solutions, Inc. All rights reserved.