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

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