资源描述：
《多旅行商问题遗传算法求解及其改进》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、多旅行商问题遗传算法求解及其改进熊翠，吴慧萍，李波华中师范大学，数学与统计学学院，湖北，武汉，430079摘要：旅行商问题是一个著名的组合优化问题,多旅行商回路是旅行商问题的扩展，本文综合均衡度，提岀应用遗传算法求解多旅行商问题的算法设计，并将其与模拟退火法比较与结合，有效提高了运算的速度和效率。关键词：多旅行商问题：遗传算法；均衡度：模拟退火算法；模拟退火遗传算法：旅行商问题（TravelingSalesmanProblem,简称TSP）卩是一个著名的组合优化问题：给定"个城市，有一个旅行商从某一城市出发，访问每个城市各一次
2、后再回到原出发城市，要求找出的巡回路径最短。如果用图论来描述，那就是己知带权图G:（C,勾，寻岀总权值最小的Hamilton圈。多旅行商回路（MTSP）是旅行商问题（TSP）的扩展。MTSP是指给岀N个城市的集合，M个推销商从目标城市出发，分别走一条行路线，使得每个城市有且仅有一个推销商走过，最后回到原来的出发城市，且总旅程最短。有关MTSP问题的研究在现实问题中有很大的使用价值周。诸如：交通运输、管道铺设、路线的选择、计算机网络的拓扑设计、邮递员送信等,都可抽象成TSP或MTSP问题。遗传算法（GeneticAlgorith
3、m）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的,是求解复杂的组合优化问题的有效方法，遗传算法在求解TSP和MTSP问题中得到了广泛的应用。而在求解多旅行商问题的时候，常常只能保证总路程最短,很少达到使每个推销商的路程均衡,第四届中国智能计算大会论文集，芜湖2010年5月2卜25日，第127-133页导致结果不合理，推销商任务不平均，不能合理利用资源。2•遗传算法模型2-1遗传算法
4、简介遗传算法是一种以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与同一群染色体的随机信息变换机制相结合的搜索算法。它通过给解向量编码、形成初始种群，然后用变异、交叉重组、自然选择等算子,进行并行迭代，求得优化解。由于它采用随机运算，对搜索空间无特殊要求,无需求导，具有运算简单、收敛速度快等优点。其主要步骤为：1）先初始产生/个编码个体；2）计算每个个体的目标函数；3）利用轮盘法选出N个个体作为下一代变异对象；4）对选岀的个体按概率循环变异，交叉选择，产生新的Tt群体；5）比较现有记录，如果比现有记录更优，记录下群体中
5、最优的/个个体：重复第二步，这样遗传到足够多代后，会收敛到一个近似最优解,算法结束。根据上述步骤,我们可结合多旅行商问题的特点，i—进行研究。2-2遗传个体的编码设计221旅行商问题的编码设计在遗传算法中，遗传个体的设计很重要，需要体现个体的遗传特性，在这儿设计编码如下：以卜个城市三个推销商为例，设A为是个城市的最短距离矩阵，用A矩阵对应的行列数1.2,3,4,5,6,7,8,9,10分别表示十个城前，其中点1表示旅行商的出发城市。在旅行商问题中,我们将这十个城市，保持起点在第一位，按次序排列表示一个结果（即染色体）：如：I,
6、2,6,3,5,4,7,8,9,10路径表示:1—2—6—3—5—4—7—8—9—10—1运算量大，表示复杂。222多旅行商问题的编码设计不妨假定此多旅行商问题存在着三条路线，同样以十个城市为例，我们需要插入两个虚点11.12用来表示路线的起点,并形成新的编码，可用来表示多旅行商问题的染色体：如：165,2,4,11,7,8,3,12z9,10二个路径表示为：1——6——5—2——.4—.1;1—7——8—3.—1;1—9—10—1。设置节点I,II,12之间的距离为无穷大（即永远不能达到）,到其它各点距离与1点一致，得到新的
7、最短距离矩阵刃：（d）12zxl2对应的行列数分别表示12个节点。并且这样遗传算法选择变异就不会得到1—1—1的路径。2-3遗传算法的目标函数遗传算法涉及到个体选择,淘汰适应性差的个体，因此，需要建立目标函数来评价个体的好坏。对于目标函数的确定，可以从四个方面进行考虑。1）总路程最短3即为三条路线距离的总和。即为：/!，其中/,表示第；条线路的长度。2）均衡度在保证了总路程最短的情况下，很有可能会出现其中某一条路线过长、负载过重，而某一条路线过短，甚至完全没有经过任何点就直接回到原点，这样的多旅行商问题就没有任何意义了。所以我
8、们需要引用均衡度的概念。均衡度的意义在于让每一条路线尽量保持均衡，故只要能满足这一条件的约束函数都能定义为均衡度。一般地，传统的均衡度定义为max{Jri,H1.2,3},Jc=~iJmaxvui回1,2,3}吴慧此时,运篦吐.表示菊J。为定义在0到1之间的数，其值越接近0时
