Python: Genetic algorithm weak performance

Question

I am currently working on a school project which consists of finding the maximum water possible out of porous medium given a fixed porosity (So we find the optimal pore distribution). I used genetic algorithm to solve this problem by modeling the medium as a square matrix filled with 0 for void, 1 for solid medium and 2 for water. I looked up the internet for optimal values of crossover rates, mutation rates,etc. The problem is that sometimes I reach a maximum and then it starts to drop over the generations, and sometimes I am stuck with 0 water out of the medium for all the generations. I don't know where did I go wrong. If you need the code for the evolution process or the crossover, feel free to tell me in the comments. Thanks in advance.

Crossover: This function crossover two mediums and maintains the porosity, the child should have the same porosity as both parents.

def crossover(g,h,n,p,cp):#crossover(parent1,parent2,size of matrix, porosity,crossover rate)
b=n*n
k=int(b*p)
l=g
if cp>rnd.random():
    l[n//3:2*n//3] = h[n//3:2*n//3]
    count = 0
    for i in range(n):
        for j in range(n):
            if l[i][j] == 1:
                count +=1
    diff = count-k
    if diff>0:
        while diff>0:
            i=rnd.randint(0,n-1)
            j=rnd.randint(0,n-1)
            if l[i][j] == 1:
                l[i][j] = 0
            diff -=1
    if diff<0:
        while diff<0:
            i=rnd.randint(0,n-1)
            j=rnd.randint(0,n-1)
            if l[i][j] == 0:
                l[i][j] = 1
            diff+=1
return l

This crossover is a two point crossover.

Evolution code:

 def evolve(pop,m,n,p,mp,cp,sp=0.3):#evolve(the population list,population length, matrix size,porosity,mutation probability, crossover probability, rate of individuals to be selected for the upcoming generation)
graded = [ (ratio(pop[i], n), i) for i in range(m)]
graded = [ x[1] for x in sorted(graded)]
retain_length = int(m*sp)
parents = [pop[x] for x in graded[retain_length:]]
# randomly add other individuals to promote genetic diversity
for individual in graded[:retain_length]:
    if 0.025 > rnd.random():
        parents.append(pop[individual])       
# mutate some individuals
for individual in parents:
    if mp>rnd.random():
       individual = mutate(individual,n,mp)
# crossover parents to create children
parents_length = len(parents)
desired_length = m - parents_length
children = []
while len(children) < desired_length:
    male = rnd.randint(0, parents_length-1)
    female = rnd.randint(0, parents_length-1)
    if male != female:
        male = parents[male]
        female = parents[female]
        children.append(crossover(male,female,n,p,cp))
parents.extend(children)
return parents

Edit: After increasing the mutation rate up to 0.05, the GA gives me good results, but doesn't it mean that I lose some of the parents genes? Another question, what if I chose the population being the result of the first GA run and use it in the next one, would it increase the performance?

Please always show code - it's very difficult for anyone to help you without workable sample data and especially without code to look at. — flyingmeatball
– flyingmeatball, Commented May 25, 2017 at 13:16
Showing your code is always a good idea here, but it sounds like you may have hit a saddle point and you might want to try again with different mutation and crossover probabilities. — Matt Cremeens
– Matt Cremeens, Commented May 25, 2017 at 13:18
@MattCremeens I tried many rates. At first it gave satisfactory results, but now with the same values, I get nothing — Oussama Boussif
– Oussama Boussif, Commented May 25, 2017 at 13:19
My main problem here is why do I not get an optimization and why when we reach a maximum, the next generations become way weaker until reaching the bare minimum — Oussama Boussif
– Oussama Boussif, Commented May 25, 2017 at 13:27
Can you tell us what parameters you call this function with? — Matt Cremeens
– Matt Cremeens, Commented May 25, 2017 at 13:38

Matt Cremeens · Accepted Answer · 2017-05-25 14:56:19Z

1

I believe the problem might be here

l[n//3:2*n//3] = h[n//3:2*n//3]

This appears to be where you take some of the chromosomes from one parent and assign them to another, but you are not doing so randomly. What I think would work better is if you generated a random crossover point and replace //3 with //k. But what you need are two new chromosomes, such as,

m = []
m_cnt = 0
for elem in l:
    if m_cnt < k:
        m[m_cnt] = elem
     m_cnt += 1

m_cnt = k
for elem in h:
    if m_cnt >= k:
        m[m_cnt] = elem
    m_cnt += 1

And do the reverse for the next child chromosome.

In any case, the initial random parameters, such as crossover and mutation probabilities should be experimented with so as to ensure a saddle point isn't being reached.

edited May 25, 2017 at 14:56

answered May 25, 2017 at 13:55

Matt Cremeens

5,2118 gold badges42 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

11 Comments

Oussama Boussif Over a year ago

But should I maintain the number of crossover points? or change it? Do I perform a two point crossover in random places for example? Plus, you might have noticed that due to the necessity of keeping the same porosity after crossover, the latter does a bit of mutation

Matt Cremeens Over a year ago

The chromosomes of the two parents should split randomly each time and be combined to form a new (offspring) chromosome or be cloned. Either way, you will create two new chromosomes each time. I am not sure what porosity is.

Oussama Boussif Over a year ago

Porosity is a property of the medium, it represents the ratio of solid nodes to the number of elements in the matrix, i.e: the number of black squares divided by the size of the matrix squared. I think that I found my problem. The problem lies within the weakness of the initial population and this might give a very slow convergence that's why I don't see a significant change, so a higher mutation probability would be suitable to converge faster towards a solution. What do you think?

Matt Cremeens Over a year ago

I don't think that you are producing two new offspring chromosomes. I edited my answer to address this. Not sure if it'll help.

Oussama Boussif Over a year ago

I see, but you still have to check whether the porosity is the same or not and fix the gap. This said, I guess that your code wouldn't be much different than mine if I change the 3 to k or a suitable number. I guess my problem had to do with the very weakness of the initial population, now that I changed some parameters, I got satisfactory results.

|

Collectives™ on Stack Overflow

Python: Genetic algorithm weak performance

1 Answer 1

11 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

11 Comments

Your Answer

Sign up or log in

Post as a guest

Related