（電路與系統(tǒng)專業(yè)論文）基于粒子群算法的路由優(yōu)化與流量均衡研究.pdf

太原理工大學(xué)工學(xué)碩士研究生學(xué)位論文 i 基于粒子群算法的路由優(yōu)化與流量均衡研究 摘 要 隨著網(wǎng)絡(luò)在諸多領(lǐng)域的應(yīng)用網(wǎng)絡(luò)業(yè)務(wù)呈現(xiàn)快速增長(zhǎng)由此而對(duì)互聯(lián) 網(wǎng)提供的服務(wù)質(zhì)量quality of serviceqos提出更高的要求已經(jīng)證明 帶有性能服務(wù)要求的qos路由和流量?jī)?yōu)化是組合規(guī)劃中的 np-hard 問(wèn)題 諸多學(xué)者引入諸如粒子群算法蟻群算法遺傳算法等智能算法用以此類 問(wèn)題智能算法在網(wǎng)絡(luò)問(wèn)題中的應(yīng)用已成為一個(gè)研究熱點(diǎn)同時(shí)粒子群算 法的應(yīng)用也成為其一個(gè)研究的重要方面 粒子群優(yōu)化particle swarm optimizationpso算法是一種群體智 能算法和啟發(fā)式全局優(yōu)化技術(shù)整個(gè)種群在算法規(guī)定的簡(jiǎn)單行為規(guī)則下能 夠表現(xiàn)出復(fù)雜的特性pso 與其他進(jìn)化計(jì)算方法相比具有可設(shè)置參數(shù)少 計(jì)算速度快和簡(jiǎn)單容易實(shí)現(xiàn)等優(yōu)點(diǎn)這些使其成為一種簡(jiǎn)單有效的隨機(jī)算 法在處理約束條件問(wèn)題時(shí)比傳統(tǒng)的搜索算法要表現(xiàn)靈活的多目前越來(lái) 越多的網(wǎng)絡(luò)應(yīng)用需要 qos 保證,路由算法的目標(biāo)由傳統(tǒng)的尋找一條最短路 徑轉(zhuǎn)變?yōu)閷ふ叶嗉s束下更優(yōu)的路徑由于基于最小跳數(shù)或最小時(shí)延的簡(jiǎn)單 路由算法已經(jīng)不能滿足網(wǎng)絡(luò)中具有質(zhì)量要求和突發(fā)性的流量的需求以及不 同類型的應(yīng)用需求由此必須通過(guò)路由優(yōu)化尋求滿足約束條件的路徑將分 組推至目的節(jié)點(diǎn)進(jìn)而可實(shí)現(xiàn)網(wǎng)絡(luò)中的性能需求負(fù)載平衡等要求 本文在對(duì)粒子群算法的相關(guān)情況和基于粒子群算法的路由算法的綜述 基礎(chǔ)上提出一種關(guān)系矩陣來(lái)作為粒子群算法的編碼方式并用來(lái)處理路 由優(yōu)化和流量均衡問(wèn)題也就是粒子的位置是一個(gè)含有整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié) 太原理工大學(xué)工學(xué)碩士研究生學(xué)位論文 ii 構(gòu)信息的關(guān)系矩陣仿真實(shí)驗(yàn)表明采用關(guān)系矩陣編碼方法可以使粒子群算 法能夠較好的應(yīng)用到路由優(yōu)化和流量均衡問(wèn)題同時(shí)能夠克服其他方法所 帶來(lái)的編碼復(fù)雜對(duì)粒子群算法改動(dòng)較大實(shí)現(xiàn)復(fù)雜等缺點(diǎn)本文所提出 的編碼方法能夠無(wú)須對(duì)粒子群算法做出較大改動(dòng)能夠減少冗余空間的產(chǎn) 生和冗余搜索 關(guān)鍵字 粒子群算法路由優(yōu)化流量均衡關(guān)系矩陣 太原理工大學(xué)工學(xué)碩士研究生學(xué)位論文 iii research on routing optimization and flow balancing based on pso abstract as the network in many fields of application,quality of service provided by network which presents the fast growth is put forward higher request. qos routing and flow balance has been proved a np complete problems, therefore, many scholars apply such as particle swarm algorithm, the ant colony algorithm and genetic algorithm of intelligent algorithm in such problems to seek the optimum solution of the problem. intelligent algorithm in network applications has become a hotspot, and particle swarm algorithm of application is also a study of important aspects. pso is a kind of swarm intelligence algorithm and heuristic global optimization technique, whose individual will flock with no quality and no volume, is a potential solution to solve the problem, and rules stipulated algorithm can show complex characteristics in the simple behavior. pso has fewer set parameters and computing speeder and easier to realize, etc. these make it become a kind of simple and effective in the treatment of random algorithm, constraint condition problem than traditional algorithm to more flexible. at present more and more network application needs to ensure the quality of service, the target by routing algorithm of traditional find a shortest path for more change more optimal path constraint. based on the minimal hop 太原理工大學(xué)工學(xué)碩士研究生學(xué)位論文 iv due to delay or simple routing algorithm in network cannot have satisfied with the constant change of the quality requirements and different types of traffic demand, the application must be sought by routing optimization path will meet the constraints of grouping nodes, which aim to push the performance requirements can realize network load balance, etc. before the related information of pso and the routing algorithm based on pso are proposed, relationship matrix as a kind of encoding method is put forward to deal with routing optimization and flow optimization by pso. therefore the position of a particle must be relationship matrix in order that pso could performance well while dealing with the problems. the kind of encoding method can solve the problem of routing optimization and load balancing in the application of pso , that is , it can reduce the redundant space generating and redundant searching with making little change of using that coding method. keywords: pso,routing optimization,flow balancing, relationship matrix 太原理工大學(xué)工學(xué)碩士研究生學(xué)位論文 1 第一章 引言 1.1 課題背景 互聯(lián)網(wǎng)網(wǎng)絡(luò)業(yè)務(wù)的速猛發(fā)展對(duì)互聯(lián)網(wǎng)的服務(wù)質(zhì)量qos提出了更高的要求目前 隨著通信設(shè)備及其技術(shù)的不斷完善改進(jìn)傳輸鏈路和傳輸節(jié)點(diǎn)已經(jīng)不再是限制網(wǎng)絡(luò)發(fā) 展的主要因素而作為網(wǎng)絡(luò)業(yè)務(wù)交換節(jié)點(diǎn)的交換路由設(shè)備已成為制約網(wǎng)絡(luò)性能的主要 瓶頸由于網(wǎng)絡(luò)動(dòng)態(tài)性和實(shí)時(shí)性的存在傳輸數(shù)據(jù)路徑的實(shí)際狀態(tài)不僅與路徑本身 的條件有關(guān)更受當(dāng)前網(wǎng)絡(luò)路徑上負(fù)載的影響此時(shí)如果網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)全局網(wǎng)絡(luò)服務(wù)質(zhì) 量的狀態(tài)了解不夠精確這就使得路徑狀態(tài)信息的概率模型難以確定預(yù)計(jì)算也不夠 準(zhǔn)確更新路由不實(shí)時(shí)路由算法的計(jì)算復(fù)雜度和時(shí)間復(fù)雜度過(guò)高而不能應(yīng)用在實(shí)際 的網(wǎng)絡(luò)由于可以通過(guò)網(wǎng)絡(luò)所分擔(dān)的網(wǎng)絡(luò)負(fù)載來(lái)充分反映互聯(lián)網(wǎng)絡(luò)復(fù)雜的動(dòng)態(tài)特性 而網(wǎng)絡(luò)負(fù)載又是網(wǎng)絡(luò)動(dòng)態(tài)行為的主導(dǎo)因素因此在保證公平性滿足約束優(yōu)化性 能減少阻塞為主要因素條件下在當(dāng)前的網(wǎng)絡(luò)環(huán)境中進(jìn)行路由優(yōu)化以尋找出最優(yōu)路 徑另外通過(guò)對(duì)網(wǎng)絡(luò)負(fù)載進(jìn)行合理的負(fù)載分擔(dān)規(guī)劃也是提升網(wǎng)絡(luò)性能和保證服務(wù)質(zhì) 量的重要途徑 生命科學(xué)與工程科學(xué)的相互交叉相互滲透和相互促進(jìn)已經(jīng)成為近代科學(xué)技術(shù)發(fā) 展的特點(diǎn)之一粒子群算法的出現(xiàn)及發(fā)展體現(xiàn)了科學(xué)交叉發(fā)展的這種特征和趨勢(shì)近 年來(lái)將粒子群算法應(yīng)用到網(wǎng)絡(luò)優(yōu)化問(wèn)題引起了很多專家學(xué)者的注意粒子群算法作 為一種新的全局優(yōu)化搜索算法以其簡(jiǎn)單通用實(shí)現(xiàn)容易設(shè)置參數(shù)少和魯棒性強(qiáng)等 優(yōu)點(diǎn)和適用于并行處理以及應(yīng)用范圍廣范等顯著特點(diǎn)被成功應(yīng)用到許多網(wǎng)絡(luò)組合優(yōu) 化問(wèn)題中qos(quality of service)路由選擇便是其中之一 為了有效地求解約束優(yōu)化問(wèn)題人們逐漸將目光轉(zhuǎn)向隨機(jī)搜索算法其中仿生隨 機(jī)算法以其較強(qiáng)的求解力通用性日益受到廣大學(xué)者的關(guān)注并逐漸成為求解約束優(yōu) 化問(wèn)題的重要工具與傳統(tǒng)的優(yōu)化算法相比仿生隨機(jī)算法具有許多不可比擬的優(yōu)越 性其中最主要的一點(diǎn)是求解過(guò)程不依賴目標(biāo)函數(shù)的解析性質(zhì)同時(shí)能通過(guò)對(duì)問(wèn)題解 太原理工大學(xué)工學(xué)碩士研究生學(xué)位論文 2 空間的多點(diǎn)并行搜索以較大概率收斂于全局最優(yōu)解另外仿生隨機(jī)算法在處理約束 條件時(shí)比傳統(tǒng)的搜索算法要靈活得多不僅可借助進(jìn)化操作對(duì)傳統(tǒng)的罰函數(shù)法進(jìn)行改 進(jìn)使之更加有效的處理約束條件也可以通過(guò)特定的編碼保證個(gè)體落在可行點(diǎn)集內(nèi) 或者在每一演化代通過(guò)特定的修正算子對(duì)后代個(gè)體進(jìn)行修正以滿足約束條件而不需 要借助于問(wèn)題的梯度信息 粒子群算法是一種簡(jiǎn)單有效的隨機(jī)算法與其它進(jìn)化計(jì)算方法比較起來(lái)它的求 解過(guò)程更加簡(jiǎn)單易行所付出的計(jì)算代價(jià)更小因此也被視為求解 co 問(wèn)題的可行方 法其同樣對(duì)于路由優(yōu)化和流量均衡問(wèn)題也是有效的 1.2 路由算法本身面臨的主要問(wèn)題 路由選擇包含路徑確定和通過(guò)確定的路徑傳輸信息路徑的確定即讓路由器尋找 到一條數(shù)據(jù)包從發(fā)送端通過(guò)諸多不同網(wǎng)絡(luò)到達(dá)目的地的可行路由的過(guò)程路由優(yōu)化的 目的是提高路由選擇協(xié)議選擇路由的能力使路由選擇算法根據(jù)度量標(biāo)準(zhǔn)如帶寬 跳數(shù)和延時(shí)等和度量標(biāo)準(zhǔn)所指定的權(quán)值選擇最優(yōu)路徑以傳輸數(shù)據(jù)分組 由于基于最小跳數(shù)或最小時(shí)延的路由算法已經(jīng)不能滿足當(dāng)前網(wǎng)絡(luò)中帶有服務(wù)質(zhì)量 要求具有突發(fā)性的流量以及不同類型服務(wù)應(yīng)用的要求有必要通過(guò)路由優(yōu)化使路由 算法選擇滿足約束條件的可行路徑將數(shù)據(jù)分組傳遞至目的節(jié)點(diǎn)進(jìn)而實(shí)現(xiàn)網(wǎng)絡(luò)中的管 理策略性能需求負(fù)載平衡和可量測(cè)性等要求當(dāng)前的路由優(yōu)化基本上是實(shí)現(xiàn)基于 多約束條件下對(duì)分組傳遞路徑的智能選擇 目前路由優(yōu)化算法的特征和性能大多都缺少路由模型和理論上的支持因此進(jìn)行 路由優(yōu)化的理論研究比較困難評(píng)價(jià)標(biāo)準(zhǔn)也不全面基于狀態(tài)信息概率分布的 qos 路 由算法必須依賴于鏈路狀態(tài)信息的概率模型而實(shí)際的鏈路狀態(tài)不僅與鏈路本身的條 件有關(guān)而且還受當(dāng)前網(wǎng)絡(luò)流量的影響使得鏈路狀態(tài)信息的概率模型難以確定大 部分路由算法都只是針對(duì) qos 路由問(wèn)題中的某些特殊情況進(jìn)行的設(shè)計(jì)缺少多個(gè)算法 的縱向的比較與分析當(dāng)前的路由算法仍停留在算法研究階段它必須被寫入通信協(xié) 議才能夠被實(shí)際應(yīng)用 太原理工大學(xué)工學(xué)碩士研究生學(xué)位論文 3 1.3 負(fù)載均衡當(dāng)前的問(wèn)題與研究的意義 提高網(wǎng)絡(luò)的運(yùn)行效率網(wǎng)絡(luò)運(yùn)行可靠性網(wǎng)絡(luò)資源的使用效率和流量均衡性能成 為當(dāng)前流量研究的主要目的負(fù)載均衡和流量?jī)?yōu)化的核心任務(wù)就是任務(wù)調(diào)度可以把 多個(gè)請(qǐng)求任務(wù)相對(duì)均衡地分擔(dān)到若干個(gè)控制節(jié)點(diǎn)然后由控制節(jié)點(diǎn)決策路由路徑這 樣就能有效的利用各個(gè)控制節(jié)點(diǎn)并能提高系統(tǒng)的運(yùn)行效率和吞吐能力保障整個(gè)網(wǎng) 絡(luò)系統(tǒng)的實(shí)時(shí)高效運(yùn)行目前開(kāi)放最短路徑優(yōu)先(open shortest path firstospf)是 internet上應(yīng)用最為廣泛的內(nèi)部網(wǎng)關(guān)協(xié)議它采用最短路徑優(yōu)先(shortest path first spf) 算法進(jìn)行路徑的選擇假設(shè)網(wǎng)絡(luò)中的每條路徑都與一個(gè)可管理的權(quán)值相關(guān)spf 總是 選擇鏈路權(quán)值總和最小的路徑但它的缺點(diǎn)是常因此導(dǎo)致網(wǎng)絡(luò)上的流量不能均衡分擔(dān) 到各條路徑使得某些鏈路因?yàn)檫^(guò)載而產(chǎn)生擁塞同時(shí)另一些鏈路分配較少的流量而 處于閑置狀態(tài)因此網(wǎng)絡(luò)流量?jī)?yōu)化體系的主要目的就是優(yōu)化網(wǎng)絡(luò)資源利用率提高 網(wǎng)絡(luò)性能能夠提供有保證的網(wǎng)絡(luò)負(fù)載服務(wù) 1.4 論文的主要內(nèi)容 本文主要針對(duì)粒子算法在網(wǎng)絡(luò)路由優(yōu)化和流量負(fù)載均衡兩個(gè)方面進(jìn)行研究提出 采用關(guān)系矩陣編碼的粒子群算法這種算法立足解決目前粒子群算法在路由優(yōu)化和負(fù) 載均衡方面研究的不足和缺點(diǎn) 本論文共分為五部分主要內(nèi)容章節(jié)安排如下 第一章為引言在提出課題研究的背景和意義后介紹了當(dāng)前路由優(yōu)化和負(fù)載均 衡研究所面臨的問(wèn)題 第二章為相關(guān)研究綜述首先介紹最優(yōu)優(yōu)化問(wèn)題的概念本文對(duì)粒子群算法的基 本概念基本原理和它的改進(jìn)算法做了較為系統(tǒng)的闡述對(duì)路由優(yōu)化的相關(guān)概念進(jìn)行 了介紹并且在此基礎(chǔ)上介紹了粒子群算法在該方面的研究進(jìn)展論文最后指出了當(dāng) 前研究存在的問(wèn)題并作了進(jìn)一步研究方向的展望 第三章主要研究了采用關(guān)系矩陣作為編碼方法的粒子群算法在負(fù)載均衡方面的研 究首先介紹負(fù)載均衡模型在此基礎(chǔ)上對(duì)優(yōu)化問(wèn)題進(jìn)行分析并進(jìn)而提出優(yōu)化的目標(biāo) 函數(shù)最后對(duì)粒子群算法在負(fù)載均衡問(wèn)題上的應(yīng)用作了試驗(yàn)仿真研究 第四章對(duì)基于關(guān)系矩陣的粒子群算法作了應(yīng)用研究在對(duì) qos路由模型進(jìn)行分析 太原理工大學(xué)工學(xué)碩士研究生學(xué)位論文 4 和提出路由優(yōu)化目標(biāo)函數(shù)之后本文對(duì)如何將關(guān)系矩陣映射為路由進(jìn)行了詳細(xì)的介紹 本文最后對(duì)所提出的算法進(jìn)行了仿真試驗(yàn)研究并與遺傳算法進(jìn)行了對(duì)比試驗(yàn) 第五章進(jìn)行了總結(jié)并針對(duì)粒子群算法在負(fù)載均衡和路由優(yōu)化上的進(jìn)一步應(yīng)用提 出一些展望 太原理工大學(xué)工學(xué)碩士研究生學(xué)位論文 5 第二章 相關(guān)研究綜述 2.1 引言 粒子群優(yōu)化(particle swarm optimization, pso)算法是由james kennedy 和russell eberhart博士于1995年提出的一種基于群智能的隨機(jī)全局優(yōu)化技術(shù),其源于鳥(niǎo)群撲食行為 的研究 1 kennedy又在1997年提出二進(jìn)制粒子群算法 2 解決了粒子群在離散問(wèn)題上 的應(yīng)用shi為了提高算法的收斂性在1998年提出了帶有慣性權(quán)重的粒子群算法 3 成 為現(xiàn)在的標(biāo)準(zhǔn)pso算法其后有諸多學(xué)者從算法的參數(shù)設(shè)置種群拓?fù)浣Y(jié)構(gòu)等方面 提出的改進(jìn)算法例如混合pso鄰域pso協(xié)同pso離散pso等并且pso在諸多 領(lǐng)域得到應(yīng)用最早是由kennedy應(yīng)用于分類xor問(wèn)題神經(jīng)網(wǎng)絡(luò)的訓(xùn)練pso已經(jīng)被學(xué) 者們應(yīng)用在函數(shù)優(yōu)化約束及多目標(biāo)優(yōu)化組合規(guī)劃問(wèn)題模糊系統(tǒng)控制等諸多工程 或計(jì)算領(lǐng)域并成為一種重要的優(yōu)化工具 pso是一種群體智能算法和啟發(fā)式全局優(yōu)化技術(shù)將鳥(niǎo)群中的個(gè)體抽象為無(wú)質(zhì)量 無(wú)體積的粒子每個(gè)粒子都是所求解問(wèn)題的一個(gè)潛在解整個(gè)種群在算法規(guī)定的簡(jiǎn)單 行為規(guī)則下能夠表現(xiàn)出復(fù)雜的特性pso與其他進(jìn)化計(jì)算方法相比具有可設(shè)置參數(shù) 少計(jì)算速度快和簡(jiǎn)單易實(shí)現(xiàn)等優(yōu)點(diǎn)這些使其成為一種簡(jiǎn)單有效的隨機(jī)算法在處 理約束條件問(wèn)題時(shí)比傳統(tǒng)的搜索算法要靈活的多 目前越來(lái)越多的網(wǎng)絡(luò)應(yīng)用需要服務(wù)質(zhì)量保證路由算法的目標(biāo)由傳統(tǒng)的尋找一條 最短路徑轉(zhuǎn)變?yōu)閷ふ叶嗉s束下更優(yōu)的路徑由于基于最小跳數(shù)或最小時(shí)延的簡(jiǎn)單路由 算法已經(jīng)不能滿足網(wǎng)絡(luò)中帶有質(zhì)量要求的不斷變化的流量以及不同類型的應(yīng)用需求的 需求必須通過(guò)路由優(yōu)化尋求滿足約束條件的路徑將分組推至目的節(jié)點(diǎn)進(jìn)而可實(shí)現(xiàn) 網(wǎng)絡(luò)中的性能需求負(fù)載平衡等要求 而wang z等 4 證明多qos參數(shù)約束的組播路由問(wèn)題一個(gè)非線性的組合優(yōu)化問(wèn)題 當(dāng)它至少含有兩個(gè)不相關(guān)可加度量的約束條件時(shí)是一個(gè)np-c問(wèn)題而傳統(tǒng)的路由算法 很難解決np-c問(wèn)題通常需要采用啟發(fā)式算法或智能算法解決當(dāng)前提出的啟發(fā)式算 法要么太復(fù)雜而難于求解要么太費(fèi)時(shí)而不能實(shí)際應(yīng)用于是人們開(kāi)始轉(zhuǎn)向研究智能 優(yōu)化算法來(lái)求解該問(wèn)題而粒子群算法是一種具有深刻群智能的演化計(jì)算方法其個(gè) 太原理工大學(xué)工學(xué)碩士研究生學(xué)位論文 6 體之間通過(guò)相互協(xié)作在多點(diǎn)并行搜索最優(yōu)解另外它可以不對(duì)特定問(wèn)題建?；虿灰?賴目標(biāo)函數(shù)的解析性質(zhì)而直接依據(jù)經(jīng)過(guò)變換的輸入信息在問(wèn)題解空間多點(diǎn)并行搜索而 得出問(wèn)題解這些特點(diǎn)使它特別適用于解決路由優(yōu)化問(wèn)題 一些學(xué)者已經(jīng)進(jìn)行了粒子群算法在路由優(yōu)化上的應(yīng)用研究并且取得了一定的成 果他們的仿真實(shí)驗(yàn)結(jié)果顯示粒子群算法在路由優(yōu)化的應(yīng)用是可行的在一定情況下 表現(xiàn)要優(yōu)于其他的智能算算法 2.2 最優(yōu)化問(wèn)題 優(yōu)化已經(jīng)成為一個(gè)廣泛使用的術(shù)語(yǔ)表示從一個(gè)問(wèn)題的可行解中找到最好解或次 優(yōu)解的概念因此可以將優(yōu)化的目標(biāo)定義為尋找滿足約束條件的一組數(shù)或向量使得 優(yōu)化目標(biāo)函數(shù)能夠取得最大值或者最小值另外將一組滿足所有約束條件的解定義 為優(yōu)化目標(biāo)的一組可行解因此最優(yōu)解也可以定義為在所有的可行解中能夠使得目 標(biāo)函數(shù)取得最優(yōu)值的解 所謂最優(yōu)化問(wèn)題就是在滿足一定的約束條件下尋找一組參數(shù)值以使某些最 優(yōu)性度量得到滿足也就是使系統(tǒng)的某些性能指標(biāo)達(dá)到最大或最小優(yōu)化問(wèn)題包括最 大化問(wèn)題和最小化問(wèn)題可以使任何一個(gè)最大化問(wèn)題通過(guò)把目標(biāo)函數(shù)取負(fù)轉(zhuǎn)化為最小 化問(wèn)題同理最小化問(wèn)題也能轉(zhuǎn)化為最大化問(wèn)題最優(yōu)化問(wèn)題的應(yīng)用可以說(shuō)涉及到 工業(yè)社會(huì)經(jīng)濟(jì)管理等各個(gè)領(lǐng)域具有著一定的重要性在本文中所討論的優(yōu)化 問(wèn)題為最小化問(wèn)題 為了后面討論的方便性和不失一般性設(shè)所討論的最小優(yōu)化問(wèn)題為 min( ) . |( )0 i f x st xsx g xir+ = 2-1 其中( )f x為優(yōu)化目標(biāo)函數(shù)( ) i g x為約束條件函數(shù)s為約束域x 為 n 維優(yōu)化 變量一般情況下可以很容易將最大化問(wèn)題( )f x轉(zhuǎn)換為最小化問(wèn)題( )f x 對(duì)于( )0 i g x 的約束也可以轉(zhuǎn)換為( )0 i g x因此對(duì)于式2-1所描述的最小優(yōu)化 問(wèn)題不失一般性 當(dāng)( )f x 為線性函數(shù)且0 x 時(shí)上述最優(yōu)化問(wèn)題即為線性規(guī)劃問(wèn)題其求解方法 太原理工大學(xué)工學(xué)碩士研究生學(xué)位論文 7 有成熟的單純形法和 karmarc方法當(dāng)( )0 () i g xir+所限制的約束空間為 n維歐 氏空間即 n r 時(shí)上述最優(yōu)化問(wèn)題為無(wú)約束優(yōu)化問(wèn)題即 min ( ) s.t. f x xsr+ 2-2 當(dāng)( )f x( ) i g x 中至少有一個(gè)函數(shù)為非線性函數(shù)時(shí)最下優(yōu)化問(wèn)題即為非線性規(guī)劃 問(wèn)題已證明了非線性規(guī)劃問(wèn)題的復(fù)雜性只到目前還沒(méi)有適應(yīng)所有問(wèn)題的有效方法 當(dāng)優(yōu)化變量 x 僅取整數(shù)值時(shí)上述問(wèn)題就成為整數(shù)規(guī)劃問(wèn)題特別是當(dāng) x 僅能取 0 或 1 時(shí)上述問(wèn)題即演變?yōu)?01 整數(shù)規(guī)劃問(wèn)題由于其計(jì)算量隨變量維數(shù)的增長(zhǎng)而呈指數(shù) 級(jí)增長(zhǎng)因此存在著維數(shù)災(zāi)難問(wèn)題 非線性規(guī)劃問(wèn)題包括無(wú)約束優(yōu)化問(wèn)題和約束優(yōu)化問(wèn)題由于函數(shù)的非線性使 得問(wèn)題的求解變得十分困難特別是當(dāng)目標(biāo)函數(shù)在約束域內(nèi)存在多峰值時(shí)常見(jiàn)的求 解非線性問(wèn)題的優(yōu)化方法其求解結(jié)果與初值的選擇關(guān)系很大也就是說(shuō)一般的約 束或無(wú)約束非線性優(yōu)化方法均是求目標(biāo)函數(shù)在約束域內(nèi)的近似極值點(diǎn)而非真正的最 小點(diǎn) 2.2.1局部?jī)?yōu)化算法 定 義2-1 若 * b xb使 得 對(duì)xb有 * ()() b f xf xxb成 立其 中 n bsrs為為由約束函數(shù)限定的搜索空間則稱 * b x 為( )f x 在 b內(nèi)的局部極小點(diǎn) * () b f x 為局部極小值 常見(jiàn)的優(yōu)化方法大多為局部?jī)?yōu)化方法都是依據(jù)一定的方法從一個(gè)給定的初始點(diǎn) 0 xs開(kāi)始尋找下一個(gè)使得目標(biāo)函數(shù)得到改善的更好解直至滿足某種停止準(zhǔn)則成 熟的局部?jī)?yōu)化方法很多如 newton-raphson法fletcher-reeves 法polar-ribiere 法 共軛梯度法 broyden-fletcher-goldfarb-shann(bfgs)方法 davidon-fletcher-power(dfp) 法等等這些優(yōu)化算法的局限性在于他們都是針對(duì)無(wú)約束優(yōu)化問(wèn)題而提出的并且對(duì) 目標(biāo)函數(shù)均有一定的解析性質(zhì)要求 將約束問(wèn)題通過(guò)罰函數(shù)法轉(zhuǎn)換為無(wú)約束優(yōu)化問(wèn)題是求解約束非線性優(yōu)化問(wèn)題最常 太原理工大學(xué)工學(xué)碩士研究生學(xué)位論文 8 用的方法然后再用無(wú)約束優(yōu)化方法進(jìn)行求解 2.2.2全局優(yōu)化算法 定義2-2 若 * xs使得xs有 * ()(),f xf xxs成立其中 n sr為 約束條件限定的搜索空間則稱 * x 為()f x 在 s 內(nèi)的全局極小點(diǎn) * ()f x為全局極小 值 目前為止全局優(yōu)化問(wèn)題也已存在了許多算法如填充函數(shù)法等但比起局部?jī)?yōu) 化問(wèn)題的眾多成熟方法其間還有很大差距另外解析性優(yōu)化方法對(duì)目標(biāo)函數(shù)及約 束域均有較強(qiáng)的解析性要求對(duì)于諸如目標(biāo)函數(shù)不連續(xù)約束域不連通目標(biāo)函數(shù)難 以用解析函數(shù)表達(dá)或者難以精確估計(jì)等問(wèn)題時(shí)解析確定性優(yōu)化方法就難以適應(yīng) 為了可靠解決全局優(yōu)化問(wèn)題人們?cè)噲D放棄解析確定型的優(yōu)化算法研究轉(zhuǎn)而探 討對(duì)函數(shù)解析性質(zhì)要求較低甚至不作要求的隨機(jī)型優(yōu)化方法最早的隨機(jī)優(yōu)化方法是 基于monte-carlo方法的思想針對(duì)具體問(wèn)題性質(zhì)的特點(diǎn)構(gòu)造以概率1收斂于全局最小 點(diǎn)的隨機(jī)搜索算法真正有效且具有普遍適應(yīng)性的隨機(jī)全局優(yōu)化方法是模擬自然界 的一些自然現(xiàn)象而發(fā)展起來(lái)的一系列仿生型智能優(yōu)化算法如模擬退火方法進(jìn)化類 算法群體智能算法等算法 2.2.3 進(jìn)化算法 近十余年來(lái)遺傳算法(genetic algorithmga)進(jìn)化策略(evolutionary strategy es)進(jìn)化規(guī)劃(evolutionary programmingep)等進(jìn)化類算法在理論和應(yīng)用兩方面發(fā)展 迅速效果顯著并逐漸走向了融合形成了一種新穎的模擬進(jìn)化的計(jì)算理論統(tǒng)稱 為進(jìn)化計(jì)算(evolutionary computationec)進(jìn)化計(jì)算的具體實(shí)現(xiàn)方法與形式稱為進(jìn)化 算法(evolutionary algorithmea)進(jìn)化算法是一種受生物進(jìn)化論和遺傳學(xué)等理論啟發(fā) 而形成的求解優(yōu)化問(wèn)題的隨機(jī)算法 1.遺傳算法 遺傳算法最早是由美國(guó) michigan 大學(xué)的 j.holland 博士提出的1975 年依他的 開(kāi)創(chuàng)性的著作adaptive in natural and artificial systems標(biāo)志著遺傳算法的正式誕生 遺傳算法的操作對(duì)象是一組二進(jìn)制串即種群(population)每一個(gè)二進(jìn)制串稱為染色 體每個(gè)染色體或個(gè)體都對(duì)應(yīng)于問(wèn)題的一個(gè)解從初始種群出發(fā)采用基于適應(yīng)值比 例的選擇策略在當(dāng)前種群中選擇個(gè)體并使用交叉和變異來(lái)產(chǎn)生下一代種群如此一 太原理工大學(xué)工學(xué)碩士研究生學(xué)位論文 9 代一代進(jìn)化下去直至滿足期望的終止條件 遺傳算法是一中可用于復(fù)雜系統(tǒng)優(yōu)化的具有魯棒性的搜索算法與傳統(tǒng)的優(yōu)化算 法相比主要有以下特點(diǎn) 1遺傳算法以決策變量的編碼作為運(yùn)算對(duì)象傳統(tǒng)的優(yōu)化算法往往直接決策變 量的實(shí)際植本身而遺傳算法處理決策變量的某種編碼形式使得我們可以借鑒生物 學(xué)中的染色體和基因的概念可以模仿自然界生物的遺傳和進(jìn)化機(jī)理也使得我們能 夠方便的應(yīng)用遺傳操作算子 2遺傳算法直接以適應(yīng)度作為搜索信息無(wú)需導(dǎo)數(shù)等其它輔助信息 3遺傳算法使用多個(gè)點(diǎn)的搜索信息具有隱含并行性 4遺傳算法使用概率搜索技術(shù)而非確定性規(guī)則 5搜索過(guò)程不直接作用在變量上而是在參數(shù)集進(jìn)行了編碼的個(gè)體此編碼操 作使得遺傳算法可以直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作 6搜索過(guò)程是一組迭代到另一組解采用同事處理群體中多個(gè)個(gè)體的方法具 有本質(zhì)的并行性 7遺傳算法利用概率轉(zhuǎn)移規(guī)則可以在一個(gè)具有不確定性的空間上尋優(yōu)與一 般的隨機(jī)型優(yōu)化方法相比遺傳算法不是從一點(diǎn)出發(fā)沿一條線尋優(yōu)而是在整個(gè)解空 間同事開(kāi)始尋優(yōu)搜索因此可以有效地比賣弄陷入局部極小點(diǎn)具備全局最優(yōu)搜索性 8對(duì)搜索空間沒(méi)有任何特殊要求只以決策變量的編碼作為運(yùn)算對(duì)象在優(yōu)化 過(guò)程中借鑒生物學(xué)中染色體和基因等概念模擬自然界中生物的遺傳和進(jìn)化等原理 應(yīng)用遺傳操作不需要導(dǎo)數(shù)等其他輔助信息可用于求解無(wú)數(shù)值概念或很難有數(shù)值概 念的優(yōu)化問(wèn)題適應(yīng)范圍更廣 9遺傳算法有極強(qiáng)的容錯(cuò)能力遺傳算法的初始串集本身就帶有大量的與最優(yōu) 解甚遠(yuǎn)的信息通過(guò)選擇交叉變異操作能迅速排除與最優(yōu)解相差極大的串這是 一個(gè)強(qiáng)烈的濾波過(guò)程并且是一個(gè)并行濾波機(jī)制因而遺傳算法具有很高的容錯(cuò)能力 10遺傳算法的選擇交叉和變異都是隨機(jī)操作而不是確定的精確規(guī)則這 說(shuō)明遺傳算法是采用隨機(jī)方法進(jìn)行最優(yōu)解搜索選擇體現(xiàn)了向最優(yōu)解的迫近交叉體 現(xiàn)了最優(yōu)解的產(chǎn)生變異體現(xiàn)了全局最優(yōu)解的覆蓋 2.進(jìn)化策略 進(jìn)化策略是由德國(guó)柏林工業(yè)大學(xué)的 i.rechenberg和 h.p.schwefel等提出的早期的 太原理工大學(xué)工學(xué)碩士研究生學(xué)位論文 10 演化策略其種群只包含一個(gè)個(gè)體且只使用變異操作具體在每一操作代中變異后 的個(gè)體與其父代個(gè)體進(jìn)行比較從中擇優(yōu)選取作為新一代個(gè)體這就是所謂的(11)策 略它所使用的變異算子主要是基于正態(tài)分布的變異操作 進(jìn)化策略與遺傳算法相比其主要不同之處在于遺傳算法是將原問(wèn)題的解空間 映射到位串空間上然后再進(jìn)行遺傳操作它強(qiáng)調(diào)的是個(gè)體基因結(jié)構(gòu)的變化對(duì)其適應(yīng) 度的影響而進(jìn)化策略則是直接在解空間上進(jìn)行遺傳操作它強(qiáng)調(diào)的是父代到子代行 為的自適應(yīng)性和多樣性 3.進(jìn)化規(guī)劃 進(jìn)化規(guī)劃(evolutionary programmingep)方法最初是由美國(guó)科學(xué)家 lawrence j.fogel 等人在 20 世紀(jì) 60 年代提出的它在求解連續(xù)參數(shù)優(yōu)化問(wèn)題時(shí)與 es 的區(qū)別很小進(jìn) 化規(guī)劃僅使用變異與選擇算子而絕對(duì)不使用任何重組算子其變異算子與進(jìn)化策略 的變異相類似也是對(duì)父代個(gè)體采用基于正態(tài)分布的變異操作進(jìn)行變異生成相同數(shù) 量的子代個(gè)體即個(gè)父代個(gè)體總共產(chǎn)生個(gè)子代個(gè)體ep 采用一種隨機(jī)競(jìng)爭(zhēng)選擇 方法從父代和子代的并集中選擇出個(gè)個(gè)體構(gòu)成下一代群體其選擇過(guò)程如下對(duì) 于由父代個(gè)體和子代個(gè)體組成的大小為 2的臨時(shí)群體中的每一個(gè)個(gè)體從其它 2 1個(gè)個(gè)體中隨機(jī)等概率地選取出 q 個(gè)個(gè)體與其進(jìn)行比較在每次比較中若該個(gè)體的適 應(yīng)值不小于與之比較的個(gè)體的適應(yīng)值則稱該個(gè)體獲得一次勝利從 2個(gè)個(gè)體中選擇 出獲勝次數(shù)最多的個(gè)個(gè)體作為下一代群體 4.模擬退火算法 模擬退火算法來(lái)源于固體退火原理將固體加溫至充分高再讓其徐徐冷卻加 溫時(shí)固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀內(nèi)能增大而徐徐冷卻時(shí)粒子漸趨有序在 每個(gè)溫度都達(dá)到平衡態(tài)最后在常溫時(shí)達(dá)到基態(tài)內(nèi)能減為最小根據(jù) metropolis 準(zhǔn) 則粒子在溫度 t 時(shí)趨于平衡的概率為 e-e/(kt)其中 e 為溫度 t 時(shí)的內(nèi)能e 為 其改變量k 為 boltzmann 常數(shù)用固體退火模擬組合優(yōu)化問(wèn)題將內(nèi)能 e 模擬為目標(biāo) 函數(shù)值 f溫度 t 演化成控制參數(shù) t即得到解組合優(yōu)化問(wèn)題的模擬退火算法由初始 解 i 和控制參數(shù)初值 t 開(kāi)始對(duì)當(dāng)前解重復(fù)產(chǎn)生新解?計(jì)算目標(biāo)函數(shù)差?接受或舍棄 的迭代并逐步衰減 t 值算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解這是基于蒙特卡 羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過(guò)程退火過(guò)程由冷卻進(jìn)度表(cooling schedule) 控制包括控制參數(shù)的初值 t 及其衰減因子 t每個(gè) t 值時(shí)的迭代次數(shù) l 和停止條件 s 太原理工大學(xué)工學(xué)碩士研究生學(xué)位論文 11 模擬退火算法與初始值無(wú)關(guān)算法求得的解與初始解狀態(tài) s(是算法迭代的起點(diǎn))無(wú) 關(guān)模擬退火算法具有漸近收斂性已在理論上被證明是一種以概率 l 收斂于全局最 優(yōu)解的全局優(yōu)化算法模擬退火算法具有并行性模擬退火法的實(shí)驗(yàn)性能具有質(zhì)量高 初始魯棒性能強(qiáng)通用易實(shí)現(xiàn)的特點(diǎn)但同時(shí)通過(guò)上面的分析可以看出模擬退火法 也存在一下不足 1盡管理論上只要計(jì)算時(shí)間足夠長(zhǎng)模擬退火法就可以保證以概率 1 收斂于全 局最優(yōu)點(diǎn)但是在實(shí)際算法的實(shí)現(xiàn)過(guò)程中由于計(jì)算速度和時(shí)間的限制在優(yōu)化效果 和計(jì)算時(shí)間二者之間存在矛盾因而難以保證計(jì)算結(jié)果為全局最優(yōu)點(diǎn)優(yōu)化效果不甚 明顯 2在每一溫度下很難判斷是否達(dá)到了平衡狀態(tài)即馬爾科夫鏈的長(zhǎng)度不易控制 反映到算法上就是 metropolis 過(guò)程的次數(shù)不易控制 3模擬退火算法的兩種退火方式t 始終按照優(yōu)化前給定的規(guī)律變化而沒(méi)有修 正這是不科學(xué)的 2.2.4 群體智能算法 1.蟻群算法 蟻群算法(ant colony algorithm)也稱螞蟻算法是在 20 世紀(jì) 90 年代初由意大利 學(xué)者 m.dorigo 提出的它是根據(jù)螞蟻覓食原理而設(shè)計(jì)的一種群體智能算法據(jù)研究 當(dāng)螞蟻找到食物并將它搬回來(lái)時(shí)就會(huì)在它經(jīng)過(guò)的路上留下一種外激素其它螞蟻 聞到這種激素的味道就沿該路線去覓食而且還會(huì)沿著最短的路徑奔向食物它 具有以下特點(diǎn) 1蟻群優(yōu)化算法是一種結(jié)合了分布式計(jì)算正反饋機(jī)制和貪婪式搜索的算法 具有很強(qiáng)的搜索較優(yōu)解的能力正反饋能夠快速地發(fā)現(xiàn)較優(yōu)解分布式計(jì)算避免了早 熟收斂而貪婪式搜索有助于在搜索過(guò)程中早期找出可接受的解決方案縮短了搜索 時(shí)間 2蟻群算法具有很強(qiáng)的并行性 3可以不通過(guò)個(gè)體之間直接通信而是通過(guò)信息素進(jìn)行合作這樣的系統(tǒng)具有更 好的可擴(kuò)展性由于隨著系統(tǒng)中個(gè)體增加而增加的系統(tǒng)通信開(kāi)銷在這里將非常小 但是蟻群算法具有以上所述的優(yōu)點(diǎn)同時(shí)它也有以下兩個(gè)方面的缺點(diǎn) 1該算法一般需要較長(zhǎng)的搜索時(shí)間蟻群中各個(gè)個(gè)體的運(yùn)動(dòng)是隨機(jī)的雖然通 太原理工大學(xué)工學(xué)碩士研究生學(xué)位論文 12 過(guò)信息交換能夠向著最優(yōu)路徑進(jìn)化但是當(dāng)群體規(guī)模較大時(shí)很難在較短的時(shí)間內(nèi)從 大量雜論無(wú)章的路徑中找到一條較好的路徑這是因?yàn)樵谶M(jìn)化的處級(jí)階段各個(gè)路徑 上信息量相差不明顯通過(guò)的信息正反饋使得較好路徑上的信息量逐漸增大經(jīng)過(guò) 較長(zhǎng)時(shí)間才能使得較好路徑上的信息量明顯高于其他路徑上的信息量隨著這一過(guò) 程的進(jìn)行差別越來(lái)越明顯從而最終收斂于較好的路徑這一過(guò)程一般需要較長(zhǎng)的 時(shí)間 2該算法容易出現(xiàn)停止現(xiàn)象即搜索進(jìn)行到一定程度后所有個(gè)體所發(fā)現(xiàn)的解 完全一致不能對(duì)解空間進(jìn)一步進(jìn)行搜索不利于發(fā)現(xiàn)更好的解 2.粒子群算法 粒子群算法(particle swarm optimizationpso)是在 1995 年由美國(guó)社會(huì)心理學(xué)家 james kennedy和電氣工程師 russell eberhart共同提出的其基本思想是受他們?cè)缙趯?duì) 鳥(niǎo)類群體行為研究結(jié)果的啟發(fā)并利用了生物學(xué)家 frank heppner 的生物群體模型有 關(guān)粒子群算法的詳細(xì)介紹是本文后續(xù)各章節(jié)的內(nèi)容在這里就不作闡述 2 . 3 粒子群算法 自然界中各種生物體均具有一定的群體行為而人工生命的主要研究領(lǐng)域之一就 是探索自然界生物的群體行為從而在計(jì)算機(jī)上構(gòu)建其群體模型通常群體行為可以 由幾條簡(jiǎn)單的規(guī)則進(jìn)行建模如魚(yú)群鳥(niǎo)群等雖然每一個(gè)個(gè)體具有非常簡(jiǎn)單的行為 規(guī)則但群體的行為卻非常復(fù)雜 粒子群算法最早是在 1995 年由美國(guó)社會(huì)心理學(xué)家 james kennedy 和電氣工程師 russell eberhart 共同提出的其基本思想是受他們?cè)缙趯?duì)許多鳥(niǎo)類的群體行為進(jìn)行建 模與仿真研究結(jié)果的啟發(fā) 由于鳥(niǎo)類使用簡(jiǎn)單的規(guī)則確定自己的飛行方向與飛行速度實(shí)質(zhì)上每一只鳥(niǎo)都 試圖停在鳥(niǎo)群中而又不相互碰撞當(dāng)一只鳥(niǎo)飛離鳥(niǎo)群而飛向棲息地時(shí)將導(dǎo)致它周圍 的其它鳥(niǎo)也飛向棲息地這些鳥(niǎo)一旦發(fā)現(xiàn)棲息地將降落在此驅(qū)使更多的鳥(niǎo)落在棲 息地直到整個(gè)鳥(niǎo)群都落在棲息地 由于 james kennedy 和 russell eberhart 所具有的專業(yè)背景就能很容易理解他們 為什么會(huì)對(duì) hepper 的鳥(niǎo)類模型感興趣鳥(niǎo)類尋找棲息地與對(duì)一個(gè)特定問(wèn)題尋找解很類 似已經(jīng)找到棲息地的鳥(niǎo)引導(dǎo)它周圍的鳥(niǎo)飛向棲息地的方式增加了整個(gè)鳥(niǎo)群都找到 太原理工大學(xué)工學(xué)碩士研究生學(xué)位論文 13 棲息地的可能性也符合信念的社會(huì)認(rèn)知觀點(diǎn) eberhart和 kennedy對(duì)以往的模型進(jìn)行了修正以使粒子個(gè)體能夠飛向解空間并在 最好解處降落其關(guān)鍵在于如何保證微粒降落在最好解處而不降落在其它解處這就 是信念的社會(huì)性及智能性所在信念具有社會(huì)性的實(shí)質(zhì)在于個(gè)體向它周圍的成功者學(xué) 習(xí)個(gè)體與周圍的其它同類比較并模仿其優(yōu)秀者的行為將這種思想用算法實(shí)現(xiàn)將 導(dǎo)致一種新的最優(yōu)化算法要解決上述問(wèn)題關(guān)鍵在于在探索尋找一個(gè)好解和開(kāi) 發(fā)利用一個(gè)好解之間尋找一個(gè)好的平衡太小的探索導(dǎo)致算法收斂于早期所遇到 的好解處而太小的開(kāi)發(fā)會(huì)使算法不收斂另一方面需要在個(gè)性與社會(huì)性之間尋求 平衡也就是說(shuō)既希望個(gè)體具有個(gè)性化像鳥(niǎo)類模型中的鳥(niǎo)不互相碰撞又希望其 知道其它個(gè)體已經(jīng)找到的好解并向它們學(xué)習(xí)即社會(huì)性 2.3.1 基本的粒子群算法原理 粒子群算法與其它進(jìn)化類算法相類似也采用群體與進(jìn)化的概念同樣 也是依據(jù)個(gè)體粒子的適應(yīng)值大小進(jìn)行操作所不同的是粒子群算法不像其它進(jìn) 化算法那樣對(duì)于個(gè)體使用進(jìn)化算子而是將每個(gè)個(gè)體看作是在n維搜索空間中的一個(gè)沒(méi) 有重量和體積的粒子并在搜索空間中以一定的速度飛行該飛行速度由個(gè)體的飛行 經(jīng)驗(yàn)和群體的飛行經(jīng)驗(yàn)進(jìn)行動(dòng)態(tài)調(diào)整 假設(shè)有m個(gè)粒子組成的粒子群體在d維空間中依一定的速度飛行搜索粒子群算法 先隨機(jī)初始化各粒子位置使得粒子具有在解空間的全局探索能力然后通過(guò)迭代找 到最優(yōu)解每次迭代粒子通過(guò)跟蹤兩個(gè)極值個(gè)體與鄰域極值來(lái)改變自己的飛行 速度使其從這些較優(yōu)解獲得信息趨向于對(duì)相應(yīng)鄰近區(qū)域的局部搜索 設(shè) 12 (,) iiiin xxxx=為粒子i 的當(dāng)前位置 12 (,) iiiin vvvv=為粒子i 的當(dāng)前飛行速度 12 (,) iiiin pp pp=為粒子i 所經(jīng)歷的最好位置也就是粒子i 所經(jīng)歷過(guò)的具有最 好適應(yīng)值的位置稱為個(gè)體最好位置對(duì)于最小化問(wèn)題目標(biāo)函數(shù)值越小對(duì)應(yīng)的適 應(yīng)值越好 由于本文以后章節(jié)討論的都是最小化問(wèn)題和討論方便設(shè)()f x 為最小化的目標(biāo)函 數(shù)則粒子i 的當(dāng)前最好位置由下式2 - 3 確定 太原理工大學(xué)工學(xué)碩士研究生學(xué)位論文 14 ( ) if( ( (1)( ( ) (1) (1) if( ( (1)( ( ) iii i iii p tf x tf p t p t x tf x tf p t + += + 2 - 3 設(shè)群體中的粒子數(shù)為m 群體中所有粒子所經(jīng)歷過(guò)的最好位置為 g p稱為全局最好 位置則有 1212 ( )( ),( ),( ) |( )min ( ( ),( ),( ) gmgm p tp tp tptf p tf p tf p tf pt=2 - 4 為了簡(jiǎn)單起見(jiàn)只列出粒子i 位置和速度的第d 維分量更新公式 1 12 2 (1)( )( )( ) ididididgdid vtvtc r pxtc rpxt+=+ 2 - 5 (1)( )(1) ididid xtxtvt+=+ 2 - 6 其中通常為了防止v i d過(guò)大 使得粒子搜索域超出搜索空間使其滿足: max | id vv 在式2 - 5 中第一部分vid(t)表示粒子的當(dāng)前飛行速度它使粒子具有一定全局的 搜索能力第二部分是粒子的認(rèn)知部分表示對(duì)自身經(jīng)驗(yàn)的學(xué)習(xí)過(guò)程第三部分 為社會(huì)認(rèn)知表示粒子學(xué)習(xí)其他粒子經(jīng)驗(yàn)的過(guò)程表現(xiàn)了微粒間信息的共享與社會(huì)協(xié) 作 1 c,2c代表粒子從個(gè)體極值和全局極值的信息繼承度反映了對(duì)繼承信息的程度 簡(jiǎn)而言之粒子在認(rèn)知模型和社會(huì)模型的作用下分別從其個(gè)體極值和全局 極值繼承部分信息并利用粒子的速度進(jìn)行隨機(jī)搜索 雖然已經(jīng)證明粒子群算法在解決非線性不可微多模態(tài)等復(fù)雜優(yōu)化問(wèn)題時(shí)具有 收斂度快強(qiáng)壯性好等特點(diǎn)并已成為的一種有效方法但它在進(jìn)化后期也存在容易 陷入局部最優(yōu)解因此其也存在收斂精度不高易發(fā)散等缺點(diǎn)為此許多學(xué)者針對(duì) 這些問(wèn)題提出了多種改進(jìn)方法以期提高算法的全局搜索能力和精度 2.3.2改進(jìn)的粒子群算法 1.帶有慣性權(quán)重的pso算法 yshi和r.c.eberhart在首次引進(jìn)慣性權(quán)重 3 即將(1)式變?yōu)橄率?2 - 7): 1 12 2 (1)( )( )( )( )( ) ididididgid vtvtc r ptxtc r p txt+=+ (2 - 7) 在大多文獻(xiàn)中將帶有慣性權(quán)重的pso算法稱為標(biāo)準(zhǔn)pso算法慣性權(quán)重w表明微 粒原先的速度能在多大程度上得到保留通常采用線性減小的方法來(lái)達(dá)到開(kāi)始階段具 有較強(qiáng)的全局搜索能力而在后期以較小的能夠收斂到最優(yōu)解但是對(duì)于某些特殊的 問(wèn)題此方法并不湊效有的學(xué)者就此提出了只對(duì)的改進(jìn)pso算法比如shi y等提出 太原理工大學(xué)工學(xué)碩士研究生學(xué)位論文 15 了一種用模糊規(guī)則動(dòng)態(tài)調(diào)整的方法 5 通過(guò)對(duì)當(dāng)前最好性能評(píng)價(jià)(cbpe)和當(dāng)前慣性權(quán) 重制定相應(yīng)的隸屬度函數(shù)和模糊推理規(guī)則, 確定慣性權(quán)重的增量胡建秀等給出了典 型的線性遞減線性微分遞減非線性微分變化和步長(zhǎng)較小的線性遞減等四種慣性權(quán) 重調(diào)整策略 6 2.帶有收縮因子的pso算法 clerc m 等人對(duì)pso算法的收斂性進(jìn)行了研究證明采用收斂因子能夠確保算法的 收斂7,8基于收斂因子的算法速度公式為 1 12 2 (1)( )( )( )( )( ) ididididgdid vtvtc r ptxtc rptxt+=+ ( 2 - 8 ) 其中收斂因子滿足 2 2 = |24 | 且 12 = + 4cc 其相關(guān)的實(shí)驗(yàn)結(jié)果表明與使用慣性權(quán)重的粒子群優(yōu)化算法相比使用收斂因子 的粒子群優(yōu)化算法有更快的收斂速度在使用收縮因子時(shí)首先對(duì)算法進(jìn)行限定這樣 幾乎可以改進(jìn)算法對(duì)所有測(cè)試函數(shù)的求解性能 3.混合粒子群算法 利用選擇的方法:文獻(xiàn)9將選擇算子引進(jìn)pso算法中作為錦標(biāo)賽選擇算子將每個(gè) 個(gè)體的適應(yīng)度與種群中的其他個(gè)體的適應(yīng)度逐一進(jìn)行比較如果當(dāng)前個(gè)體的適應(yīng)度優(yōu) 于某個(gè)個(gè)體的適應(yīng)度則每次授予該個(gè)體一分根據(jù)個(gè)體所得的分?jǐn)?shù)對(duì)種群中的個(gè)體 進(jìn)行由大到小的排列選擇種群中頂部的一半個(gè)體并對(duì)他們進(jìn)行復(fù)制取代種群底 部的一半個(gè)體在此過(guò)程中最佳個(gè)體的適應(yīng)度并未改變 借鑒雜交的方法:angeline 1 0 提出了雜交粒子群算法在每次迭代中依據(jù)指定的 雜交概率選取指定數(shù)量的粒子放入一個(gè)池中池中的粒子隨機(jī)兩兩雜交產(chǎn)生相同數(shù) 量的后代并用后代代替父代雜交算法并不改變粒子位置量的大小而只是改變其 方向 利用變異的方法:李寧提出的基于帶變異算子的粒子群算法 1 1 中在子群的歷史最 優(yōu)粒子位置pl連續(xù)無(wú)變化或變化極小時(shí)若粒子群出現(xiàn)較嚴(yán)重聚集情況則保留歷史最 優(yōu)粒子位置pl將粒子中少部分維重新隨機(jī)初始化這樣同時(shí)能夠保持算法的收斂速度 和搜索精度文獻(xiàn)12引入克隆選擇使群體最佳微粒實(shí)現(xiàn)遺傳微變局部增值具有變 異確定性,同時(shí)又設(shè)計(jì)一個(gè)考慮粒子分布和迭代次數(shù)的函數(shù),自適應(yīng)調(diào)整粒子的“社會(huì)認(rèn) 知”能力提高種群的多樣性利用logistic序列指導(dǎo)最佳粒子隨機(jī)漂移進(jìn)一步增強(qiáng)逃 太原理工大學(xué)工學(xué)碩士研究生學(xué)位論文 16 離局部極值能力 利用模擬退火算法作為收斂判據(jù)文獻(xiàn)13 提出了一種基于粒子群算法與模擬退 火算法的混合方法以模擬退火算法作為粒子群算法的收斂判據(jù)并為不收斂的群體置 換新的粒子從而使群體向全局最優(yōu)解方向飛行即當(dāng)基本粒子群算法收斂到某一解pg 時(shí),用pg作為模擬退火算法的初始點(diǎn)進(jìn)行搜索如果得到一個(gè)比pg較優(yōu)的新解y然后用 y來(lái)隨機(jī)取代粒子群中的一個(gè)粒子用基本粒子群算法繼續(xù)進(jìn)化如果不存在這樣的一 個(gè)解y則說(shuō)明pg就是全局最優(yōu)解仿真試驗(yàn)證明這種混合方法能夠有效地改進(jìn)pso算 法的早熟現(xiàn)象 引進(jìn)免疫機(jī)制的改進(jìn)算法文獻(xiàn) 1 4 結(jié)合粒子群優(yōu)化算法具有的全局尋優(yōu)能力和 免疫系統(tǒng)的免疫信息處理機(jī)制而引入免疫機(jī)制的概念以此來(lái)增強(qiáng)粒子群優(yōu)化算法擺 脫局部極值點(diǎn)的能力提高了算法收斂速度和精度 4.基于鄰域思想的改進(jìn)算法 p. n. suganthan在1999年提出一種基于領(lǐng)域結(jié)構(gòu)的粒子群算法 1 5 每個(gè)粒子領(lǐng)域隨 著迭代從自身擴(kuò)大至整個(gè)粒子群j. kennedy研究了不同拓?fù)浣Y(jié)構(gòu)對(duì)粒子群算法的影響 1 6 并且最終提出了幾種基本粒子群拓?fù)浣Y(jié)構(gòu) 1 7 隨后出現(xiàn)了諸多的基于鄰域的改進(jìn) 算法比如邢萬(wàn)波提出的自適應(yīng)改變鄰域結(jié)構(gòu)粒子群算法 1 8 5.多子群協(xié)同優(yōu)化算法 多種群協(xié)同優(yōu)化算法是將粒子群劃分成多個(gè)子群子群之間依特定方式相互聯(lián)系 交互信息共同對(duì)問(wèn)題協(xié)同優(yōu)化bask s 提出的多種群協(xié)同優(yōu)化粒子位置的不同維的 協(xié)同粒子群算法 1 9 parsopoulos k.e 提出的將子群依據(jù)多目標(biāo)函數(shù)劃分子群的用于優(yōu) 化多目標(biāo)問(wèn)題的 vepso 2 0 6.保證種群多樣性的粒子群算法 j. riget提出了一種保證種群多樣性的粒子群算法 2 1 該算法引入吸引和擴(kuò) 散兩個(gè)算子動(dòng)態(tài)地調(diào)整勘探與開(kāi)發(fā)比例從而能更好的提高算法效率 在介婧等提出的基于群體多樣性負(fù)反饋控制的自組織粒子群算法 2 2 中將粒子群體視 為自組織系統(tǒng)引入負(fù)反饋機(jī)制用多樣性參考輸入 d i和當(dāng)前的群體多樣性 do差值的 正負(fù)來(lái)動(dòng)態(tài)調(diào)整慣性權(quán)重或加速度系數(shù)通過(guò)不同的特性參數(shù)實(shí)現(xiàn)粒子的集聚或分散 使群體維持適當(dāng)?shù)亩鄻有运揭岳谌炙阉?7.保證全局收斂的隨機(jī)粒子群算 一種保證全局收斂的隨機(jī) pso 算法 2 3 其基本思想是利用停止進(jìn)化的粒子來(lái)改 善全局搜索能力在基本 pso 算法中當(dāng) w=0 時(shí)使得全局搜索能力減弱而局部搜 太原理工大學(xué)工學(xué)碩士研究生學(xué)位論文 17 索能力加強(qiáng)但這樣也使得在進(jìn)化的某一代均至少有一個(gè)粒子由于處于粒子群的歷史 最好位置而停止進(jìn)化然后在搜索空間中重新隨機(jī)產(chǎn)生新的微粒以代替停止粒子的進(jìn) 一步進(jìn)化這樣就大大增強(qiáng)了全局搜索能力 2.3.3離散粒子群算法 為了用p s o 算法求解離散組合優(yōu)化問(wèn)題主要有兩種離散粒子群算法形式 2 4 基于 連續(xù)空間的d p s o 和基于離散空間的d p s o 前者是以經(jīng)典的連續(xù)粒子群算法為基礎(chǔ)針 對(duì)特定問(wèn)題將離散問(wèn)題空間映射到連續(xù)粒子運(yùn)動(dòng)空間并適當(dāng)修改p s o 算法來(lái)求解 在計(jì)算上仍保留經(jīng)典粒子群算法速度- 位置更新中的在連續(xù)運(yùn)算規(guī)則比如二進(jìn)制p s o 算法( b p s o ) 2 和用于求解整數(shù)規(guī)劃的p s o 算法 2 5 后者是針對(duì)離散優(yōu)化問(wèn)題在保持經(jīng) 典p s o 算法信息更新機(jī)制基本思想算法框架下, 重新定義特有的粒子群離散表示方 式與操作算子來(lái)求解比如c l e r c 2 6 和k a n g - p i n g w a n g 2 7 針對(duì)旅行商問(wèn)題提出的t s p - d p s o 算法 關(guān)于粒子群算法的改進(jìn)大部分都是圍繞粒子群收斂性和多樣性而提出的但是 他們?cè)诟纳扑惴ǖ耐瑫r(shí)也增加了算法的復(fù)雜性不同的學(xué)者根據(jù)不同的情況提出了不 同的改進(jìn)方法或應(yīng)用到了不同的領(lǐng)域現(xiàn)把具有代表性的方法列表如表2 - 1