How do I find the minimum value of $x^2+y^2$ with a genetic algorithm?

I want to find $(x,y)$ which minimizes $x^2+y^2$ with GA to apply it for another function.

Does anyone know any example of GA with deap (Python) like that?

Genetic algorithm

This consists in 4 crucial steps: initialization, evaluation, selection and combination.

Initialization

Each individual in the population is encoded by some genes. In our case the genes represent our $[x, y]$ values. We will then set our search range to [0, 1000] for this specific problem. Usually you will know what is naturally possible based on your problem. For example, you should know the range of possible soil densities in nature. We will create 100 individuals in our population.

Evaluation of the fitness

This step simply asks you to put the $[x,y]$ values into your function and get its result. Pretty standard stuff.

Selection

There are many ways with which you can select parents. I will always keep the alpha male. The best individual in the population, he will be cloned to the next. Then I will use tournament selection. We will repeat the following until the next generation population is full. Pick four parents at random, take the best individual from the first two and the best from the last two. These will be the two parents which will gives us our next offspring.

Combination

From the two parents we will build the new genome for the child using the binary values of the $[x,y]$ values of the parents. The resulting binary value for each codon in the genome of the child is selected from the two parent genes by uniform random.

The code

class Genetic(object):

def __init__(self, f, pop_size = 100, n_variables = 2):
self.f = f
self.minim = -100
self.maxim = 100
self.pop_size = pop_size
self.n_variables = n_variables
self.population = self.initializePopulation()
self.evaluatePopulation()

def initializePopulation(self):
return [np.random.randint(self.minim, self.maxim, size=(self.n_variables))
for i in range(self.pop_size)]

def evaluatePopulation(self):
return [self.f(i[0], i[1]) for i in self.population]
#return [(i[0]-4)**2 + i[1]**2 for i in self.population]

def nextGen(self):
results = self.evaluatePopulation()
children = [self.population[np.argmin(results)]]

while len(children) < self.pop_size:
# Tournament selection
randA, randB = np.random.randint(0, self.pop_size), \
np.random.randint(0, self.pop_size)
if results[randA] < results[randB]: p1 = self.population[randA]
else: p1 = self.population[randB]

randA, randB = np.random.randint(0, self.pop_size), \
np.random.randint(0, self.pop_size)
if results[randA] < results[randB]: p2 = self.population[randA]
else: p2 = self.population[randB]

signs = []
for i in zip(p1, p2):
if i[0] < 0 and i[1] < 0: signs.append(-1)
elif i[0] >= 0 and i[1] >= 0: signs.append(1)
else: signs.append(np.random.choice([-1,1]))

# Convert values to binary
p1 = [format(abs(i), '010b') for i in p1]
p2 = [format(abs(i), '010b') for i in p2]

# Recombination
child = []
for i, j in zip(p1, p2):
for k, l in zip(i, j):
if k == l: child.append(k)
else: child.append(str(np.random.randint(min(k, l),
max(k,l))))

child = ''.join(child)
g1 = child[0:len(child)//2]
g2 = child[len(child)//2:len(child)]
children.append(np.asarray([signs[0]*int(g1, 2),
signs[1]*int(g2, 2)]))
self.population = children

def run(self):
ix = 0
while ix < 1000:
ix += 1
self.nextGen()
return self.population[0]


Then you can use the code by

f = lambda x, y: (x)**2 + y**2
gen = Genetic(f)
minim = gen.run()
print('Minimum found      X =', minim[0], ', Y =', minim[1])


Minimum found X = 0 , Y = 0

f = lambda x, y: (x-6)**2 + y**2
gen = Genetic(f)
minim = gen.run()
print('Minimum found      X =', minim[0], ', Y =', minim[1])


Minimum found X = 6 , Y = 0