Python 中的遗传算法问题

Question

我有 this 遗传算法，它应该给我 010010010010 或最佳解决方案，使用突变它工作正常，但当我尝试添加交叉时有时会显示此错误：'NoneType' object has no attribute 'genes'。我试了三次从头开始重做，都是同样的错误。
调试也没有用，因为它是随机的，有时在找到解决方案之前会出错，有时没有错误。

半翻译代码（推荐看original那个，有一些葡萄牙语）：

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

似乎当错误发生时，selecaoreleta 运行但最后一个 for 循环没有 return 任何东西。例如，如果你输入

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

错误发生时会打印'no cromo found'。（是的，您可以放置 else 来指示如果 for 循环不间断地完成时要做什么：p。）我不知道您正在检查什么条件，因为它是葡萄牙语，但无论如何是的，有时候pop的cromossomos中的任何cromo都不满足。

这不是一个完整的答案，但希望它有助于查明问题。

PS，您的断言可能不正确。尝试在交叉函数中使用 assert (cromo1 is not None) and (cromo2 is not None) 之类的东西，而不是使用 type(cromo1) == 'NoneType'。然后 AssertionErrors 应该开始更好地弹出。

编辑：

所以再次在 selecaoroleta 中，在使用随机 numaleatorio 的最后一个循环中，打印出 numaleatorio 和带有 print(numaleatorio, cromo.intervalo) 的 intervalo 表明当 numaleatorio 为 0...或 360 时，错误总是发生。但是如果 numaleatorio 为 0，则选择 cromo 的条件 if numaleatorio > cromo.intervalo[0] and numaleatorio <= cromo.intervalo[1]: 将失败，即使 intervalo[0] 也为 0，因为 >。另一件事，最重要的是，打印出 intervalos 显示有时最高的 intervalo 类似于 359.9999999，因此 360 的 numaleatorio 也会失败。因此，解决方法可能是将 numaleatorio 更改为 numaleatorio = r.randint(1, 359)。或者，为了保持随机性，我可能会做 numaleatorio = r.randint(0, 359)，然后从 > 和 <= 切换到使用 >= 和 <。整个最后一个循环可能看起来像

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

(else 再次与 for 循环处于同一级别。它是 for (blank in blank): ... else: (do stuff here if the for loop finished without being interrupted)。您可以根据需要进行操作。 ) 这样，您的代码输出：

MELHOR SOLUCAO: 010010011010
APTIDAO: 11

但我希望我知道这是什么意思。

Python 中的遗传算法问题

Problems with genetic algorithm in Python

python

python-3.x

genetic-algorithm