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

package algorithm.topologie;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.TreeSet;
import algorithm.objectiveFunction.TopologieObjectiveFunction;
import api.TopologieAlgorithmFramework;
import ui.model.DecoratedState;
import utility.Random;

public class GaAlgorithm extends TopologieAlgorithmFramework {

	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(){
		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);
		addBooleanParameter("useFixedSpawProbability", useFixedSpawProbability, booleanValue -> useFixedSpawProbability = booleanValue, Arrays.asList("fixedSwapProbability"), new LinkedList<String>());
		addDoubleParameter("fixedSwapProbability", fixedSwapProbability, doubleValue -> fixedSwapProbability = doubleValue, () -> fixedSwapProbability, useFixedSpawProbability, 0.0, 1.0);
		addSeperator();
		addBooleanParameter("Use Interval Mutation", useIntervalMutation, booleanValue -> useIntervalMutation = booleanValue, Arrays.asList("Probability for Frequency Mutation", "Scope of Mutation"), Arrays.asList("Probability for Bit-wise Mutation"));
		addDoubleParameter("Probability for Frequency Mutation", mutateProbabilityInterval, doubleValue -> mutateProbabilityInterval = doubleValue, () -> mutateProbabilityInterval, useIntervalMutation, 0.0, 1.0);
		addDoubleParameter("Probability for Bit-wise Mutation", fixedMutateProbability, doubleValue -> fixedMutateProbability = doubleValue, () -> fixedMutateProbability, !useIntervalMutation, 0.0, 1.0);
		addDoubleParameter("Scope of Mutation", maxMutationPercent, doubleValue -> maxMutationPercent = doubleValue, () -> maxMutationPercent, useIntervalMutation, 0.0, 1.0);
		addSeperator();
		addBooleanParameter("Print Auxiliary Information", moreInformation, booleanValue -> moreInformation = booleanValue, new LinkedList<String>(), new LinkedList<String>());
	
	}
	@Override
	protected double evaluateState(DecoratedState actualstate, int amountOfAddedSwitch, double addedCableMeters, boolean moreInformation) {
		return TopologieObjectiveFunction.getFitnessValueForState(actualstate, amountOfAddedSwitch, addedCableMeters, moreInformation);
	}

	@Override
	protected Individual executeAlgo() {
		resetWildcards();
		Individual best = new Individual();
		best.position = extractPositionAndAccess();
		int problemSize =  best.position.size();
		best.fitness = evaluatePosition(best.position);
		List<Double> runList = new ArrayList<Double>();
		runList.add(best.fitness);
		console.println("Integer_Array_length: " + best.position.size());
		List<Individual> population = initPopuluationRandom(problemSize, best);
		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;
	}

	@Override
	protected int getProgressBarMaxCount() {
		return rounds * maxGenerations * popsize + 1;
	}

	@Override
	protected String algoInformationToPrint() {
		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 "ga-topologie.txt";
	}
	/**
	 * 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;
	}
	
	private Individual createRandomIndividualWithoutFitness(int problemSize) {
		//create Random Individual Without Fitness
		Individual result = new Individual();
		result.position = new ArrayList<Integer>();
		for (int index = 0; index < problemSize; index++){
			result.position.add(Random.nextIntegerInRange(0, this.getMaximumIndexObjects(index) + 1));
		}
		//console.println("[" +result.position.stream().map(Object::toString).collect(Collectors.joining(", ")) + "]");
		return result;
	}
	
	/**
	 * 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;
	}
	/** 
	 * 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<Integer> iterA = childA.position.listIterator();
		ListIterator<Integer> iterB = childB.position.listIterator();
		for(int i= 0; i < problemSize; i++) {
			int intA = iterA.next();
			int intB = iterB.next();
			if(Random.nextDouble() <=  probability ) {
				//Swap 
				iterA.set(intB);
				iterB.set(intA);
			}
		}
	}
	/**
	 * Algorithm 22 Bit-Flip Mutation.
	 * 
	 */
	private void mutate(Individual child, int problemSize) {
		double probability = (this.useFixedMutateProbability) ? this.fixedMutateProbability : 1.0/(double)problemSize;
		ListIterator<Integer> iter = child.position.listIterator();
		while(iter.hasNext()) {
			int index = iter.nextIndex();
			Integer intValue = iter.next();
			if(Random.nextDouble() <=  probability) {
				iter.set(Random.nextIntegerInRangeExcept(0, this.getMaximumIndexObjects(index), intValue));
			}
		}
	}
	/**
	 * 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<Integer> iter = child.position.listIterator();
		if(mutationLocation.isEmpty()) return;
		int firstindex = mutationLocation.pollFirst();
		while(iter.hasNext()) {
			int index = iter.nextIndex();
			int intValue = iter.next();
			if(index == firstindex) {
				iter.set(Random.nextIntegerInRangeExcept(0, this.getMaximumIndexObjects(index), intValue));
				//println("changed Value["+ index +"]");
				if(mutationLocation.isEmpty()) break;
				firstindex = mutationLocation.pollFirst();
			}
		}
	}
}