本文選題：粒子群算法 + 旅行商問(wèn)題�。� 參考：《江南大學(xué)》2017年碩士論文

【摘要】：粒子群優(yōu)化算法(Particle Swarm Optimization,簡(jiǎn)稱(chēng)PSO)是一種基于群體的進(jìn)化算法,是一種有效的全局優(yōu)化算法。PSO因?qū)崿F(xiàn)簡(jiǎn)單、需要調(diào)整的參數(shù)少、收斂速度快等優(yōu)點(diǎn)被廣泛應(yīng)用于函數(shù)優(yōu)化、數(shù)據(jù)挖掘及電力系統(tǒng)等領(lǐng)域。旅行售貨商問(wèn)題(Traveling Salesman Problem,簡(jiǎn)稱(chēng)TSP)是運(yùn)籌學(xué)中的經(jīng)典組合優(yōu)化問(wèn)題之一,已被證明為NP完全問(wèn)題。它綜合了一大類(lèi)組合優(yōu)化問(wèn)題的典型特征,并以不同的形式存在于交通運(yùn)輸、印制電路板及數(shù)據(jù)串聚類(lèi)等許多領(lǐng)域。通過(guò)對(duì)PSO算法和TSP的分析和研究,本文提出了三種改進(jìn)的粒子群優(yōu)化算法:基于優(yōu)秀系數(shù)的局部搜索混沌離散粒子群優(yōu)化算法(ILCDPSO)、基于自適應(yīng)優(yōu)秀系數(shù)的粒子群算法(SECPSO)以及基于柯西分布和3-opt的自適應(yīng)粒子群算法(SCLPSO)。用TSPLIB中的經(jīng)典測(cè)試案例對(duì)這些算法進(jìn)行了測(cè)試,并與其他算法的求解結(jié)果進(jìn)行了比較。文章的主要工作概括如下:(1)針對(duì)基本離散粒子群算法收斂速度慢、易于陷入局部最優(yōu)等問(wèn)題,提出了一種基于優(yōu)秀系數(shù)的局部搜索混沌離散粒子群優(yōu)化算法。提出了優(yōu)秀系數(shù)的概念,給每條邊設(shè)定合理的優(yōu)秀系數(shù),以提高短邊被選擇的概率,從而有利于提高算法的尋優(yōu)能力和收斂速度;在算法機(jī)制中添加了局部搜索策略,提高算法的局部搜索能力;另外,在算法的迭代公式中加入了混沌序列來(lái)提高粒子的隨機(jī)性和多樣性,增強(qiáng)算法的全局搜索能力。研究結(jié)果表明,ILCDPSO算法在收斂速度、全局尋優(yōu)能力以及穩(wěn)定性方面均優(yōu)于其他算法。(2)為了利用問(wèn)題領(lǐng)域的啟發(fā)式信息,本文在ILCDPSO算法的基礎(chǔ)上進(jìn)行改進(jìn),提出了一種基于自適應(yīng)優(yōu)秀系數(shù)的粒子群算法(SECPSO)。SECPSO算法對(duì)靜態(tài)的優(yōu)秀系數(shù)進(jìn)行修改,使之可根據(jù)解的搜索過(guò)程進(jìn)行自適應(yīng)動(dòng)態(tài)調(diào)整;另外,為了進(jìn)一步提高解的精確性和算法的收斂速度,添加了3-opt搜索機(jī)制,以提高算法的局部搜索能力。實(shí)驗(yàn)結(jié)果表明,SECPSO算法在全局尋優(yōu)能力和更快的收斂速度方面表現(xiàn)更優(yōu)。(3)為了進(jìn)一步提高SECPSO算法的求解精度和穩(wěn)定性,利用柯西分布對(duì)慣性權(quán)重進(jìn)行了改進(jìn),提出了基于柯西分布和3-opt的自適應(yīng)粒子群算法SCLPSO。加入柯西分布可以使算法在初期階段搜索范圍更廣,并且具有更高的算法穩(wěn)定性。實(shí)驗(yàn)結(jié)果表明SCLPSO算法的收斂次數(shù)比明顯增加,能快速收斂到最優(yōu)解,且收斂精度進(jìn)一步提高,從而算法的綜合性能得到了較大提升。
[Abstract]:Particle Swarm Optimization (PSO) is a group based evolutionary algorithm. It is an effective global optimization algorithm (.PSO), which is widely used in function optimization, data mining and power system, etc. because of its simple implementation, less parameters and faster convergence speed. Traveli Ng Salesman Problem, referred to as TSP), is one of the classical combinatorial optimization problems in operational research. It has been proved to be a complete problem of NP. It combines the typical features of a large class of combinatorial optimization problems and exists in many fields, such as transportation, printed circuit board and data string clustering in a variety of forms. Through the analysis and research of PSO algorithm and TSP, In this paper, three improved particle swarm optimization algorithms are proposed: local search chaotic discrete particle swarm optimization (ILCDPSO) based on excellent coefficients, particle swarm optimization based on adaptive excellent coefficients (SECPSO) and adaptive particle swarm optimization (SCLPSO) based on Cauchy distribution and 3-opt. These algorithms are used in the classical test cases of TSPLIB. The main work of the paper is summarized as follows: (1) in view of the slow convergence speed of the basic discrete particle swarm optimization algorithm and easy to fall into the local optimal problem, a local search chaotic dispersion particle swarm optimization algorithm based on the excellent coefficient is proposed. The concept of the excellent coefficient is proposed. In order to improve the searching ability and convergence speed of the algorithm, the local search strategy is added in the algorithm mechanism to improve the local search ability of the algorithm. In addition, the chaos sequence is added to the iterative formula of the algorithm to improve the randomness of the particle and the randomness of the particle. The results show that the ILCDPSO algorithm is superior to other algorithms in the convergence speed, global optimization ability and stability. (2) in order to use the heuristic information in the problem domain, this paper is modified on the basis of the ILCDPSO algorithm, and proposes a particle based on the adaptive excellent coefficient. The group algorithm (SECPSO).SECPSO algorithm modifies the excellent static coefficient to make adaptive and dynamic adjustment according to the search process of the solution. In addition, in order to further improve the accuracy of the solution and the convergence speed of the algorithm, the 3-opt search mechanism is added to improve the local search ability of the algorithm. The experimental results show that the SECPSO algorithm is all in the whole. (3) in order to further improve the accuracy and stability of the SECPSO algorithm, the Cauchy distribution is used to improve the inertia weight, and an adaptive particle swarm optimization (SCLPSO.) distribution based on Cauchy distribution and 3-opt is proposed to make the algorithm in the initial stage of the search model. The experimental results show that the convergence times of SCLPSO algorithm are significantly increased, and the convergence of the algorithm can be quickly converged to the optimal solution, and the convergence precision is further improved. Thus the comprehensive performance of the algorithm has been greatly improved.
【學(xué)位授予單位】：江南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類(lèi)號(hào)】：TP18

【相似文獻(xiàn)】

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

1 秦玉靈;孔憲仁;羅文波;;混沌量子粒子群算法在模型修正中的應(yīng)用[J];計(jì)算機(jī)工程與應(yīng)用;2010年02期

2 陳治明;;新型量子粒子群算法及其性能分析研究[J];福建電腦;2010年05期

3 牛永潔;;一種新型的混合粒子群算法[J];信息技術(shù);2010年10期

4 全芙蓉;;粒子群算法的理論分析與研究[J];硅谷;2010年23期

5 劉衍民;趙慶禎;邵增珍;;一種改進(jìn)的完全信息粒子群算法研究[J];曲阜師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年01期

6 朱童;李小凡;魯明文;;位置加權(quán)的改進(jìn)粒子群算法[J];計(jì)算機(jī)工程與應(yīng)用;2011年05期

7 熊智挺;譚陽(yáng)紅;易如方;陳賽華;;一種并行的自適應(yīng)量子粒子群算法[J];計(jì)算機(jī)系統(tǒng)應(yīng)用;2011年08期

8 孟純青;;非線(xiàn)性粒子群算法[J];微計(jì)算機(jī)應(yīng)用;2011年08期

9 任偉建;武璇;;一種動(dòng)態(tài)改變學(xué)習(xí)因子的簡(jiǎn)化粒子群算法[J];自動(dòng)化技術(shù)與應(yīng)用;2012年10期

10 劉飛,孫明,李寧,孫德寶,鄒彤;粒子群算法及其在布局優(yōu)化中的應(yīng)用[J];計(jì)算機(jī)工程與應(yīng)用;2004年12期

相關(guān)會(huì)議論文 前10條

1 朱童;李小凡;魯明文;;位置加權(quán)的改進(jìn)粒子群算法[A];中國(guó)科學(xué)院地質(zhì)與地球物理研究所第11屆（2011年度）學(xué)術(shù)年會(huì)論文集(上)[C];2012年

2 陳定;何炳發(fā);;一種新的二進(jìn)制粒子群算法在稀疏陣列綜合中的應(yīng)用[A];2009年全國(guó)天線(xiàn)年會(huì)論文集（上）[C];2009年

3 陳龍祥;蔡國(guó)平;;基于粒子群算法的時(shí)滯動(dòng)力學(xué)系統(tǒng)的時(shí)滯辨識(shí)[A];第十二屆全國(guó)非線(xiàn)性振動(dòng)暨第九屆全國(guó)非線(xiàn)性動(dòng)力學(xué)和運(yùn)動(dòng)穩(wěn)定性學(xué)術(shù)會(huì)議論文集[C];2009年

4 于穎;李永生;於孝春;;新型離散粒子群算法在波紋管優(yōu)化設(shè)計(jì)中的應(yīng)用[A];第十一屆全國(guó)膨脹節(jié)學(xué)術(shù)會(huì)議膨脹節(jié)設(shè)計(jì)、制造和應(yīng)用技術(shù)論文選集[C];2010年

5 劉卓倩;顧幸生;;一種基于信息熵的改進(jìn)粒子群算法[A];系統(tǒng)仿真技術(shù)及其應(yīng)用（第7卷）——'2005系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)交流會(huì)論文選編[C];2005年

6 熊偉麗;徐保國(guó);;粒子群算法在支持向量機(jī)參數(shù)選擇優(yōu)化中的應(yīng)用研究[A];2007中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集[C];2007年

7 方衛(wèi)華;徐蘭玉;陳允平;;改進(jìn)粒子群算法在大壩力學(xué)參數(shù)分區(qū)反演中的應(yīng)用[A];2012年中國(guó)水力發(fā)電工程學(xué)會(huì)大壩安全監(jiān)測(cè)專(zhuān)委會(huì)年會(huì)暨學(xué)術(shù)交流會(huì)論文集[C];2012年

8 熊偉麗;徐保國(guó);;單個(gè)粒子收斂中心隨機(jī)攝動(dòng)的粒子群算法[A];2009年中國(guó)智能自動(dòng)化會(huì)議論文集（第七分冊(cè)）[南京理工大學(xué)學(xué)報(bào)（增刊）][C];2009年

9 馬向陽(yáng);陳琦;;以粒子群算法求解買(mǎi)賣(mài)雙方存貨主從對(duì)策[A];第十二屆中國(guó)管理科學(xué)學(xué)術(shù)年會(huì)論文集[C];2010年

10 趙磊;;基于粒子群算法求解多目標(biāo)函數(shù)優(yōu)化問(wèn)題[A];第二十一屆中國(guó)（天津）’2007IT、網(wǎng)絡(luò)、信息技術(shù)、電子、儀器儀表創(chuàng)新學(xué)術(shù)會(huì)議論文集[C];2007年

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

1 李慶偉;粒子群算法及電廠若干問(wèn)題的研究[D];東南大學(xué);2016年

2 杜毅;多階段可變批生產(chǎn)線(xiàn)重構(gòu)的研究[D];廣東工業(yè)大學(xué);2016年

3 尹浩;求解Web服務(wù)選取問(wèn)題的粒子群算法研究[D];東北大學(xué);2014年

4 王芳;粒子群算法的研究[D];西南大學(xué);2006年

5 安鎮(zhèn)宙;家庭粒子群算法及其奇偶性與收斂性分析[D];云南大學(xué);2012年

6 劉建華;粒子群算法的基本理論及其改進(jìn)研究[D];中南大學(xué);2009年

7 黃平;粒子群算法改進(jìn)及其在電力系統(tǒng)的應(yīng)用[D];華南理工大學(xué);2012年

8 胡成玉;面向動(dòng)態(tài)環(huán)境的粒子群算法研究[D];華中科技大學(xué);2010年

9 張靜;基于混合離散粒子群算法的柔性作業(yè)車(chē)間調(diào)度問(wèn)題研究[D];浙江工業(yè)大學(xué);2014年

10 張寶;粒子群算法及其在衛(wèi)星艙布局中的應(yīng)用研究[D];大連理工大學(xué);2007年

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

1 張忠偉;結(jié)構(gòu)優(yōu)化中粒子群算法的研究與應(yīng)用[D];大連理工大學(xué);2009年

2 李強(qiáng);基于改進(jìn)粒子群算法的艾薩爐配料優(yōu)化[D];昆明理工大學(xué);2015年

3 付曉艷;基于粒子群算法的自調(diào)節(jié)隸屬函數(shù)模糊控制器設(shè)計(jì)[D];河北聯(lián)合大學(xué);2014年

4 余漢森;粒子群算法的自適應(yīng)變異研究[D];南京信息工程大學(xué);2015年

5 梁計(jì)鋒;基于改進(jìn)粒子群算法的交通控制算法研究[D];長(zhǎng)安大學(xué);2015年

6 楊偉;基于粒子群算法的氧樂(lè)果合成過(guò)程建模研究[D];鄭州大學(xué);2015年

7 李程;基于粒子群算法的AS/RS優(yōu)化調(diào)度方法研究[D];陜西科技大學(xué);2015年

8 樊偉健;基于混合混沌粒子群算法求解變循環(huán)發(fā)動(dòng)機(jī)數(shù)學(xué)模型問(wèn)題[D];山東大學(xué);2015年

9 陳百霞;考慮風(fēng)電場(chǎng)并網(wǎng)的電力系統(tǒng)無(wú)功優(yōu)化[D];山東大學(xué);2015年

10 戴玉倩;基于混合動(dòng)態(tài)粒子群算法的軟件測(cè)試數(shù)據(jù)自動(dòng)生成研究[D];江西理工大學(xué);2015年

，

本文編號(hào)：2019750