Introduction
“Survival of the fittest” is a familiar concept that has a proven track record in many fields including business and evolutionary biology. The principles of evolution and heredity can also be used to solve a wide range of computing problems known as optimization problems. The most well known of these types of problems is the traveling salesman problem, but numerous other applications include financial analysis, inventory management, and scheduling. In this article, I will describe what genetic algorithms are and how they work. I will present a genetic algorithm template class and two example programs that solve some classic optimization problems using this template class. But first, I’d like to provide a little background on the type of problem that I am trying to solve.
Optimization Problems
The typical mathematical expression for the general optimization problem looks something this:
Maximize f(x1, x2,..xk)
Subject to the following constraints:
h1(x1,x2,..xk) <= 0 h2(x1,x2,..xk) <= 0 . . hm(x1,x2,..xk) <= 0 hm+1(x1,x2,..xk) = 0 . . hm+n(x1,x2,..xk) = 0
The f(x1..) expression is called the objective function. The objective function can be just about anything you can calculate that depends on x, like the rate of return on an investment or the number of wires in a circuit. If it’s a function that you’d like to minimize, then you can simply put a minus sign in front of it. The constraints can be equalities or inequalities involving continuous or discrete variables, and the constraint logic can be arbitrarily complex.
In addition to genetic algorithms, a number of different approaches exist for solving these types of problems. They can be roughly classified as either mathematical programming algorithms or heuristic search algorithms. Mathematical programming algorithms include linear and non-linear programming. These algorithms rely on the mathematical properties of smooth and continuous mathematical functions. Because of this, their applicability is narrow, but they are usually more computationally efficient. In fact, these algorithms were often the only feasible approach to take back in the days when computing resources were more limited. Given the dramatic increases in processing power and memory today, it is often more practical to use heuristic search algorithms. Heuristic search algorithms include “simulated annealing” and “tabu search,” and they are widely used for solving complex optimization problems today. Heuristic search approaches are very good at exploring the local optimum points in the objective function, and they can be adapted to suit many different types of problems.
Genetic algorithms offer several advantages over these techniques. A genetic algorithm keeps track of multiple independent solutions to the problem, so it easily lends itself to parallel computing possibilities. While heuristic search algorithms require you to write very problem-specific code to come up with a good solution, genetic algorithms rely on the forces of random mutation and the process of natural selection to guide the solution of the problem.
Another advantage of a genetic algorithm is its broad searching capabilities. Figure 1 illustrates an objective function that has many hills and valleys. There are many local optima within the bounded area. Finding the global minimum for a function like this is usually not a simple matter. While other techniques could become hopelessly lost within one or two of these valleys, genetic algorithms are able to conduct a broader search of the area, exploring many local optima.
On the down side, genetic algorithms have a more difficult time conducting a deep search of the local optimum. Also, there is no direct way to model the problem constraints. But this problem can be handled in several different ways, as you will see.
The Genetic Algorithm
A subtle distinction is sometimes made between the terms “genetic algorithm” and “evolution program.” The term “genetic algorithm” usually refers to a very specific approach where the optimization problem is represented as a bit string and genetic operations like mutation are carried out in a bit-wise fashion. Evolution program implies something a little more abstract where the problem can be represented in its more natural form rather than as a bit string, and the genetic operators can be customized to suit the problem. I will illustrate examples of both these approaches, but I will stick to the term “genetic algorithm” throughout.
For the moment, consider our objective function without the constraints:
Maximize f(x1, x2,...xk)
We are looking for a vector that maximizes this function. The individual elements x1,x2..xk of the vector can be Boolean, integer, or floating point. In the classical genetic algorithm, this vector is represented as a bit string. If all the elements are Boolean or integer, then this representation is pretty straightforward. For example, if you have a three-element vector where x1 and x2 are Boolean and x3 is an integer between 0 and 15, then this can be represented with as a six-bit string where the first two bits represent x1 and x2 and the remaining four bits represent x3. Depending on the desired precision and the range, floating-point numbers can also be handled this way. But for problems involving a lot of high-precision floating-point numbers, it is often more practical to use a modified version of the algorithm that works directly with floats.
Every possible bit string is a potential solution to my problem, and the GA algorithm maintains an entire population of potential solutions. Each of these potential solution bit strings in the population is called a genome. It is also sometimes referred to as a chromosome. The classical genetic algorithm uses a bit-string representation so that it can efficiently apply genetic operators like crossover and mutation to this population of genomes.
The first step in the algorithm is to initialize the population of genomes with random values and then evaluate the fitness of each using the objective function f. The fitness value is a measure of a genome’s probability of being selected for the next generation of genomes. Once the selections are made, you have a new generation of genomes. A fraction of these genomes are chosen to crossover or mate with each other to form offspring. A much smaller fraction of the resulting population is then chosen to undergo random mutation, and the entire process is repeated for some fixed number of generations. During this process, the algorithm keeps track of the best individual genome ever found and saves it as the final result.
To experiment with genetic algorithms in my own work, I’ve implemented a genetic algorithm class library. One of the key components in the library is the class template GASolver that actually implements the algorithm. Listing 1 shows the GASolver class template. The template type T that is referenced by this class must be derived from either the GAGenome class or the GABitStringGenome class also provided by the library. Before discussing the details of the genome classes, I’ll review the GA algorithm in Listing 1.
The Solve routine is the main routine in the algorithm. The first step is to initialize a population of m_popSize genomes and evaluate them. The Evaluate function computes the objective function value for each genome in the population and uses this to calculate a fitness value for each genome. For each new generation of genome, the Select routine selects the fittest genes in the population and eliminates the least fit. The Crossover routine brings together pairs of genomes and swaps genetic information between the pairs to create offspring that replace the parents. The Mutate function randomly mutates a fraction of these genomes to form the new population. Finally, the Evaluate function is called again, and the entire process is repeated for m_nGenerations.
The most powerful aspect of GA is that it deals with multiple solutions to the problem. By combining different traits of both strong and weak individuals, it can create super strong individuals through a process of incremental changes to the population. Just like in evolution, the driving force behind this process is selection. The Select routine chooses individuals based on fitness, and just like natural selection, there is a certain degree of randomness to the selections that it makes. Consider the following example, using a small population of five genomes gi(i=1,5). There are several different ways to calculate fitness, but the most simple measure of fitness is the objective function value itself. Suppose the objective function values for each of these genomes is:
f(g1) = 10 f(g2) = 30 f(g3) = 35 f(g4) = 10 f(g5) = 15
If this is a maximization problem, then the strongest individuals in this group are g2 and g3. How does the Select routine increase the odds that these individuals will be selected for the next generation? The Select routine creates a virtual roulette wheel, and it allows the strongest individuals to play more spaces on that wheel, but nearly everyone gets a chance to continue on.
The roulette wheel works as follows. The fitness values of all the individuals in the population are added up. In this case, the sum total is (conveniently) 100. Each fitness value is divided by the sum total, and this is the probability that they will be selected. Before you begin spinning the wheel, probability numbers are assigned in increasing order. For example:
f(g1) = 0.10 + 0.00 = 0.10 f(g2) = 0.30 + 0.10 = 0.40 f(g3) = 0.35 + 0.40 = 0.75 f(g4) = 0.10 + 0.75 = 0.85 f(g5) = 0.15 + 0.85 = 1.00
The Select routine spins the wheel m_popSize times. In this example, the wheel is spun 5 times, and each time a random number between 0 and 1 is generated. If it’s a number between 0.1 and 0.4, then g2 is selected. If it’s a number between 0.85 and 1.00, then g5 is selected. The most fit individuals are often selected many times and they are allowed to make that many copies of themselves in the next generation. The least fit are often not selected at all. The multiple-copy individuals will naturally replace these unfortunate few.
The Evalute routine calculates the fitness of each individual. There are several different ways to calculate fitness. This simplest method is to use the objective function itself, but this doesn’t always work very well as the following example illustrates. Suppose that the objective function value for your group of five individuals is:
f(g1) = 1010 f(g2) = 1030 f(g3) = 1035 f(g4) = 1010 f(g5) = 1015
In this case, the values are much closer in magnitude, so everyone has roughly a 20 percent chance of being selected. You need a better way to differentiate between relative fitness. The Evaluate routine does this by using some simple statistics. The Evaluate routine calculates the average and the standard deviation of the objective function and calculates a constant that is some number of standard deviations less than the average. It subtracts this constant from the objective function for a more discerning fitness value. In the example above, the average is 1,020. The standard deviation is approximately 12. If you select a sigma of 1.5 standard deviations, then the constant is 1020 - 1.5*12 = 1002. So the new fitness values are:
f(g1) = 1010 - 1002 = 8 f(g2) = 1030 - 1002 = 28 f(g3) = 1035 - 1002 = 33 f(g4) = 1010 - 1002 = 8 f(g4) = 1015 - 1002 = 13
And once again, there are strong differences between the individuals in the population. It’s possible for an individual to fall outside the sigma, yielding a negative fitness value. In that case, you simply set it to zero and that individual has no chance of being included in the next generation. This fitness calculation is called sigma truncation, and it has an additional benefit. It allows you to optimize for the minimum rather than the maximum if you choose. You simply rearrange the terms in the fitness function:
fitness(i) = f(gi) - (favg - sigma*stdDev) to find the max fitness(i) = favg + sigma*stdDev - f(gi) to find the min </p>
The GASolver class template has functions to support both minimization and maximization.
Genetic Operators
GASolver controls the frequency of mutation and crossover operations through the m_mutation and m_cross probability parameters. But it doesn’t control how these operations are carried out. The genome class must provide functions for crossover and mutation. Listing 2 shows the genome classes (GAGenome and GABitStringGenome) provided by this class library. GABitStringGenome supports the classic bit-string operators for crossover and mutation. With GAGenome on the other hand, you must override one of these classes to solve your specific optimization problem. I will demonstrate this shortly, but first let’s talk about crossover and mutation operations.
The classic crossover operation in GA is called single-point crossover, and it’s fairly simple. In this example, you start with two parent string genomes that are 10 bits long:
Position 0123456789 g1 0100110101 g2 1110001111
Next, you pick a crossover position within the bit string at random. Take bit position 5 as an example. In the crossover operation, you swap bits between the two genomes at position 5 and beyond. The resulting offspring in this case would be:
Position 0123456789 g1' 0100101111 g2' 1110010101
Multipoint crossover is a variation of this same theme, and it allows the two genes to swap multiple random segments of information. Crossover operations need not be bit-wise operations at all and can be customized to suit the individual optimization problem. This is referred to as structural crossover, where two genomes exchange information in a more natural and structured fashion.
The classic mutation operation is even simpler. For every bit within the genome, you generate a random number between 0.00 and 1.00. If this random number is smaller than the m_mutation probability, then the bit is flipped. A typical value for m_mutation is 0.01, and a typical value for probability of crossover m_cross is 0.30.
GABitStringGenome supports these operations, and the following example demonstrates how to use this class to solve a classic optimization problem called the 0/1 Knapsack problem.
The 0/1 Knapsack Problem
There are many practical examples of this problem, but the name itself comes from the far-fetched notion of a camper who is going on a hike and must use her analytic powers to decide which items to bring. She can only carry a maximum amount of weight, but each item has a different weight and a different value to her. The problem is to maximize the value without exceeding the weight capacity constraint. Typical examples of this problem are NP-hard, and many have been solved using both heuristic search and genetic algorithms.
To solve this problem, I derived a knapsack genome class KSGenome from the GABitStringGenome class. Listing 3 shows the KSGenome class. Each bit in the bit string determines if a specific item is included in the knapsack. Static member arrays are used to store the profits and weights of each item. The classic crossover and mutation functions provided by the GABitString class were used. Only the Evaluate function had to be overridden. The Evaluate function uses this profit and weight data to calculate the objective function. In order to satisfy the weight capacity constraint, a penalty function is used to penalize solutions that exceed the weight capacity.
Penalty functions are one possible way to deal with constraints in GA. Another approach is to include a repair algorithm in the crossover and mutation operators to fix the solution if it breaks a constraint. These approaches to solving knapsack problems with GA are extensively discussed in [1], which provides a good chapter on handling constraints in genetic algorithms.
I wrote a test driver that can generate random values of profits and weights for a specified number of items. Using 40 items where the profits and weight can vary independently by as much 50 percent, the GASolver found an optimal solution in less than 1,000 generations using a population size of 200. The mutation probability was set to 0.01, and the crossover probability was 0.4. The fitness sigma was set to 1.5. The solution is believed to be optimal since no better solutions were found in 10,000 generations. The bit strings were initialized at random, so no problem-specific heuristic code was really needed to obtain this solution.
The Condo Assignment Problem
A few months ago, I wrote an article [2] on solving optimization problems using simulated annealing. In that article, I solved the following example problem.
A ski resort sells time-share contracts that allow the time-share condo owners to choose which week of the year they would like to stay. In this problem, each condo building contains four identical condo units. Each condo owner owns 1 week during a 16-week ski season for a total of 64 owners per building. During any given week, 4 different owners and their family members occupy the building. Due to local fire and safety regulations, the maximum number of occupants (owners plus family members) in each building is 22.
The owners do not buy a fixed week. Rather they must request a specific week each year, and they may not get their first choice, because 5 of the 16 weeks are twice as popular as the others. They are each obliged to make first, second, and third choices, several months in advance of their ski trip. When an owner doesn’t get their first choice, the entire family is compensated with a number of free lift tickets (two free lift tickets for each family member when you get a second choice; four free lift tickets for a third choice). In order to best satisfy the owners and also to sell more tickets, the resort seeks to minimize the total number of free lift ticket giveaways. It is possible for an owner to get none of his three choices, so you must associate a cost with this possibility. When this happens, the owner is given the choice to stay in a renter’s building for that week or to accept the algorithm’s assignment along with a cash incentive and seven days of free skiing.
This problem is a sort of partitioning problem similar to the graph-coloring problem. Having solved this problem with simulated annealing, I wanted to solve this same problem using a genetic algorithm to get a feeling for how these two different approaches compare. First, I tried to solve it using the classic GA algorithm just like the knapsack problem. I had some trouble modeling all the constraints with penalty functions. I had to abandon the classic GABitStringGenome and wound up rolling my own genome. TSGenome is derived directly from GAGenome, and it does not use bit strings to represent the problem. Instead it uses a simply array of integers (m_assign) to represent which week each owner is assigned to and another array (m_period) that contains that same information sorted by week. It does not use classical genetic operators for mutation and crossover, which merely flips bits at random to generate solutions. It has its own Mutate and Crossover functions, which are better able to maintain the constraints. While these customized functions use some randomness to generate solutions, they are also aware of the four owners per building per week constraint, and they never break this constraint. Likewise, they make some effort to obey the 22 persons per building constraint. The header file for the TSGenome class is shown in Listing 4. The Mutate and Crossover functions rely on the DoGreedyAssign function to keep the constraints satisfied.
The test data was exactly the same as was used in the simulated annealing case. It is a difficult problem with a hard-to-find global optimum. The genetic algorithm found it after 2,000 generations using a population size of 200. The probability of mutation was set to 0.01. The probability of crossover was set to 0.30. The fitness sigma was 2.0. The GA algorithm was somewhat slower than simulated annealing, but it required considerably less coding. It also found many more local optima in the course of its search. This is characteristic of the broad searching powers of genetic algorithms.
Conclusion
Genetic algorithms can solve tough real-world optimization problems. It is safe to say that genetic algorithms are more of a brute-force approach than either mathematical programming or heuristic search. But with more computing resources available today than ever before, genetic algorithms are gaining popularity.
References
[1] Z. Michalewicz. Genetic Algorithms + Data Structures (Springer, 1992).
[2] M. Bucci. “Optmization with Simulated Annealing,” C/C++ Users Journal, November 2001.
Mark Bucci is the president of Business Analytics Corp, a software consulting firm. His main interests are mathematical algorithms and performance issues, database design, and software project management. Mark has used applied mathematics in the development of a number of different commercial software applications involving linear programming, graphs and charting software for medical instruments, energy management, business forecasting, and most recently a workforce scheduling application that uses the simulated annealing algorithm. He can be reached at [email protected].
