本文關(guān)鍵詞：混合算法求解多目標(biāo)平衡旅行商問(wèn)題　出處：《計(jì)算機(jī)研究與發(fā)展》2017年08期 　論文類(lèi)型：期刊論文

  更多相關(guān)文章： 混合伊藤算法 混合遺傳算法 平衡旅行商問(wèn)題 多目標(biāo)平衡旅行商問(wèn)題 蟻群算法

【摘要】：平衡旅行商問(wèn)題(balanced traveling salesman problem,BTSP)是旅行商問(wèn)題(traveling salesman problem,TSP)的變化模型,是另一種組合優(yōu)化問(wèn)題,可在汽輪機(jī)(gas turbine engines,GTE)等的優(yōu)化問(wèn)題中得到應(yīng)用,但BTSP模型只能對(duì)含單個(gè)旅行商一個(gè)任務(wù)的優(yōu)化問(wèn)題建模,不能同時(shí)對(duì)含多個(gè)旅行商多任務(wù)的問(wèn)題進(jìn)行建模和優(yōu)化.基于此,首次提出了一種多目標(biāo)平衡旅行商問(wèn)題(multiobjective balanced traveling salesman problem,MBTSP)模型,可建模含多個(gè)旅行商多任務(wù)的優(yōu)化問(wèn)題,具體可應(yīng)用在含多個(gè)目標(biāo)或個(gè)體的實(shí)際問(wèn)題,例如含多個(gè)GTE的優(yōu)化.相關(guān)文獻(xiàn)的研究已證實(shí),伊藤算法和遺傳算法(genetic algorithm,GA)在求解組合優(yōu)化問(wèn)題中具有較好的性能,因此,應(yīng)用混合伊藤算法(hybrid ITO algorithm,HITO)和混合遺傳算法來(lái)求解MBTSP問(wèn)題.HITO通過(guò)蟻群算法(ant colony optimization,ACO)來(lái)產(chǎn)生基于圖的概率生成模型,再用伊藤算法的漂移和波動(dòng)算子對(duì)該圖模型進(jìn)行更新,從而得到MBTSP的最優(yōu)解.對(duì)于混合遺傳算法,第一個(gè)用貪心法對(duì)遺傳算法進(jìn)行改進(jìn),命名為貪心法遺傳算法(genetic algorithm with greedy initialization,GAG),第二個(gè)用爬山算法優(yōu)化遺傳算法,稱(chēng)之為爬山法遺傳算法(genetic algorithm by hill-climbing,GAHC),最后一個(gè)為模擬退火遺傳算法(genetic algorithm with simulated annealing,GASA).為了有效驗(yàn)證該算法,使用小尺度到大尺度的不同規(guī)模MBTSP問(wèn)題的數(shù)據(jù)進(jìn)行實(shí)驗(yàn),結(jié)果表明:混合算法在求解MBTSP問(wèn)題是有效的,并表現(xiàn)出不同的特點(diǎn).
[Abstract]:Balanced traveling salesman problem. BTSPs are the changing model of traveling salesman problem (TSP), and another kind of combinatorial optimization problem. It can be applied to the optimization problem of steam turbine gas turbine engine, etc., but the BTSP model can only model the optimization problem with a single traveling salesman. Problems with multiple tasks cannot be modeled and optimized at the same time. A multiobjective balanced traveling salesman problem is proposed for the first time. The GTE model can be used to model the multi-task optimization problem with multiple traveling salesman. It can be applied to practical problems with multiple objectives or individuals, such as optimization with multiple GTE. Ito algorithm and genetic algorithm GA) have better performance in solving combinatorial optimization problems. Hybrid ITO algorithm is applied to hybrid Ito algorithm. HITO) and hybrid genetic algorithm (HITO) are used to solve the MBTSP problem. HITO uses ant colony optimization. ACO) is used to generate graph-based probabilistic model, and then Ito's drift and fluctuation operators are used to update the graph model to obtain the optimal solution of MBTSP. For hybrid genetic algorithm. The first one uses greedy method to improve genetic algorithm. Named greedy genetic algorithm algorithm with greedy initialization (gag). The second is genetic algorithm by ill-climbing genetic algorithm (algorithm). The last one is genetic algorithm with simulated annealing. In order to verify the algorithm effectively, we use the data of different scale MBTSP problem from small scale to large scale to carry on the experiment. The results show that the hybrid algorithm is effective in solving the MBTSP problem. And show different characteristics.
【作者單位】： 武漢大學(xué)計(jì)算機(jī)學(xué)院;
【基金】：國(guó)家自然科學(xué)基金項(xiàng)目(61672024,61170305)~~
【分類(lèi)號(hào)】：TP18
【正文快照】： 平衡旅行商問(wèn)題(balanced traveling salesmanproblem,BTSP)是TSP的變化模型,可應(yīng)用在汽輪機(jī)的優(yōu)化等問(wèn)題.但是BTSP模型只能對(duì)含一個(gè)旅行商單個(gè)任務(wù)的問(wèn)題建模,沒(méi)法同時(shí)對(duì)含多個(gè)旅行商有多個(gè)單獨(dú)任務(wù)的問(wèn)題進(jìn)行建模和優(yōu)化,基于此,本文提出了多目標(biāo)的平衡旅行商問(wèn)題(multi-obje

【參考文獻(xiàn)】

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

1 易云飛;蔡永樂(lè);董文永;林曉東;;求解帶用戶(hù)滿(mǎn)意度的多目標(biāo)實(shí)時(shí)車(chē)輛路徑問(wèn)題的改進(jìn)伊藤算法[J];電子學(xué)報(bào);2015年10期

2 董文永;張文生;于瑞國(guó);;求解組合優(yōu)化問(wèn)題伊藤算法的收斂性和期望收斂速度分析[J];計(jì)算機(jī)學(xué)報(bào);2011年04期

【共引文獻(xiàn)】

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

1 董學(xué)士;董文永;王豫峰;;混合算法求解多目標(biāo)平衡旅行商問(wèn)題[J];計(jì)算機(jī)研究與發(fā)展;2017年08期

2 滿(mǎn)振禎;余世明;何德峰;;基于改進(jìn)伊藤算法的最短路徑網(wǎng)絡(luò)路由優(yōu)化算法[J];計(jì)算機(jī)科學(xué);2017年07期

3 尹志揚(yáng);余世明;;求解環(huán)境車(chē)輛路徑問(wèn)題的多種群伊藤算法[J];計(jì)算機(jī)科學(xué);2016年12期

4 易云飛;林曉東;蔡永樂(lè);;求解旅行商問(wèn)題的改進(jìn)粒子群算法[J];計(jì)算機(jī)工程與設(shè)計(jì);2016年08期

5 華茂;余世明;;一種改進(jìn)的混沌伊藤算法求解車(chē)輛配送問(wèn)題[J];計(jì)算機(jī)科學(xué);2016年03期

6 易云飛;蔡永樂(lè);董文永;林曉東;;求解帶用戶(hù)滿(mǎn)意度的多目標(biāo)實(shí)時(shí)車(chē)輛路徑問(wèn)題的改進(jìn)伊藤算法[J];電子學(xué)報(bào);2015年10期

7 王浩光;余世明;;求解車(chē)輛路徑問(wèn)題的改進(jìn)伊藤算法[J];計(jì)算機(jī)科學(xué);2015年09期

8 易云飛;董文永;林曉東;蔡永樂(lè);;求解帶軟時(shí)間窗車(chē)輛路徑問(wèn)題的改進(jìn)伊藤算法及其收斂性分析[J];電子學(xué)報(bào);2015年04期

9 李松芳;劉偉;;基于萬(wàn)有引力思想的遺傳算子[J];廣東工業(yè)大學(xué)學(xué)報(bào);2015年01期

10 李松芳;劉偉;徐懷祥;;一種基于漂移和波動(dòng)思想的遺傳算法[J];廣東工業(yè)大學(xué)學(xué)報(bào);2014年01期

【二級(jí)參考文獻(xiàn)】

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

1 易云飛;董文永;林曉東;蔡永樂(lè);;求解帶軟時(shí)間窗車(chē)輛路徑問(wèn)題的改進(jìn)伊藤算法及其收斂性分析[J];電子學(xué)報(bào);2015年04期

2 喻飛;李元香;魏波;徐星;趙志勇;;透鏡成像反學(xué)習(xí)策略在粒子群算法中的應(yīng)用[J];電子學(xué)報(bào);2014年02期

3 董文永;張文生;于瑞國(guó);;求解組合優(yōu)化問(wèn)題伊藤算法的收斂性和期望收斂速度分析[J];計(jì)算機(jī)學(xué)報(bào);2011年04期

4 王本年;高陽(yáng);陳兆乾;謝俊元;陳世福;;RLGA:一種基于強(qiáng)化學(xué)習(xí)機(jī)制的遺傳算法[J];電子學(xué)報(bào);2006年05期

5 ;Hybrid ant colony algorithm for traveling salesman problem[J];Progress in Natural Science;2003年04期

6 徐宗本,聶贊坎,張文修;遺傳算法的幾乎必然強(qiáng)收斂性——鞅方法[J];計(jì)算機(jī)學(xué)報(bào);2002年08期

【相似文獻(xiàn)】

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

1 王大志;汪定偉;閆楊;;一類(lèi)多旅行商問(wèn)題的計(jì)算及仿真分析[J];系統(tǒng)仿真學(xué)報(bào);2009年20期

2 莫愿斌;劉賀同;王勤;;旅行商問(wèn)題的綜述教學(xué)研究[J];中國(guó)科教創(chuàng)新導(dǎo)刊;2008年08期

3 蘇麗杰,聶義勇;現(xiàn)實(shí)旅行商問(wèn)題[J];小型微型計(jì)算機(jī)系統(tǒng);2005年04期

4 顧大權(quán);徐四林;袁媛;汪晉;;求解旅行商問(wèn)題的一個(gè)有效算法[J];解放軍理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年02期

5 陳文蘭;戴樹(shù)貴;;旅行商問(wèn)題算法研究綜述[J];滁州學(xué)院學(xué)報(bào);2006年03期

6 江賀;張憲超;陳國(guó)良;;有向黑白旅行商問(wèn)題[J];計(jì)算機(jī)學(xué)報(bào);2007年03期

7 管琳;白艷萍;;用分支定界算法求解旅行商問(wèn)題[J];中北大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年02期

8 黃可為;汪定偉;;熱軋計(jì)劃中的多旅行商問(wèn)題及其計(jì)算方法[J];計(jì)算機(jī)應(yīng)用研究;2007年07期

9 張敏;金琴玲;;旅行商問(wèn)題的一種新解法[J];重慶職業(yè)技術(shù)學(xué)院學(xué)報(bào);2008年01期

10 高春濤;;求解旅行商問(wèn)題的幾種解法[J];邊疆經(jīng)濟(jì)與文化;2010年05期

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

1 馮純伯;;旅行商問(wèn)題的一種解法[A];1991年控制理論及其應(yīng)用年會(huì)論文集（下）[C];1991年

2 張雷;鄭維敏;;廣義旅行商問(wèn)題、放映員問(wèn)題和一類(lèi)調(diào)度模型[A];1996年中國(guó)控制會(huì)議論文集[C];1996年

3 胡巧華;吳懷宇;陳喬禮;陳媛;;一種求解旅行商問(wèn)題的啟發(fā)交叉算子的研究[A];第25屆中國(guó)控制會(huì)議論文集（中冊(cè)）[C];2006年

4 張輝;王錫淮;肖健梅;;基于改進(jìn)蟻群算法的旅行商問(wèn)題[A];2007中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集[C];2007年

5 李大衛(wèi);王夢(mèng)光;;熱軋調(diào)度與多旅行商問(wèn)題[A];1996年中國(guó)控制會(huì)議論文集[C];1996年

6 劉春波;潘豐;楊丹;;基于改進(jìn)的蟻群算法在中國(guó)旅行商問(wèn)題中的求解[A];2007中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集[C];2007年

7 馮純伯;蔣珉;;應(yīng)用模擬電場(chǎng)法解旅行商問(wèn)題[A];1993年控制理論及其應(yīng)用年會(huì)論文集[C];1993年

8 李麗;程玉榮;牛奔;;離散人工蜂群算法求解旅行商問(wèn)題[A];第十三屆中國(guó)管理科學(xué)學(xué)術(shù)年會(huì)論文集[C];2011年

9 孫啟瑞;李俊;丁健;戴先中;;新型訪問(wèn)域部分重疊的多旅行商問(wèn)題的GA求解[A];2013年中國(guó)智能自動(dòng)化學(xué)術(shù)會(huì)議論文集（第四分冊(cè)）[C];2013年

10 韓愛(ài)麗;朱大銘;;旅行商問(wèn)題的一種新DNA編碼方案[A];2006年全國(guó)理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會(huì)論文集[C];2006年

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

1 張夢(mèng)穎;不確定因素下路徑規(guī)劃問(wèn)題研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2016年

2 溫新剛;基于服務(wù)時(shí)間約束的在線旅行商問(wèn)題研究[D];西安交通大學(xué);2017年

3 譚陽(yáng);求解廣義旅行商問(wèn)題的若干進(jìn)化算法研究[D];華南理工大學(xué);2013年

4 王剛;兩類(lèi)圈問(wèn)題的算法研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2013年

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

1 劉欣欣;旅行商問(wèn)題的基因片段插入算法研究[D];閩南師范大學(xué);2015年

2 陳玲;基于PSO-GA混合算法的時(shí)間優(yōu)化的旅行商問(wèn)題的研究[D];合肥工業(yè)大學(xué);2015年

3 趙麗娜;帶油耗的單商品取送貨旅行商問(wèn)題研究[D];沈陽(yáng)師范大學(xué);2016年

4 毛巍;一種新的改進(jìn)人工蜂群算法及其在旅行商問(wèn)題中的應(yīng)用[D];四川理工學(xué)院;2016年

5 盧雨瀟;基于多頭絨泡菌模型的優(yōu)化蟻群算法及其在旅行商問(wèn)題中的運(yùn)用[D];西南大學(xué);2016年

6 肖聰;農(nóng)產(chǎn)品配送中的流旅行商問(wèn)題及啟發(fā)式算法的研究[D];吉林農(nóng)業(yè)大學(xué);2016年

7 孫文成;基于多目標(biāo)方法的旅行商問(wèn)題復(fù)雜度研究[D];大連理工大學(xué);2016年

8 師肖靜;不確定環(huán)境下旅行商問(wèn)題的模型及算法[D];聊城大學(xué);2017年

9 徐東鎮(zhèn);蟻群算法及其在廣義旅行商問(wèn)題求解中的應(yīng)用[D];合肥工業(yè)大學(xué);2007年

10 黃厚生;求解旅行商問(wèn)題的新方法研究[D];天津大學(xué);2005年

，

本文編號(hào)：1421280