一種基于動態(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ù)求解空間問題時均表現(xiàn)出較好的全局搜索能力。但是，在實際應(yīng)用過程中人們也發(fā)現(xiàn)，對于標(biāo)準(zhǔn)的全局粒子群算法(使用星形拓?fù)浣Y(jié)構(gòu)的粒子群算法)，由于進(jìn)化過程中種群多樣性損失過快，粒子群算法易于陷入局部極值

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

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

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

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