Genetic algorithm suspends in python?

Question

I have implemented a simple genetic algorithm in python - here is the most of the code:

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

To run it I create an instance of GeneticAlgorithm and launch it through run() method. The problem is, for low level of iterations the program works more or less fine, but if I set iteration to 50 for example, it seems to fall in infinite loop or suspend at random iteration (the logfile is not updated anymore and the program does not stop - happenes at random iteration). What can be the cause of this?

PS: Can you suggest any changes to the coding style? I'm quite new to python and i don't know all the conventions yet.

Answer 1

I don't completely understand your algorithm but it looks like your code hangs in this loop here:

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

It gets to a point where you never get a value where index1 != index2. This could either indicate you have a mistake somewhere in your code, or that there isn't a situation that meets this condition. You could try putting a cap on the number of iterations of this, for example:

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

I know the question is more than a year old. Still I wanted a GA code in python to start with and found the problem.

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

The problem is in this loop. once index2 is found to be equal it is not reset back to zero before trying to find a new value.

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