DOWNLOADABLE PRODUCT: Note that this product is available only by download. Upon placing an order, you will receive download instructions within 1 business day.
Optimization Software Using Genetic Algorithms
Wide range of business uses including manufacturing process optimization; scheduling staff members; business strategy models; finding optimal rules for decision making such as target marketing; budget optimization; scheduled machine maintenance; production scheduling optimization.
GeneHunter is a powerful software solution for optimization problems which utilizes a state-of-the-art genetic algorithm methodology. GeneHunter includes an Excel Add-In which allows the user to run an optimization problem from an Excel Release 7, Excel 97, or Excel 2000 spreadsheet, as well as a Dynamic Link Library of genetic algorithm functions that may be called from programming languages such as Microsoft® Visual Basic or C.
What Are Genetic Algorithms?
Genetic algorithms (GAs) seek to solve optimization problems using the methods of evolution, specifically survival of the fittest. In a typical optimization problem, there are a number of variables which control the process, and a formula or algorithm which combines the variables to fully model the process. The problem is then to find the values of the variables which optimize the model in some way. If the model is a formula, then we will usually be seeking the maximum or minimum value of the formula. There are many mathematical methods which can optimize problems of this nature (and very quickly) for fairly "well-behaved" problems. These traditional methods tend to break down when the problem is not so "well-behaved."
Evolution and Genetic Algorithms
Before describing how a GA can be applied to an optimization problem, let us draw the evolutionary parallel. The theory is that a population of a certain species will, after many generations, adapt to live better in its environment.
For example, if the species is an animal that lives mainly in a swampy area, it may eventually evolve with webbed feet. The reason is that the members of this population, which we call individuals, will tend to die if they are poor swimmers which cannot easily get food, and live to reproduce if they are good swimmers. The offspring of two good swimmers will probably be good swimmers because they will usually carry genetic traits of their parents, such as slight webbing between their toes. These genetic traits are carried in the chromosomes of the individuals.
How Does GeneHunter Work?
GeneHunter solves optimization problems in the same way. It will create a population of possible solutions to the problem. The individuals in this population will carry chromosomes which are the values of variables of the problem.
GeneHunter actually solves your problem by allowing the less fit individuals in the population to die, and selectively breeding the most fit individuals. The process is called selection, as in selection of the fittest. GeneHunter takes two individuals and mates them (crossover), the offspring of the mated pair will receive some of the characteristics of the mother and some of the father.
In nature, offspring often have some slight abnormalities, called mutations. Usually, these mutations are disabling and inhibit the ability of the offspring to survive, but once in a while, they improve the fitness of the individual. GeneHunter occasionally causes mutations to occur.
As GeneHunter mates fit individuals and mutates some, the population undergoes a generation change. The population will then consist of offspring plus a few of the older individuals which GeneHunter allows to survive to the next generation. These are the most fit in the population, and we will want to keep them breeding. These most fit individuals are called elite individuals. After dozens or even hundreds of "generations," a population eventually emerges wherein the individuals will solve the problem very well. In fact, the most fit (elite) individual will be an optimum or close to optimum solution.
Creating a problem solving model in GeneHunter requires that you enter the relevant data into an Excel Release 7, Excel 97, or Excel 2000 spreadsheet and specify problem solving parameters in a GeneHunter dialog screen.
The GeneHunter Dialog Screen
The GeneHunter Dialog screen enables you to identify the cells in your spreadsheet that are involved in solving your problem. You also list constraints that should be met by the solution.
Fitness Function Cell
The Fitness Function box tells GeneHunter the location of the cell which contains the formula that measures GeneHunter's success in finding a solution to your problem. The formula may be created using any of the Excel functions that are available from the Insert menu, such as average. You may also use Excel macros or Visual Basic functions to create a formula that allows you to solve very complex problems. You may even use a neural net to model the process if you don't have an appropriate mathematical formula!
If you are creating a sales application that considers variables such as advertising, distribution, and research and development budgets, the goal might be to maximize revenue, and you would want to maximize the fitness function. In another application, the goal might be to develop an oil that reaches a specified quality by adjusting the amounts of additives that go into making the oil.
Adjustable Chromosomes
Chromosomes are the variables whose values are adjusted in order to solve the problem. Their value is related in some way to the fitness function.
Chromosome Type
GeneHunter uses two types of chromosomes to solve the problems.
Continuous Chromosomes are used when the adjustable cell can take on a value that may be within a continuous range, such as the value 1.5 with the range 0 to 2. Continuous chromosomes may also be integers if you want to restrict the search space.
Enumerated Chromosomes are used when the problem involves finding an optimal combination of tasks, resources, duties, etc.
Constraints
The constraint portion of the GeneHunter dialog box allow you to do the following:
Limit the range of values that GeneHunter will search for a solution, thus limiting the time that GeneHunter will take to find an optimal solution. This is called hard constraint.
Add restrictions or subgoals to the original fitness function. This is called a soft constraint. GeneHunter attempts to find solutions that meet the soft constraints, as well as optimize the fitness function.
GeneHunter includes the following example programs in an Excel workbook.
Examples
Camping Trip - Balanced Diet Within a Budget
This example serves as a tutorial for GeneHunter. A camp leader needs to purchase the food supplies for an overnight camping trip for a group of 20 people. He has to minimize the food costs while still providing the appropriate number of servings of grains, fruits, vegetables, dairy products, meats, and sweets in order to meet the camp's recommended dietary standards.
You may have problems to solve that are similar to this one, such as minimizing the cost of an advertising budget while reaching a targeted number of people in different demographic groups by adjusting the dollars spent on different types of advertising.
GeneHunter's goal is to minimize the food cost while maximizing diet quality by varying the number of servings per person for each food group.
Portfolio
The Portfolio example is representative of many problems which require you to optimally group items with different values into sets (for example, students into academic competition teams, workers of different skills into job teams, etc.). In the example, a money manager has a list of stocks, each with a different value, that he wants to separate into six groups, based upon the specified percentages of his entire portfolio.
NYSE Prediction
In this example, GeneHunter has been used to generate rules to predict a rise in the NYSE index.
Neural Net - Bob's Deli
You will learn more about using neural networks and genetic algorithms together later on. "Bob's Deli" is just one way in which you can actually use GeneHunter to build and train a neural network without any other neural network products or algorithms.
Bob has decided to train a neural net to predict his sandwich sales so that he will have enough ingredients and staff available each day at lunch. He has been keeping records of sales for 16 weeks. He uses temperature, daily precipitation, the day of the week, and payday for the company across the street as inputs to his network.
In this example, we use GeneHunter to train Bob's neural network to predict the number of sandwiches he should be prepared to sell each day at lunchtime in his Deli. GeneHunter's genetic algorithm is used to find the network's weights.
Traveling Salesman Problem
The Traveling Salesman Problem is a well-known problem which has become a comparison benchmark test for different algorithms used to solve combinatorial optimization problems. A salesperson must make a complete closed tour of a given number of cities. All cities are connected by roads, and each city must be visited only once. GeneHunter solves this problem by minimizing the total tour length, and by changing the order of the city numbers.
Scheduler
One of the most important uses of genetic algorithms is their ability to create optimum schedules for just about any reasonable sized scheduling problem. There may be quite an opportunity for entrepreneurs to build GA schedulers for specific job scheduling environments. You can use our example as a model.
In our example, we are the manager of a small circuit board assembly plant that assembles, wires, solders and tests a number of circuit boards of different types each day. There are a total of five workstations that each board must go through, but each workstation may have several specialists on duty (or machines in the case of a fully automated shop), each of which can independently fully perform the duties of that workstation.
There are several types of circuit boards manufactured at this shop, and each type requires a different amount of time at a particular workstation. Therefore, there is the potential that some specialists or machines will have work to do at various times, because boards at the previous stations require long job times. GeneHunter creates a schedule for manufacturing the boards in a minimum amount of time.
Portfolio Optimization
The Portfolio Optimization example is more representative of a real world problem than the simple bin packing example "Portfolio". In true portfolio optimization, a trader or fund manager would seek to minimize his/her risk while simultaneously trying to maximize return. The trader does this by modeling his/her high return portfolio after an existing diversified portfolio, such as the S&P 500.
The trader picks a number of stocks, for example, that he/she believes will offer a high rate of return. The GA is used to minimize the risk by helping to adjust the portfolio so that it behaves like the more diversified S&P 500 "portfolio".
Polynomial Approximation
It is possible to use GeneHunter to find mathematical models of data, much like the models that could be built with multiple non-linear regression analysis.
The Polynomial Approximation example uses GeneHunter to determine the coefficients of five independent variables along with the power of each variable. The example could be extended to using more complicated mathematical models.
Many users want to include the power of a genetic algorithm in their applications but prefer to design their own user interface or to speed up the time that is required by Excel to compute complicated fitness functions. To meet these needs, GeneHunter also includes a complete genetic algorithm function library that is available in a Dynamic Link Library called GALIB.DLL.
The library includes functions for creating populations, evolving the populations by setting parameters such as crossover, mutation, and diversity (sometimes called "creep" in the literature), measuring the fitness values of individuals in the population, and updating the population into the next generation. The user has the option of creating individuals with either continuous or enumerated chromosomes.
Crossover, one of GeneHunter's operators, involves a process in which GeneHunter takes two fit individuals and mates them. The offspring will receive some characteristics from both parents.
Mutation is an operator that also serves to continue evolution. Instead of combining traits from two parents, however, mutation changes a single individual by randomly changing the value in one of the chromosomes. The diversity operator also changes a single individual, but changes each chromosome in small increments rather than drastically changing a single chromosome.
Extinction, another operator, allows you to destroy all but the elite of the population. It is similar to a plague destroying most of the population, and refreshing it with a large new set of individuals.
Complete Function Reference Guide
The GeneHunter manual includes a comprehensive explanation of each function, including argument descriptions, sample function calls, and a listing of related functions.
Code Listings
The manual contains separate chapters describing how to program applications with continuous and enumerated chromosomes, including detailed code listings with corresponding explanations.
Flexibility
The GALIB.DLL enables you to create applications that can simultaneously run up to 128 populations. The function MakeChromosomePool enables you to quickly create multiple similar chromosomes for applications such as optimizing the weights in a neural network. GeneHunter even allows you to mix continuous and enumerated chromosomes in a single population.
Run-Time License
Any applications you build with the GeneHunter programming interface may be distributed only within your company or specific government agency. That is, you may not allow anyone outside of your company to use it if your company purchased it (or outside of your agency if your government agency purchased it). If you purchased GeneHunter personally, you may not distribute your applications outside of your immediate family.
If you desire to sell or distribute a GeneHunter application outside of your company, agency, or family, you must negotiate a separate license from Ward Systems Group, Inc.
Example Programs
The GeneHunter distribution diskette includes the source code for three Visual Basic examples (plus C code for one example). Executable versions of these examples are installed on your computer during GeneHunter setup.
Reviews/Testimonials
PC AI Magazine: "Survival of the fittest" is the law of nature that genetic algorithms attempt to emulate. Survival of the fittest may also be the law of software marketing. GeneHunter, a new user-friendly fast-running genetic algorithm software package from Ward Systems Group, hopes to demonstrate that it is very fit indeed.
ORMS Today: "AI Trilogy is an excellent package for those who are interested in getting the results of neural networks without worrying about how the neural network works or having to make adjustments to them."
Part of line of software whose customers include 3M, AAA, AT&T, Bank of America, BMW North America, Chase Manhattan Bank, Citigroup, Coca Cola, Dell Computer, Delta Airlines, Exxon/Mobil, Federal Reserve Board, General Electric, Hewlett Packard, IBM, Merril Lynch, Microsoft, MIT, NASA, Pfizer, Procter and Gamble, Prudential Securities, Shell Oil and many more.
System Requirements
Microsoft Windows 95, 98, Windows 2000, XP, or Windows NT (Service Pack 3 or above). The GeneHunter add-in for Excel works with Release 7, Excel 97, and Excel 2000. IBM® PC or compatible computer with an 80386 or higher processor, 4 megabytes or RAM, and 1.5 megabytes of hard disk space.
Text supplied with permission from Ward Systems Group
Save $390 (over 20%) when you purchase GeneHunter as a part of the AI Trilogy!
DOWNLOADABLE PRODUCT: Note that this product is available only by download. Upon placing an order, you will receive download instructions within 1 business day.