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

package holeg.algorithm.topologie;

import holeg.algorithm.objective_function.TopologieObjectiveFunction;
import holeg.api.TopologieAlgorithmFramework;
import holeg.model.Model;
import holeg.utility.math.Random;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

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(Model model, int amountOfAddedSwitch, double addedCableMeters,
      boolean moreInformation) {
    return TopologieObjectiveFunction.getFitnessValueForState(model, 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;
  }
}