Я реализовал простой генетический алгоритм в 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 и пока не знаю всех условностей.