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

package holeg.algorithm.binary;

import holeg.api.AlgorithmFrameworkFlex;
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
import java.util.TreeSet;
import javax.swing.JFrame;

public class GaAlgorithm extends AlgorithmFrameworkFlex {

  /**
   * Should be even.
   */
  private int popsize = 20;
  private int maxGenerations = 100;
  private double tournamentSize = 2.0;
  private double swapProbability = 0.02;
  private double mutateProbability = 0.02;
  private boolean useIntervalMutation = false;
  //private double mutateProbabilityInterval = 0.01;
  private double maxMutationPercent = 0.01;
  private boolean moreInformation = false;


  public GaAlgorithm() {
    super();
    addIntParameter("Population size", popsize, intValue -> popsize = intValue, () -> popsize, 1);
    addIntParameter("Generations", maxGenerations, intValue -> maxGenerations = intValue,
        () -> maxGenerations, 1);
    addDoubleParameter("Tournament size", tournamentSize,
        doubleValue -> tournamentSize = doubleValue, () -> tournamentSize, 1.0);
    addDoubleParameter("Swap probability", swapProbability,
        doubleValue -> swapProbability = doubleValue, () -> swapProbability, 0.0, 1.0);
    addDoubleParameter("Mutation probability", mutateProbability,
        doubleValue -> mutateProbability = doubleValue, () -> mutateProbability, 0.0, 1.0);
    addBooleanParameter("Interval-based mutation", useIntervalMutation,
        booleanValue -> useIntervalMutation = booleanValue);
    //addDoubleParameter("mutateProbabilityInterval", mutateProbabilityInterval, doubleValue -> mutateProbabilityInterval = doubleValue, () -> mutateProbabilityInterval, 0.0, 1.0);
    addDoubleParameter("Mutation severity (% of problem size)", maxMutationPercent,
        doubleValue -> maxMutationPercent = doubleValue, () -> maxMutationPercent, 0.0, 1.0);
    addBooleanParameter("Detailed Information", moreInformation,
        booleanValue -> moreInformation = booleanValue);
  }

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


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

  @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: " + best.fitness);
    if (moreInformation) {
      console.println("");
    }
    int problemSize = best.position.size();
    List<Individual> population = initPopuluationRandom(problemSize, best);
    if (moreInformation) {
      console.println("Size To Test:" + population.size());
    }
    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;
  }

  /**
   * Algorithm 22 Bit-Flip Mutation.
   */
  private void mutate(Individual child, int problemSize) {
    ListIterator<Boolean> iter = child.position.listIterator();
    while (iter.hasNext()) {
      boolean boolValue = iter.next();
      if (Random.nextDouble() <= this.mutateProbability) {
        iter.set(!boolValue);
      }
    }
  }

  /**
   * Algorithm rolf
   */
  private void mutateInterval(Individual child, int problemSize) {
    //If not mutate skip
    if (Random.nextDouble() > this.mutateProbability) {
      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<Boolean> iter = child.position.listIterator();
    if (mutationLocation.isEmpty()) {
      return;
    }
    int firstindex = mutationLocation.pollFirst();
    while (iter.hasNext()) {
      int index = iter.nextIndex();
      boolean boolValue = iter.next();
      if (index == firstindex) {
        iter.set(!boolValue);
        if (mutationLocation.isEmpty()) {
          break;
        }
        firstindex = mutationLocation.pollFirst();
      }
    }
  }


  /**
   * Algorithm 25 Uniform Crossover. Probability is set to 1/Problemsize when not changed.
   */
  private void crossover(Individual childA, Individual childB, int problemSize) {
    ListIterator<Boolean> iterA = childA.position.listIterator();
    ListIterator<Boolean> iterB = childB.position.listIterator();
    for (int i = 0; i < problemSize; i++) {
      boolean boolA = iterA.next();
      boolean boolB = iterB.next();
      if (Random.nextDouble() <= this.swapProbability) {
        //Swap
        iterA.set(boolB);
        iterB.set(boolA);
      }
    }
  }

  /**
   * 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;
  }

  /**
   * 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;
  }


  /**
   * Algorithm 21 The BooleanVeator initialization.
   *
   * @param problemSize
   * @return
   */
  private Individual createRandomIndividualWithoutFitness(int problemSize) {
    //create Random Individual Without Fitness
    Individual result = new Individual();
    result.position = new ArrayList<Boolean>();
    for (int index = 0; index < problemSize; index++) {
      result.position.add(Random.nextBoolean());
    }
    return result;
  }

  @Override
  protected String algoInformationToPrint() {
//		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 = true;
//		private double mutateProbabilityInterval = 0.01;
//		private double maxMutationPercent = 0.01;
    return "GaAlgo"
        + " Rounds: " + rounds
        + " Iterations: " + maxGenerations
        + " Individuals: " + popsize
        + " TournamentSize: " + tournamentSize
        + " SwapProbability: " + swapProbability
        + (useIntervalMutation ?
        (//" MutateProbabilityInterval: " +  mutateProbabilityInterval
            " MaxMutationPercent: " + maxMutationPercent)
        :
            (" MutateProbability: " + mutateProbability));
  }

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