[PYTHON] Finding the optimum value of a function using a genetic algorithm (Part 1)

What is an evolutionary algorithm?

The evolutionary algorithm (EA) is one of the optimization algorithms, and is an optimization method that incorporates natural selection, gene recombination, mutation, etc. as a model.

Evolutionary algorithms are roughly divided into the following four types. --Genetic algorithm --Genetic programming --Evolution strategy --Evolutionary programming

This time, we will deal with the genetic algorithm (GA).

Library used

Use the following python library called DEAP. https://deap.readthedocs.io/en/master/

code

Objective function

Search for the minimum value of Bird Bunction shown below. $f(x, y) = sin(x)e^{(1-cos(y))^2}+cos(y)e^{(1-sin(x))^2}+(x-y)^2$ The Bird Function is a multimodal function with a global optimal solution-106.764537 at (x, y) = (4.70104, 3.15294), (-1.58214, -3.13024) and many local solutions around it.

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,

#drawing
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)

Figure 2020-08-11 151135.png

Library import

Import the required libraries. Since DEAP uses the random library, the results change with each trial. To avoid this, use 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)

Early population generation

Create a function to generate an initial individual. Here, initial individuals were generated in a 10 × 10 grid pattern in the range of -10 to 10 for both x and 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

Register in toolbox

Methods such as evaluation ("evaluate"), population ("population"), crossover ("mate"), mutation ("mutate"), and selection ("select") are registered in the toolbox.

For example, the following ``` toolbox.register (" mate ", tools.cxBlend, alpha = 0.2)` `` It means that the function tool.cxblend is registered as a crossover method (alpha = 0.2 is an argument of tools.cxBlend).

Blend crossing as the crossing method, Gauss mutation as the mutation, and the selection format will be carried out in a tournament of 10 individuals. If you want to specify the initial population, register it in "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)

Run

If you set up so far, the rest will work with simple commands.

In the example below, the number of evaluated individuals, mean value, standard deviation, maximum value, and minimum value of each generation are recorded in the `` `logbook. hof```Is an abbreviation for holl of fame, and you can save the specified number in descending order of evaluation.

The argument cxpb of algorithms.eaSimple indicates the crossover rate, mutpb indicates the mutation rate, and ngen indicates the number of generations. The number of individuals per generation will be 10 × 10 = 100 individuals, inheriting the one defined by `` `pop```. It is also possible to specify the initial sampling and the number of individuals at the time of generation change separately.

sample_GA.py


#Generate an early population
pop = toolbox.population_guess()

#Setting
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)

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

#Show top 3 individuals
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]

Globally optimal solution-Converged around 106.765. Since the algorithm does not use the differential information of each individual, a minute error will occur.

Summary and impressions

--Function optimization was performed with the genetic algorithm DEAP. ――Since it uses random numbers, it is doubtful whether it will converge with each trial. -Is it for multivariable optimization with discrete values?

Recommended Posts

Finding the optimum value of a function using a genetic algorithm (Part 1)
Find the optimal value of a function with a genetic algorithm (Part 2)
Cut a part of the string using a Python slice
Finding a solution to the N-Queen problem with a genetic algorithm (2)
Finding a solution to the N-Queen problem with a genetic algorithm (1)
A memorandum of using Python's input function
How to fix the initial population with a genetic algorithm using DEAP
Find the minimum value of a function by particle swarm optimization (PSO)
Learning neural networks using the genetic algorithm (GA)
Get the caller of a function in Python
[Circuit x Python] How to find the transfer function of a circuit using Lcapy
Summarizing the commercial value of an EC site using the automatic summarization algorithm LexRank
Various methods to numerically create the inverse function of a certain function Part 1 Polynomial regression
The story of introducing a multi-factor authentication function using a one-time password into a Java application
# Function that returns the character code of a string
Drawing on Jupyter using the plot function of pandas
Explanation of the concept of regression analysis using Python Part 1
Notification of weather forecast (rain, etc.) by DM as a part of the function of bot
[Linux] [C / C ++] How to get the return address value of a function and the function name of the caller
The value of meta when specifying a function with no return value in Dask dataframe apply
Avoiding the pitfalls of using a Mac (for Linux users?)
Reuse the behavior of the @property method by using a descriptor [16/100]
I made a function to check the model of DCGAN
I made a dot picture of the image of Irasutoya. (part1)
I tried a little bit of the behavior of the zip function
A memo of writing a basic function in Python using recursion
Extract the value of dict or list as a string
The story of creating a database using the Google Analytics API
[python] Value of function object (?)
A memorandum of using eigen3
When incrementing the value of a key that does not exist
Understand the function of convolution using image processing as an example
Solving the nurse scheduling problem (shift optimization) with a genetic algorithm
I tried to get the index of the list using the enumerate function
A function that measures the processing time of a method in python
How to find the memory address of a Pandas dataframe value
Count the maximum concatenated part of a random graph with NetworkX
How to save only a part of a long video using OpenCV
[Python3] Define a decorator to measure the execution time of a function
Evaluate the performance of a simple regression model using LeaveOneOut cross-validation
Get and set the value of the dropdown menu using Python and Selenium
Create a function to get the contents of the database in Go
[Python] A simple function to find the center coordinates of a circle
[Kaggle] I made a collection of questions using the Titanic tutorial
A super introduction to Django by Python beginners! Part 3 I tried using the template file inheritance function
A super introduction to Django by Python beginners! Part 2 I tried using the convenient functions of the template
Find the definition of the value of errno
Check the return value using PEP 380
About the return value of pthread_mutex_init ()
Precautions when using the urllib.parse.quote function
Algorithm generation automation using genetic algorithms
About the return value of the histogram.
[Python] Make the function a lambda function
The story of writing a program
How to divide and process a data frame using the groupby function
Calculate the shortest route of a graph with Dijkstra's algorithm and Python
Latin learning for the purpose of writing a Latin sentence analysis program (Part 1)
Various methods to numerically create the inverse function of a certain function Introduction
Try to solve the traveling salesman problem with a genetic algorithm (Theory)
How to create a wrapper that preserves the signature of the function to wrap
I tried to display the altitude value of DTM in a graph