裝箱問(wèn)題的求解與應(yīng)用可以為物流和倉(cāng)儲(chǔ)等行業(yè)提供高效便利的服務(wù),然而由于裝箱問(wèn)題的復(fù)雜性以及裝箱算法的非普適性,使得裝箱問(wèn)題和裝箱算法的研究成為需要解決的實(shí)際問(wèn)題。概念簡(jiǎn)單、容易實(shí)現(xiàn)且具有能背景的粒子群算法在求解裝箱問(wèn)題中受到了廣泛的關(guān)注。作為組合優(yōu)化問(wèn)題中的典型問(wèn)題,裝箱問(wèn)題的研究在實(shí)際應(yīng)用和理論研究方面具有重要意義,具有廣闊的研究前景。本文主要對(duì)粒子群算法的外部參數(shù)和內(nèi)部拓?fù)浣Y(jié)構(gòu)進(jìn)行改進(jìn),然后與啟發(fā)式算法相結(jié)合,得到混合啟發(fā)式算法用以求解裝箱問(wèn)題。本文的主要工作及結(jié)論概括如下:1、基于離散問(wèn)題對(duì)粒子群算法外部參數(shù)進(jìn)行調(diào)整,采用慣性權(quán)重隨機(jī)遞減,學(xué)習(xí)因子c1線性遞增,c2線性遞減的方式改進(jìn)算法性能,能到求解裝箱問(wèn)題最優(yōu)的參數(shù)設(shè)置,比傳統(tǒng)粒子群算法的收斂速度提高了86%,與WPSO算法相比收斂速度提高了36%。2、對(duì)粒子群算法內(nèi)部拓?fù)浣Y(jié)構(gòu)進(jìn)行改進(jìn),采用雙判斷的方式,在粒子調(diào)整前與粒子調(diào)整后均進(jìn)行適應(yīng)度判斷的方式構(gòu)造動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu),實(shí)現(xiàn)動(dòng)態(tài)粒子群算法改進(jìn)。改進(jìn)粒子群算法迭代500次的實(shí)驗(yàn)中,平均30次可以求得最優(yōu)解,而其它算法分別在90,1 20,150才能得到最優(yōu)解,提高了算法的收斂速度。... 

【文章來(lái)源】：西安理工大學(xué)陜西省

【文章頁(yè)數(shù)】：44 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

改進(jìn)粒子群算法流程圖

西安理工大學(xué)工程碩士專業(yè)學(xué)位論文10圖2-2三種算法求解0-1背包問(wèn)題的迭代過(guò)程Fig.2-2Iterativeprocessofthreealgorithmsforsolving0-1knapsackproblem分析表2-1和圖2-2可知，三種算法在最大迭代次數(shù)內(nèi)都可找到0-1背包問(wèn)題的最優(yōu)解，但改進(jìn)粒子群算法相比其它兩種算法可以更快的求得最優(yōu)解，收斂性較好，改進(jìn)粒子群算法與傳統(tǒng)粒子群算法比較收斂速度提高了86%，與WPSO算法相比收斂速度提高了36%。通過(guò)比較最優(yōu)迭代次數(shù)和最差迭代次數(shù)可知，本文改進(jìn)的算法穩(wěn)定性優(yōu)于其它兩種算法，更適合求解背包問(wèn)題。2.4本章小結(jié)本章主要對(duì)標(biāo)準(zhǔn)PSO算法進(jìn)行參數(shù)改進(jìn)，將PSO算法中慣性權(quán)重隨機(jī)遞減的變化方式與學(xué)習(xí)因子c1線性遞減、c2線性遞增相結(jié)合，用于求解離散問(wèn)題并取得不錯(cuò)的效果。實(shí)驗(yàn)采用背包問(wèn)題作為測(cè)試函數(shù)，與標(biāo)準(zhǔn)PSO算法，WPSO算法完成參數(shù)對(duì)比。結(jié)果顯示，作者改進(jìn)的PSO算法具有非常快的收斂速度效果。

西安理工大學(xué)工程碩士專業(yè)學(xué)位論文12在連接網(wǎng)圖中，節(jié)點(diǎn)i和j之間的最短路徑的邊數(shù)叫做節(jié)點(diǎn)i到j(luò)的距離。平均路徑長(zhǎng)度是所有結(jié)點(diǎn)之間距離的平均值，它用于測(cè)量粒子間的信息交換速率，具體的計(jì)算如式所示：jiijsNN)1(2L（3-2）式中：sij——節(jié)點(diǎn)i和j的距離；L——平均路徑長(zhǎng)度。(3)平均聚類系數(shù)聚類系數(shù)為個(gè)別部分的以節(jié)點(diǎn)為主要面向?qū)ο蟮�，就�?jié)點(diǎn)i而言，將其相鄰的節(jié)點(diǎn)集合ki找出，對(duì)其網(wǎng)絡(luò)結(jié)構(gòu)里面的邊數(shù)Ei進(jìn)行求取，再除以集合ki可能具有的邊的數(shù)量，即2/)1(iikk。見下圖3-1：一節(jié)點(diǎn)相鄰的節(jié)點(diǎn)）（2,3，二者構(gòu)成邊的數(shù)量為1，會(huì)形成1條邊，所以1=1/1，兩節(jié)點(diǎn)相鄰的節(jié)點(diǎn)為）（1,3，二者構(gòu)成邊的數(shù)量為1，會(huì)形成1條邊，所以1=1/1是，三節(jié)點(diǎn)相鄰的節(jié)點(diǎn)為）（1,2,4,5，其構(gòu)成邊的數(shù)量為1，會(huì)形成）（/234條邊，所以1/6=1/6，四節(jié)點(diǎn)相鄰的節(jié)點(diǎn)為）（3，其無(wú)法構(gòu)成邊，會(huì)構(gòu)成0條邊，所以0，五節(jié)點(diǎn)相鄰的節(jié)點(diǎn)為）（3，其無(wú)法構(gòu)成邊，會(huì)構(gòu)成0條邊，所以0。因此，節(jié)點(diǎn)為五時(shí)對(duì)應(yīng)的聚類系數(shù)為(1+1+1/6)/5=13/30。圖3-1節(jié)點(diǎn)連接圖Fig.3-1Nodeconnectiondiagram)1i(i2kkEiCi（3-3）式中：Ci——聚類系數(shù)；ki——粒子i鄰居粒子個(gè)數(shù)；Ei——ki個(gè)鄰居粒子在搜索空間中實(shí)際存在的邊數(shù)。NiiCNC11（3-4）式中：C——平均聚類系數(shù)；

【參考文獻(xiàn)】：
期刊論文
[1]高效求解三維裝箱問(wèn)題的剩余空間最優(yōu)化算法[J]. 尚正陽(yáng),顧寄南,唐仕喜,孫曉紅.  計(jì)算機(jī)工程與應(yīng)用. 2019(05)
[2]一種自適應(yīng)權(quán)重的并行PSO快速裝箱算法[J]. 廖星,袁景凌,陳旻騁.  計(jì)算機(jī)科學(xué). 2018(03)
[3]基于動(dòng)態(tài)加速因子的粒子群優(yōu)化算法研究[J]. 滕志軍,呂金玲,郭力文,王志新,許恒,袁麗紅.  微電子學(xué)與計(jì)算機(jī). 2017(12)
[4]有向動(dòng)態(tài)拓?fù)浠旌献饔昧ξ⒘Ｈ簝?yōu)化算法及可靠性應(yīng)用[J]. 姚成玉,趙哲諭,陳東寧,檀雪云,呂世君.  機(jī)械工程學(xué)報(bào). 2017(10)
[5]基于分類學(xué)習(xí)粒子群優(yōu)化算法的液壓矯直機(jī)控制[J]. 張凱,宋錦春,李松,時(shí)佳.  機(jī)械工程學(xué)報(bào). 2017(18)
[6]Dynamic Topology Multi Force Particle Swarm Optimization Algorithm and Its Application[J]. CHEN Dongning,ZHANG Ruixing,YAO Chengyu,ZHAO Zheyu.  Chinese Journal of Mechanical Engineering. 2016(01)
[7]基于自適應(yīng)搜索中心的骨干粒子群算法[J]. 王東風(fēng),孟麗,趙文杰.  計(jì)算機(jī)學(xué)報(bào). 2016(12)
[8]自適應(yīng)小世界粒子群優(yōu)化算法[J]. 龔月姣,嵇智源.  計(jì)算機(jī)工程與設(shè)計(jì). 2015(06)
[9]單一尺寸長(zhǎng)方體三維裝箱問(wèn)題的一種求解算法[J]. 王巖,潘衛(wèi)平,陳秋蓮,崔耀東.  包裝工程. 2015(11)
[10]求解三維裝箱問(wèn)題的啟發(fā)式正交二叉樹搜索算法[J]. 劉勝,朱鳳華,呂宜生,李元濤.  計(jì)算機(jī)學(xué)報(bào). 2015(08)

碩士論文
[1]價(jià)值可變的0-1多背包問(wèn)題模型及其優(yōu)化算法研究[D]. 張悅.北京交通大學(xué) 2017
[2]基于混合遺傳算法的集裝箱船三維裝箱問(wèn)題研究[D]. 朱瑩.華中科技大學(xué) 2016
[3]基于文化算法的三維裝箱問(wèn)題研究[D]. 章翼.太原理工大學(xué) 2014
[4]滾裝船舶配載優(yōu)化問(wèn)題的研究[D]. 金燕燕.大連海事大學(xué) 2011
[5]混合遺傳算法在集裝箱船舶配載中的應(yīng)用[D]. 史宗耀.長(zhǎng)春理工大學(xué) 2010



本文編號(hào)：2996488