旅行商问题的基因整合算法\O1.2(2(,01)\O.5数学杂志J.ofIath.(PRC)旅行商问题的基因整合算法燕子宗～,费浦生(1.武汉大学数学与统计学院,湖北武汉130027;2.长江大学教学学院,湖北荆州434lOO)摘要:本文针对旅行商问题提出了因整合算法.它是通过设置扰动矩阵构造与原商问题等价的近似问题.使用景优罚函数选择回路舒枝得到一系列局部最优回路?从中提取频度高的技一一基因进行整合.得到更优的回路.该算法计算量4,.对大规模问题汁算效果显着.利用该算法对CIIl{4问题给出了目前最件的结果.关键词:分板定界法;遗传算法;最优罚函数;TslMR(2000)主题分类号:90Cl0中图法分类号:0221.7文献标识码:A:0255—7797(2004)05—0531—06l前言旅干亍商问题(I”ravelirgGalesrnanIrobhm简休TSI)是运筹学中一一个古老课题,其数学模型结为0一l规划问题.它是一个易于描述却又难于处理的一个NP完全问题?在许多领域仃广泛的应用.因此有效地解决FSt问题.在可计算理论上具有十分重要意义,【州时具有重要的实朋价值.近年来,求解TSt问题的研究十分活跃,其中大多数是近似求解.代去算法有包括遗传算法的许多近似算法.从遗传学观点来看,I’St繁体最lJ亡回路本身陶成一个染色体,它的每一分枝都可以看成一个.由于一般不易找到它,我们只有从大量近似最优回路中挑选出颁发高的分枝作为基闻.在种群进化到一定阶段时,这些个体应该干”最优个体具有许多相同的基因.根据这一特点,本文提出了一种新的基因整合算法.数值实验表明,该方法在一定范围内十分有效,并对CHN¨.1问题结出了日前最佳结果.2最优罚函数在利用中寸形搜索分枝定界法时,通常是要对原矩阵进行简化,即把距离矩阵各行各列减去其最小值.如果简化矩阵各行各列的零元素构成一条回路,则该回路即为最优解.如果不能构成一条回路.就需要利用最优罚函数米选择搜索回路分枝.所谓最优罚函数max{f]的是对(i,)位的零元素所对应的实数,由下式定义Fi—F___l激收稿日期:20O2()9一l1接收Et期:?()f13一O6一3基金项目:国家自然科学基金资助项目(70371032);中国教育部博士教育基金资助(20020486035)作者简介:燕子宗(1964一),男.湖北江陵.副敦授.在馥博士.研究方向最优化理论与算法.532数学杂志Vo1.24这里在距离矩阵D一(c,,)经过一次简化后得到的矩阵,F,和F,分别表示该简化矩阵第i行和第列中除(,)位置一个零元素以外的最小值,它们也被称为边(?-J.)所对应行和列的罚函数值.根据最优罚数nlax{F}的值来选择回路的边(i,),其含义是不选择(i,)时带来的损失将最大.然后删除该元素(√),从而达到降低基向量个数简化问题的目的.例l:考虑含有5个城市的TSP问题,距离矩阵D如下*O*41071O64476lOlO4*1O41O*949*对D可以采用不同方式简化,一般要求简化后的矩阵每行每列上至少有一个元素为零.一种方式是先简化所有行,再简化所有列;另一种方式是逐行逐列依次简化.即简化时对备行各列处理顺序不同,这样得到两个不同的简化矩阵:*11*06032O023030*22**OO*O9O6O1OO6172*44*利用最优罚函数寻优可以求得两条不同的”最优”回路f(4,1),(5,2),(1,3),(2,4),(3,5)),{(4,1),(5,4),(1,3),(3,2),(2,5)}其路径长分别为29和34.虽然最优罚函数加快了搜索最优回路的分枝,但是它寻找到的最优回路仍然具有局部最优特点.3最优罚函数实验性能尽管最优罚函数仅仅具有局部最优性,但是最优罚函数能加快解的收敛速度是勿用置疑的.在不进行回溯的前提下,利用最优罚函数搜索可以得到一条局部最优回路,与整体最优回路进行比较,具有相同分枝边数情况统计如下表(试验次数100次):表1一次寻优结果与整体最优结果相同分枝边数比较相同分枝城市数最少(边)最多(边)平均值百分比lO5lO8.3683.6Ol57l5l1.8679.062Oll2Ol5.0374.5l}25142519.S378.12I30l73022.9l76.86分析上面结论不难发现,对于城市规模不超过3O的TSP问题,利用最优罚函数一次寻优结果得到局部最优回路与整体最优回路在许多分枝上相同,回路分枝相同边平均超过了7O%.换句话说,这里局部最优回路与整体最优回路的平均接近程度达到7O以上.如果通过回溯穷举得到整体最优回路,那么势必造成已经获得的这部分信息大量丧失.尤其是在只有少数几条边不是整体最优回路边的情况下,为了获得整体最...