praktikum-holons/src/holeg/algorithm/topologie/GaAlgorithm.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.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.TreeSet;

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(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<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(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(nextIntegerInRangeExcept(0, this.getMaximumIndexObjects(index), intValue));
        //println("changed Value["+ index +"]");
        if (mutationLocation.isEmpty()) {
          break;
        }
        firstindex = mutationLocation.pollFirst();
      }
    }
  }
  /**
   * Random Int in Range [min;max[ with UniformDistribution without the value between.
   *
   * @param min the minimum value
   * @param max the maximum value
   * @param valueBetween a value between min and max
   * @return next random integer value without a value between.
   */
  public static int nextIntegerInRangeExcept(int min, int max, int valueBetween) {
    if (max - min == 1) {
      //return the other value
      return (valueBetween == min) ? max : min;
    }
    int result = Random.nextIntegerInRange(min, max -1);
    if (result >= valueBetween) {
      result++;
    }
    return result;
  }
}