Im Bereich der künstlichen Intelligenz ist ein evolutionärer Algorithmus (EA) eine Teilmenge von Gesamtbevölkerungsberechnungen, die auf metaheuristischer Optimierung basieren. EA verwendet von der biologischen Entwicklung inspirierte Mechanismen wie Reproduktion, Mutation, Rekombination und Selektion. Die Kandidatenlösung im Problem der evolutionären Optimierungsalgorithmen spielt die Rolle von Individuen in der Bevölkerung. Und auch die Fitnessfunktion entscheidet über die Qualität der Antworten.
Evolutionäre Algorithmen nähern sich Lösungen für alle Arten von Problemen oft gut an. Denn im Idealfall machen sie keine Annahmen über die zugrunde liegende Fitnesslandschaft. Methoden, die für evolutionäre Modellierung und genetische Algorithmen verwendet werden, beschränken sich normalerweise auf Studien mikroevolutionärer Prozesse und Planungsmodelle, die auf zellulären Stadien basieren. In den meisten echten EA-Anwendungen ist die Rechenkomplexität ein hinderlicher Faktor.
EigentlichDieses Problem bezieht sich auf die Schätzung der Fitnessfunktion. Die Fitnessnäherung ist eine Lösung, um diese Schwierigkeit zu überwinden. Ein scheinbar einfacher EA kann jedoch oft komplexe Probleme lösen. Daher kann es keinen direkten Zusammenhang zwischen der Komplexität der Sequenz und dem Problem geben. Weitere Details finden Sie in den Büchern "Evolutionäre Algorithmen".
Implementierung
Schritt eins besteht darin, eine Anfangspopulation von Individuen nach dem Zufallsprinzip zu erstellen.
Schritt zwei ist die Beurteilung der Eignung jedes Einzelnen in dieser Gruppe (Zeitlimit, ausreichende Vorbereitung usw.).
Schritt drei - Wiederholen Sie die folgenden Regenerationsschritte bis zum Abschluss:
- Auswahl der am besten geeigneten Personen für die Zucht (Eltern).
- Bringen Sie neue Individuen mit, die den evolutionären Algorithmus bestanden haben, indem Sie Crossover und Mutation verwenden, um Nachkommen zu bekommen.
- Beurteile die individuelle Fitness neuer Leute.
- Ersetze die am wenigsten fitte Population durch sie.
Typen
Genetischer Algorithmus ist eine evolutionäre Sequenz, die beliebteste Art von Expert Advisor. Eine Lösung des Problems wird in Form von Zahlenketten gesucht (traditionell binär, obwohl die besten Darstellungen normalerweise diejenigen sind, die mehr in dem zu lösenden Problem widerspiegeln), indem Operatoren wie Rekombination und Mutation (manchmal eins, in einigen Fällen beides) angewendet werden). Diese Art von Expert Advisor wird häufig bei Optimierungsproblemen verwendet. Ein anderer Name dafür ist fetura (aus dem Lateinischen für „Geburt“):
- Genetische Programmierung. Es stellt Lösungen als Computercodes dar, und ihre Eignung wird durch ihre Fähigkeit bestimmt, Rechenaufgaben auszuführen.
- Evolutionäre Programmierung. Ähnlich dem evolutionären genetischen Algorithmus, aber die Struktur ist festgelegt und ihre numerischen Parameter können sich ändern.
- Programmierung der Genexpression. Entwickelt Computeranwendungen, erforscht aber das Genotyp-Phänotyp-System, bei dem Projekte unterschiedlicher Größe auf linearen Chromosomen mit fester Länge kodiert werden.
- Strategie. Arbeitet mit Vektoren reeller Zahlen als Darstellungen von Lösungen. Verwendet normalerweise selbstadaptive evolutionäre Mutationsratenalgorithmen.
- Unterschiedliche Entwicklung. Basiert auf Vektordifferenzen und ist daher vor allem für numerische Optimierungsprobleme geeignet.
- Neuroevolution. Ähnlich der evolutionären Programmierung und genetischen Algorithmen. Letztere sind jedoch künstliche neuronale Netze, die die Struktur und das Gewicht der Verbindungen beschreiben. Die Genomcodierung kann direkt oder indirekt erfolgen.
Vergleich mit biologischen Verfahren
Eine mögliche Einschränkung vieler evolutionärer Algorithmen ist das Fehlen einer klaren Unterscheidung zwischen Genotyp und Phänotyp. In der Natur durchläuft ein befruchtetes Ei einen komplexen Prozess, der als Embryogenese bekannt ist, um reif zu werden. Es wird angenommen, dass diese indirekte Codierung die genetische Suche zuverlässiger macht (d. h. weniger wahrscheinlich tödliche Mutationen verursacht) und möglicherweise auch die Entwicklungsfähigkeit des Organismus verbessert. Solche indirekten (mit anderen Worten,generative oder entwicklungsbedingte) Kodierungen ermöglichen es der Evolution auch, Regelmäßigkeiten in der Umgebung auszunutzen.
Jüngste Arbeiten zur künstlichen Embryogenese oder zu Entwicklungssystemen versuchen, diese Probleme anzugehen. Bei der Programmierung der Genexpression wird die Genotyp-Phänotyp-Region erfolgreich erforscht, wobei die erste aus linearen Multigen-Chromosomen fester Länge besteht und die zweite aus vielen Expressionsbäumen oder Computerprogrammen unterschiedlicher Größe und Form besteht.
Verwandte Techniken
Zu den Algorithmen gehören:
- Optimierung der Ameisenkolonie. Es basiert auf der Idee, dass Insekten nach Nahrung suchen, indem sie sich mit Pheromonen verbinden, um Pfade zu bilden. Hauptsächlich geeignet für kombinatorische Optimierung und Graphenprobleme.
- Root-Slider-Algorithmus. Der Schöpfer ließ sich von der Funktion der Pflanzenwurzeln in der Natur inspirieren.
- Algorithmus für künstliche Bienenvölker. Basierend auf dem Verh alten von Honigbienen. Es wird hauptsächlich für die numerische Optimierung vorgeschlagen und erweitert, um kombinatorische, beschränkte und multiobjektive Probleme zu lösen. Der Bienenalgorithmus basiert auf dem Nahrungssuchverh alten von Insekten. Es wurde in vielen Anwendungen wie Routing und Scheduling eingesetzt.
- Partikelschwarmoptimierung - basierend auf Ideen zum Verh alten von Tierherden. Und auch primär für numerische Prozessaufgaben geeignet.
Andere gängige metaheuristische Methoden
- Jagdsuche. Eine Methode, die auf dem Gruppenfang bestimmter Tiere, wie zum Beispiel Wölfe, basiertverteilen ihre Pflichten, um die Beute zu umgeben. Jedes der Mitglieder des evolutionären Algorithmus steht in irgendeiner Weise in Beziehung zu den anderen. Dies gilt insbesondere für die Führungskraft. Dies ist eine kontinuierliche Optimierungsmethode, die als kombinatorische Prozessmethode adaptiert wurde.
- Suche nach Messungen. Im Gegensatz zu naturbasierten metaheuristischen Methoden verwendet der adaptive Prozessalgorithmus keine Metapher als Hauptprinzip. Stattdessen wird eine einfache leistungsorientierte Methode verwendet, die auf der Aktualisierung des Suchdimensionsverhältnisparameters bei jeder Iteration basiert. Der Firefly-Algorithmus ist davon inspiriert, wie sich Glühwürmchen mit ihrem blinkenden Licht anziehen. Dies ist besonders nützlich für die multimodale Optimierung.
- Suche nach Harmonie. Basierend auf den Vorstellungen des Verh altens von Musikern. In diesem Fall sind evolutionäre Algorithmen der richtige Weg für die kombinatorische Optimierung.
- Gaußsche Anpassung. Basierend auf der Informationstheorie. Wird verwendet, um die Leistung und die durchschnittliche Verfügbarkeit zu maximieren. Ein Beispiel für evolutionäre Algorithmen in dieser Situation: Entropie in Thermodynamik und Informationstheorie.
Memetic
Eine hybride Methode, die auf Richard Dawkins' Idee eines Memes basiert. Es handelt sich in der Regel um einen populationsbasierten Algorithmus in Kombination mit individuellen Lernverfahren, die lokale Verfeinerungen durchführen können. Betont die Nutzung von problemspezifischem Wissen und versucht, feinkörnige und globale Suchen auf synergistische Weise zu organisieren.
EvolutionärAlgorithmen sind ein heuristischer Ansatz für Probleme, die nicht einfach in polynomieller Zeit gelöst werden können, wie z. B. klassische NP-schwere Probleme und alles andere, dessen vollständige Verarbeitung zu lange dauern würde. Wenn sie unabhängig voneinander verwendet werden, werden sie normalerweise für kombinatorische Probleme verwendet. Genetische Algorithmen werden jedoch häufig zusammen mit anderen Methoden verwendet, um schnell mehrere optimale Ausgangspunkte für die Arbeit zu finden.
Die Prämisse des evolutionären Algorithmus (bekannt als Berater) ist ziemlich einfach, vorausgesetzt, Sie sind mit dem Prozess der natürlichen Selektion vertraut. Es enthält vier Hauptschritte:
- Initialisierung;
- Auswahl;
- genetische Operatoren;
- end.
Jeder dieser Schritte entspricht ungefähr einem bestimmten Aspekt der natürlichen Selektion und bietet einfache Möglichkeiten, diese Kategorie von Algorithmen zu modularisieren. Einfach ausgedrückt, in EA werden die fittesten Mitglieder überleben und sich fortpflanzen, während die unfitten Mitglieder sterben und nicht zum Genpool der nächsten Generation beitragen.
Initialisierung
Um den Algorithmus zu starten, müssen Sie zuerst eine Reihe von Lösungen erstellen. Die Population enthält eine beliebige Anzahl möglicher Problemstellungen, die oft als Mitglieder bezeichnet werden. Sie werden oft zufällig generiert (innerhalb der Einschränkungen der Aufgabe) oder, wenn einige Vorkenntnisse bekannt sind, vorläufig um das zentriert, was als ideal angesehen wird. Wichtig ist, dass die Bevölkerung ein breites Lösungsspektrum abdeckt,weil es im Wesentlichen ein Genpool ist. Wenn man also viele verschiedene Möglichkeiten innerhalb eines Algorithmus erforschen will, sollte man danach streben, viele verschiedene Gene zu haben.
Auswahl
Nachdem die Population erstellt wurde, müssen ihre Mitglieder nun nach der Fitnessfunktion bewertet werden. Die Fitnessfunktion nimmt die Eigenschaften eines Mitglieds und gibt eine numerische Darstellung dessen, wie fit das Mitglied ist. Sie zu erstellen kann oft sehr schwierig sein. Es ist wichtig, ein gutes System zu finden, das die Daten genau darstellt. Das ist sehr spezifisch für das Problem. Nun gilt es, die Eignung aller Teilnehmer zu berechnen und einige der besten Mitglieder auszuwählen.
Mehrere Zielfunktionen
EAs können auch erweitert werden, um diese Systeme zu verwenden. Dies verkompliziert den Prozess etwas, da bei der Verwendung ein Satz erh alten wird, anstatt einen optimalen Punkt zu identifizieren. Die Menge der Lösungen wird als Pareto-Grenze bezeichnet und enthält Elemente, die in dem Sinne gleichermaßen geeignet sind, dass keine von ihnen eine andere dominiert.
Genetische Operatoren
Dieser Schritt beinh altet zwei Teilschritte: Crossover und Mutation. Nach der Auswahl der besten Begriffe (normalerweise die Top 2, aber diese Anzahl kann variieren) werden sie nun verwendet, um die nächste Generation im Algorithmus zu erstellen. Durch die Anwendung der Eigenschaften der gewählten Eltern werden neue Kinder geschaffen, die eine Mischung von Eigenschaften sind. Dies kann je nach Art der Daten oft schwierig sein, normalerweise jedoch bei kombinatorischen Problemenes ist durchaus möglich gültige Kombinationen zu mischen und auszugeben.
Nun ist es notwendig, neues genetisches Material in die Generation einzuführen. Wird dieser wichtige Schritt nicht unternommen, bleibt der Wissenschaftler sehr schnell in lokalen Extremen stecken und kommt nicht zu optimalen Ergebnissen. Dieser Schritt ist eine Mutation, und zwar ganz einfach, indem ein kleiner Teil der Kinder so verändert wird, dass sie überwiegend keine Teilmengen der Gene der Eltern widerspiegeln. Mutationen treten normalerweise probabilistisch auf, da die Wahrscheinlichkeit, dass ein Kind sie bekommt, sowie ihr Schweregrad von der Verteilung bestimmt werden.
Kündigung
Am Ende muss der Algorithmus enden. Dies geschieht normalerweise in zwei Fällen: Entweder hat es eine bestimmte maximale Ausführungszeit erreicht, oder es hat einen Leistungsschwellenwert erreicht. An diesem Punkt wird die endgültige Lösung ausgewählt und zurückgegeben.
Beispiel für evolutionäre Algorithmen
Nun, um das Ergebnis dieses Prozesses zu veranschaulichen, müssen Sie den Berater in Aktion sehen. Um dies zu tun, können wir uns daran erinnern, wie mehrere Generationen von Dinosauriern das Laufen lernten (und allmählich das Land eroberten), ihre Körperstruktur optimierten und Muskelkraft anwandten. Obwohl die Reptilien der frühen Generation nicht laufen konnten, konnte der Berater sie im Laufe der Zeit durch Mutation und Crossover in eine Form entwickeln, die laufen konnte.
Diese Algorithmen werden in der modernen Welt immer relevanter, da darauf basierende Lösungen zunehmend in Branchen wie digitalem Marketing, Finanzen undGesundheitswesen.
Wo werden EAs verwendet?
Im weiteren Sinne werden evolutionäre Algorithmen in einer Vielzahl von Anwendungen eingesetzt, darunter Bildverarbeitung, Fahrzeug-Routing, Optimierung der Mobilkommunikation, Softwareentwicklung und sogar das Training künstlicher neuronaler Netze. Diese Tools sind das Herzstück vieler Apps und Websites, die Menschen täglich nutzen, darunter Google Maps und sogar Spiele wie Die Sims. Darüber hinaus verwendet der medizinische Bereich EA, um klinische Entscheidungen bezüglich der Krebsbehandlung zu treffen. Tatsächlich sind evolutionäre Algorithmen so robust, dass sie verwendet werden können, um fast jedes Optimierungsproblem zu lösen.
Mooresches Gesetz
Die wachsende Prävalenz von EO wird durch zwei Hauptfaktoren angetrieben: verfügbare Rechenleistung und die Anhäufung großer Datensätze. Die erste lässt sich durch das Mooresche Gesetz beschreiben, das im Wesentlichen besagt, dass sich die Rechenleistung eines Computers etwa alle zwei Jahre verdoppelt. Diese Vorhersage gilt seit Jahrzehnten. Der zweite Faktor bezieht sich auf die wachsende Abhängigkeit von Technologie, die es Institutionen ermöglicht, eine unglaublich große Datenmenge zu sammeln, die es ihnen ermöglicht, Trends zu analysieren und Produkte zu optimieren.
Wie können evolutionäre Algorithmen Marketern helfen?
Die Marktbedingungen ändern sich schnell und sind sehr wettbewerbsintensiv. Dies hat Marketingmanager dazu gezwungen, um eine bessere Entscheidungsfindung zu konkurrieren. Erhöhung verfügbarDie Rechenleistung hat Mitarbeiter dazu veranlasst, EA zur Problemlösung zu verwenden.
Conversion-Optimierung
Eines der Hauptziele ist es, die Besucherzahlen der Website zu erhöhen. Dieses Problem läuft darauf hinaus, die Anzahl der Benutzer zu optimieren, die tun, was der Vermarkter will. Wenn ein Unternehmen beispielsweise Laptops verkauft, ist es ideal, die Anzahl der Website-Besucher zu erhöhen, die das Produkt schließlich kaufen. Das ist die Essenz der Conversion-Rate-Optimierung.
Einer der überraschend wichtigen Aspekte ist die Wahl der Benutzeroberfläche. Wenn das Webdesign nicht sehr benutzerfreundlich ist, gibt es diejenigen, die das Produkt aus dem einen oder anderen Grund nicht kaufen. Das Ziel ist dann, die Anzahl der Benutzer zu reduzieren, die am Ende nicht konvertieren, was den Gesamtgewinn erhöht.
