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

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

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

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

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

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

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

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

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

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

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

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

相關(guān)碩士學(xué)位論文 前2條

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

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

，

本文編號(hào)：2673455