1
$\begingroup$

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?

$\endgroup$
0
4
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.