[PYTHON] Trouvez la valeur optimale de la fonction à l'aide d'un algorithme génétique (partie 1)

Qu'est-ce qu'un algorithme d'évolution?

L'algorithme évolutif (EA) est l'un des algorithmes d'optimisation et est une méthode d'optimisation qui incorpore la sélection naturelle, la recombinaison génique, la mutation, etc. comme modèle.

Les algorithmes évolutifs sont approximativement divisés en quatre types suivants. --Algorithme génétique

• Programmation génétique --Stratégie évolutive
• Programmation évolutive

Cette fois, nous traiterons de l'algorithme génétique (GA).

Bibliothèque utilisée

Utilisez la bibliothèque Python suivante appelée DEAP. https://deap.readthedocs.io/en/master/

code

Fonction objective

Recherchez la valeur minimale de Bird Bunction indiquée ci-dessous. $f(x, y) = sin(x)e^{(1-cos(y))^2}+cos(y)e^{(1-sin(x))^2}+(x-y)^2$ La fonction Bird est une fonction multimodale avec une solution globale optimale-106.764537 en (x, y) = (4.70104, 3.15294), (-1.58214, -3.13024) et de nombreuses solutions locales autour d'elle.

sample_GA.py

import numpy as np
def bird(x):
    x1 = x[0]
    x2 = x[1]
    t = np.sin(x1)*np.exp((1-np.cos(x2))**2) + np.cos(x2)*np.exp((1-np.sin(x1))**2) + (x1-x2)**2 
    return t,

#dessin
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
c1 = c2 = np.arange(-10, 10, 0.1)
xx, yy = np.meshgrid(c1, c2)
len=np.size(c1)  
z=np.empty((len, len))
for i in range(len):
    for j in range(len):
        xin=np.array([xx[i,j], yy[i,j]])
        z[i,j], = bird(xin)
fig0 = plt.figure(figsize=(12,12), dpi=80).add_subplot(111, projection='3d')
fig0.plot_surface(xx, yy, z, alpha=1)
plt.xlim(10, -10)            
plt.ylim(-10, 10)

Importer la bibliothèque

Importez les bibliothèques requises. Puisque DEAP utilise une bibliothèque aléatoire, les résultats changent à chaque essai. Pour éviter cela, utilisez random.seed (1).

sample_GA.py

import pandas as pd
import random
from deap import algorithms
from deap import base,creator,tools
# random.seed(1)

Génération de population précoce

Créez une fonction pour générer un individu initial. Ici, les individus initiaux ont été générés dans un modèle de grille 10 × 10 dans la plage de -10 à 10 pour x et y.

sample_GA.py

def initPopulation(pcls, ind_init):
    x = np.linspace(-10, 10, 10)
    y = np.linspace(-10, 10, 10)
    inix, iniy = np.meshgrid(x,y)
    contents = np.concatenate([inix.reshape([-1,1]), iniy.reshape([-1,1])], axis=1)
    pcls = [ind_init(c) for c in contents]
    return pcls

Inscrivez-vous dans la boîte à outils

Enregistrez des méthodes telles que l'évaluation ("évaluer"), la population ("population"), le croisement ("mate"), la mutation ("muter") et la sélection ("sélectionner") dans la boîte à outils.

Par exemple, le suivant toolbox.register ("mate", tools.cxBlend, alpha = 0.2) ` Cela signifie qu'une fonction appelée tool.cxblend est enregistrée en tant que méthode de croisement (alpha = 0.2 est un argument de tools.cxBlend).

Le croisement par mélange comme méthode de croisement, la mutation gaussienne comme mutation et le format de sélection seront menés dans un tournoi de 10 individus. Si vous souhaitez spécifier la population initiale, enregistrez-la dans "population_guess".

sample_GA.py

creator.create("FitnessMax", base.Fitness, weights=(-1.0,))
creator.create("Individual", np.ndarray, fitness=creator.FitnessMax)

toolbox = base.Toolbox()
toolbox.register("evaluate", bird)
toolbox.register("population_guess", initPopulation, list, creator.Individual)
toolbox.register("mate", tools.cxBlend, alpha=0.2)
toolbox.register("mutate", tools.mutGaussian, mu=[0.0, 0.0], sigma=[2.0, 2.0], indpb=1)
toolbox.register("select", tools.selTournament, tournsize=10)

Courir

Si vous avez configuré jusqu'à présent, le reste fonctionnera avec des commandes simples.

Dans l'exemple ci-dessous, le nombre d'individus évalués, la valeur moyenne, l'écart type, la valeur maximale et la valeur minimale de chaque génération sont enregistrés dans le `` journal de bord ''. hofEst une abréviation pour holl of fame, et vous pouvez enregistrer le nombre spécifié dans l'ordre décroissant d'évaluation.

L'argument cxpb de algorithms.eaSimple indique le taux de croisement, mutpb indique le taux de mutation et ngen indique le nombre de générations. Le nombre d'individus par génération sera de 10 × 10 = 100 individus, héritant de celui défini par `` pop ''. Il est également possible de spécifier séparément l'échantillonnage initial et le nombre d'individus au moment du changement de génération.

sample_GA.py

#Générer une population précoce
pop = toolbox.population_guess()

#Réglage
hof = tools.HallOfFame(5, similar=np.array_equal)
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("avg", np.mean)
stats.register("std", np.std)
stats.register("min", np.min)
stats.register("max", np.max)

#Courir
pop, logbook= algorithms.eaSimple(pop, toolbox,
                        cxpb=0.9, mutpb=0.1, ngen=20,
                        stats=stats, halloffame=hof, verbose=True)

#Afficher les 3 meilleurs individus
print("holl of fame.1 : %s" % (hof[0]))
print("holl of fame.2 : %s" % (hof[1]))
print("holl of fame.3 : %s" % (hof[2]))

terminal

gen	nevals	avg    	std    	min     	max   
0  	100   	80.0665	99.3005	-83.8352	414.98
1  	74    	7.49092	62.2371	-103.255	301.724
2  	89    	11.499 	108.449	-105.693	665.594
3  	84    	-60.283	53.2721	-106.71 	161.645
4  	87    	-95.3896	32.299 	-106.723	40.9594
5  	75    	-99.3516	28.4967	-106.758	23.0967
6  	73    	-104.068	15.7185	-106.764	4.33984
7  	76    	-103.476	18.6955	-106.764	10.0824
8  	80    	-101.665	22.5172	-106.764	16.8155
9  	92    	-102.631	20.6472	-106.764	26.921 
10 	77    	-102.882	19.2791	-106.764	6.34586
11 	90    	-99.4555	30.4939	-106.764	56.3788
12 	89    	-100.566	27.1489	-106.764	30.2934
13 	79    	-100.978	25.2596	-106.764	51.745 
14 	78    	-98.4071	32.1796	-106.764	85.5625
15 	76    	-105.728	10.3096	-106.764	-3.14868
16 	89    	-95.2292	38.3427	-106.764	80.6272 
17 	91    	-102.44 	25.6436	-106.764	96.6545 
18 	80    	-105.432	11.2501	-106.764	4.33866 
19 	83    	-102.271	23.504 	-106.764	67.6912 
20 	79    	-103.856	16.5553	-106.764	-3.86946
holl of fame.1 : [4.70021671 3.1529326 ]
holl of fame.2 : [4.70021671 3.15293287]
holl of fame.3 : [4.70021671 3.15293358]

Solution globale optimale - Convergence autour de 106.765. Puisque l'algorithme n'utilise pas les informations différentielles de chaque individu, une erreur minime se produira.

Résumé et impressions

• L'optimisation des fonctions a été réalisée avec l'algorithme génétique DEAP. -Puisqu'il utilise des nombres aléatoires, il est douteux qu'il converge à chaque essai
• Est-ce pour l'optimisation multivariée avec des valeurs discrètes?