【正文】 ............................................................................................ 23 算法測試 ............................................................................................................... 24 結(jié) 論 .............................................................................................................................. 42 致 謝 .............................................................................................................................. 43 參考文獻(xiàn) .............................................................................................................................. 44 附 錄 ................................................................................................ 錯誤 !未定義書簽。在國民經(jīng)濟(jì)各部門和科學(xué)技術(shù)的各個領(lǐng)域中普遍存在著優(yōu)化問題，最優(yōu)化方法廣泛應(yīng)用十工業(yè)、農(nóng)業(yè)、國防、工程、交通、金融、化工、能源、通信等許多領(lǐng)域，如在資源利用、結(jié)構(gòu)設(shè)計、調(diào)度管理、后勤供應(yīng)等許多領(lǐng)域中產(chǎn)生了巨大的經(jīng)濟(jì)效益和社會效益。國內(nèi)外的應(yīng)用實(shí)踐表明，在同樣條件下，優(yōu)化方法對系統(tǒng)效率的提高、能耗的降低、資源的合理利用及經(jīng)濟(jì)效益的提高等均有顯著的效果，而且隨著處理對象規(guī)模的增大，這種效果也更加顯著。 追求最優(yōu)目標(biāo)一直是人類的理想，長期以來，人們對最優(yōu)化問題進(jìn)行不斷的探討和研究。早在 17 世紀(jì)，英國偉大科學(xué)家 Newton 開創(chuàng)了微積分時代，已經(jīng)提出極值問題；后來出現(xiàn) Lagrangian 乘數(shù)法， 1847 年法國數(shù)學(xué)家 Cancky 研究了函數(shù)沿什么方向下降最快的問題； 1949 年前蘇聯(lián)數(shù)學(xué)家 KaHTOPOBNq 提出解決下料問題和運(yùn)輸問題這兩種線性規(guī)劃問題的求解方法。 自 20 世紀(jì) 40 年代以來，由于生產(chǎn)和科學(xué)研究突飛猛進(jìn)地發(fā)展，最優(yōu)化理論和方法日益受到人們的重視，特別是計算機(jī)日益廣泛應(yīng)用，使最優(yōu)化問題的研究不僅成為一種迫切的需要，而且有了求解的有力工具，因此最優(yōu)化理論和算法迅速發(fā)展起來，形成了一門新的應(yīng)用數(shù)學(xué)分支學(xué)科，已經(jīng)滲透到生產(chǎn)、管理、商業(yè)、軍事、決策等各領(lǐng)域。 隨著生產(chǎn)、經(jīng)濟(jì)、技術(shù)的發(fā)展，工程技術(shù) 、管理人才在實(shí)際工作中常常會面臨工程設(shè)計中這樣的一類問題：怎樣選取參數(shù)使得設(shè)計既滿足要求又能降低成本；在資源分配中，怎樣的分配方案既能滿足各方面的基本要求，又能獲得好的經(jīng)濟(jì)效益；在生產(chǎn)計劃安排中，選擇怎樣的計劃方案才能提高產(chǎn)值和利潤；在原料配比問題中，怎樣確定各種成分的比例才能提高質(zhì)量、降低成本；在城建規(guī)劃中，怎樣安排工廠、機(jī)關(guān)、學(xué)校、商店、醫(yī)院、住宅和其他單位的合理布局，才能方便群眾，有利于城市各行各業(yè)的發(fā)展。 許多工程優(yōu)化問題性質(zhì)十 分復(fù)雜，常常需要在復(fù)雜而龐大的搜索空間中尋找最優(yōu)解或者準(zhǔn)最優(yōu)解。 20 世紀(jì) 60 年代以來，生物學(xué)中的進(jìn)化論被廣泛地應(yīng)用于工程技術(shù)、人工智能等領(lǐng)域中，形成了一類新的搜索算法 進(jìn)化算法。雖然這幾種方法在實(shí)現(xiàn)手段上各有特點(diǎn)、互不相同，但它們所遵循的進(jìn)化原則是一致的。因此從實(shí)質(zhì)上來說，進(jìn)化算法是一類具有自適應(yīng)調(diào)節(jié)功能的搜索尋優(yōu)技術(shù)，目前己經(jīng)被廣泛地應(yīng)用到組合 優(yōu)化問題、機(jī)器學(xué)習(xí)、人工生命、自動控制以及動態(tài)系統(tǒng)的故障診斷等領(lǐng)域中。共同進(jìn)化算法正是體現(xiàn)了以上思想，它不僅是對達(dá)爾文的“適者生存、優(yōu)勝劣汰”自然規(guī)律的模擬，同時也體現(xiàn)了自然界中多個物種通過相互合作而共同進(jìn)化的自然規(guī)律。目前共同進(jìn)化算法己經(jīng)成為進(jìn)化算法的一個研究熱點(diǎn)，相關(guān)的理論研究以及應(yīng)用研究已經(jīng)全面展開。 PSO 的概念起源于對鳥群覓食的行為研究，最先是一個用來圖形化仿真鳥群飛行 (Flocking)的算法，可模擬出鳥群尋找谷場(Cornfield)的過程。由于 PSO 算法概念簡單，實(shí)現(xiàn)容易，同時又有深刻的智能背景，既適合科學(xué)研究，又特別適合工程應(yīng)用。目前， PSO 已經(jīng)成為一個研究熱點(diǎn)，被廣泛應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模糊系統(tǒng)控制和決策支持等領(lǐng)域。生命不斷地繁衍生息，產(chǎn)生出具有思維和智能的高級生命體。飛機(jī)、輪船、雷達(dá)、計算機(jī)的問世，都是人類模擬自然的極好例證。 進(jìn)化算法是借鑒生物自然選擇和遺傳機(jī)制的隨機(jī)搜索算法。該算法的核心思想是：生物進(jìn)化過程 (從簡單到復(fù)雜，從低級到高級 )本身是一個自然的，并行發(fā)生的，穩(wěn)健的優(yōu)化過程，其目的就是要適應(yīng)環(huán)境。 進(jìn)化算法通過模擬“優(yōu)勝劣汰，適者生存”的規(guī)律，通過模擬孟德爾的遺傳變異理論在迭代過程中保持已有的結(jié)構(gòu)，同時尋找更好的結(jié)構(gòu)。進(jìn)化算法只需利用目標(biāo)的取值信息而不需要梯度、連續(xù)性、凸性等信息，因而適用于大規(guī)模、高度非線性的不連續(xù)、多峰函數(shù)的優(yōu)化以及無解析表達(dá)式的目標(biāo)函數(shù)優(yōu)化，具有很強(qiáng)的通用性；算法的操作對象是一組個體，而且非單個個體，具有多條搜索軌跡，因而具有隱并行性。如進(jìn)化算法用來發(fā)現(xiàn)細(xì)胞自動機(jī)規(guī)則來完成一定的任務(wù)，基于遺傳信息處理模型的人工生命的合成等。由于進(jìn)化算法是對自然進(jìn)化的一個粗糙簡化，其完整的數(shù)學(xué)基礎(chǔ)有待深入研究，假以時日，隨著不斷地完善，其應(yīng)用會更加廣泛。在這里，自治體是指在一個環(huán)境中具備自身活動能力的一個實(shí)體，其自身力求簡單，通常不必具有高級智能，但是，他們的集群的活動所表現(xiàn)出來的則是一種高級智能才能達(dá)到的活動，我們稱 這種活動為群智能 (Swarm Intelligence)。這些模擬系統(tǒng)利用局部信息從而產(chǎn)生不可預(yù)測的群體行為。昆蟲群體行為的奇妙之處在于：昆蟲的個體都很簡單，但當(dāng)它們一起協(xié)同工作時卻能表現(xiàn)出很復(fù)雜的行為，如蜜蜂能夠建造完美的蜂窩，螞蟻覓食能夠找到最短的路徑，簡單的昆蟲可建造復(fù)雜形狀的巢穴等。顯然，在所有個體活動的完美集成過程中不需要任何的指導(dǎo)。雖然這些交互行為非常簡單，但是他們聚在一起卻能解決一些難題。 群智能的特點(diǎn)是： (1)控制是分布的，不存在中心控制。 (3)個體可 改變環(huán)境 (個體間通過改變環(huán)境，感知環(huán)境變化來彼此間接通訊的方式被稱為“ Stigmergy” )。 在群智能領(lǐng)域主要有兩種基本群智能的算法，蟻群算法 (Ant Colony Optimization)和粒子群優(yōu)化算法 (Particle Swarm Optimization)。蟻群算法已經(jīng)成功 運(yùn)用在很多離散優(yōu)化問題上。 粒子群優(yōu)化算法 (PSO)也是起源于對簡單社會系統(tǒng)的模擬，最初設(shè)想是模擬鳥群覓食的過程，但后來發(fā)現(xiàn) PSO 是一種很好的優(yōu)化工具。設(shè)想這樣一個場景：一群鳥在隨機(jī)搜尋食物。那么找到食物的最優(yōu)策略是什么呢？最簡單有效的就是搜尋目前距離食物最近的鳥的周圍區(qū)域。 在粒子群優(yōu)化算法中，每個優(yōu)化問題的潛在解都是搜索空間中的一只“鳥”，稱之為“粒子”。粒子群優(yōu)化算法初始化為一群隨機(jī)粒子 (隨機(jī)解 )，然后通過迭代找到最優(yōu)解。第一個極值就是粒子本身所找到的最優(yōu)解，這個解被稱為個體極值。另外也可以不用整個種群而只是用其中一部分作為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。 12( ) ( ) ( ) ( )id id id id g d idV V c ra n d P X c ra n d P X?? ? ? ? ? （ 11） 式中 idv 表示第 i 個粒子在第 d 維上的速度； ? 為慣性權(quán)重，控制粒子的每一代速度更新有多少以前的速度保留下來； 1c 和 2c 為調(diào)節(jié) idP 和 gdP 相對重要性的參數(shù)；()rand 為隨機(jī)數(shù)生成函數(shù)。39。由此可見PSO 的基本思想就是每個個體充分利用群體與自身的智能 ,不斷地調(diào)整學(xué)習(xí) ,最終得到滿意解。 粒子群優(yōu)化算法并沒有能給出嚴(yán)格的 數(shù)學(xué)證明，但在實(shí)際應(yīng)用中被證明是有效的。在這種前提下，種群很快就達(dá)到了收斂狀態(tài)，從而能在較少的代數(shù)內(nèi)找到最優(yōu)解。在組合優(yōu)化問題里，是從一個無限集或者可數(shù)無限集里尋找一個對象，典型的是一個整數(shù)，一個集合，一個排列或一個圖。從某種意義上講，組合優(yōu)化問題的研究是從它與連續(xù)優(yōu)化問題之間的分界線上入手的。其圖論描述為：給定圖 G=(V,A)，其中 V 為頂點(diǎn)集， A為各頂點(diǎn)相互連接組成的弧集，已知各頂點(diǎn)間連接距離，要求確定一條長度最短的Hamilton 回路，即遍歷所有頂點(diǎn)一次且僅一次的最短回路。引入決策變量： 1 , i j0 ijij xx???? ???若 旅 行 商 訪 問 城 市 后 訪 問 城 市， 否 則 （ 13） 則 TSP 的目標(biāo)函數(shù)為 nij iji j 1M in Z dx?? ?。對于 N 個城市的 TSP，存在著 ( 1)!/2n? 條可能的路徑。由于對 TSP 及與之具有類似復(fù)雜性的一些其它最優(yōu)化問題現(xiàn)在還沒有有效的算法，人們把這類問題稱為“ NP 完全問題”。 粒子群 優(yōu)化 算法的國內(nèi)外研究現(xiàn)狀 粒子群優(yōu)化算法概念簡單，實(shí)現(xiàn)容易，同時又有深刻的智能背景，既適合科學(xué)研究，又特別適合工程應(yīng)用。目前，其研究現(xiàn)狀大致分為兩個方向：算 法的改進(jìn)，算法的應(yīng)用。因此，迄今已經(jīng)出現(xiàn)了很多對粒子群優(yōu)化算法的改進(jìn)方法。如何利用有效的數(shù)學(xué)工具對算法的收斂性，收斂速度的估計，計算的復(fù)雜性，以及預(yù)防陷入局部最優(yōu)和參數(shù)設(shè)置影響等進(jìn)行分析將是今后的研究熱點(diǎn)之一。 Kennedy 和 Eberhart 的報告說明 PSO 成功用于正確區(qū)分 XOR 問題，包括 13 維搜索空間的函數(shù)優(yōu)化問題。另一個神經(jīng)網(wǎng)絡(luò)訓(xùn)練的例子中 Eberhart 和 Hu 用 PSO 訓(xùn)練神經(jīng)網(wǎng)絡(luò)以正確區(qū)分病人的顫抖行為是普通顫動或是患有帕金森氏癥。 PSO 算法也用來優(yōu)化帶權(quán)神經(jīng)網(wǎng)絡(luò)的連接結(jié)構(gòu)。乘法單元神經(jīng)網(wǎng)絡(luò)是帶誤差函數(shù)的神經(jīng)網(wǎng)絡(luò)，很難訓(xùn)練。 Engelbrecht 和 Ismail 研究了不同優(yōu)化算法訓(xùn)練乘法單元神經(jīng)網(wǎng)絡(luò)的能力，發(fā)現(xiàn)在乘法單元神經(jīng)網(wǎng)絡(luò)的訓(xùn)練問題上， PSO 比其它隨機(jī)搜索算法還要好，如GA 和 LeapFrog 算法。例如用訓(xùn)練神經(jīng)網(wǎng)絡(luò)來評估電池充電的狀態(tài)； PSO 用來優(yōu)化用于促進(jìn)微生物的生長的化學(xué)成分配方，找到的解比之前使用其它優(yōu)化算法發(fā)現(xiàn)的各種解有明顯的改進(jìn)。 另一個與神經(jīng)網(wǎng)絡(luò)訓(xùn)練 有 關(guān)的應(yīng)用是 Fukuyama 和 Yoshida 發(fā)表的論文。在速度更新前，通過簡單離散值來調(diào)整 PSO的更新公式，粒子的位置也是如此。他們使用的是慣性權(quán)值線性遞減的 PSO，結(jié)果表明比原來使用的 RTS 算法效率更高。進(jìn)一步的研究還發(fā)現(xiàn)相同參數(shù)設(shè)置的 PSO 應(yīng)用在不同電力系統(tǒng)問題上獲得了高質(zhì)量的解。此外，充分利用其他進(jìn)化算法以改善微粒群算法存在的不足，也是值得研究 的問題。目前 PSO 的研究尚處于初期，還有許多問題值得做進(jìn)一步的研究。 由于實(shí)際問題的多樣性和復(fù)雜性，盡管目前已經(jīng)有了多種不同版本的 PSO 改進(jìn)算法但這些 PSO 算法不具有通用性，或者參數(shù)的設(shè)置要求使用者具備較高的經(jīng)驗(yàn)，否則難以達(dá)到理想的效果。 如何將 PSO 應(yīng)用于組合優(yōu)化問題也是一個重要的研究方向。如何加快算法的收斂速度和避免早熟收斂問題，一直是大多數(shù)研究者關(guān)注的重點(diǎn)，也是所有隨機(jī)搜索算法共同面臨的兩個主要難題。在避免早熟收斂方面，現(xiàn)有的大量研究涉及如何讓算法跳出局部最優(yōu)點(diǎn)。 粒子群優(yōu)化技術(shù)的應(yīng)用領(lǐng)域己擴(kuò)展到組合優(yōu)化 、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識別、電信 Qos 管理、生物系統(tǒng)建模、流程規(guī)劃、信號處理、機(jī)器人控制、決策支持以及仿真和系統(tǒng)辯識等方面。 第 2章 粒子群優(yōu)化算法 粒子群算法 (PSO)是 1995 由 Kennedy 和 Eberhart[12]首先提出的一類基于群智能的演化計算方法。通過對類似生物群體的行為的研究，發(fā)現(xiàn)在生物群體中存在著個體與個體、個體與群體間的相互作用、相互影響的行為，這種行為體現(xiàn)的是一種存在于生物群體中的信息共享的機(jī)制。 PSO 就是對這種社會行為的模擬，即利用信息共享機(jī)制，使得個體間可以相互借鑒經(jīng)驗(yàn)，從而促進(jìn)整個群體的發(fā)展。但 PSO 沒有 GA 的“選擇”、“交叉”、“變異”算子，編碼方式也較 GA 簡單。在 函數(shù)優(yōu)化 [14]、神經(jīng)網(wǎng)絡(luò)訓(xùn)練 [15]、系統(tǒng)控制 [10]等領(lǐng)域得到廣泛應(yīng)用。 粒子群算法的原理 粒子群優(yōu)化算法的基本概念源于對鳥群覓食行為的研究。在 這個區(qū)域里只有一塊食物。但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn)。 PSO 從這種模型中得到啟示并用于解決優(yōu)化問題。起初Kennedy 和 Eberhart 只是設(shè)想模擬鳥群覓食的過程，但后來的研究中發(fā)現(xiàn) PSO 是一種很好的優(yōu)化工具。所不同的是 PSO 是將每個個體看作是在 N 維搜索空間中的沒有重量和體積的微粒，并在搜索空間中以一定的速度飛行。 PSO 首先生成初始種群，即在可行解空間中隨機(jī)初始化一群粒子，每個粒子都為優(yōu)化問題的一個可行解，并由目標(biāo)函數(shù)為之確定一個適應(yīng)值。通常粒子