基于SFLA-GA混合算法求解時(shí)間最優(yōu)的旅行商問(wèn)題

張勇; 高鑫鑫; 王昱潔

doi:10.11999/JEIT170484

基于SFLA-GA混合算法求解時(shí)間最優(yōu)的旅行商問(wèn)題

doi: 10.11999/JEIT170484

基金項(xiàng)目:

國(guó)家科技支撐計(jì)劃項(xiàng)目(2013BAH52F01)

計(jì)量
- 文章訪問(wèn)數(shù): 1303
- HTML全文瀏覽量: 157
- PDF下載量: 183
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2017-05-18
- 修回日期: 2017-11-08
- 刊出日期: 2018-02-19

Solving the Time Optimal Traveling Salesman Problem Based on Hybrid Shuffled Frog Leaping Algorithm-Genetic Algorithm

Funds:

The National Science and Technology Support Program of China (2013BAH52F01)

摘要

摘要: 該文以經(jīng)典的對(duì)稱旅行商問(wèn)題(Symmetric Traveling Salesman Problem, STSP)為基礎(chǔ)，求解時(shí)間最優(yōu)的旅行商問(wèn)題(Time Optimal TSP, TOTSP)，將擬合函數(shù)引入到混合蛙跳遺傳算法(SFLA-GA)的適應(yīng)度函數(shù)來(lái)反映景點(diǎn)客流量隨時(shí)間的變化，旨在旅游旺季為游客提供一條游覽時(shí)間最短的路徑推送服務(wù)。實(shí)驗(yàn)結(jié)果表明：相對(duì)于隨機(jī)游覽路徑，SFLA-GA混合算法得到的游覽路徑明顯節(jié)省了游覽時(shí)間；與SFLA和混合粒子群遺傳算法(PSO-GA)相比較，SFLA-GA混合算法具有計(jì)算量少、收斂速度快、對(duì)初始種群依賴性低以及全局性更好等優(yōu)點(diǎn)，在求解TOTSP上搜索性能更強(qiáng)、時(shí)間更優(yōu)。
- 時(shí)間最優(yōu)的旅行商問(wèn)題 /
- 混合蛙跳遺傳算法 /
- 適應(yīng)度函數(shù) /
- 擬合函數(shù) /
- 游覽時(shí)間
Abstract: In order to provide a recommended-path service for tourists with the shortest traveling time in the peak-season, the Time Optimal Traveling Salesman Problem (TOTSP) is further studied and the fit function is introduced into the fitness function of the hybrid Shuffled Frog Leaping Algorithm-Genetic Algorithm (SFLA-GA) to reflect the change of traffic over time, which is based on the classic and Symmetrical Traveling Salesman Problem (STSP). The experimental results show that compared with the random tour path, the tour path significantly saves the tour time which is obtained by the hybrid SFLA-GA. Compared with SFLA and hybrid Particle Swarm Optimization-Genetic Algorithm (PSO-GA), the hybrid SFLA-GA has some advantages, such as less amount of calculation, fast speed of convergence, low dependency on initial population, good global superiority and so on. The hybrid SFLA-GA has stronger search capability and less search time in solving the TOTSP.
- Time optimal traveling salesman problem /
- Hybrid Shuffled Frog Leaping Algorithm-Genetic Algorithm (SFLA-GA) /
- Fitness function /
- Fit function /
- Tour time

HTML全文

參考文獻(xiàn)(25)

IACOPO G, FRANCOIS M, and KENJI S. The traveling salesman problem with neighborhoods: MINLP solution[J]. Optimization Methods and Software, 2013, 28(2): 364-378. doi: 10.1080/10556788.2011.648932.

ALFONSAS M, ANDRIUS B, and ANTANAS L. Modified local search heuristics for the symmetric traveling salesman problem[J]. Information Technology and Control, 2013, 42(3): 217-230. doi: 10.5755/j01.itc.42.3.1301.

張勇, 陳玲, 徐小龍, 等. 基于PSO-GA混合算法時(shí)間優(yōu)化的旅行商問(wèn)題研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2015, 32(12): 3613-3617. doi: 10.3969/j.issn.1001-3695.2015.12.019.

ZHANG Yong, CHEN Ling, XU Xiaolong, et al. Research on time optimal TSP based on hybrid PS0-GA[J]. Application Research of Computers, 2015, 32(12): 3613-3617. doi: 10.3969 /j.issn.1001-3695.2015.12.019.

ZHAN Shihua, LIN Juan, ZHANG Zejun, et al. List-based simulated annealing algorithm for traveling salesman problem[J]. Computational Intelligence and Neuroscience, 2016, (5): 1-12. doi: 10.1155/2016/1712630.

PAN G, LI K, OUYANG A, et al. Hybrid immune algorithm based on greedy algorithm and delete-cross operator for solving TSP[J]. Soft Computing, 2016, 20(2): 1-12. doi: 10.1007/s00500-014-1522-3.

YANG Jianyi, DING Ruifeng, ZHANG Yuan, et al. An improved ant colony optimization(I-ACO) method for the quasi travelling salesman problem(Quasi-TSP)[J]. International Journal of Geographical Information Science, 2015, 29(9): 1534-1551. doi: 10.1080/13658816.2015.1013960.

王勇臻, 陳燕, 于瑩瑩. 求解多旅行商問(wèn)題的改進(jìn)分組遺傳算法[J]. 電子與信息學(xué)報(bào), 2017, 39(1): 198-205. doi: 10.11999/ JEIT160211.

WANG Yongzhen, CHEN Yan, and YU Yingying. Improved grouping genetic algorithm for solving multiple traveling salesman problem[J]. Jounal of Electronics Information Technology, 2017, 39(1): 198-205. doi: 10.11999/JEIT160211.

胡穎, 莊雷, 蘭巨龍, 等. 基于自適應(yīng)協(xié)同進(jìn)化粒子群算法的虛擬網(wǎng)節(jié)能映射研究[J]. 電子與信息學(xué)報(bào), 2016, 38(10): 2660-2666. doi: 10.11999/JEIT151434.

HU Ying, ZHUANG Lei, LAN Julong, et al. Energy aware virtual network embedding using particle swarm optimization algorithm based on adaptive[J]. Journal of Electronics Information Technology, 2016, 38(10): 2660-2666. doi: 10.11999/JEIT151434.

程希, 沈建華. 一種基于改進(jìn)蟻群算法的光網(wǎng)絡(luò)波長(zhǎng)路由分配算法[J]. 電子與信息學(xué)報(bào), 2012, 34(3): 710-715. doi: 10.3724/SP.J.1146.2011.01032.

CHENG Xi and SHEN Jianhua. An improved ant colony algorithm for routing and wavelength assignment in optical networks[J]. Journal of Electronics Information Technology, 2012, 34(3): 710-715. doi: 10.3724/SP.J.1146.2011.01032.

HASANIEN H M. Shuffled frog leaping algorithm-based static synchronous compensator for transient stability improvement of a grid-connected wind farm[J]. Iet Renewable Power Generation, 2014, 8(6): 722-730. doi: 10.1049/iet-rpg. 2013.0277.

駱劍平, 李霞, 陳泯融. 基于改進(jìn)混合蛙跳算法的CVRP求解[J]. 電子與信息學(xué)報(bào), 2011, 33(2): 429-434. doi: 10.3724/ SP.J.1146.2010.00328.

LUO Jianping, LI Xia, and CHEN Minrong. Improved shuffled frog leaping algorithm for solving CVRP[J]. Journal of Electronics Information Technology, 2011, 33(2): 429-434. doi: 10.3724/SP.J.1146.2010.00328.

馬樂(lè), 葉見新, 王暉. 旅游景區(qū)智能客流統(tǒng)計(jì)系統(tǒng)應(yīng)用研究以玄武湖為例[J]. 中國(guó)科技信息, 2013, (2): 88-89. doi: 10.3969/j.issn.1001-8972.2013.02.040.

MA Le, YE Jianxin, and WANG Hui. Application research of intelligent statistical system for scenic area passenger flow- take xuanwu lake as an example[J]. China Science and Technology Information, 2013, (2): 88-89. doi: 10.3969/j.issn. 1001-8972.2013.02.040.

文俊浩, 舒珊. 一種改進(jìn)相似性度量的協(xié)同過(guò)濾推薦算法[J]. 計(jì)算機(jī)科學(xué), 2014, 41(5): 68-71. doi: 10.3969/j.issn.1002- 137X.2014.05.015.

WEN Junhao and SHU Shan. Improved collaborative filtering recommendation algorithm of similarity measure[J]. Computer Science, 2014, 41(5): 68-71. doi: 10.3969/j.issn. 1002-137X.2014.05.015.

HWANG Chaoming and YANG Miinshen. New similarity measures between generalized trapezoidal fuzzy numbers using the jaccard index[J]. International Journal of Uncertainty Fuzziness and Knowledge-Based Systems, 2014, 22(6): 831-844. doi: 10.1142/S0218488514500445.

孫沖. 混合蛙跳算法改進(jìn)及控制參數(shù)優(yōu)化仿真研究[D]. [碩士論文], 哈爾濱工業(yè)大學(xué), 2011.

SUN Chong. Shuffled frog leaping algorithm improvement and simulation research for optimization of control parameters[D]. [Master dissertation], Harbin Institute of Technology, 2011.

麻榮永, 楊磊磊, 張智超. 基于粒子迭代位移和軌跡的粒子群算法C1、C2 參數(shù)特性分析[J]. 數(shù)學(xué)計(jì)算, 2013, 2(4): 109-115.

MA Rongyong, YANG Leilei, and ZHANG Zhichao. Analysis the characteristic of C1, C2 based on the PSO of iterative shift and trajectory of particle[J]. Mathematical Computation, 2013, 2(4): 109-115.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問(wèn)統(tǒng)計(jì)