本文最早發(fā)表在本人博客:<a >http://www.gotoli.us/?p=1511</a>
這篇博客主要介紹不同問題的遺傳算法凭峡。遺傳算法是通用的全局優(yōu)化算法牙肝，因此有很多的應(yīng)用卢厂。有很多應(yīng)用我是看不懂的旭从，比如機器人步態(tài)優(yōu)化错维。機器人步態(tài)優(yōu)化應(yīng)該蠻有趣的华嘹，B站視頻<a >在此</a>吧趣，可惜看不懂。有哪位讀者了解相關(guān)知識耙厚，歡迎科普强挫。另外有一些應(yīng)用人們已經(jīng)討論很多了，比如0-1背包問題薛躬、旅行商問題和裝箱問題俯渤。這里就不做介紹。這篇博客介紹一些我能看懂的有趣應(yīng)用泛豪。
<strong><h3>“欺騙”深度學(xué)習(xí)</h3></strong>
Szegedy et al. (2013) 發(fā)現(xiàn)雖然深度學(xué)習(xí)模型在圖像物體識別任務(wù)已經(jīng)達到甚至超過了人類水平稠诲，但深度學(xué)習(xí)模型很容易被愚弄(fooled)。下圖是論文中的例子诡曙，左列的圖經(jīng)過中間的變換成右列的圖臀叙。對我們?nèi)祟悂碚f，變換前后圖片幾乎沒有變化价卤，判對左列圖片的深度學(xué)習(xí)模型卻將右列圖片都判錯了劝萤。這說明人類和深度學(xué)習(xí)模型之間的區(qū)別還有很多。
Nguyen et al. (2014) 用報告了另一種結(jié)果：我們能夠產(chǎn)生一組對人類完全沒有意義的混亂圖片慎璧，深度學(xué)習(xí)模型卻會將它們高分值判斷圖片為某一物體床嫌。遺傳算法便是產(chǎn)生這樣混亂圖片的方法之一跨释。論文中使用了不同的編碼方式，我們介紹在MNIST數(shù)據(jù)集上的簡單編碼方式厌处。種群中個體代表一張MNIST圖片鳖谈，個體中一條染色體長25 (\times) 25，染色體每一位基因代表了圖片對應(yīng)位置的像素灰度阔涉。個體適應(yīng)度等于深度學(xué)習(xí)模型將圖片判讀為一個數(shù)字的置信度缆娃。下圖就是這種編碼方式產(chǎn)生的結(jié)果。我們?nèi)祟惪聪聢D中的圖片瑰排，完全就是一片混沌贯要，但state-of-the-art的深度學(xué)習(xí)模型卻以超過99.99%的置信度將它們判斷某個數(shù)字。
<strong><h3>正則表達式生成器</h3></strong>
<a >Regex Golf</a> 是一個正則表達式生成競賽椭住。這個競賽給兩堆字符串M和U崇渗，要求參數(shù)者給出的正則表達式r盡可能地匹配M堆中的字符串，和盡可能地不匹配U堆中的字符串京郑。下圖就是競賽的示意圖宅广。
Bartoli et al. (2014)提出用遺傳算法解決這個問題。種群一個個體是一顆正則表達式樹些举，如下圖所示乘碑。正則表達樹的葉子節(jié)點是一些從M堆字符串抽取的字母和N-grams。正則表達式樹的中間節(jié)點是正則表達式的符號金拒，比如“()”、“*”和“?”套腹。
個體對應(yīng)正則表達式匹配越多M堆字符串绪抛，個體適應(yīng)度應(yīng)該越大。個體對應(yīng)正則表達式匹配越多U堆字符串电禀，個體適應(yīng)度應(yīng)該越小幢码。因此可以直接用（匹配M堆字符串?dāng)?shù)量-匹配U堆字符串?dāng)?shù)量）作為適應(yīng)度。但這樣的話尖飞，得到的正則表達式的長度會很長症副。為了控制正則表達式長度，適應(yīng)度應(yīng)該懲罰長的正則表達式政基。因此我們可以用下面的適應(yīng)度贞铣，其中w是一個權(quán)重，n_M是M堆中匹配的字符串沮明，n_U是U堆中匹配的字符串辕坝。
下表是Bartoli et al. (2014)報告的結(jié)果。其中 Norvig-RegexGolf 是一種基線方法荐健，GP-RegexGolf是作者提出的方法酱畅，GP-RegexExtract是應(yīng)用在Text Extraction任務(wù)上的遺傳算法琳袄。
有人將這種類型的遺傳算法稱為遺傳編程（Genetic Programming）。種群中一個個體代表一段程序（一段表達式也算一段程序吧）纺酸，通過遺傳算法獲得最優(yōu)的程序窖逗，就像算法自己能夠編寫程序一樣餐蔬。但目前為止，我看到的所有遺傳編程的個體都是一段表達式或者一段公式用含，離“算法能夠編寫程序”差十萬八七里。
<strong><h3>機器人路徑規(guī)劃</h3></strong>
機器人路徑規(guī)劃是遺傳算法很傳統(tǒng)的應(yīng)用之一啄骇，很多地方都有討論。不過對我們這些不搞機器人的人來說缸夹，路徑規(guī)劃還是蠻有意思的應(yīng)用。機器人路徑規(guī)劃技術(shù), 就是機器人根據(jù)自身傳感器對環(huán)境的感知, 自行規(guī)劃出一條安全的運行路線虽惭。下圖是用柵格表示的機器人路徑規(guī)劃環(huán)境橡类，柵格是最簡單的路徑規(guī)劃環(huán)境表示方法顾画。圖中的路線就是機器人的前進路線。
遺傳算法中的一個個體代表了一條路線研侣。個體染色體有起始點和終止點，起始點和終止之間是機器人的中間褪睿靠點。上圖中的路線可以用下面基因序列表示末誓。個體適應(yīng)度隨著路線長度增加而減小。有些路線并不合法（比如穿過障礙物）喇澡，這時候相應(yīng)個體的適應(yīng)度需要加一個懲罰項。
應(yīng)用于機器人路徑規(guī)劃的遺傳算法有很多問題善炫，也就是說有很多改進的空間撩幽。比如，變異過程有可能將路線中間點變到障礙物里。我們可以用一些改進的變異操作避免這個問題窜醉。Tuncer and Yildirim (2012) 就提出了一種新的變異操作解決這個問題宪萄。這個變異操作的大體思路是先將中間點隨機變異，然后檢查變異的中間點是否在障礙物內(nèi)榨惰，如果是則選擇一個附近位置拜英。下圖就是這種變異操作的示意圖。
<strong><h3>寫宋詞</h3></strong>
這里介紹一個奇技淫巧——周昌樂等(2010)用遺傳算法寫宋詞琅催。在這項工作之前居凶，作者已經(jīng)建立了一個包含情感類別、語法藤抡、語義侠碧、音韻等要素的元數(shù)據(jù)庫。種群中一個個體代表了一首詞缠黍，不同的基因位是不同詞弄兜。個體代表的一首詞的適應(yīng)度由句法和語義加權(quán)獲得。由于我對詩詞沒有啥了解瓷式，就不多瞎說了替饿。感興趣的讀者可以直接閱讀論文。下表是論文中報告的結(jié)果贸典。
這里插入一點私貨视卢，談?wù)勎覍υ娫~生成、音樂生成和自動作畫的看法廊驼。一開始我是不喜歡這一類的研究的据过，原因有兩點：1）現(xiàn)在的弱人工智能根本沒有發(fā)展到吟詩作畫的程度，2）這些東西根本沒啥用處好吧妒挎。不過后面我的觀點改變了〉悖現(xiàn)在我的觀點是有些研究就是玩啊。這時候我們只需要問有趣嗎饥漫，而不需要問有用嗎。反正這個話題那么有趣罗标，那就繼續(xù)玩咯庸队。正是有些研究不是沖著有用，而是沖著好玩去的闯割，科學(xué)的未來才有無限可能彻消。
<strong><h3>某些蛋疼的例子</h3></strong>
當(dāng)然不是所有問題都適合使用遺傳算法的。比如很多年前宙拉，石三石跟我介紹了一篇國內(nèi)論文宾尚，那篇論文用遺傳算法優(yōu)化k-means聚類的k值。你沒有看錯煌贴，是k-means聚類算法的k值。我當(dāng)時還不相信怠肋，覺得那篇論文應(yīng)該是優(yōu)化k-means初始化的值笙各。三石同學(xué)還和我確認是k-means聚類算法的k值杈抢。他和我對著那篇論文默默吐槽了仑性。我雖然不知道k-means聚類算法k值的選擇有什么辦法虏缸，但我知道遺傳算法是絕對不行的。因為我把k值從1到n(n為待聚類的樣本數(shù)量)全部試一遍的時間窥岩，時間和遺傳算法的運行時間差不多吧颂翼。另外那篇論文的適應(yīng)度是用 (類間距離的均值)/(類內(nèi)距離的均值) 衡量的慨灭。k設(shè)為n時，這個指標肯定是最大的啊呻疹。
另外一個例子是用遺傳算法調(diào)神經(jīng)網(wǎng)絡(luò)參數(shù)刽锤。這個例子倒是常見朦佩，比如Matlab就是支持。具體做法可以參考<a >這個網(wǎng)頁</a>宋彼。遺傳算法個體中一條染色代表了一組參數(shù)输涕，個體適應(yīng)度等于用這組參數(shù)訓(xùn)練的神經(jīng)網(wǎng)絡(luò)在驗證集上準確率。在十幾年前桃熄，神經(jīng)網(wǎng)絡(luò)和其他分類算法面對的是小規(guī)模的數(shù)據(jù)型奥。因此訓(xùn)練和預(yù)測的時間比較少厢汹，這種方法是適用的。但現(xiàn)在神經(jīng)網(wǎng)絡(luò)面對都是大規(guī)模的數(shù)據(jù)界弧，訓(xùn)練時間很長垢箕。有些神經(jīng)網(wǎng)絡(luò)需要一天時間訓(xùn)練条获，如果遺傳算法初始種群有100個個體蒋歌，光是計算這個一百個個體的適應(yīng)度就需要100天堂油。遺傳算法調(diào)參顯然是不實用的府框。
<strong><h3>第一次在博客中列參考文獻</h3></strong>
Bartoli, Alberto, et al. "Playing regex golf with genetic programming." Proceedings of the 2014 conference on Genetic and evolutionary computation. ACM, 2014.
Nguyen, Anh, Jason Yosinski, and Jeff Clune. "Deep neural networks are easily fooled: High confidence predictions for unrecognizable images." arXiv preprint arXiv:1412.1897 (2014).
Szegedy, Christian, et al. "Intriguing properties of neural networks." arXiv preprint arXiv:1312.6199 (2013).
Tuncer, Adem, and Mehmet Yildirim. "Dynamic path planning of mobile robots with improved genetic algorithm." Computers & Electrical Engineering 38.6 (2012): 1564-1572.
周昌樂, 游維, and 丁曉君. "一種宋詞自動生成的遺傳算法及其機器實現(xiàn)." Journal of Software 21.3 (2010): 427-437.
