Clinton Sheppard的Genetic Algorithms with Python一書總結(jié)的筆記
git鏈接:
https://github.com/handcraftsman/GeneticAlgorithmsWithPython
1. 用遺傳算法guess password
import random
import datetime
geneSet = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!。"
target = "Hello World!"
def generate_parent(length):
genes = []
while len(genes) < length:
sampleSize = min(length - len(genes), len(geneSet))
genes.extend(random.sample(geneSet, sampleSize))
return ''.join(genes)
隨機(jī)生成父母, random.sample(geneSet, sampleSize)在geneSet里隨機(jī)選sampleSize個(gè)不同的元素行施，組成字符串返回
def get_fitness(guess):
return sum(1 for expected, actual in zip(target, guess) if expected ==actual)
計(jì)算和目標(biāo)相同的元素?cái)?shù)量确丢，作為適應(yīng)度返回
def mutate(parent):
index = random.randrange(0, len(parent))
childGenes = list(parent)
newGene, alternate =random.sample(geneSet, 2)
childGenes[index] = alternate if newGene == childGenes[index] else newGene
return ''.join(childGenes)
變異，從parent里面隨機(jī)選一位變異奇钞，產(chǎn)生newGene和alternate兩個(gè)元素，是為了防止變異前和變異后相同
def display(guess):
timeDiff = datetime.datetime.now() - startTime
fitness = get_fitness(guess)
print("{}\t{}\t{}\t".format(guess, fitness, timeDiff))
random.seed()
startTime = datetime.datetime.now()
bestParent = generate_parent(len(target))
bestFitness = get_fitness(bestParent)
display(bestParent)
while True:
child = mutate(bestParent)
childFitness = get_fitness(child)
if bestFitness >= childFitness:
continue
display(child)
if childFitness >= len(bestParent):
break
bestFitness = childFitness
bestParent = child
2. 改進(jìn)一:從上面提取一個(gè)可重復(fù)使用的engine
為了讓這個(gè)GA engine不僅僅只解決這個(gè)項(xiàng)目漂坏，要單獨(dú)把初始值的產(chǎn)生景埃，變異媒至，遺傳算法的主要過程提取出來單獨(dú)放到一個(gè)py文件，命名為genetic.py
import random
def _generate_parent(length, geneSet):
genes = []
while len(genes) < length:
sampleSize = min(length - len(genes), len(geneSet))
genes.extend(random.sample(geneSet, sampleSize))
return ''.join(genes)
def _mutate(parent, geneSet):
index = random.randrange(0, len(parent))
childGenes = list(parent)
newGene, alternate =random.sample(geneSet, 2)
childGenes[index] = alternate if newGene == childGenes[index] else newGene
return ''.join(childGenes)
def get_best(get_fitness, targetLen, optimalFitness, geneSet, display):
random.seed()
bestParent = _generate_parent(targetLen, geneSet)
bestFitness = get_fitness(bestParent)
display(bestParent)
if bestFitness >= optimalFitness:
return bestParent
while True:
child = _mutate(bestParent, geneSet)
childFitness = get_fitness(child)
if bestFitness >= childFitness:
continue
display(child)
if childFitness >= optimalFitness:
return child
bestFitness = childFitness
bestParent = child
適應(yīng)度的計(jì)算谷徙，區(qū)間上下界以及主函數(shù)等放在另一個(gè)文件'guessword.py'
import datetime
import genetic
def get_fitness(genes, target):
return sum(1 for expected, actual in zip(target, genes) if expected ==actual)
def display(genes, target, startTime):
timeDiff = datetime.datetime.now() - startTime
fitness = get_fitness(genes, target)
print("{}\t{}\t{}\t".format(genes, fitness, timeDiff))
def test_Hello_World():
target = "Hello World!"
guess_password(target)
def guess_password(target):
geneSet = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!."
startTime = datetime.datetime.now()
def fnGetFitness(genes):
return get_fitness(genes, target)
def fnDisplay(genes):
display(genes, target, startTime)
optimalFitness = len(target)
genetic.get_best(fnGetFitness,len(target),optimalFitness,geneSet,fnDisplay)
if __name__ =='__main__':
test_Hello_World()
3. 改進(jìn)二: Use unittest framework
在測(cè)試環(huán)境下工作拒啰，新建一個(gè)guessPasswordTests.py
import unittest
class GuessPasswordTests(unittest.TestCase):
geneSet = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!."
def test_Hello_World():
target = "Hello World!"
guess_password(target)
def guess_password(self, target):
optimalFitness = len(target)
best = genetic.get_best(fnGetFitness, len(target), optimalFitness, self.geneset, fnDisplay)
self.assertEqual(best, target)
if __name__ == '__main__':
unittest.main()
4.改進(jìn)三: 認(rèn)識(shí)染色體(Chromosome)
在genetic.py定義一個(gè)染色體
class Chromosome:
Genes = None
Fitness = None
def __init__(self, genes, fitness):
self.Genes = genes
self.Fitness = fitness
加入定義的染色體后其它function的變化
def _generate_parent(length, geneSet, get_fitness):
genes = []
while len(genes) < length:
sampleSize = min(length - len(genes), len(geneSet))
genes.extend(random.sample(geneSet, sampleSize))
genes = ''.join(genes)
fitness = get_fitness(genes)
return Chromosome(genes, fitness)
def _mutate(parent, geneSet, get_fitness):
index = random.randrange(0, len(parent.Genes))
childGenes = list(parent.Genes)
newGene, alternate = random.sample(geneSet, 2)
childGenes[index] = alternate if newGene == childGenes[index] else newGene
genes = ''.join(childGenes)
fitness = get_fitness(genes)
return Chromosome(genes, fitness)
def get_best(get_fitness, targetLen, optimalFitness, geneSet, display):
random.seed()
bestParent = _generate_parent(targetLen, geneSet, get_fitness)
display(bestParent)
if bestParent.Fitness >= optimalFitness:
return bestParent
while True:
child = _mutate(bestParent, geneSet, get_fitness)
if bestParent.Fitness >= child.Fitness:
continue
display(child)
if child.Fitness >= optimalFitness:
return child
bestParent = child
5. 改進(jìn)四: 基準(zhǔn)測(cè)試(Benchmarking)
在genetic.py添加Benchmarking來了解一個(gè)算法求解要多久，標(biāo)準(zhǔn)偏差是多少
import statistic
import time
class Benchmark:
@staticmethod
def run(function):
timings = []
stdout = sys.stdout
for i in range(100):
sys.stdout = None
startTime = time.time()
function()
seconds = time.time() - startTime
sys.stdout = stdout
timings.append(seconds)
mean = statistics.mean(timings)
if i < 10 or i % 10 == 9:
print("{} {:3.2f} {:3.2f}".format(
1 + i, mean,
statistics.stdev(timings, mean) if i > 1 else 0))
在guessPasswordTests.py中添加相關(guān)function
import datetime
import random
import unittest
import genetic
def get_fitness(guess, target):
return sum(1 for expected, actual in zip(target, guess)
if expected == actual)
def display(candidate, startTime):
timeDiff = datetime.datetime.now() - startTime
print("{}\t{}\t{}".format(
candidate.Genes, candidate.Fitness, timeDiff))
class GuessPasswordTests(unittest.TestCase):
geneset = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!.,"
def test_Hello_World(self):
target = "Hello World!"
self.guess_password(target)
def test_For_I_am_fearfully_and_wonderfully_made(self):
target = "For I am fearfully and wonderfully made."
self.guess_password(target)
def guess_password(self, target):
startTime = datetime.datetime.now()
def fnGetFitness(genes):
return get_fitness(genes, target)
def fnDisplay(candidate):
display(candidate, startTime)
optimalFitness = len(target)
best = genetic.get_best(fnGetFitness, len(target), optimalFitness,
self.geneset, fnDisplay)
self.assertEqual(best.Genes, target)
def test_Random(self):
length = 150
target = ''.join(random.choice(self.geneset)
for _ in range(length))
self.guess_password(target)
def test_benchmark(self):
genetic.Benchmark.run(self.test_Random)
if __name__ == '__main__':
unittest.main()
