Problems with genetic algorithm in Python

Question

I have this genetic algorithm that is supposed to give me 010010010010 or the best solution, with mutation it works fine, but when I try adding crossover sometimes it shows this error: 'NoneType' object has no attribute 'genes'. I've tried redoing it from scratch three times and it's always the same error.
Debugging also didn't work since it's random, sometimes it gives an error before finding a solution and sometimes there's no errors.

Semi-translated code (recommend seeing the original one, with some words in Portuguese):

import random as r

BASE = '010010010010' #solution


class Populacao: #population
    MAX_POPULACAO = 8 #max population
    TAMANHO_TORNEIO = 5 #ignore
    TAXA_UNIFORME = 0.5 #uniform rate
    TAXA_MUTACAO = 0.015 #mutation rate
    elitismo = True #elitism

    #                  solution generate    chromossomes
    def __init__(self, solucao, gerar=True, cromossomos=None):
        self.solucao = solucao
        if gerar == True:
            self.cromossomos = self._gerar()
        else:
            if cromossomos == None:
                self.cromossomos = []
            else:
                self.cromossomos = cromossomos

        for c in self.cromossomos:
            c.calcularaptidao(self.solucao) # calculate fitness

    def setsolucao(self, solucao):
        self.solucao = solucao

    def _gerar(self):
        return [Cromossomo() for cromossomo in range(0, self.MAX_POPULACAO)]

    def setcromossomo(self, index, cromo):
        self.cromossomos[index] = cromo

    #   getbetter
    def getmelhor(self):
        c1 = self.cromossomos[0]
        for c in self.cromossomos:
            if c.aptidao > c1.aptidao: # c.fitness > c1.fitness
                c1 = c
        return c1

    #   getworst
    def getpior(self):
        #                            getindexofworst
        return self.cromossomos[self.getindicepior()]

    #   getindexofworst
    def getindicepior(self):
        indice = 0 #index
        c1 = self.cromossomos[0]
        for i in range(0, len(self.cromossomos)):
            if self.cromossomos[i].aptidao < c1.aptidao:
                c1 = self.cromossomos[i]
                indice = i
        return indice

    def __str__(self):
        return self.cromossomos

    #   mutation
    def mutacao(self, cromo):
        for i in range(0, len(cromo.genes)):
            if r.random() <= self.TAXA_MUTACAO:
                gene = r.choice([0, 1])
                cromo.setgene(i, gene)

    #   rouletteselection
    def selecaoroleta(self):
        somaaptidao = 0  # fitness sum
        for cromo in self.cromossomos:
            somaaptidao += cromo.aptidao

        #start
        comeco = 0
        for cromo in self.cromossomos:
            #porc = percentage
            porc = (cromo.aptidao * 360) / somaaptidao
            cromo.setporcao(porc)
            cromo.calcularintervalo(comeco) # calculate interval
            comeco += cromo.porcao #portion

        numaleatorio = r.randint(0, 360) #random number
        for cromo in self.cromossomos:
            if numaleatorio > cromo.intervalo[0] and numaleatorio <= cromo.intervalo[1]:
                return cromo

    #   evolve        population
    def evoluir(self, pop):
        newPop = Populacao(pop.solucao, True)

        #offset_elitism
        offset_elitismo = 0
        if pop.elitismo:
            #worst = newPop.getindexofworst()
            pior = newPop.getindicepior()
            newPop.cromossomos[pior] = pop.getmelhor()
            offset_elitismo = 1
        else:
            offset_elitismo = 0

        for i in range(offset_elitismo, len(pop.cromossomos)):
            cromo1 = pop.selecaoroleta() # roulette selection
            cromo2 = pop.selecaoroleta()

            newCromo = self.crossover(cromo1, cromo2)
            newCromo.calcularaptidao(pop.solucao)

            newPop.cromossomos.append(newCromo)

        for i in range(offset_elitismo, len(newPop.cromossomos)):
            self.mutacao(newPop.cromossomos[i])
            newPop.cromossomos[i].calcularaptidao(pop.solucao)
        return newPop

    def crossover(self, cromo1, cromo2):
        assert type(cromo1) != 'NoneType'
        assert type(cromo2) != 'NoneType'

        newCromo = cromo1
        for i in range(0, len(cromo1)):              #<--- error usually here
            if r.random() <= self.TAXA_UNIFORME:
                newCromo.setgene(i, cromo1.genes[i])
            else:
                newCromo.setgene(i, cromo2.genes[i])
        return newCromo


#     chromossomes
class Cromossomo:
    MAX_GENES = 12   #max genes
    aptidao = 0      #fitness
    porcao = 0       #portion
    intervalo = []   #interval

    def __init__(self, genes=None):
        self.genes = genes or self._gerar()

    def _gerar(self):
        cromo = []
        for i in range(0, self.MAX_GENES):
            cromo.append(r.choice([0, 1]))
        return ''.join(map(str, cromo))

    def calcularaptidao(self, solucao):
        apt = 0
        for i in range(0, self.MAX_GENES):
            if self.genes[i] == solucao[i]:
                apt += 1
        self.aptidao = apt

    def setporcao(self, porc):
        self.porcao = porc

    def calcularintervalo(self, comeco):
        self.intervalo = [comeco, comeco + self.porcao]

    def setgene(self, index, gene):
        s = ''
        for i in range(len(self.genes)):
            if i == index:
                s += str(gene)
            else:
                s += self.genes[i]
        self.genes = s

    def __str__(self):
        return self.genes

    def __len__(self):
        return len(self.genes)


if __name__ == '__main__':
    pop = Populacao(BASE, True)
    geracoes = 0              #generations
    geracoes_max = 100        #max generations

    melhor = None             #best chromossomes
    while pop.getmelhor().aptidao < len(BASE) and geracoes < geracoes_max:
        geracoes += 1
        pop = pop.evoluir(pop)
        melhor = pop.getmelhor()

        print('GENERATION ' + str(geracoes) + ', BEST: ' + str(melhor) +
              ', FITNESS: ' + str(melhor.aptidao))

    print('')
    if melhor.aptidao < len(BASE):
        print('BEST SOLUTION: ' + str(melhor))
    else:
        print('SOLUTION FOUND IN ' + str(geracoes) + ' GENERATIONS: ' +
              str(melhor))

    print('FITNESS: ' + str(melhor.aptidao))

well, you have a bunch of checks for cromo1 being None, but in the code, cromo2 is None and causes the error. — Jay Calamari
– Jay Calamari, Commented Jun 14, 2018 at 4:08
@JayCalamari I changed the code and ran a few times, cromo1 is also None sometimes. — DarkCeptor44
– DarkCeptor44, Commented Jun 14, 2018 at 4:28

Jay Calamari · Accepted Answer · 2018-06-14 10:43:58Z

2

It seems like when the error happens, selecaoreleta runs but the last for loop doesn't return anything. E.g., if you put in

for cromo in self.cromossomos:
    if numaleatorio > cromo.intervalo[0] and numaleatorio <= cromo.intervalo[1]:
        return cromo
else:
    print('no cromo found')

it will print 'no cromo found' when the error happens. (Yes, you can put else to indicate what to do if a for loop finished without interruption :p.) I don't know what condition you're checking since it's in Portuguese, but whatever it is, sometimes it's not satisfied by any cromo in the cromossomos of pop.

It's not a complete answer, but hopefully it helps pinpoint the problem.

PS, your assertions might not be working right. Try, in the crossover function, something like assert (cromo1 is not None) and (cromo2 is not None), rather than using type(cromo1) == 'NoneType'. Then the AssertionErrors should start popping up better.

EDIT:

So again in selecaoroleta, inside the last loop which uses the random numaleatorio, printing out the numaleatorio and the intervalo with print(numaleatorio, cromo.intervalo) shows that the error always happens when numaleatorio is 0...or 360. But the condition for selecting the cromo, if numaleatorio > cromo.intervalo[0] and numaleatorio <= cromo.intervalo[1]:, will fail if numaleatorio is 0, even if the intervalo[0] is also 0, because of the >. Another thing, on top of this, printing out the intervalos shows that sometimes the highest intervalo is something like 359.9999999, so that a numaleatorio of 360 will also fail. So, a fix could be to change numaleatorio to numaleatorio = r.randint(1, 359). Or, to keep the randomness even, I might do numaleatorio = r.randint(0, 359) and then switch from > and <= to using >= and <. The whole last loop might look something like

numaleatorio = r.randint(0, 359)
for cromo in self.cromossomos:
    if numaleatorio >= cromo.intervalo[0] and numaleatorio < cromo.intervalo[1]:
        return cromo
else:
    raise ValueError('Intervalo was bad. No cromo found!')

(The else is on the same level as the for loop again. It's for (blank in blank): ... else: (do stuff here if the for loop finished without being interrupted). You can do it however you want.) With that, your code outputs:

MELHOR SOLUCAO: 010010011010
APTIDAO: 11

I wish I knew what it meant though.

edited Jun 14, 2018 at 10:43

answered Jun 14, 2018 at 4:42

Jay Calamari

6531 gold badge6 silver badges17 bronze badges

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

5 Comments

DarkCeptor44 Over a year ago

Wow, I didn't even thought the error could be in the roulette selection, thanks! I'm gonna check that out.

DarkCeptor44 Over a year ago

I changed the code again, so now it prints 'cromo found' at least once per chromossome, the loop is for checking which of the cromos are in the interval, so it is supposed to return only one cromo.

Jay Calamari Over a year ago

Hey, sorry for the late reply. That helped, and I think I got it. You might have already too by now though :p (I edited my answer)

DarkCeptor44 Over a year ago

You're right, it did work, thank you and sorry that I can't translate better, I have lots of stuff to do in college with little time. By the way I'm gonna let the algorithm there in that link if you want to play around, I'm gonna translate it soon.

Jay Calamari Over a year ago

Sounds cool. And don't worry about the translation. I just like Brazil and really wish I knew more Portuguese, heh.

Collectives™ on Stack Overflow

Problems with genetic algorithm in Python

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related