praktikum-holons/src/algorithm/binary/GaAlgorithm.java

package algorithm.binary;

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
import java.util.TreeSet;

import javax.swing.JFrame;

import algorithm.objectiveFunction.ObjectiveFunctionByCarlos;
import api.AlgorithmFrameworkFlex;
import ui.model.DecoratedState;

public class GaAlgorithm extends AlgorithmFrameworkFlex{

	/**
	 * Should be even.
	 */
	private int popsize = 20;
	private int maxGenerations = 100;
	private double tournamentSize = 2.0;
	private double fixedSwapProbability = 0.02;
	private boolean useFixedSpawProbability = false;
	private double fixedMutateProbability = 0.02;
	private boolean useFixedMutateProbability = false;
	private boolean useIntervalMutation = false;
	private double mutateProbabilityInterval = 0.01;
	private double maxMutationPercent = 0.01;
	private boolean moreInformation = false;
	
	
	public GaAlgorithm() {
		super();
		addIntParameter("popsize", popsize, intValue -> popsize = intValue, () -> popsize, 1);
		addIntParameter("maxGenerations", maxGenerations, intValue -> maxGenerations = intValue, () -> maxGenerations, 1);
		addDoubleParameter("tournamentSize", tournamentSize, doubleValue -> tournamentSize = doubleValue, () -> tournamentSize, 1.0);
		addDoubleParameter("fixedSwapProbability", fixedSwapProbability, doubleValue -> fixedSwapProbability = doubleValue, () -> fixedSwapProbability, 0.0, 1.0);
		addBooleanParameter("useFixedSpawProbability", useFixedSpawProbability, booleanValue -> useFixedSpawProbability = booleanValue);
		addDoubleParameter("fixedMutateProbability", fixedMutateProbability, doubleValue -> fixedMutateProbability = doubleValue, () -> fixedMutateProbability, 0.0, 1.0);
		addBooleanParameter("useFixedMutateProbability", useFixedMutateProbability, booleanValue -> useFixedMutateProbability = booleanValue);
		addBooleanParameter("useIntervalMutation", useIntervalMutation, booleanValue -> useIntervalMutation = booleanValue);
		addDoubleParameter("mutateProbabilityInterval", mutateProbabilityInterval, doubleValue -> mutateProbabilityInterval = doubleValue, () -> mutateProbabilityInterval, 0.0, 1.0);
		addDoubleParameter("maxMutationPercent", maxMutationPercent, doubleValue -> maxMutationPercent = doubleValue, () -> maxMutationPercent, 0.0, 1.0);
		addBooleanParameter("moreInformation", moreInformation, booleanValue -> moreInformation = booleanValue);
	}
	
	public static void main(String[] args)
	{
	      JFrame newFrame = new JFrame("exampleWindow");
	      GaAlgorithm instance = new GaAlgorithm();
	      newFrame.setContentPane(instance.getPanel());
	      newFrame.pack();
	      newFrame.setVisible(true);
	      newFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
	}
	
	@Override
	protected double evaluateState(DecoratedState actualstate) {
		return ObjectiveFunctionByCarlos.getFitnessValueForState(actualstate);
	}


	@Override
	protected int getProgressBarMaxCount() {
		return this.maxGenerations * this.popsize * this.rounds + rounds;
	}
	
	@Override
	protected Individual executeAlgo() {
		Individual best = new Individual();
		best.position = extractPositionAndAccess();
		if(moreInformation)console.println("Bit-Array_length: " + best.position.size());
		best.fitness = evaluatePosition(best.position);
		List<Double> runList = new ArrayList<Double>();
		runList.add(best.fitness);
		console.print("Start with: " + best.fitness);
		if(moreInformation)console.println("");
		int problemSize = best.position.size();
		List<Individual> population = initPopuluationRandom(problemSize, best);
		if(moreInformation)console.println("Size To Test:" + population.size());
		for(int generation = 0; generation< maxGenerations; generation++) {
			if(moreInformation)console.println("Generation" + generation + " start with Fitness: " + best.fitness);
			for(Individual i : population) {
				i.fitness = evaluatePosition(i.position);
				if(moreInformation)console.println("Fitness" + i.fitness);
				if(i.fitness < best.fitness) best = i;
				
			}
			runList.add(best.fitness);
			List<Individual> childList = new ArrayList<Individual>();
			for(int k = 0; k<popsize/2; k++) {
				Individual parentA = selectAParent(population, popsize);
				Individual parentB = selectAParent(population, popsize);
				Individual childA = new Individual(parentA);
				Individual childB = new Individual(parentB);
				crossover(childA, childB, problemSize);
				if(useIntervalMutation)mutateInterval(childA, problemSize);else mutate(childA, problemSize);
				if(useIntervalMutation)mutateInterval(childB, problemSize);else mutate(childB, problemSize);
				childList.add(childA);
				childList.add(childB);
			}
			population = childList;
			if(moreInformation)console.println("________________");
			if(cancel)return null;
		}
		
		
		console.println("   End with:" + best.fitness);
		this.runList = runList;
		return best;
	}
	/**
	 * Algorithm 22 Bit-Flip Mutation.
	 * 
	 */
	private void mutate(Individual child, int problemSize) {
		double probability = (this.useFixedMutateProbability) ? this.fixedMutateProbability : 1.0/(double)problemSize;
		ListIterator<Boolean> iter = child.position.listIterator();
		while(iter.hasNext()) {
			boolean boolValue = iter.next();
			if(Random.nextDouble() <=  probability) {
				iter.set(!boolValue);
			}
		}
	}
	
	/**
	 * Algorithm rolf
	 * 
	 */
	private void mutateInterval(Individual child, int problemSize) {
		//If not mutate skip
		if(Random.nextDouble() >  this.mutateProbabilityInterval) {
			return;
		}
		//println("problemSize:" + problemSize + "    maxMutationPercent:" + maxMutationPercent);
		int maximumAmountOfMutatedBits = Math.max(1, (int)Math.round(((double) problemSize) * this.maxMutationPercent));
		int randomUniformAmountOfMutatedValues = Random.nextIntegerInRange(1,maximumAmountOfMutatedBits + 1);
		
		//println("max:" + maximumAmountOfMutatedBits + "   actual:" + randomUniformAmountOfMutatedValues);
		TreeSet<Integer> mutationLocation = new TreeSet<Integer>(); //sortedSet
		//Choose the location to mutate
		for(int i = 0; i< randomUniformAmountOfMutatedValues; i++) {
			boolean success = mutationLocation.add(Random.nextIntegerInRange(0, problemSize));
			if(!success) i--; //can be add up to some series long loops if maximumAmountOfMutatedBits get closed to problemsize.
		}
		//println("Set:" + mutationLocation);
		ListIterator<Boolean> iter = child.position.listIterator();
		if(mutationLocation.isEmpty()) return;
		int firstindex = mutationLocation.pollFirst();
		while(iter.hasNext()) {
			int index = iter.nextIndex();
			boolean boolValue = iter.next();
			if(index == firstindex) {
				iter.set(!boolValue);
				if(mutationLocation.isEmpty()) break;
				firstindex = mutationLocation.pollFirst();
			}
		}
	}
	
	
	
	
	/** 
	 * Algorithm 25 Uniform Crossover.
	 * Probability is set to 1/Problemsize when not changed.
	 */
	private void crossover(Individual childA, Individual childB, int problemSize) {
		double probability = (this.useFixedSpawProbability) ? this.fixedSwapProbability : 1.0/(double)problemSize;
		ListIterator<Boolean> iterA = childA.position.listIterator();
		ListIterator<Boolean> iterB = childB.position.listIterator();
		for(int i= 0; i < problemSize; i++) {
			boolean boolA = iterA.next();
			boolean boolB = iterB.next();
			if(Random.nextDouble() <=  probability ) {
				//Swap 
				iterA.set(boolB);
				iterB.set(boolA);
			}
		}
	}
	/**
	 * Algorithm 32 Tournament Selection.
	 * The fitnessValues are calculated for the Population List.
	 * PseudoCode
	 */
	private Individual selectAParent(List<Individual> population,int popsize) {
		Individual tournamentBest = population.get(Random.nextIntegerInRange(0, popsize));
		double participants;
		for(participants = tournamentSize ; participants >= 2; participants -= 1.0) {
			Individual next = population.get(Random.nextIntegerInRange(0, popsize));
			if(next.fitness < tournamentBest.fitness) tournamentBest = next;
		}
		//if tournament size is not a whole number like 2.5 or 3.6
		//the remaining part is the chance to fight another time; 2.7 -> 70% chance to fight a second time
		if( participants > 1) {		
			if(Random.nextDouble() < participants - 1.0) {
				//println("Chance to find a match");
				Individual next = population.get(Random.nextIntegerInRange(0, popsize));
				if(next.fitness < tournamentBest.fitness) tournamentBest = next;
			}
		}
		return tournamentBest;
	}
	/**
	 * Initialize the Population with Individuals that have a random Position.
	 */
	private List<Individual> initPopuluationRandom(int problemSize, Individual startIndidual){
		List<Individual> population =  new ArrayList<Individual>();
		for(int i = 0; i < popsize -1; i++) {
			population.add(createRandomIndividualWithoutFitness(problemSize));
		}
		//Add Start Position
		population.add(new Individual(startIndidual));
		return population;
	}
	
	
	
	/**
	 * Algorithm 21 The BooleanVeator initialization.
	 * @param problemSize
	 * @return
	 */
	private Individual createRandomIndividualWithoutFitness(int problemSize) {
		//create Random Individual Without Fitness
		Individual result = new Individual();
		result.position = new ArrayList<Boolean>();
		for (int index = 0; index < problemSize; index++){
			result.position.add(Random.nextBoolean());
		}
		return result;
	}

	@Override
	protected String algoInformationToPrint() {
//		private int popsize = 20;
//		private int maxGenerations = 100;
//		private double tournamentSize = 2.0;
//		private double fixedSwapProbability = 0.02;
//		private boolean useFixedSpawProbability = false;
//		private double fixedMutateProbability = 0.02;
//		private boolean useFixedMutateProbability = false;
//		private boolean useIntervalMutation = true;
//		private double mutateProbabilityInterval = 0.01;
//		private double maxMutationPercent = 0.01;
		return "GaAlgo"+ " Rounds:" + rounds 
				+ " maxGenerations:" + maxGenerations
				+ " popsize:" + popsize
				+ " tournamentSize:" +  tournamentSize
				+ (useFixedSpawProbability? " fixedSwapProbability:" +  fixedSwapProbability : " swapProbability:" + "1.0f/problemsize")
				+ (useIntervalMutation? 
						(" mutateProbabilityInterval:" +  mutateProbabilityInterval
						+ " maxMutationPercent:" +  maxMutationPercent)
						: 
						(useFixedMutateProbability? " fixedMutateProbability:" +  fixedMutateProbability:" mutateProbability:" + "1.0f/problemsize"));
	}

	@Override
	protected String plottFileName() {
		return "plottGaAlgo.txt";
	}
}