diff --git a/ea/Ub7/PBIL/src/PBIL.java b/ea/Ub7/PBIL/src/PBIL.java index 36c78b9..6a4816b 100644 --- a/ea/Ub7/PBIL/src/PBIL.java +++ b/ea/Ub7/PBIL/src/PBIL.java @@ -80,11 +80,14 @@ for (int j = 0; j < m_Mu; j++) { population.add(new PBilIndividual(propVector)); } - Collections.sort(population); // comparable implemente in + 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(m_Best.get(0).getStringRepresentation()); + 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)) @@ -116,8 +119,8 @@ int genotypeLength = 50; int mu = 15; int lambda = 50; - // int optimizationSteps = 100000; - int optimizationSteps = 100; + int optimizationSteps = 1000; + // int optimizationSteps = 100; int multiRuns = 1; PBIL program = new PBIL(genotypeLength, mu, lambda, optimizationSteps, multiRuns); diff --git a/ea/Ub7/PBIL/src/twin/PBIL.java b/ea/Ub7/PBIL/src/twin/PBIL.java new file mode 100644 index 0000000..8de7cde --- /dev/null +++ b/ea/Ub7/PBIL/src/twin/PBIL.java @@ -0,0 +1,153 @@ +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.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, 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 (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 (int j = 0; j < propVector.length; j++) { + double p=propVector[j]; + if (j < propVector.length / 2) { + fitnessPV += p; + } + else{ + fitnessPV-=p; + } + } + meanFitness = Math.abs(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 = 1000; + // 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/twin/PBilIndividual.java b/ea/Ub7/PBIL/src/twin/PBilIndividual.java new file mode 100644 index 0000000..bac70b4 --- /dev/null +++ b/ea/Ub7/PBIL/src/twin/PBilIndividual.java @@ -0,0 +1,203 @@ +package twin; +//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()); + return ((Double) this.evaluateAsTwin()).compareTo(o.evaluateAsTwin()); + } +} diff --git a/ea/Ub7/PBIL/src/twin/RandomNumberGenerator.java b/ea/Ub7/PBIL/src/twin/RandomNumberGenerator.java new file mode 100644 index 0000000..69177d0 --- /dev/null +++ b/ea/Ub7/PBIL/src/twin/RandomNumberGenerator.java @@ -0,0 +1,48 @@ +package twin; + + +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); + } +}