运用遗传算法求解有约束条件的旅行商问题

华南理工大学学报(自然科学版) ›› 2004, Vol. 32 ›› Issue (4): 97-100.

• • 上一篇

运用遗传算法求解有约束条件的旅行商问题

朱玲湘廖芹邹亮

华南理工大学应用数学系广东广州510640

收稿日期:2003-06-25 出版日期:2004-04-20 发布日期:2015-09-08
通信作者: 朱玲湘（1979－）女硕士研究生主要从事数理统计和优化算法研究． E-mail:hcitys＠163.com
作者简介:朱玲湘（1979－）女硕士研究生主要从事数理统计和优化算法研究．

Resolution of the Traveling Salesman Problem with Precedence Constraint Applying Genetic Algorithm

Zhu Ling-xiang Liao Qin Zou Liang

Dept．of Applied MathematicsSouth China Univ．of Tech．Guangzhou510640GuangdongChina

Received:2003-06-25 Online:2004-04-20 Published:2015-09-08
Contact: 朱玲湘（1979－）女硕士研究生主要从事数理统计和优化算法研究． E-mail:hcitys＠163.com
About author:朱玲湘（1979－）女硕士研究生主要从事数理统计和优化算法研究．

摘要/Abstract

摘要： 介绍了TSPPC（Traveling Salesman Problem with Precedence Constraint）并指出了普通遗传算法对于求解TSPPC 的局限性及在算法过程中产生大量非可行解从而降低了算法的搜索效率．提出了基于TSPPC 中约束条件的种群初始化、交叉操作以及变异操作．由于运用这些遗传操作在算法过程中不会产生非可行解因此大大提高了算法的搜索效率．最后通过定理和算例验证了本文中提出的遗传算法．

关键词: 有约束条件的旅行商问题, 遗传算法, 种群初始化, 交叉, 变异

Abstract: The Traveling Salesman Problem with Precedence Constraint （TSPPC） was introduced and the localization of the general genetic algorithm （GA） to solve TSPPC was pointed out．It is found that a lot of illegal chromosomes would be generated by using the general GAthus reducing the searching efficiency of the algorithm．To overcome the disadvantages mentioned abovethe species initializationcrossover and mutation based on the precedence constraint of TSP were proposed．None of these genetic operations would generate any illegal chromosomewhich makes the searching efficiency of the algorithm higher．This conclusion was finally verified by corresponding theorems and examples．

Key words: traveling salesman problem with precedence constraint, genetic algorithm, species initialization, crossover, mutation

中图分类号:

O242.1

朱玲湘廖芹邹亮. 运用遗传算法求解有约束条件的旅行商问题[J]. 华南理工大学学报(自然科学版), 2004, 32(4): 97-100.

Zhu Ling-xiang Liao Qin Zou Liang. Resolution of the Traveling Salesman Problem with Precedence Constraint Applying Genetic Algorithm[J]. Journal of South China University of Technology(Natural Science Edition), 2004, 32(4): 97-100.

[1]	邱宇东, 王湛, 谢志燊. 基于混合算法的半刚性连接钢框架结构优化[J]. 华南理工大学学报(自然科学版), 2023, 51(6): 72-77.
[2]	翁剑成, 王茂林, 林鹏飞, 等. 基于客流特征鉴别的公交跨线组合调度优化方法[J]. 华南理工大学学报(自然科学版), 2022, 50(9): 39-48.
[3]	卢凯, 赵世杰, 吴焕, 等. 饱和交叉口的双向红绿波协调设计数解算法[J]. 华南理工大学学报(自然科学版), 2022, 50(9): 1-11.
[4]	秦雅琴, 钱正富, 谢济铭, 等. 基于社会力的交织区突发瓶颈段协同换道决策模型[J]. 华南理工大学学报(自然科学版), 2022, 50(7): 66-75.
[5]	郑亚晶, 李耀辉, 靳文舟. 考虑换乘客流的城市轨道交通网络末班车衔接优化研究[J]. 华南理工大学学报(自然科学版), 2022, 50(5): 32-39,72.
[6]	夏琴香, 李凯, 马骏, 等. 基于遗传算法的模具电极调度问题求解[J]. 华南理工大学学报(自然科学版), 2022, 50(3): 80-87.
[7]	周中, 邓卓湘, 陈云, 等. 基于GA-BP神经网络的泡沫轻质土强度预测[J]. 华南理工大学学报(自然科学版), 2022, 50(11): 125-132.
[8]	陈小红, 胡芳. 基于可能度的交叉口信号控制区间优化模型[J]. 华南理工大学学报(自然科学版), 2022, 50(10): 29-40.
[9]	魏红卫赵凡. 饱和渗透系数变异性对边坡破坏概率的影响[J]. 华南理工大学学报(自然科学版), 2021, 49(8): 95-102.
[10]	刘璇, 王子航, 张桐瑞, 等. 港口重载AGV横向稳定的优化控制策略[J]. 华南理工大学学报(自然科学版), 2021, 49(8): 113-121.
[11]	李静王晨张家旭. 基于UniTire轮胎模型的汽车行驶速度估计[J]. 华南理工大学学报（自然科学版）, 2021, 49(5): 47-55.
[12]	罗玉涛, 周天阳, 许晓通. 基于遗传算法的四轮转向－驱动汽车时变 LQR 控制[J]. 华南理工大学学报（自然科学版）, 2021, 49(3): 114-122.
[13]	晋刚何志豪王英俊. 基于遗传算法的5G频率选择表面形状优化方法[J]. 华南理工大学学报（自然科学版）, 2021, 49(11): 95-105.
[14]	李家乐刘真伯王雪菲. 智能电网下支持充放电策略的电动汽车配送路径优化[J]. 华南理工大学学报（自然科学版）, 2021, 49(10): 31-40.
[15]	靳文舟胡为洋邓嘉怡, 等. 基于混合算法的需求响应公交灵活调度模型 [J]. 华南理工大学学报（自然科学版）, 2021, 49(1): 123-133.

运用遗传算法求解有约束条件的旅行商问题

Resolution of the Traveling Salesman Problem with Precedence Constraint Applying Genetic Algorithm

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价