遺傳演算法有哪些有趣應用?

類似於這樣的http://www.boxcar2d.com/

我其實想問的問題和下面這個帖子一樣,但是這個帖子裡面沒有太多有意義的推薦:http://stackoverflow.com/questions/4824832/whats-a-genetic-algorithm-that-would-produce-interesting-surprising-results-and
到知乎上問問有沒有其他有趣的東西。


用在NLG(自然語言生成)技術中。如下面自動生成的宋詞:

清平樂
相逢縹緲,窗外又拂曉。長憶清弦弄淺笑,只恨人間花少。
風雨重陽又過,登高多少黃昏。黃菊不待清尊,相思飄落無痕。

西江月
飲酒開懷酣暢,洞簫笑語尊前。欲看盡歲歲年年,悠然輕雲一片。
賞美景開新釀,人生堪笑歡顏。故人何處向天邊,醉里時光漸漸。


前幾天無聊的時候寫過幾個遺傳演算法的 Mathematica 程序。

1.用遺傳演算法進行互動式作曲:

寫著玩的程序,通過自己試聽,給隨機產生的音樂評分,然後在進行基因交換,如此迭代,不過效果不是太理想,迭代了N次還是難以入耳。
因為是寫著玩的,就把代碼放上來了:

SoundLever = Table[50, {i, 1, 20}];
SoundGropData =
Table[Table[{RandomInteger[14]*2, RandomInteger[3] + 1}, {j, 1, 10}], {i, 1,
20}];

評價個體:

SoundGrop =
Table[Table[
SoundNote[SoundGropData[[i]][[j]][[1]], SoundGropData[[i]][[j]][[2]]/5,
"Piano"], {j, 1, 10}], {i, 1, 20}];
加權隨機選擇交配對象(允許自交)

RandomSample[SoundLever -&> Table[i, {i, 1, 20}], 2]
RandomChoice[SoundLever -&> Table[i, {i, 1, 20}]]

基因交換:

SwapGe[list1_, list2_, p1_,
p2_] := {Table[
If[Min[{p1, p2}] &<= i &<= Max[{p1, p2}], list2[[i]], list1[[i]]], {i, 1, 10}], Table[ If[Min[{p1, p2}] &<= i &<= Max[{p1, p2}], list1[[i]], list2[[i]]], {i, 1, 10}]} swap = Table[RandomSample[SoundLever -&> Table[i, {i, 1, 20}], 2], {i, 1, 20}];
p1p2 = Table[{RandomInteger[{1, 20}], RandomInteger[{1, 20}]}, {i, 1, 20}];
Sons = Table[
SwapGe[SoundGropData[[swap[[i]][[1]]]], SoundGropData[[swap[[i]][[2]]]],
p1p2[[i]][[1]], p1p2[[i]][[2]]][[1]], {i, 1, 20}];
SoundSons =
Table[Table[
SoundNote[Sons[[i]][[j]][[1]], Sons[[i]][[j]][[2]]/5, "Violin"], {j, 1,
10}], {i, 1, 20}];
Manipulate[Sound[SoundSons[[i]]], {i, 1, 20, 1}]
Manipulate[Sound[SoundSons[[i]]], {i, 1, 20, 1}]

2.用遺傳演算法設計相干光源,使得某一處亮度極大:

這其實也是寫著玩的,不過效果還是挺贊的。
最開始隨機放置相干光源:

我設計的是讓{50,50}處光強儘可能大,隨機生成的並不理想。
經過上百次迭代,其處光強增大了近兩倍:

而光點的位置也更加集中了:

這也是寫著玩的……所以也順便放出代碼:

(*初始化,生成種群*)
Block[{n = 100(*種群數量*), t = 20(*基因長度*)},
GenoGroup =
Table[Table[([CurlyPhi] =
RandomReal[{0, [Pi]}]; {RandomInteger[{1, 20}],
RandomInteger[{1, 100}], 0, 1}), {j, 1, t}], {i, 1, n}];
]

Len[x_, y_, x2_, y2_] :=
If[{x, y} != {x2, y2}, Sqrt[N[(x - x2)^2 + (y - y2)^2]], 1.0]

(*個體的適應度*)
Fitness[[Omega]_, b_, pointlist_, getv_] := Block[
{len = Length[pointlist],
i = getv[[1]], j = getv[[2]]},
Abs[!(
*UnderoverscriptBox[([Sum]), (k = 1), (len)]((N[
*FractionBox[((pointlist[[k]])[[4]]), (b*
Len[i, j, (pointlist[[k]])[[1]], (pointlist[[k]])[[
2]]])]*
*SuperscriptBox[(E), ((-I) (([Omega] b*
Len[i, j, (pointlist[[k]])[[1]], (pointlist[[k]])[[
2]]] + (pointlist[[k]])[[3]])))]])))]
]

(*選取兩個個體交合*)
PickTwoPoints[plist_] :=
Block[
{len = Length[plist],
Onelist = 0},
Onelist = Table[i, {i, 1, len}];
RandomChoice[plist -&> Onelist, 2]
]

(*兩個個體交合,返回子代*)
CrossOver[POne_, PTwo_] := Block[
{len = Length[POne],
ab = {0, 0}},
ab = Sort[RandomInteger[{1, len}, 2]];
Table[If[ab[[1]] &<= i &<= ab[[2]], PTwo[[i]], POne[[i]]], {i, 1, len}] ] Flist = {0}; Do[ (GenoGroup = Block[{plist = Table[Fitness[1, 1, GenoGroup[[i]], {50, 50}], {i, 1, Length[GenoGroup]}]}, Table[ Block[{ab = PickTwoPoints[plist]}, CrossOver[GenoGroup[[ab[[1]]]], GenoGroup[[ab[[2]]]]]], {i, 1, 100}] ]; Flist = Append[Flist, Max[Table[ Fitness[1, 1, GenoGroup[[i]], {50, 50}], {i, 1, Length[GenoGroup]}]]]), {tt, 1, 50}]

3.遺傳演算法處理事件規劃
這個計劃還沒有開始,不過不是寫著玩的了。設計目標是可以處理大學生在學校期間的事件規劃,可以通盤考慮體力、精力、教室移動、爛課對精神的衝擊、是否在思修課上寫作業……等等。

設計完成後,將發布在個人專欄之中。


遺傳演算法可以用來攻擊神經網路
http://arxiv.org/abs/1412.1897
詳細內容自己看論文吧,原理大概如下圖

產生出來的一些圖片

圖片底下是這個圖片被AlexNet識別成了啥。
雖然不是很有用,不過這個東西還是很好玩的,玄學大戰


必須再一次貼出這個:【3D物理引擎實驗】多P補全計劃
利用遺傳演算法解決了人類行走、爬行等動作之謎,看得人迷之感動、熱淚盈眶。




變成

的過程是用遺傳演算法驅動的。———————————————————————————————————————————
項目地址:be5invis/sfdhanautohint · GitHub
捐贈地址:支付寶 13053087127
支持原創?一元也可?有你支持?有我更新


用遺傳演算法的原理寫出李白的詩,從而驗證和預言各種國際大事件。


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


自己用多目標遺傳演算法解決過混合流水車間調度問題,代碼1700行左右,用C++寫的,談不上多有趣吧,主要是為了解決車間生產調度問題。下圖是經過遺傳演算法優化後得到的甘特圖。


HTML5 Genetic Algorithm 2D Car Thingy 這是我今年見過最有意思的一個項目,曾經跑了一周就為了看看到底可以優化到什麼程度.

HTML5 Genetic Algorithm Jumping Kitten 作者之前還有一個訓練小貓jump的project

是個很有趣的人 : )

===================================
原來題目裡面已經提到了第一個,那就推薦一下這隻小貓


curve fitting
尤其是非線性方程,一個不用想太多就可以實行的演算法,只是速度太慢


轉自另一個問題的匿名答案:

Avida:https://github.com/devosoft/avida

一個有關人工生命的實驗,相關論文曾發表在Nature上。

是美國密西根大學做的一個在內存里驗證和研究進化論的模擬器。

相關的論文也很有意思,中心思想是讓程序進化以完成一些比較複雜的操作,可以自己跑一些case,通過進化得出的對問題的解決方案的奇妙程度絕對能震驚到每一個看懂的人。看完後感覺自然內在蘊含的創造力實在太令人驚嘆了。(而且每次跑出的解決方案還都不一樣)


Regex Golf 是一個正則表達式生成競賽。這個競賽給兩堆字元串M和U,要求參數者給出的正則表達式r儘可能地匹配M堆中的字元串,和儘可能地不匹配U堆中的字元串。下圖就是競賽的示意圖。

Bartoli et al. (2014)提出用遺傳演算法解決這個問題。種群一個個體是一顆正則表達式樹,如下圖所示。正則表達樹的葉子節點是一些從M堆字元串抽取的字母和N-grams。正則表達式樹的中間節點是正則表達式的符號,比如「()」、「*」和「?」。

個體對應正則表達式匹配越多M堆字元串,個體適應度應該越大。個體對應正則表達式匹配越多U堆字元串,個體適應度應該越小。因此可以直接用(匹配M堆字元串數量-匹配U堆字元串數量)作為適應度。但這樣的話,得到的正則表達式的長度會很長。為了控制正則表達式長度,適應度應該懲罰長的正則表達式。因此我們可以用下面的適應度,其中w是一個權重,n_M是M堆中匹配的字元串,n_U是U堆中匹配的字元串。


fitness(r) = w(n_M-n_U) - length(r)

下表是Bartoli et al. (2014)報告的結果。其中 Norvig-RegexGolf 是一種基線方法,GP-RegexGolf是作者提出的方法,GP-RegexExtract是應用在Text Extraction任務上的遺傳演算法。

參考文獻

Bartoli, Alberto, et al. "Playing regex golf with genetic programming." Proceedings of the
2014 conference on Genetic and evolutionary computation. ACM, 2014.


遺傳演算法系列之二:「欺騙」深度學習的遺傳演算法


寫過使用遺傳演算法驅動神經網路,可以很好的完成一維度的自動控制。
二維,卒


只變異了兩萬次, 摘掉眼鏡效果已經一樣了==============================
謝謝fool提供的Image evolution


可以預測股價 貼一篇論文

基於改進 GA 參數優化的 SVR 股價預測模型
孫秋韻, 劉金清, 劉 引, 吳慶祥 (福建師範大學 )

論文主要論述了小波去噪後GA-SVR演算法預測股價的準確性
直接貼論文截圖了

本文選取上證 A 股指數為實驗對象, 並選取收盤
價, 開盤價, 最高價, 最低價, 成交價及成交量為預測
模型的特徵值. 在數據區間上, 選取 2013 年 1 月 4 日
至 2013 年 12 月 31 日之間的 238 個交易日線數據, 其
樣本量大小為 1428, 構成 238*6 矩陣, 所有數據均來
源於大智慧資料庫. 其中, 前 180 組數據樣本為訓練
集, 後 58 組數據樣本為測試集.

原始樣本
100代進化後

順便對比一下普通的SVR模型:

最後貼一下結果


五子棋。

http://zhaochen.gq/blog/2016/12/20/%e5%9f%ba%e4%ba%8e%e9%81%97%e4%bc%a0%e7%ae%97%e6%b3%95%e7%9a%84%e4%ba%94%e5%ad%90%e6%a3%8bai%e4%bc%98%e5%8c%96/


matrix67博客上好像有篇遺傳演算法畫蒙娜麗莎的日誌


剛做的一個項目,用遺傳演算法來解Partial Index Tracking Problem(用少於指數組成的股票來複制一個股票的表現)。標的是滬深300指數,In Sample數據是2011-03到2012-12-31的300隻滬深300指數成分股,Out Of Sample數據是2013-01-04到2013-12-31。
In-sample Comparison:
Number of Candidates in portfolio: 30
Portfolio Construction Cost: 1131.629031, Percentage: 0.113163%
In-sample Tracking Error: 0.244337%, Running Time: 14.01min
In-sample Correlation Coefficient: 0.996423, p-value: 0.000000

Out-of-sample Comparison:
Out-of-sample Tracking Error: 0.004515%
Out-of-sample Correlation Coefficient: 0.897571, p-value: 0.000000


【3D物理引擎實驗】多P補全計劃
除了最後一個貌似純搞笑......


推薦閱讀:

TAG:遺傳演算法 | 機器學習 | 有趣 |