diff --git a/ea/Ub7/PBIL/src/PBIL.java b/ea/Ub7/PBIL/src/PBIL.java deleted file mode 100644 index 0b99483..0000000 --- a/ea/Ub7/PBIL/src/PBIL.java +++ /dev/null @@ -1,143 +0,0 @@ -/** - * This class implements a deterministic variant of the Genetic Algorithm described in the script, section 5.1.1. - */ -import java.util.ArrayList; -import java.util.Collections; -import java.util.List; - -public class PBIL { - /** The length of the genotype of the individuals **/ - private int m_GenotypeLength; - /** The number of individuals in the population **/ - private int m_Mu; - /** The number of children generated **/ - private double m_Lambda; - /** The number of single optimization steps to be evaluated **/ - private int m_OptimizationSteps; - /** The number of times the experiment is repeated **/ - private int m_MultiRuns; - /** Number of steps needed to reach best result **/ - private int m_OptimizationStepsNeeded = 0; - /** mean fitness **/ - private double meanFitness; - - private double[] propVector; - private double learnrate; - - /** - * This constructor sets up GeneticAlgorithm - * - * @param genotypeLength - * The length of the genotype of the individuals - * @param mu - * The number of individuals in the population - * @param lambda - * The number of children generated in each iteration - * @param optimizationSteps - * The number of single optimization steps to be evaluated - * (adjust as necessary) - * @param multiRuns - * The number of times the experiment is repeated (at least 10) - */ - public PBIL(int genotypeLength, int mu, double lambda, - int optimizationSteps, int multiRuns) { - assert multiRuns > 9; // use run configurations: vmargument: -ea - - this.m_GenotypeLength = genotypeLength; - this.m_Lambda = lambda; - this.m_Mu = mu; - this.m_OptimizationSteps = optimizationSteps; - this.m_MultiRuns = multiRuns; - - // this.learnrate = 1 / lambda; - this.learnrate = 0.05; - - } - - /** - * This method will initialize the GeneticAlgorithm - */ - public void initialize() { - - m_OptimizationStepsNeeded = 0; - this.propVector = new double[m_GenotypeLength]; - for (int i = 0; i < propVector.length; i++) { - propVector[i] = 0.5; - } - - } - - /** - * This method will optimize the evaulateAsMaxiBits Problem. Use - * m_FitnessCallsNeeded to return the number of FitnessCalls (e.g., calling - * evaluateAsMaxiBits()) needed to find the optimum. The optimization should - * terminate after m_FitnessCalls. - */ - public void optimize() { - for (int i = 0; i < m_OptimizationSteps; i++) { - List population = new ArrayList(); - for (int j = 0; j < m_Mu; j++) { - population.add(new PBilIndividual(propVector)); - } - Collections.sort(population, Collections.reverseOrder()); // comparable - // implemente - // in - - List m_Best = population.subList(0, m_Mu); - // System.out.println("Print best:"); - // System.out.println(m_Best.get(0).getStringRepresentation()); - for (PBilIndividual p : m_Best) { - for (int k = 0; k < m_GenotypeLength; k++) { - propVector[k] = (propVector[k] * (1 - learnrate)) - + ((p.getGenotype().get(k) ? 1 : 0) * learnrate); - } - } - // System.out.println(Arrays.toString(propVector)); - double fitnessPV = 0; - for (double p : propVector) { - fitnessPV += p; - } - double oldFitness = meanFitness; - meanFitness = propVector.length - fitnessPV; - if (oldFitness != meanFitness) { - m_OptimizationStepsNeeded++; - } - // System.out.println(i + " " + meanFitness); - - } - } - - /** - * This main method will start a simple GeneticAlgorithm search. No - * arguments necessary. - * - * @param args - */ - public static void main(String[] args) { - // TODO: parameters for the GeneticAlgorithm, adjust these values as - // necessary - int genotypeLength = 50; - int mu = 15; - int lambda = 50; - int optimizationSteps = 1000; - // int optimizationSteps = 100; - int multiRuns = 100; - PBIL program = new PBIL(genotypeLength, mu, lambda, optimizationSteps, - multiRuns); - int TmpMeanCalls = 0, TmpMeanFitness = 0; - // perform repeated optimization - for (int i = 0; i < program.m_MultiRuns; i++) { - - program.initialize(); - program.optimize(); - TmpMeanCalls += program.m_OptimizationStepsNeeded; - TmpMeanFitness += program.meanFitness; - } - TmpMeanCalls = TmpMeanCalls / program.m_MultiRuns; - TmpMeanFitness = TmpMeanFitness / program.m_MultiRuns; - System.out.println("(" + program.m_MultiRuns + "/" - + program.m_OptimizationSteps + ") Mean Fitness : " - + TmpMeanFitness + " Mean Calls needed: " + TmpMeanCalls); - } - // (1000/1000) Mean Fitness : 0 Mean Calls needed: 19 -} diff --git a/ea/Ub7/PBIL/src/PBilIndividual.java b/ea/Ub7/PBIL/src/PBilIndividual.java deleted file mode 100644 index 5b61585..0000000 --- a/ea/Ub7/PBIL/src/PBilIndividual.java +++ /dev/null @@ -1,162 +0,0 @@ -//import tools.RandomNumberGenerator; - -import java.util.BitSet; -import java.util.Random; - -/** - * @author Maximus - * - */ -public class PBilIndividual implements Comparable { - protected BitSet m_Genotype; - protected int m_GenotypeLength; - protected Random r = new Random(); - - /** Constructor **/ - public PBilIndividual(double[] propVector) { - // This method should call initGenotype() to initialize the genotype - this.m_GenotypeLength = propVector.length; - initGenotype(propVector); - - } - - /** - * cloning constructor - * - * @param toClone - */ - private PBilIndividual(PBilIndividual toClone) { - this.m_Genotype = (BitSet) toClone.m_Genotype.clone();// allowed, has - // only native - // typed - // fields - this.m_GenotypeLength = toClone.m_GenotypeLength; - } - - /** - * This method creates a deep copy of an individual. It should clone all - * objects contained by this object. - * - * @return An deep copy of this {@link PBilIndividual} - */ - @Override - public Object clone() { - - PBilIndividual c = new PBilIndividual(new double[m_GenotypeLength]); - c.setGenotype((BitSet) this.m_Genotype.clone()); - return c; - - // return new GAIndividual(this); - } - - /** - * This method evaluates the GAIndividual as a simple - * "maximize number of bits" problem. The fitness is the number of true bits - * in m_Genotype. Best fitness is reached if there are no false bits. - * - * @return The number of false bits (less is better!) - */ - public double evaluateAsMaxiBits() { - int zeros = 0; - for (int i = 0; i < m_GenotypeLength; i++) { - if (!m_Genotype.get(i)) { - zeros++; - } - } - return zeros; - } - - /** - * - * @return best fitness ==0 - */ - public double evaluateAsTwin() { - int f1 = 0; - int f2 = 0; - for (int i = 0; i < (m_GenotypeLength / 2); i++) { - if (m_Genotype.get(i)) { - f1++; - } - } - for (int i = (m_GenotypeLength / 2); i < m_GenotypeLength; i++) { - if (m_Genotype.get(i)) { - f2++; - } - } - return (m_GenotypeLength / 2) - Math.abs(f1 - f2); - } - - /** - * This method will return a string description of the GAIndividal notably - * the genotype: '0011000101' - * - * @return A descriptive string - */ - public String getStringRepresentation() { - // this should return exactly the representation shown in the comment - // above: - // only 0 (for false bits) and 1 (for true bits) with no extra white - // space! - String representation = ""; - for (int i = 0; i < m_GenotypeLength; i++) { - representation = m_Genotype.get(i) ? representation + "1" - : representation + "0"; - - } - return representation; - } - - /** - * This method will allow the user to read the GA genotype - * - * @return BitSet - */ - public BitSet getGenotype() { - return m_Genotype; - } - - /** - * This method will allow the user to set the current GA genotype. Should - * check if the length of the BitSet and the genotype length match. - * - * @param b - * The new genotype of the Individual - */ - public void setGenotype(BitSet b) { - - this.m_Genotype = b; - - } - - /** - * This method allows the user to read the length of the genotype. This may - * be necessary since BitSet.length only returns the index of the last - * significant bit. - * - * @return The length of the genotype. - */ - public int getGenotypeLength() { - return m_GenotypeLength; - } - - /** - * This method initializes the GA genotype randomly. Please use the - * tools.RandomNumberGenerator - * - * @param propVector - */ - public void initGenotype(double[] propVector) { - m_Genotype = new BitSet(m_GenotypeLength); - for (int i = 0; i < m_GenotypeLength; i++) { - if (r.nextDouble() < propVector[i]) { - m_Genotype.set(i); - } - } - } - - @Override - public int compareTo(PBilIndividual o) { - return ((Double) this.evaluateAsMaxiBits()).compareTo(o - .evaluateAsMaxiBits()); - } -} diff --git a/ea/Ub7/PBIL/src/RandomNumberGenerator.java b/ea/Ub7/PBIL/src/RandomNumberGenerator.java deleted file mode 100644 index 48816ea..0000000 --- a/ea/Ub7/PBIL/src/RandomNumberGenerator.java +++ /dev/null @@ -1,47 +0,0 @@ - - -import java.util.Random; - -public class RandomNumberGenerator { - - private static Random random; - private static long randomSeed; - - static { - randomSeed = System.currentTimeMillis(); - random = new Random(randomSeed); - } - - /** - * This method returns a evenly distributed integer value. The boundaries - * are included. - * - * @param lo - * Lower bound. - * @param hi - * Upper bound. - * @return Random integer from[lo,hi] - */ - public static int randomInt(int lo, int hi) { - return (Math.abs(random.nextInt()) % (hi - lo + 1)) + lo; - } - - /** - * This method returns 0 or 1 with same probability - * - * @return Random bit - */ - public static int randomBit() { - return randomInt(0, 1); - } - - /** - * This method returns true or false with same - * probability - * - * @return Random boolean value - */ - public static boolean randomBoolean() { - return (randomBit() == 1); - } -} diff --git a/ea/Ub7/PBIL/src/gen/GAIndividual.java b/ea/Ub7/PBIL/src/gen/GAIndividual.java deleted file mode 100644 index c3030b8..0000000 --- a/ea/Ub7/PBIL/src/gen/GAIndividual.java +++ /dev/null @@ -1,172 +0,0 @@ -package gen; - -//import tools.RandomNumberGenerator; - -import java.util.BitSet; - -import tools.RandomNumberGenerator; - -public class GAIndividual implements Comparable { - protected BitSet m_Genotype; - protected int m_GenotypeLength; - - /** Constructor **/ - public GAIndividual(int genotypeLength) { - // This method should call initGenotype() to initialize the genotype - this.m_GenotypeLength = genotypeLength; - initGenotype(); - } - - /** - * cloning constructor - * - * @param toClone - */ - private GAIndividual(GAIndividual toClone) { - this.m_Genotype = (BitSet) toClone.m_Genotype.clone();// allowed, has - // only native - // typed - // fields - this.m_GenotypeLength = toClone.m_GenotypeLength; - } - - /** - * This method creates a deep copy of an individual. It should clone all - * objects contained by this object. - * - * @return An deep copy of this {@link GAIndividual} - */ - @Override - public Object clone() { - - GAIndividual c = new GAIndividual(m_GenotypeLength); - c.setGenotype((BitSet) this.m_Genotype.clone()); - return c; - - // return new GAIndividual(this); - } - - /** - * This method evaluates the GAIndividual as a simple - * "maximize number of bits" problem. The fitness is the number of true bits - * in m_Genotype. Best fitness is reached if there are no false bits. - * - * @return The number of false bits (less is better!) - */ - public double evaluateAsMaxiBits() { - int zeros = 0; - for (int i = 0; i < m_GenotypeLength; i++) { - if (!m_Genotype.get(i)) { - zeros++; - } - } - return zeros; - } - - /** - * This method will return a string description of the GAIndividal notably - * the genotype: '0011000101' - * - * @return A descriptive string - */ - public String getStringRepresentation() { - // this should return exactly the representation shown in the comment - // above: - // only 0 (for false bits) and 1 (for true bits) with no extra white - // space! - String representation = ""; - for (int i = 0; i < m_GenotypeLength; i++) { - representation = m_Genotype.get(i) ? representation + "1" - : representation + "0"; - - } - return representation; - } - - /** - * This method will allow the user to read the GA genotype - * - * @return BitSet - */ - public BitSet getGenotype() { - return m_Genotype; - } - - /** - * This method will allow the user to set the current GA genotype. Should - * check if the length of the BitSet and the genotype length match. - * - * @param b - * The new genotype of the Individual - */ - public void setGenotype(BitSet b) { - - this.m_Genotype = b; - - } - - /** - * This method allows the user to read the length of the genotype. This may - * be necessary since BitSet.length only returns the index of the last - * significant bit. - * - * @return The length of the genotype. - */ - public int getGenotypeLength() { - return m_GenotypeLength; - } - - /** - * This method performs a simple one point mutation in the genotype (script - * 5.2.2). Please use the tools.RandomNumberGenerator - */ - public void mutate() { - m_Genotype.flip(RandomNumberGenerator - .randomInt(0, m_GenotypeLength - 1)); - } - - /** - * This method performs a simple one point crossover of two GAIndividuals - * (script 5.2.1). Please use the tools.RandomNumberGenerator - * - * @return An array of length 2 with the two resulting GAIndivuals - */ - public static GAIndividual[] crossover(GAIndividual ind1, GAIndividual ind2) { - assert ind1.m_GenotypeLength == ind2.m_GenotypeLength; - - int splitPoint = RandomNumberGenerator.randomInt(0, - ind1.m_GenotypeLength - 1); - GAIndividual ind1Clone = (GAIndividual) ind1.clone(); - GAIndividual ind2Clone = (GAIndividual) ind2.clone(); - for (int i = splitPoint; i < ind1Clone.m_GenotypeLength; i++) { - ind1Clone.m_Genotype.set(i, ind2.m_Genotype.get(i)); - ind2Clone.m_Genotype.set(i, ind1.m_Genotype.get(i)); - - } - // System.out.println("______"); - // System.out.println(ind1.getStringRepresentation()); - // System.out.println(ind2.getStringRepresentation()); - // System.out.println(splitPoint); - // System.out.println(ind1Clone.getStringRepresentation()); - // System.out.println(ind2Clone.getStringRepresentation()); - - return new GAIndividual[] { ind2Clone, ind1Clone }; - } - - /** - * This method initializes the GA genotype randomly. Please use the - * tools.RandomNumberGenerator - */ - public void initGenotype() { - m_Genotype = new BitSet(m_GenotypeLength); - for (int i = 0; i < m_GenotypeLength; i++) { - m_Genotype.set(i, RandomNumberGenerator.randomBoolean()); - } - } - - @Override - public int compareTo(GAIndividual o) { - return ((Double) this.evaluateAsMaxiBits()).compareTo(o - .evaluateAsMaxiBits()); - } -} diff --git a/ea/Ub7/PBIL/src/gen/GeneticAlgorithm.java b/ea/Ub7/PBIL/src/gen/GeneticAlgorithm.java deleted file mode 100644 index 7c5d84e..0000000 --- a/ea/Ub7/PBIL/src/gen/GeneticAlgorithm.java +++ /dev/null @@ -1,161 +0,0 @@ -package gen; - -/** - * This class implements a deterministic variant of the Genetic Algorithm described in the script, section 5.1.1. - */ -import java.util.ArrayList; -import java.util.Arrays; -import java.util.Collections; -import java.util.List; - -import tools.RandomNumberGenerator; - -public class GeneticAlgorithm { - /** The length of the genotype of the individuals **/ - private int m_GenotypeLength; - /** The number of individuals in the population **/ - private int m_Mu; - /** The number of children generated **/ - private int m_Lambda; - /** The number of single optimization steps to be evaluated **/ - private int m_OptimizationSteps; - /** The number of times the experiment is repeated **/ - private int m_MultiRuns; - /** Number of steps needed to reach best result **/ - private int m_OptimizationStepsNeeded = 0; - /** Current best individual **/ - private GAIndividual m_Best; - - /** - * This constructor sets up GeneticAlgorithm - * - * @param genotypeLength - * The length of the genotype of the individuals - * @param mu - * The number of individuals in the population - * @param lambda - * The number of children generated in each iteration - * @param optimizationSteps - * The number of single optimization steps to be evaluated - * (adjust as necessary) - * @param multiRuns - * The number of times the experiment is repeated (at least 10) - */ - public GeneticAlgorithm(int genotypeLength, int mu, int lambda, - int optimizationSteps, int multiRuns) { - assert multiRuns > 9; // use run configurations: vmargument: -ea - - this.m_GenotypeLength = genotypeLength; - this.m_Mu = mu; - this.m_Lambda = lambda; - this.m_OptimizationSteps = optimizationSteps; - this.m_MultiRuns = multiRuns; - this.m_Best = null; - - } - - /** - * This method will initialize the GeneticAlgorithm - */ - public void initialize() { - - m_OptimizationStepsNeeded = 0; - - } - - /** - * This method will optimize the evaulateAsMaxiBits Problem. Use - * m_FitnessCallsNeeded to return the number of FitnessCalls (e.g., calling - * evaluateAsMaxiBits()) needed to find the optimum. The optimization should - * terminate after m_FitnessCalls. - */ - public void optimize() { - // The deterministic Genetic Algorithm works as follows: - // initialize the population - // while maxSteps not reached do - // do select 2 (distinct) parents from population randomly - // perform crossover to generate two children - // until lambda children generated - // mutate the children (p_m = 0.5, use randomBoolean from - // RandomNumberGenerator) - // calculate the fitness of the children (use - // GAIndividual.evaluateAsMaxiBits()) - // select the mu best individuals for the new population - // od - - List population = new ArrayList(); - for (int i = 0; i < m_Mu; i++) { - population.add(new GAIndividual(m_GenotypeLength)); - - } - - for (int i = 0; i < m_OptimizationSteps; i++) { - - ArrayList children = new ArrayList(); - for (int a = 0; a < (m_Lambda / 2); a++) { - GAIndividual parent1; - GAIndividual parent2; - do { - parent1 = population.get(RandomNumberGenerator.randomInt(0, - m_Mu - 1)); - parent2 = population.get(RandomNumberGenerator.randomInt(0, - m_Mu - 1)); - } while (parent1 == parent2);// distinct parents - children.addAll(Arrays.asList(GAIndividual.crossover(parent1, - parent2))); - - } - for (GAIndividual child : children) { - if (RandomNumberGenerator.randomBoolean()) { - child.mutate(); - } - } - - Collections.sort(children); // comparable - // implemented - // in - // GAIndividual - // m_population = m_population.subList(0, m_Mu); - - m_Best = children.get(0); - population = children.subList(0, m_Mu); - if (m_Best.evaluateAsMaxiBits() != 0) { - m_OptimizationStepsNeeded++; - } - System.out.println(i + " " + (m_Best.evaluateAsMaxiBits())); - } - } - - /** - * This main method will start a simple GeneticAlgorithm search. No - * arguments necessary. - * - * @param args - */ - public static void main(String[] args) { - // TODO: parameters for the GeneticAlgorithm, adjust these values as - // necessary - int genotypeLength = 50; - int mu = 15; - int lambda = 50; - // int optimizationSteps = 100000; - int optimizationSteps = 1000; - int multiRuns = 1; - GeneticAlgorithm program = new GeneticAlgorithm(genotypeLength, mu, - lambda, optimizationSteps, multiRuns); - int TmpMeanCalls = 0, TmpMeanFitness = 0; - // perform repeated optimization - for (int i = 0; i < program.m_MultiRuns; i++) { - - program.initialize(); - program.optimize(); - TmpMeanCalls += program.m_OptimizationStepsNeeded; - TmpMeanFitness += program.m_Best.evaluateAsMaxiBits(); - } - TmpMeanCalls = TmpMeanCalls / program.m_MultiRuns; // ja klar 3.9 =3 - TmpMeanFitness = TmpMeanFitness / program.m_MultiRuns; - System.out.println("(" + program.m_MultiRuns + "/" - + program.m_OptimizationSteps + ") Mean Fitness : " - + TmpMeanFitness + " Mean Calls needed: " + TmpMeanCalls); - } -} diff --git a/ea/Ub7/PBIL/src/gen/HillClimbing.java b/ea/Ub7/PBIL/src/gen/HillClimbing.java deleted file mode 100644 index 86c07bf..0000000 --- a/ea/Ub7/PBIL/src/gen/HillClimbing.java +++ /dev/null @@ -1,94 +0,0 @@ -package gen; - -public class HillClimbing { - /** The length of the genotype of the individuals **/ - private int m_GenotypeLength; - /** The number of single optimization steps to be evaluated **/ - private int m_OptimizationSteps; - /** The number of times the experiment is repeated **/ - private int m_MultiRuns; - /** Number of steps needed to reach best result **/ - private int m_OptimizationStepsNeeded = 0; - /** Current best individual **/ - private GAIndividual m_Best; - - /** - * This constructor sets up HillClimber - * - * @param genotypeLength - * The length of the genotype of the individuals - * @param optimizationSteps - * The number of single optimization steps to be evaluated - * (adjust as necessary) - * @param multiRuns - * The number of times the experiment is repeated (at least 10) - */ - public HillClimbing(int genotypeLength, int optimizationSteps, int multiRuns) { - assert multiRuns > 9; - this.m_GenotypeLength = genotypeLength; - this.m_OptimizationSteps = optimizationSteps; - this.m_MultiRuns = multiRuns; - } - - /** - * This method will initialize the HillClimber - */ - public void initialize() { - m_Best = new GAIndividual(m_GenotypeLength); - m_OptimizationStepsNeeded = 0; - } - - /** - * This method will optimize the defaultEvaulateAsMiniBits Problem. Use - * m_FitnessCallsNeeded to return the number of FitnessCalls (e.g., calling - * evaluateAsMaxiBits()) needed to find the optimum. The optimization should - * terminate after m_FitnessCalls. - */ - public void optimize() { - // nur mutieren oder auch crossover? - - // TODO implement this - // use GAIndividual.evaluateAsMaxiBits() to evaluate the fitness of an - // individual and call it m_OptimizationSteps times before terminating - for (int i = 0; i < m_OptimizationSteps; i++) { - GAIndividual clone = (GAIndividual) m_Best.clone(); - clone.mutate(); - m_Best = clone.evaluateAsMaxiBits() <= m_Best.evaluateAsMaxiBits() ? clone - : m_Best; - - if (m_Best.evaluateAsMaxiBits() != 0) { - m_OptimizationStepsNeeded++; - } - } - } - - /** - * This main method will start a simple hill climber. No arguments - * necessary. - * - * @param args - */ - public static void main(String[] args) { - // TODO: parameters for the HillClimber, adjust these values as - // necessary - int genotypeLength = 50; - int optimizationSteps = 1000; - int multiRuns = 100; - HillClimbing program = new HillClimbing(genotypeLength, - optimizationSteps, multiRuns); - int TmpMeanCalls = 0, TmpMeanFitness = 0; - // perform repeated optimization - for (int i = 0; i < program.m_MultiRuns; i++) { - program.initialize(); - program.optimize(); - TmpMeanCalls += program.m_OptimizationStepsNeeded; - TmpMeanFitness += program.m_Best.evaluateAsMaxiBits(); - - } - TmpMeanCalls = TmpMeanCalls / program.m_MultiRuns; - TmpMeanFitness = TmpMeanFitness / program.m_MultiRuns; - System.out.println("(" + program.m_MultiRuns + "/" - + program.m_OptimizationSteps + ") Mean Fitness : " - + TmpMeanFitness + " Mean Calls needed: " + TmpMeanCalls); - } -} diff --git a/ea/Ub7/PBIL/src/genTwin/GAIndividualTwin.java b/ea/Ub7/PBIL/src/genTwin/GAIndividualTwin.java deleted file mode 100644 index 0df8626..0000000 --- a/ea/Ub7/PBIL/src/genTwin/GAIndividualTwin.java +++ /dev/null @@ -1,173 +0,0 @@ -package genTwin; - -//import tools.RandomNumberGenerator; - -import java.util.BitSet; - -import tools.RandomNumberGenerator; - -public class GAIndividualTwin implements Comparable { - protected BitSet m_Genotype; - protected int m_GenotypeLength; - - /** Constructor **/ - public GAIndividualTwin(int genotypeLength) { - // This method should call initGenotype() to initialize the genotype - this.m_GenotypeLength = genotypeLength; - initGenotype(); - } - - /** - * cloning constructor - * - * @param toClone - */ - private GAIndividualTwin(GAIndividualTwin toClone) { - this.m_Genotype = (BitSet) toClone.m_Genotype.clone();// allowed, has - // only native - // typed - // fields - this.m_GenotypeLength = toClone.m_GenotypeLength; - } - - /** - * This method creates a deep copy of an individual. It should clone all - * objects contained by this object. - * - * @return An deep copy of this {@link GAIndividualTwin} - */ - @Override - public Object clone() { - - GAIndividualTwin c = new GAIndividualTwin(m_GenotypeLength); - c.setGenotype((BitSet) this.m_Genotype.clone()); - return c; - - // return new GAIndividual(this); - } - - public double evaluateAsTwin() { - int f1 = 0; - int f2 = 0; - for (int i = 0; i < (m_GenotypeLength / 2); i++) { - if (m_Genotype.get(i)) { - f1++; - } - } - for (int i = (m_GenotypeLength / 2); i < m_GenotypeLength; i++) { - if (m_Genotype.get(i)) { - f2++; - } - } - return (m_GenotypeLength / 2) - Math.abs(f1 - f2); - } - - /** - * This method will return a string description of the GAIndividal notably - * the genotype: '0011000101' - * - * @return A descriptive string - */ - public String getStringRepresentation() { - // this should return exactly the representation shown in the comment - // above: - // only 0 (for false bits) and 1 (for true bits) with no extra white - // space! - String representation = ""; - for (int i = 0; i < m_GenotypeLength; i++) { - representation = m_Genotype.get(i) ? representation + "1" - : representation + "0"; - - } - return representation; - } - - /** - * This method will allow the user to read the GA genotype - * - * @return BitSet - */ - public BitSet getGenotype() { - return m_Genotype; - } - - /** - * This method will allow the user to set the current GA genotype. Should - * check if the length of the BitSet and the genotype length match. - * - * @param b - * The new genotype of the Individual - */ - public void setGenotype(BitSet b) { - - this.m_Genotype = b; - - } - - /** - * This method allows the user to read the length of the genotype. This may - * be necessary since BitSet.length only returns the index of the last - * significant bit. - * - * @return The length of the genotype. - */ - public int getGenotypeLength() { - return m_GenotypeLength; - } - - /** - * This method performs a simple one point mutation in the genotype (script - * 5.2.2). Please use the tools.RandomNumberGenerator - */ - public void mutate() { - m_Genotype.flip(RandomNumberGenerator - .randomInt(0, m_GenotypeLength - 1)); - } - - /** - * This method performs a simple one point crossover of two GAIndividuals - * (script 5.2.1). Please use the tools.RandomNumberGenerator - * - * @return An array of length 2 with the two resulting GAIndivuals - */ - public static GAIndividualTwin[] crossover(GAIndividualTwin ind1, - GAIndividualTwin ind2) { - assert ind1.m_GenotypeLength == ind2.m_GenotypeLength; - - int splitPoint = RandomNumberGenerator.randomInt(0, - ind1.m_GenotypeLength - 1); - GAIndividualTwin ind1Clone = (GAIndividualTwin) ind1.clone(); - GAIndividualTwin ind2Clone = (GAIndividualTwin) ind2.clone(); - for (int i = splitPoint; i < ind1Clone.m_GenotypeLength; i++) { - ind1Clone.m_Genotype.set(i, ind2.m_Genotype.get(i)); - ind2Clone.m_Genotype.set(i, ind1.m_Genotype.get(i)); - - } - // System.out.println("______"); - // System.out.println(ind1.getStringRepresentation()); - // System.out.println(ind2.getStringRepresentation()); - // System.out.println(splitPoint); - // System.out.println(ind1Clone.getStringRepresentation()); - // System.out.println(ind2Clone.getStringRepresentation()); - - return new GAIndividualTwin[] { ind2Clone, ind1Clone }; - } - - /** - * This method initializes the GA genotype randomly. Please use the - * tools.RandomNumberGenerator - */ - public void initGenotype() { - m_Genotype = new BitSet(m_GenotypeLength); - for (int i = 0; i < m_GenotypeLength; i++) { - m_Genotype.set(i, RandomNumberGenerator.randomBoolean()); - } - } - - @Override - public int compareTo(GAIndividualTwin o) { - // return ((Double) this.evaluateAsMaxiBits()).compareTo(o - // .evaluateAsMaxiBits()); - return ((Double) this.evaluateAsTwin()).compareTo(o.evaluateAsTwin()); - } -} diff --git a/ea/Ub7/PBIL/src/genTwin/GeneticAlgorithmTwin.java b/ea/Ub7/PBIL/src/genTwin/GeneticAlgorithmTwin.java deleted file mode 100644 index f7c436e..0000000 --- a/ea/Ub7/PBIL/src/genTwin/GeneticAlgorithmTwin.java +++ /dev/null @@ -1,161 +0,0 @@ -package genTwin; - -/** - * This class implements a deterministic variant of the Genetic Algorithm described in the script, section 5.1.1. - */ -import java.util.ArrayList; -import java.util.Arrays; -import java.util.Collections; -import java.util.List; - -import tools.RandomNumberGenerator; - -public class GeneticAlgorithmTwin { - /** The length of the genotype of the individuals **/ - private int m_GenotypeLength; - /** The number of individuals in the population **/ - private int m_Mu; - /** The number of children generated **/ - private int m_Lambda; - /** The number of single optimization steps to be evaluated **/ - private int m_OptimizationSteps; - /** The number of times the experiment is repeated **/ - private int m_MultiRuns; - /** Number of steps needed to reach best result **/ - private int m_OptimizationStepsNeeded = 0; - /** Current best individual **/ - private GAIndividualTwin m_Best; - - /** - * This constructor sets up GeneticAlgorithm - * - * @param genotypeLength - * The length of the genotype of the individuals - * @param mu - * The number of individuals in the population - * @param lambda - * The number of children generated in each iteration - * @param optimizationSteps - * The number of single optimization steps to be evaluated - * (adjust as necessary) - * @param multiRuns - * The number of times the experiment is repeated (at least 10) - */ - public GeneticAlgorithmTwin(int genotypeLength, int mu, int lambda, - int optimizationSteps, int multiRuns) { - assert multiRuns > 9; // use run configurations: vmargument: -ea - - this.m_GenotypeLength = genotypeLength; - this.m_Mu = mu; - this.m_Lambda = lambda; - this.m_OptimizationSteps = optimizationSteps; - this.m_MultiRuns = multiRuns; - this.m_Best = null; - - } - - /** - * This method will initialize the GeneticAlgorithm - */ - public void initialize() { - - m_OptimizationStepsNeeded = 0; - - } - - /** - * This method will optimize the evaulateAsMaxiBits Problem. Use - * m_FitnessCallsNeeded to return the number of FitnessCalls (e.g., calling - * evaluateAsMaxiBits()) needed to find the optimum. The optimization should - * terminate after m_FitnessCalls. - */ - public void optimize() { - // The deterministic Genetic Algorithm works as follows: - // initialize the population - // while maxSteps not reached do - // do select 2 (distinct) parents from population randomly - // perform crossover to generate two children - // until lambda children generated - // mutate the children (p_m = 0.5, use randomBoolean from - // RandomNumberGenerator) - // calculate the fitness of the children (use - // GAIndividual.evaluateAsMaxiBits()) - // select the mu best individuals for the new population - // od - - List population = new ArrayList(); - for (int i = 0; i < m_Mu; i++) { - population.add(new GAIndividualTwin(m_GenotypeLength)); - - } - - for (int i = 0; i < m_OptimizationSteps; i++) { - - ArrayList children = new ArrayList(); - for (int a = 0; a < (m_Lambda / 2); a++) { - GAIndividualTwin parent1; - GAIndividualTwin parent2; - do { - parent1 = population.get(RandomNumberGenerator.randomInt(0, - m_Mu - 1)); - parent2 = population.get(RandomNumberGenerator.randomInt(0, - m_Mu - 1)); - } while (parent1 == parent2);// distinct parents - children.addAll(Arrays.asList(GAIndividualTwin.crossover( - parent1, parent2))); - - } - for (GAIndividualTwin child : children) { - if (RandomNumberGenerator.randomBoolean()) { - child.mutate(); - } - } - - Collections.sort(children); // comparable - // implemented - // in - // GAIndividual - // m_population = m_population.subList(0, m_Mu); - - m_Best = children.get(0); - population = children.subList(0, m_Mu); - if (m_Best.evaluateAsTwin() != 0) { - m_OptimizationStepsNeeded++; - } - - } - } - - /** - * This main method will start a simple GeneticAlgorithm search. No - * arguments necessary. - * - * @param args - */ - public static void main(String[] args) { - // TODO: parameters for the GeneticAlgorithm, adjust these values as - // necessary - int genotypeLength = 50; - int mu = 15; - int lambda = 50; - // int optimizationSteps = 100000; - int optimizationSteps = 1000; - int multiRuns = 1000; - GeneticAlgorithmTwin program = new GeneticAlgorithmTwin(genotypeLength, - mu, lambda, optimizationSteps, multiRuns); - int TmpMeanCalls = 0, TmpMeanFitness = 0; - // perform repeated optimization - for (int i = 0; i < program.m_MultiRuns; i++) { - - program.initialize(); - program.optimize(); - TmpMeanCalls += program.m_OptimizationStepsNeeded; - TmpMeanFitness += program.m_Best.evaluateAsTwin(); - } - TmpMeanCalls = TmpMeanCalls / program.m_MultiRuns; // ja klar 3.9 =3 - TmpMeanFitness = TmpMeanFitness / program.m_MultiRuns; - System.out.println("(" + program.m_MultiRuns + "/" - + program.m_OptimizationSteps + ") Mean Fitness : " - + TmpMeanFitness + " Mean Calls needed: " + TmpMeanCalls); - } -} diff --git a/ea/Ub7/PBIL/src/genTwin/HillClimbingTwin.java b/ea/Ub7/PBIL/src/genTwin/HillClimbingTwin.java deleted file mode 100644 index 1918455..0000000 --- a/ea/Ub7/PBIL/src/genTwin/HillClimbingTwin.java +++ /dev/null @@ -1,95 +0,0 @@ -package genTwin; - -public class HillClimbingTwin { - /** The length of the genotype of the individuals **/ - private int m_GenotypeLength; - /** The number of single optimization steps to be evaluated **/ - private int m_OptimizationSteps; - /** The number of times the experiment is repeated **/ - private int m_MultiRuns; - /** Number of steps needed to reach best result **/ - private int m_OptimizationStepsNeeded = 0; - /** Current best individual **/ - private GAIndividualTwin m_Best; - - /** - * This constructor sets up HillClimber - * - * @param genotypeLength - * The length of the genotype of the individuals - * @param optimizationSteps - * The number of single optimization steps to be evaluated - * (adjust as necessary) - * @param multiRuns - * The number of times the experiment is repeated (at least 10) - */ - public HillClimbingTwin(int genotypeLength, int optimizationSteps, - int multiRuns) { - assert multiRuns > 9; - this.m_GenotypeLength = genotypeLength; - this.m_OptimizationSteps = optimizationSteps; - this.m_MultiRuns = multiRuns; - } - - /** - * This method will initialize the HillClimber - */ - public void initialize() { - m_Best = new GAIndividualTwin(m_GenotypeLength); - m_OptimizationStepsNeeded = 0; - } - - /** - * This method will optimize the defaultEvaulateAsMiniBits Problem. Use - * m_FitnessCallsNeeded to return the number of FitnessCalls (e.g., calling - * evaluateAsMaxiBits()) needed to find the optimum. The optimization should - * terminate after m_FitnessCalls. - */ - public void optimize() { - // nur mutieren oder auch crossover? - - // TODO implement this - // use GAIndividual.evaluateAsMaxiBits() to evaluate the fitness of an - // individual and call it m_OptimizationSteps times before terminating - for (int i = 0; i < m_OptimizationSteps; i++) { - GAIndividualTwin clone = (GAIndividualTwin) m_Best.clone(); - clone.mutate(); - m_Best = clone.evaluateAsTwin() <= m_Best.evaluateAsTwin() ? clone - : m_Best; - - if (m_Best.evaluateAsTwin() != 0) { - m_OptimizationStepsNeeded++; - } - } - } - - /** - * This main method will start a simple hill climber. No arguments - * necessary. - * - * @param args - */ - public static void main(String[] args) { - // TODO: parameters for the HillClimber, adjust these values as - // necessary - int genotypeLength = 50; - int optimizationSteps = 1000; - int multiRuns = 100; - HillClimbingTwin program = new HillClimbingTwin(genotypeLength, - optimizationSteps, multiRuns); - int TmpMeanCalls = 0, TmpMeanFitness = 0; - // perform repeated optimization - for (int i = 0; i < program.m_MultiRuns; i++) { - program.initialize(); - program.optimize(); - TmpMeanCalls += program.m_OptimizationStepsNeeded; - TmpMeanFitness += program.m_Best.evaluateAsTwin(); - - } - TmpMeanCalls = TmpMeanCalls / program.m_MultiRuns; - TmpMeanFitness = TmpMeanFitness / program.m_MultiRuns; - System.out.println("(" + program.m_MultiRuns + "/" - + program.m_OptimizationSteps + ") Mean Fitness : " - + TmpMeanFitness + " Mean Calls needed: " + TmpMeanCalls); - } -} diff --git a/ea/Ub7/PBIL/src/hcMaxiBits/GAIndividual.java b/ea/Ub7/PBIL/src/hcMaxiBits/GAIndividual.java new file mode 100644 index 0000000..010c6ff --- /dev/null +++ b/ea/Ub7/PBIL/src/hcMaxiBits/GAIndividual.java @@ -0,0 +1,172 @@ +package hcMaxiBits; + +//import tools.RandomNumberGenerator; + +import java.util.BitSet; + +import tools.RandomNumberGenerator; + +public class GAIndividual implements Comparable { + protected BitSet m_Genotype; + protected int m_GenotypeLength; + + /** Constructor **/ + public GAIndividual(int genotypeLength) { + // This method should call initGenotype() to initialize the genotype + this.m_GenotypeLength = genotypeLength; + initGenotype(); + } + + /** + * cloning constructor + * + * @param toClone + */ + private GAIndividual(GAIndividual toClone) { + this.m_Genotype = (BitSet) toClone.m_Genotype.clone();// allowed, has + // only native + // typed + // fields + this.m_GenotypeLength = toClone.m_GenotypeLength; + } + + /** + * This method creates a deep copy of an individual. It should clone all + * objects contained by this object. + * + * @return An deep copy of this {@link GAIndividual} + */ + @Override + public Object clone() { + + GAIndividual c = new GAIndividual(m_GenotypeLength); + c.setGenotype((BitSet) this.m_Genotype.clone()); + return c; + + // return new GAIndividual(this); + } + + /** + * This method evaluates the GAIndividual as a simple + * "maximize number of bits" problem. The fitness is the number of true bits + * in m_Genotype. Best fitness is reached if there are no false bits. + * + * @return The number of false bits (less is better!) + */ + public double evaluateAsMaxiBits() { + int zeros = 0; + for (int i = 0; i < m_GenotypeLength; i++) { + if (!m_Genotype.get(i)) { + zeros++; + } + } + return zeros; + } + + /** + * This method will return a string description of the GAIndividal notably + * the genotype: '0011000101' + * + * @return A descriptive string + */ + public String getStringRepresentation() { + // this should return exactly the representation shown in the comment + // above: + // only 0 (for false bits) and 1 (for true bits) with no extra white + // space! + String representation = ""; + for (int i = 0; i < m_GenotypeLength; i++) { + representation = m_Genotype.get(i) ? representation + "1" + : representation + "0"; + + } + return representation; + } + + /** + * This method will allow the user to read the GA genotype + * + * @return BitSet + */ + public BitSet getGenotype() { + return m_Genotype; + } + + /** + * This method will allow the user to set the current GA genotype. Should + * check if the length of the BitSet and the genotype length match. + * + * @param b + * The new genotype of the Individual + */ + public void setGenotype(BitSet b) { + + this.m_Genotype = b; + + } + + /** + * This method allows the user to read the length of the genotype. This may + * be necessary since BitSet.length only returns the index of the last + * significant bit. + * + * @return The length of the genotype. + */ + public int getGenotypeLength() { + return m_GenotypeLength; + } + + /** + * This method performs a simple one point mutation in the genotype (script + * 5.2.2). Please use the tools.RandomNumberGenerator + */ + public void mutate() { + m_Genotype.flip(RandomNumberGenerator + .randomInt(0, m_GenotypeLength - 1)); + } + + /** + * This method performs a simple one point crossover of two GAIndividuals + * (script 5.2.1). Please use the tools.RandomNumberGenerator + * + * @return An array of length 2 with the two resulting GAIndivuals + */ + public static GAIndividual[] crossover(GAIndividual ind1, GAIndividual ind2) { + assert ind1.m_GenotypeLength == ind2.m_GenotypeLength; + + int splitPoint = RandomNumberGenerator.randomInt(0, + ind1.m_GenotypeLength - 1); + GAIndividual ind1Clone = (GAIndividual) ind1.clone(); + GAIndividual ind2Clone = (GAIndividual) ind2.clone(); + for (int i = splitPoint; i < ind1Clone.m_GenotypeLength; i++) { + ind1Clone.m_Genotype.set(i, ind2.m_Genotype.get(i)); + ind2Clone.m_Genotype.set(i, ind1.m_Genotype.get(i)); + + } + // System.out.println("______"); + // System.out.println(ind1.getStringRepresentation()); + // System.out.println(ind2.getStringRepresentation()); + // System.out.println(splitPoint); + // System.out.println(ind1Clone.getStringRepresentation()); + // System.out.println(ind2Clone.getStringRepresentation()); + + return new GAIndividual[] { ind2Clone, ind1Clone }; + } + + /** + * This method initializes the GA genotype randomly. Please use the + * tools.RandomNumberGenerator + */ + public void initGenotype() { + m_Genotype = new BitSet(m_GenotypeLength); + for (int i = 0; i < m_GenotypeLength; i++) { + m_Genotype.set(i, RandomNumberGenerator.randomBoolean()); + } + } + + @Override + public int compareTo(GAIndividual o) { + return ((Double) this.evaluateAsMaxiBits()).compareTo(o + .evaluateAsMaxiBits()); + } +} diff --git a/ea/Ub7/PBIL/src/hcMaxiBits/GeneticAlgorithm.java b/ea/Ub7/PBIL/src/hcMaxiBits/GeneticAlgorithm.java new file mode 100644 index 0000000..a8788b0 --- /dev/null +++ b/ea/Ub7/PBIL/src/hcMaxiBits/GeneticAlgorithm.java @@ -0,0 +1,161 @@ +package hcMaxiBits; + +/** + * This class implements a deterministic variant of the Genetic Algorithm described in the script, section 5.1.1. + */ +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.List; + +import tools.RandomNumberGenerator; + +public class GeneticAlgorithm { + /** The length of the genotype of the individuals **/ + private int m_GenotypeLength; + /** The number of individuals in the population **/ + private int m_Mu; + /** The number of children generated **/ + private int m_Lambda; + /** The number of single optimization steps to be evaluated **/ + private int m_OptimizationSteps; + /** The number of times the experiment is repeated **/ + private int m_MultiRuns; + /** Number of steps needed to reach best result **/ + private int m_OptimizationStepsNeeded = 0; + /** Current best individual **/ + private GAIndividual m_Best; + + /** + * This constructor sets up GeneticAlgorithm + * + * @param genotypeLength + * The length of the genotype of the individuals + * @param mu + * The number of individuals in the population + * @param lambda + * The number of children generated in each iteration + * @param optimizationSteps + * The number of single optimization steps to be evaluated + * (adjust as necessary) + * @param multiRuns + * The number of times the experiment is repeated (at least 10) + */ + public GeneticAlgorithm(int genotypeLength, int mu, int lambda, + int optimizationSteps, int multiRuns) { + assert multiRuns > 9; // use run configurations: vmargument: -ea + + this.m_GenotypeLength = genotypeLength; + this.m_Mu = mu; + this.m_Lambda = lambda; + this.m_OptimizationSteps = optimizationSteps; + this.m_MultiRuns = multiRuns; + this.m_Best = null; + + } + + /** + * This method will initialize the GeneticAlgorithm + */ + public void initialize() { + + m_OptimizationStepsNeeded = 0; + + } + + /** + * This method will optimize the evaulateAsMaxiBits Problem. Use + * m_FitnessCallsNeeded to return the number of FitnessCalls (e.g., calling + * evaluateAsMaxiBits()) needed to find the optimum. The optimization should + * terminate after m_FitnessCalls. + */ + public void optimize() { + // The deterministic Genetic Algorithm works as follows: + // initialize the population + // while maxSteps not reached do + // do select 2 (distinct) parents from population randomly + // perform crossover to generate two children + // until lambda children generated + // mutate the children (p_m = 0.5, use randomBoolean from + // RandomNumberGenerator) + // calculate the fitness of the children (use + // GAIndividual.evaluateAsMaxiBits()) + // select the mu best individuals for the new population + // od + + List population = new ArrayList(); + for (int i = 0; i < m_Mu; i++) { + population.add(new GAIndividual(m_GenotypeLength)); + + } + + for (int i = 0; i < m_OptimizationSteps; i++) { + + ArrayList children = new ArrayList(); + for (int a = 0; a < (m_Lambda / 2); a++) { + GAIndividual parent1; + GAIndividual parent2; + do { + parent1 = population.get(RandomNumberGenerator.randomInt(0, + m_Mu - 1)); + parent2 = population.get(RandomNumberGenerator.randomInt(0, + m_Mu - 1)); + } while (parent1 == parent2);// distinct parents + children.addAll(Arrays.asList(GAIndividual.crossover(parent1, + parent2))); + + } + for (GAIndividual child : children) { + if (RandomNumberGenerator.randomBoolean()) { + child.mutate(); + } + } + + Collections.sort(children); // comparable + // implemented + // in + // GAIndividual + // m_population = m_population.subList(0, m_Mu); + + m_Best = children.get(0); + population = children.subList(0, m_Mu); + if (m_Best.evaluateAsMaxiBits() != 0) { + m_OptimizationStepsNeeded++; + } + System.out.println(i + " " + (m_Best.evaluateAsMaxiBits())); + } + } + + /** + * This main method will start a simple GeneticAlgorithm search. No + * arguments necessary. + * + * @param args + */ + public static void main(String[] args) { + // TODO: parameters for the GeneticAlgorithm, adjust these values as + // necessary + int genotypeLength = 50; + int mu = 15; + int lambda = 50; + // int optimizationSteps = 100000; + int optimizationSteps = 1000; + int multiRuns = 1; + GeneticAlgorithm program = new GeneticAlgorithm(genotypeLength, mu, + lambda, optimizationSteps, multiRuns); + int TmpMeanCalls = 0, TmpMeanFitness = 0; + // perform repeated optimization + for (int i = 0; i < program.m_MultiRuns; i++) { + + program.initialize(); + program.optimize(); + TmpMeanCalls += program.m_OptimizationStepsNeeded; + TmpMeanFitness += program.m_Best.evaluateAsMaxiBits(); + } + TmpMeanCalls = TmpMeanCalls / program.m_MultiRuns; // ja klar 3.9 =3 + TmpMeanFitness = TmpMeanFitness / program.m_MultiRuns; + System.out.println("(" + program.m_MultiRuns + "/" + + program.m_OptimizationSteps + ") Mean Fitness : " + + TmpMeanFitness + " Mean Calls needed: " + TmpMeanCalls); + } +} diff --git a/ea/Ub7/PBIL/src/hcMaxiBits/HillClimbing.java b/ea/Ub7/PBIL/src/hcMaxiBits/HillClimbing.java new file mode 100644 index 0000000..59c8350 --- /dev/null +++ b/ea/Ub7/PBIL/src/hcMaxiBits/HillClimbing.java @@ -0,0 +1,94 @@ +package hcMaxiBits; + +public class HillClimbing { + /** The length of the genotype of the individuals **/ + private int m_GenotypeLength; + /** The number of single optimization steps to be evaluated **/ + private int m_OptimizationSteps; + /** The number of times the experiment is repeated **/ + private int m_MultiRuns; + /** Number of steps needed to reach best result **/ + private int m_OptimizationStepsNeeded = 0; + /** Current best individual **/ + private GAIndividual m_Best; + + /** + * This constructor sets up HillClimber + * + * @param genotypeLength + * The length of the genotype of the individuals + * @param optimizationSteps + * The number of single optimization steps to be evaluated + * (adjust as necessary) + * @param multiRuns + * The number of times the experiment is repeated (at least 10) + */ + public HillClimbing(int genotypeLength, int optimizationSteps, int multiRuns) { + assert multiRuns > 9; + this.m_GenotypeLength = genotypeLength; + this.m_OptimizationSteps = optimizationSteps; + this.m_MultiRuns = multiRuns; + } + + /** + * This method will initialize the HillClimber + */ + public void initialize() { + m_Best = new GAIndividual(m_GenotypeLength); + m_OptimizationStepsNeeded = 0; + } + + /** + * This method will optimize the defaultEvaulateAsMiniBits Problem. Use + * m_FitnessCallsNeeded to return the number of FitnessCalls (e.g., calling + * evaluateAsMaxiBits()) needed to find the optimum. The optimization should + * terminate after m_FitnessCalls. + */ + public void optimize() { + // nur mutieren oder auch crossover? + + // TODO implement this + // use GAIndividual.evaluateAsMaxiBits() to evaluate the fitness of an + // individual and call it m_OptimizationSteps times before terminating + for (int i = 0; i < m_OptimizationSteps; i++) { + GAIndividual clone = (GAIndividual) m_Best.clone(); + clone.mutate(); + m_Best = clone.evaluateAsMaxiBits() <= m_Best.evaluateAsMaxiBits() ? clone + : m_Best; + + if (m_Best.evaluateAsMaxiBits() != 0) { + m_OptimizationStepsNeeded++; + } + } + } + + /** + * This main method will start a simple hill climber. No arguments + * necessary. + * + * @param args + */ + public static void main(String[] args) { + // TODO: parameters for the HillClimber, adjust these values as + // necessary + int genotypeLength = 50; + int optimizationSteps = 1000; + int multiRuns = 100; + HillClimbing program = new HillClimbing(genotypeLength, + optimizationSteps, multiRuns); + int TmpMeanCalls = 0, TmpMeanFitness = 0; + // perform repeated optimization + for (int i = 0; i < program.m_MultiRuns; i++) { + program.initialize(); + program.optimize(); + TmpMeanCalls += program.m_OptimizationStepsNeeded; + TmpMeanFitness += program.m_Best.evaluateAsMaxiBits(); + + } + TmpMeanCalls = TmpMeanCalls / program.m_MultiRuns; + TmpMeanFitness = TmpMeanFitness / program.m_MultiRuns; + System.out.println("(" + program.m_MultiRuns + "/" + + program.m_OptimizationSteps + ") Mean Fitness : " + + TmpMeanFitness + " Mean Calls needed: " + TmpMeanCalls); + } +} diff --git a/ea/Ub7/PBIL/src/hcTwin/GAIndividualTwin.java b/ea/Ub7/PBIL/src/hcTwin/GAIndividualTwin.java new file mode 100644 index 0000000..15bd912 --- /dev/null +++ b/ea/Ub7/PBIL/src/hcTwin/GAIndividualTwin.java @@ -0,0 +1,173 @@ +package hcTwin; + +//import tools.RandomNumberGenerator; + +import java.util.BitSet; + +import tools.RandomNumberGenerator; + +public class GAIndividualTwin implements Comparable { + protected BitSet m_Genotype; + protected int m_GenotypeLength; + + /** Constructor **/ + public GAIndividualTwin(int genotypeLength) { + // This method should call initGenotype() to initialize the genotype + this.m_GenotypeLength = genotypeLength; + initGenotype(); + } + + /** + * cloning constructor + * + * @param toClone + */ + private GAIndividualTwin(GAIndividualTwin toClone) { + this.m_Genotype = (BitSet) toClone.m_Genotype.clone();// allowed, has + // only native + // typed + // fields + this.m_GenotypeLength = toClone.m_GenotypeLength; + } + + /** + * This method creates a deep copy of an individual. It should clone all + * objects contained by this object. + * + * @return An deep copy of this {@link GAIndividualTwin} + */ + @Override + public Object clone() { + + GAIndividualTwin c = new GAIndividualTwin(m_GenotypeLength); + c.setGenotype((BitSet) this.m_Genotype.clone()); + return c; + + // return new GAIndividual(this); + } + + public double evaluateAsTwin() { + int f1 = 0; + int f2 = 0; + for (int i = 0; i < (m_GenotypeLength / 2); i++) { + if (m_Genotype.get(i)) { + f1++; + } + } + for (int i = (m_GenotypeLength / 2); i < m_GenotypeLength; i++) { + if (m_Genotype.get(i)) { + f2++; + } + } + return (m_GenotypeLength / 2) - Math.abs(f1 - f2); + } + + /** + * This method will return a string description of the GAIndividal notably + * the genotype: '0011000101' + * + * @return A descriptive string + */ + public String getStringRepresentation() { + // this should return exactly the representation shown in the comment + // above: + // only 0 (for false bits) and 1 (for true bits) with no extra white + // space! + String representation = ""; + for (int i = 0; i < m_GenotypeLength; i++) { + representation = m_Genotype.get(i) ? representation + "1" + : representation + "0"; + + } + return representation; + } + + /** + * This method will allow the user to read the GA genotype + * + * @return BitSet + */ + public BitSet getGenotype() { + return m_Genotype; + } + + /** + * This method will allow the user to set the current GA genotype. Should + * check if the length of the BitSet and the genotype length match. + * + * @param b + * The new genotype of the Individual + */ + public void setGenotype(BitSet b) { + + this.m_Genotype = b; + + } + + /** + * This method allows the user to read the length of the genotype. This may + * be necessary since BitSet.length only returns the index of the last + * significant bit. + * + * @return The length of the genotype. + */ + public int getGenotypeLength() { + return m_GenotypeLength; + } + + /** + * This method performs a simple one point mutation in the genotype (script + * 5.2.2). Please use the tools.RandomNumberGenerator + */ + public void mutate() { + m_Genotype.flip(RandomNumberGenerator + .randomInt(0, m_GenotypeLength - 1)); + } + + /** + * This method performs a simple one point crossover of two GAIndividuals + * (script 5.2.1). Please use the tools.RandomNumberGenerator + * + * @return An array of length 2 with the two resulting GAIndivuals + */ + public static GAIndividualTwin[] crossover(GAIndividualTwin ind1, + GAIndividualTwin ind2) { + assert ind1.m_GenotypeLength == ind2.m_GenotypeLength; + + int splitPoint = RandomNumberGenerator.randomInt(0, + ind1.m_GenotypeLength - 1); + GAIndividualTwin ind1Clone = (GAIndividualTwin) ind1.clone(); + GAIndividualTwin ind2Clone = (GAIndividualTwin) ind2.clone(); + for (int i = splitPoint; i < ind1Clone.m_GenotypeLength; i++) { + ind1Clone.m_Genotype.set(i, ind2.m_Genotype.get(i)); + ind2Clone.m_Genotype.set(i, ind1.m_Genotype.get(i)); + + } + // System.out.println("______"); + // System.out.println(ind1.getStringRepresentation()); + // System.out.println(ind2.getStringRepresentation()); + // System.out.println(splitPoint); + // System.out.println(ind1Clone.getStringRepresentation()); + // System.out.println(ind2Clone.getStringRepresentation()); + + return new GAIndividualTwin[] { ind2Clone, ind1Clone }; + } + + /** + * This method initializes the GA genotype randomly. Please use the + * tools.RandomNumberGenerator + */ + public void initGenotype() { + m_Genotype = new BitSet(m_GenotypeLength); + for (int i = 0; i < m_GenotypeLength; i++) { + m_Genotype.set(i, RandomNumberGenerator.randomBoolean()); + } + } + + @Override + public int compareTo(GAIndividualTwin o) { + // return ((Double) this.evaluateAsMaxiBits()).compareTo(o + // .evaluateAsMaxiBits()); + return ((Double) this.evaluateAsTwin()).compareTo(o.evaluateAsTwin()); + } +} diff --git a/ea/Ub7/PBIL/src/hcTwin/GeneticAlgorithmTwin.java b/ea/Ub7/PBIL/src/hcTwin/GeneticAlgorithmTwin.java new file mode 100644 index 0000000..c43e1f8 --- /dev/null +++ b/ea/Ub7/PBIL/src/hcTwin/GeneticAlgorithmTwin.java @@ -0,0 +1,161 @@ +package hcTwin; + +/** + * This class implements a deterministic variant of the Genetic Algorithm described in the script, section 5.1.1. + */ +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.List; + +import tools.RandomNumberGenerator; + +public class GeneticAlgorithmTwin { + /** The length of the genotype of the individuals **/ + private int m_GenotypeLength; + /** The number of individuals in the population **/ + private int m_Mu; + /** The number of children generated **/ + private int m_Lambda; + /** The number of single optimization steps to be evaluated **/ + private int m_OptimizationSteps; + /** The number of times the experiment is repeated **/ + private int m_MultiRuns; + /** Number of steps needed to reach best result **/ + private int m_OptimizationStepsNeeded = 0; + /** Current best individual **/ + private GAIndividualTwin m_Best; + + /** + * This constructor sets up GeneticAlgorithm + * + * @param genotypeLength + * The length of the genotype of the individuals + * @param mu + * The number of individuals in the population + * @param lambda + * The number of children generated in each iteration + * @param optimizationSteps + * The number of single optimization steps to be evaluated + * (adjust as necessary) + * @param multiRuns + * The number of times the experiment is repeated (at least 10) + */ + public GeneticAlgorithmTwin(int genotypeLength, int mu, int lambda, + int optimizationSteps, int multiRuns) { + assert multiRuns > 9; // use run configurations: vmargument: -ea + + this.m_GenotypeLength = genotypeLength; + this.m_Mu = mu; + this.m_Lambda = lambda; + this.m_OptimizationSteps = optimizationSteps; + this.m_MultiRuns = multiRuns; + this.m_Best = null; + + } + + /** + * This method will initialize the GeneticAlgorithm + */ + public void initialize() { + + m_OptimizationStepsNeeded = 0; + + } + + /** + * This method will optimize the evaulateAsMaxiBits Problem. Use + * m_FitnessCallsNeeded to return the number of FitnessCalls (e.g., calling + * evaluateAsMaxiBits()) needed to find the optimum. The optimization should + * terminate after m_FitnessCalls. + */ + public void optimize() { + // The deterministic Genetic Algorithm works as follows: + // initialize the population + // while maxSteps not reached do + // do select 2 (distinct) parents from population randomly + // perform crossover to generate two children + // until lambda children generated + // mutate the children (p_m = 0.5, use randomBoolean from + // RandomNumberGenerator) + // calculate the fitness of the children (use + // GAIndividual.evaluateAsMaxiBits()) + // select the mu best individuals for the new population + // od + + List population = new ArrayList(); + for (int i = 0; i < m_Mu; i++) { + population.add(new GAIndividualTwin(m_GenotypeLength)); + + } + + for (int i = 0; i < m_OptimizationSteps; i++) { + + ArrayList children = new ArrayList(); + for (int a = 0; a < (m_Lambda / 2); a++) { + GAIndividualTwin parent1; + GAIndividualTwin parent2; + do { + parent1 = population.get(RandomNumberGenerator.randomInt(0, + m_Mu - 1)); + parent2 = population.get(RandomNumberGenerator.randomInt(0, + m_Mu - 1)); + } while (parent1 == parent2);// distinct parents + children.addAll(Arrays.asList(GAIndividualTwin.crossover( + parent1, parent2))); + + } + for (GAIndividualTwin child : children) { + if (RandomNumberGenerator.randomBoolean()) { + child.mutate(); + } + } + + Collections.sort(children); // comparable + // implemented + // in + // GAIndividual + // m_population = m_population.subList(0, m_Mu); + + m_Best = children.get(0); + population = children.subList(0, m_Mu); + if (m_Best.evaluateAsTwin() != 0) { + m_OptimizationStepsNeeded++; + } + + } + } + + /** + * This main method will start a simple GeneticAlgorithm search. No + * arguments necessary. + * + * @param args + */ + public static void main(String[] args) { + // TODO: parameters for the GeneticAlgorithm, adjust these values as + // necessary + int genotypeLength = 50; + int mu = 15; + int lambda = 50; + // int optimizationSteps = 100000; + int optimizationSteps = 1000; + int multiRuns = 1000; + GeneticAlgorithmTwin program = new GeneticAlgorithmTwin(genotypeLength, + mu, lambda, optimizationSteps, multiRuns); + int TmpMeanCalls = 0, TmpMeanFitness = 0; + // perform repeated optimization + for (int i = 0; i < program.m_MultiRuns; i++) { + + program.initialize(); + program.optimize(); + TmpMeanCalls += program.m_OptimizationStepsNeeded; + TmpMeanFitness += program.m_Best.evaluateAsTwin(); + } + TmpMeanCalls = TmpMeanCalls / program.m_MultiRuns; // ja klar 3.9 =3 + TmpMeanFitness = TmpMeanFitness / program.m_MultiRuns; + System.out.println("(" + program.m_MultiRuns + "/" + + program.m_OptimizationSteps + ") Mean Fitness : " + + TmpMeanFitness + " Mean Calls needed: " + TmpMeanCalls); + } +} diff --git a/ea/Ub7/PBIL/src/hcTwin/HillClimbingTwin.java b/ea/Ub7/PBIL/src/hcTwin/HillClimbingTwin.java new file mode 100644 index 0000000..b478724 --- /dev/null +++ b/ea/Ub7/PBIL/src/hcTwin/HillClimbingTwin.java @@ -0,0 +1,95 @@ +package hcTwin; + +public class HillClimbingTwin { + /** The length of the genotype of the individuals **/ + private int m_GenotypeLength; + /** The number of single optimization steps to be evaluated **/ + private int m_OptimizationSteps; + /** The number of times the experiment is repeated **/ + private int m_MultiRuns; + /** Number of steps needed to reach best result **/ + private int m_OptimizationStepsNeeded = 0; + /** Current best individual **/ + private GAIndividualTwin m_Best; + + /** + * This constructor sets up HillClimber + * + * @param genotypeLength + * The length of the genotype of the individuals + * @param optimizationSteps + * The number of single optimization steps to be evaluated + * (adjust as necessary) + * @param multiRuns + * The number of times the experiment is repeated (at least 10) + */ + public HillClimbingTwin(int genotypeLength, int optimizationSteps, + int multiRuns) { + assert multiRuns > 9; + this.m_GenotypeLength = genotypeLength; + this.m_OptimizationSteps = optimizationSteps; + this.m_MultiRuns = multiRuns; + } + + /** + * This method will initialize the HillClimber + */ + public void initialize() { + m_Best = new GAIndividualTwin(m_GenotypeLength); + m_OptimizationStepsNeeded = 0; + } + + /** + * This method will optimize the defaultEvaulateAsMiniBits Problem. Use + * m_FitnessCallsNeeded to return the number of FitnessCalls (e.g., calling + * evaluateAsMaxiBits()) needed to find the optimum. The optimization should + * terminate after m_FitnessCalls. + */ + public void optimize() { + // nur mutieren oder auch crossover? + + // TODO implement this + // use GAIndividual.evaluateAsMaxiBits() to evaluate the fitness of an + // individual and call it m_OptimizationSteps times before terminating + for (int i = 0; i < m_OptimizationSteps; i++) { + GAIndividualTwin clone = (GAIndividualTwin) m_Best.clone(); + clone.mutate(); + m_Best = clone.evaluateAsTwin() <= m_Best.evaluateAsTwin() ? clone + : m_Best; + + if (m_Best.evaluateAsTwin() != 0) { + m_OptimizationStepsNeeded++; + } + } + } + + /** + * This main method will start a simple hill climber. No arguments + * necessary. + * + * @param args + */ + public static void main(String[] args) { + // TODO: parameters for the HillClimber, adjust these values as + // necessary + int genotypeLength = 50; + int optimizationSteps = 1000; + int multiRuns = 100; + HillClimbingTwin program = new HillClimbingTwin(genotypeLength, + optimizationSteps, multiRuns); + int TmpMeanCalls = 0, TmpMeanFitness = 0; + // perform repeated optimization + for (int i = 0; i < program.m_MultiRuns; i++) { + program.initialize(); + program.optimize(); + TmpMeanCalls += program.m_OptimizationStepsNeeded; + TmpMeanFitness += program.m_Best.evaluateAsTwin(); + + } + TmpMeanCalls = TmpMeanCalls / program.m_MultiRuns; + TmpMeanFitness = TmpMeanFitness / program.m_MultiRuns; + System.out.println("(" + program.m_MultiRuns + "/" + + program.m_OptimizationSteps + ") Mean Fitness : " + + TmpMeanFitness + " Mean Calls needed: " + TmpMeanCalls); + } +} diff --git a/ea/Ub7/PBIL/src/pbilMaxiBits/PBIL.java b/ea/Ub7/PBIL/src/pbilMaxiBits/PBIL.java new file mode 100644 index 0000000..fd438e9 --- /dev/null +++ b/ea/Ub7/PBIL/src/pbilMaxiBits/PBIL.java @@ -0,0 +1,144 @@ +package pbilMaxiBits; +/** + * This class implements a deterministic variant of the Genetic Algorithm described in the script, section 5.1.1. + */ +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +public class PBIL { + /** The length of the genotype of the individuals **/ + private int m_GenotypeLength; + /** The number of individuals in the population **/ + private int m_Mu; + /** The number of children generated **/ + private double m_Lambda; + /** The number of single optimization steps to be evaluated **/ + private int m_OptimizationSteps; + /** The number of times the experiment is repeated **/ + private int m_MultiRuns; + /** Number of steps needed to reach best result **/ + private int m_OptimizationStepsNeeded = 0; + /** mean fitness **/ + private double meanFitness; + + private double[] propVector; + private double learnrate; + + /** + * This constructor sets up GeneticAlgorithm + * + * @param genotypeLength + * The length of the genotype of the individuals + * @param mu + * The number of individuals in the population + * @param lambda + * The number of children generated in each iteration + * @param optimizationSteps + * The number of single optimization steps to be evaluated + * (adjust as necessary) + * @param multiRuns + * The number of times the experiment is repeated (at least 10) + */ + public PBIL(int genotypeLength, int mu, double lambda, + int optimizationSteps, int multiRuns) { + assert multiRuns > 9; // use run configurations: vmargument: -ea + + this.m_GenotypeLength = genotypeLength; + this.m_Lambda = lambda; + this.m_Mu = mu; + this.m_OptimizationSteps = optimizationSteps; + this.m_MultiRuns = multiRuns; + + // this.learnrate = 1 / lambda; + this.learnrate = 0.05; + + } + + /** + * This method will initialize the GeneticAlgorithm + */ + public void initialize() { + + m_OptimizationStepsNeeded = 0; + this.propVector = new double[m_GenotypeLength]; + for (int i = 0; i < propVector.length; i++) { + propVector[i] = 0.5; + } + + } + + /** + * This method will optimize the evaulateAsMaxiBits Problem. Use + * m_FitnessCallsNeeded to return the number of FitnessCalls (e.g., calling + * evaluateAsMaxiBits()) needed to find the optimum. The optimization should + * terminate after m_FitnessCalls. + */ + public void optimize() { + for (int i = 0; i < m_OptimizationSteps; i++) { + List population = new ArrayList(); + for (int j = 0; j < m_Mu; j++) { + population.add(new PBilIndividual(propVector)); + } + Collections.sort(population, Collections.reverseOrder()); // comparable + // implemente + // in + + List m_Best = population.subList(0, m_Mu); + // System.out.println("Print best:"); + // System.out.println(m_Best.get(0).getStringRepresentation()); + for (PBilIndividual p : m_Best) { + for (int k = 0; k < m_GenotypeLength; k++) { + propVector[k] = (propVector[k] * (1 - learnrate)) + + ((p.getGenotype().get(k) ? 1 : 0) * learnrate); + } + } + // System.out.println(Arrays.toString(propVector)); + double fitnessPV = 0; + for (double p : propVector) { + fitnessPV += p; + } + double oldFitness = meanFitness; + meanFitness = propVector.length - fitnessPV; + if (oldFitness != meanFitness) { + m_OptimizationStepsNeeded++; + } + // System.out.println(i + " " + meanFitness); + + } + } + + /** + * This main method will start a simple GeneticAlgorithm search. No + * arguments necessary. + * + * @param args + */ + public static void main(String[] args) { + // TODO: parameters for the GeneticAlgorithm, adjust these values as + // necessary + int genotypeLength = 50; + int mu = 15; + int lambda = 50; + int optimizationSteps = 1000; + // int optimizationSteps = 100; + int multiRuns = 100; + PBIL program = new PBIL(genotypeLength, mu, lambda, optimizationSteps, + multiRuns); + int TmpMeanCalls = 0, TmpMeanFitness = 0; + // perform repeated optimization + for (int i = 0; i < program.m_MultiRuns; i++) { + + program.initialize(); + program.optimize(); + TmpMeanCalls += program.m_OptimizationStepsNeeded; + TmpMeanFitness += program.meanFitness; + } + TmpMeanCalls = TmpMeanCalls / program.m_MultiRuns; + TmpMeanFitness = TmpMeanFitness / program.m_MultiRuns; + System.out.println("(" + program.m_MultiRuns + "/" + + program.m_OptimizationSteps + ") Mean Fitness : " + + TmpMeanFitness + " Mean Calls needed: " + TmpMeanCalls); + } + // (1000/1000) Mean Fitness : 0 Mean Calls needed: 19 +} diff --git a/ea/Ub7/PBIL/src/pbilMaxiBits/PBilIndividual.java b/ea/Ub7/PBIL/src/pbilMaxiBits/PBilIndividual.java new file mode 100644 index 0000000..7377b3d --- /dev/null +++ b/ea/Ub7/PBIL/src/pbilMaxiBits/PBilIndividual.java @@ -0,0 +1,163 @@ +package pbilMaxiBits; +//import tools.RandomNumberGenerator; + +import java.util.BitSet; +import java.util.Random; + +/** + * @author Maximus + * + */ +public class PBilIndividual implements Comparable { + protected BitSet m_Genotype; + protected int m_GenotypeLength; + protected Random r = new Random(); + + /** Constructor **/ + public PBilIndividual(double[] propVector) { + // This method should call initGenotype() to initialize the genotype + this.m_GenotypeLength = propVector.length; + initGenotype(propVector); + + } + + /** + * cloning constructor + * + * @param toClone + */ + private PBilIndividual(PBilIndividual toClone) { + this.m_Genotype = (BitSet) toClone.m_Genotype.clone();// allowed, has + // only native + // typed + // fields + this.m_GenotypeLength = toClone.m_GenotypeLength; + } + + /** + * This method creates a deep copy of an individual. It should clone all + * objects contained by this object. + * + * @return An deep copy of this {@link PBilIndividual} + */ + @Override + public Object clone() { + + PBilIndividual c = new PBilIndividual(new double[m_GenotypeLength]); + c.setGenotype((BitSet) this.m_Genotype.clone()); + return c; + + // return new GAIndividual(this); + } + + /** + * This method evaluates the GAIndividual as a simple + * "maximize number of bits" problem. The fitness is the number of true bits + * in m_Genotype. Best fitness is reached if there are no false bits. + * + * @return The number of false bits (less is better!) + */ + public double evaluateAsMaxiBits() { + int zeros = 0; + for (int i = 0; i < m_GenotypeLength; i++) { + if (!m_Genotype.get(i)) { + zeros++; + } + } + return zeros; + } + + /** + * + * @return best fitness ==0 + */ + public double evaluateAsTwin() { + int f1 = 0; + int f2 = 0; + for (int i = 0; i < (m_GenotypeLength / 2); i++) { + if (m_Genotype.get(i)) { + f1++; + } + } + for (int i = (m_GenotypeLength / 2); i < m_GenotypeLength; i++) { + if (m_Genotype.get(i)) { + f2++; + } + } + return (m_GenotypeLength / 2) - Math.abs(f1 - f2); + } + + /** + * This method will return a string description of the GAIndividal notably + * the genotype: '0011000101' + * + * @return A descriptive string + */ + public String getStringRepresentation() { + // this should return exactly the representation shown in the comment + // above: + // only 0 (for false bits) and 1 (for true bits) with no extra white + // space! + String representation = ""; + for (int i = 0; i < m_GenotypeLength; i++) { + representation = m_Genotype.get(i) ? representation + "1" + : representation + "0"; + + } + return representation; + } + + /** + * This method will allow the user to read the GA genotype + * + * @return BitSet + */ + public BitSet getGenotype() { + return m_Genotype; + } + + /** + * This method will allow the user to set the current GA genotype. Should + * check if the length of the BitSet and the genotype length match. + * + * @param b + * The new genotype of the Individual + */ + public void setGenotype(BitSet b) { + + this.m_Genotype = b; + + } + + /** + * This method allows the user to read the length of the genotype. This may + * be necessary since BitSet.length only returns the index of the last + * significant bit. + * + * @return The length of the genotype. + */ + public int getGenotypeLength() { + return m_GenotypeLength; + } + + /** + * This method initializes the GA genotype randomly. Please use the + * tools.RandomNumberGenerator + * + * @param propVector + */ + public void initGenotype(double[] propVector) { + m_Genotype = new BitSet(m_GenotypeLength); + for (int i = 0; i < m_GenotypeLength; i++) { + if (r.nextDouble() < propVector[i]) { + m_Genotype.set(i); + } + } + } + + @Override + public int compareTo(PBilIndividual o) { + return ((Double) this.evaluateAsMaxiBits()).compareTo(o + .evaluateAsMaxiBits()); + } +} diff --git a/ea/Ub7/PBIL/src/pbilMaxiBits/RandomNumberGenerator.java b/ea/Ub7/PBIL/src/pbilMaxiBits/RandomNumberGenerator.java new file mode 100644 index 0000000..8873ef0 --- /dev/null +++ b/ea/Ub7/PBIL/src/pbilMaxiBits/RandomNumberGenerator.java @@ -0,0 +1,48 @@ +package pbilMaxiBits; + + +import java.util.Random; + +public class RandomNumberGenerator { + + private static Random random; + private static long randomSeed; + + static { + randomSeed = System.currentTimeMillis(); + random = new Random(randomSeed); + } + + /** + * This method returns a evenly distributed integer value. The boundaries + * are included. + * + * @param lo + * Lower bound. + * @param hi + * Upper bound. + * @return Random integer from[lo,hi] + */ + public static int randomInt(int lo, int hi) { + return (Math.abs(random.nextInt()) % (hi - lo + 1)) + lo; + } + + /** + * This method returns 0 or 1 with same probability + * + * @return Random bit + */ + public static int randomBit() { + return randomInt(0, 1); + } + + /** + * This method returns true or false with same + * probability + * + * @return Random boolean value + */ + public static boolean randomBoolean() { + return (randomBit() == 1); + } +} diff --git a/ea/Ub7/PBIL/src/pbilTwin/PBILTwin.java b/ea/Ub7/PBIL/src/pbilTwin/PBILTwin.java new file mode 100644 index 0000000..bac1a70 --- /dev/null +++ b/ea/Ub7/PBIL/src/pbilTwin/PBILTwin.java @@ -0,0 +1,151 @@ +package pbilTwin; + +/** + * This class implements a deterministic variant of the Genetic Algorithm described in the script, section 5.1.1. + */ +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +public class PBILTwin { + /** The length of the genotype of the individuals **/ + private int m_GenotypeLength; + /** The number of individuals in the population **/ + private int m_Mu; + /** The number of children generated **/ + private double m_Lambda; + /** The number of single optimization steps to be evaluated **/ + private int m_OptimizationSteps; + /** The number of times the experiment is repeated **/ + private int m_MultiRuns; + /** Number of steps needed to reach best result **/ + private int m_OptimizationStepsNeeded = 0; + /** mean fitness **/ + private double meanFitness; + + private double[] propVector; + private double learnrate; + + /** + * This constructor sets up GeneticAlgorithm + * + * @param genotypeLength + * The length of the genotype of the individuals + * @param mu + * The number of individuals in the population + * @param lambda + * The number of children generated in each iteration + * @param optimizationSteps + * The number of single optimization steps to be evaluated + * (adjust as necessary) + * @param multiRuns + * The number of times the experiment is repeated (at least 10) + */ + public PBILTwin(int genotypeLength, int mu, double lambda, + int optimizationSteps, int multiRuns) { + assert multiRuns > 9; // use run configurations: vmargument: -ea + + this.m_GenotypeLength = genotypeLength; + this.m_Lambda = lambda; + this.m_Mu = mu; + this.m_OptimizationSteps = optimizationSteps; + this.m_MultiRuns = multiRuns; + this.propVector = new double[m_GenotypeLength]; + + // this.learnrate = 1 / lambda; + this.learnrate = 0.05; + + } + + /** + * This method will initialize the GeneticAlgorithm + */ + public void initialize() { + + m_OptimizationStepsNeeded = 0; + for (int i = 0; i < propVector.length; i++) { + propVector[i] = 0.5; + } + } + + /** + * This method will optimize the evaulateAsMaxiBits Problem. Use + * m_FitnessCallsNeeded to return the number of FitnessCalls (e.g., calling + * evaluateAsMaxiBits()) needed to find the optimum. The optimization should + * terminate after m_FitnessCalls. + */ + public void optimize() { + for (int i = 0; i < m_OptimizationSteps; i++) { + List population = new ArrayList(); + for (int j = 0; j < m_Mu; j++) { + population.add(new PBIndividualTwin(propVector)); + } + Collections.sort(population, Collections.reverseOrder()); // comparable + // implemente + // in + // PBilIndividual m_population = + // m_population.subList(0, m_Mu); + // for (int j = 0; j < population.size(); j++) { + // System.out.println(population.get(j).getStringRepresentation()); + // } + List m_Best = population.subList(0, m_Mu); + // System.out.println("Print best:"); + // System.out.println(m_Best.get(0).getStringRepresentation()); + for (PBIndividualTwin p : m_Best) { + for (int k = 0; k < m_GenotypeLength; k++) { + propVector[k] = (propVector[k] * (1 - learnrate)) + + ((p.getGenotype().get(k) ? 1 : 0) * learnrate); + } + } + // System.out.println(Arrays.toString(propVector)); + double fitnessPV = 0; + for (int j = 0; j < propVector.length; j++) { + double p = propVector[j]; + if (j < (propVector.length / 2)) { + fitnessPV += p; + } else { + fitnessPV -= p; + } + } + double oldFitness = meanFitness; + meanFitness = (m_GenotypeLength / 2) - Math.abs(fitnessPV); + if (oldFitness != meanFitness) { + m_OptimizationStepsNeeded++; + } + + } + } + + /** + * This main method will start a simple GeneticAlgorithm search. No + * arguments necessary. + * + * @param args + */ + public static void main(String[] args) { + // TODO: parameters for the GeneticAlgorithm, adjust these values as + // necessary + int genotypeLength = 50; + int mu = 15; + int lambda = 50; + int optimizationSteps = 1000; + // int optimizationSteps = 100; + int multiRuns = 100; + PBILTwin program = new PBILTwin(genotypeLength, mu, lambda, + optimizationSteps, multiRuns); + int TmpMeanCalls = 0, TmpMeanFitness = 0; + // perform repeated optimization + for (int i = 0; i < program.m_MultiRuns; i++) { + + program.initialize(); + program.optimize(); + TmpMeanCalls += program.m_OptimizationStepsNeeded; + TmpMeanFitness += program.meanFitness; + } + TmpMeanCalls = TmpMeanCalls / program.m_MultiRuns; + TmpMeanFitness = TmpMeanFitness / program.m_MultiRuns; + System.out.println("(" + program.m_MultiRuns + "/" + + program.m_OptimizationSteps + ") Mean Fitness : " + + TmpMeanFitness + " Mean Calls needed: " + TmpMeanCalls); + } +} diff --git a/ea/Ub7/PBIL/src/pbilTwin/PBIndividualTwin.java b/ea/Ub7/PBIL/src/pbilTwin/PBIndividualTwin.java new file mode 100644 index 0000000..f8fd50a --- /dev/null +++ b/ea/Ub7/PBIL/src/pbilTwin/PBIndividualTwin.java @@ -0,0 +1,165 @@ +package pbilTwin; + +//import tools.RandomNumberGenerator; + +import java.util.BitSet; +import java.util.Random; + +/** + * @author Maximus + * + */ +public class PBIndividualTwin implements Comparable { + protected BitSet m_Genotype; + protected int m_GenotypeLength; + protected Random r = new Random(); + + /** Constructor **/ + public PBIndividualTwin(double[] propVector) { + // This method should call initGenotype() to initialize the genotype + this.m_GenotypeLength = propVector.length; + initGenotype(propVector); + + } + + /** + * cloning constructor + * + * @param toClone + */ + private PBIndividualTwin(PBIndividualTwin toClone) { + this.m_Genotype = (BitSet) toClone.m_Genotype.clone();// allowed, has + // only native + // typed + // fields + this.m_GenotypeLength = toClone.m_GenotypeLength; + } + + /** + * This method creates a deep copy of an individual. It should clone all + * objects contained by this object. + * + * @return An deep copy of this {@link PBIndividualTwin} + */ + @Override + public Object clone() { + + PBIndividualTwin c = new PBIndividualTwin(new double[m_GenotypeLength]); + c.setGenotype((BitSet) this.m_Genotype.clone()); + return c; + + // return new GAIndividual(this); + } + + /** + * This method evaluates the GAIndividual as a simple + * "maximize number of bits" problem. The fitness is the number of true bits + * in m_Genotype. Best fitness is reached if there are no false bits. + * + * @return The number of false bits (less is better!) + */ + public double evaluateAsMaxiBits() { + int zeros = 0; + for (int i = 0; i < m_GenotypeLength; i++) { + if (!m_Genotype.get(i)) { + zeros++; + } + } + return zeros; + } + + /** + * + * @return best fitness ==0 + */ + public double evaluateAsTwin() { + int f1 = 0; + int f2 = 0; + for (int i = 0; i < (m_GenotypeLength / 2); i++) { + if (m_Genotype.get(i)) { + f1++; + } + } + for (int i = (m_GenotypeLength / 2); i < m_GenotypeLength; i++) { + if (m_Genotype.get(i)) { + f2++; + } + } + return (m_GenotypeLength / 2) - Math.abs(f1 - f2); + } + + /** + * This method will return a string description of the GAIndividal notably + * the genotype: '0011000101' + * + * @return A descriptive string + */ + public String getStringRepresentation() { + // this should return exactly the representation shown in the comment + // above: + // only 0 (for false bits) and 1 (for true bits) with no extra white + // space! + String representation = ""; + for (int i = 0; i < m_GenotypeLength; i++) { + representation = m_Genotype.get(i) ? representation + "1" + : representation + "0"; + + } + return representation; + } + + /** + * This method will allow the user to read the GA genotype + * + * @return BitSet + */ + public BitSet getGenotype() { + return m_Genotype; + } + + /** + * This method will allow the user to set the current GA genotype. Should + * check if the length of the BitSet and the genotype length match. + * + * @param b + * The new genotype of the Individual + */ + public void setGenotype(BitSet b) { + + this.m_Genotype = b; + + } + + /** + * This method allows the user to read the length of the genotype. This may + * be necessary since BitSet.length only returns the index of the last + * significant bit. + * + * @return The length of the genotype. + */ + public int getGenotypeLength() { + return m_GenotypeLength; + } + + /** + * This method initializes the GA genotype randomly. Please use the + * tools.RandomNumberGenerator + * + * @param propVector + */ + public void initGenotype(double[] propVector) { + m_Genotype = new BitSet(m_GenotypeLength); + for (int i = 0; i < m_GenotypeLength; i++) { + if (r.nextDouble() < propVector[i]) { + m_Genotype.set(i); + } + } + } + + @Override + public int compareTo(PBIndividualTwin o) { + // return ((Double) this.evaluateAsMaxiBits()).compareTo(o + // .evaluateAsMaxiBits()); + return ((Double) this.evaluateAsTwin()).compareTo(o.evaluateAsTwin()); + } +} diff --git a/ea/Ub7/PBIL/src/twin/PBILTwin.java b/ea/Ub7/PBIL/src/twin/PBILTwin.java deleted file mode 100644 index 27cd0d3..0000000 --- a/ea/Ub7/PBIL/src/twin/PBILTwin.java +++ /dev/null @@ -1,151 +0,0 @@ -package twin; - -/** - * This class implements a deterministic variant of the Genetic Algorithm described in the script, section 5.1.1. - */ -import java.util.ArrayList; -import java.util.Collections; -import java.util.List; - -public class PBILTwin { - /** The length of the genotype of the individuals **/ - private int m_GenotypeLength; - /** The number of individuals in the population **/ - private int m_Mu; - /** The number of children generated **/ - private double m_Lambda; - /** The number of single optimization steps to be evaluated **/ - private int m_OptimizationSteps; - /** The number of times the experiment is repeated **/ - private int m_MultiRuns; - /** Number of steps needed to reach best result **/ - private int m_OptimizationStepsNeeded = 0; - /** mean fitness **/ - private double meanFitness; - - private double[] propVector; - private double learnrate; - - /** - * This constructor sets up GeneticAlgorithm - * - * @param genotypeLength - * The length of the genotype of the individuals - * @param mu - * The number of individuals in the population - * @param lambda - * The number of children generated in each iteration - * @param optimizationSteps - * The number of single optimization steps to be evaluated - * (adjust as necessary) - * @param multiRuns - * The number of times the experiment is repeated (at least 10) - */ - public PBILTwin(int genotypeLength, int mu, double lambda, - int optimizationSteps, int multiRuns) { - assert multiRuns > 9; // use run configurations: vmargument: -ea - - this.m_GenotypeLength = genotypeLength; - this.m_Lambda = lambda; - this.m_Mu = mu; - this.m_OptimizationSteps = optimizationSteps; - this.m_MultiRuns = multiRuns; - this.propVector = new double[m_GenotypeLength]; - - // this.learnrate = 1 / lambda; - this.learnrate = 0.05; - - } - - /** - * This method will initialize the GeneticAlgorithm - */ - public void initialize() { - - m_OptimizationStepsNeeded = 0; - for (int i = 0; i < propVector.length; i++) { - propVector[i] = 0.5; - } - } - - /** - * This method will optimize the evaulateAsMaxiBits Problem. Use - * m_FitnessCallsNeeded to return the number of FitnessCalls (e.g., calling - * evaluateAsMaxiBits()) needed to find the optimum. The optimization should - * terminate after m_FitnessCalls. - */ - public void optimize() { - for (int i = 0; i < m_OptimizationSteps; i++) { - List population = new ArrayList(); - for (int j = 0; j < m_Mu; j++) { - population.add(new PBIndividualTwin(propVector)); - } - Collections.sort(population, Collections.reverseOrder()); // comparable - // implemente - // in - // PBilIndividual m_population = - // m_population.subList(0, m_Mu); - // for (int j = 0; j < population.size(); j++) { - // System.out.println(population.get(j).getStringRepresentation()); - // } - List m_Best = population.subList(0, m_Mu); - // System.out.println("Print best:"); - // System.out.println(m_Best.get(0).getStringRepresentation()); - for (PBIndividualTwin p : m_Best) { - for (int k = 0; k < m_GenotypeLength; k++) { - propVector[k] = (propVector[k] * (1 - learnrate)) - + ((p.getGenotype().get(k) ? 1 : 0) * learnrate); - } - } - // System.out.println(Arrays.toString(propVector)); - double fitnessPV = 0; - for (int j = 0; j < propVector.length; j++) { - double p = propVector[j]; - if (j < (propVector.length / 2)) { - fitnessPV += p; - } else { - fitnessPV -= p; - } - } - double oldFitness = meanFitness; - meanFitness = (m_GenotypeLength / 2) - Math.abs(fitnessPV); - if (oldFitness != meanFitness) { - m_OptimizationStepsNeeded++; - } - - } - } - - /** - * This main method will start a simple GeneticAlgorithm search. No - * arguments necessary. - * - * @param args - */ - public static void main(String[] args) { - // TODO: parameters for the GeneticAlgorithm, adjust these values as - // necessary - int genotypeLength = 50; - int mu = 15; - int lambda = 50; - int optimizationSteps = 1000; - // int optimizationSteps = 100; - int multiRuns = 100; - PBILTwin program = new PBILTwin(genotypeLength, mu, lambda, - optimizationSteps, multiRuns); - int TmpMeanCalls = 0, TmpMeanFitness = 0; - // perform repeated optimization - for (int i = 0; i < program.m_MultiRuns; i++) { - - program.initialize(); - program.optimize(); - TmpMeanCalls += program.m_OptimizationStepsNeeded; - TmpMeanFitness += program.meanFitness; - } - TmpMeanCalls = TmpMeanCalls / program.m_MultiRuns; - TmpMeanFitness = TmpMeanFitness / program.m_MultiRuns; - System.out.println("(" + program.m_MultiRuns + "/" - + program.m_OptimizationSteps + ") Mean Fitness : " - + TmpMeanFitness + " Mean Calls needed: " + TmpMeanCalls); - } -} diff --git a/ea/Ub7/PBIL/src/twin/PBIndividualTwin.java b/ea/Ub7/PBIL/src/twin/PBIndividualTwin.java deleted file mode 100644 index 7a1fa16..0000000 --- a/ea/Ub7/PBIL/src/twin/PBIndividualTwin.java +++ /dev/null @@ -1,165 +0,0 @@ -package twin; - -//import tools.RandomNumberGenerator; - -import java.util.BitSet; -import java.util.Random; - -/** - * @author Maximus - * - */ -public class PBIndividualTwin implements Comparable { - protected BitSet m_Genotype; - protected int m_GenotypeLength; - protected Random r = new Random(); - - /** Constructor **/ - public PBIndividualTwin(double[] propVector) { - // This method should call initGenotype() to initialize the genotype - this.m_GenotypeLength = propVector.length; - initGenotype(propVector); - - } - - /** - * cloning constructor - * - * @param toClone - */ - private PBIndividualTwin(PBIndividualTwin toClone) { - this.m_Genotype = (BitSet) toClone.m_Genotype.clone();// allowed, has - // only native - // typed - // fields - this.m_GenotypeLength = toClone.m_GenotypeLength; - } - - /** - * This method creates a deep copy of an individual. It should clone all - * objects contained by this object. - * - * @return An deep copy of this {@link PBIndividualTwin} - */ - @Override - public Object clone() { - - PBIndividualTwin c = new PBIndividualTwin(new double[m_GenotypeLength]); - c.setGenotype((BitSet) this.m_Genotype.clone()); - return c; - - // return new GAIndividual(this); - } - - /** - * This method evaluates the GAIndividual as a simple - * "maximize number of bits" problem. The fitness is the number of true bits - * in m_Genotype. Best fitness is reached if there are no false bits. - * - * @return The number of false bits (less is better!) - */ - public double evaluateAsMaxiBits() { - int zeros = 0; - for (int i = 0; i < m_GenotypeLength; i++) { - if (!m_Genotype.get(i)) { - zeros++; - } - } - return zeros; - } - - /** - * - * @return best fitness ==0 - */ - public double evaluateAsTwin() { - int f1 = 0; - int f2 = 0; - for (int i = 0; i < (m_GenotypeLength / 2); i++) { - if (m_Genotype.get(i)) { - f1++; - } - } - for (int i = (m_GenotypeLength / 2); i < m_GenotypeLength; i++) { - if (m_Genotype.get(i)) { - f2++; - } - } - return (m_GenotypeLength / 2) - Math.abs(f1 - f2); - } - - /** - * This method will return a string description of the GAIndividal notably - * the genotype: '0011000101' - * - * @return A descriptive string - */ - public String getStringRepresentation() { - // this should return exactly the representation shown in the comment - // above: - // only 0 (for false bits) and 1 (for true bits) with no extra white - // space! - String representation = ""; - for (int i = 0; i < m_GenotypeLength; i++) { - representation = m_Genotype.get(i) ? representation + "1" - : representation + "0"; - - } - return representation; - } - - /** - * This method will allow the user to read the GA genotype - * - * @return BitSet - */ - public BitSet getGenotype() { - return m_Genotype; - } - - /** - * This method will allow the user to set the current GA genotype. Should - * check if the length of the BitSet and the genotype length match. - * - * @param b - * The new genotype of the Individual - */ - public void setGenotype(BitSet b) { - - this.m_Genotype = b; - - } - - /** - * This method allows the user to read the length of the genotype. This may - * be necessary since BitSet.length only returns the index of the last - * significant bit. - * - * @return The length of the genotype. - */ - public int getGenotypeLength() { - return m_GenotypeLength; - } - - /** - * This method initializes the GA genotype randomly. Please use the - * tools.RandomNumberGenerator - * - * @param propVector - */ - public void initGenotype(double[] propVector) { - m_Genotype = new BitSet(m_GenotypeLength); - for (int i = 0; i < m_GenotypeLength; i++) { - if (r.nextDouble() < propVector[i]) { - m_Genotype.set(i); - } - } - } - - @Override - public int compareTo(PBIndividualTwin o) { - // return ((Double) this.evaluateAsMaxiBits()).compareTo(o - // .evaluateAsMaxiBits()); - return ((Double) this.evaluateAsTwin()).compareTo(o.evaluateAsTwin()); - } -} diff --git a/mr/ub7/mr7.pdf b/mr/ub7/mr7.pdf index eeb6759..8ee3d23 100644 --- a/mr/ub7/mr7.pdf +++ b/mr/ub7/mr7.pdf Binary files differ