[1]赵新超,郭赛.遗传算法求解多旅行商问题的相对解空间分析[J].智能系统学报,2018,13(5):760-768.[doi:10.11992/tis.201706061]
ZHAO Xinchao,GUO Sai.Analysis on the relative solution space for MTSP with genetic algorithm[J].CAAI Transactions on Intelligent Systems,2018,13(5):760-768.[doi:10.11992/tis.201706061]
点击复制
ZHAO Xinchao,GUO Sai.Analysis on the relative solution space for MTSP with genetic algorithm[J].CAAI Transactions on Intelligent Systems,2018,13(5):760-768.[doi:10.11992/tis.201706061]
遗传算法求解多旅行商问题的相对解空间分析
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
13
期数:
2018年第5期
页码:
760-768
栏目:
学术论文—智能系统
出版日期:
2018-09-05
- Title:
- Analysis on the relative solution space for MTSP with genetic algorithm
- 关键词:
- 多旅行商问题; 遗传算法; 染色体编码; 相对解空间; Stirling公式
- Keywords:
- multiple traveling salespersons problem; genetic algorithm; chromosome encoding; relative solution space; Stirling formula
- 分类号:
- O224;TP18
- 摘要:
- 首先介绍了多旅行商问题的模型，并指出遗传算法解决多旅行商问题的关键是染色体编码方案的设计，为了减少冗余解带来的代价，本文给出了传统的两种染色体编码方案（单染色体和双染色体），以及最新的两段式染色体编码方案；接着引入相对解空间概念，以此定量地给出不同染色体方案对应解空间的相对大小关系；基于相对解空间概念，本文分析了3种染色体编码方案对应的解空间在极限意义下的相对大小关系，并分析了旅行商数与城市数在不同情形下解空间的近似相对大小关系。本文对搜索空间定量分析的理论结果对工程问题的求解提供了科学的指导意义。
- Abstract:
- This paper introduces the concept of multiple traveling salespersons problem (MTSP) and a chromosome encoding design method for solving the MTSP using genetic algorithm. In order to reduce the cost of redundant solution, two traditional chromosome design methods (single and double chromosome designs) are proposed, as well as the current two-part chromosome encoding design. Then the concept of relative solution space is introduced to quantitatively compare the relative size order of spaces for different solutions. Then on based on the relative solution space, the relative size order of the solution spaces of three chromosome-encoding designs are analyzed under an infinite limit. Subsequently, the relative size order of the solution spaces is analyzed individually when the relationship presents different situations between the number of travelers and the number of cities. The theoretical results of the quantitative analysis on the search space given in this paper are of great significance in guiding engineering applications and solving practical problems.
- 参考文献/References:
-
[1] CARTER A E, RAGSDALE C T. A new approach to solving the multiple traveling salesperson problem using genetic algorithms[J]. European journal of operational research, 2006, 175(1):246-257.
[2] YUAN Shuai, SKINNER B, HUANG Shoudong, et al. A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms[J]. European journal of operational research, 2013, 228(1):72-82.
[3] WANG Xuping, XU Chuanlei, HU Xiangpei. Genetic algorithm for vehicle routing problem with time windows and a limited number of vehicles[C]//Proceedings of 2008 International Conference on Management Science and Engineering 15th Annual Conference. Long Beach, CA, USA, 2010:128-133.
[4] BRANKE J, NGUYEN S, PICKARDT C, et al. Automated design of production scheduling heuristics:a review[J]. IEEE transactions on evolutionary computation, 2016, 20(1):110-124.
[5] GOLDBERG D E. Genetic algorithms in search, optimization, and machine learning[M]. Reading, Mass:Addison-Wesley Publishing Company, 1989.
[6] KESHAVARZ T, SALMASI N, VARMAZYAR M. Minimizing total completion time in the flexible flowshop sequence-dependent group scheduling problem[J]. Annals of operations research, 2015, 226(1):351-377.
[7] 张永库, 尹灵雪, 孙劲光. 基于改进的遗传算法的模糊聚类算法[J]. 智能系统学报, 2015, 10(4):627-635 ZHANG Yongku, YIN Lingxue, SUN Jinguang. Fuzzy clustering algorithm based on the improved genetic algorithm[J]. CAAI transactions on intelligent systems, 2015, 10(4):627-635
[8] KATAYAMA K, SAKAMOTO H, NARIHISA H. The efficiency of hybrid mutation genetic algorithm for the travelling salesman problem[M]. The Netherlands:Elsevier Science Publishers B. V., 2000.
[9] 黄可为, 汪定伟. 热轧计划中的多旅行商问题及其计算方法[J]. 计算机应用研究, 2007, 24(7):43-45, 57 HUANG Kewei, WANG Dingwei. Multiple traveling salesman problem and its application to hot rolling planning[J]. Application research of computers, 2007, 24(7):43-45, 57
[10] 江贺, 张宪超, 车皓阳, 等. 带多项式量级约束条件的多商品流BWTSP线性规划[J]. 计算机研究与发展, 2007, 44(10):1796-1800 JIANG He, ZHANG Xianchao, CHE Haoyang, et al. A multi-commodity flow linear programming with polynomial constraints for black and white traveling salesman problem[J]. Journal of computer research and development, 2007, 44(10):1796-1800
[11] TRIGUI S, CHEIKHROUHOU O, KOUBAA A, et al. FL-MTSP:a fuzzy logic approach to solve the multi-objective multiple traveling salesman problem for multi-robot systems[J]. Soft computing, 2017, 21(24):7351-7362.
[12] 王宇平, 李英华. 求解TSP的量子遗传算法[J]. 计算机学报, 2007, 30(5):748-755 WANG Yuping, LI Yinghua. A novel quantum genetic algorithm for TSP[J]. Chinese journal of computers, 2007, 30(5):748-755
[13] 赵新超, 刘国莅, 刘虎球, 等. 基于非均匀变异和多阶段扰动的粒子群优化算法[J]. 计算机学报, 2014, 37(9):2058-2070 ZHAO Xinchao, LIU Guoli, LIU Huqiu, et al. Particle swarm optimization algorithm based on non-uniform mutation and multiple stages perturbation[J]. Chinese journal of computers, 2014, 37(9):2058-2070
[14] 张筑生. 数学分析新讲(第2册)[M]. 北京:北京大学出版社, 1990.
- 相似文献/References:
-
[1]周本达,陈明华.随机化均匀设计混合遗传算法求解图的二划分问题[J].智能系统学报,2009,4(1):91.
ZHOU Ben-da,CHEN Ming-hua.Solving the 2-way graph partitioning problem using a genetic algorithm based on randomized uniform design[J].CAAI Transactions on Intelligent Systems,2009,4():91.
[2]康 琦,汪 镭,刘小莉,等.基于群体智能框架理念的遗传算法总体模式描述[J].智能系统学报,2007,2(5):42.
KANG Qi,WANG Lei,LIU Xiao-li,et al.General mode description genetic algorithms based on a framework of swarm intelligence[J].CAAI Transactions on Intelligent Systems,2007,2():42.
[3]马 炫,张亚龙.基于遗传算法的大规模矩形件优化排样[J].智能系统学报,2007,2(5):48.
MA Xuan,ZHANG Ya-long.A genetic algorithm for the layout of large scale rectang ular parts[J].CAAI Transactions on Intelligent Systems,2007,2():48.
[4]徐 雄.人工情感的进化控制系统实现[J].智能系统学报,2008,3(2):135.
XU Xiong.Implementation of an evolutionary control system based on artificial emotion[J].CAAI Transactions on Intelligent Systems,2008,3():135.
[5]刘 胜,李高云,孙天英.一种基于种群多样度的实数编码并行遗传算法[J].智能系统学报,2008,3(5):423.
L IU Sheng,L I Gao-yun,SUN Tian-ying.A real coding parallel genetic algorithm based on diversity of population[J].CAAI Transactions on Intelligent Systems,2008,3():423.
[6]张 涛,费树岷,李晓东.基于GARBF神经网络及边界不变特征的车辆识别[J].智能系统学报,2009,4(3):278.
ZHANG Tao,FEI Shu-min,LI Xiao-dong.Vehicle recognition using boundary invariants and a genetic algorithm trained radial basis function neural network[J].CAAI Transactions on Intelligent Systems,2009,4():278.
[7]秦世引,高书征.面向救援任务的地面移动机器人路径规划[J].智能系统学报,2009,4(5):414.[doi:10.3969/j.issn.1673-4785.2009.05.005]
QIN Shi-yin,GAO Shu-zhen.Path planning for mobile rescue robots in disaster areas with complex environments[J].CAAI Transactions on Intelligent Systems,2009,4():414.[doi:10.3969/j.issn.1673-4785.2009.05.005]
[8]周树德,孙增圻.遗传算法中的联结关系[J].智能系统学报,2009,4(6):483.[doi:10.3969/j.issn.1673-4785.2009.06.003]
ZHOU Shu-de,SUN Zeng-qi.Linkage in genetic algorithms[J].CAAI Transactions on Intelligent Systems,2009,4():483.[doi:10.3969/j.issn.1673-4785.2009.06.003]
[9]程显毅,巩向普.改进的模糊C-均值算法在医学图像分割中的应用[J].智能系统学报,2010,5(1):80.
CHENG Xian-yi,GONG Xiang-pu.An improved fuzzy Cmeans algorithm for segmentation of medical images[J].CAAI Transactions on Intelligent Systems,2010,5():80.
[10]王斐,闻时光,吴成东,等.基于模糊逻辑的多移动机器人自适应协作围捕[J].智能系统学报,2011,6(1):44.
WANG Fei,WEN Shiguang,WU Chengdong,et al.Adaptive cooperative hunting for multiple mobile robots based on fuzzy logic[J].CAAI Transactions on Intelligent Systems,2011,6():44.
备注/Memo
收稿日期:2017-06-17。
基金项目:国家自然科学基金项目（61375066，11671052，71772060）.
作者简介:赵新超,男,1976年生,教授,博士生导师,主要研究方向为进化计算、群体智能及其运筹优化;郭赛,女,1993年生,硕士研究生,主要研究方向为群体智能理论。
通讯作者:郭赛.E-mail:saisaismily@163.com.
更新日期/Last Update:
2018-10-25