Genetic algorithm: problem of convergence-CodePudding

I'm trying to find the solution of the one-max problem with a genetic algorithm, but it is not converging, instead the maximum fitness is getting lower. I can't see why it's not working; I tried to execute the functions on their own and they worked, I'm not sure about the calling in the main though.the one max problem is when you have a population N of binary individuals (1/0) of length m, and you want to optimize your population so you generate at least one individual containing only 1s (in my case 0s)

Here's my code:

import random

def fitness(individual):
    i = 0
    for m in individual:
        if m == 0:
            i  = 1
    return i

def selection(pop):
    chosen = []
    for i in range(len(pop)):
        aspirants = []
        macs = []
        for j in range(3):
            aspirants.append(random.choice(pop))
        if fitness(aspirants[0]) > fitness(aspirants[1]):
            if fitness(aspirants[0]) > fitness(aspirants[2]):
                macs = aspirants[0]
            else: macs = aspirants[2]
        else:
            if fitness(aspirants[1]) > fitness(aspirants[2]):
                macs = aspirants[1]
            else: macs = aspirants[2]
        chosen.append(macs)
    return chosen

def crossover(offspring):
    for child1, child2 in zip(offspring[::2], offspring[1::2]):
        if random.random() < 0.7:
            child1[50:100], child2[50:100]=child2[50:100], child1[50:100]

def mutate(offspring):
    for mut in offspring:
        if random.random() < 0.3:
            for i in range(len(mut)):
                if random.random() < 0.05:
                    mut[i] = type(mut[i])(not mut[i])

def gen_individ():
    ind = []
    for s in range(100):
        ind.append(random.randint(0, 1))
    return ind

def gen_pop():
    pop = []  
    for s in range(300):
        pop.append(gen_individ())
    return pop

g = 0
popul = gen_pop()
print("length of pop = %i "% len(popul))
fits = []
for k in popul:
    fits.append(fitness(k))    
print("best fitness before = %i"% max(fits))
while(max(fits) < 100 and g < 100):   
    g  = 1
    offspring = []
    offspring = selection(popul)
    crossover(offspring)
    mutate(offspring)
    popul.clear()
    popul[:] = offspring
    fits.clear()
    for k in popul:
    fits.append(fitness(k))
print("lenght of pop = %i "% len(popul))
print("best fitness after = %i"% max(fits))  
print("generation : %i"%g)

CodePudding user response：

The problem seems to be that in all your functions, you always just modify the same individuals instead of creating copies. For instance, in the selection function you repeatedly select the best-out-of-three (in a rather convoluted way), and then insert multiple references to that same list into the chosen list. Later, when you mutate any of those, you mutate all the references. In the end you might even end up with just N references to the same list, at which point obviously no more actual selection can take place.

Instead, you should create copies of the lists. This can happen in different places: in your main method, in mutate and recombine, or in the selection for the next iteration. I'll put it into selection, mainly for the reason that this function can be improved in other ways, too:

def selection(pop):
    chosen = []
    for i in range(len(pop)):
        # a lot shorter
        aspirants = random.sample(pop, 3)
        macs = max(aspirants, key=fitness)
        # create COPIES of the individual, not multiple references
        chosen.append(macs[:])
    return chosen

With this, you should get a quality of 100 each time.