Implementation of a Generic Genetic Algorithm

    Now that you understand the general structure of a genetic algorithm, we will examine a common problem to which they are often applied. To implement a generic genetic algorithm, several classes have been created:

• Chromosome
• GeneticAlgorithm
• MateWorker

    The Chromosome class implements a single chromosome. The GeneticAlgorithm class is used to control the training process. It implements the Train interface and can be used to train feedforward neural networks.

Mating

    Mating is performed either in the base Chromosome class or in a subclass. Subclasses can implement their own mate methods if specialization is needed. However, the examples in this book do not require anything beyond the base Chromosome class's mate method. We will now examine how the mate method works. The signature for the mate method of the Chromosome class is shown here:

public void mate(
  final Chromosome<GENE_TYPE, GA_TYPE> father,
  final Chromosome<GENE_TYPE, GA_TYPE> offspring1,
  final Chromosome<GENE_TYPE, GA_TYPE> offspring2)
throws NeuralNetworkError

    The mating process treats the genes of a chromosome as a long array of elements. For this neural network, these elements will be double variables taken from the weight matrix. For the traveling salesman problem, these elements will represent cities at which the salesman will stop; however, these elements can represent anything. Some genes will be taken from the mother and some will be taken from the father. Two offspring will be created. Figure 6.1 shows how the genetic material is spliced by the mate method.

Figure 6.1: Mating two chromosomes.

    As you can see, two cut-points are created between the father and the mother. Some genetic material is taken from each region, defined by the cut-points, to create the genetic material for each offspring.

    First, the length of the gene array is determined.

final int geneLength = getGenes().length;

    Two cut-points must then be established. The first cut-point is randomly chosen. Because all “cuts” will be of a constant length, the first cut-point cannot be chosen so far in the array that there is not a sufficiently long section left to allow the full cut length to be taken. The second cut-point is simply the cut length added to the first cut-point.

final int cutpoint1 = (int) (Math.random() * (geneLength - getGeneticAlgorithm().getCutLength()));
final int cutpoint2 = cutpoint1 + getGeneticAlgorithm().getCutLength();

    Two arrays are then allocated that are big enough to hold the two offspring.

final Set<GENE_TYPE> taken1 = new HashSet<GENE_TYPE>();
final Set<GENE_TYPE> taken2 = new HashSet<GENE_TYPE>();

    There are three regions of genetic material that must now be considered. The first is the area between the two cut-points. The other two are the areas before and after the cut-points.

for (int i = 0; i < geneLength; i++) {
  if ((i < cutpoint1) || (i > cutpoint2)) {
  } else {
    offspring1.setGene(i, father.getGene(i));
    offspring2.setGene(i, this.getGene(i));
    taken1.add(offspring1.getGene(i));
    taken2.add(offspring2.getGene(i));
  }
}

    Now that the middle section has been handled, the two outer sections must be addressed.

		// handle outer sections
		for (int i = 0; i < geneLength; i++) {
			if ((i < cutpoint1) || (i > cutpoint2)) {
				if (getGeneticAlgorithm().isPreventRepeat()) {
					offspring1.setGene(i, getNotTaken(this, taken1));
					offspring2.setGene(i, getNotTaken(father, taken2));
				} else {
					offspring1.setGene(i, this.getGene(i));
					offspring2.setGene(i, father.getGene(i));
				}
			}
		}

    Copy the results for the two offspring.

		// copy results
		offspring1.calculateCost();
		offspring2.calculateCost();

    A random number is used to see if the first offspring should be mutated.

if (Math.random() < this.geneticAlgorithm.getMutationPercent()) {
  offspring1.mutate();
}

    Likewise, mutating the second offspring is considered.

if (Math.random() < 
this.geneticAlgorithm.getMutationPercent()) {
  offspring2.mutate();
}

    The exact process for mutation varies depending on the problem being solved. For a neural network application, some weight matrix value is scaled by a random percentage. For the traveling salesman problem, two random stops on the trip are swapped.

Multithreading Issues

    Most new computers being purchased today are multicore. Multicore processors can execute programs considerably faster if they are written to be multithreaded. Neural network training, in particular, can benefit from multithreading. While backpropagation can be somewhat tricky to multithread, genetic algorithms are fairly easy. The GeneticAlgorithm class provided in this book is designed to use a thread pool, if one is provided. A complete discussion of Java's built-in thread-pooling capabilities is beyond the scope of this book; however, the basics will be covered.

    To use Java's built-in thread pool, a class must be created that processes one unit of work. The real challenge in writing code that executes well on a multicore processor is breaking the work down into small packets that can be divided among the threads.

    Classes that perform these small work packets must implement the Callable interface. For the generic genetic algorithm, the work packets are performed by the MateWorker class. MateWorker objects are created during each iteration of the training. These objects are created for each mating that must occur. Once all of the MateWorker objects are created, they are handed off to a thread pool. The MateWorker class is shown in Listing 6.1.

Listing 6.1: The MateWorker Class (MateWorker.java)

/**
 * Introduction to Neural Networks with Java, 2nd Edition
 * Copyright 2008 by Heaton Research, Inc. 
 * http://www.heatonresearch.com/books/java-neural-2/
 * 
 * ISBN13: 978-1-60439-008-7  	 
 * ISBN:   1-60439-008-5
 *   
 * This class is released under the:
 * GNU Lesser General Public License (LGPL)
 * http://www.gnu.org/copyleft/lesser.html
 */
package com.heatonresearch.book.introneuralnet.neural.genetic;

import java.util.concurrent.Callable;

/**
 * MateWorker: This class is used in conjunction with a thread pool.
 * This allows the genetic algorithm to offload all of those calculations
 * to a thread pool.  
 * 
 * @author Jeff Heaton
 * @version 2.1
 */
public class MateWorker<CHROMOSME_TYPE extends Chromosome<?, ?>> implements
		Callable<Integer> {
	private final CHROMOSME_TYPE mother;
	private final CHROMOSME_TYPE father;
	private final CHROMOSME_TYPE child1;
	private final CHROMOSME_TYPE child2;

	public MateWorker(final CHROMOSME_TYPE mother, final CHROMOSME_TYPE father,
			final CHROMOSME_TYPE child1, final CHROMOSME_TYPE child2) {
		this.mother = mother;
		this.father = father;
		this.child1 = child1;
		this.child2 = child2;
	}

	@SuppressWarnings("unchecked")
	public Integer call() throws Exception {
		this.mother.mate((Chromosome)this.father, 
				(Chromosome)this.child1, 
				(Chromosome)this.child2);
		return null;
	}

}

    As you can see from the above listing, the class is provided with everything that it needs to mate two chromosomes and produce two offspring. The actual work is done inside the run method. The work consists of nothing more than calling the mate method of one of the parents.