今天无意中看到了一篇讲遗传算法的文章,文章内容很短,大部分都是代码,代码跟平时见到的遗传算法不同
之所以要拿这篇文章来讲,主要是因为原文没有对代码进行解释,但是,这段简短的代码的确十分有效,先来看看原代码,待会我会在原代码的基础上进行小小的修改:
from string import ascii_lowercase
from random import choice, random
target = list("welcome to http://www.cnhup.com")
charset = ascii_lowercase + ' .:/'
parent = [choice(charset) for _ in range(len(target))]
minmutaterate = .09
C = range(100)
perfectfitness = len(target)
def fitness(trial):
return sum(t==h for t,h in zip(trial, target))
def mutaterate(parent):
return 1.0-(1.0*(perfectfitness - fitness(parent)) / perfectfitness * (1.0 - minmutaterate))
def mutate(parent, rate):
return [(ch if random() <= rate else choice(charset)) for ch in parent]
def log(iterations,rate,parent):
print ("#%-4i, rate: %4.3f, fitness: %4.1f%%, '%s'" %
(iterations, rate, fitness(parent)*100./perfectfitness, ''.join(parent)))
iterations = 0
while parent != target:
rate = mutaterate(parent)
iterations += 1
if iterations % 10 == 0: log(iterations,rate,parent)
copies = [ mutate(parent, rate) for _ in C ] + [parent]
parent = max(copies, key=fitness)
print (log(iterations,rate,parent))
运行一下,发现这段代码是可以运行的,并且能正确地输出结果,但是,给我的第一感觉是,这段代码有些凌乱,对于刚入门的同学来说,可能会看不懂,因此,在我的理解范围内,我用这篇文章对这段代码做一些注释,可能会有解释的不够好的地方,还请各位朋友帮我指出错误。
from string import ascii_lowercase # 导入小写字母
from random import choice, random
首先是第一行,导入的资源包,这是string模块,可能不是经常用的原因,第一眼见到他的时候会有些陌生:
可以看出,输出的结果是小写字母:‘abcdefghijklmnopqrstuvwxyz’
继续往下,既然是遗传算法,于是我写成了一个类:
class GA(object):
def __init__(self):
self.target = list("hello world") # 目标
self.charset = ascii_lowercase + ' ' # 字符集
self.parent = [choice(self.charset) for _ in range(len(self.target))] # ’_’ 是一个循环标志
self.minmutaterate = 0.09
self.perfectfitness = len(self.target)
- self.target里存放的是想要输出的结果,大家可以更改里面的内容
- self.charset里存放的是一个大集合,这个大集合里面必须要有self.target这个小集合里需要的元素
- self.parent会在上面的大集合里选出n个元素,这个n的大小取决于输出结果。接下来,for循环里用了一个下划线,其实 ’_’ 是一个循环标志,也可以用i,j 等其他字母代替,循环中不会用到,起到的是循环此数的作用
- self.minmutaterate = 0.09我理解为变异的概率
- self.perfectfitness其实就是预期输出内容的长度
下面就是四个自定义函数:
def fitness(self, trial):
return sum(t == h for t, h in zip(trial, self.target))
可以看出,这个函数应该是求匹配度用的,可以用来检验输出内容是否与预期输出内容匹配。
def mutaterate(self, parent): # 变异
return 1.0 - (1.0 * (self.perfectfitness - self.fitness(parent)) / self.perfectfitness * (1.0 - self.minmutaterate))
def mutate(self, parent, rate):
return [(ch if random() <= rate else choice(self.charset)) for ch in parent]
这两个是变异操作的函数,是该程序的核心部分,对parent这个集合里的元素进行调整。但是具体为什么要这样写,我还没有看懂…
def log(self, iterations, rate, parent): #日志打印
print("#%-4i, rate: %4.3f, fitness: %4.1f%%, '%s'" %
(iterations, rate, self.fitness(parent) * 100. / self.perfectfitness, ''.join(parent)))
最后一个函数其实就是用来打印算法结果的:
最后是主函数:
def main():
ga = GA()
iterations = 0 # 迭代次数,计数器
while ga.parent != ga.target:
rate = ga.mutaterate(ga.parent)
iterations += 1
if iterations % 10 == 0:
ga.log(iterations, rate, ga.parent)
copies = [ga.mutate(ga.parent, rate) for _ in range(100)] + [ga.parent]
# print(copies)
ga.parent = max(copies, key=ga.fitness)
print(ga.log(iterations, rate, ga.parent))
if __name__ == '__main__':
main()
大致意思是,用一个while循环,让parent里的元素不断朝着目标变异,知道和目标完全相同为止。
以上就是我对该程序的简单理解,如果有理解不到位的地方,还请大家指出!一下是我改进的全部代码:
from string import ascii_lowercase # 导入小写字母'abcdefghijklmnopqrstuvwxyz'
from random import choice, random
class GA(object):
def __init__(self):
self.target = list("hello world") # 目标
self.charset = ascii_lowercase + ' ' # 字符集
self.parent = [choice(self.charset) for _ in range(len(self.target))] # ’_’ 是一个循环标志,也可以用i,j 等其他字母代替,循环中不会用到,起到的是循环此数的作用
self.minmutaterate = 0.09
self.perfectfitness = len(self.target)
def fitness(self, trial):
return sum(t == h for t, h in zip(trial, self.target))
def mutaterate(self, parent): # 变异
return 1.0 - (1.0 * (self.perfectfitness - self.fitness(parent)) / self.perfectfitness * (1.0 - self.minmutaterate))
def mutate(self, parent, rate):
return [(ch if random() <= rate else choice(self.charset)) for ch in parent]
def log(self, iterations, rate, parent): #日志打印
print("#%-4i, rate: %4.3f, fitness: %4.1f%%, '%s'" %
(iterations, rate, self.fitness(parent) * 100. / self.perfectfitness, ''.join(parent)))
def main():
ga = GA()
iterations = 0 # 迭代次数,计数器
while ga.parent != ga.target:
rate = ga.mutaterate(ga.parent)
iterations += 1
if iterations % 10 == 0:
ga.log(iterations, rate, ga.parent)
copies = [ga.mutate(ga.parent, rate) for _ in range(100)] + [ga.parent]
# print(copies)
ga.parent = max(copies, key=ga.fitness)
print(ga.log(iterations, rate, ga.parent))
if __name__ == '__main__':
main()