123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251 |
- package algorithm.binary;
- import java.util.ArrayList;
- import java.util.List;
- import java.util.ListIterator;
- import java.util.TreeSet;
- import javax.swing.JFrame;
- import api.AlgorithmFrameworkFlex;
- 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("popsize", popsize, intValue -> popsize = intValue, () -> popsize, 1);
- addIntParameter("maxGenerations", maxGenerations, intValue -> maxGenerations = intValue, () -> maxGenerations, 1);
- addDoubleParameter("tournamentSize", tournamentSize, doubleValue -> tournamentSize = doubleValue, () -> tournamentSize, 1.0);
- addDoubleParameter("SwapProbability", swapProbability, doubleValue -> swapProbability = doubleValue, () -> swapProbability, 0.0, 1.0);
- addDoubleParameter("MutateProbability", mutateProbability, doubleValue -> mutateProbability = doubleValue, () -> mutateProbability, 0.0, 1.0);
- addBooleanParameter("useIntervalMutation", useIntervalMutation, booleanValue -> useIntervalMutation = booleanValue);
- addDoubleParameter("mutateProbabilityInterval", mutateProbabilityInterval, doubleValue -> mutateProbabilityInterval = doubleValue, () -> mutateProbabilityInterval, 0.0, 1.0);
- addDoubleParameter("maxMutationPercent", maxMutationPercent, doubleValue -> maxMutationPercent = doubleValue, () -> maxMutationPercent, 0.0, 1.0);
- addBooleanParameter("moreInformation", 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.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<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";
- }
- }
|