AI con Python - Algoritmi genetici

Questo capitolo discute in dettaglio gli algoritmi genetici dell'IA.

Cosa sono gli algoritmi genetici?

Gli algoritmi genetici (GA) sono algoritmi basati sulla ricerca basati sui concetti di selezione naturale e genetica. I GA sono un sottoinsieme di un ramo molto più ampio del calcolo noto come calcolo evolutivo.

Gli GA sono stati sviluppati da John Holland e dai suoi studenti e colleghi presso l'Università del Michigan, in particolare David E. Goldberg. Da allora è stato provato su vari problemi di ottimizzazione con un alto grado di successo.

In GA, abbiamo un pool di possibili soluzioni al problema dato. Queste soluzioni subiscono quindi ricombinazione e mutazione (come nella genetica naturale), producono nuovi bambini e il processo si ripete per varie generazioni. Ad ogni individuo (o soluzione candidata) viene assegnato un valore di fitness (in base al valore della sua funzione oggettiva) e agli individui più in forma viene data una maggiore possibilità di accoppiarsi e cederefitterindividui. Ciò è in linea con la teoria darwiniana diSurvival of the Fittest.

Quindi, mantiene evolving individui o soluzioni migliori nel corso delle generazioni, fino a raggiungere un criterio di arresto.

Gli algoritmi genetici sono di natura sufficientemente casuale, ma funzionano molto meglio della ricerca locale casuale (dove proviamo solo soluzioni casuali, tenendo traccia delle migliori finora), poiché sfruttano anche le informazioni storiche.

Come utilizzare GA per problemi di ottimizzazione?

L'ottimizzazione è un'azione volta a rendere il design, la situazione, le risorse e il sistema il più efficaci possibile. Il seguente diagramma a blocchi mostra il processo di ottimizzazione:

Fasi del meccanismo GA per il processo di ottimizzazione

Di seguito è riportata una sequenza di passaggi del meccanismo GA quando viene utilizzato per l'ottimizzazione dei problemi.

Passaggio 1: genera la popolazione iniziale in modo casuale.
Passaggio 2: selezionare la soluzione iniziale con i migliori valori di fitness.
Passaggio 3: ricombinare le soluzioni selezionate utilizzando operatori di mutazione e crossover.
Passaggio 4: inserire una prole nella popolazione.
Passaggio 5: ora, se la condizione di arresto è soddisfatta, restituire la soluzione con il miglior valore di fitness. Altrimenti vai al passaggio 2.

Installazione dei pacchetti necessari

Per risolvere il problema utilizzando gli algoritmi genetici in Python, utilizzeremo un potente pacchetto per GA chiamato DEAP. È una libreria di nuovi framework di calcolo evolutivo per la prototipazione rapida e la verifica delle idee. Possiamo installare questo pacchetto con l'aiuto del seguente comando sul prompt dei comandi:

pip install deap

Se stai usando anaconda ambiente, quindi il seguente comando può essere utilizzato per installare deap -

conda install -c conda-forge deap

Implementazione di soluzioni utilizzando algoritmi genetici

Questa sezione spiega l'implementazione di soluzioni che utilizzano algoritmi genetici.

Generazione di schemi di bit

L'esempio seguente mostra come generare una stringa di bit che conterrebbe 15 unità, in base a One Max problema.

Importa i pacchetti necessari come mostrato -

import random
from deap import base, creator, tools

Definisci la funzione di valutazione. È il primo passo per creare un algoritmo genetico.

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

Ora, crea la cassetta degli attrezzi con i parametri giusti -

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

Inizializza la casella degli strumenti

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)

Registra l'operatore di valutazione -

toolbox.register("evaluate", eval_func)

Ora registra l'operatore di crossover -

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

Registra un operatore di mutazione -

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

Definisci l'operatore per l'allevamento -

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

Valuta l'intera popolazione -

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

Crea e itera attraverso le generazioni -

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

Selezione di individui di nuova generazione -

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

Ora, clona gli individui selezionati -

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

Applica crossover e mutazione sulla prole -

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

Elimina il valore di fitness del bambino

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

Ora, applica la mutazione -

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

Valuta le persone con una forma fisica non valida -

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

Ora sostituisci la popolazione con individui di nuova generazione -

population[:] = offspring

Stampa le statistiche per le generazioni attuali -

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

Stampa l'output finale -

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

Problema di regressione dei simboli

È uno dei problemi più noti nella programmazione genetica. Tutti i problemi di regressione simbolica utilizzano una distribuzione di dati arbitraria e cercano di adattare i dati più accurati con una formula simbolica. Di solito, una misura come RMSE (Root Mean Square Error) viene utilizzata per misurare la forma fisica di un individuo. È un classico problema del regressore e qui stiamo usando l'equazione5x³-6x²+8x=1. Dobbiamo seguire tutti i passaggi come nell'esempio precedente, ma la parte principale sarebbe creare i set primitivi perché sono i mattoni per gli individui in modo che la valutazione possa iniziare. Qui useremo il classico set di primitive.

Il seguente codice Python lo spiega in dettaglio:

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)

Si noti che tutti i passaggi di base sono gli stessi utilizzati durante la generazione di schemi di bit. Questo programma ci darà l'output come min, max, std (deviazione standard) dopo 10 generazioni.

↰ Previous page Next page ↱