昨日私は遺伝的アルゴリズムの探求を始めました、そして私がいくつかの基本的な理論にたどり着いたとき、私はディオファントス方程式を解く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： 染色体を整数ではなくグレイコードで保存します。