xx大學
智慧型優化演算法課內實驗報告書
非線性規劃問題的粒子群演算法
1.1 背景介紹
1.1.1 非線性規劃簡介
具有非線性約束條件或目標函式的數學規劃，是運籌學的乙個重要的分支，，目標函式和約束條件都是線性函式的情形則屬於線性規劃。
非線性規劃是20世紀50年代才開始形成的一門新興學科。2023年h.w庫恩和a.
w塔克發表的關於最優性條件的**是非線性規劃正式誕生的乙個重要標誌。在50年代可得出了可分離規劃和二次規劃的n種解法，它們大都是以g.b.
丹齊克提出的解線性規劃的單純形法為基礎的。50年代末到60年代末出現了許多解非線性規劃問題的有效的演算法，70年代又得到進一步的發展。非線性規劃在工程、管理、經濟、科研、軍事等方面都有廣泛的應用，為最優設計提供了有力的工具。
非線性規劃問題廣發存在於科學與工程領域，是一模擬較難以解決的優化問題，沒有普遍使用的解法。傳統的求解該問題的方法（如罰函式，可行方向法，以及變尺度法等）是基於梯度的方法所以目標函式與約束式必須是可微的，並且這些方法只能保證求的區域性最優解。
1.1.2 粒子群演算法簡介
粒子群演算法（particle swarm optimization，pso）的基本概念源於對於鳥群捕食行為的簡化社會模型的模擬，2023年由kenndy和eberhart等人提出，它同遺傳演算法類似，通過個體間的協作和競爭實現全域性搜尋系統初始化為一組隨機解，稱之為粒子。通過粒子在搜尋空間的飛行完成尋優，在數學公式中即為迭代，它沒有遺傳演算法的交叉及變異運算元，而是粒子在解空間追隨最優的粒子進行搜尋。
pso演算法的改進主要在引數選擇、拓撲結構以及與其他優化演算法相融合方面。據此當前典型的改進演算法有：自適應pso演算法、模糊pso演算法、雜交pso演算法、混合粒子演算法（hpso）和離散pso演算法等等。
其中自適應和模糊pso演算法是eberhartshi研究了慣性因子ω對優化效能的影響，發現較大的ω值有利於跳出區域性極小點，較小的ω值有利於演算法的收斂。自適應pso演算法通過線性地減少ω值動態的調整引數ω，而模糊pso演算法則在此基礎上利用模糊規則動態調整引數ω的值，即構造乙個2輸入、1輸出的模糊推理機來動態地修改慣性因子ω。雜交和混合粒子群演算法（hpso）是受遺傳演算法、自然選擇機制的啟示，將遺傳運算元與基本pso相結合而得。
雜交pso在基本pso中引入了雜交運算元，兩者均取得了滿意的結果，改善了演算法的效能。
基本pso演算法是求解連續函式優化的有力工具，但對離散問題卻無能為力。因此kenndy和eberhart發展了離散pso演算法，用於解決組合優化問題等。在一定程度上完善發展了基本pso演算法，並將其應用於旅行商問題（tsp）的求解，取得了較好的結果。
目前pso已經廣泛應用於函式優化、神經網路訓練、模糊系統控制以及其它遺傳演算法的應用領域。最初應用到神經網路訓練上，在隨後的應用中pso又可以用來確定神經網路的結構。一般說來，pso比較有潛在的應用包括系統設計、多目標優化、分類、模式識別、排程、訊號處理、決策、機械人應用等。
其中具體應用例項是非線性規劃的粒子群演算法。總之，pso演算法的應用十分廣泛，它有著比較好的發展前景，值得做進一步的研究。
4 基本粒子群演算法
4.1 粒子群演算法簡介
粒子群演算法是乙個非常簡單的演算法，且能夠有效的優化各種函式。從某種程度上說，此演算法介於遺傳演算法和進化規劃之間。此演算法非常依賴於隨機的過程，這也是和進化規劃的相識之處，此演算法中朝全域性最優和區域性最優靠近的調整非常的類似於遺傳演算法中的交叉運算元。
此演算法還是用了適應值的概念，這是所有進化計算方法所共有的特徵。
在粒子群演算法中，每個個體稱為乙個「粒子」，其實每個粒子代表著乙個潛在的解。例如，在乙個d維的目標搜尋空間中，每個粒子看成是空間內的乙個點。設群體由m個粒子構成。
m也被稱為群體規模，過大的m會影響演算法的運算速度和收斂性。
pso演算法通常的數學描述為：設在乙個d維空間中，由m個粒子組成的種群，其中第i個粒子位置為，其速度為。它的個體極值為，種群的全域性極值為，按照追隨當前最優例子的原理，粒子將按(4.
1)、(4.2)式改變自己的速度和位置。
4.1)
4.2)式中j=1,2,…,d，i=1,2,…m，m為種群規模，t為當前進化代數，為分布於[0,1]之間的隨機數；為加速常數。從式(4.
1)中可知，每個粒子的速度由三部分組成：第一部分為粒子先前的速度；第二部分為「認知」部分，表示粒子自身的思考；第三部分為「社會」部分，表示粒子間的資訊共享與相互合作。
4.1.3 粒子群演算法的特點
粒子群演算法是一種新興的智慧型優化技術，是群體智慧型中乙個新的分支，它也是對簡單社會系統的模擬。該演算法本質上是一種隨機搜尋演算法，並能以較大的概率收斂於全域性最優解。實踐證明，它適合在動態、多目標優化環境中尋優，與傳統的優化演算法相比較具有更快的計算速度和更好的全域性搜尋能力。
具體特點如下：
（1）粒子群優化演算法是基於群體智慧型理論的優化演算法，通過群體中粒子間的合作與競爭產生的群體智慧型指導優化搜尋。與進化演算法比較，pso是一種更為高效的並行搜尋演算法。
（2）pso與ga有很多共同之處，兩者都是隨機初始化種群，使用適應值來評價個體的優劣程度和進行一定的隨機搜尋。但pso是根據自己的速度來決定搜尋，沒有ga的明顯的交叉和變異。與進化演算法比較，pso保留了基於種群的全域性搜尋策略，但是其採用的速度-位移模型操作簡單，避免了複雜的遺傳操作。
（3）pso有良好的機制來有效地平衡搜尋過程的多樣性和方向性。
（4）ga中由於染色體共享資訊，故整個種群較均勻地向最優區域移動。在pso中gbest將資訊傳遞給其他粒子，是單向的資訊流動。多數情況下，所有的粒子可能更快地收斂於最優解。
（5）pso特有的記憶使其可以動態地跟蹤當前的搜尋情況並調整其搜尋策略。
（6）由於每個粒子在演算法結束時仍然保持著其個體極值。因此，若將pso用於排程和決策問題時可以給出多種有意義的選擇方案。而基本遺傳演算法在結束時，只能得到最後一代個體的資訊，前面迭代的資訊沒有保留。
（7）即使同時使用連續變數和離散變數，對位移和速度同時採用和離散的座標軸，在搜尋過程中也並不衝突。所以pso可以很自然、很容易地處理混合整數非線性規劃問題。
（8）pso演算法對種群大小不十分敏感，即種群數目下降時效能下降不是很大。
（9）在收斂的情況下，由於所有的粒子都向最優解的方向飛去，所以粒子趨向同一化（失去了多樣性）使得後期收斂速度明顯變慢，以致演算法收斂到一定精度時無法繼續優化。因此很多學者都致力於提高pso演算法的效能。
4.1.4 粒子群演算法的應用
粒子群演算法提供了一種求解複雜系統優化問題的通用框架，它不依賴於問題的具體領域，對問題的種類有很強的適應性，所以廣泛應用於很多學科。下面是粒子群演算法的一些主要應用領域：
（1）函式優化。函式優化是粒子群演算法的經典應用領域，也是對粒子群演算法進行效能評價的常用算例。
（2）約束優化。隨著問題的增多，約束優化問題的搜尋空間也急劇變換，有時在目前的計算機上用列舉法很難或甚至不可能求出其精確最優解。粒子群演算法是解決這類問題的最佳工具之一。
實踐證明，粒子群演算法對於約束優化中的規劃，離散空間組合問題的求解非常有效。
（3）工程設計問題。工程設計問題在許多情況下所建立起來的數學模型難以精確求解，即使經過一些簡化之後可以進行求解，也會因簡化得太多而使得求解結果與實際相差甚遠。現在粒子群演算法已成為解決複雜排程問題的有效工具，在電路及濾波器設計、神經網路訓練、控制器設計與優化、任務分配等方面粒子群演算法都得到了有效的應用。
（4）電力系統領域。在其領域中有種類多樣的問題，根據目標函式特性和約束型別許多與優化相關的問題需要求解。pso在電力系統方面的應用主要如下：
配電網擴充套件規劃、檢修計畫、機組組合、負荷經濟分配、最優潮流計算與無功優化控制、諧波分析與電容配置、配電網狀態估計、引數辨識、優化設計。隨著粒子群優化理論研究的深入，它還將在電力市場競價交易、投標策略以及電力市場**等領域發揮巨大的應用潛在力。
（5）機械人智慧型控制。機械人是一類複雜的難以精確建模的人工系統，而粒子群演算法可用於此類機械人群搜尋，如機械人的控制與協調，移動機械人路徑規劃。所以機械人智慧型控制理所當然地成為粒子群演算法的乙個重要應用領域。
（6）交通運輸領域。交通方面有車輛路徑問題，在物流配送**領域中要求以最少的車輛數、最小的車輛總行程來完成貨物的派送任務；交通控制，城市交通問題是困擾城市發展、制約城市經濟建設的重要因素。城市交通運輸系統的管理和控制技術進行研究，來為緩解交通擁擠發揮巨大作用。
其中在其解決方法中應用粒子群演算法給解決問題提供了新的，有效的計算方式。
（7）通訊領域。其中包括路由選擇及移動通訊基站布置優化，在順序分碼多重進接連線方式（ds-cdma）通訊系統中使用粒子群演算法，可獲得可移植的有力演算法並提供並行處理能力。比傳統的先前的演算法有了顯著的優越性。
還應用到天線陣列控制和偏振模色散補償等方面。
（8）計算機領域。在計算機中處理各種問題都涉及到大量的資訊計算的方法選擇以減少程式執行的時間，增加系統解決問題的能力，其中包括任務分配問題、資料分類、影象處理等，都得到了粒子群演算法的實際問題解決效率的提高。
（9）生物醫學領域。許多菌體的生長模型即為非線性模型提出了用粒子群演算法解決非線性模型的引數估計問題。還在分子力場的引數設定和蛋白質圖形的發現。
根據粒子群演算法提出的自適應多峰生物測定融合演算法，提高了解決問題的準確性。在醫學方面，如醫學成像上得到的推廣應用等。
非線性規劃理論和演算法
非線性最優化理論與演算法 第一章引論 本章首先給出了一些常見的最優化問題和非線性最優化問題解的定義，並且根據不同的條件對其進行了劃分。接著給出了求解非線性優化問題的方法，如 法等，同時又指出乙個好的數值方法應對一些指標有好的特性，如收斂速度與二次終止性 穩定性等。隨後給出了在非線性最優化問題的理論分...
非線性規劃
習題六6.1 試計算函式f x x12 x1x2 x22 的梯度和hesse矩陣。6.2 試證明下述函式f x 2x1x2x3 4x1x3 2x2x3 x12 x22 x32 2x1 4x2 4x3具有駐點 0，3，1 0，1，1 1，2，0 2，1，1 2，3，1 再應用充分性條件找出其極點。6....
求解非線性規劃
非線性規劃的例項與定義 如果目標函式或約束條件中包含非線性函式，就稱這種規劃問題為非線性規劃問題。一般說來，解非線性規劃要比解線性規劃問題困難得多。而且，也不象線性規劃有單純形法這一通用方法，非線性規劃目前還沒有適於各種問題的一般演算法，各個方法都有自己特定的適用範圍。1.2 線性規劃與非線性規劃的...