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))

Answer 1

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.