【摘要】：針對傳統(tǒng)粒子群算法不適合求解離散型問題,提出一種基于漢明距離的改進粒子群算法。該算法保留了粒子群算法的基本思想和流程,并基于漢明距離為粒子定義了一種新型的速度表示。同時,為了使算法尋優(yōu)能力更高、避免迭代過程陷入局部最優(yōu)無法跳出,設計了2-opt和3-opt算子,結合隨機貪婪規(guī)則,使求解質量更高、收斂更快。在算法后期,為了提高粒子在整體解空間中的全局搜索能力,采用一部分粒子重新生成的方式去重新探索解空間。為了驗證算法的有效性,采用了眾多旅行商問題(TSP)標準算例進行測試。實驗結果表明,對于小規(guī)模TSP,該算法可以找到歷史最優(yōu)解;對于大規(guī)模TSP,如城市數(shù)在100以上的問題,也可以找到滿意解,與已知最優(yōu)解之間偏差度較小,通常在5%以內。
[Abstract]:An improved particle swarm optimization algorithm based on hamming distance is proposed to solve discrete problems. The algorithm preserves the basic idea and flow of particle swarm optimization algorithm and defines a new speed representation for particles based on hamming distance. At the same time, in order to improve the optimization ability of the algorithm and avoid the iterative process falling into the local optimal can not jump out, the 2-opt and 3-opt operators are designed, combined with the random greedy rules, the solution quality is higher and the convergence is faster. In the later stage of the algorithm, in order to improve the global search ability of particles in the global solution space, a part of the particle is regenerated to re-explore the solution space. In order to verify the validity of the algorithm, many (TSP) standard examples of traveling salesman problems are used to test. The experimental results show that the historical optimal solution can be found for the small scale TSP, algorithm and the satisfactory solution can be found for the large scale TSP, problem such as the number of cities above 100. The deviation between the proposed algorithm and the known optimal solution is less than 5%.
【作者單位】： 北京科技大學工程技術研究院;北京科技大學鋼鐵共性技術協(xié)同創(chuàng)新中心;
【基金】：國家自然科學基金資助項目(51274043)~~
【分類號】：TP18

【相似文獻】

相關期刊論文 前10條

1 車林仙;;基于粒子群算法的混沌系統(tǒng)快速控制[J];瀘州職業(yè)技術學院學報;2006年03期

2 郭明山;劉秉瀚;;一種改進的混沌粒子群算法[J];福建電腦;2008年02期

3 張楠;邢志棟;董建民;王辛;;一種基于粒子群算法和育種算法的混合算法[J];西北大學學報(自然科學版);2008年01期

4 張大興;賈建援;張愛梅;郭永獻;;基于粒子群算法的三軸跟瞄裝置跟蹤策略研究[J];儀器儀表學報;2009年09期

5 張?zhí)├?劉春生;;基于改進粒子群算法的控制分配研究與應用[J];伺服控制;2012年06期

6 黃珍;潘穎;曹曉麗;;粒子群算法的基本理論及其改進研究[J];硅谷;2014年05期

7 焦國輝;;一種改進的粒子群算法穩(wěn)定性證明及其應用[J];現(xiàn)代計算機(專業(yè)版);2014年14期

8 王晟;潘郁;;個體激勵粒子群算法及其社會學背景分析[J];計算機工程;2008年21期

9 彭志平;張慧;;一種改進的粒子群算法在協(xié)商優(yōu)化中的應用[J];計算機工程;2008年10期

10 沈佳寧;須文波;孫俊;;基于量子粒子群算法的收斂性研究[J];微計算機信息;2009年06期

相關會議論文 前10條

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

2 馬向陽;陳琦;;以粒子群算法求解買賣雙方存貨主從對策[A];第十二屆中國管理科學學術年會論文集[C];2010年

3 黃勝;任萬龍;王超;何新;;多目標粒子群算法在翼型優(yōu)化的應用[A];第二十五屆全國水動力學研討會暨第十二屆全國水動力學學術會議文集（上冊）[C];2013年

4 李洪全;王京;;基于粒子群算法的自適應PID控制[A];冶金企業(yè)自動化、信息化與創(chuàng)新——全國冶金自動化信息網(wǎng)建網(wǎng)30周年論文集[C];2007年

5 李曙光;;粒子群算法在高速公路多路徑費用拆分方法研究[A];第二十六屆中國控制會議論文集[C];2007年

6 趙亮;;遺傳增強混沌粒子群算法[A];第二十九屆中國控制會議論文集[C];2010年

7 楊誠;楊傳啟;;基于粒子群算法的PID參數(shù)優(yōu)化[A];第七屆工業(yè)儀表與自動化學術會議論文集[C];2006年

8 劉文許;林禮清;溫步瀛;;電力市場下基于改進粒子群算法的AGC機組選擇[A];中國高等學校電力系統(tǒng)及其自動化專業(yè)第二十四屆學術年會論文集（中冊）[C];2008年

9 劉衍民;馬衛(wèi)民;;基于高斯白噪聲擾動的混合粒子群算法及其應用[A];第十屆中國不確定系統(tǒng)年會、第十四屆中國青年信息與管理學者大會論文集[C];2012年

10 王征;劉大寶;王家林;王永驥;;基于離散粒子群算法的船舶電力系統(tǒng)重構研究[A];2011年中國智能自動化學術會議論文集（第一分冊）[C];2011年

相關博士學位論文 前10條

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

2 尹浩;求解Web服務選取問題的粒子群算法研究[D];東北大學;2014年

3 邵晴;粒子群算法研究及其工程應用案例[D];吉林大學;2017年

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

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

6 張靜;基于混合離散粒子群算法的柔性作業(yè)車間調度問題研究[D];浙江工業(yè)大學;2014年

7 劉宏達;粒子群算法的研究及其在船舶工程中的應用[D];哈爾濱工程大學;2008年

8 馮琳;改進多目標粒子群算法的研究及其在電弧爐供電曲線優(yōu)化中的應用[D];東北大學;2013年

9 劉衍民;粒子群算法的研究及應用[D];山東師范大學;2011年

10 王雪飛;粒子群算法的動態(tài)拓樸結構研究[D];西南大學;2008年

相關碩士學位論文 前10條

1 李強;基于改進粒子群算法的艾薩爐配料優(yōu)化[D];昆明理工大學;2015年

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

3 余漢森;粒子群算法的自適應變異研究[D];南京信息工程大學;2015年

4 梁計鋒;基于改進粒子群算法的交通控制算法研究[D];長安大學;2015年

5 楊偉;基于粒子群算法的氧樂果合成過程建模研究[D];鄭州大學;2015年

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

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

8 仲偉彪;改進粒子群算法的研究及其云計算資源調度的應用[D];江西理工大學;2015年

9 艾東;基于粒子群算法的雙重目標設施布置優(yōu)化[D];西安建筑科技大學;2015年

10 劉召軍;解優(yōu)化問題的混合粒子群算法[D];陜西師范大學;2015年

，

本文編號：2350682