AI z Pythonem - algorytmy genetyczne

W tym rozdziale szczegółowo omówiono algorytmy genetyczne sztucznej inteligencji.

Co to są algorytmy genetyczne?

Algorytmy genetyczne (GA) to algorytmy oparte na wyszukiwaniu, oparte na pojęciach doboru naturalnego i genetyki. GA są podzbiorem znacznie większej gałęzi obliczeń znanej jako obliczenia ewolucyjne.

GA zostały opracowane przez Johna Hollanda oraz jego studentów i kolegów z University of Michigan, w szczególności Davida E. Goldberga. Od tego czasu został wypróbowany w różnych problemach optymalizacyjnych z dużym powodzeniem.

W GA mamy pulę możliwych rozwiązań danego problemu. Roztwory te następnie ulegają rekombinacji i mutacji (podobnie jak w genetyce naturalnej), rodzą nowe dzieci, a proces powtarza się przez różne pokolenia. Każdej osobie (lub proponowanemu rozwiązaniu) przypisywana jest wartość przystosowania (w oparciu o jej wartość funkcji celu), a sprawniejsze osobniki mają większą szansę na kojarzenie się i plonfitterosoby. Jest to zgodne z darwinowską teoriąSurvival of the Fittest.

Tak więc zachowuje evolving lepsze jednostki lub rozwiązania na przestrzeni pokoleń, aż osiągną kryterium zatrzymania.

Algorytmy genetyczne mają wystarczająco losowy charakter, ale działają znacznie lepiej niż losowe wyszukiwanie lokalne (gdzie po prostu próbujemy losowych rozwiązań, śledząc najlepsze do tej pory), ponieważ wykorzystują również informacje historyczne.

Jak używać Google Analytics do rozwiązywania problemów z optymalizacją?

Optymalizacja to działanie mające na celu uczynienie projektu, sytuacji, zasobów i systemu tak efektywnymi, jak to tylko możliwe. Poniższy schemat blokowy przedstawia proces optymalizacji -

Etapy mechanizmu GA w procesie optymalizacji

Poniżej znajduje się sekwencja kroków mechanizmu GA wykorzystywanego do optymalizacji problemów.

  • Krok 1 - Losowe wygenerowanie populacji początkowej.

  • Krok 2 - Wybierz początkowe rozwiązanie z najlepszymi wartościami sprawności.

  • Krok 3 - Ponownie połącz wybrane rozwiązania za pomocą operatorów mutacji i krzyżowania.

  • Krok 4 - Wstaw potomstwo do populacji.

  • Krok 5 - Teraz, jeśli warunek zatrzymania zostanie spełniony, zwróć rozwiązanie z najlepszą wartością dopasowania. W przeciwnym razie przejdź do kroku 2.

Instalowanie niezbędnych pakietów

Aby rozwiązać problem za pomocą algorytmów genetycznych w Pythonie, użyjemy potężnego pakietu dla GA o nazwie DEAP. Jest to biblioteka nowatorskich ewolucyjnych ram obliczeniowych do szybkiego prototypowania i testowania pomysłów. Możemy zainstalować ten pakiet za pomocą następującego polecenia w wierszu polecenia -

pip install deap

Jeśli używasz anaconda środowisko, można użyć następującego polecenia, aby zainstalować deap -

conda install -c conda-forge deap

Wdrażanie rozwiązań wykorzystujących algorytmy genetyczne

Ta sekcja wyjaśnia wdrażanie rozwiązań wykorzystujących algorytmy genetyczne.

Generowanie wzorów bitowych

Poniższy przykład pokazuje, jak wygenerować ciąg bitów, który zawierałby 15 jedynek, na podstawie One Max problem.

Zaimportuj niezbędne pakiety, jak pokazano -

import random
from deap import base, creator, tools

Zdefiniuj funkcję oceny. To pierwszy krok do stworzenia algorytmu genetycznego.

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

Teraz utwórz zestaw narzędzi z odpowiednimi parametrami -

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

Zainicjuj przybornik

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)

Zarejestruj operatora oceny -

toolbox.register("evaluate", eval_func)

Teraz zarejestruj operator zwrotnicy -

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

Zarejestruj operator mutacji -

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

Zdefiniuj operatora hodowli -

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')

Oceń całą populację -

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

Twórz i powtarzaj przez pokolenia -

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

Wybór osób następnego pokolenia -

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

Teraz sklonuj wybrane osoby -

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

Zastosuj krzyżowanie i mutację u potomstwa -

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

Usuń wartość sprawności dziecka

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

Teraz zastosuj mutację -

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

Oceń osoby z niepełnosprawnością -

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')

Teraz zastąp populację osobnikiem nowego pokolenia -

population[:] = offspring

Wydrukuj statystyki dla obecnych pokoleń -

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")

Wydrukuj wynik końcowy -

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 regresji symboli

Jest to jeden z najbardziej znanych problemów w programowaniu genetycznym. Wszystkie problemy związane z regresją symboliczną używają dowolnego rozkładu danych i próbują dopasować najdokładniejsze dane do wzoru symbolicznego. Zwykle miara taka jak RMSE (Root Mean Square Error) jest używana do pomiaru sprawności danej osoby. Jest to klasyczny problem regresorowy i tutaj używamy równania5x3-6x2+8x=1. Musimy wykonać wszystkie kroki opisane w powyższym przykładzie, ale główna część polegałaby na utworzeniu zestawów prymitywnych, ponieważ są one elementami budulcowymi dla jednostek, aby można było rozpocząć ocenę. Tutaj będziemy używać klasycznego zestawu prymitywów.

Poniższy kod Pythona wyjaśnia to szczegółowo -

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)

Zwróć uwagę, że wszystkie podstawowe kroki są takie same, jak podczas generowania wzorów bitowych. Ten program da nam wynik jako min, max, std (odchylenie standardowe) po 10 liczbie pokoleń.