今天是教師節(jié)，老師們，教師節(jié)快樂！
遺傳算法初嘗，火狐像素進(jìn)化
前言
作為本科生物出生的我，對遺傳算法好奇已久。再后來看到科學(xué)松鼠會的一篇文章遺傳算法：內(nèi)存中的進(jìn)化，對其使用三角形進(jìn)化成火狐，感到十分有趣。于是我準(zhǔn)備也寫一個(gè)程序來生成一個(gè)火狐。
這里我不使用三角形來進(jìn)化，而是直接使用像素。多個(gè)三角形拼成一個(gè)火狐，實(shí)際也是是三角形內(nèi)的像素顏色組合成火狐的樣子。所以，我決定直接使用像素生成一個(gè)火狐。
背景知識
簡略說一下遺傳算法以及我寫的程序邏輯。
遺傳算法：初始化種群后，種群間的個(gè)體之間進(jìn)行交叉(可能發(fā)生變異)繁殖出下一代，然后優(yōu)勝劣汰，最差勁的部分個(gè)體被淘汰，存活的個(gè)體之間繼續(xù)進(jìn)行交叉(變異)繁殖。直到種群中個(gè)體符合某個(gè)條件終止。
-
遺傳算法組成：
- 編碼：為便于計(jì)算機(jī)編程，個(gè)體基因需要以合適編碼方式進(jìn)行編碼。(程序中直接使用圖片像素色值進(jìn)行編碼)
- 群體：多個(gè)個(gè)體組成群體。(程序中，就是多個(gè)圖片組成群體)
- 適應(yīng)度函數(shù)：用于判定個(gè)體的適應(yīng)度，是否適合存活。(程序中，就是圖片與火狐圖片進(jìn)行像素色值的比較)
- 選擇：淘汰適應(yīng)度差的個(gè)體之后，選擇剩下的部分個(gè)體進(jìn)行交叉繁殖(程序直接隨機(jī)選擇n對個(gè)體)
- 交叉：即父母各提供部分基因繁殖組成出下一代。(程序中就是兩圖片各自提供一半像素組成新圖片)
- 變異：為了種群基因多樣性，繁殖個(gè)體可能發(fā)生變異。(程序中表現(xiàn)為部分像素色值發(fā)生變化)
程序邏輯：
根據(jù)火狐圖片大小，生成P張相同大小，但像素色值隨機(jī)的圖片種群，然后用適應(yīng)度函數(shù)給每個(gè)圖片個(gè)體打分。然后隨機(jī)選擇n對父母，父母雙方各提供一半像素組成新的后代圖片。后代進(jìn)行適應(yīng)度打分后，根據(jù)適應(yīng)度分?jǐn)?shù)將種群中適應(yīng)度分?jǐn)?shù)最不好的個(gè)體淘汰以維持種群大小。然后進(jìn)行新一輪的交叉繁殖變異淘汰，直到合適的圖片個(gè)體產(chǎn)生或進(jìn)化代數(shù)結(jié)束。
圖片
這里使用圖片是一張RGBA四通道的圖片，R表示紅色，G表示綠色，B表示藍(lán)色，A表示不透明度。R,G,B三個(gè)色值的不同大小組合疊加，幾乎涵蓋人眼感知的所有顏色。R,G,B,A四個(gè)取值都在0-255之間（在matplotlib中使用的話，取值范圍被縮放到0-1之間了）
而一張圖片由許多像素組成，不同像素有著各自的色彩數(shù)值，對于RGBA圖來說，一個(gè)像素點(diǎn)顏色就由這四個(gè)數(shù)值（r,g,b,a）確定。比如，用matplotlib讀取一張500*500像素大小的圖片
>>> img = mpimg.imread('./ff.png')
>>> img.shape ## 500*500的像素大小，每個(gè)像素由（r,g,b,a）4個(gè)色值確定顏色
(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個(gè)像素點(diǎn)則：
>>> plt.imshow(img[list(range(250)),:][:,list(range(250))])
所以我們的目標(biāo)就是由一些像素rgba數(shù)值隨機(jī)生成的圖片進(jìn)化成一個(gè)火狐形狀的圖片。
結(jié)果
最后效果我感覺還行，雖然跟原圖比的話，還是差了一些。程序運(yùn)行后，其實(shí)很快就能看到大致雛形，但是細(xì)節(jié)上就不行了。
上面圖片中，g后面的數(shù)字表示代數(shù)，最后一個(gè)"_"后面的額數(shù)字就是相似度分?jǐn)?shù)了，可以看到，一開始分值是幾百上千的下降，到后面就是個(gè)位數(shù)的下降了。
我在B站上上傳了個(gè)像素進(jìn)化過程的動(dòng)畫，感興趣的可以去看看小視頻
代碼組成講解
程序運(yùn)行環(huán)境：
- Win10
- Python3 (需要安裝兩個(gè)庫：matplotlib、numpy）
目標(biāo)圖片
編碼
我們直接使用像素色值作為基因。那么，初始化一個(gè)個(gè)體的所有基因，則可以第一個(gè)函數(shù)：
def init_genes(id, x, y, z):
"""初始化個(gè)體基因
:param id: 隨機(jī)數(shù)種子，與其他初始化相區(qū)別
:param x: 圖片高
:param y: 圖片長
:param z: 4表示rgba, 3表示rgb
"""
np.random.seed(id)
pixel = np.random.random((x, y, z))
return pixel
通過隨機(jī)生成一個(gè)維數(shù)（x, y, z）大小的的ndarray，其中數(shù)值在[0，1)之間。比如生成一個(gè)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]]])
適應(yīng)度函數(shù)
由于我們的目的簡單，就是讓進(jìn)化的個(gè)體圖片與目標(biāo)圖片盡量相似。那么適應(yīng)度函數(shù)就直接用進(jìn)化個(gè)體和目標(biāo)進(jìn)行比較，計(jì)算得分。
def comp_similarity(indv, target):
"""計(jì)算相似度，計(jì)算兩個(gè)array的差值平方和，即越小，相似度越大。
:param indv: 圖片像素
:param target: 目標(biāo)圖片像素
"""
score = np.sum(np.square((indv - target)))
return score
初始化群體
根據(jù)目標(biāo)圖片的大小，初始化群體個(gè)體的大小，并根據(jù)目標(biāo)圖片像素，計(jì)算群體個(gè)體與目標(biāo)圖片的相似度。
def init_indv(id, x, y, z, target):
"""初始化個(gè)體數(shù)據(jù)，初始話像素基因，與目標(biāo)相似度分?jǐn)?shù)
:param id: 一個(gè)數(shù)字，與其他初始化相區(qū)別
:param x: 圖片高
:param y: 圖片長
:param z: 4表示rgba, 3表示rgb
:param target: 目標(biāo)像素
"""
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):
"""初始化群體數(shù)據(jù)
:param target: 目標(biāo)像素
:param p: 群體大小
:param jobs: 進(jìn)程數(shù)
"""
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
繁衍，變異下一代
這里變異的話，我認(rèn)為是比較trick的一個(gè)地方。一開始，我是直接一個(gè)一個(gè)的像素點(diǎn)的色值數(shù)據(jù)突變，不過我發(fā)現(xiàn)進(jìn)化太慢。
后來我想到，正常圖片的話，一個(gè)像素點(diǎn)附近的像素，也基本上是相同的像素。于是呢，突變時(shí)，我就隨機(jī)選擇一些像素點(diǎn)，以它為中心，周圍n個(gè)像素點(diǎn)的色值都設(shè)置成該像素的色值，這樣，我發(fā)現(xiàn)像素可能能快速成型，但是，后面也是沒法進(jìn)化了，因?yàn)閷⒅車O(shè)置一樣的色值，缺少多樣性，導(dǎo)致后期很難進(jìn)化。
然后，我就想設(shè)成一樣的缺少多樣性，那就設(shè)成不一樣的，以當(dāng)前像素色值為均值，標(biāo)準(zhǔn)差設(shè)置0.05（也可以設(shè)成其他）隨機(jī)生成正太分布的數(shù)值了。這樣突變多樣性就就有了。
def breed(p1, p2, mutation, width=5):
"""初始化群體數(shù)據(jù)
:param p1: 個(gè)體1
:param p2: 個(gè)體2
:param mutation: 突變率
:param width: 變異寬度
"""
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
選擇，交叉
每一代，隨機(jī)選擇n對個(gè)體進(jìn)行交叉繁殖，繁殖下的個(gè)體后，對整個(gè)種群個(gè)體的適應(yīng)度進(jìn)行比較，選擇出最差的部分個(gè)體淘汰，以維持種群大小一致。
這里我處理的簡單，就不放代碼了。
全部代碼：
見代碼
