計算智能諸問題整理

2022.01.03

繼前天的數據分析問題整理之後, 昨天簡單覆習了計算智能的基礎概念, 由於相關題目和參考內容都是已經事先整理過, 發現遊覽過目的覆習效果似乎並不如自己整理一遍. 在這里也繼續透過對基礎概念相關的基本問題整理方式覆習計算智能部分內容, 也供其他有需要者查閱. 相關概念和內容僅涉及初級基礎概念, 僅供參考不建議作任何入門系統性學習, 如有疏漏或錯誤請以實際為準.

段落劃分

由於計算智能相關題目略多於數據分析, 在這里便不妨以章節為段劃分進行整理, 根據教材和講師的授課順序暫簡單劃分如下:

  • 緒論內容
  • 人工神經網絡
  • 遺傳算法
  • 蟻群算法
  • 人工免疫算法
  • 粒子群算法
  • 人工蜂群算法

緒論內容

首先, 計算智能是人工智能領域的一個重要研究方向, 是受到自然智慧和人類智慧的啟發設計而出的一類算法之統稱. 在計算智能中的優化算法則是已知所有解(即解空間)的情況下依據一定的判別規則(適應度函數或目標函數)並在某種搜索機制的引導下在解空間中尋找最優解的過程.

最優化問題的分類

根據最優化問題要素的不同特點, 我們可以從三個角度對最優化問題進行分類:

  • 目標數: 單優化問題和多優化問題(多優化問題又可以分為二維三維和高維多目標優化問題)
  • 設計變量是否連續: 連續變量優化問題和離散變量優化問題
  • 是否約束條件: 約束優化問題和無約束優化問題

傳統優化方法和計算智能方法

傳統優化方法通常計算簡單, 優化效率高, 可靠性也比較強. 但與此同時, 傳統優化方法也存在一定的局限性:

  • 單點計算限制計算效率: 傳統優化方法是從一個初始解出發, 每次叠代只對一個點進行計算;
  • 容易陷入局部最優不具備全局搜索能力: 傳統優化方法在每一次的叠代中, 要求能夠向目標函數值的方向進行移動, 這種思想不具備跳出局部的能力, 也就意味著一旦算法進入局部極值區域就很難跳出;
  • 算法應用範圍限制大: 由於傳統優化方法通常要求目標函數和約束條件是連續可導的, 凸的, 可行域是凸集, 而在實際應用中這些條件又難以滿足, 因此限制了算法的應用範圍.

相對於此, 盡管計算智能方法的算法理論工作相對比較薄弱, 並不能保證算法一定能夠收斂到最優解, 但其也具有另外一些特點和優勢:

  • 具有隱並行性, 協同優化和全局搜索能力強, 魯棒性高, 可以適用於大規模數據;
  • 計算智能方法不以達到某個最優條件或找到理論上的精確最優解為目標, 而是更看重計算的速度和效率;
  • 計算智能方法對於目標函數和約束條件函數的要求比較寬松, 不需要滿足可微可導性以及連續性和凸性等要求;
  • 計算智能方法的算法基本思想均來自於某些自然規律, 非常具有人工智能特點;
  • 算法是以包含多個進化個體的種群為基礎, 尋優的過程實際上就是種群的進化過程;

計算智能現狀與發展趨勢

首先, 計算智能方法的理論研究依然有待進一步發展完善. 目前大多數的計算智能方法都是透過大量的數值仿真實驗來驗證算法的性能, 缺乏傳統優化方法對收斂性的理論證明和數學解釋. 但與此同時, 計算智能方法在大規模變量和高維多目標問題上發揮著重要作用, 我們的實際應用系統設計中越來越多地出現大規模優化問題, 具有隱並行性和協同進化等優勢的計算智能方法是一個非常好的選擇. 而作為當前人工智能大熱門的深度學習其算法應用效果很大程度上取決於模型參數的訓練結果, 面對如此巨量的參數優化問題, 想要透過傳統的優化方法是非常困難的, 如果充分發揮計算智能方法較強的全局優化能力和算法高魯棒性的優勢, 計算智能方法勢必能夠與深度學習有機融合. 不僅與深度學習之類的領域概念是如此, 計算智能方法在自身不同算法之間優勢互補取長補短來提升算法性能也越來越受到重視, 想必構建混合計算智能方法將會稱為熱點. 當然, 大多數的實際系統工程設計和管理等問題最終都可以透過建模的方式轉換為最優化問題, 各種系統的優化設計已然是發展趨勢, 計算智能方法的實際應用領域也在不斷進一步拓展之中.

人工神經網絡

從基本概念上講, 人工神經網絡(ANN)是模擬人腦細胞提出的計算智能方法, 人工神經網絡通常劃分為有監督式學習和無監督式學習兩種, 其網絡結構又可以分為前饋型和反饋型. 實際上人工神經網絡的學習過程就是計算加權系數的過程, 用於解決非線性數學模型問題. 有實驗證明三層及三層以上的網絡結構可以逼近任意非線性函數. 作為人工神經網絡核心的反向傳播算法(BP), 其透過最小二乘法判定誤差, 並采用梯度下降法進行各層加權系數的調整.

需要指出的是, 激活函數也被稱為激勵函數, 作用函數或變換函數等, 一般為非線性函數. 它決定了神經元節點的輸出, 也因此它的 作用是從輸入到輸出的非線性變換.

前饋與反饋型神經元網絡

正如上文所述, 神經元網絡根據其網絡結構可以分為前饋型和反饋型. 其中, 前饋型神經元網絡取連續或離散變量, 通常不考慮輸出與輸入在時間上的滯後效應, 只去表達輸出與輸入的映射關系. 而反饋型神經元網絡則可以用離散變量也可以用連續取值, 考慮輸出與輸入之間在時間上的延遲, 需要動態方程來描述系統的模型. 此外, 前饋型網絡的學習通常采用誤差修正法, 如反向傳播算法等, 這也就意味著計算過程一般比較慢, 收斂速度也比較慢. 而反饋型網絡則主要采用 Hebb 學習規則, 一般而言其計算的收斂速度比較快. 盡管反饋型網絡也有類似前饋型網絡的應用, 但在優化計算方面則更能體現出反饋網絡的特點及優勢.

感知器的主要缺陷是什麽?

由於感知器的激活函數采用閾值函數, 因此輸出矢量只能取 0 或 1, 所以 只能用來解決簡單的分類問題. 並且感知器 僅能夠線性地將輸入矢量進行分類, 但理論證明也說明只要輸入矢量是線性可分的, 感知器在有限的時間內總能達到目標矢量. 另外, 感知器在當輸入矢量中有一個數比其他數都大或小很多時可能會導致比較慢的收斂速度.

需要注意的是, 感知器並不是只能解決線性分類問題, 只是比較適合解決線性分類問題, 它也能夠解決簡單的非線性分類問題.

反向傳播算法思想與缺陷

簡言之, 反向傳播算法的基本思想是: 學習過程由信號的正向傳播和誤差的反向傳播兩個過程構成. 這里的正向傳播即: 輸入樣本 - 輸入層 - 隱含層 - 輸出層. 而我們的輸出層實際輸出並不總是與期望輸出相符, 因此就需要轉入誤差的反向傳播過程: 輸出誤差 - 隱含層 - 輸入層. 這麽做的主要目的就是 透過將誤差反傳來分攤至各層所有單元, 從而獲得各層單元的誤差信號, 進而修正各單元的權值. 這個調整權重的過程就是網絡的學習和訓練過程. 盡管反向傳播算法在非常廣泛的領域得到應用, 但由於其訓練過程的不確定, 也是有其自身的缺陷和不足的:

  • 容易形成局部極小值而得不到全局最優;
  • 訓練次數多因此學習效率低收斂速度慢;
  • 隱節點的選取卻反一定的理論依據支持;
  • 訓練時學習新樣本有遺忘舊樣本的趨勢.

BP 網絡如何進行參數的設定?

這一問題可以從以下六個方面考慮:

  • 輸入輸出層的設計
  • 隱含層數的選擇
  • 隱含層單元數的選擇
  • 初始權值的選取
  • 學習速率的調整
  • 激勵函數的選取

BP 網絡和 RBF 網絡的不同

  • RBF 網絡只有一個隱含層, 而 BP 網絡的隱含層可以是多層;
  • BP 網絡的隱含層和輸出層其神經元模型是一樣的, 而 RBF 網絡的隱含層神經元和輸出層神經元不僅模型不同, 而且在網絡中起到的作用也是不一樣的;
  • RBF 網絡的隱含層是非線性的, 輸出層是線性的. 而當用 BP 網絡解決模式分類問題時, 它的隱含層和輸出層通常選為非線性的, 當用 BP 網絡解決非線性回歸問題時則通常選擇線性輸出層;
  • RBF 網絡的基函數計算的是輸入向量和重心的歐氏距離, 而 BP 網絡隱含層單元的激勵函數計算的是輸入單元和連接權值之間的內積;
  • RBF 網絡使用局部指數衰減的非線性函數(如高斯函數)對非線性輸入輸出映射進行局部逼近, 而 BP 網絡的隱含層節點采用輸入模式與權向量的內積作為激活函數的自變量, 激活函數則采用 Sigmoid 函數或硬限幅函數, 因此 BP 網絡對非線性映射的全局逼近.

遺傳算法

遺傳算法(GA)透過模擬自然界中生物進化的過程 提出, 可以解決全局優化問題. 其主要步驟是: 編碼 - 計算適應度函數 - 遺傳算子. 遺傳算法的三個算子分別是選擇, 交叉和變異.

在這里也對生物遺傳進化的相關基本觀點作羅列:

  • 生物的所有遺傳信息都包含在其染色體中, 染色體決定了生物的性狀;
  • 染色體是由基因及其有規律地排列所構成的, 遺傳和進化過程發生在染色體上;
  • 生物的繁殖過程是由其基因的覆制過程來完成的;
  • 透過同源染色體之間的交叉或染色體的變異會產生新的物種, 使生物呈現新的性狀;
  • 對環境適應性好的基因或染色體常比適應性差的基因或染色體有更多機會遺傳給下一代.

遺傳算子

遺傳算子是模擬生物進化過程最關鍵的進化機制, 包括選擇算子, 交叉算子和變異算子, 它們是遺傳算法的核心和基本算子.

  • 選擇算子: 選擇是為了從當前種群中選出優良的個體, 使其有機會作為父代來繁殖子代. 進化過程中是根據各個個體的適應度值來按照一定的規則和方法從上一代種群中選擇出一些優良的個體遺傳到下一個種群中, 遺傳算法正式透過選擇算子的操作來體現這一思想, 而進行選擇的原則是適應度高的個體為下一代貢獻一個或多個子代的概率大, 這是生物能夠保持性狀而達到物種穩定的最主要原因;
  • 交叉算子: 交叉算子也被稱為交換算子, 它同時對兩個染色體的部分基因進行交換, 是遺傳算法中最主要的遺傳操作. 其作用是不斷產生新的染色體, 避免算法陷入局部最優;
  • 變異算子: 遺傳算法在選擇算子和交叉算子的作用下已經能夠起到種群進化的作用, 但在這個過程中, 算法並不能夠保證一些重要的遺傳信息不丟失. 因此, 僅僅依靠前兩種遺傳操作, 算法缺乏搜索整個解空間的能力, 並且正如前文所述獲得的解有可能是局部最優解. 在生物的遺傳和進化過程中, 生物的某些基因偶爾會發生變異從而產出新的個體, 雖然概率較小但對於新物種的產生仍然是不可忽視的因素. 為了模仿生物遺傳和進化過程中的這種變異現象, 在遺傳算法中引入了變異算子來產生新的個體, 從而在叠代過程中擴展算法的搜索空間, 使得算法有能力整個解空間中進行魯棒搜索而不陷入局部最優.

交叉率

交叉率顧名思義就是交叉概率, 其控制著交叉算子的應用概率. 較大的交叉概率可以使得各代充分交叉從而產生更多的新解, 使得算法的搜索能力更強. 與此同時, 種群中的優良模式遭到破壞的可能性也會更大, 以致產生較大的鴻溝使搜索走向隨機化; 但如果交叉概率太低, 又會使得更多的個體直接覆制到下一代, 使搜索結果陷入停滯. 因此, 交叉率一般取值 0.5 - 0.85 之間.

變異率

變異率顧名思義就是變異的概率. 當變異率取較大值時我們就能夠產生較多的個體, 從而增加種群的多樣性, 但也有可能破壞掉很多好的模式, 使得遺傳算法的性能近似於隨機搜索; 但若變異率取較小值雖然提高了種群的穩定性, 但一旦陷入局部極值就很難跳出, 容易產生早熟收斂.

在變異操作中, 有著 以高變異率開始進化, 隨著代數增加遞減變異率 的策略, 這種策略是有其積極意義的. 在進化初期我們需要保持較高的變異率, 從而對解空間進行較為充分的探索, 維護種群多樣性避免陷入局部最優; 而在進化的中後期我們對解空間的探索已經較為充分, 這就需要加強對最優解附近的開發力度, 來保證算法的收斂性.

染色體交叉

再利用遺傳算法解決一些實際問題特別是 TSP 問題時, 常常需要采用基於位置的交叉方式對於染色體進行交叉, 具體的交叉過程以兩組數據為例, 詳見圖示:

最優解不同問題

在遺傳算法中, 所有參數都相同的情況下, 算法每次得到的最優解是會有所不同的. 這是因為遺傳算法每次都是隨機產生初始種群, 正是由於初始種群不同, 即便所有的各個參數都相同, 每次叠代的結果都會有所不同, 因此得到的最優解也有所不同. 但需要注意的是, 算法每次得到的最優解即便有所不同但通常都會相差不多, 都是目標的近似解.

蟻群算法

蟻群算法(ACO)模擬了自然界中螞蟻覓食的過程而提出, 用以解決組合優化問題. 蟻群算法需要一個記憶空間, 我們稱之為禁忌列表, 表示已經過的路徑. 判斷選擇城市的主要依據有能見度和虛擬信息素. 能見度代表啟發式願望, 而虛擬信息素則代表獲知式願望, 反映了問題求解過程中經驗的積累.

遺忘因子

參數 ρ 表示信息素揮發因子, 也就是遺忘因子, 遺忘因子的大小反映螞蟻群體中個體之間相互影響的強弱, 這也就意味著它直接關系到蟻群算法的全局搜索能力及其收斂速度. 當我們的遺忘因子較小, 就會導致殘留信息素增多, 進而信息的正反饋作用增強, 也就使得算法搜索的隨機性減弱, 雖然收斂速度加快了, 但搜索的質量卻下降了; 當我們的遺忘因子較大時, 又會導致殘留信息素減少, 進而信息的負反饋作用增強, 使得算法搜索的隨機性隨之增強, 此時雖然有利於搜索到更多潛在的最優解並提高算法的搜索質量, 但會導致算法的收斂速度降低. 1-ρ 通常代表信息殘留因子, 一般取值在 0.1 - 0.99 範圍內.

禁忌列表

在 TSP 問題中, 我們要求螞蟻必須經過所有不同的城市, 為了避免螞蟻重覆走入同一個城市, 我們就要為每只螞蟻配備一個記憶空間, 即在具體的算法實現中設計一個數據結構, 由這些數據結構組成的表(矩陣)被稱為禁忌列表.

蟻群算法解決 TSP 問題的步驟

  • 初始化, 首先設定相關參數: 如遍歷城市數 n 以及螞蟻數 m 等, 並保證禁忌列表中沒有城市;
  • 將 m 只螞蟻隨機放在各個城市, 每個城市最多分布一只螞蟻並將 m 個螞蟻所在城市存入禁忌列表;
  • 所有螞蟻根據概率轉換規則選擇下一個城市並將其選擇城市存入禁忌列表;
  • 所有螞蟻遍歷完 n 個城市後再經過的路徑上更新信息素並記錄本次叠代過程中的最優路徑及其長度;
  • 清空禁忌列表, 重覆前兩步直到每一只螞蟻完成 Nmax 次便利所有城市, 最後輸出最優路徑.

α 和 β 參數

α 參數表示殘留信息的相對重要程度, 其大小反映了螞蟻在路徑搜索過程中隨機性因素作用的強弱; β 參數則表示能見度的相對重要程度, 其大小反映了在路徑搜索過程中確定性因素作用的強弱. 參數 α 越小, 信息素積累的作用越小, 螞蟻越偏向於隨即搜索; 參數 β 越大, 能見度的確定性越大, 蟻群算法的隨機性也就越弱.

蟻群算法其特點

  • 自組織: 自組織就是在沒有外界作用下使得系統熵減小的過程, 也就是系統從無序到有序的變化過程, 蟻群算法就充分體現了這個過程;
  • 分布式: 每只螞蟻的搜索過程彼此獨立, 僅通過信息素進行通信, 不僅提高了算法的效率和可靠性, 還使得算法具有較強的全局搜索能力, 且使算法易於並行實現;
  • 有正反饋機制: 蟻群算法中的正反饋機制就是較優路徑上留下更多的信息素, 這個過程引導系統向最優解的方向進化, 加快了算法的進化過程, 最終使得算法收斂到最優解;
  • 較強的魯棒性: 相比於其他算法, 蟻群算法對於初始路線要求不高, 其求解結果也不依賴於初始線路的選擇, 並且在搜索過程中不需要進行人工幹預. 此外, 蟻群算法參數少, 設置簡單, 非常易於應用到其他的組合優化問題的求解當中.

人工免疫算法

人工免疫算法(AIA)是基於免疫學理論和生物免疫系統機制而提出的計算智能算法, 是對生物免疫機理的一種模擬, 判別優劣的適應度函數這里稱為親和度. 利用生物免疫系統的某一個方面原理就可以設計新算法, 因此人工免疫算法實際上是多個算法的統稱, 其中比較有代表性的有否定選擇算法, 免疫規劃算法, 克隆選擇算法. 其具有以下特點:

  • 具有全局搜索能力;
  • 具有多樣性保持機制;
  • 魯棒性強;
  • 具有並行分布搜索機制.

克隆選擇算法的基本流程

  • 初始化: 隨機產生 N 個抗體對應問題的可能解, 作為初始種群;
  • 克隆選擇: 第一次評價和選擇, 計算種群抗體的親和度函數;
  • 克隆操作: 在記憶記憶集中選擇親和度最高的那些抗體中進行克隆, 克隆的數量與其親和度成正比;
  • 重組變異: 模擬生物克隆選擇中的重組變異過程, 對克隆後的抗體執行重組變異操作, 對變異和重組分別按照某一概率以一定規模隨機進行;
  • 克隆選擇: 第二次評價和選擇, 重新計算重組變異操作後的抗體親和度, 若操作後的抗體中親和度最高的抗體比原抗體的親和度還有高, 就用該抗體替換原抗體, 形成新的記憶集;
  • 刪除和補充: 模擬生物克隆選擇中 5% 的 B 細胞自然消亡的過程, 在選擇親和度最低的抗體進行刪除操作的同時按照抗體補充算子產生新抗體加入種群, 以保證抗體多樣性;
  • 檢查終止條件: 檢查是否滿足終止條件, 若是則終止, 否則進入步驟二繼續叠代.

遺傳算法與 AIS 算法

遺傳算法和 AIS 算法都能夠適用於數值函數的優化, 兩者也都屬於啟發式叠代搜索算法. 相比之下其二者具有以下五個不同之處:

  • AIS 算法搜索多峰值函數的多個極值效果較好, 而遺傳算法搜索全局最優解效果較好;
  • AIS 算法起源於宿主和宿原之間的內部競爭, 其相互作用的環境包括外部環境也包括內部環境, 而遺傳算法則起源於個體和自身基因之間的外部環境競爭, 即適者生存.
  • AIS 算法中基因由個體選擇, 而遺傳算法中基因由環境選擇;
  • AIS 算法一般較少使用交叉算子, 基因在同一代個體中進化, 而遺傳算法的子代個體則是父代個體基因交叉組合的結果;
  • 遺傳算法中沒有記憶庫的概念, 記憶庫的概念是受免疫系統具有免疫記憶特性的啟示將問題最後的解及問題的特征參數存入記憶庫, 以便在下次遇到同類問題時可以直接借用這次的結論從而加快問題的求解速度, 提高算法的效率.

粒子群優化算法

粒子群算法(PSO)模擬了自然界中鳥群覓食的過程而提出. 在粒子群算法中, 最關鍵的兩個變量分別是位置和速度. 粒子群算法每次疊代後都會得到一個個體的局部最優解和群體的局部最優解. 同時, 學習因子 C1 和 C2 分別為 認知部分 代表向自身學習, 社會部分 代表向群體學習.

粒子群算法流程

  • 對實際問題的解進行編碼;
  • 根據實際問題構造評價問題可能解優劣的適應度函數;
  • 對粒子群進行初始化, 確定初始種群的大小以及終止條件等參數;
  • 確定初始種群的個體解方向和全局解方向;
  • 計算每個粒子的適應度, 確定個體最優解和全局最優解;
  • 判斷是否滿足終止條件, 若滿足則終止否則進行第五步.

人工蜂群算法

人工蜂群算法(ABC)模擬了蜜蜂采蜜的機制, 用於解決優化問題. 在人工蜂群算法中, 有三種蜜蜂執行不同的任務, 分別是引領蜂, 跟隨蜂和偵察蜂.

人工蜂群算法的基本流程

  • 初始化相關參數, 包括種群個數 NP, limit 和最大叠代次數 G 等;
  • 在設計變量可行空間內隨機產生初始種群, 設置進化代數 t=0;
  • 計算種群中各個個體的適應度值;
  • 由適應度較優的一半個體構成引領蜂種群, 另一半個體為跟隨蜂種群;
  • 引領蜂種群中個體搜索產生新個體, 擇優保留形成新的引領蜂種群;
  • 跟隨蜂種群按照輪盤賭選擇方式在上一步驟的種群中選擇較優個體, 搜索產生新個體, 形成跟隨蜂種群;
  • 結合前兩步, 個體構成叠代種群;
  • 判斷是否發生偵察蜂行為, 若某個個體連續 limit 代不變, 則發生偵察蜂行為並更新叠代種群;
  • 判斷是否滿足算法的終止條件, 若滿足則輸出最優解, 否則回到步驟三.

需要注意的是, 引領蜂搜索中產生新個體後, 需要比較該新個體和目標個體的適應度擇優進入引領蜂種群. 但在跟隨蜂搜索時, 跟隨蜂種群直接根據個體交叉搜索生成, 並不與原跟隨蜂種群進行一對一適應度比較.

高維覆雜單目標優化問題

人工蜂群算法在求解高維覆雜單目標函數優化問題時會遇到容易陷入局部最優, 早熟收斂, 後期收斂速度慢等問題, 導致其在大規模和高度非線性的實際工程應用中可行性較差. 為了提高人工蜂群算法在求解高維覆雜單目標函數優化問題上的收斂精度和收斂速度, 可以進行一定程度上的改進:

  • 改進跟隨蜂選擇蜜源的概率模型: 在人工蜂群算法中, 跟隨蜂依據輪盤賭的方式選擇蜜源, 這種 基於貪婪策略的選擇方式會使種群多樣性降低, 從而導致過早收斂和提前停滯. 因此我們不妨將靈敏度與信息素配合, 代替輪盤賭的方式選擇較優的蜜源. 理論上可以選擇任何區域進行搜索, 這就在很大程度上避免了陷入局部最優, 所搜索區域的信息素必須適應其靈敏度, 這就使算法有導向作用, 決定了目標函數在搜索空間中的收斂和發散.
  • 最差蜜源的替換: 在人工蜂群算法中, 引領蜂和跟隨蜂都可能會以來本次叠代中的最差蜜源進行交叉操作產生新的蜜源, 但 最差蜜源幾乎不可能對最終結果做出積極貢獻, 而且在一定程度上會降低算法的收斂速度. 對此我們不妨考慮產生一個新蜜源替換最差蜜源, 由於依靠產生候選解的相對點取代候選解的反向學習策略是對原候選解的一種較好估計, 與產生隨機點代替原候選解的方式相比, 往往會取得更佳的優化效果, 不僅極大地提高了收斂速度, 而且在一定程度上避免了陷入局部最優. 因此, 采用現有的一種應用效果較好的改進反向學習策略產生新蜜源取代最差蜜源.

小結

這里主要基於一些基礎概念對計算智能的幾個基本算法做了概要和問題說明, 由於內容較應試, 並且非常基礎, 大多都是概念問題, 因此還是建議僅供參考, 如有錯漏以實際為準. 對於計算智能相關領域還是建議在有指導的情況下透過一些可靠的教材來學習, 本文僅供參考, 並不用作任何入門指引或權威定義, 特此說明.