本文轉(zhuǎn)載至知乎ID:Charles(白露未晞)知乎個(gè)人專欄
本文轉(zhuǎn)載至知乎ID:Charles(白露未晞)知乎個(gè)人專欄
下載W3Cschool手機(jī)App,0基礎(chǔ)隨時(shí)隨地學(xué)編程>>戳此了解
導(dǎo)語
日子真是...
發(fā)現(xiàn)不知不覺又好多天沒發(fā)文章了。
恰巧看到一個(gè)關(guān)于遺傳算法的很有意思的應(yīng)用,利用遺傳算法擬合圖像,于是過來分享一波。
讓我們愉快地開始吧~~~
相關(guān)文件
百度網(wǎng)盤下載鏈接: https://pan.baidu.com/s/1VMyY7u2C9Zq0vlMJZE1GSw
密碼: ec77
開發(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
原理簡介
改編參考資料中的故事:
很久很久以前,海岸邊生活著一群扇貝,它們衣食不愁,有房有車。但好景不長,人類的到來打破了它們原本無憂無慮的生活。
每隔一段時(shí)間,人類就會(huì)挖走它們之中的一部分。不過,這些人不喜歡貝殼花紋長得像哈士奇的扇貝,所以他們總是選擇那些長得比較不像哈士奇的扇貝。
這種狀況持續(xù)了好幾萬年。這個(gè)時(shí)候,神奇的事情發(fā)生了:所有的扇貝貝殼上都印著哈士奇!
遺傳算法——元啟發(fā)式算法之一:
首先致敬一波達(dá)爾文?
簡單而言,遺傳算法模擬了大自然中種群在選擇壓力下的演化過程,從而得到了對應(yīng)問題的近似解。
具體而言,就是生物體長什么樣子很大程度上是由染色體上的基因決定的。如果我們利用n個(gè)多邊形組成一只哈士奇的話,我們同樣也可以認(rèn)為哈士奇長什么樣子由這些多邊形的具體位置和顏色決定,也就是說這些多邊形可以被看作是哈士奇的“基因”。
當(dāng)然,需要注意的是,這個(gè)算法得到的只是問題的近似解而非精確解,且存在基因過早同一化等問題。
來自http://xkcd.com/534/的冷笑話:
算法設(shè)計(jì):
遺傳算法只是一個(gè)框架,對于具體問題當(dāng)然需要設(shè)計(jì)具體的算法。
時(shí)間關(guān)系,本次算法設(shè)計(jì)一切從簡。
Step1:
隨機(jī)生成100幅與原始圖像大小相同的噪聲圖像。
Step2:
種群變異(變異概率50%),即在100幅生成的圖像上加一些隨機(jī)噪聲。
Step3:
計(jì)算與原始圖像的差異度。計(jì)算公式為:
Step4:
保留與原始圖像差異度較低的生成圖像,并讓它們交叉融合生成新的圖像以使得種群的數(shù)量保持不變。
Step5:
循環(huán)執(zhí)行Step2-4。
具體實(shí)現(xiàn)過程詳見相關(guān)文件中的源代碼。
使用演示
在cmd窗口運(yùn)行Genetic.py文件即可。
部分參數(shù)解釋:
以chrome瀏覽器圖標(biāo)(大小為30×30)為例:
【圖像較大的話時(shí)間花銷比較大T_T】
可以看到還是有那么點(diǎn)意思的。
有興趣的同學(xué)可以多跑幾輪,看看幾萬輪之后的結(jié)果是什么,時(shí)間關(guān)系我就不繼續(xù)跑了。
更多
參考資料中的第一個(gè)鏈接是一個(gè)遺傳算法擬合蒙娜麗莎的在線測試系統(tǒng)。
其最終的結(jié)果為:
當(dāng)然還有其他圖案的:
emmm,比我的結(jié)果好很多的樣子。
有空再優(yōu)化我自己寫的東西吧~~~