優化演算法從鳥群、魚群中借鑑了什麼 | 演算法科普文
本文作者將與你分享：演算法是如何借鑑大自然中的鳥群、魚群等，來找尋最優解的，以及演算法是不是可能自己設計演算法。enjoy~
生活工作中，很多時候都是在尋求最優解。
比如選擇進入哪個行業去工作，怎樣填寫高考志願，怎樣找到自己深愛的伴侶，怎樣在合適時機和地點購房，怎樣在變幻莫測的股市中淘金，怎樣在平衡客戶需求和開發能力之間找到一個成本-效益最佳的專案方案，等等。
這些待解決的問題，按理說，都有最優解。
而本文作者嶽亞丁博士將告訴你，演算法是如何借鑑大自然中的鳥群、魚群等，來找尋最優解的，以及演算法是不是可能自己設計演算法。
文章要點：
- 哪些問題需要優化演算法？
- 設計優化演算法時，大自然給了我們什麼啟發
- 舉個例子看優化演算法到底啥樣
- 擺脫對大自然的依賴，自創更好的優化演算法
演算法工程師與他的好友在公園觀魚。一群色彩斑斕的錦鯉在水面翻騰，追逐著遊人們拋下的魚食。
最優決策需要優化演算法
：想什麼呢？你不想餵它們嗎？
：我在想，這些魚遊動的軌跡，與魚群演算法有多麼的相似。
：這裡也有演算法？
：你看，它們時而捕食，時而群聚，時而追隨，時而漫遊，最終目的是儘快找到更多的食物，同時又避免可能的風險。魚群演算法，正是由此而來啊。
：你說的魚群演算法，是指仿生學嗎？
：不是。仿生學主要是借鑑生物界的形態、結構、功能，設計出新的機械、裝置、裝置，比如人類受魚類形狀的啟發，設計出水下航行的潛艇；或者通過研究鳥類肢體構造和飛行技能，來改進飛機的效能。
魚群演算法，則是受魚群行為的啟發，設計出的一種演算法，可以用來找到問題的最優解。
：問題的最優解，是什麼意思？
：我們生活和工作中，很多時候都是在尋求最優解。
比如說，選擇進入哪個行業去工作，怎樣填寫高考志願，怎樣找到自己深愛的伴侶，怎樣在合適時機和地點購房，怎樣在變幻莫測的股市中淘金，怎樣在平衡客戶需求和開發能力之間找到一個成本-效益最佳的專案方案，等等。這些待解決的問題，按理說，都有最優解。
：聽起來，像是在做最優決策。
：是同一個意思。人是智慧生物，是解決問題的高手，有分析、綜合、歸納、推理等能力，有尋找最優解的能力。
但是當面臨的問題規模太大，複雜程度太高，特別是大社會、大工業中的問題，要找到最優解，哪怕記憶力再好、再聰明的人腦也吃不消了，靠直覺、拍腦袋做決策，已經不靠譜，還是需要用計算機來幫忙做這個事情，這時就需要優化演算法了。
：計算機算數還是挺快的，聽說都每秒多少億次了，用它做優化，還沒怎麼聽說。所以你讓它模仿魚群？
：計算機比較笨，只能按照我們人類的指令來做事情，但它最大的特點是算得快，我們可以利用這個特點來做更復雜的事情，包括優化。
勤能補拙嘛。我先通過一個簡單例子，解釋一下計算機是怎麼做優化的，然後再說魚群的事。
：好吧，你說說看。
一種簡單的優化演算法
：假設有一個人，在漆黑不見五指的夜裡，獨自登山，目標是山頂，你覺得他應該怎麼做？
：山上不會有斷崖、溪流、野獸吧？
：暫時假定沒有這些危險東西。
：那就只能四處伸腳試試，感受一下，哪個方向是向上的，就往那個方向走唄。
：是的。這也正是計算機的最簡單的優化演算法之一。山頂就是待求的最優解。
從某個座標點（東經多少度、北緯多少度）出發，演算法開始之後，給計算機一個旁邊緊挨著的新座標點（相當於人往某個方向挪動一步），它算一下，是不是好些（人感覺是不是升高了一點），如果是，計算機就認定這個座標點更好（人就往這個方向走一步），然後在這個點的基礎上繼續嘗試；否則，就退回來，給它旁邊另一個座標點算一下（人往另一個方向挪動一步），再試。
就這樣逐步嘗試，走了很多步之後（所幸計算機“走”得挺快），如果發現四處挪動都是下降的方向，就算是到達山頂了。
：是夠笨的，但是聽起來，似乎還是有效的。
：對呀。
：不過，我覺得這裡有一個問題。按照這樣的方案，會不會走到了一個小山包的頂端，甚至一個小土堆上，就以為到山頂了，而實際上真正的山頂還遠著呢？
：你說得對。小山包的頂端，只是一個區域性的最優解，真正的山頂，才是一個全域性的最優解。我們當然希望找到後者。上面說的演算法還不是一個非常好的演算法，它有可能找不到全域性最優解。
：還有一個問題：如果能夠通過鞋底感覺到地面的不平，有點傾斜，那就不需要前後左右地伸腿嘗試，而只要按照鞋底感覺到的往上傾斜的方向走，這樣豈不是更快？
：正是！如果待求問題與目標之間可以表示為一個數學公式，我們一般就可以求出哪個方向是往上傾斜的，然後讓計算機沿著那個方向進行搜尋，就更快捷了。
學術界把這種演算法叫做“瞎子爬山法”。但是很多情況下，待求問題很複雜，沒法寫出一個數學式子，所以還是得四處伸腳嘗試。
：這也是沒有辦法的辦法了。
：但這樣也好，可以處理更多型別的問題。
例如，學生成績受很多因素影響，包括學生的年齡、性別、學習時長、健康程度、家庭背景等等，但到底是怎樣影響的，我們可能寫不出一個很精確的數學公式來（總不能瞎編一個“數學期考成績 = 年齡x平均每天學習小時數”吧）。
也沒必要去寫，可以通過“伸腿”去試，照樣可以求得最優解，從而得知怎樣才能獲得更高分數。
：最後一個問題：如果真的有斷崖、溪流這些東西，怎麼辦？
：現實世界中，它們當然對爬山人構成阻礙和威脅。計算機做的話，都是在虛擬世界中嘗試，即使突然發現“踩空一腳”，也沒什麼大不了的，照樣可以退回來，不影響後續的逐步搜尋。
：這個瞎子爬山法，除了用來爬到山頂，還能用於更復雜的問題嗎？比如說炒股，你前面也提到了的。
：瞎子爬山法難以勝任，其它優化演算法恐怕也夠嗆，因為股市資料的隨機性太強。當然，也可以試一試，只要能夠把問題用數值表示出來。
炒股的情況雖然很複雜，但簡略地講，我們的目標，還是希望一段時間內的投資收益最大化；要尋找的，則是應該買哪幾只股票，買多少股，持有多長時間，等等，這些待求的東西，都是可以表示成一組數值的，就跟上面爬山的情況那樣，那裡是用經緯度座標值來表示的。
：你是說，把待求的東西表示為一組數（如經緯度、股票倉位），目標是另一個數（如海拔、收益），然後讓優化演算法來找出能使目標最大的一組數，對嗎？
：是的，這就是優化演算法的本質。
鳥群演算法的優勢
：比瞎子爬山法好的優化演算法，有哪些？
：還有魚群、鳥群、蜂群、蟻群、螢火蟲、細菌、猴群、布穀鳥、蝙蝠、病毒、免疫系統、生物進化 ……
人們從它們的行為得到啟發，設計了優化演算法，很多情況下，它們比瞎子爬山法好。
：嚯！開動物園了。
：也有非生物的，例如，和聲、水滴、螺旋、星系、重力、量子……
：夠多的了。能舉一個例子嗎？我來感受一下比瞎子爬山法好在哪裡。
：就說說鳥群演算法吧，它比起魚群演算法更簡單一點，也相對容易解釋一點。
：好。
：鳥群演算法裡面，假設食物就像蚊蟲，不均勻散落在空中，在某些點更密集。一群鳥在空中盤旋飛翔，想找到那個食物最集中的點，也就是全域性最優點。
：有一隻頭鳥帶領它們飛嗎？
：不需要，假定每隻鳥的能力都一樣。每隻鳥的下一步飛翔方向受到三股力量的影響：
- 第一，是當前的飛翔方向，即它自身有一定慣性，會有一股力量想拉著它沿著當前的方向飛。
- 第二，是它自己迄今為止經過的食物最密集的某個點，它對此還有記憶，覺得那個點有戲，於是也會受到那個點的牽引，儘管那個點不一定是全域性最優點。
- 第三，假設鳥群之間是有通訊聯絡的，隨時保持溝通，對於整個鳥群迄今為止經過的食物最密集的某個點，每隻鳥都是知道的，於是這隻鳥也有點受那個點的牽引，儘管那個點也不一定是全域性最優點。
：這樣的假設，好像還是有道理的，但不知道是否符合實際情況。
：對實際情況，我們可能無法準確知道。但是設計一種演算法，只要借鑑生物的一部分行為，只要效果好，也就可以了，不一定非要完全符合實際情況。
：然後呢，鳥群怎麼飛？
：每隻鳥受三股力量的牽引，在空中飛翔，會逐漸向最優點靠攏。
飛了一段時間後，估計差不多了，就盤點一下，所有鳥截止到最後時刻經過的食物最密集的某個點，就被認為是全域性最優點。
：什麼叫做“認為是全域性最優點”？它不是真正的全域性最優點嗎？
：不能確保。這樣找到的，仍然可能是區域性最優點。要想找到全域性最優點，還是需要別的更復雜演算法，或者與其它演算法結合進行。
例如，在爬山情況下，改為允許犯錯，即使在區域性最優點，伸腿嘗試時發生下降，也聽之任之，說不定就能慢慢走出區域性最優點，重新找到通往真正山頂的路徑。
：既然都不能確保找到全域性最優點，那鳥群演算法比瞎子爬山法好在哪裡呢？
：很多情況下，鳥群演算法可以更快地找到最優點。這一點，數學上可以證明，大量的實驗和實際的工程應用，也可以證實。
可能是因為有一群鳥在行事，它們之間互相協作，集團智慧高於個體智慧嘛。
信天翁的搜尋策略
：這樣比較，好像不太公平哦。我也可以安排很多個瞎子同時爬山的。
：但是瞎子之間沒有通訊協作吧。如果允許瞎子之間有協作，那就又有點像是鳥群演算法了。
：倒也是。不過，你能否找一個單打獨鬥的情況，一個瞎子，和一個別的什麼，看他們做優化時，誰更厲害？
：是有一些依靠一個個體進行搜尋的其它優化演算法，只是很少看到哪份資料中比較過它們誰更厲害，我自己也沒有實驗過。
：你說說看吧。我總覺得瞎子爬山法還有點過於機械，希望還有更聰明的做法。
：如果曠野中的食物稀少，隨機分佈在一塊很大的區域裡，動物在搜尋它們時，並不一定是完全漫無目的地隨機搜尋，那樣的效率是比較低的。
科學家們發現，海洋中的掠食者，如皺鰓鯊、黃鰭金槍魚、藍色馬林、旗魚，還有信天翁，它們的搜尋方式，有一些很獨特的特徵，即：可能沿某個方向走出很遠，才改變方向另搜。
這種搜尋方式稱為“列維飛行”，是根據法國數學家Lévy的名字命名的。在相同時間內，列維飛行找到的食物數量，很可能高於隨機搜尋。可能是千百萬年的進化，使得他們學會了這種搜尋方式。
（左圖：隨機搜尋形成的軌跡 右圖：Levy飛行搜尋形成的軌跡）
：哦，這倒有點意思。你們可以讓計算機也學著這麼搜尋，快點找到最優解嗎？
：已經有人做了。
當演算法自己設計演算法
：感覺只要是要求“最大”、“最小”、“最優”的問題，就可以用優化演算法來做了，對嗎？
：基本上可以這麼說。其實，優化演算法還可以幫我們更多的忙，它不僅授人以魚，也能授人以漁。
：這是怎麼說？
：就好像一個小學生在做數學題，因為掌握的方法不熟練，或者運用的方法不對，做得很慢，旁邊坐著的老師，就會指點他改進方法。
：嗯，改進學習方法，這很重要，老師、家長、學生們都在說這個事。
：有一類優化演算法，就是可以在一個演算法正在工作的時候，隨時指點這個工作的演算法進行改進的。
：神奇。這回優化的是演算法的好壞了。
：此外，我們還面臨的一種情況是，已經有很多優化演算法，告訴我們如何儘快到達山頂，或者解決別的問題。但優化演算法太多了，為什麼不用一個優化演算法來幫我們選一個呢？
：是啊。我剛才還在琢磨，你說了一大堆優化演算法，但是我真正動起手來，也不知道應該用哪一個。
我總不能每一個都去試一下，那樣也太耗費時間了。如果有一個演算法來幫我選出一種好的，就省事了。
：最後，腦洞不妨再開大一點：如果有一種優化演算法，它作為母體，能夠自行設計出一個優化演算法，使得其在效率上優於所有人工設計出來的優化演算法，豈不更妙？
：這……有可能麼？
：只要待設計的優化演算法本身，能夠用數值表示，就好辦了。而且已經有一些這方面的研究，也有一些初步成果，似乎還不錯。當然，這個過程還有很多困難，理論上也尚待突破。
：那以後都不用借鑑大自然、動物的行為，不需要那麼費力地人工地構造那麼多的優化演算法了，甚至電腦科學家們都可以失業了，是不是？
：還沒有那麼激進。至少，用於設計優化演算法的那些優化演算法，我們稱之為“元演算法”的，還是需要人工設計的。元演算法，是關於演算法的演算法。
：就不能再加多一層，再另外用一個演算法來設計元演算法，出現一種關於演算法的演算法的演算法，甚至關於演算法的演算法的演算法的演算法？
：你還真問倒我了。學術界好像還沒有人搞這麼多層的，我也不清楚這樣做，帶來的好處有多大。再看看吧。
：我想起來了，打敗世界圍棋冠軍的AlphaGo，據說是向人類學習，借鑑了幾千萬局人工對弈的棋譜。
後來的AlphaGo Zero，擺脫對人類的模仿，左右手互搏，自學圍棋，最後以100:0的戰績打敗它的“前輩”。這個是不是關於演算法的演算法？
：有一點類似。
：想一想都很恐怖，感覺以後的演算法會越來越厲害，它們可以自主設計出演算法，比我們人類設計出來的演算法更牛，說不定哪天會全面超過人類的智力。
：AI能否超越人類，是一個有爭議的話題。今天我們沒時間細聊了，留待下次吧。
：好的。
：還是得感謝大自然的饋贈，啟發了人類設計出這麼多的優化演算法，可以用於解決很多的實際問題。就看我們能否很好地利用了。
：就像中醫藥——人處在大自然的環境中，得了病怎麼辦，答案還是在大自然中。
*文中圖片來源於網路
作者：嶽亞丁
來源：微信公眾號“騰訊研究院（ID：cyberlawrc）”
本文由 @騰訊研究院 授權釋出於人人都是產品經理，未經作者許可，禁止轉載。
題圖來自 Pixabay，基於 CC0 協議