智能優化演算法-第四次工業革命的重要引擎
『運籌OR帷幄』原創
作者：常征
這篇文章想給大家簡單聊一聊智能優化演算法~
本著通俗，精湛的寫作風格，希望本文能對智能優化演算法進行一個簡單的概述，並對大家有所幫助。
1
智能優化演算法--第四次工業革命的重要引擎
第三次工業革命，又稱計算機技術革命，其最大的貢獻是通過互聯網信息共享等方式，產生了大量的數據，使數據像蒸汽和電力一樣，成為推動工業進步重要的能源；第四次工業革命的首要任務，就是如何更智慧地點燃這些能源 ，讓這些能源發揮更大的作用。所以，人工智慧，機器學習，大數據等便成為開啟第四次工業革命的熱點辭彙。
參照：【學界】人工智慧的「引擎」--運籌學，一門建模、優化、決策的科學 （鏈接：https://zhuanlan.zhihu.com/p/25579864）一文
我們可知道，其實人工智慧中熱點的神經網路，深度學習等問題的最終，還是落到了解決一個優化問題上。包括大數據，機器學習等其實最後都與優化問題密不可分。
見於傳統解決優化問題的精確演算法在當前「大數據」面前的捉襟見肘，近代智能優化演算法便成為解決當前複雜優化問題的「重要武器」，所以，刨根問底之後，我們也可以說智能優化演算法是第四次工業革命的重要引擎。
02
什麼是智能優化演算法
目前業界關於智能優化演算法還沒有一個統一的定義。本文將通過對比分析，嘗試提出智能優化演算法的定義。
所謂演算法就是解決問題的方法。智能，首先要搞清楚誰的智能，在我看來目前這個主語應該是人；那麼什麼叫做智能呢，智能是人的智慧和能力，重在巧妙和妥當。
所以，本文提出智能演算法的定義為： 智能優化演算法，是指人類基於自身對宇宙自然的認知、學習或經驗構造出來的，用於在人類可接受的花費（計算時間和空間）下在解空間中推廣一系列有目的地訪問巧妙地給出待解決組合優化問題的一個較好可行解的計算方法的統稱。
備註：
1） 啟發式演算法 VS 精確演算法
精確演算法是指在優化問題中可求出最優解的演算法（http://t.cn/RnQqkvy）。到目前為止，已提出的精確演算法種類較多，有分支定界法、割平面法、整數規劃演算法和動態規劃演算法等。
但往往複雜的組合優化問題，用精確演算法在有限的計算時間下，難以得到最終的最優解，於是人們就提出了啟發式演算法。
啟發式演算法（heuristic algorithm)是相對於最優化（http://t.cn/RnQ57QT）演算法提出的。一個問題的最優演算法求得該問題每個實例的最優解（http://t.cn/RnQ52zU）。啟發式演算法可以這樣定義：一個基於直觀或經驗構造的演算法，在可接受的花費（指計算時間和空間）下給出待解決組合優化問題每一個實例的一個可行解（http://t.cn/RnQ5UoX），該可行解與最優解的偏離程度一般不能被預計。
根據英國Cranfield大學@宋伯陽 的見解：演算法如果只分兩種，就是精確演算法和啟發演算法。所有啟發、元啟發演算法都不是精確演算法 (不保證能得到最優解）。
參見文章 :留德華叫獸：【學界】整數規劃精確演算法/近似演算法/(元)啟發演算法/神經網路反向傳播等演算法的區別與關聯
2） 智能優化演算法 VS 啟發式演算法
根據「王凌. 啟發式優化演算法. ：《中國大百科全書》(第二版). 北京: 中國大百科全書出版社, 2004.」一書中對智能優化演算法的描述可知：
智能優化演算法（intelligent optimization algorithms）是基於計算智能的機制求解複雜優化問題最優解或滿意解的方法，學術界也稱之為meta-heuristics。智能優化通過對生物、物理、化學、社會、藝術等系統或領域中的相關行為、功能、經驗、規則、作用機理的認知，揭示優化演算法的設計原理，在特定問題特徵的導引下提煉相應的特徵模型，設計智能化的迭代搜索型優化演算法。
那麼智能優化演算法，即元啟發式演算法，與啟發式演算法有什麼區別和聯繫呢？
啟發演算法和元啟發演算法最大的區別是，啟發演算法更多求局部最優，元啟發演算法（智能優化演算法）設計有克服陷入局部優化的機構，更適合尋求全局最優，比如遺傳演算法GA有突變Mutation機制。其次，啟發演算法的設計更多是取決於問題Problem-dependent，元啟發演算法（智能優化演算法）是獨立於問題Problem-independent (可以作為一個black box操作，適用性廣，但還是要根據問題調演算法各種參數）。元啟發演算法範圍內大部分應用了隨機優化機構，多目標優化用的蠻多。
但是多目標優化中，目標太多時一般會先降維（比如PCA），多於3-5個目標的優化效率低，也沒有太多實際的可讀性。接近實際的案例裡面一般都會涉及多種演算法，先用元啟發演算法（智能優化演算法）求得一個小範圍的滿意解，再用啟發或者精確演算法找最優解，這樣即提高了計算效率又能有高質量結果。（演算法種類和術語名字太多，看到各種名字很容易暈，其實很多都有相關性（差不多），弄清楚他們之間的關係還是有點重要的）。
（參考文章：【學界】整數規劃精確演算法/近似演算法/(元)啟發演算法/神經網路反向傳播等演算法的區別與關聯）
最後，因為智能優化演算法的可行解與最優解的偏離程度一般不能被預計，所以我們也可以把智能優化演算法理解為人類解決問題時的一種「沒有辦法的辦法」，是人類智慧的體現。
03
智能優化演算法的基本分類
目前業界關於智能優化演算法的分類也沒有標準答案，本文作者根據自己對演算法的理解提出智能演算法的一套分類方法。
智能優化演算法按智能來源分大概可分為：自然進化類演算法， 仿生類演算法，人工搜索類演算法，人工神經網路演算法等。
（由於篇幅原因，此處只整理提綱不進行解讀，力圖幫業內同仁建立演算法綱領，拋磚引玉~）
1 自然進化類演算法
1.1 遺傳演算法
1.2 差分進化演算法
1.3 免疫演算法
.....
2 仿生類演算法
2.1 蟻群演算法
2.2 粒子群演算法（鳥群演算法）
2.3 魚群演算法
2.4 蜂群演算法
2.5 鯨群演算法
.....
3 仿物類演算法
3.1 模擬退火演算法
......
4 人工搜索類演算法
4.1 禁忌搜索
4.2 迭代局部搜索
4.3 鄰域搜索
......
5 人工神經網路演算法（仿腦）
5.1 監督式學習網路
5.2 無監督式學習網路
5.3 混合式學習網路
5.4 聯想式學習網路
5.5 最進化學習網路
...
04
智能優化演算法的特點
1 相關性： 各種演算法其實是解決問題的辦法，條條大路通羅馬。各種演算法，都是基於當前可行解根據一個方向或路徑去尋找潛在的更優可行解，其區別無非是各自建立了自己的理論體系，其走向問題真理的大方向並沒有改變。所以，各種演算法相互之間具有一定的相關性。
例如仿生類演算法，也有進化的特點；進化的思想，在神經網路中演算法中也有體現。
2 協同性： 各種演算法猶如十八般兵器，各有所長，有些演算法從宏觀上進行構架，有些從微觀層面進行分析，要想最大程度的提高演算法效率，各種演算法必須進行協同。所以研究高效並行（http://t.cn/RnQtPtV）或分散式（http://t.cn/RnQtw2H）優化演算法，開發新的混合式演算法都是智能演算法的發展方向。
參見知乎：遺傳演算法，模擬退火演算法，粒子群演算法，神經網路等智能演算法的作用？http://t.cn/RQxINE0
3 隨機性： 智能優化演算法既然是人類基於自身對宇宙自然的認知、學習或經驗構造出來的解決問題的辦法。那麼就具有一定的不確定性或隨機性，其可行解與最優解的偏離程度一般不能被預計。所以，沒有最好的智能演算法，只有更好的智能演算法。
......
05
智能演算法的腦洞
1 這個世界是否存在"終極演算法」？
所謂終極演算法，就是說這套演算法，可以解決一切問題。現在之所以有不合適的演算法，其原因多為在有限時間和精力下人們無法得出答案罷了。
如此而論，假如計算機的計算速度和能力，大大超越數據的量和複雜度的話，那麼終極演算法，就理應存在。
個人以為未來最有可能成為終極的演算法的是---影響自然界萬物進化的「遺傳演算法」和決定人類成為萬物之靈的"神經網路演算法」。
2 智能演算法之後的演算法是什麼？
智能優化演算法的隨機性是其最大的缺陷，這個缺陷本質是人類認知、學習或經驗的局限性。智能優化演算法之後的演算法，或許是第五次工業革命的重要引擎，將重點優化人工智慧演算法的隨機性的缺陷，本文姑且把這種演算法稱之為機器智能演算法。
......
在此感謝『運籌OR帷幄』審稿人對本文提出了寶貴的意見。
『運籌OR帷幄』審稿人王銳，謝菲爾德大學博士、現任國防科大教授，研究方向：智能演算法，進化演算法。
『運籌OR帷幄』審稿人孫卓，日本名古屋大學工學博士，現任新加坡國立大學海事研究中心客座研究員，大連海事大學交通運輸管理學院教授，研究方向：交通物流。
轉載請聯繫本公眾號獲得授權
TAG:運籌OR帷幄 |