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

package algorithm.topologie;

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

import algorithm.objectiveFunction.TopologieObjectiveFunction;
import api.TopologieAlgorithmFramework;
import ui.model.DecoratedState;
import utility.Random;

public class AcoAlgorithm extends TopologieAlgorithmFramework {

	private int popsize = 20;
	private int maxGenerations = 100;
	private boolean moreInformation = false;
	/**
	 * The vaporization factor;
	 */
	private double p = 0.05;
	private double convergenceFactorReset = 0.90;
	
	public AcoAlgorithm(){
		addIntParameter("popsize", popsize, intValue -> popsize = intValue, () -> popsize, 1);
		addIntParameter("maxGenerations", maxGenerations, intValue -> maxGenerations = intValue, () -> maxGenerations, 1);
		addSeperator();
		addDoubleParameter("Vaporization", p, doubleValue -> p = doubleValue, () -> p, true, 0.0, 1.0);
		addDoubleParameter("FactorReset", convergenceFactorReset, doubleValue -> convergenceFactorReset = doubleValue, () -> convergenceFactorReset, true, 0.0, 1.0);
		addSeperator();
		addBooleanParameter("moreInformation", 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<List<Double>> pheromones = initPheromones(problemSize);
		List<Individual> population = new ArrayList<Individual>();
		if(moreInformation)console.println("Size To Test:" + population.size());
		for(int generation = 0; generation< maxGenerations; generation++) {
			population.clear();
			population = constructSolutionsBiasedBy(pheromones);
			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);
			if(moreInformation)console.println("________________");
			vaporizeIntensifiePheromons(pheromones, best.position, problemSize);
			double cf = calculateConvergenceFactor(pheromones, problemSize);
			if(moreInformation)console.println("ConvergenceFactor = " + cf);
			if(moreInformation)console.println("pheromones:" + pheromones);
			if(cf > this.convergenceFactorReset) {
				pheromones = initPheromones(problemSize);
			}
			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 "Aco for Topologie "+ " Rounds:" + rounds 
				+ " maxGenerations:" + maxGenerations 
				+ " popsize:" +  popsize
				+ " vaporization:" +  p
				+ " convergenceFactorReset:" +  convergenceFactorReset;
	}

	@Override
	protected String plottFileName() {
		return "aco-topologie.txt";
	}
	/**
	 * tj1 is the pheromon level in the j position
	 * cf is the convergence factor cf e [0;1]
	 * 
	 * 
	 * 
	 * @param pheromones
	 * @return cf
	 */
	private double calculateConvergenceFactor(List<List<Double>> pheromones,int problemSize) {
		double sumofmax = pheromones.stream().map(listPheromons -> listPheromons.stream().max((a,b) -> Double.compare(a,b)).get()).reduce(0.0, Double::sum);
		double cf = sumofmax / (double)problemSize;
		return cf;
	}
	/**
	 * pheromone <- (1-p) * pheromone;
	 * if(best is true at this position) pheromone <- pheromone + p;
	 * @param pheromones
	 * @param position
	 */
	private void vaporizeIntensifiePheromons(List<List<Double>> pheromones, List<Integer> position, int problemSize) {
		ListIterator<List<Double>> iterPheromone = pheromones.listIterator();
		ListIterator<Integer> iterBest = position.listIterator();
		for(int i = 0; i < problemSize; i++) {
			List<Double> tauList = iterPheromone.next();
			int bestDecision = iterBest.next();
			ListIterator<Double> tauListiter = tauList.listIterator();
			for(int k = 0; tauListiter.hasNext(); k++) {
				double value = tauListiter.next();
				tauListiter.set((1.0 - p) * value + (k == bestDecision?p:0.0));
			}
		}
	}
	/**
	 * 
	 * @param pheromones
	 * @return
	 */
	private List<Individual> constructSolutionsBiasedBy(List<List<Double>> pheromones) {
		List<Individual> population =  new ArrayList<Individual>();
		for(int i = 0; i < popsize; i++) {
			population.add(constructASolutionBiasedBy(pheromones));
		}
		return population;
	}
	
	
	/**
	 * Walks the path with a ant and decide by pheromones if should take true or false;
	 * A pheromone have a level of 0 < pheromone < 1.
	 * A Pheromone is  equal to the probability.
	 * @param pheromones
	 * @return
	 */
	private Individual constructASolutionBiasedBy(List<List<Double>> pheromones) {
		Individual result = new Individual();
		result.position = new ArrayList<Integer>();
		for(List<Double> pheromoneList : pheromones) {
			ListIterator<Double> tauListiter = pheromoneList.listIterator();
			double radnomValue = Random.nextDouble();
			for(int i = 0;tauListiter.hasNext(); i++) {
				double actualtau = tauListiter.next();
				if(radnomValue > actualtau) {
					radnomValue -= actualtau;
				}else {
					result.position.add(i);
					break;
				}
			}
		}
		return result;
	}
	/**
	 * Initialize Pheromons with 1.0 / maxIndex;
	 */
	private List<List<Double>> initPheromones(int problemSize) {
		List<List<Double>> result = new ArrayList<List<Double>>();
		for(int i = 0; i < problemSize;i++) {
			//generate list equal tau values with max Int
			int maxIndex = this.getMaximumIndexObjects(i);
			double tauValue = 1.0 / (double) (maxIndex + 1);
			List<Double> tauList = new ArrayList<Double>();
			for(int tau= 0; tau < maxIndex + 1; tau++) {
				tauList.add(tauValue);				
			}
			result.add(tauList);
		}
		return result;
	}
}