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