遺傳演算法,模擬退火演算法,粒子群演算法,神經網路等智能演算法的作用?
前三個演算法(遺傳演算法 Genetic Algorithm (GA), 模擬退火演算法 Simulated Annealing (SA), 粒子群演算法 Particle Swarm Optimization (PSO))屬於智能優化演算法範疇,最後一個神經網路(Neural Networks),一般使用的是人工神經網路(Artificial Neural Networks),可以應用於模式識別、信號處理、專家系統、優化組合、機器人控制等方面,屬於現在現在很火的人工智慧(Artificial Intelligence)的一個分支,AI 還包括深度學習(Deep Learning, 最近前百度首席科學家,斯坦福大學教授吳恩達會在Coursera上發布關於 DL 的課程,大家可以關注),超限學習機(Extremely Learning Machine, ELM, 由南洋理工大學黃廣斌教授提出,發表的論文被引次數位於近十年人工智慧文章第二位)等。
我的研究和前三個演算法比較相關,結合我的研究: 設施布局問題 (Facility Layout Problem)(已知每台機器的尺寸以及兩兩之間的物流量,求得合理布局使得搬運成本最低),談談自己的看法。優化領域解決問題通常使用三種方法,第一種是精確方法(Exact Approaches),另外還有啟發式演算法(Heuristics Algorithm)和以及元啟發式演算法(Meta-heuristics Algorithm)。
1. 精確方法(Exact Approaches),通常使用數學建模的方法建立數學模型(包括決策變數,目標函數以及約束條件),通過優化演算法(單純形法,分支定界,分支切割,割平面方法等)解這個數學模型得出問題的最優解。解的好壞由模型建立的是否合理,優化演算法的設計等決定。
對於常見的數學模型,比如線性規劃(Linear Programming),整數規劃 (Integer Programming),混合整數規劃 (Mixed Integer Programming),二次規劃 (Quadratic Programming)等,都可以使用優化求解器IBM Cplex,Gurobi,FICO Xpress,SCIP (前兩個學術用戶可以免費申請,最後一個是開源的)等進行求解,大大節省了求解時間。關於各個優化求解器性能,可參見這個網址,可以看出Cplex 和 Gurobi 的性能總體較好。值得注意的是,這個網站的性能對比僅僅是對比算例的結果,對於其他模型或者算例的結果可能有所不同。比如我最近解決一個問題,同樣的求解器,同樣的問題,變數和約束少的模型求解時間時間是變數和約束多的模型求解時間近十倍。
為什麼使用啟發式演算法呢?使用精確方法雖然可以求得最優解(Optimal Solution),可以從理論上證明求得的解是最優的,但隨著問題規模的擴大(可能呈指數級或者階乘級的增長),對於中等規模或者大規模的問題,在有限的時間內不可能求得最優解(對於我研究的問題,目前可以求得42個機器最優解)。這就需要在求解精讀和運算時間之間有一個折衷和權衡(trade off)。對於大規模的問題,我們不需要求得最優解,只需在短時間內求得次優解(Sub-Optimal Solution)或者滿意解(Satisfactory Solution)(西南交通大學靳番教授和金煒東教授對滿意優化理論做了開創性研究),加之計算機性能的提升,出現了啟發式演算法。
2. 啟發式演算法(Heuristics Algorithm),啟發式演算法是以問題為導向(Problem-oriented)程序,根據問題的特殊結構或者性質來改進解。一般情況下,啟發式演算法比精確方法更容易實現。啟發式演算法包括構造演算法(Construction Algorithm)和 改進演算法 (Improvement Algorithm)等。對於構造演算法(Construction Algorithm),針對布局問題,對於和其它機器流量比較小的機器盡量擺在機器序列的兩端,這樣就可以形成一個啟發式規則,基於流量的排列(Flow-based permutation, FBP), 這樣就可以根據這個規則得到機器序列;另外還有基於機器長度的排列(Length-based permutation, LBP)規則,盡量把長度小的機器排列到中間,基於這規則也可以得到一個機器序列。這樣產生的解都是可行解(Feasible Solution),但一般情況下都不是最優解。對於 改進演算法 (Improvement Algorithm),常見的就是使用基於貪婪方法的爬山法(Hill Climbing),見下圖,它是由一個初始解開始改進解,爬山法太貪婪,容易陷入局部最優(Local Optimum)。如圖所示,從C點搜索到A點,就陷入了局部最優,而問題的全局最優在B點。
3. 元啟發式演算法(Meta-heuristics Algorithm),相對於啟發式演算法,元啟發式演算法是問題獨立(Problem-independent)的(感謝英國克蘭菲爾德大學 @宋伯陽 博士的更正!),是針對大範圍的優化問題提供通用的流程。一般地,需要提供至少一個初始可行解(Initial Feasible Solution),在預定義的搜索空間高效搜索用以迭代地改進解。可以分為基於單個解(Single solution based)的元啟發式演算法,例如: 模擬退火演算法 (Simulated Annealing)和禁忌搜索演算法(Tabu Search); 另外是基於群體(Population based)的元啟發式演算法,比如遺傳演算法(Genetic Algorithm),分散搜索演算法(Scatter Search Algorithm),粒子群演算法(Particle Swarm Optimization)和蟻群演算法(Ant Colony Optimization)等。元啟發式演算法可以使用某些操作跳出局部最優。關於更詳細的分類,可以參考下圖:
現在越來越多的學者使用混合演算法(Hybrid Algorithm),包括元啟發式演算法與精確方法的混合,比如這篇09年的綜述文章:Hybridizing exact methods and metaheuristics: A taxonomy。對於雙行布局問題,既要確定機器排列順序,又要確定機器的精確位置,這是一個組合優化和連續優化結合的問題,對於大規模的算例,需要元啟發式演算法和精確方法協同解決。元啟發式演算法與啟發式演算法的混合,元啟發式演算法的性能非常依賴初始解的質量,可以使用啟發式演算法為元啟發式演算法產生初始解,以提高其性能。元啟發式演算法與元啟發式演算法的混合,可以參考11年的綜述文章:Hybrid metaheuristics in combinatorial optimization: A survey。演算法的混合可以發揮各個演算法的優點,抵消其缺點,以實現更好的性能。
大數據,AI 是未來的趨勢,現在很多領域(醫療,製造,物流等)都朝這個方向發展, @Robin Shen 在「[運籌帷幄]大數據和人工智慧時代下的運籌學」知乎專欄中提到:「人工智慧、大數據,最終幾乎都歸結為一個求解能量最小的優化問題,而運籌學正是研究優化理論的學科。因此,我把運籌學/優化理論稱為人工智慧、大數據的「引擎」。」。
隨著技術的進步,我們有理由相信優化運籌領域在國內會發展的越來越好!
—————————————2017年8月11日補充—————————————
在 @Robin Shen 建立的運籌優化微信群中對這個問題進行討論,分享兩位博士的觀點:
英國克蘭菲爾德大學@宋伯陽 博士:個人理解,輕拍:演算法如果只分兩種,就是精確演算法和啟發演算法。所有啟發、元啟發演算法都不是精確演算法 (不保證能得到最優解),啟發演算法和元啟發演算法最大的區別是,啟發演算法更多求局部最優(local optimal不知道翻譯正確不),元啟發演算法設計有克服陷入局部優化的機構,更適合尋求全局最優,比如遺傳演算法GA有突變Mutation機構。其次,啟發演算法的設計更多是取決於問題Problem-dependent,元啟發演算法是獨立於問題Problem-independent (可以作為一個black box操作,適用性廣,但還是要根據問題調演算法各種參數)。元啟發演算法範圍內大部分應用了隨機優化機構,多目標優化用的蠻多。但是多目標優化中,目標太多時一般會先降維(比如PCA),多於3-5個目標的優化效率低,也沒有太多實際的可讀性。接近實際的案例裡面一般都會涉及多種演算法,先用元啟發演算法求得一個小範圍的滿意解,再用啟發或者精確演算法找最優解,這樣即提高了計算效率又能有高質量結果。(演算法種類和術語名字太多,看到各種名字很容易暈,其實很多都有相關性(差不多),弄清楚他們之間的關係還是有點重要的)。
德國海德堡大學陳曉宇博士:
1. 每種進化演算法都有跳出最優解的機制或者運算元。但是要用進化演算法求解大規模組合優化問題時,首先應該根據問題類型(比如優化參數類型)選擇適合的演算法,然後考慮問題所具有的特性,引入數學規劃方法和設計一些相應的啟發式運算元去指導尋優策略。如果只是簡單套用某個進化演算法,或把它當作黑盒操作,效果往往都不會太好,意義不大。
2. 演化演算法在2000-2007年間就火爆過一次了,並且有各種模擬自然界物種的進化演算法被提出來,很多領域都有被應用。在進化演算法領域,Deb和張青富教授算得上是多目標優化的領軍人物了。張青富07年將數學規劃方法和進化演算法相結合提出了基於分解的多目標進化演算法(MOEA/D)。Deb最新提出的NSGA-III貌似可以很好的求解到20個目標(之前看過一篇文章中寫的,不是很確定是不是20)。還有姚鑫、金耀初、周愛民、公茂果、王勇...教授各個都是大牛(不過好多在國外)。個人認為,基本所有的組合優化問題都可以用演化演算法去解(但是效果不一定好)。
首先,贊同xn geo的說法。然後回答你的問題,嚴格來說,神經網路和前三種演算法不是一類的。遺傳演算法、模擬退火和粒子群演算法都是用來做優化的,神經網路可以理解為做簡化的。前三種演算法我們稱為啟發式演算法,他們是對自然過程的數學模擬。其中,遺傳演算法是對自然界生物種群優勝劣套的模擬;模擬退火是對熱力學中退火過程的模擬,而粒子群演算法則是對鳥群捕食行為的模擬。我們運用這些演算法可以計算出一個問題的近似最優解。這些演算法與Matlab沒有必然聯繫,更多的是一種思想。神經網路一般是用於對一個複雜問題的簡化模擬,就比如我們建立了一個非常複雜的模型,由於這個模型計算起來相當耗時,我們就可喲根據這個模型的輸入輸出來訓練一個能達到相近效果的神經網路,從而簡化了計算。以上是我的理解,如有不對地方還請指正。
遺傳演算法適合大海撈針,可以並行運算,離散型的,如反潛艇搜索。神經網路是黑箱模擬,適合無確定規律性的,如下圍棋,有神經網路晶元,離散型的。粒子群演算法是散彈,適合撒網捕魚,解決目標難有行蹤問題,如用於投資撒網,離散型的。模擬退火是跳山搜索,防止陷入局部最優解,適合組合優化問題,並行運算難。對於遺傳演算法,神經網路通用性比較強,研究應用比較多。深度學習的崛起,讓神經網路在解決複雜難建模如圖像識別,圍棋,語音等領域應用方興未艾。現代智能演算法,往往結合大數據平台,gpu運算,並行計算,HPC,多模式結合等手段,來完成更加複雜多變的業務需求。
常用的智能演算法如下,可以結合使用:
基於仿生/模擬演算法:
人工神經網路深度學習
遺傳演算法
人工免疫演算法
蟻群演算法
粒子群演算法
人工魚群演算法
文化演算法
禁忌搜索演算法
模擬退火演算法
基於數學理論演算法:
線性規劃回歸分析
梯度下降
K近鄰演算法
SVM支持向量機
樸素貝葉斯
決策樹
圖論演算法
並行演算法
模糊數學
混沌演算法
馬爾可夫鏈你說的這些演算法分為兩類,都是上個世紀八九十年的產物。這兩類簡單分就是啟發式最優化演算法,函數近似/逼近演算法
第一類演算法:啟發式優化演算法
無論遺傳演算法,模擬退火演算法,粒子群演算法,還是後來的森林演算法,煙花演算法,蟻群演算法,這一類都是全局尋優演算法。簡單的說就是人們把一些問題用一個優化模型建模了,解這個優化模型就可以得到問題的答案。但是這些模型不能或者很難用普通的數值優化辦法快速得到結果,於是人們就借鑒大自然中的一些自然現象(比如生物遺傳變異,鳥類覓食等)作為搜索的隨機變化條件,以期望能快速收斂到最優解。這類方法對於有多個極值點的問題以及大部分組合優化問題的效果並不好。
第二類演算法:函數近似/逼近演算法
神經網路等近似方法進行函數映射逼近。主要用於得到一個映射,能從X得到Y。相當於是本來有一個很的映射,但是只提供了一些數據,我們就用神經網路去你和這些數據,以期望得到這個映射。但現實往往是數據有雜訊,數據量不夠,導致過擬合。第二類演算法和第一類的聯繫就是,要求得第二類演算法的映射函數,需要解一個優化問題,那麼理論上講是可以用第一類演算法解決的,但是人們更希望用更高效的數值演算法解決。
僅從運籌學、數學規劃的的角度,解決實際問題的一般步驟:建立數學模型-設計演算法-編程實現。
以上(遺傳等等演算法)是求解優化問題的演算法,而首先要思考的,演算法之上的數學模型是什麼?
在4中,我介紹了這些演算法最常見應用領域(組合優化問題)及其數學模型。
而神經是優化模型,反向傳播法是這個模型下求解優化問題的演算法。
正式回答該問題前,先簡介一下運籌學--Operations Research (O.R.), 別名數學規劃、最優化理論,當然並不完全等價。此外我還把其稱為人工智慧的「引擎」,因為幾乎所有人工智慧的問題最後都會轉化為求解一個優化問題。五年前流行的支持向量機(SVM,二次規劃問題)如此,近倆年席捲全球的深度學習(DL)的參數優化(訓練)也是(高度複合函數無約束優化問題)。
對於運籌學還不是很了解的朋友,或許下面的文章會有用:
人工智慧的「引擎」--運籌學,一門建模、優化、決策的科學
我所建的全球運籌學者群中對該問題進行了激烈的討論,英國Cranfield大學@宋伯陽 認為:演算法如果只分兩種,就是精確演算法和啟發演算法。所有啟發、元啟發演算法都不是精確演算法 (不保證能得到最優解),啟發演算法和元啟發演算法最大的區別是,啟發演算法更多求局部最優,元啟發演算法設計有克服陷入局部優化的機構,更適合尋求全局最優,比如遺傳演算法GA有突變Mutation機構。其次,啟發演算法的設計更多是取決於問題Problem-dependent,元啟發演算法是獨立於問題Problem-independent (可以作為一個black box操作,適用性廣,但還是要根據問題調演算法各種參數)。元啟發演算法範圍內大部分應用了隨機優化機構,多目標優化用的蠻多。但是多目標優化中,目標太多時一般會先降維(比如PCA),多於3-5個目標的優化效率低,也沒有太多實際的可讀性。接近實際的案例裡面一般都會涉及多種演算法,先用元啟發演算法求得一個小範圍的滿意解,再用啟發或者精確演算法找最優解,這樣即提高了計算效率又能有高質量結果。(演算法種類和術語名字太多,看到各種名字很容易暈,其實很多都有相關性(差不多),弄清楚他們之間的關係還是有點重要的)。
------------------------------------------------------------------------------
對這些演算法沒有特別的研究,但是在七年的運籌學學習中也或多或少有所接觸。僅從啟發式演算法、近似演算法和整數規劃精確演算法的角度捋一下他們之間的關係。
1,啟發式演算法(Heuristic Algorithm)
首先前三類演算法應該都屬於啟發式演算法(概念問題,不確定?),經常被用來解組合優化問題。
由於組合優化通常是NP(完全)困難(全局最優解通常需要指數級演算法複雜度,不存在多項式時間演算法)的,現實應用中需要演算法(通常多項式時間演算法)來快速得到質量較高的可行解,以上三種演算法便可以一試。
此外這三個演算法模仿生物進化原理設計演算法,本質上還是貪心演算法(有閥值)和(蒙特卡羅)隨機演算法(有一定概率跳出局部最優區域)。
另外要注意的是,以上演算法通常不是多項式時間收斂。
2,貪心演算法(Greedy),近似演算法(Approximation)
其次求解組合優化問題時,近似演算法也經常用到,他們本質上是貪心演算法,而且通常都是多項式時間的演算法。
與一般的貪心演算法不同,他們通過巧妙的演算法設計,可以用嚴格的數學證明這個演算法得到的解,離全局最優解差A倍。A被稱為近似係數。
例如一個最大化的組合優化問題,假設全局最優解的目標函數為100,那麼近似係數A=2的近似演算法收斂求得的解一定在[100,200],最壞情況是200。
理論計算機方向便是專門研究近似演算法的,其頂級會議FOCS,STOC,SODA是其頂級會議。
3,數學模型、精確演算法(Exact)
組合優化問題的精確演算法,是混合整數規劃模型下的優化演算法,然後用分支定界法求解。然而分支定界法是指數級複雜度的,例如n是0,1變數的個數,那麼最壞情況下,分支定界法最壞情況需要求解2^n個線性規劃問題(多項式時間可解),才能得到全局最優解。
因此通常的做法是,先用1或2的演算法,得到一個可行解F,然後把這個可行解F作為初始解插入到分支定界法的優化求解器(例如Cplex),作為上界(Min 問題)。
這時候,混合整數規劃模型的意義有倆點:
一,只需要求解Root node(原問題的線性鬆弛問題),便得到原問題的下界,上下界的所形成的百分比(GAP),便可作為F質量的檢驗標準。(上界=下界時,GAP=0,即已找到全局最優解)
二,隨著分支定界法分支的求解,優化求解器很有可能找到比F更優的解,從而縮小GAP。
在工業應用中,例如最小化企業成本,我們通過1或2可以較為快速地得到一個方案(可行解),其成本為F。然後我們設計一個混合整數規劃模型,那麼我們可以很快地知道F這個解到底有多好,其次,優化求解器可以幫我們找到一個更優的解G,縮小GAP 例如2%。
可別小看這2%,在工業界,2%的成本可能已經是幾百甚至上千萬的差別!!!
更多介紹:
混合整數規劃/離散優化的精確演算法--分支定界法及優化求解器
4,神經網路
神經網路,包括CNN(深度學習的底層模型),他是一個模型,而不是演算法。其目標函數是一個高度複合的無約束的函數,而訓練參數的過程(演算法),通常使用方向傳播法。可以把它理解為一種特殊的梯度下降法。
CNN裡面,有Relu和Dropout,前者是為了提高函數的非線性性,後者為了簡化函數參數的訓練。
這個高度複合的函數是極度非凸函數,很難求解全局最優解,但是貌似有理論證明(還是大量實驗表明?),方向傳播法求得的局部最優解,通常已經是一個非常好的解(並且存在大量類似高質量的局部最優解,因此隨便找到哪一個都是不錯的結果)。
但是,由於沒有約束條件,在相同維度(變數個數)下,運籌學的模型由於約束條件的存在,都比它複雜很多很多。
和3同樣的思路,我可以把神經網路求得的局部最優解,作為初始解放入混合整數規劃(MIP)模型,然後利用優化求解器給出GAP以及搜索更優解。(當然CNN解決的問題通常規模實在太大,MIP通常跑不動:)
更多介紹:
離散/整數/組合/非凸優化概述及其在AI的應用
大話「人工智慧、數據科學、機器學習」--綜述
--------------------------------------------------------------------------------------------------------
如果你是運籌學博士或博士在讀,歡迎知乎私信我,我會拉你進全球運籌學者群(私信請附上個人或機構主頁)。
歡迎大家關注我的運籌學專欄,會陸續發布運籌學、人工智慧相關乾貨,也歡迎同行投稿:
[運籌帷幄]大數據和人工智慧時代下的運籌學 - 知乎專欄
歡迎參加2017.6.11和7.29號舉辦的「運籌學系列」知乎live,探討關於運籌學、優化、AI的相關話題:
大數據人工智慧時代的運籌學-知乎Live入口
知乎 Live - 運籌學與供應鏈、金融大數據 (與斯坦福大學博士、明尼蘇達大學王子卓教授合辦的喲:)
首先這個不是MATLAB的演算法吧其次遺傳演算法 粒子群演算法是用於最優化問題 神經網路一般用於分類和回歸
遺傳演算法 模擬退火 以及 粒子群,都是求接近最優解的演算法。本質上就是一個數學窮舉問題優化,比如讓你求一下一堆數據的最大值,這些演算法都可以用窮舉來做,只是窮舉過程需要漫長的幾天到幾十年以上。如果使用這三種演算法,就會非常快速的逐漸求出一個非常接近最優解的結果,時間比窮舉要少很多,而結果即便有些許不是完美解,也基本符合實際需要。完美解只有窮舉之後才能得到。
這三種演算法的每一步,每一個步驟每一個參數都是有現實的物理意義數學意義的。神經網路就不同於其他三種演算法了。往往你會驚訝於一小塊白白的腦漿就能指導蟑螂在非常複雜環境下存活。神經網路就是初步向這種黑箱子式的自然界解決問題的思路靠攏的一個嘗試。裡面每個變數都是毫無意義的,就好像神經元A與神經元B之間有個突觸傳導電流,這個電流到底是什麼意思、如何影響生物活動,人類一點也搞不懂。你輸入一個值,經過非常複雜的運算之後它就會給你輸出這個值對應的結果。當然神經網路需要訓練,輸入一些已知的變數值和相對應的結果值,讓系統自發的修正內部參數實現擬合。對神經網路沒有過學習,但我理解中前三種演算法都是最優解的搜索過程模擬其他過程而得到的優化演算法。
如果學習過基礎的運籌學,我們知道,在線性規劃中有經典的單純形法,從單純形的各個頂點出發去找最優解。這是一種按照確定的方向/規則去尋找最優解的方法,即其他答主回答中有所陳述的精確解法。
這裡是這樣一種思路,規劃問題求最優解是一個搜索過程,通過「嘗試-判斷」的反覆來「找」到最值。面對同一個問題時,搜索如何展開,就直接決定了演算法的求解效率;如何判斷與評價,就決定了解的質量。
相比於精確演算法,模擬退火、遺傳演算法、粒子群演算法、蟻群演算法這樣的元啟發式演算法對最優解的尋找沒有一個確定的方向,它們尋找最優解的方向與演算法自身的適應規則有關,在局部某一/幾步是隨機的、但總體來說是有趨向性的。
這種演算法在初接觸到的時候令我感到十分巧妙,但它們的「道理」其實就是對「優化方向」的設計。不僅僅可以是固體退火、基因遺傳、鳥群覓食、螞蟻回家,可以是其他任何有趨向性的過程,重要的是演算法所表現出來的優良性能彌補了已有演算法的哪些局限。
以上都是個人理解……難免有謬誤,希望可以在評論區友好探討ヽ(??ω?? )ゝ
關於啟發式演算法和元啟發式演算法的區分,目前最高贊答主大洪的回答中有提到,知乎也有胖友提過這個問題http://www.zhihu.com/question/29919290?utm_source=com.example.android.notepadutm_medium=social前三種是做優化的演算法,以我在的電力領域舉個例子。例如一年24小時的電價不同,你需要制定一個電池的充電計劃,讓其既可以滿足能量平衡的約束,又可以讓你的電在高價時賣出,低價時買進。這個時候,你的目標是收益最大化。那麼你有N種可能性,第一個小時你可以充電、放電或者不充不放,第二/三/四...個小時也是如此。現在沒有優化的話,你就要窮舉這3的24次方種可能性,分別計算一遍。但是有了優化,你就可以不用窮舉,讓他自動達到最優,這樣就快很多倍。遺傳演算法是模擬生物遺傳的,具體方法是,你隨機產生一組數據,可以用上蒙地卡羅場景來生成,然後讓這些數據交叉,例如,數據一是01000110,數據二是10110010,你讓這兩組數據交換一小個片段,相當於生物中的交配和遺傳變異,具體表現是,如果有兩個數據:6.9,7.3交叉一下,可能就變成了6.4,7.1,然後,再來評估,不滿足條件的數據殺掉,剩下滿足條件的再繼續交叉,一直到滿足條件為止。遺傳上也是一樣的,要白色的狗,就讓一群雜交狗互相交配,然後留下白色多的,再讓其交配幾代,最後可以得到白色的狗。模擬退火和粒子群也是一樣的作用,只是他們的模擬過程不同。需要注意的是,要滿足生成的東西是全局最優,不是局部的。神經網路沒有做過,但是控制上有用過,可以先建立一個模型,然後通過不停的學習和改進,讓系統輸出達到與真正模型一樣的效果。這些演算法在控制上都有應用,現在流行做預測控制,用重複學習,深度學習等控制方法。
自己干過遺傳演算法,也幫不少人寫過螞蟻演算法,PSO,免疫演算法的文章,感覺這東西尋找最大值還是挺快的,但是找不到的情況也多。一句說到底,就是說起來高深的東西,其實實際作用還真低。
元啟發式搜算演算法(meta-heuristics),解決NP難或者NP完全問題的有效方法。有時候也稱為軟計算,由於該類演算法的起源於人工智慧,所以也叫智能優化演算法。除神經網路以外,其他演算法都是用來搜索的。這裡不說神經網路,因為現在這個傢伙已經不是以前的它了。
該類演算法的特點是簡潔暴力快速,容易並行化,只要定幾個領域結構和參數,幾乎不需要什麼理論基礎就可以對一個問題進行優化。比如著名的TSP問題,目前最快的演算法就是基於遺傳演算法的實現。大部分NPC問題的最快演算法一般都是這種方法。
當然,這種演算法也有缺點,早期理論性不足,不過目前歐洲的幾個大牛也開始研究這種演算法的複雜性了,國際會議FOGA也是專門研究這種演算法的理論基礎的。另外一個最主要的特點,與傳統的基於數學規劃的確定性演算法對比,我們只能找到一個比較好的解,但是我們並不知道,這個解到底是不是這個問題的最好的解。比如我跑演算法跑了半天搜索到一個最優值是100,沒法找到更好的了。但是這個問題真正的最優解是多少?也許是50?或者20?這個數值我們就不知道了。所以從理論的角度來看,有點先天不足。
如果想做研究的話,好入門,難精通。不過這個領域的科研人員不管從廣度、深度還是大牛的水平來說,還是非常深厚的,院士啥的都有。東西也好玩,人工智慧、運籌學、音樂美術設計各種應用五花八門,國際會議也是盛會型。歐洲美國各有據點。前三種屬於meta-heuristic優化演算法,基本思路都是通過不斷的隨機嘗試來尋找最優解。不同的名稱是由於指導如何隨機的思路不同,但是基本的原理是相同的,簡單的講就是在一個解的區域密集尋找最優解的同時,隨機的嘗試一些不同的解的區域。遺傳演算法這類演算法,被發明出來的原因是為了解決比較難用經典優化演算法解決的問題,比如存在多個局部最優的問題。舉個簡單的例子,比如我們想知道一座山的最高峰在哪裡,經典優化理論像是找一個人爬山,沿著山脊一路向上,就能到頂峰(最大值),但是如果問題是個山脈,有好多山峰,這樣經典優化理論可能找到的不是最高的峰。遺傳演算法這些,會用10個人放在不同的位置同時開始找,可以爬山,有時候也可以下山,以找到附近的可能更高的山峰。至於解決什麼問題,裝逼點講,任何問題都屬於優化問題,就是說只要問題可以被寫成一個優化的問題,就可以用這些演算法去解。但是這類演算法壞處也很多,缺乏嚴格的理論基礎是很重要的一條。神經網路可以看成是模擬人的大腦,通過大量的歷史數據培訓,讓演算法學會判斷。比如我們看到一個人一般情況下可以判斷對方是男是女,可以培訓一個神經網路,通過規定一些指標(身高,三維等等),然後用1萬個男女的指標數據進行培訓,當它收到一個新的數據,就可以判斷說是男是女了。當然,只是一個非常簡單的解釋,背後理論也是有很多很多。
前三個是最優化演算法,既然是最優化演算法,自然是為了給實際問題尋求最優化答案的。。
作比賽的話大部分不實用,聽起來高大上而已
不知道題主是想知道這些智能優化演算法目前應用的領域還是認為這些演算法無用?如果想了解應用的領域可以看下進化演算法領域的期刊,Evolutionary Computation | MIT Press Journals其次,這些演算法的思想來源像其它答主所說,是對自然過程的模擬,但是我認為這些演算法早已超越了這個階段,已經大量的與數學結合,其過程也更加嚴謹,也有很多證明收斂性的文章,其實還是有很多的工作可以做。
前三個多數找最優解,最後一個相當於對黑箱系統的擬合吧。實現功能的參考代碼遍地都是,看看原理,找找注釋好的,照貓畫虎編一個應該不難。當然這些演算法裝逼很好用,都能跑出個結果。效果就因人而異了。比如神經網路,前期要大量數據訓練,而且是處理過的數據(比如1.2和2.4表示相同的情況)如果不看應用背景冒泡套代碼效果很可能一般的。。。