KI mit Python - Genetische Algorithmen

In diesem Kapitel werden die genetischen Algorithmen der KI ausführlich beschrieben.

Was sind genetische Algorithmen?

Genetische Algorithmen (GAs) sind suchbasierte Algorithmen, die auf den Konzepten der natürlichen Selektion und Genetik basieren. GAs sind eine Teilmenge eines viel größeren Berechnungszweigs, der als evolutionäre Berechnung bekannt ist.

GAs wurden von John Holland und seinen Studenten und Kollegen an der University of Michigan entwickelt, insbesondere von David E. Goldberg. Seitdem wurden verschiedene Optimierungsprobleme mit hohem Erfolg ausprobiert.

In GAs haben wir einen Pool möglicher Lösungen für das gegebene Problem. Diese Lösungen werden dann rekombiniert und mutiert (wie in der natürlichen Genetik), bringen neue Kinder hervor und der Vorgang wird für verschiedene Generationen wiederholt. Jeder Person (oder Kandidatenlösung) wird ein Fitnesswert zugewiesen (basierend auf ihrem objektiven Funktionswert), und den fitteren Personen wird eine höhere Chance gegeben, sich zu paaren und nachzugebenfitterEinzelpersonen. Dies steht im Einklang mit der Darwinschen Theorie vonSurvival of the Fittest.

So bleibt es evolving bessere Individuen oder Lösungen über Generationen hinweg, bis ein Stoppkriterium erreicht ist.

Genetische Algorithmen sind von Natur aus ausreichend randomisiert, bieten jedoch eine viel bessere Leistung als die zufällige lokale Suche (bei der wir nur zufällige Lösungen ausprobieren und die bisher besten verfolgen), da sie auch historische Informationen nutzen.

Wie verwende ich GA für Optimierungsprobleme?

Bei der Optimierung werden Design, Situation, Ressource und System so effektiv wie möglich gestaltet. Das folgende Blockdiagramm zeigt den Optimierungsprozess -

Stufen des GA-Mechanismus für den Optimierungsprozess

Das Folgende ist eine Abfolge von Schritten des GA-Mechanismus, wenn er zur Optimierung von Problemen verwendet wird.

• Schritt 1 - Generieren Sie die anfängliche Population zufällig.

• Schritt 2 - Wählen Sie die ursprüngliche Lösung mit den besten Fitnesswerten.

• Schritt 3 - Kombinieren Sie die ausgewählten Lösungen mithilfe von Mutations- und Crossover-Operatoren neu.

• Schritt 4 - Fügen Sie einen Nachwuchs in die Population ein.

• Schritt 5 - Wenn die Stoppbedingung erfüllt ist, geben Sie die Lösung mit dem besten Fitnesswert zurück. Andernfalls fahren Sie mit Schritt 2 fort.

Erforderliche Pakete installieren

Um das Problem mithilfe genetischer Algorithmen in Python zu lösen, verwenden wir ein leistungsstarkes Paket für GA namens DEAP. Es ist eine Bibliothek neuartiger evolutionärer Berechnungsrahmen für das schnelle Prototyping und Testen von Ideen. Wir können dieses Paket mit Hilfe des folgenden Befehls an der Eingabeaufforderung installieren:

pip install deap

Wenn Sie verwenden anaconda Umgebung, dann kann der folgende Befehl verwendet werden, um deap zu installieren -

conda install -c conda-forge deap

Implementieren von Lösungen mithilfe genetischer Algorithmen

In diesem Abschnitt wird die Implementierung von Lösungen mithilfe genetischer Algorithmen erläutert.

Bitmuster erzeugen

Das folgende Beispiel zeigt Ihnen, wie Sie eine Bitfolge generieren, die 15 Einsen enthält, basierend auf der One Max Problem.

Importieren Sie die erforderlichen Pakete wie gezeigt -

import random
from deap import base, creator, tools

Definieren Sie die Auswertungsfunktion. Dies ist der erste Schritt zur Erstellung eines genetischen Algorithmus.

def eval_func(individual):
   target_sum = 15
   return len(individual) - abs(sum(individual) - target_sum),

Erstellen Sie nun die Toolbox mit den richtigen Parametern -

def create_toolbox(num_bits):
   creator.create("FitnessMax", base.Fitness, weights=(1.0,))
   creator.create("Individual", list, fitness=creator.FitnessMax)

Initialisieren Sie die Toolbox

toolbox = base.Toolbox()
toolbox.register("attr_bool", random.randint, 0, 1)
toolbox.register("individual", tools.initRepeat, creator.Individual,
   toolbox.attr_bool, num_bits)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

Registrieren Sie den Bewertungsbetreiber -

toolbox.register("evaluate", eval_func)

Registrieren Sie nun den Crossover-Operator -

toolbox.register("mate", tools.cxTwoPoint)

Registrieren Sie einen Mutationsoperator -

toolbox.register("mutate", tools.mutFlipBit, indpb = 0.05)

Definieren Sie den Operator für die Zucht -

toolbox.register("select", tools.selTournament, tournsize = 3)
return toolbox
if __name__ == "__main__":
   num_bits = 45
   toolbox = create_toolbox(num_bits)
   random.seed(7)
   population = toolbox.population(n = 500)
   probab_crossing, probab_mutating = 0.5, 0.2
   num_generations = 10
   print('\nEvolution process starts')

Bewerten Sie die gesamte Bevölkerung -

fitnesses = list(map(toolbox.evaluate, population))
for ind, fit in zip(population, fitnesses):
   ind.fitness.values = fit
print('\nEvaluated', len(population), 'individuals')

Erstellen und iterieren Sie über Generationen hinweg -

for g in range(num_generations):
   print("\n- Generation", g)

Auswahl der Personen der nächsten Generation -

offspring = toolbox.select(population, len(population))

Klonen Sie nun die ausgewählten Personen -

offspring = list(map(toolbox.clone, offspring))

Crossover und Mutation auf die Nachkommen anwenden -

for child1, child2 in zip(offspring[::2], offspring[1::2]):
   if random.random() < probab_crossing:
   toolbox.mate(child1, child2)

Löschen Sie den Fitnesswert des Kindes

del child1.fitness.values
del child2.fitness.values

Wenden Sie nun die Mutation an -

for mutant in offspring:
   if random.random() < probab_mutating:
   toolbox.mutate(mutant)
   del mutant.fitness.values

Bewerten Sie die Personen mit einer ungültigen Fitness -

invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
fitnesses = map(toolbox.evaluate, invalid_ind)
for ind, fit in zip(invalid_ind, fitnesses):
   ind.fitness.values = fit
print('Evaluated', len(invalid_ind), 'individuals')

Ersetzen Sie jetzt die Bevölkerung durch eine Person der nächsten Generation -

population[:] = offspring

Drucken Sie die Statistiken für die aktuellen Generationen aus -

fits = [ind.fitness.values[0] for ind in population]
length = len(population)
mean = sum(fits) / length
sum2 = sum(x*x for x in fits)
std = abs(sum2 / length - mean**2)**0.5
print('Min =', min(fits), ', Max =', max(fits))
print('Average =', round(mean, 2), ', Standard deviation =',
round(std, 2))
print("\n- Evolution ends")

Drucken Sie die endgültige Ausgabe -

best_ind = tools.selBest(population, 1)[0]
   print('\nBest individual:\n', best_ind)
   print('\nNumber of ones:', sum(best_ind))
Following would be the output:
Evolution process starts
Evaluated 500 individuals
- Generation 0
Evaluated 295 individuals
Min = 32.0 , Max = 45.0
Average = 40.29 , Standard deviation = 2.61
- Generation 1
Evaluated 292 individuals
Min = 34.0 , Max = 45.0
Average = 42.35 , Standard deviation = 1.91
- Generation 2
Evaluated 277 individuals
Min = 37.0 , Max = 45.0
Average = 43.39 , Standard deviation = 1.46
… … … …
- Generation 9
Evaluated 299 individuals
Min = 40.0 , Max = 45.0
Average = 44.12 , Standard deviation = 1.11
- Evolution ends
Best individual:
[0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 
 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0,
 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1]
Number of ones: 15

Problem der Symbolregression

Es ist eines der bekanntesten Probleme bei der genetischen Programmierung. Alle symbolischen Regressionsprobleme verwenden eine beliebige Datenverteilung und versuchen, die genauesten Daten mit einer symbolischen Formel abzugleichen. Normalerweise wird ein Maß wie der RMSE (Root Mean Square Error) verwendet, um die Fitness einer Person zu messen. Es ist ein klassisches Regressorproblem und hier verwenden wir die Gleichung5x³-6x²+8x=1. Wir müssen alle Schritte wie im obigen Beispiel befolgen, aber der Hauptteil wäre, die primitiven Mengen zu erstellen, da sie die Bausteine ​​für die Individuen sind, damit die Bewertung beginnen kann. Hier werden wir den klassischen Satz von Grundelementen verwenden.

Der folgende Python-Code erklärt dies ausführlich -

import operator
import math
import random
import numpy as np
from deap import algorithms, base, creator, tools, gp
def division_operator(numerator, denominator):
   if denominator == 0:
      return 1
   return numerator / denominator
def eval_func(individual, points):
   func = toolbox.compile(expr=individual)
   return math.fsum(mse) / len(points),
def create_toolbox():
   pset = gp.PrimitiveSet("MAIN", 1)
   pset.addPrimitive(operator.add, 2)
   pset.addPrimitive(operator.sub, 2)
   pset.addPrimitive(operator.mul, 2)
   pset.addPrimitive(division_operator, 2)
   pset.addPrimitive(operator.neg, 1)
   pset.addPrimitive(math.cos, 1)
   pset.addPrimitive(math.sin, 1)
   pset.addEphemeralConstant("rand101", lambda: random.randint(-1,1))
   pset.renameArguments(ARG0 = 'x')
   creator.create("FitnessMin", base.Fitness, weights = (-1.0,))
   creator.create("Individual",gp.PrimitiveTree,fitness=creator.FitnessMin)
   toolbox = base.Toolbox()
   toolbox.register("expr", gp.genHalfAndHalf, pset=pset, min_=1, max_=2)
   toolbox.expr)
   toolbox.register("population",tools.initRepeat,list, toolbox.individual)
   toolbox.register("compile", gp.compile, pset = pset)
   toolbox.register("evaluate", eval_func, points = [x/10. for x in range(-10,10)])
   toolbox.register("select", tools.selTournament, tournsize = 3)
   toolbox.register("mate", gp.cxOnePoint)
   toolbox.register("expr_mut", gp.genFull, min_=0, max_=2)
   toolbox.register("mutate", gp.mutUniform, expr = toolbox.expr_mut, pset = pset)
   toolbox.decorate("mate", gp.staticLimit(key = operator.attrgetter("height"), max_value = 17))
   toolbox.decorate("mutate", gp.staticLimit(key = operator.attrgetter("height"), max_value = 17))
   return toolbox
if __name__ == "__main__":
   random.seed(7)
   toolbox = create_toolbox()
   population = toolbox.population(n = 450)
   hall_of_fame = tools.HallOfFame(1)
   stats_fit = tools.Statistics(lambda x: x.fitness.values)
   stats_size = tools.Statistics(len)
   mstats = tools.MultiStatistics(fitness=stats_fit, size = stats_size)
   mstats.register("avg", np.mean)
   mstats.register("std", np.std)
   mstats.register("min", np.min)
   mstats.register("max", np.max)
   probab_crossover = 0.4
   probab_mutate = 0.2
   number_gen = 10
   population, log = algorithms.eaSimple(population, toolbox,
      probab_crossover, probab_mutate, number_gen,
      stats = mstats, halloffame = hall_of_fame, verbose = True)

Beachten Sie, dass alle grundlegenden Schritte dieselben sind wie beim Generieren von Bitmustern. Dieses Programm gibt uns die Ausgabe als min, max, std (Standardabweichung) nach 10 Generationen.