昨天我开始探索遗传算法，当我结束了一些基本理论时，我尝试在 Python 上编写简单的 GA 来解决丢番图方程。我是 Python 和 GA 的新手，所以请不要严格判断我的代码。
问题
由于过早收敛，我无法得到任何结果（有一些不归路点（n-population），population[n] == population[n+i]，其中 i 是任何整数。即使是随机突变元素也无法改变这一点，这一代正在迅速退化）
GA 正在使用交叉来繁殖，并加权选择父母。
- Q1：我的代码（如下）是否有任何设计错误？
- Q1.2：我需要添加精英主义吗？
- Q1.3：我需要改变品种逻辑吗？
- Q2：真的需要深拷贝吗？
代码：
# -*- coding: utf-8 -*-
from random import randint
from copy import deepcopy
from math import floor
import random
class Organism:
#initiate
def __init__(self, alleles, fitness, likelihood):
self.alleles = alleles
self.fitness = fitness
self.likelihood = likelihood
self.result = 0
def __unicode__(self):
return '%s [%s - %s]' % (self.alleles, self.fitness, self.likelihood)
class CDiophantine:
def __init__(self, coefficients, result):
self.coefficients = coefficients
self.result = result
maxPopulation = 40
organisms = []
def GetGene (self,i):
return self.organisms[i]
def OrganismFitness (self,gene):
gene.result = 0
for i in range (0, len(self.coefficients)):
gene.result += self.coefficients[i]*gene.alleles[i]
gene.fitness = abs(gene.result - self.result)
return gene.fitness
def Fitness (self):
for organism in self.organisms:
organism.fitness = self.OrganismFitness(organism)
if organism.fitness == 0:
return organism
return None
def MultiplyFitness (self):
coefficientSum = 0
for organism in self.organisms:
coefficientSum += 1/float(organism.fitness)
return coefficientSum
def GenerateLikelihoods (self):
last = 0
multiplyFitness = self.MultiplyFitness()
for organism in self.organisms:
last = ((1/float(organism.fitness)/multiplyFitness)*100)
#print '1/%s/%s*100 - %s' % (organism.fitness, multiplyFitness, last)
organism.likelihood = last
def Breed (self, parentOne, parentTwo):
crossover = randint (1,len(self.coefficients)-1)
child = deepcopy(parentOne)
initial = 0
final = len(parentOne.alleles) - 1
if randint (1,100) < 50:
father = parentOne
mother = parentTwo
else:
father = parentTwo
mother = parentOne
child.alleles = mother.alleles[:crossover] + father.alleles[crossover:]
if randint (1,100) < 5:
for i in range(initial,final):
child.alleles[i] = randint (0,self.result)
return child
def CreateNewOrganisms (self):
#generating new population
tempPopulation = []
for _ in self.organisms:
iterations = 0
father = deepcopy(self.organisms[0])
mother = deepcopy(self.organisms[1])
while father.alleles == mother.alleles:
father = self.WeightedChoice()
mother = self.WeightedChoice()
iterations+=1
if iterations > 35:
break
kid = self.Breed(father,mother)
tempPopulation.append(kid)
self.organisms = tempPopulation
def WeightedChoice (self):
list = []
for organism in self.organisms:
list.append((organism.likelihood,organism))
list = sorted((random.random() * x[0], x[1]) for x in list)
return list[-1][1]
def AverageFitness (self):
sum = 0
for organism in self.organisms:
sum += organism.fitness
return float(sum)/len(self.organisms)
def AverageLikelihoods (self):
sum = 0
for organism in self.organisms:
sum += organism.likelihood
return sum/len(self.organisms)
def Solve (self):
solution = None
for i in range(0,self.maxPopulation):
alleles = []
#
for j in range(0, len(self.coefficients)):
alleles.append(randint(0, self.result))
self.organisms.append(Organism(alleles,0,0))
solution = self.Fitness()
if solution:
return solution.alleles
iterations = 0
while not solution and iterations <3000:
self.GenerateLikelihoods()
self.CreateNewOrganisms()
solution = self.Fitness()
if solution:
print 'SOLUTION FOUND IN %s ITERATIONS' % iterations
return solution.alleles
iterations += 1
return -1
if __name__ == "__main__":
diophantine = CDiophantine ([1,2,3,4],30)
#cProfile.run('diophantine.Solve()')
print diophantine.Solve()
我试图改变品种和加权随机选择逻辑，但没有结果。这个GA应该是工作，我不知道，有什么问题。我知道 Python 上有一些 GA 库，我现在正试图理解它们——它们对我来说似乎相当复杂。对不起，英语不是我的母语。感谢您的理解。
NECROUPDATE： 以格雷码存储染色体，而不是整数。