智能優化算法解析第5章

基于人類行為的智能優化算法5.1人工神經網絡算法5.2禁忌搜索算法5.3頭腦風暴優化算法主要內容CONTENTS3基于人類行為的智能優化算法在人工智能和信息科學領域，對人類行為的借鑒與模擬已成為推動智能優化方法發展的重要動力。導讀人工神經網絡算法：模擬大腦神經元的交互、學習與記憶過程禁忌搜索算法：避免重復錯誤，基于“試錯”行為搜索全局最優解頭腦風暴優化算法：模擬集體討論，激發創新解決方案5.1人工神經網絡算法55.1.1

算法原理人工神經網絡的基本概念人工神經網絡(簡稱神經網絡)是由一些簡單處理單元構成的大規模分布式處理器，具有存儲和復用經驗知識的特性，是對人腦神經網絡的某種簡化、抽象和模擬。神經網絡與人腦的相似性：通過學習過程從外界環境中獲取知識利用互連神經元的連接強度(突觸權值)存儲獲取的知識神經網絡的主要目標是設計一個學習算法，通過調整網絡中突觸權值，實現既定任務。65.1.1

算法原理神經網絡的優勢及發展神經網絡算法的主要優勢：擁有能夠存儲信息的大規模并行分布式結構具有學習能力和泛化能力(對不曾學習過的數據進行預測并得到合理輸出)這些優勢讓神經網絡具有學習更新并獲得復雜問題近似解的能力。75.1.1

算法原理神經網絡的優勢及發展歷史發展：1943年：McCulloch和Pitts提出了神經元的數學模型，開創了神經科學理論研究的時代1957年：Rosenblatt提出了感知機模型，模擬動物和人腦的感知和學習能力1982年：Hopfield提出了具有聯想記憶功能的Hopfield神經網絡，引入了能量函數，給出了網絡的穩定性判據。85.1.1

算法原理人工神經元人腦神經元由細胞體、軸突、突觸和樹突組成信息傳遞通過電信號和神經遞質完成人工神經元結構模擬人腦神經元輸入信號、權值、觸發閾值、總輸入、激活函數、輸出根據人腦神經細胞的基本結構，人工神經網絡由人工神經元、對應的連接權值和實現信號轉換的激活函數組成。95.1.1

算法原理激活函數激活函數限制神經元輸出的振幅模擬人腦神經元的線性或非線性特性構建神經網絡的重要環節激活函數的選擇激活函數的選擇對神經網絡的性能有重要影響不同任務和網絡結構可能需要不同的激活函數多層感知機具有一個或多個隱含層的神經網絡每層的輸入是上一層的輸出105.1.1

算法原理感知機模型單層感知機前饋神經網絡的一種簡單形式僅由輸入層和一個神經元層構成人工神經網絡是將神經元模型以某種方式組合起來的網絡結構，通過學習的方式來模擬人腦的某些功能，用以解決不同的實際問題。115.1.2反向傳播神經網絡算法反向傳播神經網絡算法神經網絡設計結構設計：選擇適合的神經網絡結構，如多層感知機參數學習：確定網絡權值和閾值重點解決問題：通過調整權值使網絡輸出盡可能接近預期值BP(BackPropagation，簡稱BP)算法：Rumelhart于1985年提出，解決了多層感知機中隱含層神經元連接權值的學習問題，廣泛用于函數擬合、信息處理、模式識別和智能控制。125.1.2反向傳播神經網絡算法BP神經網絡參數學習方法訓練多層感知機的一個經典方法是BP算法，其訓練過程主要分為兩個階段前向階段：輸入信號在網絡中逐層傳播信號流動直到抵達輸出端網絡中的權值在此階段保持不變反向階段：比較網絡輸出與預期輸出，生成誤差信號誤差信號從輸出端向輸入端逐層反向傳播調整網絡權值以減小誤差135.1.2反向傳播神經網絡算法BP神經網絡參數學習方法選擇具有一個隱含層的多層感知機為例，說明BP算法權值學習過程。首先，將神經網絡的輸入層變量表示為輸出層的變量表示為隱含層的權值矩陣可表示為145.1.2反向傳播神經網絡算法BP神經網絡參數學習方法若選取所有神經元激活函數均為f(.)，且觸發閾值為零，則隱含層第l個神經元的輸出可表示為輸出層的權值矩陣可表示為神經網絡輸出層第j個神經元的輸出表示為155.1.2反向傳播神經網絡算法BP神經網絡參數學習方法對于給定的預期輸出

，根據神經網絡的實際輸出可定義第

j個神經元誤差信號進一步地，總誤差信號為神經網絡的學習過程是通過修改各層神經元的連接權值，使得誤差信號e趨向最小。165.1.2反向傳播神經網絡算法BP神經網絡參數學習方法在BP算法中，采用誤差信號反向傳播，故先考慮輸出層的權值調整。根據梯度下降方法，取誤差函數的負梯度方向作為權值的調整方向，即對于輸出層權值系數，可按照如下方向調整輸出層權值系數迭代公式為按照上式經過多次調整，直至尋找到滿意的權值。175.1.2反向傳播神經網絡算法BP神經網絡參數學習方法當神經元位于隱含層時，沒有與該神經元層直接對應的預期輸出。因此，隱含層神經元的誤差信號要根據與隱含層相連的神經元向后反傳決定。對于隱含層的權值系數需按照如下方向調整由于隱含層第u個神經元與輸出層的神經元都有連接，因此綜上，隱含層權值系數的迭代公式為對于具有多個隱含層的BP網絡，其他的隱含層權值調整可通過類似方法給出。185.1.2反向傳播神經網絡算法BP神經網絡參數學習流程前向傳播輸入信號逐層傳遞至輸出端，計算每層神經元的輸出誤差計算比較網絡輸出與預期輸出，計算誤差信號反向傳播誤差信號從輸出層反向傳播，逐層調整權值以減小誤差取誤差函數的負梯度方向作為權值的調整方向，逐步逼近最優解195.1.2反向傳播神經網絡算法BP神經網絡的不足及改進收斂緩慢及改進原因：學習率設置不當、網絡結構簡單、數據質量差改進：調整學習率、優化結構、數據預處理局部最優問題及改進原因：誤差曲面復雜，多個局部最優點改進：多組初始值訓練、采用隨機梯度下降泛化性能差及改進原因：過擬合、數據質量問題改進：增加數據量、數據預處理、優化超參數選擇205.1.3徑向基函數神經網絡算法網絡概述定義與結構：徑向基函數(RadialBasisFunction,RBF)神經網絡是一種基于核函數的神經網絡算法。組成：輸入層：連接外部輸入隱含層：利用非線性激活函數對輸入空間進行非線性變換輸出層：進行線性變換，提供網絡的輸出響應特點：隱含層通常為一層，區別于多層感知機模型應用領域：非線性函數逼近時間序列分析系統建模控制和故障診斷215.1.3徑向基函數神經網絡算法參數學習方法RBF是一種沿著徑向對稱的標量函數。定義RBF為徑向基函數中心徑向基函數半徑輸入信號利用RBF作為激活函數，構建隱含層具有個

神經元和

m個輸出節點的RBF神經網絡。為了簡單說明，本節輸入層到隱含層的權值系數均取1，則第

j個神經元的輸出可表示為輸出層的權值矩陣可表示為225.1.3徑向基函數神經網絡算法參數學習方法RBF神經網絡輸出層采用線性累加，網絡的第l個輸出可表示為RBF神經網絡需要學習的參數：徑向基函數的中心，半徑，以及輸出層權值W。學習過程：無監督自學習：確定樣本中心和半徑方法：K-means法、自組織選取法有監督學習：計算輸出層權值方法：最小二乘法235.1.4典型問題求解案例例題例題5-1利用BP和RBF神經網絡分別擬合如下非線性函數這里選取63個樣本，輸入變量為，預期的輸出由如下命令生成：245.1.4典型問題求解案例求解過程其中，y_gd為BP神經網絡的輸出，netgd為訓練后的BP神經網絡。(1)利用Matlab工具箱，實現BP神經網絡擬合非線性函數255.1.4典型問題求解案例求解過程其中，y_rbf為RBF神經網絡的輸出，netrbf為訓練后的RBF神經網絡。(2)利用Matlab工具箱，實現RBF神經網絡擬合非線性函數(3)通過繪制兩個神經網絡的學習曲線，觀察擬合結果265.1.4典型問題求解案例求解過程RBF神經網絡和BP神經網絡輸出結果275.1.5前沿進展進展概述人工神經網絡領域迎來黃金時代，深度學習框架的飛躍性突破，引領復雜任務處理邁向高效精準新紀元構建復雜網絡結構，融合先進優化算法，訓練高性能神經網絡從AlphaGo到ChatGPT，見證神經網絡領域的飛速發展285.1.5前沿進展案例分析：長短期記憶網絡長短期記憶(Longshort-termmemory,LSTM)網絡是一種特殊的遞歸神經網絡，通過其特有的門控機制，能夠有效地捕獲和存儲序列中的依賴關系。遺忘門：基于歷史信息，篩選舊狀態，控制信息保留與遺忘輸入門：綜合多種輸入，通過非線性映射，精準選擇信息更新輸出門：調控記憶信息輸出比例，平衡新舊信息貢獻，優化長序列處理295.1.5前沿進展LSTM前沿LSTM神經網絡具有強大的自學習能力、魯棒性和容錯性、并行處理能力、逼近非線性關系的能力，使其能靈活應對多種實際問題，展現出卓越的應用性能。在自然語言處理任務中，捕捉上下文信息、對語言序列的理解能力增強在長時間依賴的復雜模型中，模型的收斂速度和穩定性顯著提高在視頻分析、動作識別、天氣預測等涉及時空序列問題的領域中，對時空信息的捕捉能力有所提升5.2禁忌搜索算法315.2.1典型搜索算法概述禁忌搜索算法禁忌搜索(TabuSearch,TS)算法基本思想：模擬人類的智力過程，避免重復錯誤可行解向目標函數變化最多的方向移動，通過靈活的“記憶”技術更新目標是找到使適應度函數值最優的解禁忌搜索算法在組合優化等領域取得了顯著進展，并應用到調度和規劃等問題中局部鄰域搜索算法(非梯度法)算法選定一個可行解，并產生鄰域解，逐一比較其目標函數值，不斷選擇最優解進行更新325.2.1典型搜索算法概述典型搜索算法梯度下降法從當前解出發，沿著目標函數變化最大方向前進，直到達到局部最優解梯度下降算法易陷入局部最優，且不適用于梯度信息未知的目標函數局部鄰域搜索算法搜索性能依賴于初始解和鄰域結構。若初始解不合適或鄰域結構設置不當，依然可能導致陷入局部最優335.2.1典型搜索算法概述禁忌搜索算法原理禁忌搜索算法由于引入接受劣質解的機制，禁忌算法能夠向其他方向尋優，實現目標函數值先降后升，最終搜索到全局最優局部鄰域搜索算法算法在鄰域尋優使目標函數最終走向x(1)，導致求解陷入局部最優，且無法跳出，無法到全局最優禁忌搜索算法核心思想通過設立禁忌表來避免算法陷入局部最優解利用記憶功能在搜索過程中接受劣解以擴大搜索范圍通過特赦準則避免錯過優質解通過不斷迭代和優化搜索策略，禁忌搜索算法結合了局部鄰域搜索和全局優化的思想345.2.2基本概念禁忌搜索基本概念禁忌搜索算法是一種迭代啟發式搜索算法，靠“記憶”引導算法的搜索過程，其中很多構成要素極大地影響搜索的速度與效果。禁忌對象和禁忌長度禁忌對象是指禁忌表中被禁止的某些變化元素。禁忌長度是禁忌對象不能被選取的周期。鄰域移動鄰域移動是解更新的關鍵，本質是一個函數，根據當前解的移動產生其相應的鄰居解集合，進而產生合適的候選解集合。目標函數目標函數用于評價鄰域中的鄰居，是判斷解優劣的衡量指標。禁忌表禁忌表用于記錄被禁止的變化元素，以防出現搜索循環、陷入局部最優。35禁忌搜索基本概念禁忌搜索算法是一種迭代啟發式搜索算法，靠“記憶”引導算法的搜索過程，其中很多構成要素極大地影響搜索的速度與效果。解的初始化禁忌搜索算法可以隨機給出初始解，也可以使用其它啟發式算法給出一個較好的初始解。但針對復雜約束的優化問題，如果隨機選取初始解，可能經過多次搜索也無法確定一個可行解。特赦準則在禁忌搜索算法中，可能會出現候選解全部被禁忌，或者存在一個優于當前最優目標值的禁忌候選解，此時特赦準則將某些可行解進行解禁，以實現更高效的優化。終止規則禁忌搜索算法中常用的終止規則有：最大迭代次數原則、禁忌頻率控制原則、目標值變化控制原則。5.2.2基本概念36禁忌搜索算法流程禁忌對象、最大迭代數領域解不優于當前最優解達到最大迭代數領域解優于當前最優解5.2.3算法流程37禁忌搜索算法不足及改進算法對初始解有較強依賴性好的初始解可使禁忌搜索算法在解空間中搜索到優質的解，而較差的初始解則會降低禁忌搜索的收斂速度改進：可以與遺傳算法、模擬退火算法等優化算法形成組合算法迭代搜索過程是串行的僅是單個解層面的移動，而非并行搜索改進：可以針對算法的初始化、參數設置等方面實施并行策略，向群體智能方向改善禁忌搜索5.2.3算法流程38例題例題5-2利用禁忌搜索算法，求解如下目標函數的最大值，其中且圖中藍色標記為當前解的搜索過程，紅色標記為迭代過程最優解目標函數圖像解空間搜索過程5.2.4典型問題求解案例39例題優化后最終結果為和，函數的最大值為3.9000，得到全局最優。當前解迭代變化曲線當前最優解迭代變化曲線由圖可知，禁忌搜索的過程中當前解可接受劣解，存在暫時降低目標函數的情況，以增強算法搜索能力，保證當前最優解不斷優化。5.2.4典型問題求解案例40求解過程(1)初始化各個參數和各類解變量，并置空禁忌表5.2.4典型問題求解案例41求解過程5.2.4典型問題求解案例(2)定義算法主循環中核心功能函數。定義生成函數，用于產生鄰域解作為候選解42求解過程5.2.4典型問題求解案例定義目標函數定義更新函數，用于更新禁忌表定義判斷函數，用于判斷候選解是否在禁忌表中43求解過程5.2.4典型問題求解案例(3)實施禁忌搜索算法程序主循環，包含產生鄰域解和候選解，對其判斷藐視準則，以進行當前解和當前最優解的更新44求解過程5.2.4典型問題求解案例(4)繪制算法運行圖形455.2.5前沿進展案例分析：禁忌搜索算法優化BP神經網絡BP神經網絡存在收斂速度慢和易陷入局部最優的問題，導致網絡參數優化困難。因此，可以通過結合禁忌算法的全局優化能力，實現BP神經網絡參數的全局優化。初始化BP神經網絡初始化禁忌算法進行網絡訓練禁忌算法尋優，通過藐視準則和禁忌表，更新當前解和當前最優解判斷停止準則5.3頭腦風暴優化算法475.3.1

頭腦風暴法概述頭腦風暴優化算法的起源受人類開會過程集思廣益的啟發，2011年史玉回教授在第二屆AdvancesinSwarmIntelligence國際會議中提出了一種新的頭腦風暴優化(BrainStormOptimization,BSO)算法。該算法采用聚類思想搜索局部最優，再通過比較局部最優得到全局最優。首次發表在TheSecondInternationalConferenceonSwarmIntelligence485.3.1

頭腦風暴法概述頭腦風暴法的基本概念頭腦風暴法是一種激發人類思維，以尋找問題最優解的方法。頭腦風暴法的核心是，讓參會人員圍繞中心話題暢所欲言，通過思想碰撞、觀念融合，得到問題的最優解。頭腦風暴法所蘊含的開放性和協作精神為BSO算法的設計提供了寶貴的啟示，有助于在算法研究中實現高效的優化和創新495.3.1頭腦風暴法概述頭腦風暴法的組成從明確問題到會后評價，頭腦風暴法一般分為三個階段。第一階段為明確闡述問題，主持人介紹問題。如果專家對問題感到困惑，主持人應該利用案例形式對問題進行分析。第二階段為主持人記錄專家提出的所有見解，并積極鼓勵專家自由提出見解。第三階段為專家以鑒別眼光討論所有列出的見解，也可以讓另一組專家來進行評價。頭腦風暴法遵循的四個原則：庭外判決原則(延遲評判原則)，對各種意見的評判必須放到最后階段自由暢想原則，鼓勵各抒己見，創造一種自由、活躍的氣氛以量求質，意見越多，產生好意見的可能性越大綜合改善原則，強調相互啟發、相互補充和相互完善505.3.2

算法原理頭腦風暴優化算法的主要構成BSO算法中的每一個體都代表一個問題的解，利用個體的演化和融合進行更新，通過反復迭代求得問題的最優值。BSO算法主要由聚類和變異兩部分組成，利用聚與散相輔相承的搜索機制來搜索最優解。聚類BSO算法采用K-means聚類機制，將相同領域或者相似領域的成員分為一組。所有個體可以聚集成幾個集群，每個集群的中心可以是該集群中目標函數最優的個體，也可以是距離空間的中間個體515.3.2

算法原理頭腦風暴優化算法的主要構成K-means聚類K-means聚類是一種經典的無監督聚類算法，用于將數據集劃分為K類。該算法的目標是使得數據點與其所屬聚類中心之間距離的平方和達到最小。K-means聚類算法具體操作步驟如下：初始化。隨機選擇K個初始聚類中心點分配數據點。對于每個數據點，計算其與各個聚類中心的距離，并將其分配到距離最近的聚類中心所對應的類更新聚類中心。對于每個類，計算所有屬于該類的數據點的均值，將該均值作為新的聚類中心重復步驟2和3，直到聚類中心滿足停止誤差準則，或達到預定的迭代次數輸出結果。最終得到K個聚類中心，以及每個數據點所屬的類525.3.2

算法原理頭腦風暴優化算法的主要構成變異為了避免BSO算法陷入局部最優，采用變異思想增加算法解的多樣性，從而有助于得到全局最優解。變異過程主要由個體生成、個體變異構成個體生成個體生成用于從集群中選擇臨時個體，定義生成的臨時解個體為： 。根據概率選擇如下方式生成臨時個體A，即：隨機選中一個類，選擇此類的聚類中心隨機選中一個類，選擇此類中的一個隨機個體隨機選中兩個類，把這兩個類的聚類中心進行生成融合隨機選中兩個類，分別從這兩個類中隨機選出一個個體進行生成融合535.3.2

算法原理頭腦風暴優化算法的主要構成個體變異個體變異是對選擇的臨時解個體疊加隨機擾動，以增強算法的全局尋優能力通過疊加隨機擾動，對生成的臨時個體A進行更新，更新過程為：其中，為疊加隨機擾動后產生的新個體，是均值為且方差為的高斯隨機函數，為對數傳遞函數，用于改變函數的斜率，為最大的進化代數，為在上的隨機數。545.3.2

算法原理頭腦風暴優化算法策略優化過程通過聚類與變異這兩個過程的有機結合，BSO算法能夠在保持種群多樣性的同時，實現高效的局部和全局搜索。BSO算法詳細的實現過程如下在可行解空間內產生潛在問題的L個解個體確定適應度函數并計算L個解個體的適應度值利用K-means聚類算法將L解個體劃分成K類，選中每一類的概率大小與類內個體數量成正比對每個類內個體的適應度值大小進行排序，將適應度值最優的個體視為此類的類中心按照概率進行變異更新將新個體適應度值與原個體進行比較，若新個體較優，替換原個體對所有個體逐一進行更新，若達到停止條件，則迭代停止；否則返回步驟3，直到迭代停止555.3.3典型問題求解案例例題例題5-3