####Genetic Algorithms in Plain English //evtl eine andere Überschrift Genetische Algorhytmen in verständlichem Deutsch ####Introduction Einführung ####The aim of this tutorial is to explain genetic algorithms sufficiently for you to be able to use them in your own projects. This is a stripped-down to-the-bare-essentials type of tutorial. I'm not going to go into a great deal of depth and I'm not going to scare those of you with math anxiety by throwing evil equations at you every few sentences. In fact, I'm not going to throw any nasty equations at you at all! Not in this particular tutorial anyway... //equations nachschlagen Das Ziel dieses Tutorials ist es, euch die Funktionsweise von Genetische Algorytmen verständlich zu machen, dass ihr sie in euren eigenen Projekten ensetzen könnt. Dies ist eine auf das Minimum reduzierte Version des Tutorials. Ich werde nicht besonders auf Details eingehen und werde euch nicht alle paar Sätze mit schrecklichen mathematischen Axiomen vertreiben. Um genau zu sein, werde ich euch beinahe garnicht mit Mathematik quälen... zumindest nicht in diesem Tutorial ####This tutorial is designed to be read through twice... so don't worry if little of it makes sense the first time you study it. Dieses Tutorial wurde so entworfen, dass es zweimal gelesen werden sollte... also mach dir keine sorgen, wenn du beim ersten Durchgang nur die Hälfte verstehst. ####First, a Biology Lesson Zunächst, ein wenig Nachhilfe in Biologie ####Every organism has a set of rules, a blueprint so to speak, describing how that organism is built up from the tiny building blocks of life. These rules are encoded in the genes of an organism, which in turn are connected together into long strings called chromosomes. Each gene represents a specific trait of the organism, like eye colour or hair colour, and has several different settings. For example, the settings for a hair colour gene may be blonde, black or auburn. These genes and their settings are usually referred to as an organism's genotype. The physical expression of the genotype - the organism itself - is called the phenotype. Jeder Organismus hat einen Satz Regeln, einen Bauplan so zu sagen, welche beschreiben, wie und aus welchen Bausteinen des Lebens, der Organismus aufgebaut ist. Diese Regeln sind in den Genen des Organismus eingebettet, welche wiederum in langen Strängen, den sogenannten Chromosomen, organisiert sind. Jedes Gen beschreibt eine spezielle Eigenschaft des Organismus, zB die Augen- oder Haarfarbe und kann verschiedene Werte annehmen. Zum Beispiel, könnte der Wert für das Harrfarben Gen Blond, Schwarz oder Braun sein. Diese Gene und ihre Werte werden in der Regel als die sog. Genotypen des Organismus bezeichnet. Das Physikalische Ergebniss dieser Genotypen, der Organismus selbst, wird als Phenotyp bezeichnet. ####When two organisms mate they share their genes. The resultant offspring may end up having half the genes from one parent and half from the other. This process is called recombination. Very occasionally a gene may be mutated. Normally this mutated gene will not affect the development of the phenotype but very occasionally it will be expressed in the organism as a completely new trait. Wenn zwei Organismen sich vermehren, dann teilen sie ihre Gene. Der Abkömmling wird seine Gene zur Hälfte vom einen Partner und zur anderen vom anderen Partner erhalten. Dies wird auch als Rekombination bezeichnet. Mit einer geringen Warscheinlichkeit kann es bei diesem Prozess zu einer Mutation von Genen kommen. Normalerweise beeinflusst eine solche Mutation den Phenotypen des Organismus nicht, doch eine geringe Warscheinlichkeit besteht, dass eine solche Mutation auch komplett neue Eigenschaften des Phenotypen hervorbringt [A.d.Ü.: zB neue Haarfarben, komplette Gliedmaßen etc] ####Life on earth has evolved to be as it is through the processes of natural selection, recombination and mutation. To illustrate how these processes work together to produce the diverse range of flora and fauna we share our planet with let me tell you a little story.... Das Leben auf der Erde entwickelte sich durch den Prozess der natürlichen Auslese, Rekombination und Mutation. Um euch besser zeigen zu können, wie diese Prozesse beim entwickeln verschiedenster Flora und Fauna, mit der wir unseren Planeten teilen, zusammenarbeiten, werde ich euch eine kleine Geschichte erzählen.... ####Once upon a time there lived a species of creatures called Hooters. Hooters had evolved entirely within the darkened confines of a vast cave system hidden deep in the bowels of a mountain range. They'd had an easy life, feeling and smelling around the damp cave walls for the algae they so loved to eat, oozing between rocks and, at mating time, listening intently for the hoots of other Hooters. There were no predators in the caves, it was just the Hooters, the algae and the occasional friendly slug, so the Hooters never had anything to fear (except for maybe the occasional bad tempered Hooter). An underground river flowed through the cave system and water continuously dripped down through the water table bringing with it the fresh nutrients the algae thrived on so there was always plenty to eat and drink. However, although Hooters could feel and hear well they never had any need for eyes in the pitch blackness of the caves and as a result were totally blind. This never seemed to concern any of the Hooters Vor langer Zeit lebte eine Spezies mit dem Namen Quieker. Quieker entwickelten sich in einem verzweigten Höhlensystem, tief in dem Herzen einer Gebirgskette. Sie führten ein schönes Leben, die feuchten Höhlenwände nach ihren Algen, die sie so liebten, abtastend und abriechend, zwischen Steinen rumschlendern und, zur Paarungszeit, nach den quieken anderer Quieker horschen. In den Höhlen gab es keine Eindringlinge, nur die Quieker, die Algen und gelegentlich die nette Schnecke. Die Quieker mussten also vor nichts Angst haben (abgesehen vielleicht von den gelegentlich schlecht gelaunten Quiekern). Ein unterirdischer Fluss floss durch das Höhlensystem und Wasser tropfte kontinuirlich von der Decke, ständig Nährstoffe für die Algen mitbringend. Es gab also immer genug zu essen und zu trinken, für die Quieker. Die Quieker konnten zwar gut höhren und fühlen, aber in der Dunkelheit der Höhlen brauchten sie keine Augen und deshalb waren sie absolut blind. Dies schien die Quieker jedoch nicht besonders zu stören und so hatten sie eine ####though and they all had a whale of a time munching away and hooting in the darkness. tolle Zeit beim Fressen und quieken in der Dunkelheit. ####Then one day an earthquake caused part of the cave system to collapse and for the first time in many millennia the Hooters felt the warmth of sunlight upon their skin and the soft springiness of moss beneath their feet. A few daring Hooters tasted the moss and found that it was even better eating than the cave algae. "Ooooooooooh!" they hooted between mouthfuls of moss and promptly got gobbled up by the marauding eagles who had flown in to see what all the commotion was about. Eines Tages brachte ein Erdbeben einen Teil des Höhlensystems zum Einsturz und zum ersten mal seit Jahrtausenden fühlten die Quieker die wärme des Sonnlicht auf ihrer Haut und die weiche geschmeidigkeit von Moss unter ihren Füßen. Ein paar verwegene Quieker probierten von dem Moss und mussten feststellen, dass es sogar noch besser schmeckt als die Algen in der Höhle. "Oooooooooooooh!", riefen sie, wärend sie das Moss in sich schaufelten und wurden dadurch auch sofort von ein paar plündernden Adlern entdeckt, die hergeflogen kamen um zu schaun, was das alles für ein Terz gewesen ist. ####For a while it looked as though the Hooters may be hunted to extinction, for although they liked to eat the moss they could never tell if an eagle was flying above. Not only that, they couldn't even tell if they were concealed beneath a rock or not unless it was low enough to reach for with their feelers. Every day many Hooters would stumble out from the caves with the sweet smell of moss in their nostrils only to be swiftly carried away and eaten by an eagle. Their situation seemed grim indeed. Eine ganze Zeit lang schien es, als ob die Quieker bis zu ihrer absoluten Ausrottung gejagt werden würden. Zwar mochten sie das Moß sehr, doch konnten sie ja nicht erkennen, dass Adler über ihnen flogen. Und nichtnur das: Sie wußten ja nichteinmal, ob sie unter einem schützenden Stein saßen, wenn sie ihn nicht mit ihren Fühlern erreichen konnten. Jeden Tag, stolperten viele Quieker, den süßen Geruch des Moßes in ihren Nasen, aus den Höhlen um prompt von einem Adler verschleppt und aufgefressen zu werden. Ihre Lage war durchaus schlecht. ####Fortunately, over the years, the population of Hooters had grown to be enormous in the safety of the caves and enough of them were surviving to mate - after all, an eagle can only eat so much. One day, a brood of Hooters was born that shared a mutated skin cell gene. This particular gene was responsible for the development of the skin cells on their foreheads. During the development of the baby Hooters, when their skin cells grew from the mutated gene instructions they were slightly light sensitive. Each new baby Hooter could sense if something was blocking the light to its forehead or not. When these little baby Hooters grew up into bigger Hooters and ventured into the light to eat the moss they could tell if something was swooping overhead or not. So these Hooters grew up to have a slightly better chance of survival than their totally blind cousins. And because they had a better chance of survival, they reproduced much more, therefore passing the new light sensitive skin cell gene to their offspring. Glücklicherweise wuchs die Population der Quieker über die Jahre in den sicheren Höhlen und genug von ihnen überlebten um sich zu paaren - immerhin hat auch ein Adler einen begrenzten Appetit. Eines Tages wurde ein Wurf von Quiekern geboren, die alle eine mutiertes Haut-Zellen-Gen besaßen. Dieses Gen war für die Entwicklung der Hautzellen auf ihrem Vorderkopf verantwortlich. Eben diese Hautzellen der Baby-Quieker, welche langsam heranwuchsen, entwickelten eine, durch die Mutation bedingte, leichte Lichtempfindlichkeit. Jedes dieser Baby-Quieker konnte nun erkennen, ob etwas vor ihnen das Licht blockiert oder nicht. Als die Quieker aufwuchsen und sich hinaus ins Licht begaben um vom Moß zu essen konnten sie erkennen, ob sich etwas über ihren Köpfen bewegte. Diese Quieker wuchsen mit einer leicht höheren Chance zum Überleben auf, als ihre absolut blinden Cousins. Da sie eine höhere Lebenserwartung hatten, konnten sie sich auch viel mehr repoduzieren und das neue Lichtempfindliche Hautzellen Gen an ihre nachkommen weiterreichen. ####After a very short while the population became dominated by the Hooters with this slight advantage. Nach nur kurzer Zeit dominierten Quieker mit diesem kleinen Vorteil die Population. #####Now let's zip a few thousand generations into the future. If you extrapolate this process over very many years and involving lots of tiny mutations occurring in the skin cell genes it's easy to imagine a process where one light sensitive cell may become a clump of light sensitive cells, and then how the interior cells of the clump may mutate to harden into a tiny lens shaped area, which would help to gather the light and focus it into one place. It's not too difficult to envision a mutation that gives rise to two of these light gathering areas thereby bestowing binocular vision upon the Hooters. This would be a huge advantage over their Cyclopsian cousins as the Hooters would now be able to judge distances accurately and have a greater field of view. Wollen wir mal ein paar tausend Generationen überspringen. Wenn man diesen Prozess über viele Jahre hinweg weiterführt und viele weitere kleine Mutation in den Hautzellen-Genen auftreten, kann man sich leicht vorstellen, dass aus einer einzelnen lichtempfindliche Zelle ein ganzer Klumpen dieser Zellen wird und dann wie sich das innere dieses Klumpens zu einer art Linse formt, welche dabei behilflich sein kann Licht zu sammeln und den Fokus auf bestimmte Orte zu setzen. Auch ist es nicht besonders schwer vorstellbar, dass eine Mutation zwei dieser Licht sammelnden Gebiete hervorbringen könnte. womit die Quieker über räumliches sehen verfügen würden. Dies wäre ein dramatischer Vorteil ihren zyklopischen Cousins gegenüber, da sie nun in der Lage wären entfernungen einzuschätzen und einen größeren Sichtradius hätten. #####As you can see the processes of natural selection - survival of the fittest - and gene mutation have very powerful roles to play in the evolution of an organism. But how does recombination fit into the scheme of things? Well to show you that I need to tell about some other Hooters... Wie du unschwer erkennen kannst spielen die Prozesse der natürlichen Auslese, nämlich Mutation und überleben des Stärkeren, eine gravierende Rolle in der Evolution eines Organismus. Aber wo kommt da jetzt die Rekombination is Spiel? Tja, dazu muss ich euch wohl von ein paar anderen Quiekern erzählen... #####At around the same time the Hooters with the light sensitive cells were frolicking around in the moss and teasing the eagles, another brood of Hooters had been born who shared a mutated gene that affected their hooter. This mutation gave rise to a slightly bigger hooter than their cousins, and because it was bigger they could now hoot over longer distances. This turned out to be useful in the rapidly diminishing population because the Hooters with the bigger hooters could call out to potential mates situated far away. Not only that but the female Hooters began to show a slight preference to males with larger hooters . The upshot of this of course was that the better endowed Hooters stood a much better chance of mating than any not so well off Hooters. Over a period of time, large hooters became prevalent in the population. Etwa zur selben Zeit, als die Quieker mit den Lichtempfindlichen Zellen im Moß rumtollten und die Adler veräppelten, wurde ein weiterer Wurf Quieker geboren, die alle über ein mutierstes Gen verfügten, dass ihr quieken beeinfluste. Diese Mutation verlieh ihnen ein etwas lauteres Quieken als das ihrer Cousins und konnten dadurch auch über größere Distanzen hinweg quieken. Das war sehr vorteilhaft in der stark dezimierten Population, weil die Quieker mit dem lauteren quieken, konnten auch von Geschlechtspartnern in großer Entfernung noch gehört werden. Dazu kam noch, dass die weiblichen Quieker anscheinend gefallen an dem lauteren Quieken gefunden hatten und Quieker mit lauterem Quieken bevorzugten. Das hatte natürlich zur Folge, dass die besser ausgestatteten Quieker eine höhere Chance hatten sich zu paaren. Über die Zeit wurden laute Quieker vorherrschend in der Population. #####Then one fine day a female Hooter with the gene for light sensitive skin cells met a male Hooter with the gene for producing huge hooters. They fell in love, and shortly afterwards produced a brood of lovely baby Hooters. Now, because the babies chromosomes were a recombination of both parents chromosomes, some of the babies shared both the special genes and grew up not only to have light sensitive skin cells, but huge hooters too! These new offspring were extremely good at avoiding the eagles and reproducing so the process of evolution began to favour them and once again this new improved type of Hooter became dominant in the population. Dann, eines schönen Tages, traf ein mit dem Gen für die Lichtempfindlichen Hautzellen ausgestattetes Weibchen auf ein Männchen, dass über das laute Quieken verfügte. Sie verliebten sich und kurze Zeit später bekamen sie einen ganzen Wurf niedlicher Baby-Quieker. Durch die Rekombination der Chromosome von beiden Elternteilen, verfügten manche der Quieker-Babies nun über beide speziellen Gene und besaßen nichtnur lichtempfindlichen Zellen, sondern auch ein lautes Quieken! Die neue Generation war extrem gut darin, den Adlern aus dem Weg zu gehen und im sich reproduzieren, was sie erfolgreicher im evolutionären Prozess als die anderen Quieker machte. Wieder wurde die besseren Quieker in der Population dominierend. #####And so on. And so on... Und so weiter. Und so weiter... #####Genetic Algorithms are a way of solving problems by mimicking the same processes mother nature uses. They use the same combination of selection, recombination and mutation to evolve a solution to a problem. Neat huh? Turn the page to find out exactly how it's done. Genetische Agorythmen sind ein Weg Probleme zu lösen indem man die Prozesse, die auch Mutter Natur einsetzt. Sie bauen auf der selben Kombination von Selektion und Mutation auf um eine Lösung zu einem Problem zu entwickeln. Ganz schön Ordentlich, hä? Blätter weiter um zu erfahren wies funktioniert. #####The Genetic Algorithm - a brief overview Der genetische Agorythmus - ein kurzer Überblick #####Before you can use a genetic algorithm to solve a problem, a way must be found of encoding any potential solution to the problem. This could be as a string of real numbers or, as is more typically the case, a binary bit string. I will refer to this bit string from now on as the chromosome. A typical chromosome may look like this: Befor du genetische Algorytmen einsetzen kannst um mit ihnen Probleme zu lösen, muss ein Weg gefunden werden alle potentiell möglichen Lösungen zu codieren. Dies könnte in Form eines aus Gleitzahlwerten bestehender String sein, aber auch, der üblichere Weg, ein aus Binären Zahlen bestehender String. Ich werde diesen Binär-String von nun an Chromosom nennen. Ein typisches Chromosom könnte in etwas so aussehen: 10010101110101001010011101101110111111101 #####(Don't worry if non of this is making sense to you at the moment, it will all start to become clear shortly. For now, just relax and go with the flow.) (Keine Angst, wenn nichts von alledem für dich im Moment Sinn ergibt, es wird dir bald alles etwas klarer werden. Solange entspann dich und lass dich berieseln.) #####At the beginning of a run of a genetic algorithm a large population of random chromosomes is created. Each one, when decoded will represent a different solution to the problem at hand. Let's say there are N chromosomes in the initial population. Then, the following steps are repeated until a solution is found Am Anfang eines genetischen Algorythmus muss eine große Population von zufällig generierten Chromosomen erzeugt werden. Jedes einzelne stellt decodiert eine eigene Lösung zu unserem Problem dar. Sagen wir es gibt zu Anfang N Chromosome in unserer Population. Dann werden folgende Schritte solange wiederholt, bis eine Lösung für unser Problem gefunden wurde #####Test each chromosome to see how good it is at solving the problem at hand and assign a fitness score accordingly. The fitness score is a measure of how good that chromosome is at solving the problem to hand. Teste jedes Chromosom wie gut es darin ist, das gestellte Problem zu lösen und teile ihm eine entsprechende Fitness Punktzahl zu. Die Fitness Punktzahl ist ein Maß, das angibt wie gut das Chromosom darin ist, das gestellte Problem zu lösen. #####Select two members from the current population. The chance of being selected is proportional to the chromosomes fitness. Roulette wheel selection is a commonly used method. Wähle zwei Chromosome der Population aus. Die warscheinlichkeit, dass ein Chromosom dabei gewählt wird ist proportinal zur Fitness des Chromosoms. Die Roulette Rad Selektion ist eine gern benutzte Methode. #####Dependent on the crossover rate crossover the bits from each chosen chromosome at a randomly chosen point. Abhängig von der Rekombinationsrate (Anm.d.Ü.: Der Autor wählte hier Ursprünglich den Begirff der "Crossover"-Rate, da aber bereits früher von einer "Recombination" die Rede war, fand ich es sinnvoll den Begriff beizubehalten), rekombiniere die Bits von beiden Chromosomen an einer zufällig gewählten Stelle. #####Step through the chosen chromosomes bits and flip dependent on the mutation rate. Gehe durch die Bits der gewählten Chromosome und negiere den Wert der Bits abhängig von der Mutationsrate. #####Repeat step 2, 3, 4 until a new population of N members has been created. Gehe alle Schritte erneut durch, bis eine neue Population mit N Mitgliedern entstanden ist. #####Tell me about Roulette Wheel selection Wie funktioniert das mit der Roulette Rad Auswahl? #####This is a way of choosing members from the population of chromosomes in a way that is proportional to their fitness. It does not guarantee that the fittest member goes through to the next generation, merely that it has a very good chance of doing so. It works like this: Mit der Roulette Rad auswahl ist es möglich einzelne Chromosome in proportinaler Abhängigkeit ihrer Fitness aus der Population auszuwählen. Es wird nicht garantiert, dass der das Fitteste Chromosom in die nächste Generation weiter geht, aber es besteht eine sehr gute Chance, dass es das wird. Und so funktioniert's: #####Imagine that the population’s total fitness score is represented by a pie chart, or roulette wheel. Now you assign a slice of the wheel to each member of the population. The size of the slice is proportional to that chromosomes fitness score. i.e. the fitter a member is the bigger the slice of pie it gets. Now, to choose a chromosome all you have to do is spin the ball and grab the chromosome at the point it stops. Stell dir vor, dass die Gesamt-Fitness der Population ein Kreisdiagramm oder ein Roukette Rad darstellt. Nun bekommt jedes Mitglied der Population ein Stückchen aus dem Rad zugewiesen. Die größe dieses Stückchen ist proportinal zur Fitness Punktzahl des Chromosoms. zB: je fitter ein Chromosom ist, desto größer ist das Stückchen, dass ihm zugewiesen ist. Nun musst du nurnoch das Rad "drehen", um das Chromosom auszuwählen an dessen Stückchen der Scheibe es anhält. #####What's the Crossover Rate? Was ist die Rekombinationsrate #####This is simply the chance that two chromosomes will swap their bits. A good value for this is around 0.7. Crossover is performed by selecting a random gene along the length of the chromosomes and swapping all the genes after that point. Die Rekombinationsrate ist einfach die Warscheinlichkeit, mit der zwei Chromosome ihre Bits austauschen. Ein guter Wert liegt bei etwa 7.0. Rekombination wird vollführt indem eine zufällige Stelle im Chromosom ausgewählt hinter welcher die Chromosome einfach alle Bits miteinander austauschen. #####e.g. Given two chromosomes zB haben wir hier zwei Chromosome 10001001110010010 01010001001000011 #####Choose a random bit along the length, say at position 9, and swap all the bits after that point Wir wählen einen zufälligen Wert innerhalb der Länge der Chromosome, sagen wir 9, und tauschen einfach alle Bits dahinter aus #####so the above become: aus dem von oben wird dann: 10001001101000011 01010001010010010 #####What's the Mutation Rate? Was ist die Mutationsrate? #####This is the chance that a bit within a chromosome will be flipped (0 becomes 1, 1 becomes 0). This is usually a very low value for binary encoded genes, say 0.001 Dabei handelt es sich um die Warscheinlichkeit mit der ein Bit in einem Chromosom sich umkehrt (0 wird zu 1 und 1 zu 0). Normalerweise wird hier ein sehr geringer Wert gewählt, zB 0.001 #####So whenever chromosomes are chosen from the population the algorithm first checks to see if crossover should be applied and then the algorithm iterates down the length of each chromosome mutating the bits if applicable. Jedesmal wenn ein Chromosomenpaar aus der Population ausgewählt wird, wird erst geprüft ob eine Rekombination stattfinden soll und dann durchläuft der Algorythmus die gesamte Länge jedes Chromsomes und lässt die Bits mutieren, falls das erwünscht ist. #####From Theory to Practice Von der Theorie zur Praxis #####To hammer home the theory you've just learnt let's look at a simple problem: Um die Theorie, die war grad verinnigt haben im Einsatz zu sehen, schauen wir uns folgendes simple Problem an: #####Given the digits 0 through 9 and the operators +, -, * and /, find a sequence that will represent a given target number. The operators will be applied sequentially from left to right as you read. Wir haben die Zahlen 0 bis 9 und die Operanten +, -, * und /; unser genetischer Algorythmus soll nun einen Term finden, der eine bestimmte Nummer als Ergebnis hat. Die Operationen werden dabei von links nach rechts ausgeführt, wie man sie auch liest. #####So, given the target number 23, the sequence 6+5*4/2+1 would be one possible solution. Wenn man zB die Nummer 23 hat, wäre der Term 6+5*4/2+1 eine mögliche Lösung. #####If 75.5 is the chosen number then 5/2+9*7-5 would be a possible solution. Wäre die Zahl jedoch 75,5 dann wäre 5/29*7-5 eine mögliche Lösung. #####Please make sure you understand the problem before moving on. I know it's a little contrived but I've used it because it's very simple. Vergewissere dich bitte, dass du das Problem wirklich verstanden hast, bevor du weiter liest. Ich weiß, es ist sehr an den Haaren herbeigezogen, dafür ist es jedoch sehr simpel. #####Stage 1: Encoding Schritt 1: Codierung #####First we need to encode a possible solution as a string of bits… a chromosome. So how do we do this? Well, first we need to represent all the different characters available to the solution... that is 0 through 9 and +, -, * and /. This will represent a gene. Each chromosome will be made up of several genes. zunächst müssen wir eine mögliche Lösung als String aus Bits codieren... ein chromosom. Aber wie machen wir das? Zunächst müssen wir die verschiedenen Zeichen zur Lösung unseres Problems darstellen... dies wären die Zahlen 0 bis 9 und die Rechenzeichen +, -, * und /. Jedes dieser Zeichen ist ein Gen und ein Chromosom ist die Verbindung mehrerer Gene. ####Four bits are required to represent the range of characters used: Um alle Zeichen darstellen zu können muss jedes Zeichen aus 4 Bits bestehen: 0: 0000 1: 0001 2: 0010 3: 0011 4: 0100 5: 0101 6: 0110 7: 0111 8: 1000 9: 1001 +: 1010 -: 1011 *: 1100 /: 1101 #####The above show all the different genes required to encode the problem as described. The possible genes 1110 & 1111 will remain unused and will be ignored by the algorithm if encountered. Die oben aufgeführten Gene werden benötigt um unser Problem zu codieren. Die Gene 1110 und 1111 bleiben dabei ungenutzt und werden einfach ignoriert. #####So now you can see that the solution mentioned above for 23, ' 6+5*4/2+1' would be represented by nine genes like so: Eine codierung des Terms für die oben Aufgeführte 23 (6+5*4/2+1) würde also so ausshene: 0110 1010 0101 1100 0100 1101 0010 1010 0001 6 + 5 * 4 / 2 + 1 ######These genes are all strung together to form the chromosome: Die Gene zu einem Chromosom zusammengezogen so: 011010100101110001001101001010100001 #####A Quick Word about Decoding Noch ein paar Worte zur decodierung #####Because the algorithm deals with random arrangements of bits it is often going to come across a string of bits like this: Da der Algrythmus zufällig generierte Bitreihen (Anm.d.Ü.: Chromosome) benutzt, wird er des öfteren über Strings stolpern, di so aussehen könnten: 0010001010101110101101110010 #####Decoded, these bits represent: Decodiert sähe das wie folgt aus: 0010 0010 1010 1110 1011 0111 0010 2 2 + n/a - 7 2 #####Which is meaningless in the context of this problem! Therefore, when decoding, the algorithm will just ignore any genes which don’t conform to the expected pattern of: number -> operator -> number -> operator …and so on. With this in mind the above ‘nonsense’ chromosome is read (and tested) as: Dieser Term ergibt natürlich keinen Sinn. Deshalb muss unser Algorythmus Gene, die nicht in das Muster "Zahl -> Operant -> Zahl -> Operant -> usw" passen beim decodieren einfach ignorieren. Wenn wir dies beachten würde das oben gezeigte Sinnlose Chromosom wie folgt gelesen werden: 2 + 7 #####Stage 2: Deciding on a Fitness Function Scgritt 2: Auswahl eine Fitness-Funktion #####This can be the most difficult part of the algorithm to figure out. It really depends on what problem you are trying to solve but the general idea is to give a higher fitness score the closer a chromosome comes to solving the problem. With regards to the simple project I'm describing here, a fitness score can be assigned that's inversely proportional to the difference between the solution and the value a decoded chromosome represents. Eine richtige Fitenss-Funktion zu finden kann das komplizierteste an einem genetischen Algorythmus sein. Natürlich kommt es darauf an, welche Problem du lösen willst, aber in der Regel kann man sagen, dass je näher ein Chromosom an die Lösung des Problems kommt, desto höher sollte seine Fitness werden. Für unser genanntes Problem wäre also eine Fitness-Funktion sinnvoll, die einen Wert ereugt, der proportional dazu ist, wie nah die Funktion an den Zielwert gekommen ist. #####If we assume the target number for the remainder of the tutorial is 42, the chromosome mentioned above Für den Rest des Tutorials sagen wir, dass unsere Zielnummer die 42 ist. Das oben gezeigte Chromosom 011010100101110001001101001010100001 #####has a fitness score of 1/(42-23) or 1/19. hätte einen Fitness Wert von 1/(42-23) bzw 1/19. #####As it stands, if a solution is found, a divide by zero error would occur as the fitness would be 1/(42-42). This is not a problem however as we have found what we were looking for... a solution. Therefore a test can be made for this occurrence and the algorithm halted accordingly. Im Moment würde ein "Division by Zero" (A.d.Ü.: Devision durch Null) Fehler auftreten, wenn die Zielzahl erreicht wird, den die Fitness wäre 1/(42-42). Das sollte aber kein Problem sein, denn wir haben dann ja bereits gefunden was wir suchten: Eine Lösung für unser Problem! Der Algorythmus kann nun dementsprechend gestoppt werden. #####Stage 3: Getting down to business Schritt 3: Dann leg mal los! #####First, please read this tutorial again. Bitte lese an dieser Stelle das Tutorial erst ein weiteres mal. #####If you now feel you understand enough to solve this problem I would recommend trying to code the genetic algorithm yourself. There is no better way of learning. If, however, you are still confused, I have already prepared some simple code which you can find here. Please tinker around with the mutation rate, crossover rate, size of chromosome etc to get a feel for how each parameter effects the algorithm. Hopefully the code should be documented well enough for you to follow what is going on! If not please email me and I’ll try to improve the commenting. Falls du der Meinung bist du verstehst genug von der Materie, schlage ich dir vor, du fängst am besten gleich an einen eigenen genetischen Algorythmus zu schreiben. Es gibt keinen besseren weg etwas zu lernen. Falls es dir noch immer nicht ganz klar geworden ist, habe ich hier ein wenig einfachen Code vorbereitet. Bitte spiele etwas an der Mutationsrate, der Rekombinationsrate und der länge der Chromosome, usw herum um ein Gefühl dafür zu bekommen wir sich die einzelnen Parameter auf das Ergebnis ausüben. Ich hoffe der Code ist ausreichend kommentiert, so dass du auch verstehst was passiert. Falls das nicht der Fall ist, schreib mir eine eMail und ich werde versuchen die Kommentare zu verbessern! #####Note: The code given will parse a chromosome bit string into the values we have discussed and it will attempt to find a solution which uses all the valid symbols it has found. Therefore if the target is 42, + 6 * 7 / 2 would not give a positive result even though the first four symbols("+ 6 * 7") do give a valid solution. Achtung: Der Code decodiert die Bit-Strings genau, wie oben besprochen und versucht eine Lösung zu finden indem es den gesamten Term abarbeitet. Falls also die Zielnummer 42 ist, dann wäre + 6 * 7 / 2 keine Lösung, obwohl die ersten paar Zeichen + 6 * 7 eine gültige Lösung wären. ######(Delphi code submitted by Asbjørn can be found here and Java code submitted by Tim Roberts can be found here) (Delphi Code eingeschickt von Asbjørn kann hier gefunden werden und Java Code eingeschickt von Tim Roberts kann hier gefunden werden) #####Last Words Schluß #####I hope this tutorial has helped you get to grips with the basics of genetic algorithms. Please note that I have only covered the very basics here. If you have found genetic algorithms interesting then there is much more for you to learn. There are different selection techniques to use, different crossover and mutation operators to try and more esoteric stuff like fitness sharing and speciation to fool around with. All or some of these techniques will improve the performance of your genetic algorithms considerably. Ich hoffe dieses Tutorial hilft dir einen Einstieg in die Grundlagen von genetischen Agorythmen zu finden. Bitte beachte, dass ich nur die Grundlagen behandelt habe. Falls du dich weitergehend für genetische Algorythmen interessierst, dann gibt es noch eine Menge zu lernen. Es gibt verschiedene Auswahlverfahren, verschiedene Rekombinations- und Mutationsfunktionen die man einsetzen kann und auch ne ganze Menge esoterischer Sachen, wie zB Fitnesswert Teilung und Spezialisierung, an der man rumspielen könnte. Viele dieser Techniken können die Performance deines genetischen Algrythmus stark erhöhen. #####Stuff to Try Zeugs zum ausprobieren #####If you have succeeded in coding a genetic algorithm to solve the problem given in the tutorial, try having a go at the following more difficult problem: Falls du deinen genetischen Algorythmus programmiert und das im Tutorial gestellte Problem gelöst hast, dann kannst du dich ja mal an folgenden Aufgaben versuchen: #####Given an area that has a number of non overlapping disks scattered about its surface as shown in Screenshot 1, In einem Gebiet gibt es eine Anzahl von sich nicht überlappenden, zufällig verteilten Scheiben, wie auf Screenshot 1 zu sehen Screenshot 1 #####Use a genetic algorithm to find the disk of largest radius which may be placed amongst these disks without overlapping any of them. See Screenshot 2. Benutze nun einen genetischen Algorythmus um die größtmögliche Scheibe zu ermitteln, die du zwischen die anderen legen kannst, ohne, dass sich die scheiben überschneiden. Schau dir dazu Screenshot 2 an. Screenshot 2 ######As you may have already gathered, I've already written some code that solves this problem so if you get stuck you can find it here. (but you will have a go yourself first eh? ;0)). For those of you without compilers, you can get the executable file here. Wie du evtl schon gemerkt hast, habe ich dazu schon etwas Code geschrieben. Falls du also stecken bleibst und nicht weiter kommst, dann kannst du diesen Code hier finden (zuvor aber probierst du es mal schön alleine, ja? ;0)). Für die unter euch ohne Compiler, gibt es hier eine ausführbare Version.