diff --git a/ea/UB3/Blatt3/EA3/src/strategies/HillClimbing.java b/ea/UB3/Blatt3/EA3/src/strategies/HillClimbing.java index a47e192..9d0505c 100644 --- a/ea/UB3/Blatt3/EA3/src/strategies/HillClimbing.java +++ b/ea/UB3/Blatt3/EA3/src/strategies/HillClimbing.java @@ -1,4 +1,4 @@ -package src.strategies; +dpackage src.strategies; import src.individuals.GAIndividual; diff --git a/ea/UB3/Blatt3/src/strategies/PBIL.java b/ea/UB3/Blatt3/src/strategies/PBIL.java new file mode 100644 index 0000000..19b3a3f --- /dev/null +++ b/ea/UB3/Blatt3/src/strategies/PBIL.java @@ -0,0 +1,166 @@ +package strategies; + +/** + * This class implements a deterministic variant of the Genetic Algorithm described in the script, section 5.1.1. + */ +import individuals.GAIndividual; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.List; + +import tools.RandomNumberGenerator; + +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 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; + + 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 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++; + } + + } + } + + /** + * 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 = 25; + int mu = 10; + int lambda = 50; + // int optimizationSteps = 100000; + int optimizationSteps = 100; + int multiRuns = 100; + 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/.classpath b/ea/Ub7/PBIL/.classpath new file mode 100644 index 0000000..fb50116 --- /dev/null +++ b/ea/Ub7/PBIL/.classpath @@ -0,0 +1,6 @@ + + + + + + diff --git a/ea/Ub7/PBIL/.gitignore b/ea/Ub7/PBIL/.gitignore new file mode 100644 index 0000000..ae3c172 --- /dev/null +++ b/ea/Ub7/PBIL/.gitignore @@ -0,0 +1 @@ +/bin/ diff --git a/ea/Ub7/PBIL/.project b/ea/Ub7/PBIL/.project new file mode 100644 index 0000000..a5437ca --- /dev/null +++ b/ea/Ub7/PBIL/.project @@ -0,0 +1,17 @@ + + + PBIL + + + + + + org.eclipse.jdt.core.javabuilder + + + + + + org.eclipse.jdt.core.javanature + + diff --git a/ea/Ub7/PBIL/src/PBIL.java b/ea/Ub7/PBIL/src/PBIL.java new file mode 100644 index 0000000..36c78b9 --- /dev/null +++ b/ea/Ub7/PBIL/src/PBIL.java @@ -0,0 +1,139 @@ +/** + * 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; + +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.propVector = new double[m_GenotypeLength]; + for (int i = 0; i < propVector.length; i++) { + propVector[i] = 0.5; + } + + // this.learnrate = 1 / lambda; + this.learnrate = 0.05; + + } + + /** + * 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() { + 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); // comparable implemente in + // PBilIndividual m_population = + // m_population.subList(0, m_Mu); + List m_Best = population.subList(0, m_Mu); + 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; + } + meanFitness = fitnessPV; + if (fitnessPV != propVector.length) { + 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 = 100; + int multiRuns = 1; + 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); + } +} diff --git a/ea/Ub7/PBIL/src/PBilIndividual.java b/ea/Ub7/PBIL/src/PBilIndividual.java new file mode 100644 index 0000000..6361654 --- /dev/null +++ b/ea/Ub7/PBIL/src/PBilIndividual.java @@ -0,0 +1,201 @@ +//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 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 PBilIndividual[] crossover(PBilIndividual ind1, + // PBilIndividual ind2) { + // assert ind1.m_GenotypeLength == ind2.m_GenotypeLength; + // + // int splitPoint = RandomNumberGenerator.randomInt(0, + // ind1.m_GenotypeLength - 1); + // PBilIndividual ind1Clone = (PBilIndividual) ind1.clone(); + // PBilIndividual ind2Clone = (PBilIndividual) 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 PBilIndividual[] { ind2Clone, ind1Clone }; + // } + + /** + * 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 new file mode 100644 index 0000000..48816ea --- /dev/null +++ b/ea/Ub7/PBIL/src/RandomNumberGenerator.java @@ -0,0 +1,47 @@ + + +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); + } +}