畢業(yè)論文-非線性規(guī)劃問題的粒子群算法（定稿）

西安科技大學畢業(yè)設計（論文）PAGEPAGEI西安科技大學學士學位論文題目：非線性規(guī)劃問題的粒子群算法作者：摘要優(yōu)化技術是一種以數(shù)學為基礎，用于求解各種組合優(yōu)化問題的應用技術。最優(yōu)化問題是人們在工程技術、科學研究、和經(jīng)濟管理等諸多領域中經(jīng)常碰到的問題，它是指在滿足一定的約束條件下，尋找一組參數(shù)值，使目標函數(shù)達到最大或最小。最優(yōu)化問題根據(jù)其目標函數(shù)、約束條件的性質以及優(yōu)化變量的取值范圍可以分為許多類型，例如：根據(jù)目標函數(shù)和約束條件是否均為線性表達式，把最優(yōu)化問題劃分為線性規(guī)劃問題和非線性規(guī)劃問題。針對不同的最優(yōu)化問題，提出了許多不同的優(yōu)化方法，如牛頓法、共軛梯度法、Polar-Ribiere法、拉格朗日乘子法等。這些優(yōu)化算法能很好地找到問題的局部最優(yōu)點，是成熟的局部優(yōu)化算法。但是隨著人類生存空間的擴大以及認識與改造世界范圍的拓展，人們發(fā)現(xiàn)由于問題的復雜性、約束性、非線性、建模困難等特點，解析性優(yōu)化算法已不能滿足人們的要求，需要尋找一種適合于大規(guī)模并行且具有智能特征的優(yōu)化算法?，F(xiàn)代進化類方法如人工神經(jīng)網(wǎng)絡、遺傳算法、禁忌搜索法、模擬退火法和蟻群算法等在解決大規(guī)模的問題時體現(xiàn)出強大的潛力，它們可以在合理的時間限制內逼近優(yōu)化問題的較好可行解。其中，遺傳算法和蟻群算法被稱為智能優(yōu)化算法，其基本思想是通過模擬自然界生物的行為來構造隨機優(yōu)化算法。近年來，另一種智能優(yōu)化算法—粒子群算法（particleswarmoptimization，簡稱PSO）越來越受到學者的關注。粒子群算法是美國社會心理學家JamesKennedy和電氣工程師RussellEberhart在1995年共同提出的，它是受到鳥群社會行為的啟發(fā)并利用了生物學家FrankHeppner的生物群體模型而提出的。它用無質量無體積的粒子作為個體，并為每個粒子規(guī)定簡單的社會行為規(guī)則，通過種群間個體協(xié)作來實現(xiàn)對問題最優(yōu)解的搜索。由于算法收斂速度快，設置參數(shù)少，容易實現(xiàn)，能有效地解決復雜優(yōu)化問題，在函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡訓練、圖解處理、模式識別以及一些工程領域都得到了廣泛的應用。關鍵字：非線性規(guī)劃；粒子群算法；智能算法ABSTRACTOptimizationtechnologyisbasedonmathematicsandcansolvevariouscombinatorialoptimizationproblems.Manyproblemspossessasetofparameterstobeoptimized,especiallyinthefieldsofengineeringtechnology,scientificresearchandeconomicmanagement.Optimizationistolookforasetofparametersindefiniterestrictionwiththeaimofminimizingormaximizingtheobjectivefunction.Accordingtoqualityofobjectivefunctionandrestrictconditionandscopeofvariable,optimizationproblemcanbedividedintolotsoftypes.Forexample,ifobjectivefunctionandrestrictconditionarebothlinealexpression,thisproblembelongstolinearprogrammingproblem,ifnot,itbelongstononlinearprogrammingproblem.Differentmethodshavebeenpresentedtosovledifferentkindsofproblems,suchasNewton'smethod,conjugategradientmethod,Polar-Ribiere'smethod,LagrangeMultiplierMethodetc.Thesemethodscannicelyfindlocalextremeindifferentproblems.However,withthedevelopmentofhumanlivingspaceandthescopeofunderstandingandtransformingtheworld,peoplehavefoundthatbecauseofthecomplexity,binding,nonlinear,modelingdifficultiescharacteristic,itisnoteasytofindasatisfyinganalyticsolutions.It’snecessarytofindaoptimizationalgorithmsuitingforlarge-scaleparallelOperationwithsmartfeatures.Modernevolutionmethodssuchasartificialneuralnetworks,geneticalgorithms,Taboosearchmethod,simulatedannealing,andantcolonyalgorithmetc.,reflectastrongpotentialinsolvinglarge-scaleproblems.Theycanapproximatethebetterfeasiblesolutionfortheoptimizationproblemwithinareasonableperiodoftime.TheGeneticAlgorithmandantcolonyalgorithmareknownasintelligentoptimizationalgorithm,andtheirbasicideaistoconstructstochasticoptimizationalgorithmsbysimulatingthebehaviorofthenaturalworld.Inrecentyears,anotherkindofintelligentoptimizationalgorithm–PSOalgorithm(particleswarmoptimization,orPSO)increasinglyaccessestotheconcernsofscholars.PSOalgorithmisproposedbyAmericansocialpsychologistJamesKennedyandelectricalengineerRussellEberhartin1995,anditisinspiredbybirdpopulations'socialbehaviorandusesthebiologicalgroupmodelofbiologistFrankHeppner.Itusesparticleswithoutqualityandvolumesindividuals,providessimplesocialrulesofconductforeachparticle,andsearchestheoptimalsolutiontotheproblemthroughindividualcollaborationamongpopulations.Thealgorithmconvergesfast,needinglessparameters.Alsoitiseasilyachieved,andcaneffectivelysolvecomplexoptimizationproblems.Ithasbeenwidelyusedinfunctionoptimization,neuralnetworktraining,graphicprocessing,patternrecognitionaswellassomeengineeringfields.KeyWords:NonlinearProgramming;PSO(ParticleSwarmoptimization);Intelligentalgorithm目錄1概論 11.1背景介紹 11.1.1非線性規(guī)劃簡介 11.1.2粒子群算法簡介 11.2研究內容 22非線性規(guī)劃的分析 32.1非線性規(guī)劃的概念 32.2非線性規(guī)劃的應用 32.3非線性規(guī)劃相關的概念 42.4凸函數(shù)與凸規(guī)劃 42.4.1凸函數(shù)定義 42.4.2凸規(guī)劃 53基本的非線性規(guī)劃算法 53.1罰函數(shù)概述 53.2無約束非線性規(guī)劃求解算法描述 73.2.1最優(yōu)速下降法 73.2.2共軛梯度法 83.2.3牛頓法 93.3算法優(yōu)缺點性能分析 104基本粒子群算法 114.1粒子群算法概述 114.1.1粒子群算法發(fā)展 114.1.2粒子群算法簡介 124.1.3粒子群算法的特點 124.1.4粒子群算法的應用 134.2基本粒子群算法 144.2.1基本遺傳算法的構成要素 144.2.2基本遺傳算法的形式化定義 154.2.3基本遺傳算法描述 154.3粒子群算法的關鍵 164.3.1粒子狀態(tài)向量形式的確定 164.3.2適應度函數(shù)的建立 164.3.3粒子多樣性的保證 174.3.4粒子群算法的運行參數(shù)設置 175基于粒子群算法的非線性規(guī)劃問題的求解設計 185.1實用粒子群算法設計 185.1.1編碼方法設計 185.1.2適應度函數(shù)設計 185.1.3基于約束適應度優(yōu)先排序的約束條件處理方法 195.1.4動態(tài)鄰域算子 195.1.5可變慣性權重和最大速度 205.1.6粒子群算法運行參數(shù)設計 205.2非線性規(guī)劃的粒子群算法程序設計 215.2.1算法過程描述 215.2.2粒子群算法程序流程圖 216基于粒子群算法的非線性規(guī)劃求解的性能分析 306.1概述 306.2粒子群算法參數(shù)設置效果比較 306.3時間復雜度 336.3.1理論時間復雜度 336.3.2樣本數(shù)對算法運行時間的影響 336.4算法的發(fā)展與展望 367總結 37致謝 38參考文獻 391概論1.1背景介紹1.1.1非線性規(guī)劃簡介具有非線性約束條件或目標函數(shù)的數(shù)學規(guī)劃，是運籌學的一個重要的分支，非線性規(guī)劃研究一個n元實函數(shù)在一組等式或不等式的約束條件下的機制問題且目標函數(shù)和約束條件至少有一個是未知量的非線性函數(shù)，目標函數(shù)和約束條件都是線性函數(shù)的情形則屬于線性規(guī)劃。非線性規(guī)劃是20世紀50年代才開始形成的一門新興學科。1951年H.W庫恩和A.W塔克發(fā)表的關于最優(yōu)性條件的論文是非線性規(guī)劃正式誕生的一個重要標志。在50年代可得出了可分離規(guī)劃和二次規(guī)劃的n種解法，它們大都是以G.B.丹齊克提出的解線性規(guī)劃的單純形法為基礎的。50年代末到60年代末出現(xiàn)了許多解非線性規(guī)劃問題的有效的算法，70年代又得到進一步的發(fā)展。非線性規(guī)劃在工程、管理、經(jīng)濟、科研、軍事等方面都有廣泛的應用，為最優(yōu)設計提供了有力的工具。非線性規(guī)劃問題廣發(fā)存在于科學與工程領域，是一類比較難以解決的優(yōu)化問題，沒有普遍使用的解法。傳統(tǒng)的求解該問題的方法（如罰函數(shù)，可行方向法，以及變尺度法等）是基于梯度的方法所以目標函數(shù)與約束式必須是可微的，并且這些方法只能保證求的局部最優(yōu)解。1.1.2粒子群算法簡介粒子群算法（ParticleSwarmoptimization，PSO）的基本概念源于對于鳥群捕食行為的簡化社會模型的模擬，1995年由Kenndy和Eberhart等人提出，它同遺傳算法類似，通過個體間的協(xié)作和競爭實現(xiàn)全局搜索系統(tǒng)初始化為一組隨機解，稱之為粒子。通過粒子在搜索空間的飛行完成尋優(yōu)，在數(shù)學公式中即為迭代，它沒有遺傳算法的交叉及變異算子，而是粒子在解空間追隨最優(yōu)的粒子進行搜索。PSO算法的改進主要在參數(shù)選擇、拓撲結構以及與其他優(yōu)化算法相融合方面。據(jù)此當前典型的改進算法有：自適應PSO算法、模糊PSO算法、雜交PSO算法、混合粒子算法（HPSO）和離散PSO算法等等。其中自適應和模糊PSO算法是EberhartShi研究了慣性因子ω對優(yōu)化性能的影響，發(fā)現(xiàn)較大的ω值有利于跳出局部極小點，較小的ω值有利于算法的收斂。自適應PSO算法通過線性地減少ω值動態(tài)的調整參數(shù)ω，而模糊PSO算法則在此基礎上利用模糊規(guī)則動態(tài)調整參數(shù)ω的值，即構造一個2輸入、1輸出的模糊推理機來動態(tài)地修改慣性因子ω。雜交和混合粒子群算法（HPSO）是受遺傳算法、自然選擇機制的啟示，將遺傳算子與基本PSO相結合而得。雜交PSO在基本PSO中引入了雜交算子，兩者均取得了滿意的結果，改善了算法的性能?；綪SO算法是求解連續(xù)函數(shù)優(yōu)化的有力工具，但對離散問題卻無能為力。因此Kenndy和Eberhart發(fā)展了離散PSO算法，用于解決組合優(yōu)化問題等。在一定程度上完善發(fā)展了基本PSO算法，并將其應用于旅行商問題（TSP）的求解，取得了較好的結果。目前PSO已經(jīng)廣泛應用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡訓練、模糊系統(tǒng)控制以及其它遺傳算法的應用領域。最初應用到神經(jīng)網(wǎng)絡訓練上，在隨后的應用中PSO又可以用來確定神經(jīng)網(wǎng)絡的結構。一般說來，PSO比較有潛在的應用包括系統(tǒng)設計、多目標優(yōu)化、分類、模式識別、調度、信號處理、決策、機器人應用等。其中具體應用實例是非線性規(guī)劃的粒子群算法。總之，PSO算法的應用十分廣泛，它有著比較好的發(fā)展前景，值得做進一步的研究。1.2研究內容本課題主要研究非線性規(guī)劃的粒子群算法分析與實現(xiàn)。將非線性規(guī)劃的問題使用粒子群最優(yōu)算法求解其最優(yōu)解，在一般求解非線性規(guī)劃的問題時都與選擇的算法有很大的關系，在選擇變尺度法和梯度法時都必須考慮非線性規(guī)劃函數(shù)的可微性，在初始值選擇上也給函數(shù)的局部收斂帶來局部的最優(yōu)，不能達到全局最優(yōu)解，這樣就給一些其它非線性規(guī)劃問題帶來很大的困難。粒子群算法（PSO）是一種新興的優(yōu)化技術，通過粒子追隨自己找到最好解和整個群的最優(yōu)解來完成優(yōu)化。該算法簡單易實現(xiàn)，可調參數(shù)少是解決非線性規(guī)劃問題的比較理想的算法。題目以粒子群算法為工具，設計基于非線性規(guī)劃問題的應用，并對求解過程總結，比較其它算法的優(yōu)越性和其存在的問題。2非線性規(guī)劃分析2.1非線性規(guī)劃的概念如果目標函數(shù)或約束條件中至少有一個是非線性函數(shù)時的最優(yōu)化問題就叫做非線性規(guī)劃問題。其可分為兩大類問題有約束問題與無約束問題，它們在處理方法上有明顯的不同。實際問題中大多數(shù)都是有約束條件的問題。球接待有約束條件的問題比起無約束問題要困難得多，也復雜得多。在每次迭代時，不僅要使目標函數(shù)值有所下降，而且要使迭代點都落在可行域內。與線性規(guī)劃一樣，非線性規(guī)劃也是運籌學的一個重要的分支，于20世紀50年代開始逐步形成，到20世紀70年代開始處于興旺發(fā)展時期。隨著計算機技術的日益發(fā)展，很多領域越來越重視這門學科，應用非線性規(guī)劃方法進行設計、管理等，非線性規(guī)劃理論自身也得到了進一步的發(fā)展。關于求解非線性規(guī)劃的迭代方法有二分法、簡單迭代法、牛頓迭代法與擬牛頓迭代法、同論延拓法、單純形法等。以上方法都有一定的局限性。2.2非線性規(guī)劃的應用非線性規(guī)劃在軍事、經(jīng)濟、管理、生產過程自動化、工程設計和產品優(yōu)化設計等方面都有著重要的應用。但非線性規(guī)劃的研究目前還不成熟，有許多問題需要進一步完善。非線性規(guī)劃不像線性規(guī)劃有統(tǒng)一的算法，對于不同的問題需要用不同的算法處理，現(xiàn)階段各種算法都有一定的局限性，只有對各種算法加以改正，才能有效地解決人們在日常的生產、生活中遇到的優(yōu)化問題，做出最優(yōu)的決策。一般來說，解非線性規(guī)劃問題要比求解線性規(guī)劃的問題困難得多，而且也不想線性規(guī)劃那樣有統(tǒng)一的數(shù)學模型及如單純形法這一通用的解法，非線性規(guī)劃的各種算法大都有自己特定的適應范圍。都有一定的局限性，到目前為止還沒有適合于各種非線性規(guī)劃問題的一般算法。這正是需要人么進一步研究的課題。非線性規(guī)劃在工程、管理、經(jīng)濟、科研、軍事等方面都有廣泛的應用，為最優(yōu)設計提供了有力的工具。例如：如何在有人力、物力、財力要求的前提下合理安排產品生產，以取得最高的利潤；如何設計某種產品，在滿足規(guī)格、性能要求的前提下，達到最低的成本；如何確定一個自動控制系統(tǒng)的某些參數(shù)，使系統(tǒng)的工作狀態(tài)最佳；如何安排庫存儲量，既能保證供應，又使儲存費用最低；如何分配一個動力系統(tǒng)中各電站的負荷，在保證一定指標要求的前提下，使總耗費量最??；如何組織貨源，既能滿足顧客需要，又使資金周轉最快等對于靜態(tài)的最優(yōu)化問題，當目標函數(shù)或約束條件出現(xiàn)未知量的非線性函數(shù)，且不便于線性化，或勉強線性化后會招致較大誤差時，就可以應用非線性規(guī)劃的方法去處理。2.3非線性規(guī)劃相關的概念定義：如果目標函數(shù)或約束條件中至少有一個是非線性規(guī)劃函數(shù)時的最優(yōu)化問題就叫做非線性規(guī)劃問題。一般形式：minSKIPIF1<0SKIPIF1<0SKIPIF1<0（2-1）其中SKIPIF1<0是定義在SKIPIF1<0上的實值函數(shù)，簡記：SKIPIF1<0其它情況：求目標函數(shù)的最大值或約束條件為小于等于零的情況，都可通過取其相反數(shù)化為上述一般形式。定義1把滿足問題(2-1)中條件的解SKIPIF1<0稱為可行解（或可行點），所有可行點的集合稱為可行集（或可行域）．記為D．即SKIPIF1<0問題(2-1)可簡記為SKIPIF1<0定義2對于問題(2-1)，設SKIPIF1<0，若存在SKIPIF1<0，使得對于一切SKIPIF1<0且‖SKIPIF1<0‖<SKIPIF1<0，都有SKIPIF1<0則稱SKIPIF1<0是SKIPIF1<0在D上的局部極小值點（局部最優(yōu)解）。特別地當SKIPIF1<0時，若SKIPIF1<0，則稱SKIPIF1<0在D上的嚴格局部極小值點（嚴格局部最優(yōu)解）。定義3對于問題(2-1),設SKIPIF1<0，對于任意的SKIPIF1<0，都有SKIPIF1<0則稱SKIPIF1<0是SKIPIF1<0在D上的全局極小值點（全局最優(yōu)解）。特別地當SKIPIF1<0時，若SKIPIF1<0，則稱SKIPIF1<0是SKIPIF1<0上的嚴格全局極小值點（嚴格全局最優(yōu)解）。2.4凸函數(shù)與凸規(guī)劃在最優(yōu)化理論中，凸集與凸函數(shù)占有非常重要的地位。通過對凸函數(shù)的學習了解求解非線性規(guī)劃的基礎知識。2.4.1凸函數(shù)定義設SKIPIF1<0為凸集，SKIPIF1<0是定義在凸集S上的函數(shù)，如果SKIPIF1<0恒有SKIPIF1<0，則稱SKIPIF1<0是凸集S上的凸函數(shù)，如果上式取嚴格不等式，則稱SKIPIF1<0是凸集S上的嚴格凸函數(shù)，將上式的不等號反向，即可得到凹函數(shù)和嚴格凹函數(shù)的定義。凸函數(shù)的性質如下：設SKIPIF1<0是定義在凸集S上的凸函數(shù)，則SKIPIF1<0，以及SKIPIF1<0，恒有SKIPIF1<0。設SKIPIF1<0是定義在凸集S上的凸函數(shù)，如果SKIPIF1<0，那么SKIPIF1<0仍是凸集S上的凸函數(shù)。設SKIPIF1<0是定義在凸集S上的凸函數(shù)，那么對任意實數(shù)SKIPIF1<0，集合SKIPIF1<0是S的凸子集，稱為水平集。凸函數(shù)的判定：設n元函數(shù)SKIPIF1<0可微，稱列向量SKIPIF1<0為f在X處的梯度，記作SKIPIF1<0。若SKIPIF1<0二階連續(xù)可微，則稱f的所有二階偏導數(shù)構成的n階方陣SKIPIF1<0為f在X處的二階導數(shù)矩陣或稱海賽（Hessian）矩陣，記作SKIPIF1<0或SKIPIF1<0。f在X處沿梯度方向有最快的上升趨勢。一階可微的函數(shù)SKIPIF1<0是凸集S上的凸函數(shù)的充分必要條件是：SKIPIF1<0，恒有SKIPIF1<0類似地，SKIPIF1<0是在凸集S上的嚴格凸函數(shù)的充分必要條件是上式不等號嚴格成立。二階連續(xù)可微的函數(shù)SKIPIF1<0是凸集S上的凸函數(shù)的充分必要條件是：SKIPIF1<0為半正定矩陣。類似地，SKIPIF1<0是凸集S上的嚴格凸函數(shù)的充分必要條件是SKIPIF1<0為正定矩陣。2.4.2凸規(guī)劃若SKIPIF1<0是凸函數(shù)，SKIPIF1<0是凹函數(shù)（即所有SKIPIF1<0全為凸函數(shù)），則稱這種規(guī)劃問題為凸規(guī)劃。顯然，線性規(guī)劃是一種凸規(guī)劃，其性質有如以下：（1）可行解集為凸集。（2）最優(yōu)解集為凸集（假定最優(yōu)解存在）。（3）中心任何局部最優(yōu)解也是其全局最優(yōu)解。（4）若目標函數(shù)為嚴格凸函數(shù)，且最優(yōu)解存在，則其最優(yōu)解必唯一。3基本非線性規(guī)劃算法3.1罰函數(shù)法概述罰函數(shù)法基本思想是通過構造罰函數(shù)把約束問題轉化為一系列無約束最優(yōu)化問題，進而用無約束最優(yōu)化方法去求解。這類方法稱為序列無約束最小化方法，簡稱為SUMT法。其一為SUMT外點法，其二為SUMT內點法。SUMT外點法其基本思想是：利用目標函數(shù)和約束條件組成輔助函數(shù)對一般的非線性規(guī)劃：minSKIPIF1<0SKIPIF1<0(3.1)可設：SKIPIF1<0(3.2)將問題(3.1)轉化為無約束問題：SKIPIF1<0(3.3)其中T(X,M)稱為罰函數(shù)，M稱為罰因子，帶M的項稱為罰項，這里的罰函數(shù)只對不滿足約束條件的點實行懲罰：當SKIPIF1<0時，滿足各SKIPIF1<0故罰項=0，不受懲罰，當SKIPIF1<0時，必SKIPIF1<0或SKIPIF1<0約束條件，故罰項>0，要受懲罰。SUMT外點法（罰函數(shù)法）的迭代步驟：1、任意給定初始點SKIPIF1<0，取SKIPIF1<0，給定允許誤差SKIPIF1<0，令k=1；2、求無約束極值問題SKIPIF1<0的最優(yōu)解，設為SKIPIF1<0，即SKIPIF1<0；3、若存在SKIPIF1<0，使SKIPIF1<0，則取SKIPIF1<0令k=k+1返回(3.2)，否則，停止迭代。取得最優(yōu)解SKIPIF1<0。計算時也可將收斂性判別準則SKIPIF1<0改為SKIPIF1<0。罰函數(shù)法的缺點是：每個近似最優(yōu)解SKIPIF1<0往往不是容許解，而只能近似滿足約束，在實際問題中這種結果可能不能使用；在解一系列無約束問題中，計算量太大，特別是隨著SKIPIF1<0的增大，可能導致錯誤。SUMT內點法（障礙函數(shù)法）其基本思想是：迭代過程中總是從可行域內的出發(fā)，并保持在可行域內進行搜索。該方法適用于只有不等式約束的問題?？紤]問題：SKIPIF1<0(3.4)設集合SKIPIF1<0，SKIPIF1<0是可行域中所有嚴格內點的集合。構造障礙函數(shù)SKIPIF1<0或SKIPIF1<0其中稱SKIPIF1<0或SKIPIF1<0為障礙項，r為障礙因子。這樣問題(3.4)就轉化為求一系列極值問題：SKIPIF1<0得SKIPIF1<0。內點法的迭代步驟：1、給定允許誤差SKIPIF1<0，取SKIPIF1<0；2、求出約束集合D的一個內點SKIPIF1<0，令k=1；3、以SKIPIF1<0為初始點，求解SKIPIF1<0，其中SKIPIF1<0的最優(yōu)解，設為SKIPIF1<0；4、檢驗是否滿足SKIPIF1<0或SKIPIF1<0，滿足，停止迭代，SKIPIF1<0；否則取SKIPIF1<0，令k=k+1，返回3。3.2無約束非線性規(guī)劃求解方法無約束非線性規(guī)劃問題的求解方法分為解析法和直接法兩類。解析法需要計算函數(shù)的梯度，直接法僅通過比較目標函數(shù)值的大小來移動迭代點。其中最速下降法、共軛梯度法、牛頓法、變尺度法等解析方法和步長加速法、旋轉方法、方向加速法等直接方法。一般來說，無約束非線性規(guī)劃問題的求解是通過一系列一維搜索來實現(xiàn)。因此，如何選擇搜索方向是求解無約束非線性規(guī)劃問題的核心問題，搜索方向的不同選擇，形成不同的求解方法。3.2.1最優(yōu)速下降法最速下降法是由法國著名數(shù)學家Cauchy于1847年首次提出。該方法將目標函數(shù)SKIPIF1<0在SKIPIF1<0的負梯度方向SKIPIF1<0作為下降迭代法的迭代公式SKIPIF1<0中的SKIPIF1<0，并通過求解SKIPIF1<0，確定最佳步長SKIPIF1<0。若SKIPIF1<0具有二階連續(xù)偏導，在SKIPIF1<0處作SKIPIF1<0的二階泰勒展開式SKIPIF1<0對SKIPIF1<0求導令其等于零，得最佳步長SKIPIF1<0。最速下降法的計算步驟如下：（1）給定初始點SKIPIF1<0，允許誤差SKIPIF1<0，置k=0（2）計算搜索方向SKIPIF1<0。（3）若SKIPIF1<0，則停止計算，得近似極小點SKIPIF1<0；否則，確定最佳步長SKIPIF1<0，轉第（4）步（4）令SKIPIF1<0，置k=k+1，轉第（2）步。3.2.2共軛梯度法共軛梯度法最初由Hesteness和Stiefel于1952年為求解非線性方程組而提出，后來成為求解無約束非線性規(guī)劃問題的一種重要的方法。其基本思想是：把共軛性與最速下降方法相結合，利用已知點處的梯度構造一組共軛方向，并沿這組方向進行搜索，求出目標函數(shù)的極小點。該方法對于正定二次函數(shù)能在有限步內達到極小點，即該算法具有二次終結性。對于問題SKIPIF1<0，由于SKIPIF1<0，可推出其唯一極小點SKIPIF1<0。如果已知某共軛向量組SKIPIF1<0，由SKIPIF1<0（3.1）可知，問題SKIPIF1<0的極小點SKIPIF1<0可通過下列算法得到SKIPIF1<0（3.2）該算法稱為共軛方向法。它要求搜索方向SKIPIF1<0必須共軛，確定各近似極小點時必須按最佳一維搜索進行。共軛梯度法是共軛方向的一種，它的方向是利用一維搜索所得極小點處的梯度生成的。由于SKIPIF1<0，故SKIPIF1<0，又因為SKIPIF1<0故SKIPIF1<0。任取初始近似點SKIPIF1<0，并取初始搜索方向的負梯度方向，即SKIPIF1<0，沿射線SKIPIF1<0進行一維搜索，得到SKIPIF1<0，其中SKIPIF1<0滿足SKIPIF1<0，計算SKIPIF1<0，由SKIPIF1<0，從而SKIPIF1<0和SKIPIF1<0正交，構成正交系，在由它構成的子空間中搜尋SKIPIF1<0，令SKIPIF1<0，SKIPIF1<0為待定系數(shù)，欲使SKIPIF1<0和SKIPIF1<0為A共軛，從而可求的SKIPIF1<0。令SKIPIF1<0由此可得SKIPIF1<0。綜合以上步驟可以得到共軛梯度法德一般計算公式如下：SKIPIF1<0(3.3)其中SKIPIF1<0為初始近似，SKIPIF1<0。對于正定二次函數(shù)，從理論上說，進行n次迭代即可達到極小點。但是，在實際計算中，由于數(shù)據(jù)的輸入以及計算誤差的積累，往往做不到這一點。此外，由于n維問題的共軛方向最多只有n個，在n步以后繼續(xù)加上進行是沒有意義的。因此，在實際應用時，如迭代到n步還不收斂，就將SKIPIF1<0作為新的初始近似，重新開始迭代。共軛梯度法的計算步驟如下：（1）選擇初始近似SKIPIF1<0，給出允許誤差SKIPIF1<0。（2）計算SKIPIF1<0，置k=0。（3）用式(3.3)計算SKIPIF1<0。（4）若k<n-1，則置k=k+1，并轉向第（3）步，否則，轉向第（5）步。（5）若SKIPIF1<0，停止計算，SKIPIF1<0即為近似極小點；否則，令SKIPIF1<0，并轉向第（2）步。3.2.3牛頓法牛頓法在搜索方向上比梯度法有所改進，它不但利用了目標函數(shù)的搜索點的梯度，而且還利用了目標函數(shù)的二階偏導數(shù)。也就是說，它不但考慮了函數(shù)的梯度，還考慮了梯度的變化趨勢，所以在更大范圍內考慮了函數(shù)的性質。與梯度法一樣，牛頓法也有其缺陷。例如對一般多變量非線性函數(shù)的極小化問題，它可能收斂不到所尋找的極小值點。因而，有些在實踐中被認為非常成功的方法，是由牛頓法經(jīng)過修改后得到的。假定SKIPIF1<0是二階連續(xù)可微函數(shù)，在給定點SKIPIF1<0附近取SKIPIF1<0的二階泰勒多項式作逼近SKIPIF1<0(3.4)式中，SKIPIF1<0，SKIPIF1<0為函數(shù)在點SKIPIF1<0的n階海賽矩陣，設為非奇異陣。SKIPIF1<0的極小點處，必然滿足SKIPIF1<0，將SKIPIF1<0代入式(3.4)，然后求一階微分得：SKIPIF1<0(3.5)可解得點SKIPIF1<0(3.6)式中，SKIPIF1<0為函數(shù)SKIPIF1<0在點SKIPIF1<0的搜索方向，稱為牛頓方向，即SKIPIF1<0。若令SKIPIF1<0為二次函數(shù)，有SKIPIF1<0（Q為對稱非奇陣）則SKIPIF1<0，即為海賽矩陣，它是一個常數(shù)矩陣。用SKIPIF1<0代入(3.4)右邊，可知該式是一個等式而不是近似式。若再設Q為正定矩陣，則SKIPIF1<0有一極小值點SKIPIF1<0，并且SKIPIF1<0，因此有SKIPIF1<0。令SKIPIF1<0綜合這兩個方程得SKIPIF1<0將此式與(3.6)式比較可知，從任意點SKIPIF1<0出發(fā)，用牛頓法只要一步就達到一個二次函數(shù)的極小值點，如果這個二次函數(shù)存在極小值的話。但對一般的非線性函數(shù)，一步是達不到SKIPIF1<0的極小點的。迭代中往往也會有一些問題。例如SKIPIF1<0在SKIPIF1<0點非正定，或者由式(3.6)得到的點SKIPIF1<0不靠近SKIPIF1<0，以致SKIPIF1<0在SKIPIF1<0附近的二階近似在SKIPIF1<0處無效，還可能出現(xiàn)SKIPIF1<0的情況等等。為了補救這些問題，人們往往用一個限步牛頓公式：SKIPIF1<0來代替式(3.6)，其中SKIPIF1<0的選擇有各種方法，總是使SKIPIF1<0。一般也多用使SKIPIF1<0沿牛頓方向取極小的一維搜索法。牛頓法迭代步驟如下：（1）取初始點SKIPIF1<0，允許誤差SKIPIF1<0，令k：=0。（2）檢驗是否滿足收斂性判別準則SKIPIF1<0，若滿足判別準則，迭代停止，得到SKIPIF1<0。否則進行（3）。（3）令SKIPIF1<0。（4）求單變量極值問題的最優(yōu)解SKIPIF1<0，SKIPIF1<0。（5）令SKIPIF1<0，k：=k+1。轉到（2）。3.3算法性能優(yōu)缺點分析（1）梯度法優(yōu)點：計算量少，存儲變量較少，初始點要求不高。梯度法缺點：初值依賴，收斂慢，最速下降法適用于尋優(yōu)過程的前期迭代或作為間插步驟，越接近極值點時，收斂熟讀越慢，后期宜選用收斂快的算法。（2）牛頓迭代法優(yōu)點：收斂速度很快。牛頓迭代法缺點：當維數(shù)較高時，計算SKIPIF1<0的工作量很大，初值依賴，當初值選擇不好時，有可能計算出現(xiàn)異常，導致迭代無法進行，該法需要修正。所以此算法在計算復雜，要計算二次偏導數(shù)，又要計算逆矩陣。尤其在變量較多時，計算量就更大了。（3）罰函數(shù)法在實際應用中，由于外點法的初始點可任意選擇，不必保證在可行域內，迭代過程中也不要求在可行域內，而是逐步向可行域靠近，因此它比內點法優(yōu)越。內點法要求初始點在可行域內，在搜索過程中要控制中要控制每次的搜索步長，以保持迭代點的可行性，因此，在實現(xiàn)上要比外點法困難，但它的最終收斂點總在可行域內，即使最后只得到一個粗略的近似最優(yōu)點，這個點也必是可行的。4基本粒子群算法4.1粒子群算法概述4.1.1粒子群算法發(fā)展1995年美國電氣工程師Eberhart和社會心理學家Kenndy基于鳥群覓食行為提出了粒子群優(yōu)化算法（particleswarmoptimization，PSO），簡稱粒子群算法。由于該算法概念簡明、實現(xiàn)方便、收斂速度快、參數(shù)設置少，是一種高效的搜索算法。PSO是模擬鳥群隨機搜尋食物的捕食行為。假設在搜索食物區(qū)域里只有一塊食物，所有的小鳥都不知道食物在什么地方，所以Kenndy等認為鳥之間存在著互相交換信息，通過估計自身的適應度值，它們知道當前的位置離食物還有多遠，所以搜索目前離食物最近的鳥的周圍區(qū)域是找到食物的最簡單有效的辦法，通過鳥之間的集體協(xié)作使群體達到最優(yōu)。PSO就是從這種模型中得到啟示并用于解決優(yōu)化問題。在PSO中每個優(yōu)化問題的潛在解都可以想象成搜索空間中的一只鳥，我們稱之為“粒子”。粒子主要追隨當前的最優(yōu)粒子在解空間中搜索，PSO初始化為一群隨機粒子（隨機解），然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個“極值”來更新自己，第一個就是粒子本身所找到的最優(yōu)解，這個解叫做個體極值pbest，另一個極值是整個種群目前找到的最優(yōu)解，這個極值是全局極值gbest。這兩個最優(yōu)變量使得鳥在某種程度上朝著這些方向靠近，此外也可以不用整個種群而只用其中一部分作為粒子的鄰居，那么所有鄰居的極值就是局部極值，粒子始終跟隨這兩個極值變更自己的位置和速度直到找到最優(yōu)解。到目前為止粒子群算法的發(fā)展得到越來越多的眾多領域學者的關注和研究，稱為解決許多問題的熱點算法的研究重點。其中對PSO算法的改進也非常多，有增強算法自適應性的改進、增強收斂性的改進、增加多種群多樣性的改進、增強局部搜索的改進、與全局優(yōu)化算法相結合、與確定性的局部優(yōu)化算法相融合等。以上所述的是對于算法改進的目的的討論的，實際改進中應用的方法有基于參數(shù)的改進，即對PSO算法的迭代公式的形式上做改進；還有從粒子的行為模式進行改進，即粒子之間的信息交流方式，如拓撲結構的改進、全局模式與局部模式相結合的改進等；還有基于算法融合的粒子群算法的改進，算法融合可以引入其他算法的優(yōu)點來彌補PSO算法的缺點，設計出更適合問題求解的優(yōu)化算法。4.1.2粒子群算法簡介粒子群算法是一個非常簡單的算法，且能夠有效的優(yōu)化各種函數(shù)。從某種程度上說，此算法介于遺傳算法和進化規(guī)劃之間。此算法非常依賴于隨機的過程，這也是和進化規(guī)劃的相識之處，此算法中朝全局最優(yōu)和局部最優(yōu)靠近的調整非常的類似于遺傳算法中的交叉算子。此算法還是用了適應值的概念，這是所有進化計算方法所共有的特征。在粒子群算法中，每個個體稱為一個“粒子”，其實每個粒子代表著一個潛在的解。例如，在一個D維的目標搜索空間中，每個粒子看成是空間內的一個點。設群體由m個粒子構成。m也被稱為群體規(guī)模，過大的m會影響算法的運算速度和收斂性。PSO算法通常的數(shù)學描述為：設在一個D維空間中，由m個粒子組成的種群SKIPIF1<0，其中第i個粒子位置為SKIPIF1<0，其速度為SKIPIF1<0。它的個體極值為SKIPIF1<0，種群的全局極值為SKIPIF1<0，按照追隨當前最優(yōu)例子的原理，粒子SKIPIF1<0將按(4.1)、(4.2)式改變自己的速度和位置。SKIPIF1<0(4.1)SKIPIF1<0(4.2)式中j=1,2,…,D，i=1,2,…m，m為種群規(guī)模，t為當前進化代數(shù)，SKIPIF1<0為分布于[0,1]之間的隨機數(shù)；SKIPIF1<0為加速常數(shù)。從式(4.1)中可知，每個粒子的速度由三部分組成：第一部分為粒子先前的速度；第二部分為“認知”部分，表示粒子自身的思考；第三部分為“社會”部分，表示粒子間的信息共享與相互合作。4.1.3粒子群算法的特點粒子群算法是一種新興的智能優(yōu)化技術，是群體智能中一個新的分支，它也是對簡單社會系統(tǒng)的模擬。該算法本質上是一種隨機搜索算法，并能以較大的概率收斂于全局最優(yōu)解。實踐證明，它適合在動態(tài)、多目標優(yōu)化環(huán)境中尋優(yōu)，與傳統(tǒng)的優(yōu)化算法相比較具有更快的計算速度和更好的全局搜索能力。具體特點如下：（1）粒子群優(yōu)化算法是基于群體智能理論的優(yōu)化算法，通過群體中粒子間的合作與競爭產生的群體智能指導優(yōu)化搜索。與進化算法比較，PSO是一種更為高效的并行搜索算法。（2）PSO與GA有很多共同之處，兩者都是隨機初始化種群，使用適應值來評價個體的優(yōu)劣程度和進行一定的隨機搜索。但PSO是根據(jù)自己的速度來決定搜索，沒有GA的明顯的交叉和變異。與進化算法比較，PSO保留了基于種群的全局搜索策略，但是其采用的速度-位移模型操作簡單，避免了復雜的遺傳操作。（3）PSO有良好的機制來有效地平衡搜索過程的多樣性和方向性。（4）GA中由于染色體共享信息，故整個種群較均勻地向最優(yōu)區(qū)域移動。在PSO中gbest將信息傳遞給其他粒子，是單向的信息流動。多數(shù)情況下，所有的粒子可能更快地收斂于最優(yōu)解。（5）PSO特有的記憶使其可以動態(tài)地跟蹤當前的搜索情況并調整其搜索策略。（6）由于每個粒子在算法結束時仍然保持著其個體極值。因此，若將PSO用于調度和決策問題時可以給出多種有意義的選擇方案。而基本遺傳算法在結束時，只能得到最后一代個體的信息，前面迭代的信息沒有保留。（7）即使同時使用連續(xù)變量和離散變量，對位移和速度同時采用和離散的坐標軸，在搜索過程中也并不沖突。所以PSO可以很自然、很容易地處理混合整數(shù)非線性規(guī)劃問題。（8）PSO算法對種群大小不十分敏感，即種群數(shù)目下降時性能下降不是很大。（9）在收斂的情況下，由于所有的粒子都向最優(yōu)解的方向飛去，所以粒子趨向同一化（失去了多樣性）使得后期收斂速度明顯變慢，以致算法收斂到一定精度時無法繼續(xù)優(yōu)化。因此很多學者都致力于提高PSO算法的性能。4.1.4粒子群算法的應用粒子群算法提供了一種求解復雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的適應性，所以廣泛應用于很多學科。下面是粒子群算法的一些主要應用領域：（1）函數(shù)優(yōu)化。函數(shù)優(yōu)化是粒子群算法的經(jīng)典應用領域，也是對粒子群算法進行性能評價的常用算例。（2）約束優(yōu)化。隨著問題的增多，約束優(yōu)化問題的搜索空間也急劇變換，有時在目前的計算機上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。粒子群算法是解決這類問題的最佳工具之一。實踐證明，粒子群算法對于約束優(yōu)化中的規(guī)劃，離散空間組合問題的求解非常有效。（3）工程設計問題。工程設計問題在許多情況下所建立起來的數(shù)學模型難以精確求解，即使經(jīng)過一些簡化之后可以進行求解，也會因簡化得太多而使得求解結果與實際相差甚遠?，F(xiàn)在粒子群算法已成為解決復雜調度問題的有效工具，在電路及濾波器設計、神經(jīng)網(wǎng)絡訓練、控制器設計與優(yōu)化、任務分配等方面粒子群算法都得到了有效的應用。（4）電力系統(tǒng)領域。在其領域中有種類多樣的問題，根據(jù)目標函數(shù)特性和約束類型許多與優(yōu)化相關的問題需要求解。PSO在電力系統(tǒng)方面的應用主要如下：配電網(wǎng)擴展規(guī)劃、檢修計劃、機組組合、負荷經(jīng)濟分配、最優(yōu)潮流計算與無功優(yōu)化控制、諧波分析與電容配置、配電網(wǎng)狀態(tài)估計、參數(shù)辨識、優(yōu)化設計。隨著粒子群優(yōu)化理論研究的深入，它還將在電力市場競價交易、投標策略以及電力市場仿真等領域發(fā)揮巨大的應用潛在力。（5）機器人智能控制。機器人是一類復雜的難以精確建模的人工系統(tǒng)，而粒子群算法可用于此類機器人群搜索，如機器人的控制與協(xié)調，移動機器人路徑規(guī)劃。所以機器人智能控制理所當然地成為粒子群算法的一個重要應用領域。（6）交通運輸領域。交通方面有車輛路徑問題，在物流配送供應領域中要求以最少的車輛數(shù)、最小的車輛總行程來完成貨物的派送任務；交通控制，城市交通問題是困擾城市發(fā)展、制約城市經(jīng)濟建設的重要因素。城市交通運輸系統(tǒng)的管理和控制技術進行研究，來為緩解交通擁擠發(fā)揮巨大作用。其中在其解決方法中應用粒子群算法給解決問題提供了新的，有效的計算方式。（7）通信領域。其中包括路由選擇及移動通信基站布置優(yōu)化，在順序碼分多址連接方式（DS-CDMA）通訊系統(tǒng)中使用粒子群算法，可獲得可移植的有力算法并提供并行處理能力。比傳統(tǒng)的先前的算法有了顯著的優(yōu)越性。還應用到天線陣列控制和偏振模色散補償?shù)确矫妗＃?）計算機領域。在計算機中處理各種問題都涉及到大量的信息計算的方法選擇以減少程序運行的時間，增加系統(tǒng)解決問題的能力，其中包括任務分配問題、數(shù)據(jù)分類、圖像處理等，都得到了粒子群算法的實際問題解決效率的提高。（9）生物醫(yī)學領域。許多菌體的生長模型即為非線性模型提出了用粒子群算法解決非線性模型的參數(shù)估計問題。還在分子力場的參數(shù)設定和蛋白質圖形的發(fā)現(xiàn)。根據(jù)粒子群算法提出的自適應多峰生物測定融合算法，提高了解決問題的準確性。在醫(yī)學方面，如醫(yī)學成像上得到的推廣應用等。4.2基本粒子群算法4.2.1基本粒子群算法的構成要素（1）粒子群編碼方法。基本粒子群算法使用固定長度的二進制符號串來表示群體中的個體，其等位基因是由二值符號集{0，1}所組成的。初始群體中各個個體的基因值可用均勻分布的隨機數(shù)來生成。（2）個體適應度評價。通過確定局部最優(yōu)迭代達到全局最優(yōu)收斂，得出結果。（3）基本粒子群算法的運行參數(shù)。基本粒子群算法有下述7個運行參數(shù)需要提前設定：●r為粒子群算法的種子數(shù)，對粒子群算法其中種子數(shù)值可以隨機生成也可以固定為一個初始的數(shù)值，要求能涵蓋目標函數(shù)的范圍內。●M：粒子群群體大小，即群體中所含個體的數(shù)量，一般取為20～100。在變量比較多的時候可以取100以上較大的數(shù)。●max_d：一般為最大迭代次數(shù)以最小誤差的要求滿足的。粒子群算法的最大迭代次數(shù)，也是終止條件數(shù)?！駌1,r2：兩個在[0,1]之間變化的加速度權重系數(shù)隨機產生?！馽1,c2：加速度數(shù)，取隨機2左右的值?！駑w：為慣性權重產生的?！駐k，xk：為一個粒子的速度和位移數(shù)值，用粒子群算法迭代出每一組數(shù)值。4.2.2基本粒子群算法的形式化定義基本粒子群算法可定義為的元素：max_d——粒子群算法的最大迭代次數(shù)；r——給定個體的種子數(shù)值；fmax——為最大的慣性權值；fmin——為最小的慣性權值；pg——初始群體值；M——粒子群的群體大小；vk——粒子移動的速度；xk——粒子移動的方向；c1,c2；r1,r1——隨機參數(shù)變量；[x,dd]=judge(x,M)——算法調用的求解函數(shù)。4.2.3基本粒子群算法描述beginInitalize;%包括初始化粒子群數(shù)，粒子初始速度和位置[x,xd]=judge(x,pop_size);%調用judge函數(shù)，初始化第一次值fornum=2:最大迭代次數(shù)wk=wmax-num*(wmax-wmin)/max_gen;%計算慣性權重r1=;r2=%隨機產生加速權重PSO算法迭代求vk,xk；While判斷vk是否滿足條件再次重新生成加速權重系數(shù)r1;r2PSO算法再次迭代求vk;xk數(shù)值end調用[x,xd]=judge(x,pop_size);重新計算出目標函數(shù)值判斷并重新生成pj數(shù)值；判斷并重新生成pjd數(shù)值；if迭代前數(shù)值>迭代后的數(shù)值累加迭代次數(shù)值end輸出隨機數(shù)種子、進度、最優(yōu)迭代次數(shù)、每個函數(shù)的數(shù)值和目標函數(shù)的數(shù)值用ASCII保存粒子位移的數(shù)值用ASCII保存粒子速度的數(shù)值end4.3粒子群算法的關鍵4.3.1粒子狀態(tài)向量形式的確定類似于遺傳算法中染色體串的形式，粒狀態(tài)向量的構造形式也屬于一種編碼，但不同的是，由于PSO算法中粒子狀態(tài)的更新方式的簡捷，因此其編碼形式相比遺傳算法更簡單，向量維數(shù)更小。可以根據(jù)優(yōu)化系統(tǒng)的規(guī)模與控制變量的性質和特點來確定粒子狀態(tài)的維數(shù)n和編碼的排列順序以及不同維的含義。對于同一問題，即使采用同一種優(yōu)化算法，也可以有不同的編碼方式。4.3.2適應度函數(shù)的建立適應度函數(shù)用于評價各粒子的性能優(yōu)劣，根據(jù)適應值的大小來尋找粒子的狀態(tài)極值，從而更新群中其它粒子的狀態(tài)。粒子的適應度函數(shù)值越大，表示該個體粒子的適應度越高，也即該粒子個體的質量越好，更適應目標函數(shù)所定義的生存環(huán)境。全局極值就是粒子群中適應值最高的粒子狀態(tài)，個體極值也是如此。適應度函數(shù)為群體極值的選擇和更新提供了依據(jù)。對于一般函數(shù)優(yōu)化問題可以直接將函數(shù)本身作為適應度函數(shù)，但是對于復雜的多目標函數(shù)適應度函數(shù)一般不那么直觀，往往需要研究者自己根據(jù)具體情況和預定的優(yōu)化效果來自行構造。特別地，對于多變量、多約束的復雜系統(tǒng)，變量的不等式約束通常采用罰函數(shù)形式來處理，通過這個廣義目標函數(shù)，使得算法在懲罰項的作用下找到原問題的最優(yōu)解。4.3.3粒子多樣性的保證在基本PSO算法搜索后期，粒子群容易向局部極小或全局極小收斂，此時群中粒子也在急劇地聚集，粒子狀態(tài)的更新速度越來越慢，群體粒子出現(xiàn)趨同性，粒子的多樣性越來越差，甚至陷入局部最優(yōu)值。如何采取一定的措施增加粒子的多樣性，以避免陷入局部最優(yōu)也是基本PSO算法的一個關鍵問題。4.3.4粒子群算法的參數(shù)設置PSO算法一個最大的優(yōu)點是不需要調節(jié)太多的參數(shù)，但是算法中少數(shù)幾個參數(shù)卻直接影響著算法的性能以及收斂性。目前，PSO算法的理論研究尚處于初始階段，所以算法的參數(shù)設置在很大程度上還依賴于經(jīng)驗。PSO參數(shù)包括：群體規(guī)模m，微粒子長度l，微粒范圍SKIPIF1<0，微粒最大速度SKIPIF1<0，慣性權重SKIPIF1<0，加速常數(shù)SKIPIF1<0。下面是這些參數(shù)的作用及其設置經(jīng)驗。群體規(guī)模m：即微粒數(shù)目，一般取20～40。試驗表明，對于大多數(shù)問題來說，30個微粒就可以取得很好的結果，不過對于比較難的問題或者特殊類別的問題，微粒數(shù)目可以取到100或200。微粒數(shù)目越多，算法搜索的空間范圍就越大，也就更容易發(fā)現(xiàn)全局最優(yōu)解。當然，算法運行的時間也越長。微粒長度l：即每個微粒的維數(shù)，由具體優(yōu)化問題而定。微粒范圍SKIPIF1<0：微粒范圍由具體優(yōu)化問題決定，通常將問題的參數(shù)取值范圍設置為微粒的范圍。同時，微粒每一維也可以設置不同的范圍。微粒最大速度SKIPIF1<0：微粒最大速度決定了微粒在一次飛行中可以移動的最大距離。如果SKIPIF1<0太大，微?？赡軙w過好解；如果SKIPIF1<0太小，微粒不能在局部好區(qū)間之外進行足夠的搜索，導致陷入局部最優(yōu)值。通常設定SKIPIF1<0，SKIPIF1<0，每一維都采用相同的設置方法。慣性權重fw：fw使微粒保持運動慣性，使其有擴展搜索空間的趨勢，有能力探索新的區(qū)域。取值范圍通常為SKIPIF1<0。早期的實驗將fw固定為1.0發(fā)現(xiàn)，動態(tài)慣性權重因子能夠獲得比固定值更為優(yōu)越的尋優(yōu)結果，使算法在全局搜索前期有較高的探索能力以得到合適的種子。動態(tài)慣性權重因子可以在PSO搜索過程中線性變化，亦可根據(jù)PSO性能的某個測度函數(shù)而動態(tài)改變，比如模糊規(guī)則系統(tǒng)。目前采用較多的動態(tài)慣性權重因子是Shi建議的線性遞減權值策略，如式(4.3)。它能使fw由0.8隨迭代次數(shù)遞減到0.2。SKIPIF1<0(4.3)式中，max_d為最大進化代數(shù)，fmax為初始慣性值，fmin為迭代至最大代數(shù)時的慣性權值。經(jīng)典取值fmax=0.8，fmin=0.2。加速常數(shù)SKIPIF1<0和SKIPIF1<0：SKIPIF1<0和SKIPIF1<0代表將每個微粒推向pBest和gBest位置的統(tǒng)計加速項的權重。低的值允許微粒在被拉回之前可以在目標區(qū)域外徘徊，而高的值則導致微粒突然的沖向或越過目標區(qū)域。SKIPIF1<0和SKIPIF1<0是固定常數(shù)，早期實驗中一般取2。有些文獻也采取了其它取值，但一般都限定SKIPIF1<0和SKIPIF1<0相等并且取值范圍為SKIPIF1<0。5基于粒子群算法求解非線性規(guī)劃問題的設計作為運籌學的一個重要的分支，非線性規(guī)劃問題求解方法一直式人們研究的重點。隨著優(yōu)化對象復雜性的增加，優(yōu)化問題的規(guī)模也越來越大，傳統(tǒng)的優(yōu)化方法難以適應，因此人們在尋求嚴格最優(yōu)化理論化方法和智能優(yōu)化方法如遺傳算法，蟻群算法等，但各種方法都有其相應的適用范圍和局限性。粒子群優(yōu)化算法是由Kennedy和Eberhart開發(fā)的一種演化計算技術。由于PSO概念簡單、容易實現(xiàn)并且沒有許多參數(shù)需要調整，同時又有深刻的智能背景，即適合科學計算，又特別適合工程應用。因此，將粒子群算法應用于非線性規(guī)劃，是改善求解非線性規(guī)劃的效果，提高非線性規(guī)劃質量的有效途徑。本章就是介紹粒子群算法在非線性規(guī)劃中的具體應用，設計并實現(xiàn)基于粒子群算法的非線性規(guī)劃問題的求解。5.1實用粒子群算法設計5.1.1編碼方法設計在MATLAB中編寫非線性規(guī)劃問題的粒子群算法編碼的過程中，首先在函數(shù)中把非線性規(guī)劃函數(shù)轉化為一種MATLAB可以閱讀的矩陣型的函數(shù)值，在其中添加約束條件，并作超出約束的變換的方法。在運行函數(shù)中設置各種參數(shù)數(shù)值，編寫粒子群方法的實現(xiàn)方法，并迭代求解各個過程中目標函數(shù)的數(shù)值解，輸出結果值。在所有局部解中搜索最優(yōu)解，作為最終的目標函數(shù)數(shù)值。計算結束。5.1.2適應度函數(shù)設計適應度表示個體x對環(huán)境的適應程度。分為兩類，一類為針對被優(yōu)化的目標函數(shù)的優(yōu)化型適應度，另一類為針對約束函數(shù)的約束性適應度。其中優(yōu)化型適應度和約束型適應度分別表示為SKIPIF1<0（5-1）SKIPIF1<0（