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

《分形法与范例库推理相结合进化求解旅行商问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第24卷第12期(总第156期)　　　　　　系　统　工　程Vol.24,No.122006年12月　　　　　　　　　　　　SystemsEngineeringDec.,2006文章编号:100124098(2006)1220102205X分形法与范例库推理相结合进化求解旅行商问题袁丽华,黎　明,李军华(1.南京航空航天大学自动化学院,江苏南京　210016;2.南昌航空工业学院无损检测技术教育部重点实验室,江西南昌　330063)摘　要:旅行商问题(TravelingSalesmanProblem,简称TSP)是一个典型的组合优化问题,而且是一个NP完全问题。

2、遗传算法(GeneticAlgorithm,简称GA)是求解组合优化问题的行之有效的算法。但遗传算法并不是一个完美无缺的算法,它最突出的问题是早熟现象。在解决像旅行商这类组合优化中的NP完全问题,是极易陷入早熟收敛,城市规模越大越难求得最优解。如何缓和旅行商问题中的早熟现象,使问题的解尽可能接近最优解,这是本文研究的主要内容。本文在分形法的基础上提出了一种分形法与范例库推理相结合的改进方法用以求解TSP问题。首先建立范例库,选取其中优良的个体来指导城市规模大的旅行商问题进行合理的区域分割,由于优良个体与最优值的结构大体相同,相似度大,故可以有效地实施“分而治之

3、”的策略。在寻优进化过程中,还要对范例库进行更新与维护。通过对TSPLIB测试库中的eil51、eil101、ch130和ch150问题的求解,说明该方法在求解TSP问题上是行之有效的。关键词:旅行商问题;分形法;范例库推理中图分类号:TP301;TP391　　　文献标识码:A枚举法无法解决较大规模的TSP。1　引言目前对较大规模的TSP研究是采用启发式算法寻求旅行商问题(TravelingSalesmanProblem,简称TSP)在可接受的时间内得到问题的满意解,启发式算法可分[2]是一个典型的组合优化问题,而且是一个NP完全问题,为环路构造算法和环路改进

4、算法两大类。环路构造算[3]对TSP的研究已远远超过其本身的含义,成为了衡量一法主要包括最近邻算法、贪心算法、Clarke2Wright算[4][5]种算法的优劣标准。TSP的实际模型可扩展为电路板的布法和Christofides算法等,这类算法是从某个起始点局、路由器的分布、机器人的控制等应用[1],因而长期以来或某一段路径出发,通过增广策略来得到一个闭合的路[6-8][9]TSP问题得到许多领域的学者们的关注。径。环路改进算法主要包括局部搜索、模拟退火、[10][11]TSP问题描述为:已知s座城市之间的相互距离,有禁忌搜索和多重规约等,这类算法是在给定的

5、初始一推销员必须遍访这s座城市,并且每个城市只能访问一解的基础上,使用某种策略来改进初始解。在此提出一种次,最后又必须返回出发城市。问如何优化旅行路线,使其新的启发式算法,即分形法与范例库推理相结合的环路旅行路线的总长度最短。TSP的数学模型并不复杂,但计改进算法,从范例库中选取一个初始解,应用分形法进行算时间却随着城市规模的增加而以惊人的速度增长。当城局部搜索。范例库推理应用于遗传算法中在国内尚无报[12]市规模较小时,用最简单的枚举法就可以算出,但是,当城道,近年来国外对此有研究,译为“注入式遗传算法”市规模较大时,传统的枚举法面临“秩数爆炸”或称之为(C

6、aseinjectedgeneticalgorithms)。在运算中从库里周期地“维数灾难”问题。对于s座城市,有(s-1)!ö2条不同路径,注入优良个体,改善种群的多样性,增强寻优能力。而本文在计算每条路径长度时,需要进行s次加法运算,所以解运用范例库推理是与分形法相结合,实现“分而治之”的策决TSP的总计算量为s!ö2。如果使用运算速度为1亿次ös略,达到降低维数的目的。应用分形法与范例库推理相结[13]的计算机求解,当s=25时,需花费的时间是25亿年。显然合求解了TSPLIB测试库中的eil51、eil101、ch130和X收稿日期:200620922

7、4基金项目:国家自然科学基金资助项目(60475002)作者简介:袁丽华(19702),女,副教授,博士研究生,研究方向:进化计算;黎明,教授,博士生导师;4李军华,博士研究生。第12期　　　　　　　袁丽华,黎明等:分形法与范例库推理相结合进化求解旅行商问题103[15]ch150问题,均优于网上公布的相对应的范例路径值,说明能力与破坏能力的具体分析,李敏强等人分析了多点[16]该方法在求解TSP问题上是行之有效的。交叉算子下2阶模式的存活概率的下界ps(2,K,L1,L)2　分形法与范例库推理KKL1iL-L1K-i=∑õLõLõpL1(i)(1)2.1　分

8、形法i=0i式中,K为交叉点数,L1为