现在有这样一个游戏,准备10枚(当然,也可以更多)硬币,正反两面分别被涂上了黄色和绿色,然后把这些硬币都扔在桌子上。
现在把你的眼睛蒙上,然后去翻硬币,赢的条件是把所有硬币都翻到绿色一面朝上。
当你翻正确的时候,旁边人会告诉你,你翻对了;而你翻错了的时候,他会告诉你错了,并且把这个硬币翻回去……当然,他还需要把这个硬币移到另外的地方,防止你能够马上改正错误。
然后两个人轮流玩,以此比较,谁的次数最少。
在这种规则下,区区十枚硬币,极有可能要翻几十次甚至几百次(翻对了的有可能又会被翻回去)……实在是一场坚苦卓绝的比赛。
这也是本节所要给大家介绍的算法和实现。导入需要的包:
import numpy,datetime,random
import matplotlib.pyplot as plt
还是一样,先定义遗传算法的各种基础组件,先是定义一个健壮性验证函数:
def get_fitness(genes):
return genes.count(1)
定义一个类,用来存储当前进化到的这一代物种的染色体和健壮性:
class Chromosome:
def __init__(self, genes, fitness):
self.Genes = genes
self.Fitness = fitness
继续定义变异、进化的方法:从父本里面随机选择一个基因进行变化,生成下一代种群
def mutate(parent):
childGenes = parent.Genes
index = random.randrange(0, len(parent.Genes))
newGene, alternate = random.sample([1,0], 2)
childGenes[index] = alternate if newGene == childGenes[index] else newGene
fitness = get_fitness(childGenes)
return Chromosome(childGenes, fitness)
这是一个显示的方法,用来显示前15个元素和最后15个,不100个元素会显示很长:
def display(candidate, startTime):
timeDiff = datetime.datetime.now() - startTime
print("{}...{}\t{:3.2f}\t{}".format(
''.join(map(str, candidate.Genes[:15])),
''.join(map(str, candidate.Genes[-15:])),
candidate.Fitness,
timeDiff))
然后就是执行方法了:首先初始化一个祖先……用numpy的randint来生成一个100个元素的0和1的整数数组。如果这个祖先函数直接就全部是1,就不用玩了……之后进入进化,一直进化到全部都是1为止,其中num是我添加在里面的计数器。
def get_best():
random.seed()
startTime = datetime.datetime.now()
c1 = numpy.random.randint(0,2,(100)).tolist()
bestParent = Chromosome(c1,get_fitness(c1))
if bestParent.Fitness >= 100:
return bestParent
num = 0
while True:
num +=1
child = mutate(bestParent)
if bestParent.Fitness >= child.Fitness:
continue
display(bestParent,startTime)
if child.Fitness >= 100:
display(child,startTime)
return (child,num)
bestParent = child
执行函数:
b = get_best()
print(b[0].Fitness,",",b[1])
执行结果如下:
111110111000110...110111100101100 47.00 0:00:00
111110111000110...110111100101100 55.00 0:00:00
111110111000110...110111100101100 56.00 0:00:00
111110111000110...110111100101100 57.00 0:00:00.000997
111110111000110...110111100101100 58.00 0:00:00.000997
111110111000110...110111110101100 59.00 0:00:00.000997
……
111111111011111...111111111111111 96.00 0:00:00.012965
111111111111111...111111111111111 97.00 0:00:00.013963
111111111111111...111111111111111 98.00 0:00:00.014960
111111111111111...111111111111111 99.00 0:00:00.016993
111111111111111...111111111111111 100.00 0:00:00.016993
100 , 414
一次执行,用了0.16秒,总共翻了414次硬币,才全部翻正确(因为随机的关系,每次执行,结果会不一样)
现在我们来迭代1000次,看看统计信息:
n = []
for i in range(1000):
n.append(get_best()[1])
plt.hist(n)
结果如下:
可以看见,一般说,最少需要200次,而最多需要1000多次,才能全部翻对,平均也得451次才能完成,可见真是一个艰难的游戏。
但是,我们要是修改一下游戏规则:
比如,再你翻对一枚硬币的时候,就把这枚硬币从桌子上拿下来。这时候桌子上剩下的就是你翻错的,或者还没有翻的硬币了,这样看起来是不是就容易很多了啊。因为你不用重复去翻你已经翻对过的硬币了。
具体的转换到算法上,就是要记录你翻对过的硬币在哪里——翻对过,从桌上已经拿掉了,就等于你不用再去翻一次了,下面来看看这种规则下的游戏:
修改基因进化变异函数,传入一个记录数组,如果你随机的索引已经是翻过且正确的(拿掉的硬币,则重新选择一个索引)
def mutate(parent,idxlist):
childGenes = parent.Genes[:]
while True:
index = random.randrange(0, len(parent.Genes),1)
if index in idxlist:
pass
else:
break
newGene, alternate = random.sample([0,1], 2)
childGenes[index] = alternate if newGene == childGenes[index] else newGene
fitness = get_fitness(childGenes)
return (Chromosome(childGenes, fitness),index)
开始运行之前,设定一个list,用来存储拿掉的那些硬币
def get_best():
oneIndex = []
random.seed()
startTime = datetime.datetime.now()
c1 = numpy.random.randint(0,2,(100)).tolist()
bestParent = Chromosome(c1,get_fitness(c1))
if bestParent.Fitness >= 100:
return bestParent
num = 0
while True:
num +=1
child,idx = mutate(bestParent,oneIndex)
if bestParent.Fitness >= child.Fitness:
continue
oneIndex.append(idx)
#display(bestParent,startTime)
if child.Fitness >= 100:
display(child,startTime)
return (child,num)
bestParent = child
display(bestParent,startTime)
执行1000次之后,结果如下:
可以看见,效果显著——平均仅需要274次,就能够完成全部硬币的翻面。
这种算法,在游戏中经常用到,你不用管开局是什么样子的,只需要知道你这样做是更好还是更坏,就可以最终达到最佳效果。
联系客服