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

package holeg.algorithm.binary;

import holeg.api.AlgorithmFrameworkFlex;
import holeg.utility.math.decimal.Format;
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
import javax.swing.JFrame;

public class AcoAlgorithm extends AlgorithmFrameworkFlex {

  //Parameter for Algo with default Values:
  /**
   * Should be even.
   */
  private int popsize = 20;
  private int maxGenerations = 200;
  /**
   * The vaporization factor;
   */
  private double p = 0.3;
  private double convergenceFactorReset = 0.99;
  private boolean moreInformation = false;


  public AcoAlgorithm() {
    super();
    addIntParameter("Population size", popsize, intValue -> popsize = intValue, () -> popsize, 1);
    addIntParameter("Generations", maxGenerations, intValue -> maxGenerations = intValue,
        () -> maxGenerations, 1);
    addDoubleParameter("Vaporization rate", p, doubleValue -> p = doubleValue, () -> p, 0.0, 1.0);
    addDoubleParameter("Convergence factor threshold", convergenceFactorReset,
        doubleValue -> convergenceFactorReset = doubleValue, () -> convergenceFactorReset, 0.0,
        1.0);
    addBooleanParameter("Detailed information", moreInformation,
        booleanValue -> moreInformation = booleanValue);
  }


  public static void main(String[] args) {
    JFrame newFrame = new JFrame("exampleWindow");
    AcoAlgorithm instance = new AcoAlgorithm();
    newFrame.setContentPane(instance.getPanel());
    newFrame.pack();
    newFrame.setVisible(true);
    newFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  }


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


  /**
   * Algorithm 20 !! Fitness is better when smaller.: PseudoCode: Best <- actual; pheromones =
   * initPheromons(); for(maxGeneration times){ population = createSolutionsBiasedBy(pheromones);
   * for(each Individual i from population){ fitness <- evaluatePosition(i); if(fitness <
   * best.fitnessValue) Best <- i; } vaporizeIntensifiePheromons(pheromones); }
   *
   * @return
   */
  @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: " + Format.doubleFixedPlaces(2, best.fitness));
    if (moreInformation) {
      console.println("");
    }
    if (best.position.isEmpty()) {
      return best;
    }
    int problemSize = best.position.size();
    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" + Format.doubleFixedPlaces(2, 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 (cf > this.convergenceFactorReset) {
        pheromones = initPheromones(problemSize);
      }
      if (cancel) {
        return null;
      }
    }

    console.println("   End With:" + Format.doubleFixedPlaces(2, best.fitness));
    this.runList = runList;
    return best;

  }


  /**
   * tj1 is the pheromon level in the j position cf is the convergence factor cf e [0;1] difference
   * = | tj1 - tj0 | = | tj1 - (1 - tj1) |
   *
   * @param pheromones
   * @return cf
   */
  private double calculateConvergenceFactor(List<Double> pheromones, int problemSize) {
    double sumOfDifference = pheromones.stream().map(tj1 -> Math.abs(tj1 - (1.0 - tj1)))
        .reduce(0.0, Double::sum);
    double cf = sumOfDifference / (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<Double> pheromones, List<Boolean> position,
      int problemSize) {
    ListIterator<Double> iterPheromone = pheromones.listIterator();
    ListIterator<Boolean> iterBest = position.listIterator();
    for (int i = 0; i < problemSize; i++) {
      double pheromone = iterPheromone.next();
      boolean bestDecision = iterBest.next();
      iterPheromone.set((1.0 - p) * pheromone + (bestDecision ? p : 0.0));
    }
  }

  /**
   * @param pheromones
   * @return
   */
  private List<Individual> constructSolutionsBiasedBy(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<Double> pheromones) {
    Individual result = new Individual();
    result.position = new ArrayList<Boolean>();
    for (double pheromone : pheromones) {
      result.position.add((Random.nextDouble() < pheromone));
    }
    return result;
  }

  /**
   * Initialize Pheromons with 0.5
   */
  private List<Double> initPheromones(int problemSize) {
    List<Double> result = new ArrayList<Double>();
    for (int i = 0; i < problemSize; i++) {
      result.add(0.5);
    }
    return result;
  }


  @Override
  protected String algoInformationToPrint() {
//		private int popsize = 20;
//		private int maxGenerations = 200;
//		private double p = 0.3;
//		private double convergenceFactorReset = 0.99;
    return "AcoAlgo"
        + " Rounds: " + rounds
        + " Iterations: " + maxGenerations
        + " Individuals: " + popsize
        + " vaporization: " + Format.doubleAllPlaces(p)
        + " convergenceFactorReset: " + Format.doubleAllPlaces(convergenceFactorReset);
  }


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


}