基于遗传算法与模拟退火算法的旅行商问题研究论文.doc

《基于遗传算法与模拟退火算法的旅行商问题研究论文.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于遗传算法与模拟退火算法的旅行商问题研究AstudyofGeneticAlgorithmandSimulatedAnnealingforTravelingSalesmanProblemAbstract:(null)Keywords:GeneticAlgorithmSimulatedAnnealingTSP摘要:启发式算法被用来求解NP难问题，遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。模拟退火算法是一种通用概率算法，用来在一个大的搜寻空间找问题的最优解。两种算法各具优势，本文主要研究学习遗传算法和模

2、拟退火算法，并在此基础之上结合两算法的优点，将遗传算法和模拟退火算法思想相结合研究旅行商问题。关键词遗传算法模拟退火算法旅行商问题1.TSP问题描述旅行商问题是组合优化问题领域中的著名难题之一。问题描述：旅行商从驻地出发，经过每个所要访问的城市一次且只经过一次，并最终返回驻地。问如何安排旅行的路线使得旅行的总路程最短。旅行商问题在军事通讯电路板的设计大规模集成电路基因排序等领域具有广泛的应用。给定一个完全无向带权图G=（V,E），其中每一边有一非负权值（代价）w(u,v)。目的是要找到G的一条经过每个顶点一次且仅经过一次的回路，即汉密尔顿回路{v1,v2,…vn}使得回路的总权

3、值和最小。即：对于这种类型的旅行商问题，如果顶点数为

4、V

5、，则搜索空间是

6、V

7、顶点的一个全排列，其大小为

8、V

9、！2.遗传算法求解TSP2.1遗传算法介绍遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因

10、型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。遗传算法伪代码：G

11、A()1t←0;initializePop(t)withNchromosomesPopi(t)2whilenot(terminatingcondition)do3fori←1toNdofi←f(Popi(t))4fori←1toNdo5NewPopi(t+1)←randomlychoosePopi(t)∈Pop(t)withpj=fj/(∑kfk)6CrossPop(t+1)←recombine(NewPop(t+1))withpc7MutPop(t+1)←mutate(CrossPop(t+1))withpm8Pop(t+1)←MutPop(t+1)9t←t+1遗传算法包括以

12、下几个重要的部分：1)编码和初始群体的生成2)适应度函数3)选择算子4)杂交算子5)变异算子6)终止条件[1]遗传算法作为一种全局最优算法，具有简单通用、健壮性强、适于并行处理以及高效、使用，具有智能求解许多复杂问题的能力，在组合优化问题，而本文所研究的正是组合优化问题中的经典问题TSP、神经网络学习。模式识别等领域得到了广泛的应用。缺点是待定参数太多，计算速度比较慢。2.2遗传算法解TSP2.2.1染色体和种群编码旅行商问题的解形式为1N的全排列，不同城市构成染色体上的基因，由这些基因构成基因序列即染色体。基因编码形式为：n，其中，n为1到N中的任意数字。染色体直接表示旅行商

13、问题的任意解，染色体有自身的适应生存的能力，本文中称为适应度。适应度越大，生存能力越强，越能够在竞争中获胜而生存或者参与配对产生下一代。旅行商的解是最小化问题，需用一个足够大的数字减去路程总权值和，可得到染色体适应度。染色体编码为：{H，fitness}，其中H为哈密顿回路，亦可认为是染色体编码，fitness为染色体适应度。种群的由大量的染色体构成。种群的大小即为种群中染色体的个数。种群亦有自身的适应度，它的适应度是所有染色体适应度的总和。种群的适应度表征种群的生存能力，种群的适应度越强，