Chapter 6 |
In this chapter we will explore different techniques that are frequently used to optimize genetic algorithms. Additional optimization techniques become increasingly important as the problem being solved becomes more complex. A well-optimized algorithm can save hours or even days when solving larger problems; for this reason, optimization techniques are essential when the problem reaches a certain level of complexity.
In addition to exploring some common optimization techniques, this chapter will also cover a few implementation examples using the genetic algorithms from the previous chapters’ case studies.
Adaptive Genetic Algorithms
Adaptive genetic algorithms (AGA) are a popular subset of genetic algorithms which can provide significant performance improvements over standard implementations when used in the right circumstances. As we have come to learn in the previous chapters, a key factor which determines how well a genetic algorithm will perform is the way in which its parameters are configured. We have already discussed the importance of finding the right values for the mutation rate and crossover rate when constructing an efficient genetic algorithm. Typically, configuring the parameters will require some trial and error, together with some intuition, before eventually reaching a satisfactory configuration. Adaptive genetic algorithms are useful because they can assist in the tuning of these parameters automatically by adjusting them based on the state of the algorithm. These parameter adjustments take place while the genetic algorithm is running, hopefully resulting in the best parameters being used at any specific time during execution. It’s this continuous adaptive adjustment of the algorithm’s parameters which will often result in a performance improvement for the genetic algorithm.
Adaptive genetic algorithms use information such as the average population fitness and the population’s current best fitness to calculate and update its parameters in a way that best suits its present state. For example, by comparing any specific individual to the current fittest individual in the population, it’s possible to gauge how well that individual is performing in relation to the current best. Typically, we want to increase the chance of preserving individuals that are performing well and reduce the chance of preserving individuals that don’t perform well. One way we can do this is by allowing the algorithm to adaptively update the mutation rate.
Unfortunately, it’s not quite that simple. After a while, the population will start to converge and individuals will begin to fall nearer to a single point in the search space. When this happens, the progress of the search can stall as there is very little difference between individuals. In this event, it can be effective to raise the mutation rate slightly, encouraging the search of alternative areas within the search space.
We can determine if the algorithm has begun to converge by calculating the difference between the current best fitness and the average population fitness. When the average population fitness is close to the current best fitness, we know the population has started to converge around a small area of the search space.
Adaptive genetic algorithms can be used to adjust more than just the mutation rate however. Similar techniques can be applied to adjust other parameters of the genetic algorithm such as the crossover rate to provide further improvements as needed.
Implementation
As with many things concerning genetic algorithms, the optimal way to update the parameters usually requires some experimentation. We will explore one of the more common approaches and leave it to you personally to experiment with other approaches if you wish.
As discussed previously, when calculating what the mutation rate should be for any given individual, two of the most important characteristics to consider are how well the current individual is performing and how well the entire population is performing as a whole. The algorithm we will use to assess these two characteristics and update the mutation rate is as follows:
pm = (fmax - fi ) / (fmax – favg ) * m, fi > favg
pm = m, fi ≤ favg
When the individual’s fitness is greater than the population’s average fitness we take the best fitness from the population (fmax) and find the difference between the current individual’s fitness (fi). We then find the difference between the max population fitness and the average population fitness (favg) and divide the two values. We can use this value to scale our mutation rate that was set during initialization. If the individual’s fitness is the same or less than the population’s average fitness we simply use the mutation rate as set during initialization.
To make things easier, we can implement our new adaptive genetic algorithm code into our previous class scheduler code. To begin, we need to add a new method for getting the average fitness of the population. We can do this by adding the following method to the Population class, anywhere in the file:
/**
* Get average fitness
*
* @return The average individual fitness
*/
public double getAvgFitness(){
if (this.populationFitness == -1) {
double totalFitness = 0;
for (Individual individual : population) {
totalFitness += individual.getFitness();
}
this.populationFitness = totalFitness;
}
return populationFitness / this.size();
}
Now we can complete the implementation by updating the mutation function to use our adaptive mutation algorithm,
/**
* Apply mutation to population
*
* @param population
* @param timetable
* @return The mutated population
*/
public Population mutatePopulation(Population population, Timetable timetable){
// Initialize new population
Population newPopulation = new Population(this.populationSize);
// Get best fitness
double bestFitness = population.getFittest(0).getFitness();
// Loop over current population by fitness
for (int populationIndex = 0; populationIndex < population.size(); populationIndex++) {
Individual individual = population.getFittest(populationIndex);
// Create random individual to swap genes with
Individual randomIndividual = new Individual(timetable);
// Calculate adaptive mutation rate
double adaptiveMutationRate = this.mutationRate;
if (individual.getFitness() > population.getAvgFitness()) {
double fitnessDelta1 = bestFitness - individual.getFitness();
double fitnessDelta2 = bestFitness - population.getAvgFitness();
adaptiveMutationRate = (fitnessDelta1 / fitnessDelta2) * this.mutationRate;
}
// Loop over individual’s genes
for (int geneIndex = 0; geneIndex < individual.getChromosomeLength(); geneIndex++) {
// Skip mutation if this is an elite individual
if (populationIndex > this.elitismCount) {
// Does this gene need mutating?
if (adaptiveMutationRate > Math.random()) {
// Swap for new gene
individual.setGene(geneIndex, randomIndividual.getGene(geneIndex));
}
}
}
// Add individual to population
newPopulation.setIndividual(populationIndex, individual);
}
// Return mutated population
return newPopulation;
}
This new mutatePopulation method is identical to the original except for the adaptive mutation code which implements the algorithm mentioned above.
When initializing the genetic algorithm with adaptive mutation enabled, the mutation rate used will now be the maximum possible mutation rate and will scale down depending on the fitness of the current individual and population as a whole. Because of this, a higher initial mutation rate may be beneficial.
Exercises
- Use what you know about the adaptive mutation rate to implement an adaptive crossover rate into your genetic algorithm.
Multi-Heuristics
When it comes to optimizing genetic algorithms implementing a secondary heuristic is another common method to achieve significant performance improvements under certain conditions. Implementing a second heuristic into a genetic algorithm allows us to combine the best aspects of multiple heuristic approaches into one algorithm, providing further control over the search strategy and performance.
Two popular heuristics that are often implemented into genetic algorithms are simulated annealing and Tabu search. Simulated annealing is a search heuristic modeled on the process of annealing found in metallurgy. Put simply, it is a hill climbing algorithm that is designed to gradually reduce the rate in which worse solutions are accepted. In the context of genetic algorithms, simulated annealing will reduce the mutation rate and/or crossover rate over time.
On the other hand, Tabu search is a search algorithm that keeps a list of “tabu” (which derives from “taboo”) solutions that prevents the algorithm from returning to previously visited areas in the search space that are known to be weak. This tabu list helps the algorithm avoid repeatedly considering solutions it’s previously found and knows to be weak.
Typically, a multi-heuristic approach would only be implemented in situations where including it could bring certain needed improvements to the search process. For example, if the genetic algorithm is converging on an area in the search space too quickly, implementing simulated annealing into the algorithm might help to control how soon the algorithm converges.
Implementation
Let’s go over a quick example of a multi-heuristic algorithm by combining the simulated annealing algorithm with a genetic algorithm. As mentioned previously, the simulated annealing algorithm is a hill climbing algorithm which initially accepts worse solutions at a high rate; then as the algorithm runs, it gradually reduces the rate in which worse solutions are accepted.
One of the easiest ways to implement this characteristic into a genetic algorithm is by updating the mutation and crossover rate to start with a high rate then gradually lower the rate of mutation and crossover as the algorithm progresses. This initial high mutation and crossover rate will cause the genetic algorithm to search a large area of the search space. Then as the mutation and crossover rate is slowly decreased the genetic algorithm should begin to focus its search on areas of the search space where fitness values are higher.
To vary the mutation and crossover probability, we use a temperature variable which starts high, or “hot”, and slowly decreases, or “cools” as the algorithm runs. This heating and cooling technique is directly inspired by the process of annealing found in metallurgy. After each generation the temperature is cooled slightly, which decreases the mutation and crossover probability.
To begin the implementation, we need to create two new variables in the GeneticAlgorithm class. The coolingRate should be set to a small fraction, typically on the order of 0.001 or less – though this number will depend on the number of generations you expect to run and how aggressive you’d like the simulated annealing to be.
private double temperature = 1.0;
private double coolingRate;
Next, we need to create a function to cool the temperature based on the cooling rate.
/**
* Cool temperature
*/
public void coolTemperature() {
this.temperature *= (1 - this.coolingRate);
}
Now, we can update the mutation function to consider the temperature variable when deciding whether to apply mutation. We can do this by changing this line of code,
// Does this gene need mutation?
if (this.mutationRate > Math.random()) {
To now include the new temperature variable,
// Does this gene need mutation?
if ((this.mutationRate * this.getTempature()) > Math.random()) {
To finish this off, update the genetic algorithm’s loop code in the executive class’ “main” method to run the coolTemperature( ) function at the end of each generation. Again, you may need to adjust the initial mutation rate as it will now function as a max rate depending on the temperature value.
Exercises
- Use what you know about the simulated annealing heuristic to apply it to crossover rate.
Performance Improvements
Aside from improving the search heuristics, there are other ways to optimize a genetic algorithm. Possibly one of the most effective ways to optimize a genetic algorithm is by simply writing efficient code. When building genetic algorithms that need to run for many thousands of generations, just taking a fraction of a second off of each generation’s processing time can greatly reduce the overall running time.
Fitness Function Design
With the fitness function typically being the most processing demanding component of a genetic algorithm, it makes sense to focus code improvements on the fitness function to see the best return in performance.
Before making improvements to the fitness function, it’s a good idea to first ensure it adequately represents the problem. A genetic algorithm uses its fitness function to gauge the best area of the search space to focus its search in. This means a poorly designed fitness function can have a huge negative impact on the search ability and overall performance of the genetic algorithm. As an example, imagine a genetic algorithm has been built to design a car panel, but the fitness function which evaluated the car panel did so entirely by measuring the car’s top speed. This overly simple fitness function may not provide an adequate fitness value if it was also important that the panel could meet certain durability or ergonomic constraints as well as being aerodynamic enough.
Parallel Processing
Modern computers will often come equipped with several separate processing units or “cores”. Unlike standard single-core systems, multi-core systems are able to use additional cores to process multiple computations simultaneously. This means any well-designed application should be able to take advantage of this characteristic allowing its processing requirements to be distributed across the extra processing cores available. For some applications, this could be as simple as processing GUI related computations on one core and all the other computations on another.
Supporting the benefits of multi-core systems is one simple but effective way to achieve performance improvements on modern computers. As we discussed previously, the fitness function is often going to be the bottleneck of a genetic algorithm. This makes it a perfect candidate for multi-core optimization. By using multiple cores, it’s possible to calculate the fitness of numerous individuals simultaneously, which makes a huge difference when there are often hundreds of individuals to evaluate per population.
Lucky for us, Java 8 provides some very useful libraries that makes supporting parallel processing in our genetic algorithm much easier. Using IntStream, we can achieve parallel processing in our fitness function without worrying about the fine details of parallel processing (such as the number of cores we need to support); it will instead create an optimal number of threads depending on the number of cores available.
You may have wondered why, in Chapter 5, the GeneticAlgorithm calcFitness method clones the Timetable object before using it. When threading applications for parallel processing, one needs to take care to ensure that objects in one thread will not affect objects in another thread. In this case, changes made to the timetable object from one thread may have unexpected results in other threads using the same object at the same time – cloning the Timetable first allows us to give each thread its own object.
We can take advantage of threading in chapter 5’s class scheduler by modifying the GeneticAlgorithm’s evalPopulation method to use Java’s IntStream:
/**
* Evaluate population
*
* @param population
* @param timetable
*/
public void evalPopulation(Population population, Timetable timetable){
IntStream.range(0, population.size()).parallel()
.forEach(i -> this.calcFitness(population.getIndividual(i), timetable));
double populationFitness = 0;
// Loop over population evaluating individuals and suming population fitness
for (Individual individual : population.getIndividuals()) {
populationFitness += individual.getFitness();
}
population.setPopulationFitness(populationFitness);
}
Now the calcFitness function is able to run across multiple cores if the system supports them.
Because the genetic algorithms covered in this book have used fairly simple fitness functions, parallel processing may not provide much of a performance improvement. A nice way to test how much parallel processing can improve the genetic algorithms performance might be to add a call to Thread.sleep( ) in the fitness function. This will simulate a fitness function which takes a significant amount of time to complete execution.
Fitness Value Hashing
As discussed previously, the fitness function is usually the most computationally expensive component of a genetic algorithm. Thus, even small improvements to the fitness function can have a considerable effect on performance. Value hashing is another method that can reduce the amount of time spent calculating fitness values by storing previously computed fitness values in a hash table. In large distributed systems, you could use a centralized caching service (such as Redis or memcached) to the same end.
During execution, solutions found previously will occasionally be revisited due to the random mutations and recombinations of individuals. This occasional revisiting of solutions becomes more common as the genetic algorithm converges and starts to find solutions in an increasingly smaller area of the search space.
Each time a solution is revisited its fitness value needs to be recalculated, wasting processing power on repetitive, duplicate calculations. Fortunately, this can be easily fixed by storing fitness values in a hash table after they have been calculated. When a previously visited solution is revisited, its fitness value can be pulled straight from the hash table, avoiding the need to recalculate it.
To add the fitness value hashing to your code, first create the fitness hash table in the GeneticAlgorithm class,
// Create fitness hashtable
private Map<Individual, Double> fitnessHash = Collections.synchronizedMap(
new LinkedHashMap<Individual, Double>() {
@Override
protected boolean removeEldestEntry(Entry<Individual, Double> eldest) {
// Store a maximum of 1000 fitness values
return this.size() > 1000;
}
});
In this example, the hash table will store a maximum of 1000 fitness values before we begin to remove the oldest values. This can be changed as required for the best trade-off in performance. Although a larger hash table can hold more fitness values, it comes at the cost of memory usage.
Now, the get and put methods can be added to retrieve and store the fitness values. This can be done by updating the calcFitness method as follows. Note that we’ve removed the IntStream code from the last section, so that we can evaluate a single improvement at a time.
/**
* Calculate individual’s fitness value
*
* @param individual
* @param timetable
* @return fitness
*/
public double calcFitness(Individual individual, Timetable timetable){
Double storedFitness = this.fitnessHash.get(individual);
if (storedFitness != null) {
return storedFitness;
}
// Create new timetable object for thread
Timetable threadTimetable = new Timetable(timetable);
threadTimetable.createClasses(individual);
// Calculate fitness
int clashes = threadTimetable.calcClashes();
double fitness = 1 / (double) (clashes + 1);
individual.setFitness(fitness);
// Store fitness in hashtable
this.fitnessHash.put(individual, fitness);
return fitness;
}
Finally, because we are using the Individual object as a key for the hash table, we need to override the “equals” and “hashCode” methods of the Individual class. This is because we need the hash to be generated based on the individual’s chromosome, not the object itself, as it is by default. This is important because two separate individuals with the same chromosomes should be identified as the same by the fitness value hash table.
/**
* Generates hash code based on individual’s
* chromosome
*
* @return Hash value
*/
@Override
public int hashCode() {
int hash = Arrays.hashCode(this.chromosome);
return hash;
}
/**
* Equates based on individual’s chromosome
*
* @return Equality boolean
*/
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
Individual individual = (Individual) obj;
return Arrays.equals(this.chromosome, individual.chromosome);
}
Encoding
Another component which can affect the genetic algorithm’s performance is the encoding chosen. Although, in theory, any problem can be represented using a binary encoding of 0s and 1s, it’s rarely the most efficient encoding to choose.
When a genetic algorithm struggles to converge, it can often be because a bad encoding was chosen for the problem causing it to struggle when searching for new solutions. There is no hard science to picking a good encoding, but using an overly complex encoding will typically produce bad results. For example, if you want an encoding which can encode 10 numbers between 0-10, it would usually be best to use an encoding of 10 integers instead of a binary string. This way it’s easier to apply mutation and crossover functions which can be applied to the individual integers instead of bits representing integer values. It also means you don’t need to deal with invalid chromosomes such as “1111” representing the value 15 which is beyond our 0-10 required range.
Mutation and Crossover Methods
Picking good mutation and crossover methods is another important factor when considering options to improve a genetic algorithm’s performance. The optimal mutation and crossover methods to use will depend mostly on the encoding chosen and the nature of the problem itself. A good mutation or crossover method should be capable of producing valid solutions, but also be able to mutate and crossover individuals in an expected way.
For example: if we were optimizing a function which accepts any value between 0-10, one possible mutation method is Gaussian mutation which adds a random value to the gene increasing or decreasing its original value slightly. However, another possible mutation method is boundary mutation where a random value between a lower and upper boundary is chosen to replace the gene. Both of these mutation methods are capable of producing valid mutations, however depending on the nature of the problem and other specifics of the implementation, one will likely outperform the other. A bad mutation method might simply round the value down to 0 or up to 10 depending on the original value. In this situation, the amount of mutation that occurs depends on the gene’s value which can result in poor performance. An initial value of 1 would be changed to 0 which is a relatively small change. However, a value of 5 would be changed to 10 which is much larger. This bias can cause a preference for values closer to 0 and 10 which will often negatively impact the search process of the genetic algorithm.
Summary
Genetic algorithms can be modified in different ways to achieve significant performance improvements. In this chapter, we looked at a number of different optimization strategies and how to implement them into a genetic algorithm.
Adaptive genetic algorithms is one optimization strategy which can provide performance improvements over a standard genetic algorithm. An adaptive genetic algorithm allows the algorithm to update its parameters dynamically, typically modifying the mutation rate or crossover rate. This dynamic update of parameters often achieves better results than statically defined parameters which don’t adjust based on the algorithm’s state.
Another optimization strategy we considered in this chapter is multi-heuristics. This strategy involves combining a genetic algorithm with another heuristic such as the simulated annealing algorithm. By combining search characters with another heuristic, it is possible to achieve performance improvements in situations where those characteristics are useful. The simulated annealing algorithm we looked at in this chapter is based on the annealing process found in metallurgy. When implemented in a genetic algorithm, it allows for large changes to occur in the genome initially, then gradually reduces the amount of change allowing the algorithm to focus on promising areas of the search space.
One of the easiest ways to achieve a performance improvement is by optimizing the fitness function. The fitness function is typically the most computationally expensive component, making it ideal for optimization. It’s also important that the fitness function is well-defined and provides a good reflection of an individual’s actual fitness. If the fitness function gives a poor reflection of an individual’s performance, it can slow the search process and direct it towards poor areas of the search space.
One easy way to optimize the fitness function is by supporting parallel processing. By processing multiple fitness functions at a time, it is possible to greatly reduce the amount of time the genetic algorithm spends evaluating individuals.
Another tactic which can be used to reduce the amount of time needed to process the fitness function is fitness value hashing. Fitness value hashing uses a hash table to store fitness values for a number of recently used chromosomes. If those chromosomes appear again in the algorithm, it can recall the fitness value instead of recalculating it. This can prevent tedious reprocessing of individuals that have already been evaluated in the past.
Finally, it can also be effective to consider if improving the genetic encoding or using a different mutation or crossover method could improve the evolution process. For example, using an encoding which poorly represents the encoded individual, or a mutation method which doesn’t generate the required diversity in the genome can cause stagnation of the algorithm and lead to poor solutions being produced.