分形法与范例库推理相结合进化求解旅行商问题

• 作者: 李军华 袁丽华 黎明
• 来源期刊: 系统工程
• 学科: 工学
• 关键词: 旅行商问题 分形法 范例库推理
• 年，卷（期）: 2006,（12）
• 页码范围: 102-106
• 页数: 5页
• 分类号: TP301|TP391
• 字数: 3654字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-4098.2006.12.020

摘要

旅行商问题(Traveling Salesman Problem,简称TSP)是一个典型的组合优化问题,而且是一个NP完全问题.遗传算法(Genetic Algorithm,简称GA)是求解组合优化问题的行之有效的算法.但遗传算法并不是一个完美无缺的算法,它最突出的问题是早熟现象.在解决像旅行商这类组合优化中的NP完全问题,是极易陷入早熟收敛,城市规模越大越难求得最优解.如何缓和旅行商问题中的早熟现象,使问题的解尽可能接近最优解,这是本文研究的主要内容.本文在分形法的基础上提出了一种分形法与范例库推理相结合的改进方法用以求解TSP问题.首先建立范例库,选取其中优良的个体来指导城市规模大的旅行商问题进行合理的区域分割,由于优良个体与最优值的结构大体相同,相似度大,故可以有效地实施"分而治之"的策略.在寻优进化过程中,还要对范例库进行更新与维护.通过对TSPLIB测试库中的eil51、eil101、ch130和ch150问题的求解,说明该方法在求解TSP问题上是行之有效的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	袁丽华	南京航空航天大学自动化学院	8	106	5.0	8.0
2	黎明	南昌航空工业学院无损检测技术教育部重点实验室	182	1686	21.0	33.0
3	李军华	南京航空航天大学自动化学院	9	141	6.0	9.0