## Generator
## What Can Generator Do?Generator is a computer program that can help you solve a
wide variety of problems, whether they are complex or simple. It's
designed to interact with Microsoft Excel(tm) worksheets. Basically, if
you can define your problem in an Excel worksheet, you can use
Generator to find a solution. You can use Generator to
maximize profits, minimize costs, or solve equations. All you need is an
Excel worksheet with input variables and a single output expression which
describes the quality of a solution (eg., cost, profit, etc.). You can
use Generator to maximize profits, minimize costs, or
solve equations. Generator is designed to run on IBM
compatible computers under Windows and NT, and is Y2K compliant.
- solve complex routing and scheduling problems
- design electronic circuits
- maximize profit
- curve fit
- improve factory efficiency
- solve coupled sets of nonlinear partial differential equations
- optimize dynamic systems
Generator! It's POWERFUL!
## System RequirementsGenerator requires at least a 386 IBM(tm) compatible
computer with 2 MB of RAM, with Microsoft Windows 3.x, Windows 95 or NT,
and
Excel 4, Excel 5, Excel for Windows 95, or Office 97 {English Versions
Only!} . The
program will run considerably faster if a later model computer with more memory is used.
## Genetic AlgorithmsApplications which use genetic algorithms to solve problems are surfacing in a wide range of areas. Over 500 research articles were published in 1994 alone on genetic algorithms, and widespread interest in these computer programs is increasing. Genetic algorithms are essentially a software version of the evolutionary process. The main difference is the computer process can be greatly accelerated by fine-tuning and manipulating the evolutionary principles, where members of the population are born, mate, and die in a few microseconds. This allows for enormous change to occur rapidly.
Genetic algorithms require a set of
The inputs for the fitness function are often called
Genetic Algorithms work by starting with relatively poor trial
solutions, that is, population members with poor fitness. Three basic
processes are then allowed to occur: mating, mutation, and
selection ("survival of
the fittest"). The first process, mating, involves an exchange of
information between population members, something which is referred to as
Once the crossover has taken place, the offspring undergo
## How Generator WorksGenerator employs all of the basic evolutionary
processes: crossover, mutation, and natural selection. What
distinguishes Generator from other commercial genetic
algorithm software is that in Generator, users can
fine-tune these parameters on the fly. In addition,
Generator
has special hill climbing features, recombination operators and mate
selection processes to rapidly find the best solution.
The crossover process in
Once crossover has taken place, Generator determines
a) which population members may undergo mutation, b) which genes of these
population members will mutate, and c) how much mutation these genes will
undergo. As a user of Generator, you have full control
over these parameters, as shown from the Generator screen below:
For Random Mutation, Generator randomly selects the
population members which undergo mutation according to the Population
Mutation Probability. Generator then randomly selects
the genes that will be mutated. Population members are selected
undergo a second selection to determine which genes will be mutated,
according to the Gene Mutation Probability. Next, each gene selected
is mutated using a random number and the Percent of the Range. Once the
mutation amount has been calculated, it is either added to or subtracted from the original gene. The new value of the gene is checked to make sure that it does not go outside the specified range. The overall mutation process is shown below:
The mutation hill climbing features in Generator provide
an opportunity to find solutions fasterin certain kinds of problems. Two
types of hill climbing are provided: random mutation hill climbing, and
directional hill climbing. In random mutation hill climbing, the user
specifies how many random mutations can take place before finishing the
random mutation process. For instance, if five steps are specified, up to five mutations will occur consecutively, as long as the mutations result in improvement. Directional hill climbing, on the other hand, examines the results of the first mutation, and allows more identical mutations to occur if the first mutation resulted in improvement. The mutation strategy (random, random mutation hill climb, or directional hill climb) will depend upon the problem. The multiple strategies available in Generator give the user the flexibility needed solve the problem optimally, and strategies are fully detailed in the user's manual!The generation is complete once the "survival of the fittest" strategy is implemented at the end of the mutation process. Once the mutation process is finished, the population members are re-ordered according to their fitness. This new list is compared to the "old" list (before crossover and mutation). Members from the old list are allowed to replace members of the new list if they are better. In this fashion, if the crossover and mutation result in worse population members, the best solutions are not lost. The user is allowed to specify how many of the old population members can be carried over to the next generation. This flexibility is very important, and control of this parameter allows for much faster solution speed in some instances.
## Performance and ApplicationsBy giving the user a high level of control over the mutation and hill climbing strategies, strategies can be tailored to each problem. Detailed examples in the operator's manual provide insight and advice into specifying these parameters. By tailoring the evolutionary principles to suit each problem, large gains in performance can be obtained.Generator permits the user to control many of the features of the solution process and has advanced hill climbing features which are unavailable in our nearest competitor. As a result, Generator runs significantly faster.
## 1. Traveling Salesman ProblemThis classic problem is often the test of merit for genetic algorithms. Basically, the problem involves trying to find the shortest route between twenty cities by arranging them in the proper order. Our test runs usingGenerator resulted in an optimal solution for a
20-city problem in about 20 minutes (on a 486 DX computer).
## 2. Insecticide PlacementWe created an example problem for our user's manual where three cans of insecticide must be used to get rid of insects living in a dozen nests. The cans have a fixed "kill" radius, and placing them in different locations will either decrease or increase the number of wasps killed.## 3. Curve FittingWhen making silicon computer chips, part of the processing involves coating the silicon wafer with photoresist, and then exposing and developing the photoresist to form patterns for circuit formation. Recently, New Light Industries and other research groups have developed methods to form sub- micron sized 3-dimensional shapes in photoresist by using partial electron- beam exposure. We have used Generator to fit a photoresist depth versus electron-beam exposure curve, shown below (the blue line is the experimental data, the red line is the fit by Generator):
Finding an equation to fit the data gives a better understanding of the process and helps predict depths for different exposures. The notches on the curve are the result of different electron-beam current settings (multiple passes of a high and low current beam). Standard curve fitting routines are useless on this type of data, since the curve is not continuous. Generator, on the other hand, helped us to find the coefficients for an equation which fits the data quite well and at the same time gave us some important insights into the physical mechanisms of the process.
## 4. Thermoelectric CoolersThermoelectric coolers work by passing current through a specially designed diode. The current flowing into the diode carries less heat than the current flowing out, so the diode junction cools. The equations which govern these devices are quite complex (coupled differential equations). The situation becomes much more complex when a cascade configuration is used - that is, the thermoelectric coolers are "stacked" to create a bigger temperature drop than can be achieved for a single diode. The temperature equations for coupled thermoelectric devices consist of a large set of differential equations which depend on the working temperatures of each individual diode. When the temperatures have been correctly solved, the equations will all balance nicely. Solving for these temperatures, however, is a math nightmare.We used Generator to quickly find the set of temperatures that balance the equations. This saved us the trouble of trying to solve a large set of differential equations the hard way. ## 5. Optimal RoutingAnother example problem in our manual involves finding the best route for a power line through a city. We simulated the city by defining a 10x10 city grid, with different costs at each grid. Twenty moves were then provided on an Excel(tm) worksheet to find the best route from one end of the grid to the other. This problem contains a local optima, which tends to "trap" the solution at the wrong value.Generator is able to locate alternate solutions much better than the competition's software. Generator took an average time of 5.5 hours to find the solution.
A demo version of this program is available on the demos page.
9715 West Sunset Highway Spokane, WA 99224 Phone: 509-456-8321 FAX: 509-456-8351 |