My Genetic Algorithm for AI Coursework

GeneticAlgorithm.java

package uk.calumgilchrist.ai.pathfinder;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Random;

import org.json.simple.JSONArray;


public class PathFinderGA extends PathFinder implements FindPath {

	private PriorityQueue<Chromosome> population;
	private int populationSize;
	
	private String start;
	private String goal;
	
	public PathFinderGA(JSONArray array, int populationSize, String start, String goal) {
		super(array);

		this.populationSize = populationSize;
		population = new PriorityQueue<Chromosome>();
		
		this.start = start;
		this.goal = goal;
		
		initialisePopulation();
		
		evaluatePopulation();
	}

	public void stepPopulation() {
		produceTheNextGeneration();
		evaluatePopulation();
	}
	
	private void initialisePopulation() {
		List<String> swappedCities;
		
		for (int i = 0; i < populationSize; i++) {
			
			do {
				swappedCities = getCityNames();
				Collections.shuffle(swappedCities);
			} while (!swappedCities.get(0).equals(start));
				
			population.add(new Chromosome(swappedCities));
		}
	}
	
	public void evaluatePopulation() {
		
		PriorityQueue<Chromosome> newPopulation = new PriorityQueue<Chromosome>();
		
		int fitness;
		
		Iterator<String> itCity;
		Chromosome tempChromosome;
		Route tempRoute;
		
		String city1;
		String city2;
		while (population.size() > 0) {
			tempChromosome = population.remove();
			
			itCity = tempChromosome.iterator();
			if (itCity.hasNext()) {
				
				city1 = itCity.next();
				fitness = 0;
				while (itCity.hasNext()) {
					city2 = city1;
					city1 = itCity.next();
					tempRoute = new Route(city1, city2);
					fitness += (getRoute(tempRoute.hashCode()).getWeight());
				}
				
				//Add the goal to the fitness
				tempRoute = new Route(city1, goal);
				fitness += (getRoute(tempRoute.hashCode()).getWeight());
				tempChromosome.setFitness(fitness);
			}
			newPopulation.add(tempChromosome);
		}
		
		population = newPopulation;
	}

	public void produceTheNextGeneration() {
		
		Chromosome parent1, parent2;
		
		Chromosome child;
		
		List<Chromosome> intermediatePop = new ArrayList<Chromosome>(populationSize);
		
		//Add best chromosome to population
		intermediatePop.add(population.peek());
		//For population
		while (intermediatePop.size() < populationSize) {
			parent1 = roulletteWheelSelect();
			parent2 = roulletteWheelSelect();
			
			child = crossover(parent1, parent2);
			child = mutate(child);
			
			// Add child to the population
			intermediatePop.add(child);
		}
		
		//Set population to new generation
		population.clear();
		population.addAll(intermediatePop);
	}
	
	private Chromosome mutate(Chromosome child) {
		int gene = getRandomNumberBetween(2, child.size() - 1) - 1;
		
		List<String> tempList = child.getCities();
		String tempCity = tempList.get(gene);
		
		tempList.set(gene, tempList.get(gene + 1));
		tempList.set(gene + 1, tempCity);
		
		child = new Chromosome(tempList);
		return child;
	}

	/**
	 * Create a new Chromosome from the paths in parent1 and parent2
	 * @param parent1
	 * @param parent2
	 * @return
	 */
	public Chromosome crossover(Chromosome parent1, Chromosome parent2) {
		//TODO: Do not move the goal or start node
		
		List<String> prevAdded = new LinkedList<String>();
		
		int i;
		String child[] = new String[parent1.size()];
		
		child[0] = start;
		parent1 = removeDuplicates(child, parent1);
		
		int numberOfGenes = parent1.size();
		int halfGenes = numberOfGenes / 2;
		int gene;
		
		//Set some of the child's genes to randomly selected ones from parent
		for (i = 1; i < halfGenes; i++) {
			
			do {
				gene = getRandomNumberBetween(0, parent1.size() - 1);
			} while (child[gene + 1] != null);
			child[gene + 1] = parent1.getCity(gene);
		}
		
		parent2 = removeDuplicates(child, parent2);
		
		//Add genes from parent2 where needed
		for (i = 0; i < numberOfGenes; i++) {

			if (child[i + 1] == null) {
				child[i + 1] = parent2.remCity(i % (parent2.size()));
			}		
		}
		
		Chromosome cChild = new Chromosome();
		cChild.addArray(child);
		return cChild;
	}

	/**
	 * Remove duplicates from List that appear in child
	 * @param child
	 * @param cities
	 * @return List without duplicates
	 */
	private Chromosome removeDuplicates(String[] child, Chromosome cities) {
		
		cities = new Chromosome(cities.getCities());
		Iterator<String> city;
		
		String tempName;
		for (int i = 0; i < child.length; i++) {
			//reset iterator
			city = cities.iterator();
			
			while (city.hasNext()) {
				tempName = city.next();
				
				if (tempName.equals(child[i])) {
					city.remove();
				}
			}
		}
		return cities;
	}

	/**
	 * Choose a member of the population with a roulette wheel style weighting
	 * @return Randomly selected Chromosome from the population
	 */
	public Chromosome roulletteWheelSelect() {
				

		int totalFitness = getTotalFitness();
		
		double maxReal = 100000.0;
		int randInt = getRandomNumberBetween(0, (int) maxReal);
		
		double randReal = randInt / maxReal;
		
		double pointer = randReal * totalFitness;
		
		int currentFitness = 0;
		
		Iterator<Chromosome> chromosome = population.iterator();
		Chromosome tempChromosome = null;
		
		while (chromosome.hasNext()) {
			tempChromosome = chromosome.next();
			currentFitness += tempChromosome.getFitness();
			
			if (currentFitness < pointer && currentFitness > 0) {
				break;
			}
		}
		
		//TODO: tempChromosome MAY be null
		return tempChromosome;
	}

	public int getTotalFitness() {
		Iterator<Chromosome> chromosome = population.iterator();
		
		int totalFitness = 0;
		while (chromosome.hasNext()) {
			totalFitness += chromosome.next().getFitness();
		}
		return totalFitness;
	}

	public void findPath(){

	}
	
    /**
     * Find a random number between min and max
     * @param min
     * @param max
     * @return
     */
    private int getRandomNumberBetween(int min, int max) {
        Random rand = new Random();
        int randomNumber = rand.nextInt((max + 1) - min) + min;
        return randomNumber;
    }
    
    public Chromosome getFittest() {
    	Chromosome tempChromosome = population.peek();
    	tempChromosome.add(goal);
    	return tempChromosome;
    }

	public PriorityQueue<Chromosome> getPopulation() {
		return population;
	}
	
	public void printPopulationFitness() {
		
		PriorityQueue<Chromosome> tempPop = new PriorityQueue<Chromosome>(population);
		while (tempPop.size() > 0)
			System.out.print(tempPop.remove().getFitness() + ", ");
		
		
		System.out.println();
	}
}