本文轉(zhuǎn)載至知乎ID：Charles（白露未晞）知乎個(gè)人專欄

下載W3Cschool手機(jī)App，0基礎(chǔ)隨時(shí)隨地學(xué)編程>>戳此了解

導(dǎo)語(yǔ)

日子真是...

發(fā)現(xiàn)不知不覺(jué)又好多天沒(méi)發(fā)文章了。

恰巧看到一個(gè)關(guān)于遺傳算法的很有意思的應(yīng)用，利用遺傳算法擬合圖像，于是過(guò)來(lái)分享一波。

讓我們愉快地開(kāi)始吧~~~

相關(guān)文件

百度網(wǎng)盤(pán)下載鏈接: https://pan.baidu.com/s/1VMyY7u2C9Zq0vlMJZE1GSw

密碼: ec77

開(kāi)發(fā)工具

Python版本：3.6.4

相關(guān)模塊：

PIL模塊；

以及一些python自帶的模塊。

環(huán)境搭建

安裝Python并添加到環(huán)境變量，pip安裝需要的相關(guān)模塊即可。

參考資料

50個(gè)半透明多邊形重現(xiàn)蒙娜麗莎：

http://alteredqualia.com/visualization/evolve/

科學(xué)松鼠會(huì)《遺傳算法》：

http://songshuhui.net/archives/10462

原理簡(jiǎn)介

改編參考資料中的故事：

很久很久以前，海岸邊生活著一群扇貝，它們衣食不愁，有房有車。但好景不長(zhǎng)，人類的到來(lái)打破了它們?cè)緹o(wú)憂無(wú)慮的生活。

每隔一段時(shí)間，人類就會(huì)挖走它們之中的一部分。不過(guò)，這些人不喜歡貝殼花紋長(zhǎng)得像哈士奇的扇貝，所以他們總是選擇那些長(zhǎng)得比較不像哈士奇的扇貝。

這種狀況持續(xù)了好幾萬(wàn)年。這個(gè)時(shí)候，神奇的事情發(fā)生了：所有的扇貝貝殼上都印著哈士奇！

遺傳算法——元啟發(fā)式算法之一：

首先致敬一波達(dá)爾文？

簡(jiǎn)單而言，遺傳算法模擬了大自然中種群在選擇壓力下的演化過(guò)程，從而得到了對(duì)應(yīng)問(wèn)題的近似解。

具體而言，就是生物體長(zhǎng)什么樣子很大程度上是由染色體上的基因決定的。如果我們利用n個(gè)多邊形組成一只哈士奇的話，我們同樣也可以認(rèn)為哈士奇長(zhǎng)什么樣子由這些多邊形的具體位置和顏色決定，也就是說(shuō)這些多邊形可以被看作是哈士奇的“基因”。

當(dāng)然，需要注意的是，這個(gè)算法得到的只是問(wèn)題的近似解而非精確解，且存在基因過(guò)早同一化等問(wèn)題。

來(lái)自http://xkcd.com/534/的冷笑話：

算法設(shè)計(jì)：

遺傳算法只是一個(gè)框架，對(duì)于具體問(wèn)題當(dāng)然需要設(shè)計(jì)具體的算法。

時(shí)間關(guān)系，本次算法設(shè)計(jì)一切從簡(jiǎn)。

Step1：

隨機(jī)生成100幅與原始圖像大小相同的噪聲圖像。

Step2：

種群變異（變異概率50%），即在100幅生成的圖像上加一些隨機(jī)噪聲。

Step3：

計(jì)算與原始圖像的差異度。計(jì)算公式為：

Step4：

保留與原始圖像差異度較低的生成圖像，并讓它們交叉融合生成新的圖像以使得種群的數(shù)量保持不變。

Step5：

循環(huán)執(zhí)行Step2-4。

具體實(shí)現(xiàn)過(guò)程詳見(jiàn)相關(guān)文件中的源代碼。

使用演示

在cmd窗口運(yùn)行Genetic.py文件即可。

部分參數(shù)解釋：

以chrome瀏覽器圖標(biāo)（大小為30×30）為例：

【圖像較大的話時(shí)間花銷比較大T_T】

可以看到還是有那么點(diǎn)意思的。

有興趣的同學(xué)可以多跑幾輪，看看幾萬(wàn)輪之后的結(jié)果是什么，時(shí)間關(guān)系我就不繼續(xù)跑了。

更多

參考資料中的第一個(gè)鏈接是一個(gè)遺傳算法擬合蒙娜麗莎的在線測(cè)試系統(tǒng)。

其最終的結(jié)果為：

當(dāng)然還有其他圖案的：

emmm，比我的結(jié)果好很多的樣子。

有空再優(yōu)化我自己寫(xiě)的東西吧~~~