粒子群論文--有關(guān)非線(xiàn)性規(guī)劃問(wèn)題的粒子群算法

1、<p>　　有關(guān)非線(xiàn)性規(guī)劃問(wèn)題的粒子群算法</p><p>　　學(xué) 院（系）： 數(shù)理學(xué)院 </p><p>　　專(zhuān) 業(yè)： 運(yùn)籌學(xué)與控制論 </p><p>　　學(xué) 號(hào)： 2014100057 </p><p>　　學(xué) 生 姓 名： 劉

2、麗娜 </p><p><b>　　摘要</b></p><p>　　優(yōu)化這一技術(shù)，正是為這些問(wèn)題的解決，提供理論基礎(chǔ)和求解方法，它是一門(mén)應(yīng)用廣泛、實(shí)用性很強(qiáng)的科學(xué)。近十余年來(lái)，粒子群優(yōu)化算法作為群體智能算法的一個(gè)重要分支得到了廣泛深入的研究，在路徑規(guī)劃等許多領(lǐng)域都有應(yīng)用。本文主要結(jié)合現(xiàn)階段的非線(xiàn)性規(guī)劃問(wèn)題的研究概況對(duì)粒子群優(yōu)化算法進(jìn)行初步介紹。<

3、;/p><p>　　優(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)題，它是指在滿(mǎn)足一定的約束條件下，尋找一組參數(shù)值，使目標(biāo)函數(shù)達(dá)到最大或最小。最優(yōu)化問(wèn)題根據(jù)其目標(biāo)函數(shù)、約束條件的性質(zhì)以及優(yōu)化變量的取值范圍可以分為許多類(lèi)型，例如：根據(jù)目標(biāo)函數(shù)和約束條件是否均為線(xiàn)性表達(dá)式，把最優(yōu)化問(wèn)題劃分為線(xiàn)性規(guī)劃問(wèn)題和非線(xiàn)性規(guī)劃問(wèn)題。針對(duì)不同的最

4、優(yōu)化問(wèn)題，提出了許多不同的優(yōu)化方法，如牛頓法、共軛梯度法、Polar-Ribiere 法、拉格朗日乘子法等。這些優(yōu)化算法能很好地找到問(wèn)題的局部最優(yōu)點(diǎn)，是成熟的局部?jī)?yōu)化算法。</p><p>　　但是隨著人類(lèi)生存空間的擴(kuò)大以及認(rèn)識(shí)與改造世界范圍的拓展，人們發(fā)現(xiàn)由于問(wèn)題的復(fù)雜性、約束性、非線(xiàn)性、建模困難等特點(diǎn)，解析性?xún)?yōu)化算法已不能滿(mǎn)足人們的要求，需要尋找一種適合于大規(guī)模并行且具有智能特征的優(yōu)化算法?，F(xiàn)代進(jìn)化類(lèi)方法如人

5、工神經(jīng)網(wǎng)絡(luò)、遺傳算法、禁忌搜索法、模擬退火法和蟻群算法等在解決大規(guī)模的問(wèn)題時(shí)體現(xiàn)出強(qiáng)大的潛力，它們可以在合理的時(shí)間限制內(nèi)逼近優(yōu)化問(wèn)題的較好可行解。其中，遺傳算法和蟻群算法被稱(chēng)為智能優(yōu)化算法，其基本思想是通過(guò)模擬自然界生物的行為來(lái)構(gòu)造隨機(jī)優(yōu)化算法。</p><p>　　近年來(lái)，另一種智能優(yōu)化算法—粒子群算法（particle swarm optimization，簡(jiǎn)稱(chēng)PSO）越來(lái)越受到學(xué)者的關(guān)注。粒子群算法是美國(guó)社

6、會(huì)心理學(xué)家JamesKennedy 和電氣工程師Russell Eberhart 在1995 年共同提出的，它是受到鳥(niǎo)群社會(huì)行為的啟發(fā)并利用了生物學(xué)家Frank Heppner 的生物群體模型而提出的。它用無(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)

7、域都得到了廣泛的應(yīng)用。本文主要結(jié)合現(xiàn)階段的非線(xiàn)性規(guī)劃問(wèn)題的研究概況對(duì)粒子群優(yōu)化算法進(jìn)行初步介紹。</p><p>　　關(guān)鍵詞：非線(xiàn)性規(guī)劃；粒子群算法；智能算法</p><p><b>　　ABSTRACT</b></p><p>　　Optimization of this technology is to solve these proble

8、ms, to provide a theoretical basis and solution method, it is a wide range of applications, practical science. In the last ten years, the particle swarm optimization algorithm is a very important branch of the swarm inte

9、lligence algorithm, which has been applied in many fields such as path planning. In this paper, we mainly introduce the general situation of the research on the nonlinear programming problems at the present stage.</p&

10、gt;<p>　　The optimization technology is a kind of application technology based on mathematics, which is used to solve various combinatorial optimization problems. Optimization problems are widely encountered the i

11、n many fields of engineering technology, scientific research and economic management, it is to satisfy certain constraints, looking for a set of parameters values, the objective function to achieve the maximum or minimum

12、. Optimization problem according to the range of objective function and cons</p><p>　　But with the human living space and the scope of understanding and transforming the world development, it was found that

13、due to the characteristics of the problem of complexity, constraint, nonlinearity and difficulty in modeling and analytical optimization algorithm has been unable to meet the people's requirements and need to find a

14、suitable in large scale parallel and intelligent optimization algorithm with. Modern evolution methods such as artificial neural network, genetic algorithm, tabu s</p><p>　　In recent years, the swarm optimiz

15、ation particle (PSO), another kind of intelligent optimization algorithm, has received more and more attention. Particle swarm algorithm is American social psychologist along and electrical engineer Russell Eberhart in 1

16、995 put together. It is inspired by social behavior of bird flocking and use the biologist Frank Heppner biological group model proposed. It is used as an individual with no mass and no volume, and the optimal solution o

17、f the problem is realized </p><p>　　Keywords: nonlinear programming; particle swarm algorithm; intelligent algorithm</p><p><b>　　一．背景介紹</b></p><p>　　1．非線(xiàn)性規(guī)劃問(wèn)題的簡(jiǎn)介</p&g

18、t;<p>　　1.1非線(xiàn)性規(guī)劃的應(yīng)用</p><p>　　具有非線(xiàn)性約束條件或目標(biāo)函數(shù)的數(shù)學(xué)規(guī)劃，是運(yùn)籌學(xué)的一個(gè)重要的分支，非線(xiàn)性規(guī)劃研究一個(gè)n元實(shí)函數(shù)在一組等式或不等式的約束條件下的機(jī)制問(wèn)題且目標(biāo)函數(shù)和約束條件至少有一個(gè)是未知量的非線(xiàn)性函數(shù)，目標(biāo)函數(shù)和約束條件都是線(xiàn)性函數(shù)的情形則屬于線(xiàn)性規(guī)劃。</p><p>　　非線(xiàn)性規(guī)劃是20世紀(jì)50年代才開(kāi)始形成的一門(mén)新興學(xué)科。19

19、51年H.W庫(kù)恩和A.W塔克發(fā)表的關(guān)于最優(yōu)性條件的論文是非線(xiàn)性規(guī)劃正式誕生的一個(gè)重要標(biāo)志。在50年代可得出了可分離規(guī)劃和二次規(guī)劃的n種解法，它們大都是以G.B.丹齊克提出的解線(xiàn)性規(guī)劃的單純形法為基礎(chǔ)的。50年代末到60年代末出現(xiàn)了許多解非線(xiàn)性規(guī)劃問(wèn)題的有效的算法，70年代又得到進(jìn)一步的發(fā)展。非線(xiàn)性規(guī)劃在工程、管理、經(jīng)濟(jì)、科研、軍事等方面都有廣泛的應(yīng)用，為最優(yōu)設(shè)計(jì)提供了有力的工具。</p><p>　　非線(xiàn)性規(guī)劃問(wèn)

20、題廣發(fā)存在于科學(xué)與工程領(lǐng)域，是一類(lèi)比較難以解決的優(yōu)化問(wèn)題，沒(méi)有普遍使用的解法。傳統(tǒng)的求解該問(wèn)題的方法（如罰函數(shù)，可行方向法，以及變尺度法等）是基于梯度的方法所以目標(biāo)函數(shù)與約束式必須是可微的，并且這些方法只能保證求的局部最優(yōu)解。</p><p>　　1.2非線(xiàn)性規(guī)劃的相關(guān)概念</p><p>　　定義：如果目標(biāo)函數(shù)或約束條件中至少有一個(gè)是非線(xiàn)性規(guī)劃函數(shù)時(shí)的最優(yōu)化問(wèn)題就叫做非線(xiàn)性規(guī)劃問(wèn)題。&l

21、t;/p><p><b>　　一般形式：min </b></p><p><b>　?。?-1）</b></p><p>　　其中是定義在上的實(shí)值函數(shù)，簡(jiǎn)記：</p><p>　　其它情況：求目標(biāo)函數(shù)的最大值或約束條件為小于等于零的情況，都可通過(guò)取其相反數(shù)化為上述一般形式。 </p>&l

22、t;p>　　定義1 把滿(mǎn)足問(wèn)題(2-1)中條件的解稱(chēng)為可行解（或可行點(diǎn)），所有可行點(diǎn)的集合稱(chēng)為可行集（或可行域）．記為D．即問(wèn)題(2-1)可簡(jiǎn)記為</p><p>　　定義2 對(duì)于問(wèn)題(2-1)，設(shè)，若存在，使得對(duì)于一切且‖‖<，都有則稱(chēng)是在D上的局部極小值點(diǎn)（局部最優(yōu)解）。特別地當(dāng)時(shí)，若，則稱(chēng)在D上的嚴(yán)格局部極小值點(diǎn)（嚴(yán)格局部最優(yōu)解）。</p><p>　　定義3 對(duì)于

23、問(wèn)題(2-1),設(shè)，對(duì)于任意的，都有則稱(chēng)是在D上的全局極小值點(diǎn)（全局最優(yōu)解）。特別地當(dāng)時(shí)，若，則稱(chēng)是上的嚴(yán)格全局極小值點(diǎn)（嚴(yán)格全局最優(yōu)解）。</p><p>　　2.粒子群算法的簡(jiǎn)介</p><p>　　2.1 粒子群優(yōu)化算法的起源</p><p>　　粒子群優(yōu)化（PSO）算法是由Kennedy和Eberhart于1995年用計(jì)算機(jī)模擬鳥(niǎo)群覓食這一簡(jiǎn)單的社會(huì)行為時(shí)，

24、受到啟發(fā)，簡(jiǎn)化之后而提出的[1][2]。</p><p>　　設(shè)想這樣一個(gè)場(chǎng)景：一群鳥(niǎo)隨機(jī)的分布在一個(gè)區(qū)域中，在這個(gè)區(qū)域里只有一塊食物。所有的鳥(niǎo)都不知道食物在哪里。但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn)。那么找到食物的最優(yōu)策略是什么呢。最簡(jiǎn)單有效的方法就是追尋自己視野中目前離食物最近的鳥(niǎo)。如果把食物當(dāng)作最優(yōu)點(diǎn)，而把鳥(niǎo)離食物的距離當(dāng)作函數(shù)的適應(yīng)度，那么鳥(niǎo)尋覓食物的過(guò)程就可以當(dāng)作一個(gè)函數(shù)尋優(yōu)的過(guò)程。魚(yú)群和鳥(niǎo)群的社會(huì)行為

25、一直引起科學(xué)家的興趣。他們以特殊的方式移動(dòng)、同步，不會(huì)相互碰撞，整體行為看上去非常優(yōu)美。生物學(xué)家CargiReynolds提出了一個(gè)非常有影響的鳥(niǎo)群聚集模型。在他的模擬模型boids中，每一個(gè)個(gè)體遵循：避免與鄰域個(gè)體相沖撞、匹配鄰域個(gè)體的速度、試圖飛向感知到的鳥(niǎo)群中心這三條規(guī)則形成簡(jiǎn)單的非集中控制算法驅(qū)動(dòng)鳥(niǎo)群的聚集，在一系列模擬實(shí)驗(yàn)中突現(xiàn)出了非常接近現(xiàn)實(shí)鳥(niǎo)群聚集行為的現(xiàn)象。該結(jié)果顯示了在空中回旋的鳥(niǎo)組成輪廓清晰的群體，以及遇到障礙物時(shí)鳥(niǎo)

26、群的分裂和再度匯合過(guò)程。由此受到啟發(fā)，經(jīng)過(guò)簡(jiǎn)化提出了粒子群優(yōu)化算法。</p><p>　　2.2粒子群優(yōu)化算法的原理</p><p>　　在粒子群優(yōu)化算法中，每個(gè)優(yōu)化問(wèn)題的潛在解都是搜索空間中的一只鳥(niǎo)，稱(chēng)之為“粒子”。所有的粒子都有一個(gè)由被優(yōu)化的函數(shù)決定的適應(yīng)值，每個(gè)粒子還有一個(gè)速度決定他們飛翔的方向和距離。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索。優(yōu)化開(kāi)始時(shí)先初始化為一群隨機(jī)粒子（隨

27、機(jī)解）。然后通過(guò)迭代找到最優(yōu)解。在每一次迭代中，粒子通過(guò)跟蹤兩個(gè)極值來(lái)更新自己。第一個(gè)極值就是整個(gè)種群目前找到的最優(yōu)解。這個(gè)極值是全局極值。另外也可以不用整個(gè)種群而只是用其中一部分作為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。第二個(gè)極值是粒子本身所找到的最優(yōu)解，稱(chēng)為個(gè)體極值。這是因?yàn)榱Ｗ觾H僅通過(guò)跟蹤全局極值或者局部極值來(lái)更新位置，不可能總是獲得較好的解。這樣在優(yōu)化過(guò)程中，粒子在追隨全局極值或局部極值的同時(shí)追隨個(gè)體極值則圓滿(mǎn)的解決了

28、這個(gè)問(wèn)題。這就是粒子群優(yōu)化算法的原理。</p><p>　　在算法開(kāi)始時(shí)，隨機(jī)初始化粒子的位置和速度構(gòu)成初始種群，初始種群在解空間中為均勻分布。其中第i個(gè)粒子在n維解空間的位置和速度可分別表示為Xi=（xi1,xi2,…,xid）和Vi=（vi1,vi2,…,vid），然后通過(guò)迭代找到最優(yōu)解。在每一次迭代中，粒子通過(guò)跟蹤兩個(gè)極值來(lái)更新自己的速度和位置。一個(gè)極值是粒子本身到目前為止所找到的最優(yōu)解，這個(gè)極值稱(chēng)為個(gè)體極

29、值Pbi=（Pbi1,Pbi2,…,Pbid）。另一個(gè)極值是該粒子的鄰域到目前為止找到的最優(yōu)解，這個(gè)極值稱(chēng)為整個(gè)鄰域的最優(yōu)粒子Nbesti=(Nbesti1,Nbesti2,…,Nbestid)。粒子根據(jù)如下的式(1-2)和式(1-3)來(lái)更新自己的速度和位置：</p><p>　　Vi=Vi+c1·rand()·(Pbesti-Xi)+c2·rand()·(Nbesti-X

30、i) (1-2)</p><p>　　Xi= Xi+ Vi (1-3)</p><p>　　式中c1和c2是加速常量，分別調(diào)節(jié)向全局最好粒子和個(gè)體最好粒子方向飛行的最大步長(zhǎng)，若太小，則粒子可能遠(yuǎn)離目標(biāo)區(qū)域,若太大則會(huì)導(dǎo)致突然向目標(biāo)區(qū)域飛去，或飛過(guò)目標(biāo)區(qū)域。

31、合適的c1，c2可以加快收斂且不易陷入局部最優(yōu)。rand()是0到1之間的隨機(jī)數(shù)。粒子在每一維飛行的速度不能超過(guò)算法設(shè)定的最大速度Vmax。設(shè)置較大的Vmax可以保證粒子種群的全局搜索能力，Vmax較小則粒子種群優(yōu)化算法的局部搜索能力加強(qiáng)。</p><p>　　粒子群優(yōu)化算法是在模擬鳥(niǎo)群覓食時(shí)受到啟發(fā)提出的。提出之后卻發(fā)現(xiàn)用動(dòng)物或人的認(rèn)知來(lái)解釋算法的原理更加完美。在速度更新公式(1-2)中由3個(gè)部分構(gòu)成。第1個(gè)部

32、分是Vi，表示粒子在解空間有按照原有方向和速度進(jìn)行搜索的趨勢(shì)，這可以用人在認(rèn)知事物時(shí)總是用固有的習(xí)慣來(lái)解釋。第2個(gè)部分是c1·rand()·(Pbesti-Xi)，表示粒子在解空間有朝著過(guò)去曾碰到的最優(yōu)解進(jìn)行搜索的趨勢(shì)，這可以用人在認(rèn)知事物時(shí)總是用過(guò)去的經(jīng)驗(yàn)來(lái)解釋。第3部分是c2·rand()·(Nbesti-Xi)，表示粒子在解空間有朝著整個(gè)鄰域過(guò)去曾碰到的最優(yōu)解進(jìn)行搜索的趨勢(shì)。</p&g

33、t;<p>　　2.3粒子群優(yōu)化算法的優(yōu)點(diǎn)</p><p>　　粒子群優(yōu)化算法具有以下主要優(yōu)點(diǎn)：(1)易于描述；(2)便于實(shí)現(xiàn)；(3)要調(diào)整的參數(shù)很少；(4)使用規(guī)模相對(duì)較少的群體；(5)收斂需要評(píng)估函數(shù)的次數(shù)少；(6)收斂速度快粒子群優(yōu)化算法很容易實(shí)現(xiàn)，計(jì)算代價(jià)低，由于其內(nèi)存和CPU速度要求都很低。而且，它不需要目標(biāo)函數(shù)的梯度信息，只依靠函數(shù)值。粒子群優(yōu)化算法已被證明是解決許多全局優(yōu)化問(wèn)題的有效方

34、法。</p><p>　　二.非線(xiàn)性規(guī)劃問(wèn)題的粒子群算法設(shè)計(jì)</p><p><b>　　1．編碼方法設(shè)計(jì)</b></p><p>　　在MATLAB中編寫(xiě)非線(xiàn)性規(guī)劃問(wèn)題的粒子群算法編碼的過(guò)程中，首先在函數(shù)中把非線(xiàn)性規(guī)劃函數(shù)轉(zhuǎn)化為一種MATLAB可以閱讀的矩陣型的函數(shù)值，在其中添加約束條件，并作超出約束的變換的方法。在運(yùn)行函數(shù)中設(shè)置各種參數(shù)數(shù)值

35、，編寫(xiě)粒子群方法的實(shí)現(xiàn)方法，并迭代求解各個(gè)過(guò)程中目標(biāo)函數(shù)的數(shù)值解，輸出結(jié)果值。在所有局部解中搜索最優(yōu)解，作為最終的目標(biāo)函數(shù)數(shù)值。計(jì)算結(jié)束。</p><p>　　2. 適應(yīng)度函數(shù)設(shè)計(jì)</p><p>　　適應(yīng)度表示個(gè)體x對(duì)環(huán)境的適應(yīng)程度。分為兩類(lèi)，一類(lèi)為針對(duì)被優(yōu)化的目標(biāo)函數(shù)的優(yōu)化型適應(yīng)度，另一類(lèi)為針對(duì)約束函數(shù)的約束性適應(yīng)度。</p><p>　　其中優(yōu)化型適應(yīng)度和約束

36、型適應(yīng)度分別表示為</p><p>　　（2-1） （2-2）</p><p>　　定義不同約束條件的權(quán)重為，則總的約束型適應(yīng)度為。其中，，這里，隨機(jī)獲得，任意選取k組，獲得的k個(gè)適應(yīng)值的均值作為最終的總的約束型適應(yīng)度。</p><p>　　3． 基于約束適應(yīng)度優(yōu)先排序的約束條件處理方法</p>

37、<p>　　因?yàn)榱Ｗ酉蜻m應(yīng)度函數(shù)值高的方向群游，因此對(duì)群體中所有粒子按照適應(yīng)值進(jìn)行排序，基本思想是：首先比較粒子的約束適應(yīng)度，適應(yīng)值大的粒子排名靠前；如果約束值大的粒子排名靠前。與通常的懲罰函數(shù)方法相比，這種方法的優(yōu)點(diǎn)是可行點(diǎn)的適應(yīng)度總是優(yōu)于非可行點(diǎn)的適應(yīng)度。從而使得優(yōu)化過(guò)程先得到可行點(diǎn)，然后由這些可行點(diǎn)及較好的不可行點(diǎn)的進(jìn)行操作得到最優(yōu)可行點(diǎn)。這樣可以將進(jìn)入可行域和得到優(yōu)化點(diǎn)統(tǒng)一起來(lái)，且無(wú)需變換優(yōu)化目標(biāo)的適應(yīng)度到大于零，并且

38、無(wú)需設(shè)置約束適應(yīng)度和目標(biāo)適應(yīng)度的權(quán)重，使用較為簡(jiǎn)單。</p><p><b>　　4． 動(dòng)態(tài)鄰域算子</b></p><p>　　因?yàn)樵谶m應(yīng)值較好的點(diǎn)的鄰域一定存在適應(yīng)度更好的個(gè)體，為此可采用動(dòng)態(tài)鄰域算子方法，基本思想是：在優(yōu)化的初始階段，一個(gè)微粒的鄰域就是它本身，當(dāng)優(yōu)化代數(shù)增加后，鄰域逐漸變大，最后將包括所有的微粒。為得到鄰域，首先在約束適應(yīng)度空間，計(jì)算候選個(gè)體與其

39、他所有個(gè)體的距離，其中對(duì)第個(gè)個(gè)體的距離為，找出距離最近的k個(gè)個(gè)體（k為鄰域大?。渲心繕?biāo)函數(shù)適應(yīng)值大的個(gè)體為鄰域的局部歷史最好值，其中最大距離為，并定義一個(gè)與當(dāng)前計(jì)算代數(shù)有關(guān)的分?jǐn)?shù)，如果，且，則針對(duì)進(jìn)行搜索；否則使用。</p><p>　　根據(jù)粒子鄰域是否為整個(gè)群體，PSO分為全局模型和局部模型，對(duì)于模型，每個(gè)粒子與整個(gè)群體的其他粒子進(jìn)行信息交換，并有向所有粒子中的歷史最佳位置移動(dòng)的趨勢(shì)。Kennedy指出，模

40、型雖然具有較快的收斂速度，但更容易陷入局部極值。為了克服全局模型的缺點(diǎn)，研究人員采用每個(gè)粒子僅在一定的鄰域內(nèi)進(jìn)行信息交換，提出各種局部模型。根據(jù)現(xiàn)有的研究成果，本文將鄰域分為空間鄰域、性能空間鄰域和社會(huì)關(guān)系鄰域?？臻g鄰域直接在搜索空間按粒子間的距離進(jìn)行劃分，如Suganthan引入一個(gè)時(shí)變的歐式空間鄰域算子：在搜索初始階段，將鄰域定義為每個(gè)粒子自身；隨著迭代次數(shù)的增加，將鄰域范圍逐漸擴(kuò)展到整個(gè)種群。性能空間指根據(jù)性能指標(biāo)（如適應(yīng)度、目標(biāo)

41、函數(shù)值）劃分的鄰域。社會(huì)關(guān)系鄰域通常按粒子存儲(chǔ)陣列的索引編號(hào)進(jìn)行劃分，這也是研究最多的一種劃分手段，主要有：環(huán)形拓?fù)?、輪形拓?fù)浠蛐切瓮負(fù)?、塔形拓?fù)?、馮-諾以曼拓?fù)湟约半S機(jī)拓?fù)涞取ａ槍?duì)不同的優(yōu)化問(wèn)題，這些拓?fù)涞男阅鼙憩F(xiàn)各異；但總的來(lái)說(shuō)隨機(jī)拓?fù)渫鶎?duì)大多數(shù)問(wèn)題能表現(xiàn)出較好的性能，其次是馮-諾以曼拓?fù)洹?lt;/p><p>　　5． 可變慣性權(quán)重和最大速度</p><p>　　慣性權(quán)重控制前一變化量

42、對(duì)當(dāng)前變化量的影響，如果較大，能夠搜索以前未能達(dá)到的區(qū)域，整個(gè)算法的全局搜索能力加強(qiáng)；若較小，則前一部分的影響較小，主要是在當(dāng)前解的附近搜索，局部搜索能力較強(qiáng)，在具體實(shí)例中的方法將慣性權(quán)重設(shè)為從0.8到0.2隨時(shí)間線(xiàn)性減小的變量，使其在前期時(shí)有較高的探索能力以及得到合適的種子，而在后期時(shí)有較高的開(kāi)發(fā)能力以加快收斂速度。</p><p>　　最大速度決定在當(dāng)前位置與最好的位置之間的區(qū)域的分辨率（或精度），如果太高，

43、微?？赡軙?huì)飛過(guò)好解，如果太小，微粒不能在局部好區(qū)間之外進(jìn)行足夠的探索，導(dǎo)致陷入局部?jī)?yōu)值。</p><p>　　6． 粒子群算法運(yùn)行參數(shù)設(shè)計(jì)</p><p>　?。?）群體大小M。群體大小M表示群體中所含個(gè)體的數(shù)量。M取值的大小與粒子群算法運(yùn)行速度，群體多樣性有關(guān)。一般取值為50～100。在變量比較多的時(shí)候會(huì)影響粒子群算法的精確度，因此可以擴(kuò)大粒子群的大小，本文引用300個(gè)粒子數(shù)。</

44、p><p>　　（2）權(quán)重fmax，fmin，c1，c2。fmax為初始慣性權(quán)重，fmin為終止慣性權(quán)重。c1粒子自身加速度權(quán)重系數(shù)，一般在0-2之間的取值，c2為全局加速度權(quán)重系數(shù)，一般在0-2之間取值。在算法中c1和c2為隨機(jī)產(chǎn)生數(shù)值。</p><p>　　（3）r1，r2。[0,1]范圍內(nèi)兩個(gè)相互獨(dú)立的，均勻分布的隨機(jī)數(shù)。</p><p>　?。?）粒子自身速度v

45、k。為了減少在搜索過(guò)程中粒子離開(kāi)搜索空間的可能性，vk通過(guò)被限定于一定的范圍內(nèi)，即，當(dāng)然，亦可根據(jù)具體情況，將搜索空間限定于一定的范圍內(nèi)，粒子的位移內(nèi)。</p><p>　?。?）代溝G。這里我們由父代生成子代過(guò)程中，不是單純地直接遺傳，而是進(jìn)行兩次遺傳操作。將當(dāng)前群體Mi作為父代，對(duì)父代Mi進(jìn)行遺傳操作（交叉、變異）產(chǎn)生群體大小相同的子代Mi1，在對(duì)父代Mi和子代Mi1按適應(yīng)度值大小降序排列，將種群Mi和Mi1

46、中前1/2的較好個(gè)體整合成一個(gè)種群Mx2，對(duì)種群Mx2進(jìn)行遺傳操作（交叉、變異）產(chǎn)生群體大小相同的孫代Mi2。由此得到3個(gè)群體大小相同的種群Mi、Mi1、Mi2。對(duì)3個(gè)種群按適應(yīng)度大小進(jìn)行降序排列，用Mi1、Mi2中前1/3的個(gè)體（即最好的M/3個(gè)個(gè)體）淘汰Mi中后2/3的個(gè)體，新形成的種群Mx3，將種群Mx3作為子代種群Mi+1。</p><p>　　三．算法的發(fā)展與展望</p><p>

47、;　　算法的展望與發(fā)展-----------粒子群優(yōu)化算法自提出以來(lái)，得到了國(guó)際上相關(guān)領(lǐng)域眾多學(xué)者的關(guān)注和研究，成為國(guó)際化計(jì)算研究的熱點(diǎn)。目前，PSO出現(xiàn)了多種改進(jìn)算法，且已經(jīng)應(yīng)用于許多科學(xué)和工程領(lǐng)域，特別是在非線(xiàn)性規(guī)劃等領(lǐng)域的應(yīng)用。</p><p>　　算法的發(fā)展趨勢(shì)----------縱觀(guān)國(guó)內(nèi)外粒子群優(yōu)化算法的研究和應(yīng)用現(xiàn)狀，本人歸納了粒子群優(yōu)化算法的發(fā)展趨勢(shì)：</p><p><

48、;b>　　1.算法的理論分析</b></p><p>　　雖然粒子群算法在實(shí)際應(yīng)用中被證明是有效的，但其算法分析還不夠成熟和系統(tǒng)。利用有效數(shù)學(xué)工具對(duì)算法的收斂性，收斂速度，參數(shù)選擇以及參數(shù)魯棒性等進(jìn)行分析將是未來(lái)的發(fā)展趨勢(shì)之一。</p><p><b>　　2.算法的改進(jìn)</b></p><p>　　目前對(duì)算法的改進(jìn)主要有兩個(gè)

49、方面：預(yù)期它理論結(jié)合改進(jìn)和與其它算法結(jié)合改進(jìn)。</p><p>　　已有的協(xié)同PSO（CPSO）算法、隨機(jī)PSO（SPSO）算法、有拉伸功能的PSO算法、耗散PSO（DPSO）算法都是與其它領(lǐng)域的結(jié)合改進(jìn)，而混合PSO（HPSO）算法、雜交PSO算法、基于模擬退火的PSO算法、免疫PSO算法、自適應(yīng)變異的PSO（AMPSO）算法都是與其它算法結(jié)合。</p><p>　　今后的改進(jìn)方向仍以提

50、高算法的性能為目的，提高收斂精度和速度，增強(qiáng)全局搜索能力等。另外，與其它各種智能方法和先進(jìn)技術(shù)的融合還不足，粒子群優(yōu)化算法必將通過(guò)與其它優(yōu)化算法相比較，將其優(yōu)點(diǎn)與自身優(yōu)點(diǎn)相結(jié)合，揚(yáng)長(zhǎng)避短。</p><p><b>　　3.算法的應(yīng)用</b></p><p>　　由于PSO算法具有計(jì)算速度快，概念簡(jiǎn)明，依賴(lài)的經(jīng)驗(yàn)參數(shù)少，實(shí)現(xiàn)方便等特點(diǎn)它已成為應(yīng)用于諸多領(lǐng)域，特別是優(yōu)化問(wèn)

51、題的求解，又粒子群優(yōu)化算法中的微粒速度和位置都是連續(xù)變量，能夠直接應(yīng)用于連續(xù)優(yōu)化問(wèn)題，而對(duì)于非線(xiàn)性規(guī)劃這類(lèi)問(wèn)題，需要做一些調(diào)整和改變才能應(yīng)用PSO求解。算法的研究最終是為了應(yīng)用，而應(yīng)用又反作用于算法的研究，對(duì)深化算法有非常重要的意義。粒子群優(yōu)化算法是一種新興的基于群體智能的進(jìn)化算法，與遺傳算法和模擬退火算法相比，PSO算法缺乏系統(tǒng)的理論分析方法，其數(shù)學(xué)基礎(chǔ)相對(duì)薄弱，且還存在許多不完善和未涉及到的問(wèn)題，在收斂性理論、計(jì)算性能、實(shí)現(xiàn)技術(shù)和參

52、數(shù)的設(shè)置等方面缺乏嚴(yán)密的數(shù)學(xué)基礎(chǔ)，其應(yīng)用大多數(shù)仍然依靠經(jīng)驗(yàn)和實(shí)驗(yàn)，對(duì)具體問(wèn)題和應(yīng)用環(huán)境的依賴(lài)性比較大，如何將PSO算法應(yīng)用與離散、多目標(biāo)、約束、不確定、動(dòng)態(tài)等優(yōu)化問(wèn)題將是粒子群優(yōu)化算法的主要研究方向。然而，就非線(xiàn)性規(guī)劃領(lǐng)域而言，其研究的復(fù)雜問(wèn)題有多種解法，在其中選擇合適的仍沒(méi)有一套系統(tǒng)的理論和方法。如何選擇、優(yōu)化和、調(diào)整PSO算法參數(shù)，使得PSO算法既能避免早熟又能比較快速的收斂，較好地應(yīng)用于生產(chǎn)調(diào)度這類(lèi)組合優(yōu)化問(wèn)題必將有著十分重要的意

53、義。</p><p><b>　　四． 結(jié)論</b></p><p>　　本文詳細(xì)介紹了非線(xiàn)性規(guī)劃、粒子群算法和傳統(tǒng)非線(xiàn)性規(guī)劃的基本理論。分析了傳統(tǒng)非線(xiàn)性規(guī)劃的兩個(gè)致命缺陷：一是容易陷入局部最優(yōu)解，二是對(duì)初始值敏感。詳細(xì)介紹了粒子群算法的優(yōu)點(diǎn)：簡(jiǎn)單，通用，魯棒性強(qiáng)，不要求目標(biāo)函數(shù)可導(dǎo)，是一種由局部最優(yōu)到全局搜索算法。由此我們意識(shí)到將粒子群算法應(yīng)用于非線(xiàn)性規(guī)劃是提高求解

54、效果的有效途徑。在充分理解粒子群算法基本理論，算法思想，關(guān)鍵技術(shù)的基礎(chǔ)上，結(jié)合實(shí)際情況，設(shè)計(jì)并最終實(shí)現(xiàn)了基于粒子群算法的非線(xiàn)性規(guī)劃求解過(guò)程。同時(shí)我們也通過(guò)實(shí)例并實(shí)現(xiàn)了最經(jīng)典的傳統(tǒng)非線(xiàn)性規(guī)劃——牛頓法。通過(guò)比較兩種算法的實(shí)際運(yùn)行結(jié)果，分析兩者之間的性能差異。</p><p>　　通過(guò)理論分析以及對(duì)測(cè)試數(shù)據(jù)的統(tǒng)計(jì)分析，我們可以看到基于粒子群算法的聚類(lèi)分析算法與傳統(tǒng)聚類(lèi)分析算法相比，聚類(lèi)效果整體性較好，聚類(lèi)結(jié)果更合理，

55、性能更穩(wěn)定，魯棒性強(qiáng)，受隨機(jī)因素影響小，有效地克服了傳統(tǒng)算法受隨機(jī)因素影響較大，容易陷入局部最優(yōu)解的缺陷。但遺傳算法程序設(shè)計(jì)復(fù)雜，算法耗費(fèi)大量存儲(chǔ)空間和運(yùn)行時(shí)間。但在硬件成本大幅下降的今天，用空間和時(shí)間換取最佳結(jié)果是值得的。傳統(tǒng)算法程序簡(jiǎn)單，易于實(shí)現(xiàn)，耗費(fèi)資源少，但聚類(lèi)效果較差，性能不穩(wěn)定，受隨機(jī)因素影響較大，容易陷入局部最優(yōu)解。同時(shí)我們也看到，有時(shí)候傳統(tǒng)算法所得結(jié)果比遺傳算法要好，這說(shuō)明傳統(tǒng)算法也有其可取之處，遺傳算法無(wú)法完全取代傳統(tǒng)

56、算法。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 董穎，唐加福，許寶棟，汪定偉.東北大學(xué)學(xué)報(bào)（自然科學(xué)版）[J]，2003:2-6</p><p>　　[2] 梁軍.粒子群算法在最優(yōu)化問(wèn)題的研究[J].廣西師范大學(xué).2008：30-99</p><p>　　[3] 趙瑞安，吳方著.非線(xiàn)性最

57、優(yōu)化理論和方法[M] .浙江：浙江科學(xué)技術(shù)出版社，1992：1-41</p><p>　　[4] 朱儒，黃皓，朱開(kāi)水.非線(xiàn)性規(guī)劃[M] .北京：中國(guó)礦業(yè)大學(xué)出版社，1990：79-210</p><p>　　[5] 趙瑞安，吳方.非線(xiàn)性最優(yōu)化理論和方法[M] .北京：浙江科學(xué)技術(shù)出版社</p><p>　　[6]陸林花,王波.一種改進(jìn)的遺傳聚類(lèi)算法[J].計(jì)算機(jī)工程

58、與應(yīng)用,2007,43(21):170～172</p><p>　　[7]阮飛鵬，王冬利，陳學(xué)理.遺傳算法在聚類(lèi)分析中的應(yīng)用[J].中國(guó)水運(yùn),2007,2(07):241～242</p><p>　　[8]陳國(guó)良,王熙法,莊鎮(zhèn)泉,王東生.遺傳算法及其應(yīng)用[M].北京:人民郵電出版社,1996</p><p>　　[9]Holland J H.Adaptation i