廣義粒子群優(yōu)化算法及其在作業(yè)車間調(diào)度中的應(yīng)用研究

《廣義粒子群優(yōu)化算法及其在作業(yè)車間調(diào)度中的應(yīng)用研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、華中科技大學(xué)碩士學(xué)位論文1.2國內(nèi)外研究現(xiàn)狀1.2.1基本粒子群優(yōu)化算法由螞蟻、蜜蜂等生物組成的群體，雖然個(gè)體的智能不高，但在一定內(nèi)在規(guī)律的作用下，整個(gè)群體卻表現(xiàn)出異常復(fù)雜而有序的行為來，群體智能(SwarmIntelligence)正是在對(duì)這些生物群體行為的觀察和研究中得到的[1]。群體智能中的群體指的是一組相互之間可以進(jìn)行直接或者間接通信的主體，這組主體能夠合作進(jìn)行分布式問題的求解。群體智能具有協(xié)作性、分布性、魯棒性和快速性的特點(diǎn)，這使其在沒有全局信息的情況下，為尋找復(fù)雜問題的解決方案提供了新的途徑。群體智能領(lǐng)域主要有兩種優(yōu)化方法：粒子群優(yōu)

2、化和蟻群優(yōu)化[2]。粒子群優(yōu)化算法(ParticleSwarmOptimization,PSO)是由Kennedy和Eberhart于1995年提出的[3][4]，它源于對(duì)鳥群運(yùn)動(dòng)行為的研究。生物學(xué)家FrankHeppner建立了這樣的鳥群運(yùn)動(dòng)模型：一群小鳥在空中漫無目的地飛行，當(dāng)群體中的一只小鳥發(fā)現(xiàn)棲息地時(shí)，它會(huì)飛向這個(gè)棲息地，同時(shí)也會(huì)將它周圍的小鳥吸引過來，而它周圍的這些鳥也將影響群體中其它的小鳥，最終將整個(gè)鳥群引向這個(gè)棲息地。Kennedy和Eberhart從這個(gè)模型中得到啟發(fā)，將模型中的棲息地類比為所求問題解空間中可能解的位置，群體中的

3、小鳥被抽象為一個(gè)個(gè)沒有質(zhì)量和形狀的粒子，通過這些粒子之間的相互協(xié)作和信息共享，引導(dǎo)整個(gè)粒子群向可能解的方向移動(dòng)，從而在復(fù)雜的解空間中尋找最優(yōu)的解。粒子群優(yōu)化算法是一種基于種群的進(jìn)化計(jì)算技術(shù)，系統(tǒng)初始化為一組隨機(jī)解，稱之為粒子。每個(gè)粒子都有一個(gè)由被優(yōu)化的函數(shù)決定的適應(yīng)值，每個(gè)粒子通過一個(gè)速度來決定它們飛翔的方向和距離。在每一次迭代中，粒子通過跟蹤兩個(gè)極值來更新自己，第一個(gè)極值是粒子自身所找到的最優(yōu)解，稱為個(gè)體極值；另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解，稱為全局極值。粒子群優(yōu)化算法的基本概念定義如下：定義1粒子類似于遺傳算法中的染色體，PSO中粒子

4、為基本的組成單位，代表解空間的一個(gè)候選解。設(shè)解向量為d維變量，則當(dāng)算法迭代次數(shù)為t時(shí)，第i個(gè)粒子x(t)可表示為ix(t)=[x(t),x(t),...,x(t)]。其中x(t)表示第i個(gè)粒子在第k維解空間中的位置。ii1i2idik定義2種群種群由n個(gè)粒子組成，代表n個(gè)候選解。經(jīng)過t次迭代產(chǎn)生的種群表示為2華中科技大學(xué)碩士學(xué)位論文pop(t)=[x(t),x(t),...,x(t),...,x(t)]，其中x(t)為種群中的第i個(gè)粒子。12ini定義3粒子速度粒子速度表示為v(t)=[v(t),v(t),...,v(t)]，代表粒子在單次迭代

5、中位置的變化。ii1i2id其中，v(t)為第i個(gè)粒子在第k維的速度值。ik定義4適應(yīng)值適應(yīng)值由優(yōu)化目標(biāo)決定，用于評(píng)價(jià)粒子的搜索性能，指導(dǎo)整個(gè)種群的搜索。算法迭代停止時(shí)適應(yīng)值最優(yōu)的解變量即為優(yōu)化搜索的最優(yōu)解。定義5個(gè)體極值個(gè)體極值p=(p,p,...,p)表示第i個(gè)粒子從搜索開始到當(dāng)前迭代時(shí)找到的適應(yīng)ii1i2id值最優(yōu)的解。定義6全局極值全局極值g=(g,g,...,g)是整個(gè)種群從搜索開始到當(dāng)前迭代時(shí)找到的適應(yīng)值最優(yōu)12d的解。在每一次迭代中，粒子通過個(gè)體極值與全局極值更新自身的速度和位置，迭代公式如下：v=v+c×rand×p?x+c×R

6、and×p?x(0.1)1()()2()()iiiigix=x+v(0.2)iii其中rand()和Rand()是均勻分布在[0,1]之間的隨機(jī)數(shù)。c和1c是學(xué)習(xí)因子，通2常c1=c2=2[5]。粒子在每一維飛行的速度不能超過算法設(shè)定的最大速度值v，設(shè)置max較大的v可以保證粒子種群的全局搜索能力，v較小則粒子種群的局部搜索能力加maxmax強(qiáng)。基本粒子群優(yōu)化算法的流程如圖1-1所示。3華中科技大學(xué)碩士學(xué)位論文種群初始化計(jì)算每個(gè)粒子的適應(yīng)值根據(jù)粒子的適應(yīng)值更新個(gè)體極值與全局極值根據(jù)迭代公式更新粒子的速度與位置No是否達(dá)到停止準(zhǔn)則？Yes輸出最優(yōu)

7、解圖1-1粒子群優(yōu)化算法流程圖與遺傳算法相比，粒子群優(yōu)化算法保留了基于種群的全局搜索策略，但是其采用的速度－位移模型操作簡單，避免了復(fù)雜的遺傳操作。其特有的記憶機(jī)制使其可以根據(jù)當(dāng)前的搜索情況動(dòng)態(tài)調(diào)整搜索策略。與遺傳算法相比，粒子群優(yōu)化算法是一種更高效的并行搜索算法。1.2粒子群優(yōu)化算法的發(fā)展1.2.1帶慣性權(quán)重的粒子群優(yōu)化算法公式(0.1)的右邊由三部分組成，第一部分是粒子上一次迭代的速度值，后兩部分反映了粒子速度的更新。Shi與Eberhart研究發(fā)現(xiàn)[6]，公式(0.1)的第一部分v使粒子具i有隨機(jī)性，整個(gè)種群有擴(kuò)大搜索空間、搜索新區(qū)域的趨

8、勢(shì)。在考慮實(shí)際優(yōu)化問題時(shí)，往往希望先采用全局搜索，使搜索空間快速收斂于某一區(qū)域，然后采用局部搜索以獲得高精度的解。因此，在公式(0.1)的v前乘以慣性