Python: algorithme génétique faible performance

Question

Je travaille actuellement sur un projet scolaire qui consiste à trouver le maximum d'eau possible en milieu poreux compte tenu d'une porosité fixe (on trouve donc la répartition optimale des pores). J'ai utilisé l'algorithme génétique pour résoudre ce problème en modélisant le milieu comme une matrice carrée remplie de 0 pour le vide, 1 pour le milieu solide et 2 pour l'eau. J'ai cherché sur Internet les valeurs optimales des taux de croisement, des taux de mutation, etc. Le problème est que parfois j'atteins un maximum et puis il commence à tomber au fil des générations, et parfois je suis coincé avec 0 l'eau hors du milieu pour toutes les générations. Je ne sais pas où je me suis trompé. Si vous avez besoin du code pour le processus d'évolution ou le crossover, n'hésitez pas à me le dire dans les commentaires. Merci d'avance. Crossover: Cette fonction croise deux milieux et maintient la porosité, l'enfant doit avoir la même porosité que les deux 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 

Ce croisement est un croisement à deux points.

Code Evolution:

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: Après avoir augmenté le taux de mutation jusqu'à 0,05, l'AG me donne de bons résultats, mais ne pas dire que je perds certains des gènes des parents? Une autre question, et si je choisissais la population étant le résultat de la première exécution GA et l'utilisiez dans le suivant, cela augmenterait-il la performance?

Answer 1

Je crois que le problème est peut-être ici

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

Cela semble être là où vous prenez certains des chromosomes d'un parent et de les affecter à une autre, mais vous ne le font pas au hasard. Ce que je pense fonctionnerait mieux si vous générez un point de croisement aléatoire et remplacez //3 par //k. Mais ce que vous avez besoin de deux nouveaux chromosomes, tels que,

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 

Et faire l'inverse pour le prochain chromosome de l'enfant.

Dans tous les cas, les paramètres aléatoires initiaux, tels que les probabilités de croisement et de mutation doivent être expérimentés afin de s'assurer qu'un point de selle n'est pas atteint.