现代优化计算方法研究报告——遗传算法解决TSP问题

1现代优化计算方法研究报告——遗传算法解决TSP问题授课老师：专业：学号：姓名：2摘要旅行商问题（TSP）是典型的NP完全问题，遗传算法是解决NP完全问题的一种常用算法。本文首先简要介绍了TSP问题和遗传算法，然后用遗传算法对TSP问题进行了求解，并在MATLAB上进行了编程实现。最后探讨了遗传算法解决TSP问题的一些特点。关键词：TSP问题；遗传算法；MATLAB3目录摘要................................................................................................................................2目录................................................................................................................................31旅行商问题................................................................................................................41.1旅行商问题简介.............................................................................................41.2TSP的数学描述..............................................................................................42遗传算法....................................................................................................................42.1遗传算法简介.................................................................................................42.2遗传算法的步骤.............................................................................................53遗传算法求解TSP问题...........................................................................................53.1初始群体和适应度函数.................................................................................63.2城市的位置和城市间的距离.........................................................................63.3交叉和变异.....................................................................................................63.4种群的更新和迭代终止条件.........................................................................64MATLAB仿真以及运行结果...................................................................................75总结............................................................................................................................7附件——MATLAB程序代码......................................................................................841旅行商问题1.1旅行商问题简介旅行商问题（travelingsalesmanproblem,TSP）是一个有名的、典型的、易于描述却难以求解的组合优化问题。TSP已被证明具有NPC计算复杂性，并且许多实际问题都可以转化为TSP。它是一个具有广泛的实用背景和重要的理论价值的组合优化难题。1.2TSP的数学描述一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为ijd，如何选择一条道路使得商人每个城市走一遍后回到起点且所走路径最短？TSP可以细分为对称和非对称距离两大类问题。当jiddjiij,,时，称为对称距离TSP，否则为飞对称距离TSP。对于一般的TSP，一种数学模型描述为jiijijxdmin（1-1）njijnixts1,,2,1,1..（1-2）niijnjx1,,2,1,1（1-3）SjiijnSnSSx,},,2,1{,2||2,1||（1-4）jinjixij,,,1,},1,0{（1-5）以上是基于图论的数学模型，其中式（1-5）中的决策变量1ijx表示商人行走的路线包含从城市i到城市j的路径，0ijx表示商人没有选择走这条路。ji的约束可以减少变量的个数，使得共有)1(nn个决策变量。目标（1-1）要求距离之和最小。式（1-2）要求商人从城市i恰好出来一次，式（1-3）要求商人恰好走入城市j一次。式（1-2）和式（1-3）合起来表示每个城市恰好经过一次。仅有约束（1-2）和（1-3）无法避免子回路的产生，因此，式（1-4）约束旅行商在任何一个城市真子集中不形成回路，其中||S表示集合S中元素个数。2遗传算法2.1遗传算法简介遗传算法（geneticalgorithms,GA）是由Holland教授在20世纪70年代初期首先提出来的。1975年，Holland出版了第一本比较系统论述遗传算法的专著《AdaptationinNaturalandArtificialSystems》。遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。它起源于达尔文的进化论,，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。其主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不以梯度信息为基础。它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题,可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。作为一种全局优化搜索算法,遗传算法以其简单通用、鲁棒性强、适于并行处理以及应用范围广等特点,使其成为21世纪智能计算核心技术之一。进入80年代,遗传算法迎来了兴盛发展时期,5无论是理论研究还是应用研究都成了十分热门的话题。2.2遗传算法的步骤遗传算法主要借鉴了生物进化的一些特征，它的一些主要生物进化特征体现在下面几个方面：1．进化发生在解的编码上。这些编码按生物学的术语称为染色体。由于进行了编码，优化问题的一切性质都通过编码来研究。编码和解码是遗传算法的一个主题。2．自然选择规律据顶哪些染色体产生超过平均数的后代。遗传算法中，通过优化问题的目标而人为地构造适应函数以达到好的染色体产生超过平均数的后代。3．当染色体结合时，双亲的遗传基因的结合使得子女保持父母的特征。4．当染色体结合后，随机的变异会造成子代与父代的不同。最优化问题的求解过程是从众多的解中选出最优的解。生物进化的适者生存规律使得具有生存能力的染色体以最大的可能性生存。这样的共同点使得遗传算法能在优化问题中应用。遗传算法的步骤简化如下：STEP1选择问题的一个编码；给出一个有N个染色体的初始种群POP（1），1:t。STEP2对种群POP(t)中的每个染色体)(tpopi计算它的适应函数))((tpopfitnessfii。STEP3若停止规则满足，则算法停止；否则，计算概率NiffpNjjii,,2,1,1（轮盘赌），并以概率分布从POP(t)中随机选一些染色体构成一个种群},,2,1|)({)1(NjtpoptNewPOPj注：)1(tNewPOP集合中可能重复选)(tPOP中的元素。STEP4通过交配，得到一个有N个染色体的)1(tCrossPOP。STEP5以一个较小的概率p，使得染色体的一个基因发生变异，形成)1(tMutPOP；1:tt，一个新的群体)()(tMutPOPtPOP；返回STEP2。遗传算法的本质是处理复杂问题的一种鲁棒性强的启发性随机搜索算法,由于其全局搜索的特性，遗传算法在解决TSP问题中有着其他算法所没有的优势。本文提出的TSP问题包含15个城市之间的距离。下面针对这个TSP问题进行遗传算法的编程和求解。3遗传算法求解TSP问题给定某个TSP问题，15个城市之间的距离如图1所示。6图1TSP问题中15个城市间的距离矩阵3.1初始群体和适应度函数初始群体采用随机生成的形式，在MATLAB中使用randperm(N)产生一个N1的矩阵（N为所有城市的个数，本例中为15）为一个随机路径。利用Nm矩阵即可存储具有m个个体的初始群体。本例中，计算第i个个体的适应度的函数为)min/(max)()(LenLeniLengthifitness通过适应函数，使群体得到更新。3.2城市的位置和城市间的距离城市的位置使用随机生成的坐标参数来确定。种群中每个个体的城市序列决定的城市总距离可通过MATLAB程序得到（具体程序代码见附件）。3.3交叉和变异在经过淘汰得到种群之后，需要进行交叉和变异操作。由于染色体编码是非常规码，双亲遗传很容易出现不可行解。因此本文采用单亲遗传法。单亲遗传的一个特点是只有一个父代，下一代的产生通过单亲自身的基因变化。交叉方式为：选定一个单亲，随机选两个基因位置，将两个位置的元素进行交换。例如，父代染色体10987654321A交叉之后产生的子代染色体10983654721A变异方式为：在染色体序列中随机选择两个基因位置，将这两个基因中的染色体序列反序排列。例如，某个个体的染色体10987654321A变异之后产生的新的个体的染色体10983456721A3.4种群的更新和迭代终止条件在交叉和变异过程之后，父代种群和子代种群共同构成一个新的种群NewPOP，显然，新的种群个体数大于m，为了保证种群数量不变，必须进行种群的更新。本例中种群更新的方式：将NewPOP中所有个体的适应度从小到大7排列，然后选出前200个适应度所对应的个体作为更新后的种群。种群迭代的终止方式，由种群迭代步数C决定。当种群迭代步数达到给定的C时就停止算法。4MATLAB仿真以及运行结果给出20次算法的运行结果，统计数据如表1所示。表1MATLAB仿真的20次运行结果运行结果-839、-836、-832、-837、-841、-838、-841、-839、-833、-844、-837、-836、-841、-839、-837、-834、-844、-835、-834、-841最佳性能-844最差性能-832平均性能-837.9000方差11.7789这20次运行结果中，最优结果为-844，对应的城市路径为135931421516412810711最优结果的图形如图2所示。图2最优结果的图形5总结本次研究报告用遗传算法对TSP问题进行了求解，证明了遗传算法在求解TSP问题时，具有可行性，并且M