發(fā)布時間：2020-05-21 00:37

【摘要】：容量約束P-中位問題(Capacitated P-Median Problem,CPMP)是一類由圖演變的組合優(yōu)化問題。CPMP在實際生產(chǎn)中有著廣泛的應用背景,且已被證明是具有NP-hard特征的難解問題,隨著問題規(guī)模增加,其時間計算復雜性呈指數(shù)級增長,精確的數(shù)學方法只能求解較小規(guī)模CPMP,而基于群搜索的啟發(fā)式算法在求解大規(guī)模CPMP具有優(yōu)勢。粒子群優(yōu)化算法(Particle Swarm Optimization,PSO)算法是一種模擬自然界鳥群活動及群體智能的隨機搜索算法。該算法具有操作簡單、易于實現(xiàn)、收斂速度快等優(yōu)點。本文對CPMP及其特征進行分析,在標準粒子群優(yōu)化算法基礎上進行離散化改進,并在算法中增加不同的啟發(fā)式策略,形成兩種新的離散粒子群優(yōu)化算法。為驗證所提算法的性能,將算法用于求解一些公開CPMP數(shù)據(jù)集,并與一些知名算法測試結果進行對比分析。本文主要工作包括:(1)提出一種改進的離散粒子群優(yōu)化算法(Improved Discrete Particle Swarm Optimization Algorithm,IDPSO)求解CPMP。在所提算法中,考慮CPMP的求解可分解為中位點選取和需求點分配兩階段。在算法中去掉速度更新操作,引進遺傳算法的交叉、變異算子操作,增加粒子中位點在全局范圍內的重組。在算法中加入變鄰域局部搜索過程提升粒子質量,并設計了模擬退火接受機制用于保持種群多樣性。最后將所提算法應用到20個公開CPMP測試用例中測試,并將實驗數(shù)據(jù)與幾種文獻啟發(fā)式算法得到的結果進行對比分析。(2)提出一種基于多啟發(fā)式離散粒子群優(yōu)化算法(Multiheuristics Discrete Particle Swarm Optimization,MDPSO)。在所提算法中,重新定義了粒子速度和位置更新方式�？紤]CPMP的求解困難在于中位點的調整和變化,在算法中對中位點搜索采用了全局中位點選擇,局部中位點調整以及深層次中位點調整方式,在算法中加入聚類思想對中位點擇優(yōu)選擇操作、對需求點分配與調整局部搜索算子操作,使算法從多個維度達到對粒子中位點和需求點的選擇和分配進行優(yōu)化。最后,將所提算法應用于求解公開的20個小規(guī)模測試用例和6個較大規(guī)模測試用例,并與文獻知名算法測試結果進行對比。綜上,通過分析CPMP在求解中所表現(xiàn)的特征,設計了兩種基于不同啟發(fā)式信息的離散粒子群算法,理論分析和實驗測試驗證了所提算法的正確性和有效性。
【學位授予單位】：西安理工大學
【學位級別】：碩士
【學位授予年份】：2018
【分類號】：TP18

【參考文獻】

相關期刊論文 前10條

1 孫文彬;閆志遠;趙學勝;;基于網(wǎng)絡分割的P-中位問題求解方法[J];中國礦業(yè)大學學報;2016年06期

2 李倩;張惠珍;Cesar Beltran-Royo;;帶投資約束p-中位問題的混合蟻群算法[J];計算機應用研究;2017年06期

3 黃利;杜偉偉;丁立新;;基于Sigmoid慣性權重自適應調整的粒子群優(yōu)化算法[J];計算機應用研究;2012年01期

4 徐先瑞;李響;李小杰;;改進的求解約束P-Median問題的分散搜索算法[J];計算機工程與應用;2011年20期

5 遲玉紅;孫富春;王維軍;喻春明;;基于空間縮放和吸引子的粒子群優(yōu)化算法[J];計算機學報;2011年01期

6 李芬;徐國虎;;基于遺傳算法的配送中心選址問題求解[J];商品儲運與養(yǎng)護;2007年03期

7 李有梅,陳曄;一種新的求解約束P-中位問題的啟發(fā)式算法[J];計算機工程;2005年19期

8 竇全勝,周春光,馬銘;粒子群優(yōu)化的兩種改進策略[J];計算機研究與發(fā)展;2005年05期

9 李寧,劉飛,孫德寶;基于帶變異算子粒子群優(yōu)化算法的約束布局優(yōu)化研究[J];計算機學報;2004年07期

10 高鷹,謝勝利;免疫粒子群優(yōu)化算法[J];計算機工程與應用;2004年06期

相關碩士學位論文 前2條

1 路鳳敏;幾種離散選址模型的算法研究[D];南京航空航天大學;2010年

2 吳仆;設施選址中的一些模型與算法[D];南京航空航天大學;2010年

，

本文編號：2673455