StudySmarter - Die all-in-one Lernapp.
4.8 • +11k Ratings
Mehr als 5 Millionen Downloads
Free
Americas
Europe
Ein städtischer Paketdienst erhielt von einem Kunden den Auftrag, Pakete vom Lager an die Adresse des Kunden zu liefern. Die Anzahl der Pakete ist so gering, dass ein LKW ausreicht, um alle Pakete auf einmal transportieren zu können. Die Frage im Lieferprozess lautet: In welche Richtung soll der Lkw-Fahrer fahren, damit die Fahrstrecke möglichst kurz ist?Es wird ein genetischer Algorithmus eingerichtet,…
Entdecke über 200 Millionen kostenlose Materialien in unserer App
Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken
Jetzt kostenlos anmeldenEin städtischer Paketdienst erhielt von einem Kunden den Auftrag, Pakete vom Lager an die Adresse des Kunden zu liefern. Die Anzahl der Pakete ist so gering, dass ein LKW ausreicht, um alle Pakete auf einmal transportieren zu können. Die Frage im Lieferprozess lautet: In welche Richtung soll der Lkw-Fahrer fahren, damit die Fahrstrecke möglichst kurz ist?
Es wird ein genetischer Algorithmus eingerichtet, um ein ausreichend gutes Ergebnis zu ermitteln.
Genetische Algorithmen sind die bekannteste Art evolutionärer Algorithmen. Der Begriff genetischer Algorithmus geht auf eine von Bagleys frühen Arbeiten zurück. Die Form, die man heute kennt, wurde jedoch von John H. Holland entwickelt.
Ein genetischer Algorithmus ist eine Optimierungstechnik, die Optimierungsprobleme durch die Kombinierung guter Teillösungen löst, die letztlich zu einer guten globalen Lösung führen.
Hollands Ziele waren weitreichend. Die Ziele dieser Arbeit waren zweigeteilt:
Eine der bemerkenswertesten Errungenschaften von Hollands Arbeit war die Formulierung des Schema-Theorems. Damit wurde versucht zu erklären, wie und warum genetische Algorithmen funktionieren. Genetische Algorithmen bilden eine Untergruppe evolutionärer Algorithmen.
Evolutionäre Algorithmen modellieren eine Vielzahl natürlicher Prozesse wie Selektion, Rekombination, Mutation, Migration, Lokalität, Parallelität und Konkurrenz. Jeder dieser Prozesse kann in zahlreichen Varianten auftreten.
Evolutionäre Algorithmen sind probabilistische Suchverfahren, die auf den Prinzipien der natürlichen biologischen Evolution basieren.
Genetische Algorithmen sind an der biologischen Evolution beteiligt und basieren auf ihrer Genetik und Terminologie. In der folgenden Tabelle wird kurz auf die wichtigsten Begriffe und ihre Entwicklung eingegangen.
Begriff | Funktionsweise |
Zellen | Die Grundbausteine aller Organismen sind Zellen. Die meisten Zellen bilden eukaryotische Zellen. |
Chromosomen | Zellen enthalten Chromosomen, Träger des genetischen Materials. Das Erbgut ist in der Erbsubstanz verschlüsselt und bildet den „Bauplan“ des Organismus (Individuums). |
Gene | Chromosomen können in kleine Teile, sogenannte Gene, zerlegt werden, die ein bestimmtes Merkmal wie die Augenfarbe bestimmen. |
Allele | Gene können keine Zustände annehmen, sondern haben feste Ausprägungen, die Allele genannt werden. Zum Beispiel es gibt Allele für die braune, grüne und blaue Augenfarbe. |
Heutzutage gibt es viele Bereiche, in denen genetische Algorithmen zur Lösung von Problemen eingesetzt werden.
Die Form eines Flügels und die Form des Rumpfes von Flugzeugen werden beispielsweise mit genetischen Algorithmen optimiert und mit Computersimulationen getestet.
Auch beim Brückenbau können Position, Form und Gewicht einzelner Brückenbauteile durch den Einsatz von genetischen Algorithmen verbessert werden.
Im Allgemeinen helfen genetische Algorithmen, NP-schwere Probleme wie das Problem des Handlungsreisenden oder das Backpacking-Problem zu lösen.
Der genetische Algorithmus wird verwendet, um den Schwellenpotentialvektor sowie die Netzwerktopologie des neuronalen Netzwerks abzustimmen.
Darüber hinaus unterstützen genetische Algorithmen die Erstellung von Fahrplänen, Stundenplänen und Grundrissen, die von öffentlichen Einrichtungen wie Schulen und Universitäten verwendet werden.
Evolution ist die Veränderung vererbter Eigenschaften oder Gene. Gene werden während des Fortpflanzungsprozesses an die Nachkommen weitergegeben. Es gibt drei grundlegende Mechanismen, die die Evolution formen:
Im Folgenden werden die einzelnen Operatoren eines genetischen Algorithmus mit einigen wichtigen Verfahren aufgelistet. Die einzelnen Verfahren werden in den folgenden Abschnitten erläutert.
Die Selektion bestimmt, welche Individuen für die Zucht ausgewählt werden und wie viele Nachkommen jedes ausgewählte Individuum produzieren wird. Der erste Schritt besteht darin, jeder Person mithilfe einer der folgenden Methoden die Fitness zuzuordnen:
Die Anpassungsfähigkeit eines Individuums wird als Fitness bezeichnet.
Nach der Selektion mutieren die Nachkommen. Die Untervariablen werden durch kleine Störungen (Mutationsschritte) verändert. Diese Änderungen sind fast unwahrscheinlich. Abhängig von der Repräsentation der Variablen und der Art der Zielfunktion können unter anderem die folgenden Methoden verwendet werden:
Nachkommen werden von den Eltern durch Rekombination geboren. Dazu werden Informationen der Eltern kombiniert (die Eltern sind die Paarungspopulation). Je nach Repräsentation der Variablen im Individuum und der Zielsetzung (Art der Zielfunktion) können unterschiedliche Methoden verwendet werden:
Die Grundidee des genetischen Algorithmus ist zunächst die “Empfohlene Lösung“ zu verwenden und zu kombinieren, bis eine ausreichend gute Lösung für das Problem gefunden ist. Dies führt zu folgendem Ablauf des genetischen Algorithmus:
Gegeben: ein Optimierungsproblem mit einem Suchraum S und einer Fitnessfunktion f. Auflösung: Generiere eine zufällige Startpopulation P, WHILE (Endbedingung nicht erfüllt). { Die Fitness von Personen aus P. Wähle nach Fitness aus. Wende den genetischen Operator an. } Ergebnisse: Bestes Individuum(Lösung) aus der Population.
Ein „Individuum“ in einer Population P ist als Zeichenkette, Zahlenfolge oder Variablenfolge binär kodiert, und statt eines Individuums spricht man nur von dem Chromosom, das dieses Individuum repräsentiert.
In Analogie zur Genetik sind Gene einzelne Merkmale oder Variablen und Allele sind die Werte, die sie annehmen können. Individuen oder Chromosomen entsprechen Lösungen aus dem Suchraum S des Problems.
Die drei Schritte der Fitnessberechnung, der Selection des genetischen Operators und der Anwendung können beliebig oft wiederholt werden.
Mit jeder neuen Generation können Veränderungen eintreten, die neue und bessere Lösungen in Form von Chromosomen schaffen. Allerdings gibt es keine Garantie dafür, dass die neue Lösung immer besser ist als die vorherige.
Daher ist es sinnvoll und notwendig, ein Abbruchkriterium zu definieren, das dem Algorithmus mitteilt, wann die Chromosomen der Population ausreichend sind, um eine gute Lösung darzustellen. Hier sind einige Beispiele für Stoppkriterien:
Nr. | Genetischer Algorithmus Abbruchkriterium |
1. | Algorithmen haben eine gewisse Anzahl von Generationen durchlaufen. |
2. | Es gibt keine Verbesserung gegenüber der vorherigen Generation. |
3. | Die durchschnittliche Verbesserung früherer Generationen ist unter einen Wert gefallen. |
Das KI-System arbeitet mit intelligenten Algorithmen. In diese Kategorie fallen heuristische Methoden, künstliche neuronale Netze und evolutionäre (genetische) Algorithmen.
Watson ist die KI von IBM. Es ist ein kognitives System, das durch Interaktionen lernt und laut IBM evidenzbasierte Antworten liefert, die bessere Ergebnisse garantieren. Watson basiert auf einem genetischen Algorithmus.
Diese Algorithmen können Daten als Eingabe verwenden und eine Ausgabelösung bereitstellen. Sie kopieren biologische und evolutionäre Mechanismen, um aus einer Vielzahl von Lösungen die beste zu finden. Dabei „lernen“ sie aus ihren Fehlern und verbessern ihr eigenes Verhalten.
Genetische Algorithmen werden hauptsächlich im Deep Learning eingesetzt. Dort werden neuronale Netze gebildet, bei denen beim Training die Gewichte der Neuronen angepasst werden, was sich auf das Endergebnis auswirkt. Hier kommen genetische Algorithmen ins Spiel.
Eine neuronale Netzpopulation wird mit zufälligen Gewichtungen für jedes Neuron erstellt. Anschließend werden diese Netze getestet und die Ergebnisse ausgewertet. Die besten werden beibehalten und Neuronen durchlaufen Stadien der Rekombination und Mutation. Das heißt, die Gewichte der Neuronen werden angepasst.
Hier ist ein kleines Beispiel für Dich. Dies ist eines der bekanntesten mathematischen Sudoku-Rätsel. Dieses Rätsel kann durch einen genetischen Algorithmus gelöst werden. Siehe unten für den entsprechenden Python-Code.
Sudoku:
#PGAPy ist eine Python-Bibliothek für genetische Algorithmen #Die meisten genetischen Methoden sind dort vordefiniert, wie z.B. get_allele() def evaluate (self, p, pop) : sudoku = Sudoku (verbose = False, solvemax = 50) count = 0 for x in range (6) : for y in range (6) : val = self.get_allele (p, pop, 6 * x + y) count += val != 0 sudoku.set (x, y, val) sudoku.resolve () resolvecount = sudoku.resolvecount if not resolvecount : return 1000 * count * count if resolvecount == 1 : return count return 1000 - count + resolvecount
Ein genetischer Algorithmus ist eine Optimierungstechnik, die Optimierungsprobleme löst.
Die Grundidee des genetischen Algorithmus ist zunächst die “Empfohlene Lösung“ zu verwenden und zu kombinieren, bis eine ausreichend gute Lösung für das Problem gefunden ist.
Wie möchtest du den Inhalt lernen?
94% der StudySmarter Nutzer erzielen bessere Noten.
Jetzt anmelden94% der StudySmarter Nutzer erzielen bessere Noten.
Jetzt anmeldenWie möchtest du den Inhalt lernen?
Kostenloser informatik Spickzettel
Alles was du zu . wissen musst. Perfekt zusammengefasst, sodass du es dir leicht merken kannst!
Sei rechtzeitig vorbereitet für deine Prüfungen.
Teste dein Wissen mit spielerischen Quizzes.
Erstelle und finde Karteikarten in Rekordzeit.
Erstelle die schönsten Notizen schneller als je zuvor.
Hab all deine Lermaterialien an einem Ort.
Lade unzählige Dokumente hoch und habe sie immer dabei.
Kenne deine Schwächen und Stärken.
Ziele Setze dir individuelle Ziele und sammle Punkte.
Nie wieder prokrastinieren mit unseren Lernerinnerungen.
Sammle Punkte und erreiche neue Levels beim Lernen.
Lass dir Karteikarten automatisch erstellen.
Erstelle die schönsten Lernmaterialien mit unseren Vorlagen.
Melde dich an für Notizen & Bearbeitung. 100% for free.