Biologielehrer: Mathelehrer, bitte gehen Sie weg, ich werde dieses Problem lösen!

Die Natur ist für den Menschen eine unerschöpfliche Quelle innovativer Inspiration. Die Lebewesen in der Natur verfügen über eine außergewöhnliche Anpassungsfähigkeit und Weisheit: Wie finden Ameisenkolonien den kürzesten Weg zu Nahrungsquellen, wie fliegen Wildgänse bei der Nahrungssuche die kürzeste Distanz, wie entwickeln Organismen verschiedene Merkmale ... Können wir durch die rationale Anwendung dieser Gesetze ... mathematische Probleme lösen?

(Bildquelle: Veer-Fotogalerie)

Das stimmt, und es behandelt Probleme, die mit der traditionellen mathematischen Theorie nur schwer zu lösen sind.

Optimierungsprobleme und heuristische Algorithmen

Schauen wir uns zunächst ein mathematisches Problem an:

Berechnen Sie den Maximalwert der folgenden quadratischen Funktion

Für diese einfache Zielfunktion können Sie die folgende Formel direkt anwenden: Wenn die unabhängige Variable x = -b/2a ist, beträgt der Maximalwert der Zielfunktion (4ac-b^2)/4a (wenn Sie es vergessen, wenden Sie sich bitte an Ihren Mathematiklehrer an der High School). Diese Lösung, die direkt als Formel ausgedrückt werden kann, wird als analytische Lösung bezeichnet.

Bei einfachen Fragen erhalten Sie die Antwort in einem Schritt

Dieses Problem, den Maximal-/Minimalwert einer Funktion zu finden, ist ein Optimierungsproblem, und diese Funktion wird als Zielfunktion bezeichnet. Ein Optimierungsalgorithmus ist ein Algorithmus, der den Minimalwert einer Zielfunktion berechnet.

In der Praxis ist die Zielfunktion des Optimierungsproblems oft komplex und kann nicht analytisch gelöst werden. Daher werden Gradienten (Ableitungen multivariater Funktionen) häufig für iterative Lösungen verwendet.

Für einige komplexere Zielfunktionen können Gradientenmethoden jedoch nicht verwendet werden. Um beispielsweise den Minimalwert der folgenden Funktion zu berechnen

Komplexe Zielfunktion, Formel nicht anwendbar

Bei Verwendung herkömmlicher Gradientenmethoden tendieren diese eher dazu, zum lokalen Optimum (Lokales Optimum) zu konvergieren, also zum Maximalpunkt innerhalb eines bestimmten Bereichs, als zum globalen Optimum (Globales Optimum) , also zum Maximalpunkt innerhalb des globalen Bereichs.

Gradientenmethoden neigen dazu, in die lokale Optimalität zu fallen

Die Optimierung ähnlich komplexer Funktionen war schon immer ein schwieriges Problem. Inspiriert von bestimmten Naturgesetzen simulierten Wissenschaftler natürliche Algorithmen und schlugen mehrere heuristische Algorithmen vor, um Optimierungsprobleme zu bewältigen, die mit traditionellen mathematischen Theorien nur schwer zu lösen sind.

Durch die Simulation der Gesetze von Ameisenkolonien bei der Nahrungssuche und dem Nahrungstransport wurde beispielsweise der Ant Colony Algorithm vorgeschlagen. Durch die Simulation der Gesetze der Nahrungssuche von Gänsen in der Luft wurde der Algorithmus zur Partikelschwarmoptimierung vorgeschlagen. Durch die Simulation der Gesetze der biologischen Vererbung und Evolution wurde der genetische Algorithmus vorgeschlagen ...

Was denken algorithmische Wissenschaftler über biologische Genetik und Evolution?

Der in diesem Artikel vorgestellte heuristische Algorithmus basiert auf der Simulation der Gesetze der biologischen Genetik und Evolution. Wie also sehen Genetik und Evolution aus der Sicht von Algorithmenforschern aus? Hier nehmen wir die Evolution der Giraffen als Beispiel (beachten Sie, dass genetische Algorithmen lediglich Nachahmungen bekannter Evolutionsgesetze sind und nicht unbedingt den biologischen Gesetzen entsprechen).

In der Natur gibt es viele Arten von Organismen, deren Eigenschaften sowohl durch Gene als auch durch externe Faktoren bestimmt werden. Da die Gene jedoch eine dominierende Rolle spielen, werden externe Faktoren hier ignoriert. Beispielsweise wird die Halslänge einer Giraffe durch ihre Gene bestimmt.

Gene sind das genetische Material von Organismen und bestehen aus mehreren Nukleotiden, ähnlich wie „AaBbCc“. Die Evolution einer Population bringt zwangsläufig genetische Veränderungen mit sich.

Die natürliche Selektion wirkt nicht direkt auf Gene, sondern auf Merkmale. Individuen haben unterschiedliche Eigenschaften und unterschiedliche Fähigkeiten zum Überleben. Je länger beispielsweise der Hals eines Hirsches ist, desto mehr Blätter kann er fressen und desto besser sind seine Überlebenschancen. Die Überlebensfähigkeit wird quantifiziert und als Fitness bezeichnet.

Die Fitness sollte durch mehrere Faktoren bestimmt werden, wie etwa die Länge des Halses des Hirsches, seine körperliche Stärke, sein Sehvermögen usw. Hier berücksichtigen wir jedoch nur die Länge des Halses. Je länger der Hals, desto höher die Fitness.

(Dieser Artikel geht davon aus, dass Gene Merkmale bestimmen, die wiederum die Überlebensfähigkeit bestimmen.)

Es war einmal eine Gruppe gewöhnlicher Hirsche. Jeder Hirsch hatte andere Gene und daher andere Merkmale (mit den Merkmalen ist hier insbesondere die Länge des Halses gemeint). Diese Hirschgeneration wurde als „Hirschherde 0“ erfasst.

In der „Hirschherde 0“ können Individuen mit langem Hals mehr Blätter fressen und haben eine höhere Überlebenschance, sie verfügen also über eine hohe Fitness. Individuen mit kurzem Hals werden eher ausgeschieden und weisen eine geringe Fitness auf. Dieser Vorgang wird Selektion genannt und nur die Hirsche, die die Selektion überleben, sind paarungsfähig.

(Fotoquelle: Wang Moyi, ein Seelenmaler)

Wenn sich ein männlicher Hirsch mit einem weiblichen Hirsch paart, kopiert er nicht einfach seine eigenen Gene, sondern kreuzt und kombiniert vielmehr deren Gene mit denen des weiblichen Hirsches (Gene werden hier als gleichwertig mit Chromosomen angesehen). Beispiel: „Aa BbCc“ + „aa bbcc“ = „Aa bbcc“ + „aa BbCc“.

Natürlich können bei der Kombination zweier Gene ein oder mehrere Nukleotide der Gene mutieren . Beispielsweise mutiert ein Gen b zu B.

Genetische Kreuzung

Genetische Variation

Auf diese Weise brachte „Deer Herd 0“ eine neue Generation hervor, die als „Deer Herd 1“ registriert wurde. Im Allgemeinen werden nach dem Auswahlprozess die maximalen und durchschnittlichen Fitnesswerte der „Hirschherde 1“ zunehmen, d. h. die maximalen und durchschnittlichen Werte der Halslänge werden zunehmen.

Nach Generationen der Fortpflanzung werden die Hälse der „Hirschherde N“ aufgrund genetischer Veränderungen deutlich länger sein als die der „Hirschherde 0“ und ihre Fitness wird höher sein. An diesem Punkt können wir sagen, dass sich die Art weiterentwickelt hat.

Die Bevölkerung tendiert dazu, optimal zu sein

Natürlich hängt die optimale Halslänge auch von den Umgebungsbedingungen, insbesondere der Höhe der Baumkrone, ab. Ein Hals, der höher liegt als die Baumkronen, hat mehr Nachteile als Vorteile. Solange sich die Umgebung nicht wesentlich ändert, werden sich nach der „Hirschherde N“ die Gene der Population nicht wesentlich ändern und die Fitness wird sich nicht wesentlich ändern und die Population wird sich bei der optimalen Lösung stabilisieren.

Wie funktioniert ein genetischer Algorithmus?

John Holland aus den USA simulierte die natürliche Selektion und die genetischen Mechanismen von Darwins Theorie der biologischen Evolution und schlug einen heuristischen Optimierungsalgorithmus vor – den genetischen Algorithmus .

Der Algorithmus wandelt unabhängige Variablen in Individuen um, ordnet Individuen durch Kodierung Genen zu, verwendet die zu lösende Zielfunktion als Fitnessfunktion, behält Crossover und Mutation bei und nach mehreren Iterationen kann sich die Population (mehrere Individuen) der optimalen Lösung annähern.

Am Beispiel des Maximalwerts der Zielfunktion F(x)=x+8sin(5x)+5cos(4x) löst der genetische Algorithmus das Problem in sechs Schritten:

1. Initialisierung

Der genetische Algorithmus betrachtet die möglichen Werte der unabhängigen Variablen als Individuen und generiert nach Festlegung der Gesamtpopulation eine initialisierte Population. Angenommen, die Population umfasst 100 Individuen und es werden 100 Anfangswerte zufällig im Intervall [0,8] ausgewählt.

Erzeugen Sie zufällig die Anfangspopulation innerhalb eines bestimmten Intervalls der unabhängigen Variable

2. Kodierung und Dekodierung

Die unabhängige Variable Individuum selbst kann nicht als Gen betrachtet werden und muss in irgendeiner Weise transformiert werden. Normalerweise wird das Individuum in eine Folge von Binärzahlen umgewandelt, die als Kodierung bezeichnet wird, und diese Folge von Binärzahlen kann als Gen betrachtet werden.

Wenn beispielsweise 4 Binärbits zur Darstellung des ganzzahligen Teils und 2 Binärbits zur Darstellung des Dezimalteils verwendet werden, kann 3,25 als „001101“ dargestellt werden und „001101“ ist das Gen des Individuums.

Die binäre Darstellung der 3,25 des Individuums ist 001101, was eine Simulation des Gens ist.

Der Zweck der Kodierung besteht darin, Gene zu simulieren, um anschließende Kreuzungen und Mutationen durchzuführen. Dekodierung ist der Prozess der Umwandlung von Genen (binär) in Individuen (dezimal). Zur Berechnung der Fitness können Dezimalzahlen in die Fitnessfunktion eingesetzt werden.

3. Fitnessberechnung

Nach der Umwandlung des Gens (binär) in Individuen (dezimal) kann die Fitness jedoch durch Einsetzen der Dezimalindividuen in die Zielfunktion ermittelt werden.

Es ist nicht schwer zu verstehen, dass die Fitnessfunktion oft die zu lösende Zielfunktion F(x)=x+8sin(5x)+5cos(4x) ist.

4. Wählen Sie

Jedes Individuum wird entsprechend seiner Fitness ausgewählt. Diejenigen mit besserer Fitness werden eher behalten, während diejenigen mit weniger Fitness eher ausscheiden. Dieser Prozess wird üblicherweise mit dem „Roulette“-Modell durchgeführt.

Selbstverständlich müssen wir bei der Auswahl darauf achten, dass die Anzahl der Personen unverändert bleibt. Um dies zu gewährleisten, werden diejenigen mit hoher Fitness nicht nur behalten, sondern auch kopiert.

Personen mit besserer Fitness haben eine höhere Überlebenschance

5. Crossover und Mutation

Die verbleibenden Individuen werden nach der Kodierung ihrer Gene gekreuzt. Beispiel: „001 101“ + „010 010“ = „001 010“ + „010 101“. Im Allgemeinen werden die Schnittpunkte zufällig gewählt.

Dabei kreuzen sich zwei Gene und es entstehen zwei neue Gene (das entspricht der Geburt von Zwillingen bei den Eltern). Daher ändert sich durch Crossover die Populationsgröße nicht.

Nach dem Crossover kann jedes Gen auch mutieren. Generell sind auch die Mutationspunkte zufällig. Beispielsweise wird eine 1 in einem bestimmten Bit in eine 0 geändert oder eine 0 in eine 1.

Binärzahlenkreuz

Variation von Binärzahlen

Nach der Selektion werden sowohl die Maximal- als auch die Durchschnittswerte der Populationsfitness im Vergleich zur vorherigen Generation verbessert. Insbesondere konzentrieren sich alle Personen auf den höchsten Punkt der Zielfunktion. Nach vielen Iterationen konzentriert es sich auf den Maximalwert.

6. Ist es vorbei?

Da es sich um einen Optimierungsalgorithmus handelt, muss eine Endbedingung festgelegt werden, und der Algorithmus darf nicht endlos in einer Schleife laufen (tote Schleife). Am einfachsten ist es, die Anzahl der Durchläufe des Algorithmus festzulegen. Lassen Sie den Algorithmus beispielsweise 50 Mal durchlaufen und dann beenden.

Hier ist ein allgemeines Flussdiagramm des genetischen Algorithmus

Im Laufe der Evolution, also während der Zyklen des Algorithmus, steigt die durchschnittliche Fitness der Population zwangsläufig von Generation zu Generation an und konvergiert schließlich zu einem Maximalwert, der den Maximalpunkt der gesuchten Zielfunktion darstellt.

Populationsverteilung nach 50 Zyklen des genetischen Algorithmus: konzentriert auf einen Punkt

Während der Algorithmus iteriert, verbessert sich auch die durchschnittliche Fitness der Bevölkerung.

Bei jedem Schritt gibt es kleine Strategien

Um die Effizienz des genetischen Algorithmus zu verbessern, gibt es in den obigen Schritten tatsächlich einige Tricks.

1. Initialisierung

Wenn Vorabinformationen über den Maximalpunkt vorliegen, d. h. der ungefähre Bereich, in dem sich der Maximalpunkt befindet. Innerhalb dieses Bereichs kann die Ausgangspopulation generiert werden. Wenn nicht, muss es in einem größeren Bereich zufällig generiert werden.

Die Wahl des Anfangswerts beeinflusst die Konvergenzgeschwindigkeit des Algorithmus. Je näher der Anfangswert an der optimalen Lösung liegt, desto schneller ist die Konvergenzgeschwindigkeit. Darüber hinaus können ungeeignete Anfangswerte dazu führen, dass der Algorithmus in ein lokales Optimum fällt.

Können wir schneller die optimale Lösung finden?

2. Kodierung und Dekodierung

Bei der digitalen Signalverarbeitung müssen Messungen Minimal- und Maximalwerte aufweisen, d. h. der Wert der Variablen ist nicht kontinuierlich und unendlich, sondern diskontinuierlich und endlich. Der durch die Messung verursachte Fehler wird als Quantisierungsfehler bezeichnet.

Wenn wir beispielsweise 4 Binärbits zur Darstellung des ganzzahligen Teils und 2 Binärbits zur Darstellung des Dezimalteils verwenden, kann der Maximalwert der unabhängigen Variablen nur 15,75 betragen (entsprechend 111111 im Binärformat), und der Dezimalteil kann nur einen Unterschied von 0,25 erkennen. Der Mindestwert der Messung wird auch als Auflösungsverhältnis bezeichnet.

Die optimale Lösung von F(x)=x+8sin(5x)+5cos(4x) liegt bei 7,860, aber der Algorithmus kann nur gegen 7,875 konvergieren.

Natürlich können wir die Länge des Gens sehr groß machen, indem wir beispielsweise 100 Binärbits zur Darstellung des ganzzahligen Teils und 10 Binärbits zur Darstellung des Dezimalteils verwenden, um den Bereich der unabhängigen Variablenwerte zu erweitern und die Auflösung zu verbessern. Dies erhöht jedoch die Rechenkomplexität und die Speichergröße des Algorithmus.

3. Wählen Sie

Wenn im Auswahlprozess die Individuen mit der höchsten Fitness beibehalten und repliziert werden, spricht man von Elitereservierung . Wenn die Individuen mit der höchsten Fitness nicht unbedingt zurückgehalten werden und dennoch eliminiert werden können, spricht man von keiner Elite-Reservierung.

Experimente zeigen, dass der genetische Algorithmus mit Elite-Retention schneller zum optimalen Wert konvergiert und stabiler ist.

4. Crossover und Mutation

Crossover kann in Einzelpunkt-Crossover und Mehrpunkt-Crossover unterteilt werden, und Mutationen können ebenfalls in Einzelpunktmutationen und Mehrpunktmutationen unterteilt werden. Crossover und Mutation werden verwendet, um die genetische Vielfalt zu erhöhen, die Konvergenz zu beschleunigen und der lokalen Optimalität zu entkommen.

Wenn beispielsweise alle Individuen in der Nähe des lokalen Optimums konzentriert sind, dann mutiert plötzlich ein Individuum und „springt“ in die Nähe des globalen Optimums, und die Population kann sich weiterentwickeln.

Für eine Population ist Stabilität wichtiger als Vielfalt, daher können Kreuzungen und Mutationen oft an einem einzigen Punkt durchgeführt werden und die Wahrscheinlichkeit einer Mutation ist oft sehr gering.

5. Ist es vorbei?

Obwohl es einfach ist, das Ende des Algorithmus durch Festlegen der Anzahl der Algorithmusläufe zu steuern, gibt es zwei Probleme:

(1) Konvergiert der Algorithmus langsam, wenn beispielsweise die Population nach 50 Iterationen nicht zu einer optimalen Lösung konvergiert, dann ist das Ergebnis zwangsläufig falsch;

(2) Wenn der Algorithmus schnell konvergiert, beispielsweise wenn die Population nur 20 Iterationen benötigt, um zu einer optimalen Lösung zu konvergieren, werden viele Rechenressourcen verschwendet.

Eine andere, zuverlässigere Methode besteht darin, den Unterschied in der durchschnittlichen Fitness der Population zwischen zwei benachbarten Operationen zu bestimmen, d. h., ob dieser unter einem bestimmten Schwellenwert liegt. Wenn ja, gilt der Algorithmus als konvergiert und kann beendet werden. Wenn nicht, wird davon ausgegangen, dass der Algorithmus nicht konvergiert ist und der Zyklus sollte fortgesetzt werden.

Die Steuerung der Beendigung des Algorithmus basierend auf dem durchschnittlichen Fitnessunterschied ist zuverlässiger

Genetische Algorithmen können nicht nur Bilder zeichnen, sondern Ihnen auch sagen,

Heuristische Algorithmen wie genetische Algorithmen verfügen zwar nicht über extrem strenge mathematische Ableitungen, doch die Natur hat diese Gesetze zur Lösung zahlloser Probleme genutzt. Heutzutage werden genetische Algorithmen in vielen Bereichen unseres Lebens eingesetzt, beispielsweise bei der Gestaltung der Form von Fahrzeugen, um den Luftwiderstand zu verringern. wie der Arbeitsablauf von Robotern gestaltet werden kann, um die Arbeitseffizienz zu verbessern; So planen Sie Routen, um die Entfernung bei Expresslieferungen zu minimieren …

Zuvor hat jemand ein Projekt auf GitHub hochgeladen, bei dem genetische Algorithmen zum Zeichnen bestimmter Bilder verwendet wurden. Nachfolgend sehen Sie ein Simulationsbeispiel, um zu sehen, wie der genetische Algorithmus anhand des obigen Fotos das folgende Werk „zeichnet“:

(Bildquelle: https://github.com/anopara/genetic-drawing)

Zunächst werden mehrere anfängliche Farbbalken angegeben, um ein Farbbalkenbild zu bilden, und der Unterschied zwischen dem Farbbalkenbild und dem Originalbild wird als Zielfunktion verwendet. Anschließend wird mithilfe eines genetischen Algorithmus die Anordnung der Farbbalken iterativ gelöst, sodass die Zielfunktion minimiert wird, d. h. das Farbbalkenbild dem Originalbild „am ähnlichsten“ ist, wodurch das Ziel erreicht wird, das Originalbild mit mehreren Farbbalken zu „zeichnen“.

PS: Wenn Sie kein Programmierer sind, müssen Sie genetische Algorithmen vorerst nicht verwenden, Sie können jedoch dennoch einige Erkenntnisse aus genetischen Algorithmen gewinnen:

●Es gibt keinen perfekten Algorithmus. Um die Genauigkeit zu gewährleisten, muss der Rechenaufwand erhöht werden. Bei allen Strategien handelt es sich um die Kunst, ein Gleichgewicht zwischen mehreren Faktoren zu finden.

●Wenn Sie nur nach Stabilität streben, werden Sie keine Fortschritte machen können. wer nur auf Vielfalt setzt, wird keine Vorteile erzielen können. Daher müssen wir ein Gleichgewicht zwischen Stabilität und Vielfalt finden. Auf lange Sicht ist jedoch Stabilität (Akkumulation, Vererbung) oft wichtiger als Vielfalt.

●Es ist wichtig, die Elite zu behalten, aber wir dürfen niemals auf gewöhnliche Menschen außerhalb der Elite herabsehen. Ohne gewöhnliche Individuen gäbe es keinen Nährboden für Mutationen und die Population würde eintönig werden. Und Monotonie bedeutet oft Zerbrechlichkeit.

Quellen:

[1] Zheng Shuquan. Technologie und Anwendung industrieller Intelligenz[M]. Shanghai: Shanghaier Wissenschafts- und Technologieverlag.

[2] Li Deyi, Yu Jian. Einführung in die künstliche Intelligenz, China Association for Science and Technology, Reihe „Informationstechnologie der neuen Generation“ [M]. Peking: China Science and Technology Press.

Autor: Wang Moyi

Einheit des Autors: School of Navigation, Northwestern Polytechnical University

Dieser Artikel stammt vom öffentlichen Konto „Science Academy“. Bitte geben Sie beim Nachdruck die Quelle des öffentlichen Kontos an.