今天是教师节，老师们，教师节快乐！
遗传算法初尝，火狐像素进化
前言
作为本科生物出生的我，对遗传算法好奇已久。再后来看到科学松鼠会的一篇文章遗传算法：内存中的进化，对其使用三角形进化成火狐，感到十分有趣。于是我准备也写一个程序来生成一个火狐。
这里我不使用三角形来进化，而是直接使用像素。多个三角形拼成一个火狐，实际也是是三角形内的像素颜色组合成火狐的样子。所以，我决定直接使用像素生成一个火狐。
背景知识
简略说一下遗传算法以及我写的程序逻辑。
遗传算法：初始化种群后，种群间的个体之间进行交叉(可能发生变异)繁殖出下一代，然后优胜劣汰，最差劲的部分个体被淘汰，存活的个体之间继续进行交叉(变异)繁殖。直到种群中个体符合某个条件终止。
-
遗传算法组成：
- 编码：为便于计算机编程，个体基因需要以合适编码方式进行编码。(程序中直接使用图片像素色值进行编码)
- 群体：多个个体组成群体。(程序中，就是多个图片组成群体)
- 适应度函数：用于判定个体的适应度，是否适合存活。(程序中，就是图片与火狐图片进行像素色值的比较)
- 选择：淘汰适应度差的个体之后，选择剩下的部分个体进行交叉繁殖(程序直接随机选择n对个体)
- 交叉：即父母各提供部分基因繁殖组成出下一代。(程序中就是两图片各自提供一半像素组成新图片)
- 变异：为了种群基因多样性，繁殖个体可能发生变异。(程序中表现为部分像素色值发生变化)
-
程序逻辑：
根据火狐图片大小，生成P张相同大小，但像素色值随机的图片种群，然后用适应度函数给每个图片个体打分。然后随机选择n对父母，父母双方各提供一半像素组成新的后代图片。后代进行适应度打分后，根据适应度分数将种群中适应度分数最不好的个体淘汰以维持种群大小。然后进行新一轮的交叉繁殖变异淘汰，直到合适的图片个体产生或进化代数结束。
图片
这里使用图片是一张RGBA四通道的图片，R表示红色，G表示绿色，B表示蓝色，A表示不透明度。R,G,B三个色值的不同大小组合叠加，几乎涵盖人眼感知的所有颜色。R,G,B,A四个取值都在0-255之间（在matplotlib中使用的话，取值范围被缩放到0-1之间了）
而一张图片由许多像素组成，不同像素有着各自的色彩数值，对于RGBA图来说，一个像素点颜色就由这四个数值（r,g,b,a）确定。比如，用matplotlib读取一张500*500像素大小的图片
>>> img = mpimg.imread('./ff.png')
>>> img.shape ## 500*500的像素大小，每个像素由（r,g,b,a）4个色值确定颜色
(500, 500, 4)
>>> img
array([[[1., 1., 1., 0.],
[1., 1., 1., 0.],
[1., 1., 1., 0.],
...,
[1., 1., 1., 0.],
[1., 1., 1., 0.],
[1., 1., 1., 0.]],
[[1., 1., 1., 0.],
[1., 1., 1., 0.],
[1., 1., 1., 0.],
...,
[1., 1., 1., 0.],
[1., 1., 1., 0.],
[1., 1., 1., 0.]]], dtype=float32)
>>> plt.imshow(img)
若长宽各取250个像素点则：
>>> plt.imshow(img[list(range(250)),:][:,list(range(250))])
所以我们的目标就是由一些像素rgba数值随机生成的图片进化成一个火狐形状的图片。
结果
最后效果我感觉还行，虽然跟原图比的话，还是差了一些。程序运行后，其实很快就能看到大致雏形，但是细节上就不行了。
上面图片中，g后面的数字表示代数，最后一个"_"后面的额数字就是相似度分数了，可以看到，一开始分值是几百上千的下降，到后面就是个位数的下降了。
我在B站上上传了个像素进化过程的动画，感兴趣的可以去看看小视频
代码组成讲解
程序运行环境：
- Win10
- Python3 (需要安装两个库：matplotlib、numpy）
目标图片
编码
我们直接使用像素色值作为基因。那么，初始化一个个体的所有基因，则可以第一个函数：
def init_genes(id, x, y, z):
"""初始化个体基因
:param id: 随机数种子，与其他初始化相区别
:param x: 图片高
:param y: 图片长
:param z: 4表示rgba, 3表示rgb
"""
np.random.seed(id)
pixel = np.random.random((x, y, z))
return pixel
通过随机生成一个维数（x, y, z）大小的的ndarray，其中数值在[0，1)之间。比如生成一个500*500像素大小的rgba图，则：
>>> img = init_genes(1, 500, 500, 4)
>>> img.shape
(500, 500, 4)
>>> img
array([[[4.17022005e-01, 7.20324493e-01, 1.14374817e-04, 3.02332573e-01],
[1.46755891e-01, 9.23385948e-02, 1.86260211e-01, 3.45560727e-01],
[3.96767474e-01, 5.38816734e-01, 4.19194514e-01, 6.85219500e-01],
...,
[2.54232355e-01, 8.40863542e-02, 8.64144095e-01, 4.47898916e-01],
[5.61786261e-01, 7.36710958e-01, 7.96488867e-01, 4.47508139e-01],
[1.84127556e-01, 8.28732852e-01, 3.09979598e-02, 9.46728270e-01]],
...,
[[5.68421936e-01, 3.39263061e-01, 4.29541410e-02, 4.75883106e-01],
[3.49561943e-02, 6.97079682e-01, 2.07790075e-01, 2.31854801e-01],
[3.56860024e-01, 7.54193790e-01, 5.53116793e-01, 5.94979902e-01],
...,
[4.51152445e-01, 1.17319322e-01, 6.25857591e-01, 6.13930562e-01],
[1.19037827e-01, 1.30051715e-01, 6.84848503e-01, 4.96384839e-02],
[4.26193435e-01, 4.93233752e-01, 1.08809709e-01, 3.70251829e-01]]])
适应度函数
由于我们的目的简单，就是让进化的个体图片与目标图片尽量相似。那么适应度函数就直接用进化个体和目标进行比较，计算得分。
def comp_similarity(indv, target):
"""计算相似度，计算两个array的差值平方和，即越小，相似度越大。
:param indv: 图片像素
:param target: 目标图片像素
"""
score = np.sum(np.square((indv - target)))
return score
初始化群体
根据目标图片的大小，初始化群体个体的大小，并根据目标图片像素，计算群体个体与目标图片的相似度。
def init_indv(id, x, y, z, target):
"""初始化个体数据，初始话像素基因，与目标相似度分数
:param id: 一个数字，与其他初始化相区别
:param x: 图片高
:param y: 图片长
:param z: 4表示rgba, 3表示rgb
:param target: 目标像素
"""
pixel = init_genes(id, x, y, z)
score = comp_similarity(pixel, target)
indv = {}
indv['score'] = score
indv["gene"] = pixel
return indv
def init_pop(target, p=15, jobs=5):
"""初始化群体数据
:param target: 目标像素
:param p: 群体大小
:param jobs: 进程数
"""
x, y, z = target.shape
f_init = partial(init_indv, x=x, y=y, z=z,target=target)
with Pool(jobs) as pl:
for i,v in enumerate(pl.map(f_init, list(range(p)))):
data_pool[i] = v
繁衍，变异下一代
这里变异的话，我认为是比较trick的一个地方。一开始，我是直接一个一个的像素点的色值数据突变，不过我发现进化太慢。
后来我想到，正常图片的话，一个像素点附近的像素，也基本上是相同的像素。于是呢，突变时，我就随机选择一些像素点，以它为中心，周围n个像素点的色值都设置成该像素的色值，这样，我发现像素可能能快速成型，但是，后面也是没法进化了，因为将周围设置一样的色值，缺少多样性，导致后期很难进化。
然后，我就想设成一样的缺少多样性，那就设成不一样的，以当前像素色值为均值，标准差设置0.05（也可以设成其他）随机生成正太分布的数值了。这样突变多样性就就有了。
def breed(p1, p2, mutation, width=5):
"""初始化群体数据
:param p1: 个体1
:param p2: 个体2
:param mutation: 突变率
:param 变异宽度
"""
x, y, z = p1.shape
new_p = p1.copy()
x1_idx = random.sample(range(x), int(x/2))
y1_idx = random.sample(range(y), int(y/2))
x2_idx = list(set(range(x)) - set(x1_idx))
y2_idx = list(set(range(y)) - set(y1_idx))
temp1 = p2[x1_idx]
temp1[:,y1_idx] = p1[x1_idx][:, y1_idx]
new_p[x1_idx] = temp1
temp2 = p2[x2_idx]
temp2[:,y2_idx] = p1[x2_idx][:, y2_idx]
new_p[x2_idx] = temp2
m_x = random.sample(range(x), int(x*mutation))
m_y = random.sample(range(y), int(x*mutation))
indv_m = new_p.copy()
for i,j in zip(m_x, m_y):
channel = random.randint(0,z-1)
center_p = new_p[i,j][channel]
sx = list(range(max(0, i-width), min(i+width, x-1)))
sy = list(range(max(0, j-width), min(j+width, y-1)))
mtemp = indv_m[sx]
normal_rgba = np.random.normal(center_p,.01, size=mtemp[:,sy].shape[:2])
normal_rgba[normal_rgba>1] = 1
normal_rgba[normal_rgba<0] = 0
mtemp[:,sy, channel] = normal_rgba
indv_m[sx] = mtemp
return new_p, indv_m
选择，交叉
每一代，随机选择n对个体进行交叉繁殖，繁殖下的个体后，对整个种群个体的适应度进行比较，选择出最差的部分个体淘汰，以维持种群大小一致。
这里我处理的简单，就不放代码了。
全部代码：
见代码
听说手机好的人才能扫上这个进化成功锦鲤二维码。
