491      阿裏雲  技術社區[雲棲]

獨家 | 一文讀懂優化算法

一、前言

模擬退火、遺傳算法、禁忌搜索、神經網絡等在解決全局最優解的問題上有著獨到的優點，其中共同特點就是模擬了自然過程。模擬退火思路源於物理學中固體物質的退火過程，遺傳算法借鑒了自然界優勝劣汰的進化思想，禁忌搜索模擬了人類有記憶過程的智力過程，神經網絡更是直接模擬了人腦。它們之間的聯係也非常緊密，比如模擬退火和遺傳算法為神經網絡提供更優良的學習算法提供了思路。把它們有機地綜合在一起，取長補短，性能將更加優良。 這幾種智能算法有別於一般的按照圖靈機進行精確計算的程序，尤其是人工神經網絡，是對計算機模型的一種新的詮釋，跳出了馮·諾依曼機的圈子，按照這種思想來設計的計算機有著廣闊的發展前景。

二、常用數據處理算法

2.1 灰色關聯分析（GM）

2.1.1 簡介

灰色理論認為係統的行為現象盡管是朦朧的，數據是複雜的。灰色理論建立的是生成數據模型，不是原始數據模型。所謂灰色係統是介於白色係統和黑箱係統之間的過渡係統，其具體的含義是：如果某一係統的全部信息已知為白色係統，全部信息未知為黑箱係統，部分信息已知，部分信息未知，那麼這一係統就是灰色係統。一般地說，社會係統、經濟係統、生態係統都是灰色係統。例如物價係統，導致物價上漲的因素很多，但已知的卻不多，因此對物價這一灰色係統的預測可以用灰色預測方法。

灰色係統理論認為對既含有已知信息又含有未知或非確定信息的係統進行預測，就是對在一定方位內變化的、與時間有關的灰色過程的預測。盡管過程中所顯示的現象是隨機的、雜亂無章的，但畢竟是有序的、有界的，因此這一數據集合具備潛在的規律，灰色預測就是利用這種規律建立灰色模型對灰色係統進行預測。灰色預測通過鑒別係統因素之間發展趨勢的相異程度，即進行關聯分析，並對原始數據進行生成處理來尋找係統變動的規律，生成有較強規律性的數據序列，然後建立相應的微分方程模型，從而預測事物未來發展趨勢的狀況。

2.1.2 食品價格灰色關聯分析

針對食品價格趨勢預測，運用灰色關聯分析法，深入分析我國的食品價格指數與哪些商品價格有關聯，而又在多大程度上影響了CPI的上漲，從而說明影響物價的因素來自多方麵的，有糧食生產、流通成本上漲、自然因素、國家調控作用等等，進而說明食品價格是一個動態的經濟模型，對預測食品價格變化有一定的作用。

表1 食品價格指數

圖1 各類食品價格指數變化趨勢圖

灰色關聯分析MATLAB主要程序代碼：

2.2 偏最小二乘回歸（PLS）

2.2.1 簡介

在實際工作中，經常需要研究兩組多重相關變量間的相互依賴關係，並研究用一組變量（常稱為自變量和因變量）去預測另一組變量（常稱為因變量和響應變量），除了使用最小二乘準則下的經典多元線性回歸分析（MRL）、提取自變量組主成分回歸分析（PCR）等方法外，還可以利用近幾年發展起來的偏最小二乘（PLS）回歸方法。

具體的偏回歸流程圖如圖所示：

圖2偏回歸流程圖

2.2.2 偏最小二乘數據分析

根據體能訓練的數據進行最小二乘回歸建模，樣本為某健身俱樂部20位中年男子身體特征指標，包括體重、腰圍和脈搏，如表2所示。

表2 體能訓練數據

   在預測圖3上，如果所有點都能在圖的對角線附近均勻分布，則方程的擬合值與原值差異很小，這個方程的擬合效果就是滿意的。

圖3 體能訓練預測圖

MATLAB主要程序代碼：

2.3 時間序列（ES）

2.3.1 簡介

時間序列數據是指按照時間先後依次排列的觀測值所構成的數列，如各年度的國內生產總值、人口數據等。研究時間序列數據模型處理的主要目的是進行數據預測，如預測下一年度的銷售額、預測股票價格的走勢等。

時間序列的預測方法有很多，一般的處理方法有：

• 先繪圖確定時間序列的類型，再選擇適當的預測方法。

• 平穩序列的預測方法：簡單平均法、移動平均法、指數平滑法（1階，2階，3階，…）；

• 非平穩序列的預測方法：指數平滑法和自回歸預測、曲線擬合和回歸分析等；特別對於含季節趨勢的預測方法包括時間序列分解（利用乘法模型先進行趨勢預測，再進行季節變動分析，然後用它們的乘積來進行預測）和季節多元回歸模型（利用加法模型把趨勢和季節放在一個模型中進行回歸分析，得到回歸方程，然後利用該方程來進行預測）。

2.3.2 食品價格分析

表3  食品零售價格數據

圖4鮮菜類食品增長率曲線

MATLAB主要程序代碼：

2.4 馬爾科夫鏈（Markov）

2.4.1 簡介

馬爾科夫鏈是數學中具有馬爾科夫性質的離散時間隨機過程。對於離散時間隨機過程，在給定當前知識或信息的情況下，過去（即當期以前的曆史狀態）對於預測將來（即當期以後的未來狀態）是無關的。因此馬爾科夫鏈有眾多的應用，如人口過程、排隊理論、食品價格趨勢、統計學應用等。

2.4.2 食品價格趨勢預測

MATLAB主要程序代碼：

2.5 貝葉斯（Bayes）

2.5.1 簡介

貝葉斯統計方法是基於貝葉斯定理而發展起來用於係統地闡述和解決統計問題的方法。貝葉斯統計方法不同於經典統計方法。經典統計方法隻利用兩種信息：一是模型信息，二是樣本信息。然而貝葉斯統計方法的核心是貝葉斯公式。貝葉斯統計方法在統計過程中用到了先驗概率分布，即決策者的主觀因素。可以說在統計過程中是否使用先驗概率分布是區分貝葉斯統計方法和非貝葉斯統計方法的標誌。使用不同的先驗概率分布對後驗概率分布的確定是有影響的。但是貝葉斯學派已經證明，開始時不管使用什麼樣的先驗概率分布，隨著實驗次數的增多，後驗概率分布對初始先驗概率分布的依賴會越來越小，後驗概率分布最終趨於一致。

貝葉斯（Bayes）預測是一種以貝葉斯統計方法為基礎、以貝葉斯定理為理論依據，以動態模型為研究對象的時間序列預測方法。貝葉斯（Bayes）預測方法在統計推斷中不僅僅使用了模型信息及樣本數據信息，還使用了先驗概率分布信息，這也是不同於非貝葉斯統計預測的標誌。貝葉斯預測在預測過程中，對總體分布的未知參數預先規定一個先驗概率分布，此概率分布可以是根據以前的數據、經驗給出，也可以是完全根據決策者的主觀意識給出。這樣將先驗概率分布、總體分布、樣本信息通過貝葉斯定理（貝葉斯公式）就可以得到後驗概率分布，通過後驗概率分布對預測目標進行預測。

貝葉斯網絡作為機器學習的一個分支，在處理不確定問題以及複雜係統中多因素間的相互依賴問題時，它具有推論和可視化兩方麵的獨一無二的強壯性。而航班延誤正是一個這樣的問題，直接影響航班延誤的因素有很多，產生延誤的間接影響因素較多，部分因素之間還有一定的依賴關係。故貝葉斯網絡可作為分析和預測航班延誤的方法和手段。

2.5.2 基於貝葉斯網絡模式識別

三、神經網絡算法

人工神經網絡（artificial neural network，ANN）是模仿生物神經網絡功能的一種經驗模型。生物神經元受到傳入的刺激，其反應又從輸出端傳到相聯的其它神經元，輸入和輸出之間的變換關係一般是非線性的。神經網絡是由若幹簡單（通常是自適應的）元件及其層次組織，以大規模並行連接方式構造而成的網絡，按照生物神經網絡類似的方式處理輸入的信息。模仿生物神經網絡而建立的人工神經網絡，對輸入信號有功能強大的反應和處理能力。人工神經網絡需要有一定量的曆史數據，通過曆史數據的訓練，網絡可以學習到數據中隱含的知識。

3.1 BP神經網絡

3.1.1 簡介

BP（Back Propagation）神經網絡是一種神經網絡學習算法。其由輸入層、中間層、輸出層組成的階層型神經網絡，中間層可擴展為多層。相鄰層之間各神經元進行全連接，而每層各神經元之間無連接，網絡按有教師示教的方式進行學習，當一對學習模式提供給網絡後，各神經元獲得網絡的輸入響應產生連接權值（Weight）。然後按減小希望輸出與實際輸出誤差的方向，從輸出層經各中間層逐層修正各連接權，回到輸入層。此過程反複交替進行，直至網絡的全局誤差趨向給定的極小值，即完成學習的過程。

BP算法是一種有監督式的學習算法，其主要思想是：輸入學習樣本，使用反向傳播算法對網絡的權值和偏差進行反複的調整訓練，使輸出的向量與期望向量盡可能地接近，當網絡輸出層的誤差平方和小於指定的誤差時訓練完成，保存網絡的權值和偏差。

具體步驟如下：

• 初始化，隨機給定各連接權及閥值；

• 由給定的輸入輸出模式對計算隱層、輸出層各單元輸出；

• 計算新的連接權及閥值；

• 選取下一個輸入模式對返回第2步反複訓練直到網絡設輸出誤差達到要求結束訓練。

BP神經網絡具有以下優點：

• 非線性映射能力：BP神經網絡實質上實現了一個從輸入到輸出的映射功能，數學理論證明三層的神經網絡就能夠以任意精度逼近任何非線性連續函數。這使得其特別適合於求解內部機製複雜的問題，即BP神經網絡具有較強的非線性映射能力。

• 自學習和自適應能力：BP神經網絡在訓練時，能夠通過學習自動提取輸出、輸出數據間的“合理規則”，並自適應的將學習內容記憶於網絡的權值中。即BP神經網絡具有高度自學習和自適應的能力。

• 泛化能力：所謂泛化能力是指在設計模式分類器時，即要考慮網絡在保證對所需分類對象進行正確分類，還要關心網絡在經過訓練後，能否對未見過的模式或有噪聲汙染的模式，進行正確的分類。也即BP神經網絡具有將學習成果應用於新知識的能力。

• 容錯能力：BP神經網絡在其局部的或者部分的神經元受到破壞後對全局的訓練結果不會造成很大的影響，也就是說即使係統在受到局部損傷時還是可以正常工作的。即BP神經網絡具有一定的容錯能力。

3.1.2 BP神經網絡的語音信號識別

語音特征信號識別是語音識別研究領域中的一個重要方麵，一般采用模式匹配的原理解決。語音識別的運算過程為：首先，待識別語音轉化為電信號後輸入識別係統，經過預處理後用數學方法提取語音特征信號，提取出的語音特征信號可以看成該段語音的模式。然後將該段語音模型同已知參考模式相比較，獲得最佳匹配的參考模式為該段語音的識別結果。語音識別流程如圖5所示。

圖5語音識別流程圖

MATLAB主要程序代碼：

3.1.3 人臉方向預測

• 首先提取特征數據；

• BP神經網絡進行數據訓練、預測、檢驗；

MATLAB主要程序代碼：

3.1.4 蝴蝶花分類預測

算法步驟：

• 初始化數據，設定各層節點數、學習效率等值；

• 輸入層FA輸入樣品，計算出隱層FB活動；

  b(ki)=logsig(a*V(:,ki)+Pi(ki))

• 計算出輸出層FC活動；

  c(kj)=logsig(b*W(:,kj)+Tau(kj))

• 網絡輸出和期望輸出相比較，計算出輸出層FC的錯誤；

  d=c.*(1-c).*(ck-c)

• 反傳，計算出隱層FB的錯誤；

  e=b.*(1-b).*(d*W')

• 修改FC層和FB之間的權值wij；

  DeltaW(ki,kj)=Alpha*b(ki)*d(kj)+Gamma*DeltaWOld(ki,kj)

  W=W+DeltaW

• 修改FA層和FB之間的權值vhj；

  DeltaV(kh,ki)=Beta*a(kh)*e(ki)

  V=V+DeltaV

• 修改偏差。

MATLAB主要程序代碼：

3.2 自組織特征映射神經網絡（SOM）

3.2.1 簡介

1981年芬蘭Helsink大學的T.Kohonen教授提出一種自組織特征映射網，簡稱SOM網，又稱Kohonen網。生物神經係統中，存在一種“側抑製”現象，即一個神經細胞興奮後，通過它的分支會對周圍其他神經細胞產生抑製。由於側抑製的作用，各細胞之間相互競爭的最終結果是：興奮作用最強的神經細胞所產生的抑製作用戰勝了周圍所有其他細胞的抑製作用而“贏”了，其周圍的其他神經細胞則全“輸”了。

自組織特征映射神經網絡（Self-organizing Feature Maps）簡稱SOFM或者SOM，也是一種無導師學習的網絡，主要用於對輸入向量進行區域分類。和自組織競爭網絡不同的是，它不但識別輸入區域臨近的區域，還研究輸入向量的分布特性和拓撲特性結構。SOM網絡模擬大腦神經係統自組織特征映射的功能，是一種競爭型網絡，並在學習中能無導師進行自組織學習。腦神經學研究結果表明：神經元之間的信息交互具有的共同特征是：最近鄰的兩個神經元互相激勵，較遠的神經元互相抑製，更遠的則又具有較弱的激勵作用。

3.2.2 柴油機故障分類

應用SOM神經診斷網絡柴油機故障的步驟如下：

• 選取標準故障樣本；

• 對每一種標準故障樣本進行學習，學習結束後，對具有最大輸出的神經元標以該故障的記號；

• 將待檢樣本輸人到SOM神經網絡中；

• 若輸出神經元在輸出層的位置與某標準故障樣本的位置相同，說明待檢樣本發生了相應的故障；若輸出神經元在輸出層的位置介於很多標準故障之間，說明這兒種標準故障都有可能發生，且各故障的程度由該位置與相應標準故障樣本位置的歐氏距離確定。

MATLAB主要程序代碼：

3.3 Hopfield網絡

3.1.1 簡介

Hopfield網絡是神經網絡發展曆史上的一個重要的裏程碑。由美國加州理工學院物理學家J.J.Hopfield教授於1982年提出，是一種單層反饋神經網絡。1984年，Hopfield設計並研製了網絡模型的電路，並成功地解決了旅行商（TSP）計算難題（優化問題）。

Hopfield網絡是一種互連型網絡，它引入類似於切Lyapunov函數的能量函數概念，在滿足條件的情況下，某種“能量函數”的能量在網絡運行過程中不斷地減少，最後趨於穩定的平衡狀態。對於一個非線性動力學係統，係統的狀態從某一初值出發經過演變後可能有如下幾種結果：漸進穩定點（吸引子）、極限環、混沌、狀態發散。因為人工神經網絡的變換函數是一個有界函數，故係統的狀態不會發生發散現象。

目前，人工神經網絡經常利用漸進穩定點來解決某些問題。如果把係統的穩定點視為一個記憶的話，那麼從初態朝這個穩定點的演變過程就是一個尋找記憶的過程。如果把係統的穩定點視為一個能量函數的極小點，而把能量函數視為一個優化問題的目標函數，那麼從初態朝這個穩定點的演變過程就是一個求解該優化問題的過程。因此，HoPfield神經網絡的演變過程是一個計算聯想記憶或求解優化問題的過程。實際上，它的解決並不需要真的去計算，而是通過構成反饋神經網絡，適當地設計其連接權和輸入就可以達到這個目的。

Hopfield神經網絡模型是一種循環神經網絡，從輸出到輸入有反饋連接。在輸入的激勵下，會產生不斷的狀態變化。對於一個Hopfield網絡來說，關鍵是在於確定它在穩定條件下的權係數。反饋網絡有穩定的，也有不穩定的。對於Hopfield網絡來說，如何判別其穩定性也是需要確定的。

分類：

• 離散Hopfield網絡（DHNN）

  對於離散Hopfield網絡（DHNN）而言，神經元的輸出隻取1和0，分別表示神經元處於激活和抑製狀態。

• 連續Hopfield網絡（CHNN）

  對於連續Hopfield網絡（CHNN）而言，拓撲結構和DHNN的結構相同。不同之處在於其函數g不是階躍函數，而是S形的連續函數。

3.1.2 Hopfield數字識別

用離散Hopfield網絡，使其具有聯想記憶功能,能正確識別阿拉伯數字，當數字被噪聲汙染後仍可以正確地識別。基於DHNN的數字識別：

圖6離散Hopfield網絡算法設計流程圖

MATLAB主要程序代碼：

3.4 模煳RBF網絡

3.4.1 簡介

RBF網絡的學習過程與BP網絡的學習過程類似，兩者的主要區別在於各使用不同的作用函數。BP網絡中隱層使用的是Sigmoid函數，其值在輸入空間中無限大的範圍內為非零值，因而是一種全局逼近的神經網絡；而RBF網絡中的作用函數是高斯基函數，其值在輸入空間中有限範圍內為非零值，因為RBF網絡是局部逼近的神經網絡。

RBF網絡是一種3層前向網絡，由輸入到輸出的映射是非線性的，而隱層空間到輸出空間的映射是線性的，而且RBF網絡局部逼近的神經網絡，因而采用RBF網絡大大加快學習速度並避免局部極小問題，適合於實時控製的要求。采用RBF網絡構成神經網絡控製方案，可有效提高係統的精度、魯棒性和自適應性。

3.4.2 基於模煳RBF的網絡逼近

利用模煳RBF網絡逼近下列函數：

圖7模煳RBF網絡逼近效果

MATLAB主要程序代碼：

四、智能算法

4.1 遺傳算法（GA）

4.1.1 簡介

遺傳算法（Genetic Algorithm）是一類借鑒生物界的進化規律（適者生存，優勝劣汰遺傳機製）演化而來的隨機優化搜索方法。它是由美國的J. Holland教授1975年首先提出，其主要特點是直接對結構對象進行操作，不存在求導和函數連續性的限定；具有內在的隱並行性和更好的全局尋優能力；采用概率化的尋優方法，能自動獲取和指導優化的搜索空間，自適應地調整搜索方向，不需要確定的規則。遺傳算法的這些性質，已被人們廣泛地應用於組合優化、機器學習、信號處理、自適應控製和人工生命等領域。它是現代有關智能計算中的關鍵技術。

由於遺傳算法的整體搜索策略和優化搜索方法在計算時不依賴於梯度信息或其它輔助知識，而隻需要影響搜索方向的目標函數和相應的適應度函數，所以遺傳算法提供了一種求解複雜係統問題的通用框架，它不依賴於問題的具體領域，所以廣泛應用於許多科學。

隨著應用領域的擴展，遺傳算法的研究出現了幾個引人注目的新動向：

• 基於遺傳算法的機器學習，這一新的研究課題把遺傳算法從曆來離散的搜索空間的優化搜索算法擴展到具有獨特的規則生成功能的嶄新的機器學習算法。這一新的學習機製對於解決人工智能中知識獲取和知識優化精煉的瓶頸難題帶來了希望。

• 遺傳算法正日益和神經網絡、模煳推理以及混沌理論等其它智能計算方法相互滲透和結合，這對開拓21世紀中新的智能計算技術將具有重要的意義。

• 並行處理的遺傳算法的研究十分活躍。這一研究不僅對遺傳算法本身的發展，而且對於新一代智能計算機體係結構的研究都是十分重要的。

• 遺傳算法和另一個稱為人工生命的嶄新研究領域正不斷滲透。所謂人工生命即是用計算機模擬自然界豐富多彩的生命現象，其中生物的自適應、進化和免疫等現象是人工生命的重要研究對象，而遺傳算法在這方麵將會發揮一定的作用。

• 遺傳算法和進化規劃（Evolution Programming，EP）以及進化策略（Evolution Strategy，ES）等進化計算理論日益結合。EP和ES幾乎是和遺傳算法同時獨立發展起來的，同遺傳算法一樣，它們也是模擬自然界生物進化機製的智能計算方法，即同遺傳算法具有相同之處，也有各自的特點。目前，這三者之間的比較研究和彼此結合的探討正形成熱點。

遺傳算法的特點：

• 遺傳算法從問題解的串集開始嫂索，而不是從單個解開始。這是遺傳算法與傳統優化算法的極大區別。傳統優化算法是從單個初始值迭代求最優解的；容易誤入局部最優解。遺傳算法從串集開始搜索，覆蓋麵大，利於全局擇優。

• 許多傳統搜索算法都是單點搜索算法，容易陷入局部的最優解。遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進行評估，減少了陷入局部最優解的風險，同時算法本身易於實現並行化。

• 遺傳算法基本上不用搜索空間的知識或其它輔助信息，而僅用適應度函數值來評估個體，在此基礎上進行遺傳操作。適應度函數不僅不受連續可微的約束，而且其定義域可以任意設定。這一特點使得遺傳算法的應用範圍大大擴展。

• 遺傳算法不是采用確定性規則，而是采用概率的變遷規則來指導他的搜索方向。

• 具有自組織、自適應和自學習性。遺傳算法利用進化過程獲得的信息自行組織搜索時，適應度大的個體具有較高的生存概率，並獲得更適應環境的基因結構。

4.1.2 基於遺傳算法的公交排班係統分析

由於城市交通設施建設滯後於交通需求的增長速度，使城市交通狀況日趨惡化，在主要交通道口和某些流量集中的道路上，不同程度地出現交通阻塞現象，城市交通問題已成為製約城市發展的一個瓶頸。運營車輛智能排班問題是公交車輛智能調度需要解決的典型問題之一，在智能交通係統（ITS）的背景下，公交車發車時刻表的製定是城市公交調度的核心內容，是公交調度日常指揮車輛正常運行的重要依據，也是公交調度人員和司乘人員進行工作的基本依據。合理的公交發車時刻表可以幫助公交企業提高車輛利用效率、降低運營成本和減少乘客的等車時間以提高服務質量等。

 圖8 隨時間變化的發車頻率圖

MATLAB主程序代碼：

4.2 基本粒子群算法（PSO）

4.2.1 簡介

粒子群算法（Particle Swarm Optimization，PSO）是一種基於群體的隨機優化技術。與其它基於群體的進化算法相比，它們均初始化為一組隨機解，通過迭代搜尋最優解。不同的是：進化計算遵循適者生存原則，而PSO模擬社會。將每個可能產生的解表述為群中的一個微粒，每個微粒都具有自己的位置向量和速度向量，以及一個由目標函數決定的適應度。所有微粒在搜索空間中以一定速度飛行，通過追隨當前搜索到的最優值來尋找全局最優值。

PSO模擬社會采用了以下三條簡單規則對粒子個體進行操作：

• 飛離最近的個體，以避免碰撞。

• 飛向目標。

• 飛向群體的中心。這是粒子群算法的基本概念之一。

粒子群算法其基本思想是受許多鳥類的群體行為進行建模與仿真研究結果的啟發。Frank Heppner的鳥類模型在反映群體行為方麵與其它類模型有許多相同之處。由於鳥類用簡單的規則確定自己的飛行方向與飛行速度（實質上，每隻鳥都試圖停在鳥群中而又不相互碰撞），當一隻鳥飛離鳥群而飛向棲息地時，將導致它周圍的其他鳥也飛向棲息地。這些鳥一旦發現棲息地，將降落在此，驅使更多的鳥落在棲息地，直到整個鳥群都落在棲息地。粒子群算法與其它的進化類算法類似，也采用“群體”和“進化”的概念，同樣也根據個體的適應值大小進行操作。不同的是，PSO中沒有進化算子，而是將每個個體看作搜索空間中沒有重量和體積的微粒，並在搜索空間中以一定的速度飛行，該飛行速度由個體飛行經驗和群體的飛行經驗進行動態調整。

4.2.2 基於人工免疫PSO的聚類算法

聚類分析指將物理或抽象對象的集合分組成為由類似的對象組成的多個類的分析過程。聚類分析的目標就是在相似的基礎上收集數據來分類。聚類源於很多領域，包括數學，計算機科學，統計學，生物學和經濟學。在不同的應用領域，很多聚類技術都得到了發展，這些技術方法被用作描述數據，衡量不同數據源間的相似性，以及把數據源分類到不同的簇中。

聚類分析作為數據挖掘中的一個很重要的研究領域，有著許多不同的聚類算法。傳統的聚類算法一般分為五類：層次方法、劃分方法、基於網格方法、基於密度方法和基於模型方法。

傳統的聚類算法已經足夠成熟，能夠解決低維數據的聚類問題。但因為實際應用中數據的複雜性，處理許多問題時，現有的算法容易失效，特別是對高維數據和大型數據等情況。因此傳統聚類在高維數據集中進行聚類時，主要存在以下兩個問題：

• 高維數據集中大量存在無關的屬性使得在所有維中存在簇的可能度幾乎為零；

• 高維空間中數據較低維空間中數據分布要稀疏，其中數據間距離幾乎相等是普遍現象，而傳統聚類方法是基於距離進行聚類的，因此傳統聚類方法在高維空間數據分析較吃力。

人工免疫特性分析：多樣性是免疫係統的重要特征之一，研究表明，通過細胞分裂分化作用，抗體的可變區與不變區基因重組，體細胞超變異等方式，免疫係統可產生大量的不同抗體來抵禦各種抗原，從而使免疫抗體庫具有豐富的多樣性。在使用人工免疫係統來求最優解的問題時，一般用抗原表示滿足約束條件的最優解，抗體表示候選解，用抗體和抗原之間的親和力來表示候選解和最優解的接近程度，也就是在約束條件下候選解對於目標函數的滿足程度；而抗體和抗體之間的親和力可反映出不同候選解之間的差異，即抗體的多樣性。從而防止算法陷入局部最優。

通過比較抗體與抗原間的親和力來選擇有效抗體更好地體現了“優勝劣汰”的原則，特別是當待選抗體之間相差不明顯時，“優勝劣汰”的效果更能得到體現，搜索效率會更高.而免疫記憶的引入能夠有效地抑製進化算法優化過程中出現的退化現象，提高進化算法的性能。免疫接種即是免疫記憶引入的一個方麵，有選擇、有目的地利用待求問題中的一些特征信息或知識，提取“疫苗”並接種“疫苗”，從而達到引進的目的。

基於人工免疫粒子群的聚類算法，這將使得聚類算法具有很好的全局收斂性，不僅能夠有效地克服傳統聚類算法對初始值敏感和易陷入局部極小值的問題，並且使得算法具有更快的收斂速度。

在粒子群算法求解聚類問題中，每個粒子作為一個可行解組成粒子群（即解集）。根據解的含義不同，通常可以分為兩種：一種是以聚類結果為解；一種是以聚類中心集合為解。基於人工免疫粒子群算法討論的方法采用的是基於聚類中心集合作為粒子對應解，也就是每個粒子的位置是由 M 個聚類中心組成，M 為已知的聚類數目。

圖9粒子群聚類算法流程圖

MATLAB主程序代碼：

4.3 蟻群算法（ACO）

4.3.1 簡介

最初提出的AS有三種版本：Ant density、Ant quantity和Ant cycle。在Ant density和Ant quantity中螞蟻在兩個位置節點間每移動一次後即更新信息素，而在Ant cycle中當所有的螞蟻都完成了自己的行程後才對信息素進行更新，而且每隻螞蟻所釋放的信息素被表達為反映相應行程質量的函數。

較早的一種改進方法是精英策略（Elitist Strategy），其思想是在算法開始後，即對所有已發現的最好路徑給予額外的增強，並將隨後與之對應的行程記為Tgb（全局最有行程）。當進行信息素更新時，對這些行程予以加權，同時將經過這些行程的螞蟻記為“精英”，從而增大較好行程的選擇機會。這種改進型算法能夠以更快的速度獲得更好的解，但是若選擇的精英過多則算法會由於較早的收斂於局部次優解而導致搜索中的過早停滯。

蟻群算法是一種新型的模擬進化算法，鑒於目前國內尚缺乏這一方麵的研究，其研究剛剛開始，遠未像遺傳算法、模擬退火算法等算法那樣行程係統的分析方法和堅實的數學基礎，有許多問題有待進一步研究，如算法的收斂性、理論依據等更多細致的工作還有待於進一步展開。

單隻螞蟻的行為極其簡單，但由這樣的單個簡單個體所組成的蟻群群體卻表現出及其複雜的行為，如：在螞蟻運動路徑上突然出現障礙物時，螞蟻能夠很快重新找到最優路徑。像螞蟻這類群居昆蟲，雖然沒有視覺，卻能找到由蟻穴到食物源的最短路徑，究其願意，馬一個題之間通過一種稱之為信息素（pheromone）的物質進行信息傳遞，從而能相互協作，完成複雜的任務。螞蟻之所以表現出複雜有序的行為，個體之間的信息交流和相互協作起著重要作用。

螞蟻在運動過程中，能夠在它所過的路徑上留下該物質，並以此指導自己的運動方向。螞蟻傾向於朝著該物質強度高的方向移動。因此，由大量螞蟻組成的蟻群的集體行為便表現出一種信息正反饋現象：某一路徑上走過的螞蟻越多，則後者選擇該路徑的概率約大。螞蟻個體之間就是通過這種信息的交流達到搜索實物的目的。這裏，用一個形象化的圖示來說明螞蟻群體的路徑搜索原理和機製。

4.3.2 基於ACO的TSP求解

旅行商問題（Traveling Salesman Problem，簡稱TSP），也稱貨郎擔問題，是數學領域中的著名問題之一。TSP問題已經被證明是一個NP-hard問題，由於TSP問題代表一類組合優化問題，因此對其近似解的研究一直是算法設計的一個重要問題。該問題的求解算法主要分為兩類。一類是與問題特征相關的啟發式搜索算法。主要有動態規劃法、分支界定法等。另一類是獨立於問題的智能優化算法，如模擬退火法、禁忌搜索法、蟻群算法、遺傳算法、粒子群算法等。

蟻群算法利用了信息素進行傳遞信息，而粒子群優化算法利用了本身信息、個體極值信息和全局極值3個信息，來指導粒子下一步迭代位置。蟻群算法利用正反饋原理和某種啟發式算法的有機結合，容易出現早熟現象以及陷入局部最優解。混合的思路是讓螞蟻也具有“粒子”的特性，首先螞蟻按照蟻群算法，完成一次遍曆後，再讓螞蟻根據局部最優解和全局最優解進行調整。

調整思路如下：對於旅行商問題，其當前的位置是基本路徑，讓當前解與個體極值和全局極值分別作交叉操作，產生的解為新的位置，再做變異操作。

圖10 ACO優化下的TSP求解

MATLAB主程序代碼：

4.4 模擬退火算法（SA）

4.4.1 簡介

模擬退火算法的思想來源於對固體退火降溫過程的模擬。即將固體加溫至充分高，再讓其徐徐冷卻。在加熱固體時，固體中原子的熱運動不斷增強，內能增大，隨著溫度的不斷升高，固體的長程有序被徹底破壞，固體內部粒子隨溫度的升高而變為無序狀。冷卻時，粒子逐漸趨於有序，在每個溫度下都達到平衡狀態，最後在常溫下達到基態，同時內能也減為最小。

在實際應用中，將內能模擬為目標函數值 f，將溫度 T 模擬為控製參數，然後從一給定解開始，從其鄰域中隨機產生一個新解，接受準則允許目標函數在一定範圍內接受使目標函數惡化的解，算法持續進行“產生新解——計算目標函數差——判斷是否接受新解——接受或舍棄”的迭代過程，對應著固體在某一恒定溫度下趨於熱平衡的過程。經過大量的解變化後，可以求得給定控製參數 T 值的時候優化問題的相對最優解。然後減小控製參數 T 的值，重複執行上述迭代過程。當控製參數逐漸減小並趨於零時，係統也越來越趨於平衡狀態，最後係統狀態對應於優化問題的整體最優解。

4.4.2 基於模擬退火的粒子群算法

基於模擬退火的微粒群算法中的微粒群算法采用帶壓縮因子的PSO優化算法，Clerc和Kennedy提出的帶壓縮因子的PSO優化算法通過選取合適參數，可確保PSO算法的收斂性，並可取消對速度的邊界限製。速度和位置更新公式如下：

突跳概率：

MATLAB主程序代碼：

4.5 人群搜索算法（SOA）

4.5.1 簡介

人群搜索算法SOA（Seeker Optimization Algorithm）是對人的隨機搜索行為進行分析，借助腦科學、認知科學、心理學、人工智能、多Agents係統、群體智能等的研究成果，分析研究人作為高級Agent的利己行為、利他行為、自組織聚集行為、預動行為和不確定性推理行為，並對其建模用於計算搜索方向和步長。由於SOA直接模擬人的智能搜索行為，立足傳統的直接搜索算法，概念明確、清晰、易於理解，是進化算法研究領域的一種新型群體智能算法。SOA算法有以下幾種行為：利己行為、利他行為、預動行為、不確定推理行為等。

利己行為：智能群體是存在於自然界的社會群體，他們通過相互協作完成日常所需的各項任務，人類智能來自於社會交流，人類社會無疑也是一個智能群體。協作行為有兩種相互對立的形式：一種是利己行為，完全遵循自我優先原則；另一種是利他行為，遵循群體優先原則。作為智能群體中的一個獨立智能體，每個搜尋者都一樣地具有利己行為，相信自己的經驗，並通過認知學習傾向於向自己的曆史最佳位置移動。

利他行為：作為智能群體內的個體，每個搜尋者同樣具有利他行為。利他行為意味著智能群體內的個體相互合作，互通信息，分享群體的社會經驗，不斷調整各自的行為以達到一個共同的目標，這種達到共同目標的利他行為在空間的移動就表現為自組織聚集行為。聚集行為是自然界中從單細胞生物到社會性昆蟲和哺乳動物的一種基本自組織行為，它的正反饋通常表現為向一個給定的信號源匯集。

一般的優化問題往往是一個全局最小值事先並不知道的“黑箱”問題，這樣，鄰域曆史或當前最佳位置就成了該鄰域內所有搜尋者向其聚集的“信號源”。正因如此，每個搜尋者都具有群體優先的搜索策略，采取自組織聚集行為通過社會學習傾向於向鄰域曆史或當前最佳位置移動。

預動行為：智能體能夠展現目標導向的行為，主動地執行某種操作或者任務。此外，過去的行為及其由此產生的結果可以預測和指導未來行為。因此，搜尋者能夠根據自己過去的行為和環境的反饋，自適應地采取主動措施，實時地，靈活地改變搜索策略，展現目標導向的預動行為。

不確定性行為：不確定性，是人類社會現象的基本屬性。人類的認知過程是通過語言和思維進行的，人類依托語言進行思維；自然語言是人類的思維基礎，是人類智能的體現。模煳係統正是基於模擬人類利用自然語言來描述

複雜係統的需要提出的，模煳控製規則就是人類控製行為的語言模型；人類思維具有普遍模煳性的現象表明，模煳邏輯在描述人類思維方麵扮演了重要的角色。

4.5.2  基於SOA的PID整定

PID控製是典型的工業控製之一，對於PID控製，主要難點在於PID的參數整定，現用的工業控製中，PID參數整定多依賴於經驗法，根據不斷的調試，試得出一個較為合理的PID參數，達到係統的要求。隨著智能算法的出現，一些例如SOA、PSO、GA算法等，魯棒性較好，能夠為係統PID參數整定，提供參考依據，使得係統收斂於最佳狀態。

圖11  PID控製係統框

MATLAB主要程序代碼：

4.6 人工蜂群算法（ABC）

4.6.1 簡介

自然界中的群居昆蟲，它們雖然個體結構簡單，但是通過個體間的合作卻能夠表現出極其複雜的行為能力。受這些社會性昆蟲群體行為的啟發，研究者通過模擬這些群體的行為提出了群集智能算法。這些群集智能算法的出現，使得一些比較複雜且難於用經典優化算法進行處理的問題得到了有效的解決，同時這些算法已不斷地運用於解決實際問題，在很多領域得到了廣泛的應用，如調度問題，人工神經網絡，組合優化問題等工程領域。

人工蜂群算法（Artificial Bee Colony algorithm，ABC）是一種模擬蜜蜂采蜜行為的群集智能優化算法，它為解決存在於科學領域的全局優化問題提供了一種新的方法。由於它具有控製參數少、易於實現、計算簡單等優點，已經被越來越多的研究者所關注。

4.6.2 基於人工蜂群算法的函數優化分析

函數：

MATLAB主程序代碼：

4.7 萬有引力搜索算法（GSA）

4.7.1 簡介

萬有引力搜索算法（Gravitational Search Algorithm，GSA）是由伊朗克曼大學的Esmat Rashedi等人於2009年所提出的一種新的啟發式優化算法，其源於對物理學中的萬有引力進行模擬產生的群體智能優化算法。萬有引力搜索算法GSA的原理是通過將搜索粒子看作一組在空間運行的物體，物體間通過萬有引力相互作用吸引，物體的運行遵循動力學的規律。適度值較大的粒子其慣性質量越大，因此萬有引力會促使物體們朝著質量最大的物體移動，從而逐漸逼近求出優化問題的最優解。

萬有引力搜索算法GSA具有較強的全局搜索能力與收斂速度。隨著GSA理論研究的進展，其應用也越來越廣泛，逐漸引起國內外學者的關注。但是萬有引力搜索算法GSA與其他全局算法一樣，存在易陷入局部解，解精度不商等問題，有很多待改進之處。本章將著重向廣大編程愛好者介紹最基本的萬有引力算法，各編程科研人員可以基於本章算法加以改進並應用到實際案例中。

4.7.2 基於萬有引力算法函數優化

函數：

MATLAB主程序代碼：

4.8 細菌覓食算法（BFOA）

4.8.1 簡介

實際生活需求促進了最優化方法的發展。近半個多世紀以來，由於傳統優化方法的不足，一些具有全局優化性能且通用性強的進化算法，因其高效的優化性能、無需問題精確描述信息等優點，受到各領域廣泛的關注和應用。其中產生最早也最具代表性的進化算法是20世紀70年代源於達爾文自然選擇學說和孟德爾遺傳變異理論的遺傳算法（Genetic Algorithm，GA）。而近年來，人們模擬自然界生物群體行為產生出一係列群體智能優化算法，如Dorigo等通過模擬螞蟻的尋徑行為於1991年提出了蟻群優化算法（Ant Colony Optimization，ACO）；Eberhart和Kennedy通過模擬鳥群捕食行為於1995年提出了粒子群優化算法（Particle Swarm Optimization，PSO）。

這些算法被廣泛應用於工程領域並取得了顯著的成果。隨著群體智能優化算法的蓬勃發展，Passino於2002年提出了模擬人類大腸杆菌覓食行為的細菌覓食優化算法（Bacteria Foraging Optimization Algorithm，BFOA），為仿生進化算法家族增添了新成員。

4.8.2 基於細菌覓食算法函數優化

函數：

MATLAB主程序代碼：

4.9 匈牙利算法

4.9.1 簡介

1955年，庫恩（w·w·Kuhn）提出了匈牙利算法，它是一種關於指派問題的求解方法。匈牙利算法引用了匈牙利數學家康尼格（D.konig）的一個關於矩陣中獨立0元素個數的定理：矩陣中獨立0元素的個數等於能夠覆蓋所有0元素的最少直線數。

匈牙利算法的基本思想是修改效益矩陣的行或列，使得每一行或列中至少有一個為零的元素，經過修正後，直至在不同行、不同列中至少有一個零元素，從而得到與這些零元素相對應的一個完全分配方案。

當它用於效益矩陣時，這個完全分配方案就是一個最優分配，它使總的效益為最小。這種方法總是在有限步內收斂於一個最優解。該方法的理論基礎是：在效益矩陣的任何行或列中，加上或減去一個常數後不會改變最優分配。其求解步驟如下：

第一步，修正效益矩陣，使之變成每一行和每一列至少有一個零元素的縮減矩陣：

• 從效益矩陣的每一行元素減去各該行中最小元素；

• 再從所得縮減矩陣的每列減去各該列的最小元素。

第二步，試製一個完全分配方案，它對應於不同行不同列隻有一個零元素的縮減矩陣，以求得最優解：

• 如果得到分布在不同行不同列的N個零元素，那麼就完成了求最優解的過程。結束。

• 如果所分布於不同行不同列中的零元素不夠N個，則轉下步。

第三步，作出覆蓋所有零元素的最少數量的直線集合：

• 標記沒有完成分配的行。

• 標記已標記行上所有未分配零元素所對應的列。

• 對標記的列中，已完成分配的行進行標記。

• 重複（2）、（3）直到沒有可標記的零元素。

• 對未標記的行和已標記的列畫縱、橫線，這就得到能覆蓋所有零元素的最少數量的直線集合。

第四步，修改縮減矩陣，以達到每行每列至少有一個零元素的目的：

• 在沒有直線覆蓋的部分中找出最小元素。

• 對沒有畫直線的各元素都減去這個元素。

• 對畫了橫線和直線交叉處的各元素都加上這個最小元素。

• 對畫了一根直線或橫線的各元素保持不變。

• 轉第二步。

4.9.2 基於匈牙利算法的指派問題優化

指派問題的數學模型：

MATLAB主程序代碼：

4.10 魚群算法

4.10.1 簡介

有學者研究發現，有些魚群的形狀隨著其行為的改變而改變，魚群在緩慢遊泳時成兩端變細的形狀，在捕食獵物時，魚群形狀為圓形，魚群在防禦時，則魚群成密集的形狀或包圍捕食魚的形狀，在受到進一步威嚇時會潛入深處。

魚類的活動中，覓食行為、聚群行為、追尾行為和隨機行為與我們的待尋優函數問題有著較密切的關係，如何利用簡便有效的方式來構造並實現這些行為將是工魚群算法主要麵臨的問題。

覓食行為是一種魚群循著食物多的方向遊動的行為，在尋優過程中則是向較優方向前進。

在聚群行為中，為了保證生存和躲避危害，魚會自然地聚集成群。魚聚群時所遵守的規則有3條：

• 分隔規則，盡量避免與臨近夥伴過於擁擠；

• 對準規則，盡量與臨近夥伴的平均方向一致；

• 內聚規則，盡量朝臨近夥伴的中心移動。

追尾行為就是一種向臨近的最活躍者追逐的行為，在尋優算法中可以理解為是向附近的最優夥伴前進的過程。

4.10.2 魚群算法函數優化

MATLAB主程序代碼：

五、優化算法相關著作

[1]     張永禮, 董誌良, 安海崗. 神經網絡優化算法在技術經濟領域中的應用[M]. 冶金工業出版社, 2015.

[2]     李子輝. 基於智能優化算法的複雜車間調度問題研究[M]. 信息工程與自動化學院, 2015.

[3]     李愛國, 覃征. 粒子群優化算法[M]. 黑龍江人民出版社, 2015.

[4]     李士勇, 李研. 智能優化算法原理與應用[M]. 哈爾濱工業大學出版社, 2012.

[5]     張學良, 劉麗琴. 智能優化算法及其在機械工程中的應用[M]. 國防工業出版社, 2012.

[6]     王超學. 智能優化算法與應用[M]. 西北大學出版社, 2012.

[7]     雷秀娟. 群智能優化算法及其應用[M]. 科學出版社, 2012.

[8]     崔誌華. 微粒群優化算法[M]. 科學出版社, 2011.

原文發布時間為：2017-09-15 

本文作者：謝旺

本文來自雲棲社區合作夥伴“數據派THU”，了解相關信息可以關注“數據派THU”微信公眾號

最後更新：2017-10-10 15:03:56

  上一篇：  數據蔣堂 | 有序遍曆語法

  下一篇：  獨家 | 環境大數據的應用案例及前景