diff --git a/ea/UB3/Blatt3/src/individuals/GAIndividual.java b/ea/UB3/Blatt3/src/individuals/GAIndividual.java index 2bcd4cf..02e2f11 100644 --- a/ea/UB3/Blatt3/src/individuals/GAIndividual.java +++ b/ea/UB3/Blatt3/src/individuals/GAIndividual.java @@ -12,15 +12,20 @@ /** Constructor **/ public GAIndividual(int genotypeLength) { - // TODO implement this // 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; } @@ -61,7 +66,6 @@ * @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 @@ -81,7 +85,6 @@ * @return BitSet */ public BitSet getGenotype() { - // TODO implement this return m_Genotype; } @@ -93,7 +96,7 @@ * The new genotype of the Individual */ public void setGenotype(BitSet b) { - assert b.length() == m_Genotype.length() : "Lengths intern =" + assert b.length() == m_Genotype.length() : "Length not euqual: intern:" + m_GenotypeLength + " input:" + b.length(); this.m_Genotype = b; @@ -107,7 +110,6 @@ * @return The length of the genotype. */ public int getGenotypeLength() { - // TODO implement this return m_GenotypeLength; } @@ -146,10 +148,8 @@ 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 diff --git a/ea/UB3/Blatt3/src/strategies/GeneticAlgorithm.java b/ea/UB3/Blatt3/src/strategies/GeneticAlgorithm.java index 0158b6d..dcd74de 100644 --- a/ea/UB3/Blatt3/src/strategies/GeneticAlgorithm.java +++ b/ea/UB3/Blatt3/src/strategies/GeneticAlgorithm.java @@ -28,7 +28,7 @@ /** Current best individual **/ private GAIndividual m_Best; /** Current list of parents **/ - private List parents = new ArrayList(); + private List m_parents = new ArrayList(); /** * This constructor sets up GeneticAlgorithm @@ -47,7 +47,7 @@ */ public GeneticAlgorithm(int genotypeLength, int mu, int lambda, int optimizationSteps, int multiRuns) { - assert multiRuns > 9; + assert multiRuns > 9; // use run configurations: vmargument: -ea assert (lambda % 2) == 0; this.m_GenotypeLength = genotypeLength; this.m_Mu = mu; @@ -60,14 +60,14 @@ * This method will initialize the GeneticAlgorithm */ public void initialize() { - parents.clear(); + m_parents.clear(); m_OptimizationStepsNeeded = 0; for (int i = 0; i < m_Mu; i++) { - parents.add(new GAIndividual(m_GenotypeLength)); + m_parents.add(new GAIndividual(m_GenotypeLength)); } - Collections.sort(parents, Collections.reverseOrder()); - m_Best = parents.get(0); + Collections.sort(m_parents, Collections.reverseOrder()); + m_Best = m_parents.get(0); } /** @@ -77,7 +77,6 @@ * 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 @@ -94,10 +93,14 @@ 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)); + GAIndividual parent1; + GAIndividual parent2; + do { + parent1 = m_parents.get(RandomNumberGenerator.randomInt(0, + m_Mu - 1)); + parent2 = m_parents.get(RandomNumberGenerator.randomInt(0, + m_Mu - 1)); + } while (parent1 == parent2);// distinct parents children.addAll(Arrays.asList(GAIndividual.crossover(parent1, parent2))); } @@ -106,19 +109,18 @@ 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_parents.addAll(children); + Collections.sort(m_parents, Collections.reverseOrder()); // comparable + // implemented + // in + // GAIndividual + m_parents = m_parents.subList(0, m_Mu); + m_Best = m_parents.get(0); m_OptimizationStepsNeeded++; if (m_Best.evaluateAsMaxiBits() == m_GenotypeLength) { break; } - // System.out.println(m_Best.getStringRepresentation() + " " - // + m_OptimizationStepsNeeded); + } } @@ -131,7 +133,7 @@ public static void main(String[] args) { // TODO: parameters for the GeneticAlgorithm, adjust these values as // necessary - int genotypeLength = 10; + int genotypeLength = 50; int mu = 10; int lambda = 50; int optimizationSteps = 100000; diff --git a/ea/UB3/Blatt3/src/strategies/HillClimbing.java b/ea/UB3/Blatt3/src/strategies/HillClimbing.java index 66b69d7..a239c27 100644 --- a/ea/UB3/Blatt3/src/strategies/HillClimbing.java +++ b/ea/UB3/Blatt3/src/strategies/HillClimbing.java @@ -73,7 +73,7 @@ public static void main(String[] args) { // TODO: parameters for the HillClimber, adjust these values as // necessary - int genotypeLength = 10; + int genotypeLength = 50; int optimizationSteps = 100000; int multiRuns = 100; HillClimbing program = new HillClimbing(genotypeLength, diff --git a/ea/UB3/ea2.pdf b/ea/UB3/ea2.pdf new file mode 100644 index 0000000..cbee4be --- /dev/null +++ b/ea/UB3/ea2.pdf Binary files differ diff --git a/ea/UB3/ea2.tex b/ea/UB3/ea2.tex new file mode 100644 index 0000000..8bec441 --- /dev/null +++ b/ea/UB3/ea2.tex @@ -0,0 +1,107 @@ +\documentclass[a4paper,12pt]{scrartcl} +\usepackage[ngerman]{babel} +\usepackage{graphicx} %BIlder einbinden +\usepackage{amsmath} %erweiterte Mathe-Zeichen +\usepackage{amsfonts} %weitere fonts +\usepackage[utf8]{inputenc} %Umlaute & Co +\usepackage{hyperref} %Links +\usepackage{ifthen} %ifthenelse +\usepackage{enumerate} + +\usepackage{algpseudocode} %Pseudocode +\usepackage{dsfont} % schöne Zahlenräumezeichen +\usepackage{amssymb, amsthm} %noch stärker erweiterte Mathe-Zeichen +\usepackage{tikz} %TikZ ist kein Zeichenprogramm +\usetikzlibrary{trees,automata,arrows,shapes} + +\pagestyle{empty} + + +\topmargin-50pt + +\newcounter{aufgabe} +\def\tand{&} + +\newcommand{\makeTableLine}[2][0]{% + \setcounter{aufgabe}{1}% + \whiledo{\value{aufgabe} < #1}% + {% + #2\tand\stepcounter{aufgabe}% + } +} + +\newcommand{\aufgTable}[1]{ + \def\spalten{\numexpr #1 + 1 \relax} + \begin{tabular}{|*{\spalten}{p{1cm}|}} + \makeTableLine[\spalten]{A\theaufgabe}$\Sigma$~~\\ \hline + \rule{0pt}{15pt}\makeTableLine[\spalten]{}\\ + \end{tabular} +} + +\def\header#1#2#3#4#5#6#7{\pagestyle{empty} +\begin{minipage}[t]{0.47\textwidth} +\begin{flushleft} +{\bf #4}\\ +#5 +\end{flushleft} +\end{minipage} +\begin{minipage}[t]{0.5\textwidth} +\begin{flushright} +#6 \vspace{0.5cm}\\ +% Number of Columns Definition of Columns second empty line +% \begin{tabular}{|*{5}{C{1cm}|}}\hline A1&A2&A3&A4&$\Sigma$\\\hline&&&&\\\hline\end{tabular}\\\vspace*{0.1cm} +\aufgTable{#7} +\end{flushright} +\end{minipage} +\vspace{1cm} +\begin{center} +{\Large\bf Übungsblatt #1} + +{(Abgabe #3)} +\end{center} +} + + + +%counts the exercisenumber +\newcounter{n} + +%Kommando für Aufgaben +%\Aufgabe{AufgTitel}{Punktezahl} +\newcommand{\Aufgabe}[2]{\stepcounter{n} +\textbf{Aufgabe \arabic{n}: #1} (#2 Punkte)} + + +\begin{document} + %\header{BlattNr}{Tutor}{Abgabedatum}{Vorlesungsname}{Namen}{Semester}{Anzahl Aufgaben} + \header{3}{}{2015-12-05}{Evolutionäre Algorithmen}{ + \textit{Jan-Peter Hohloch}\\ \textit{Maximus Mutschler} + }{SS 15}{3} + \vspace{0.5cm} \Aufgabe{Bit String Individuum}{6}\\ + Siehe Quellcode\\ + \Aufgabe{Hill-Climber und Genetischer Algorithmus}{10}\\ + Siehe Quellcode\\ + \Aufgabe{Vergleich Hill-Climber und Genetischer Algorithmus}{4}\\ + $\mu=10$ \\$\lambda =50$\\ + Durchschnittliche Optimierungsschritte bei 100 Optimierungsläufen:\\\\ + \begin{tabular}{c|c|c} + n & Hill-Climber & Genetischer Algorithmus \\ \hline + 10 & 24 & 3 \\ + 25 & 80 & 8 \\ + 50 & 202 & 18 + \end{tabular}\\\\ + Warum ist es nötig die Ergebnisse zu mitteln?\\ + Es handelt sich um stochastische Optimierungsverfahren. Demnach gibt es kein deterministisches Ergebnis. Folglich muss der Mittelwert aus den Zufalls belasteten Ergebnissen als Ergebnismaß verwendet werden.\\\\ + + Sind die Ergebnisse von Hill-Climber und Genetischen Algorithmus direkt vergleichbar?\\ + warum nicht ?? TODO\\ + Beim Hill-Climber Algorithmus kommt es nur zu 1 Bit Mutationen beim Genetischen Algorithmus werden Crossover angewandt. Wehrendessen es beim Hill-Climber Algorithmus maßgeblich vom initialen Individuum abhängt, wie viele Schritte benötigt werden um das Maximum zu erreichen, ist beim Genetischen Algorithmus der Crossover ausschlaggebend. + Beim Hill Climber wird nur eine "Population" von einem Individuum angenommen, um ihn mit dem Genetischen Algorithmus vergleichbar zu machen, müsste man $\mu$ Individuuen und deren Mutationen und die daraus folgende Fitness je Optimierungsschritt untersuchen. + \\ + Gibt das Sinn? + + + + +\end{document} +