资源描述：
《求解大规模TSP问题的》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第卷第期工程数学学报年月,一一一文章编号求解大规模问题的混合算法,朱旭韩志西安交通大学理学院,西安摘要遗传算法求解大规模时呈现出求解时间长、后期效率明显降低等缺陷。通过结合分块方法、局部搜索算法以及禁忌算法,本文提出一个求解的混合算法,以提高初始解质量,减少计算量。利用遗传算法和混合算法对几个进行数值实验,表明无论在结果的质量上还是,,,。在运行效率上混合算法都明显优于遗传算法而且规模越大效果越明显关键词遗传算法分块方法搜索算法禁忌算法问题分类号中图分类号文献标识码引言货郎担问题升,以下简称是指给定个城市和两两城市之间的距离,要求确定一条经过各城市当且仅当一次的最短路线。近年来
2、基于遗传算法求解问题的研究相当活跃,如见凡罗,等人的工作。,遗传算法简称利用简单的编码技术和繁殖机制来表现复杂的现,、、,象它模拟生物界的复制取杂交变异的进化现象,,,。进行优胜劣汰按适应值高低来选择个体经过数代的进化可以得到较优化的解由于它不,、,以受搜索空间的限制性的约束不必要求诸如连续性导数存在和单峰等假设及其固有的并,、。行性遗传算法目前己经在最优化机器学习和并行处理等领域得到了广泛的应用冈遗传算法求解的优势,,。当用来解决时编码可采用自然编码方法即按每个城市代码组合成串复制则,。,按照适应度大小进行选择适应度函数通常取为路径长度的倒数杂交有多种方法应用比较多的是循环杂
3、交,即在父代中标号为坛的城市被选取,则在父代中标号为乞的城市也应当,,,。被选取如此得到的子代既包含父代的基因又与父代不同容易生成优于父代的新个体变异是通过很小的概率随机交换基因串中的某些位。可以看,,出在模糊计算中在全区域上有着很强的搜索能力而不容易陷入局部极小解,因,。尤其是遗传算法对于问题依赖性很弱此对于求解大规模具有优势遗传算法的劣势以及相应解决办法目,。,前遗传算法在求解大规模中应用十分广泛但仍存在一些劣势第一通过随机产生的第一代个体其性能无法保证第二,对于大规模,的杂交过程会消耗大量的计算,而,,时间且每一步进化要多次计算适应值第三当进化到后期阶段时种群中个体的适应
4、值,,。,已普遍很好而随着杂交与变异常会出现震荡的情况甚至是退化最后当遗传算法进行到中期的时候,物种就逐步趋子单一化,个体的相似程度很大,此时一种方法是在中期移入新个收稿日期一作者简介朱旭年月,男,副教授研究方向应用数学生今基金项目国家自然科学基金工程数学学报第卷,,。,体但新个体的适应值往往差异较大从而难以存活或杂交出新的优秀个体为此首先必须产生具有良好性能或能够组合出具有良好性能的第一代个体其次在进化过程中对于不良个体,。因,需要进行有目标的改良等从而需要对求解大规模的进行改造此本文提出求解的一种混合算法,该算法是将分块方法、探索方法以及禁忌算法进行有机的结合。混合算法的思
5、想与描述基于上面的讨论,下面试图提出一种混合方法来改进相关问题。首先对大规模进行分,。,块在城市较少的每个块中得出较优解后再合并其次是进行局部搜索它可以被看作是半精,因,。确搜索为在分块的基础上每块中城市的数目较少不容易陷入局部极小最后利用禁忌算法将原来所求解中的不良基因进行改造,使结果逐步最优。分块方法,,。对于大规模问题为了提高运算效率首先采用分块方法把问题化繁为简我们把整个问题分解成若干区和层,各层中的每个区作为一个小规模问题,并用精确或半精确算法求解,再把各层视为以每个区作为一个点的又一个小规模问题,结合局部搜索算法逐区逐层,以。,,求解快速地得到一个满意解譬如可将个城
6、市等分为个区则空间容量就由。缩小为。探索算法对于局部区域上小规模的求解,本文提出逐步搜索算法即求得序列中的一点后,探索其周围最近点,将其加入到序列中去。其实现步骤步骤在某一区域块中随机取一点,如图中点,。,,步骤从点出发找其最近点再从点出发找其最近点以此类推步骤按步骤得到一闭合路线。,步骤次重复执行步骤得到个路线再从中取出最优路线,一步骤对每个区域块按照步骤步骤产生相应的区域局部最优路线,寻,,步骤再随机从一个区出发找与其端点最近的区域的端点并将其连接起来以此类推,就得到一个完整的首尾相连的路线图,如图。图从开始探索路径图从开始探索路径,。,,,显然该算法容易陷入局部极小点如图
7、所示如果从点出发每次找最近点则形成一个路径较短但有交叉的路径。由于每一区的城市数目较少,同时每次出发点都是随机产生的,所以在得到局部较优解后再对其进行调整改良,从而使其成为一个性态良好的初始解。禁忌算法第期朱旭,韩志求解大规模问题的混合算法禁忌搜索七,简称最早由提出,它是对局部邻域搜索的一种扩展,,,是一种全局逐步寻优算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索并通过藐视准则来赦免一些被禁忌的优良状态,进而保证多样化的有效探索以最终实现全局最优化。相对于模拟退火和遗传算法,是
