123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300 |
- 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;
- }
- }
|