遗传算法在Python中暂停？

Question

我在 python 中实现了一个简单的遗传算法 - 这是大部分代码：

import random

ings = (('w1',  200,  25,  80),
        ('su1',  50,  55, 150),
        ('su2', 400, 100, 203),
        ('sy1',  10, 150, 355),
        ('sy2', 123,  88, 101),
        ('sy3', 225,   5,  30),
        ('sy4',   1,  44,  99),
        ('sy5', 500, 220, 300))

mutationRate = 0.2
crossoverRate = 0.9
iterations = 100
file = open('D:\\logfile2.txt', 'a')

class Ingredient:
    def __init__(self, n, p, mi, ma):
        self.name = n
        self.price = p
        self.min = mi
        self.max = ma
        self.perc = random.randrange(self.min, self.max)

class Drink:
    def __init__(self):
        self.ing = [Ingredient(*x) for x in ings]
        self.normalize()
        self.fitness = self.evaluate()

    def normalize(self):
        sum = 0
        for x in self.ing:
            sum += x.perc
        if sum < 1000:
            offset = 1000 - sum
            while not offset == 0:
                index = random.randrange(len(self.ing))
                val = self.ing[index].max - self.ing[index].perc
                threshold = random.randrange(val) if val > 0 else 0
                threshold = threshold if threshold < offset else offset
                self.ing[index].perc += threshold
                offset -= threshold
        if sum > 1000:
            offset = sum - 1000
            while not offset == 0:
                index = random.randrange(len(self.ing))
                val = self.ing[index].perc - self.ing[index].min
                threshold = random.randrange(val) if val > 0 else 0
                threshold = threshold if threshold < offset else offset
                self.ing[index].perc -= threshold
                offset -= threshold

    def evaluate(self):
        fitness = 0
        for x in self.ing:
            fitness += x.perc * x.price
        return 300000 - fitness

class GeneticAlgorithm:
    def __init__(self):
        self.drinkList = [Drink() for x in range(8)]
        self.pool = []

    def mutate(self, index):
        ing1, ing2 = random.randrange(8), random.randrange(8)
        while ing1 == ing2:
            ing2 = random.randrange(8)
        ptr = self.drinkList[index].ing
        ing1thr = ptr[ing1].max - ptr[ing1].perc
        ing2thr = ptr[ing2].perc - ptr[ing2].min
        if ing1thr & ing2thr:
            change = random.randrange(ing1thr if ing1thr < ing2thr else ing2thr)
            ptr[ing1].perc += change
            ptr[ing2].perc -= change

    def crossover(self, index1, index2):
        ing1, ing2 = random.randrange(8), random.randrange(8)
        while ing1 == ing2:
            ing2 = random.randrange(8)
        ptr1 = self.drinkList[index1].ing[:]
        ptr2 = self.drinkList[index2].ing[:]
        resultIndex1 = random.randrange(len(self.drinkList))
        while True:
            resultIndex2 = random.randrange(len(self.drinkList))
            if not resultIndex1 == resultIndex2:
                break
        bias = 1 if ptr1[ing1].perc > ptr2[ing1].perc else -1
        if bias == 1:
            maxChange = min(ptr1[ing1].perc - ptr1[ing1].min,
                            ptr1[ing2].max - ptr1[ing2].perc,
                            ptr2[ing1].max - ptr2[ing1].perc,
                            ptr2[ing2].perc - ptr2[ing2].min)
            if maxChange:
                change = random.randrange(maxChange)
                ptr1[ing1].perc -= change
                ptr1[ing2].perc += change
                ptr2[ing1].perc += change
                ptr2[ing2].perc -= change
                self.drinkList[resultIndex1].ing = ptr1[:]
                self.drinkList[resultIndex2].ing = ptr2[:]
        if bias == -1:
            maxChange = min(ptr1[ing1].max - ptr1[ing1].perc,
                            ptr1[ing2].perc - ptr1[ing2].min,
                            ptr2[ing1].perc - ptr2[ing1].min,
                            ptr2[ing2].max - ptr2[ing2].perc)
            if maxChange:
                change = random.randrange(maxChange)
                ptr1[ing1].perc += change
                ptr1[ing2].perc -= change
                ptr2[ing1].perc -= change
                ptr2[ing2].perc += change
                self.drinkList[resultIndex1].ing = ptr1[:]
                self.drinkList[resultIndex2].ing = ptr2[:]

    def roulette(self):
        sum = 0
        lst = []
        for x in self.drinkList:
            sum += x.fitness
            lst.append(sum)
        return lst

    def selectOne(self):
        selection = random.randrange(self.pool[-1])
        index = 0
        while selection >= self.pool[index]:
            index += 1
        return index

    def selectCouple(self):
        selection1 = random.randrange(self.pool[-1])
        index1, index2 = 0, 0
        while selection1 >= self.pool[index1]:
            index1 += 1
        while True:
            selection2 = random.randrange(self.pool[-1])
            while selection2 >= self.pool[index2]:
                index2 += 1
            if not index1 == index2: break
        return (index1, index2)

    def save(self, text):
        file.write(text)
        for x in self.drinkList:
            for y in x.ing:
                file.write('min: ' + str(y.min) +
                           ' max: ' + str(y.max) +
                           ' value: ' + str(y.perc) + '\n')
            file.write('\n\n')
        file.write('\nPopulation fitness: ' +
                   str(self.calculatePopulationFitness()) +
                   '\n\n----------------------------------------------\n\n')

    def run(self):
        file.write("Genetic algorithm\n\nAttributes values:\n" +
                   "Mutation rate: " + str(mutationRate) +
                   "\nCrossover rate: " + str(crossoverRate) +
                   "\nIterations: " + str(iterations) +
                   "\nIngredients:\n\n" + str(ings))
        self.save('\n\n--First population--\n\n')
        for cnt in range(iterations):
            self.updateFitness()
            self.pool = self.roulette()
            if random.random() < mutationRate:
                index = self.selectOne()
                self.showFitness('Mutation in iteration ' + str(cnt))
                self.mutate(index)
                self.updateFitness()
                self.showFitness('Results: ')
            if random.random() < crossoverRate:
                index1, index2 = self.selectCouple()
                self.showFitness('Crossover in iteration ' + str(cnt))
                self.crossover(index1, index2)
                self.updateFitness()
                self.showFitness('Results: ')
        self.save('--Final population--\n\n')

    def calculatePopulationFitness(self):
        sum = 0
        for x in self.drinkList:
            sum += x.fitness
        return sum

    def updateFitness(self):
        for x in self.drinkList:
            x.fitness = x.evaluate()

    def showFitness(self, text):
        lst = [x.fitness for x in self.drinkList]
        all = sum(lst)
        file.write(text + '\n' + str(lst) + '||' + str(all) + '\n')

为了运行它，我创建了 GeneticAlgorithm 的实例并通过 run() 方法启动它。 问题是，对于低级别的迭代，程序或多或少工作得很好，但如果我将迭代设置为 50，例如，它似乎陷入无限循环或随机迭代挂起（日志文件不再更新，程序也这样做）不停止 - 随机迭代发生）。这可能是什么原因造成的？

PS：您能建议对编码风格进行任何更改吗？我对 python 很陌生，还不知道所有的约定。

Answer 1

我不完全理解你的算法，但看起来你的代码挂在这个循环中：

while True:
    selection2 = random.randrange(self.pool[-1])
    while selection2 >= self.pool[index2]:
        index2 += 1
    if not index1 == index2: break

它达到了你永远不会得到索引1！=索引2的值的地步。这可能表明您的代码中某个地方有错误，或者不存在满足此条件的情况。您可以尝试对其迭代次数设置上限，例如：

iters = 0
while iters < 5000:
    selection2 = random.randrange(self.pool[-1])
    while selection2 >= self.pool[index2]:
        index2 += 1
    iters += 1
    if index1 != index2: break

if iters == 5000:
    # Deal with not being able to identify a Couple

Answer 2

我知道这个问题已经存在一年多了。我仍然想要一个 python 中的 GA 代码来开始并发现问题。

while True:
    selection2 = random.randrange(self.pool[-1])
    while selection2 >= self.pool[index2]:
        index2 += 1
    if not index1 == index2: break

问题出在这个循环中。一旦发现 index2 相等，在尝试查找新值之前，它不会重置为零。

while True:
    index2 = 0
    selection2 = random.randrange(self.pool[-1])
    while selection2 >= self.pool[index2]:
        index2 += 1
    if not index1 == index2: break