一種基于動(dòng)態(tài)群體結(jié)構(gòu)的粒子群算法及其在啤酒分配游戲中的應(yīng)用研究.pdf

1、粒子群優(yōu)化算法作為一種新的智能優(yōu)化算法，由于其收斂速度快、參數(shù)設(shè)置少，近年來受到眾多學(xué)者的研究和重視。它常被用于解決大量非線性、不光滑和多峰值的復(fù)雜問題優(yōu)化，現(xiàn)己廣泛應(yīng)用于許多科學(xué)和工程領(lǐng)域。大量的研究結(jié)果表明，粒子群算法在解決離散求解空間和連續(xù)求解空間問題時(shí)均表現(xiàn)出較好的全局搜索能力。但是，在實(shí)際應(yīng)用過程中人們也發(fā)現(xiàn)，對(duì)于標(biāo)準(zhǔn)的全局粒子群算法(使用星形拓?fù)浣Y(jié)構(gòu)的粒子群算法)，由于進(jìn)化過程中種群多樣性損失過快，粒子群算法易于陷入局部極值

2、，引起算法過早收斂。而對(duì)于局部?jī)?yōu)化粒子群算法(使用環(huán)形拓?fù)浣Y(jié)構(gòu)的粒子群算法)，粒子群算法收斂速度較慢，需要對(duì)目標(biāo)函數(shù)進(jìn)行大量次數(shù)的評(píng)價(jià)。
　　 針對(duì)這個(gè)問題，本文提出了基于動(dòng)態(tài)更新群體拓?fù)浣Y(jié)構(gòu)的新算法。種群拓?fù)浣Y(jié)構(gòu)是指整個(gè)種群所有粒子之間的連接方式。粒子群算法是一種隨機(jī)性智能搜索算法，算法成功的關(guān)鍵在于能否有效地在早期全局開拓與晚期局部搜索解空間之間進(jìn)行平衡。由于種群的拓?fù)浣Y(jié)構(gòu)決定了信息在整個(gè)種群?jiǎn)柕牧鲃?dòng)速度，而信息流動(dòng)的速度可

3、以用來控制算法的探測(cè)和開發(fā)能力。目前最普遍使用的拓?fù)浣Y(jié)構(gòu)是星形和環(huán)形。在星形拓?fù)浣Y(jié)構(gòu)下，每個(gè)粒子都與其他粒子相連接，因此信息流動(dòng)最快，導(dǎo)致了粒子群算法收斂過快，出現(xiàn)“早熟”現(xiàn)象。而在環(huán)形拓?fù)浣Y(jié)構(gòu)下，每個(gè)粒子僅與相鄰的兩個(gè)粒子相連接，因此信息流通非常慢，最終導(dǎo)致使用該拓?fù)浣Y(jié)構(gòu)的粒子群算法收斂速度慢。因此，我們可以說星形和環(huán)形結(jié)構(gòu)代表了信息流通速度的兩個(gè)極端。但是我們不難發(fā)現(xiàn)環(huán)形結(jié)構(gòu)滿足了該算法早期對(duì)空間進(jìn)行全局解空間探索的要求，而星形結(jié)構(gòu)

4、恰恰滿足了該算法晚期對(duì)搜索空間進(jìn)行局部開發(fā)的要求。因此如果能夠動(dòng)態(tài)地改變拓?fù)浣Y(jié)構(gòu)將是一個(gè)有效的平衡探測(cè)和開發(fā)的要求，基于這個(gè)想法，本文提出了動(dòng)態(tài)增加每個(gè)粒子連接個(gè)數(shù)的方法來改變?nèi)后w的拓?fù)浣Y(jié)構(gòu)。本文還調(diào)查了增加的速度對(duì)算法的影響。通過對(duì)一系列經(jīng)典優(yōu)化函數(shù)進(jìn)行測(cè)試，驗(yàn)證了本文提出算法的有效性。
　　 本文的另一個(gè)重要研究方面是把粒子群算法應(yīng)用到供應(yīng)鏈管理領(lǐng)域。本文以啤酒分配游戲?yàn)槔芯苛嗽撍惴ㄔ诠?yīng)鏈管理中的潛在應(yīng)用。啤酒分配游戲是

5、上世紀(jì)60年代在MIT開發(fā)的，代表了一類典型的供應(yīng)鏈管理優(yōu)化問題。這個(gè)游戲提供了一個(gè)復(fù)雜的模擬環(huán)境，并涉及了多維受限制的參數(shù)。傳統(tǒng)上，啤酒分配游戲的研究都是基于一個(gè)簡(jiǎn)單的客戶需求。本文設(shè)計(jì)了其它三種更為復(fù)雜的客戶需求。另外，對(duì)每一種客戶需求，我們還研究了兩種不同的場(chǎng)景。在第一種場(chǎng)景下，所有啤酒分配游戲的角色都使用相同的策略管理他們的庫(kù)存。在第二種場(chǎng)景下，不同的角色允許使用不同的策略。從優(yōu)化的角度來說，由于第二種場(chǎng)景設(shè)計(jì)更多的參數(shù)，因此也