diff --git a/ea/UB3/Blatt3.zip b/ea/UB3/Blatt3.zip
new file mode 100644
index 0000000..9bfe146
--- /dev/null
+++ b/ea/UB3/Blatt3.zip
Binary files differ
diff --git a/ea/UB3/Blatt3/.classpath b/ea/UB3/Blatt3/.classpath
new file mode 100644
index 0000000..fb50116
--- /dev/null
+++ b/ea/UB3/Blatt3/.classpath
@@ -0,0 +1,6 @@
+
+
+
+
+
+
diff --git a/ea/UB3/Blatt3/.gitignore b/ea/UB3/Blatt3/.gitignore
new file mode 100644
index 0000000..ae3c172
--- /dev/null
+++ b/ea/UB3/Blatt3/.gitignore
@@ -0,0 +1 @@
+/bin/
diff --git a/ea/UB3/Blatt3/.project b/ea/UB3/Blatt3/.project
new file mode 100644
index 0000000..4f2cab2
--- /dev/null
+++ b/ea/UB3/Blatt3/.project
@@ -0,0 +1,17 @@
+
+
+ EvolutionäreAlgorithmenUe3
+
+
+
+
+
+ org.eclipse.jdt.core.javabuilder
+
+
+
+
+
+ org.eclipse.jdt.core.javanature
+
+
diff --git a/ea/UB3/Blatt3/src/individuals/GAIndividual.java b/ea/UB3/Blatt3/src/individuals/GAIndividual.java
new file mode 100644
index 0000000..2bcd4cf
--- /dev/null
+++ b/ea/UB3/Blatt3/src/individuals/GAIndividual.java
@@ -0,0 +1,164 @@
+package individuals;
+
+//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) {
+ // TODO implement this
+ // This method should call initGenotype() to initialize the genotype
+ this.m_GenotypeLength = genotypeLength;
+ initGenotype();
+ }
+
+ private GAIndividual(GAIndividual toClone) {
+ this.m_Genotype = (BitSet) toClone.m_Genotype.clone();// allowed, has
+ // only native
+ // 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() {
+ // Clone methoden... nein!
+ 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 sum = 0;
+ for (int i = 0; i < m_GenotypeLength; i++) {
+ if (m_Genotype.get(i)) {
+ sum++;
+ }
+ }
+ return sum;
+ }
+
+ /**
+ * This method will return a string description of the GAIndividal notably
+ * the genotype: '0011000101'
+ *
+ * @return A descriptive string
+ */
+ public String getStringRepresentation() {
+ // TODO implement this
+ // 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() {
+ // TODO implement this
+ 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) {
+ assert b.length() == m_Genotype.length() : "Lengths intern ="
+ + m_GenotypeLength + " input:" + b.length();
+ 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() {
+ // TODO implement this
+ 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));
+ }
+
+ /**
+ * 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);
+ GAIndividual ind1Clone = (GAIndividual) ind1.clone();
+ GAIndividual ind2Clone = (GAIndividual) ind2.clone();
+ for (int i = splitPoint; i < ind1Clone.m_GenotypeLength; i++) {
+ boolean saveBit = ind1Clone.m_Genotype.get(i);
+ ind1Clone.m_Genotype.set(i, ind2Clone.m_Genotype.get(i));
+ ind2Clone.m_Genotype.set(i, saveBit);
+ }
+ 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());
+ }
+ // TODO implement this
+ }
+
+ @Override
+ public int compareTo(GAIndividual o) {
+ if (this.evaluateAsMaxiBits() > o.evaluateAsMaxiBits()) {
+ return 1;
+ } else if (this.evaluateAsMaxiBits() < o.evaluateAsMaxiBits()) {
+ return -1;
+ }
+ return 0;
+ }
+}
diff --git a/ea/UB3/Blatt3/src/strategies/GeneticAlgorithm.java b/ea/UB3/Blatt3/src/strategies/GeneticAlgorithm.java
new file mode 100644
index 0000000..0158b6d
--- /dev/null
+++ b/ea/UB3/Blatt3/src/strategies/GeneticAlgorithm.java
@@ -0,0 +1,155 @@
+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 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;
+ /** Current list of parents **/
+ private List parents = new ArrayList();
+
+ /**
+ * 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;
+ assert (lambda % 2) == 0;
+ this.m_GenotypeLength = genotypeLength;
+ this.m_Mu = mu;
+ this.m_Lambda = lambda;
+ this.m_OptimizationSteps = optimizationSteps;
+ this.m_MultiRuns = multiRuns;
+ }
+
+ /**
+ * This method will initialize the GeneticAlgorithm
+ */
+ public void initialize() {
+ parents.clear();
+ m_OptimizationStepsNeeded = 0;
+ for (int i = 0; i < m_Mu; i++) {
+ parents.add(new GAIndividual(m_GenotypeLength));
+
+ }
+ Collections.sort(parents, Collections.reverseOrder());
+ m_Best = parents.get(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() {
+ // TODO implement this
+ // 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
+
+ for (int i = 0; i < m_OptimizationSteps; i++) {
+ ArrayList children = new ArrayList();
+ for (int a = 0; a < (m_Lambda / 2); a++) {
+ GAIndividual parent1 = parents.get(RandomNumberGenerator
+ .randomInt(0, m_Mu - 1));
+ GAIndividual parent2 = parents.get(RandomNumberGenerator
+ .randomInt(0, m_Mu - 1));
+ children.addAll(Arrays.asList(GAIndividual.crossover(parent1,
+ parent2)));
+ }
+ for (GAIndividual child : children) {
+ if (RandomNumberGenerator.randomBoolean()) {
+ child.mutate();
+ }
+ }
+ parents.addAll(children);
+ Collections.sort(parents, Collections.reverseOrder()); // comparable
+ // implemented
+ // in //
+ // GAIndividual
+ parents = parents.subList(0, m_Mu);
+ m_Best = parents.get(0);
+ m_OptimizationStepsNeeded++;
+ if (m_Best.evaluateAsMaxiBits() == m_GenotypeLength) {
+ break;
+ }
+ // System.out.println(m_Best.getStringRepresentation() + " "
+ // + 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 = 10;
+ int mu = 10;
+ int lambda = 50;
+ int optimizationSteps = 100000;
+ 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/UB3/Blatt3/src/strategies/HillClimbing.java b/ea/UB3/Blatt3/src/strategies/HillClimbing.java
new file mode 100644
index 0000000..66b69d7
--- /dev/null
+++ b/ea/UB3/Blatt3/src/strategies/HillClimbing.java
@@ -0,0 +1,96 @@
+package strategies;
+
+import individuals.GAIndividual;
+
+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;
+ m_OptimizationStepsNeeded++;
+ if (m_Best.evaluateAsMaxiBits() == m_GenotypeLength) {
+ break;
+ }
+ }
+ }
+
+ /**
+ * 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 = 10;
+ int optimizationSteps = 100000;
+ 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/UB3/Blatt3/src/tools/RandomNumberGenerator.java b/ea/UB3/Blatt3/src/tools/RandomNumberGenerator.java
new file mode 100644
index 0000000..facdcca
--- /dev/null
+++ b/ea/UB3/Blatt3/src/tools/RandomNumberGenerator.java
@@ -0,0 +1,47 @@
+package tools;
+
+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/UB3/blatt3.pdf b/ea/UB3/blatt3.pdf
new file mode 100644
index 0000000..1ced0c2
--- /dev/null
+++ b/ea/UB3/blatt3.pdf
Binary files differ