２０１５年第２期 文章编号：１００６－２４７５（２０１５）０２－００３４－０６ 计算机与现代化 ＪＩＳＵＡＮＪＩ ＹＵ ＸＩＡＮＤＡＩＨＵＡ 第２３４期 基于改进遗传算法的大规模ＴＳＰ问题求解方案 雷玉梅 （阜新高等专科学校，辽宁阜新１２３０００） 摘要：ＴＳＰ问题不仅描述旅行商周游城市的问题，也是许多工程领域中复杂问题的抽象形式，找到一种有效的ＴＳＰ问题 求解方案具有十分重要的意义。针对大规模ＴＳＰ问题中最小回路代价的求解问题，提出一种基于遗传算法的大规模 ＴＳＰ问题的求解方案，采用分而治之的思想，并对传统遗传算法的初始化和遗传算子进行改进，提高了算法性能。多个 数据集上的实验结果证明了提出的算法能够优化收敛结果，一定程度上解决过早收敛的问题。 关键词：大规模ＴＳＰ问题；最短路径；遗传算法；改进遗传算法 中图分类号：ＴＰ３ｏ１．６ 文献标识码：Ａ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００６－２４７５．２０１５．０２．００８ Ａ Ｓｏｌｕｔｉｏｎ ｏｆ Ｌａｒｇｅ・ｓｃａｌｅ ＴＳＰ Ｂａｓｅｄ ｏｎ Ｉｍｐｒｏｖｅｄ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ ＬＥＩ ＹＵ．ｍｅｉ （Ｆｕｘｉｎ Ｈｉｇｈｅｒ Ｔｒａｉｎｉｎｇ Ｃｏｌｌｅｇｅ，Ｆｕｘｉｎ １２３０００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：ＴＳＰ ｎｏｔ ｏｎｌｙ ｄｅｓｃｒｉｂｅｓ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｔｒａｖｅｌｌｉｎｇ ａｒｏｕｎｄ ａ ｎｕｍｂｅｒ ｏｆ ｃｉｔｉｅｓ，ｂｕｔ ａｌｓｏ ｓｔａｎｄｓ ｆｏｒ ａ ｎｕｍｂｅｒ ｏｆ ｐｒｏｂｌｅｍｓ ｉｎ ｓｏｍｅ ｏｔｈｅｒ ｆｉｅｌｄｓ．Ｔｈｕｓ，ｉｔ ｉｓ ｍｅａｎｉｎｇｆｕｌ ｔｏ ｆｉｎｄ ａｎ ｅｆｆｅｃｔｉｖｅ ｓｏｌｕｔｉｏｎ ｔｏ ｌａｒｇｅ—ｓｃａｌｅ ＴＳＰ．Ａｓ ｆｏｒ ｔｈｅ ｓｏｌｕｔｉｏｎ ｔＯ ｆｉｎｄ ｔｈｅ ｍｉｎｉｍｕｍ ｄｉｓｔａｎｃｅ ｏｆ ａ ｌｏｏｐ ｃｏｎｓｉｓｔｉｎｇ ｏｆ ａ ｌａｒｇｅ ｎｕｍｂｅｒ ｏｆ ｃｉｔｉｅｓ ｉｎ ＴＳＰ，ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｗｅ ｐｒｏｐｏｓｅ ｓｕｃｈ ａ ｎｅｗ ｓｏｌｕｔｉｏｎ ｂａｓｅｄ ｏｎ ｇｅｎｅｔｉｃ ａｌ— ｇｏｒｉｔｈｍｓ．Ｉｔ ａｄｏｐｔｓ ｔｈｅ ｉｄｅａ ｏｆ ｄｉｖｉｄｉｎｇ ａｎｄ ｒｕｌｉｎｇ，ａｎｄ ｕｔｉｌｉｚｅｓ ａ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｉｍｐｒｏｖｅｄ ｉｎｉｔｉａｌｉｚａｔｉｏｎ ｍｅｔｈｏｄ ａｎｄ ｇｅｎｅｔｉｃ ｏｐｅｒａｔｏｒｓ ｔｏ ｉｍｐｒｏｖｅ ｉｔｓ ｐｅｒｆｏｒｍａｎｃｅ．Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ａｃｒｏｓｓ ｍｕｌｔｉｐｌｅ ｄａｔａｓｅｔｓ ｉｌｌｕｓｔｒａｔｅ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｐｅｒ— ｆｏｒｍｓ ｗｅｌｌ ｉｎ ｏｐｔｉｍｉｚｉｎｇ ｃｏｎｖｅｒｇｅｎｃｅ ｒｅｓｕｌｔ ａｎｄ ｓｏｌｖｉｎｇ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｐｒｅｍａｔｕｒｅ ｃｏｎｖｅｒｇｅｎｃｅ ｔｏ ｓｏｍｅ ｅｘｔｅｎｔ． Ｋｅｙ ｗｏｒｄｓ：ｌａｒｇｅ—ｓｃａｌｅ ＴＳＰ；ｓｈｏｒｔｅｓｔ ｐａｔｈ；ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ；ｉｍｐｒｏｖｅｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ０ 引 言 ＴＳＰ（Ｔｒａｖｅｌｉｎｇ Ｓａｌｅｓｍａｎ Ｐｒｏｂｌｅｍ）问题，也称旅行 商问题或货郎担问题，是一个典型的ＮＰ（Ｎｏｎ．ｄｅｔｅｒ— ｍｉｎｉｓｔｉｃ Ｐｏｌｙｎｏｍｉａ１）完全问题。它不仅描述了商人从 个城市出发，经过其他多个城市，且只经过一次之 后，又回到出发城市的问题，也是数学领域一个复杂 一ｒｉｔｈｍ），没有严密的数理逻辑，但通常能够更为高效 地求得可接受的问题的解，因此在实际中应用更为广 的组合优化问题，更是诸多领域内许多复杂问题的概 括的形式化描述。凡是可以抽象地表示为遍历且只 遍历所有结点一次，最终回到初始结点，求代价最小 的回路问题，都可以仿照求解ＴＳＰ问题的方法进行 求解。因此，ＴＳＰ问题的解决方案在计算机理论和实 际应用中得到广泛的关注。 目前解决ＴＳＰ问题的方法大致可以分为２大 类ｌＬ】ｊ，一类是拥有较好的数理逻辑和理论基础的精 确的计算方法（Ｅｘａｃｔ Ａｌｇｏｒｉｔｈｍ），能够找到问题的最 优解，另一类是近似的计算方法（Ａｐｐｒｏｘｉｍａｔｉｏｎ Ａｌｇｏ－ 收稿日期：２０１４—１１－０６ 泛，遗传算法就是一种典型的近似计算方法。 遗传算法是根据优胜劣汰的生物进化理论设计 出来的一种优化的搜索算法，主要通过遗传染色体信 息，选择对“环境”的“适应能力”高于父代的子代，直 到适应能力满足一定的要求。高经纬等人在文献 ［２］中证明了使用遗传算法求解ＴＳＰ问题时具有结 果准确、收敛速度快的特点。文献［３－９］从不同的方 面对遗传算法进行改进，提升了其解决ＴＳＰ问题的 能力。然而，对于大规模的ＴＳＰ问题，始终没有较好 的解决办法，也吸引了越来越多的研究学者的关注。 本文结合启发式的思想和改进的遗传算法，提出 了新的解决大规模ＴＳＰ问题的ＨＧ方法，采用分而治 之和启发式的初始化方法，利用改进的遗传算子，提 高了遗传算法的性能，多个数据集上的实验结果证明 了ＨＧ算法的有效性。 作者简介：雷玉梅（１９８０．），女，辽宁阜新人，阜新高等专科学校讲师，硕士，研究方向：计算机软件。 ２０１５年第２期 雷玉梅：基于改进遗传算法的大规模ＴＳＰ问题求解方案 ３５ １ 相关概念 １．１ ＴＳＰ问题形式化描述 给定Ｎ个城市的集合，城市用Ｃｉ，ｉ∈｛０，１，．．．， Ｎ一１］表示，Ｒ＝（Ｃ。，Ｃ ．．，ｅ 一 ）表示经过所有Ｎ 个城市的一条路线，当路线Ｒ满足公式（１）取得最小 值时，Ｒ即为ＴＳＰ问题的最优解： Ｎ一２ ｆ（Ｒ）＝ ｄ（ｃ．，ｃ．＋．）＋ｄ（ｃＮ一 ，ｃ。） （１） 其中，ｄ（Ｃｉ，Ｃｉ＋ ）表示城市Ｃｉ与城市Ｃｉ＋ 之间的距离， ｆ（Ｒ）表示路线Ｒ的距离。 解决ＴＳＰ问题的目标就是找到一条路线Ｒ ，使得 ｆ（Ｒ ）取得最小值。对于Ｎ个城市的ＴＳＰ问题，采用全 局搜索的方式，可行的组合有（Ｎ—１）！种，当Ｎ变得很 大时，全局搜索的方法已经不可能解决ｒｌＳｐ问题。 １．２遗传算法 遗传算法首先对问题中的参数集进行编码，形成 初始种群，计算适应度，然后通过染色体信息的代代相 传（利用选择、交叉和变异算子不停地进行算法迭代）搜 索具有最高适应度的个体，算法流程可用图１表示。 将问题中的参数信息编码为个体染色体信息 初始化种群 产生下一代种群 计算适应度 适应度是否满足要求 ～—＼—／ 是 葚甬 Ｊ否 根据交叉概率执行交叉算子 根据变异算子执行变异算子 解码输出 图１遗传算法流程图 ２ ＨＧ算法 ２．１聚类 本文沿用分而治之的思想解决大规模的ＴＳＰ问 题，根据坐标位置进行聚类操作，把相对位置较近的 城市划分到一个类簇（聚类的结果）中。城市之间的 “相似性”采用欧式距离描述，如公式（２）所示： （２） 其中，Ｐ表示结点的属性的数量，这里是２（城市的经 度和纬度），Ｗｉｊ表示结点ｃｉ与 ｊ的相似性。在ＴＳＰ 问题中，结点之间的欧式距离表示城市之间的位置距 离，因此聚类操作会把距离较近的城市划分到同一个 类簇，符合进行聚类操作的初衷。 经过聚类操作，把一个大规模的ＴＳＰ问题，划分 为多个类簇中的子ＴＳＰ问题，然后采用本文改进的 遗传算法求解各个子ＴＳＰ问题。 ２．２编码与初始化 本文采用序号编码的方式，把每个类簇中的城市 编号为１，２，３，…，ｎｉ，ｎｉ表示第ｉ个类簇的城市数量。 一条路径编码为一条染色体，用１～ｎｉ的任一排列组 合表示。 初始化过程用来构造初始的种群（染色体的集 合），初始化结果的好坏，一定程度上决定了遗传算 法收敛所用的时间。传统的遗传算法中，一般采用随 机的方式产生初始化种群，但是这种方法的不稳定性 极高，遗传算法的收敛可能需要很长时间。Ｏｓａｂａ等 人在文献［９］中指出，使用启发式的初始化函数能够 有效地提升遗传算法的性能。本文就采用了ＮＮ［１Ｏ］ 的启发式初始化函数，具体地，在类簇ｉ中随机选择 一个起始城市ｃ。∈｛１，２，…，ｎ；｝，然后根据公式（３） 依次选择剩下的ｎｉ一１个城市，组成初始路线： ｃｊ ａｒｇ “ｄ（ｃｊ，Ｃｋ），ｊ∈｛１，２ ．＇ｎｉ一１ｔ，ｋ∈｛１，２…．＇ｎ。｝ ｓ．ｔ．。ｊ鹾｛ｃ０，ｃｌ，。卜ｌ｝ （３） ＨＧ的初始化方法，使最初的路线拥有较高的适 应度，有利于从根本上提升算法的收敛速度以及优化 收敛结果。 ２．３适应度函数 适应度是用来评价个体对“环境”的适应能力， 适应度越高，说明适应能力越强。在ＴＳＰ问题中，适 应度可以用路线的距离来表示，路线的距离越短，说 明路线越优。为方便后续的遗传算子的操作，ＨＧ方 法采用公式（４）所示的适应度函数： ｎｉ一２ ｆ（Ｒ。）＝ （ＭＡＸ—ｄ（ｃ ，ｃ ｋ＋１））＋ＭＡＸ—ｄ（ｃ ；＿ｌ’ｃ０） （４） 其中，ＭＡＸ表示无穷大，ｆ（Ｒ；）表示种群中个体ｉ的适 应度，其值越大，表示个体的适应能力越强。 ２．４交叉算子 交叉是指父代２个个体的部分染色体信息进行 互换，重组为新的个体的操作，在生物进化的过程中 发挥着核心作用。遗传算法中的交叉算子同样发挥 着重要作用，但不是任意２个父代的个体都会进行交 叉操作，交叉行为的发生有一定的概率，发生交叉行 为的个体占种群个体总数的比例称为交叉率。由于 ＨＧ方法采用的是序号编码，因此采用单亲遗传的方 法，在单条染色体内进行单点交叉操作。对满足交叉 率的染色体，利用公式（５）选择交叉点： ３６ 计算机与现代化 ２０１５年第２期 ｔｉｋ＝ａｒｇ ｍａｘ ｄ（ｃｉ，ｃ｛＋１），ｊ∈｛０，１，．．．，ｎ。一２｝，ｋ∈｛１， Ｊ ２，．．．，Ｓ｝ （５） 其中，ｔｉ 表示染色体ｉ的第ｋ个交叉点，Ｓ表示交叉点 的总数。由公式（４）可知，根据路线Ｒ 中连续２个城 市之间的距离最远的ｓ个位置，依次选择ｓ个交叉 点，把染色体ｉ切成Ｓ＋１个片段，然后将这Ｓ＋１个 片段重新组合成完整的一条染色体。 ＨＧ的交叉算子消除了个体中对适应度影响最 大的染色体信息（切断路线中距离最远的连续的２个 城市），有利于促进算法的收敛进程，同时能够增加 种群的多样性，有利于避免过早收敛的现象。 ２．５变异算子 变异算子是指对染色体上某位置的信息进行变 动，比如，交换路线上任意２个不同城市的位置。跟 交叉操作一样，变异操作同样有变异率的约束，是指 发生变异的个体占种群中个体总数的比例。传统的 遗传算法通常为变异率选择固定的数值，而ＨＧ算法 利用公式（６）定义动态的变异率： ｍｕｔａｔｉｏｎ＝— （６） 其中，ｍｕｔａｔｉｏｎ表示变异率，分子表示种群中染色体信息 相同的个体数目的最大值，分母表示种群的数量。比 如，随着算法的迭代，在某一世代的种群中染色体Ａ出 现了２次，染色体Ｂ出现了３次，且Ａ≠Ｂ，且没有其他 染色体对应多个个体，则公式（６）的分子值为３。 在满足变异率的前提下，随机交换染色体２个位 置的信息，而且在算法迭代初期，只针对染色体的前 段信息进行变异操作，以扩大解空间的搜索范围，到 算法迭代后期，则只变异染色体的后段信息，否则可 能会影响算法的收敛。 ＨＧ算法的动态变异算子，保证了种群的多样 性，有利于避免过早收敛的问题，同时还保证了较大 的解空间的搜索范围和较好的收敛结果。 ２．６选择算子 选择算子用来把种群中的优良个体直接选人下 一代。轮盘赌方法是一种简单又常用的选择方法，每 个个体对应一个选择概率，适应能力强的个体，选择 概率大，适应能力低的，选择概率小，选择概率通过公 式（７）计算： ｐ。ｋ 雨 —一： （７）， ｌ ∑ｆ（Ｒ １ 。 ） 其中ｐｉｋ表示种群ｉ中个体ｋ的选择概率。 由公式（７）可知，种群中所有个体的选择概率之 和为１，因此可以通过累加的方式为每个个体确定一 个概率区间。比如个体１的选择概率为０．１，个体２ 的选择概率为０．２，则个体１的概率区间为０～０．１， 而个体２为０．１～０．３。然后根据０～１区间内的一个 随机数，确定被选中的个体。 ２．７全局ＴＳＰ问题的解 在求得各子ＴＳＰ问题的解之后，需要将它们集 成为全局的ＴＳＰ问题的解，即把各个类簇连接起来。 ＨＧ方法仿照单链接的聚类方法，在２个待连接的类 簇之间应用２次单链接方法，把２个类簇连接起来， 但要求２次单链接方法选中的４个点必须是２对点， 即同一个类簇中的２个点是直接相连的。单链接聚 类是指根据２个类簇对象之间的最短距离连接类簇 的方法，具体可由图２表示。 ＼ ＼＼ ．．．．一．．．．．．．．．．．．． ．．．一．．．．一 ．．．．．．．．．．．．．．．．．．．．．．．． ．．．．．．．．． ／ ＼ 图２聚类连接 图２中，中间的虚线分割的上下２个类簇就是待 连接的类簇。２次单链接方法，分别可以找到结点１ 和３之间的虚线，以及结点２和４之间的虚线，然后 把结点１和２之间以及结点３和４之间的黑色加粗 连线剪断，把结点１和３以及结点２和４连接起来， 就成功地把２个类簇连在了一起。实际操作过程中， 是先找到２个类簇距离最近的４个点，如图２中的１， ２，３，４，然后比较１．３，２＿４的距离之和与１ ４，２—３的距 离之和，选择较短的一组进行连接。这样就把２个类 簇连接成了一次类簇，再继续与其他的类簇连接，就 可以得到全局的ＴＳＰ问题的解。 ２．８ ＨＧ算法流程 根据前文的阐述，可用表１描述ＨＧ算法的流程。 表１ ＨＧ算法流程 ２０１５年第２期 雷玉梅：基于改进遗传算法的大规模ＴＳＰ问题求解方案 ３７ ３ 实 验 为了验证ＨＧ算法解决大规模的ＴＳＰ问题的性 能，本节选用标准问题库ＴＳＰＬＩＢ的Ａ２８０和 ＮＲＷ１３７９两个数据集进行实验，采用标准的遗传算 法（ＳＧＡ）以及Ｌｅ等人 和金聪 提到的利用启发 式思想改进的遗传算法作为对比算法。文献［１０］主 要将ＮＮ的启发式思想用于初始路径的选取（Ｈ． ＮＮ），而文献［１ １］则选用梯度寻优技术对变异算子 进行了改进（Ｈ—ＧＯ）。 实验中选用ｋ－ｍｅａｎｓ的聚类方法 １２ｊ，Ａ２８０数据 集聚成１０个类簇，ＮＲＷ１３７９数据集聚成２５个类簇。 实验均在Ｉｎｔｅｌ ｉ５处理器、２Ｇ的ＰＣ机上运行。 图３和图４分别展示了ＨＧ和Ｈ—ＮＮ算法在２个 数据集上随着迭代次数的增加，所计算出来的全局联 通路径的长度的变化，而图５和图６则是与ＳＧＡ算 法以及Ｈ．ＧＯ算法的对比结果。 全 局 距 离 算法迭代次数 图３路径长度随迭代次数的变化（Ａ２８０） 迭代次数 图４路径长度随迭代次数的变化（ＮＲＷ１３７９） 全 局 距 离 图５ ＨＧ ＶＳ（ＳＧＡ＆＆Ｈ—ＧＯ）（Ａ２８０） 图６ ＨＧ ＶＳ（ＳＧＡ＆＆Ｈ—ＧＯ）（ＮＲＷ１３７９） 从图３～图６可以看出，随着迭代次数的增多， ＨＧ算法计算得到的路径长度逐渐减小。在Ａ２８０数 据集上，ＨＧ算法经过３ ０００次迭代之后，路径长度已 减小到３ ２００左右，而ＳＧＡ算法仍徘徊在１３ ０００附 近，大概是ＨＧ计算结果的４倍。Ｈ—ＮＮ与ＨＧ算法 的效果比较接近，但Ｈ—ＧＯ算法由于采用了梯度优化 的方法，在算法迭代后期，收敛速度较慢。在 ＮＲＷ１３７９数据集上，ＨＧ算法经过５ ０００次迭代，路 径长度已减小到６８ ０００左右，而ＳＧＡ算法的计算结 果却仍相当于ＨＧ的７倍之多。Ｈ—ＮＮ算法由于并没 有考虑样本的多样性，出现了过早收敛的趋势，而Ｈ— ＧＯ算法同样存在后期收敛速度减缓的问题。此外， ＳＧＡ算法在Ａ２８０数据集上表现出了不稳定，距离长 度曲线有回升的情况，这是由于算法运行一段时间 后，路径的前段序列已接近最优，而在变异算子随机 交换了２个结点之间的顺序之后，使得原本较优的路 径变差所导致的，采用动态变异算子的ＨＧ算法就没 有出现这种情况。 迭代次数的增加，必然伴随着运行时间的增加，图７ ３８ 计算机与现代化 ２０１５年第２期 和图８展示了算法计算结果随着运行时间的变化。 运行时间／ｓ 图７路径长度随运行时间的变化（Ａ２８０） （ａ）ＨＧ算法 （ｂ）ＳＧＡ算法 图８路径长度随运行时间的变化（ＮＲＷ１３７９） 从图７和图８中可以看出，随着运行时间的增 加，ＨＧ算法和ＳＧＡ算法计算的路径长度大体都呈下 降趋势，但两者之间仍存在很大差距。例如在 ＮＲＷ１３７９数据集上，当ＨＧ算法的计算结果达到７０ ０００左右时，ＳＧＡ的计算结果还停留在２５０ ０００附近， 并且有出现过早收敛的迹象，而ＨＧ算法则始终呈现 较好的下降趋势。在图７和图８中，Ｈ．ＮＮ算法过早 收敛的问题和Ｈ．ＧＯ后期收敛速度缓慢的问题表现 的更加明显。 此外，为了直观、明显地观察ＨＧ算法分而治之 的思想，以及各个类簇连接的效果，图９展示了 ＮＲＷ１３７９数据集上ＨＧ算法在迭代５ ０００次之后的 路径（并没有把各个聚类连接），而图１０则展示了 Ａ２８０数据集上类簇连接前后的路径结果图，同样证 明了ＨＧ算法的有效性。 图９ ＮＲＷ１３７９数据集路径 结点横坐标 （ａ）类簇连接前 结点横坐标 （ｂ）类簇连接后 图１０ Ａ２８０数据集路径 ２０１５年第２期 雷玉梅：基于改进遗传算法的大规模ＴｓＰ问题求解方案 ３９ Ｉ 数据集 Ｊ ＨＧ均值 Ｊ ＨＧ均方差Ｊ ＳＧＡ均值｝ＳＧＡ均方差Ｊ Ｉ Ａ２８０ ｌ ３ ０９９．７９ ｌ ５６．０８９ ｌ ３６９１．１ ｌ ６１．１３ ｌ Ｉ ＮＲＷ１３７９ ｌ ６９ １０４．３５ ｌ ９２９．６４８ ｌ ４５４ ４４０．１ ｌ ５ ３５２．６ Ｉ ｎｏａｔ： （８） ４ 结束语 ［４］Ｙｕ Ｙｉｎｇｙｉｎｇ，Ｃｈｅｎ Ｙａｎ，Ｌｉ Ｔａｏｙｉｎｇ．Ａ ｎｅｗ ｄｅｓｉｇｎ ｏｆ ｇｅ－ ｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｓｏｌｖｉｎｇ ＴＳＰ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｆｏｕａｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｉｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｓｃｉｅｎｃｅｓ ａｎｄ Ｏｐｔｉｍｉｚａｔｉｏｎ．２０１１：３０９—３１３． ［５］ 王斌，李元香，王治．一种求解ＴＳＰ问题的单亲遗传算 法［Ｊ］．计算机科学，２００３，３０（５）：７３－７５． ［６］ 李茂军，朱陶业，童调生．单亲遗传算法与传统遗传算 法的比较研究［Ｊ］．系统工程，２００１，１９（１）：６１－６５． ［７］ Ｃｈｅｎ Ｊｕｎｈｏｎｇ，Ｈｕ Ｊｕｎｘｉａｎｇ，Ｚｈｅｎ Ｘｕｎｙａｎ．Ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｉｍｐｒｏｖｅｄ ｐａ￣ｈｅｎｏ—ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｉｎ ｄｉｓｔｉｒｂｕｔｉｏｎ ｎｅｔ— ｗｏｒｋ ｓｗｉｔｃｈ ｏｐｔｉｍａｌ ｐｌａｎｎｉｎｇ［Ｃ］／／２０１０ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｅｌｅｃｔｉｒｃａｌ ａｎｄ Ｃｏｎｔｒｏｌ Ｅｎｇｉｎｅｅｒｉｎｇ （ＩＣＥＣＥ）．２０１０：４６７４７０． ［８］ Ｙａｎｇ Ｊｉｎｑｉｕ，Ｙａｎｇ Ｊｉａｎｇａｎｇ，Ｃｈｅｎ Ｇｅｎｌａｎｇ．Ｓｏｌｖｉｎｇ ｌａｒｇｅ— ｓｃａｌｅ ＴＳＰ ｕｓｉｎｇ ａｄａｐｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇ ｍｅｔｈｏｄ［Ｃ］／／Ｔｈｅ Ｓｅｃｏｎｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｃｏｍｐｕｔｉｏｎａｌ Ｉｎｔｅｌｌｉ— ｇｅｎｃｅ ａｎｄ Ｄｅｓｉｇｎ．２００９：４９—５１． ［９］Ｏｓａｂａ Ｅ，Ｃａｒｂａｌｌｅｄｏ Ｒ，Ｄｉａｚ Ｆ，ｅｔ ａ１．Ｏｎ ｔｈｅ ｉｎｆｌｕｅｎｃｅ ｏｆ ｕｓｉｎｇ ｉｎｉｔｉａｌｉｚａｔｉｏｎ ｆｕｎｃｔｉｏｎｓ ｏｎ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍｓ ｓｏｌｖｉｎｇ ｃｏｍｂｉｎａｔｏｒｉａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍｓ：Ａ ｆｉｒｓｔ ｓｔｕｄｙ ｏｎ ｔｈｅ ＴＳＰ［Ｃ］／／２０１４ ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｅｖｏｌｖｉｎｇ ａｎｄ Ａｄａｐ． ｔｉｖｅ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ（ＥＡＩＳ）．２０１４：１－６． ［１０］Ｌｅ Ｎｙ Ｊ，Ｆｅｒｏｎ Ｅ，Ｆｒａｚｚｏｌｉ Ｅ．Ｏｎ ｔｈｅ Ｄｕｂｉｎｓ ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ『Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ａｕｔｏｍａｔｉｃ Ｃｏｎｔｒｏｌ，２０１２，５７（１）：２６５－２７０． ［１１］金聪．启发式遗传算法及其应用［Ｊ］．数值计算与计算 机应用，２００３，２４（１）：３０—３５． ［１２］戴文华，焦翠珍，何婷婷．基于并行遗传算法的Ｋ．ｍｅａｎｓ 聚类研究［Ｊ］．计算机科学，２００８，３６（６）：１７１—１７４． ［１３］戚玉涛，刘芳，焦李成．求解大规模ＴＳＰ问题的自适应 规约免疫算法［Ｊ］．软件学报，２００８，１９（６）：１２６５— １２７３． ［１４］赵连朋，金喜子，王娜，等．求解超大规模旅行商问题的 纵深遗传算法［Ｊ］．计算机工程与应用，２００９，４５（４）： ５６—５８． ［１５］左国才，杨金民．Ｋ．ｍｅａｎｓ算法在电信ＣＲＭ客户分类中 的应用［Ｊ］．计算机系统应用，２０１０，１９（２）：１５５—１５９． ［１６］温光辉，王明旭，郭嗣琮．一种求解ＴＳＰ问题的新型遗 传编码方案［Ｊ］．科学技术与工程，２００６，６（２）：２０６． ２０８ ［１７］滕奇志，唐棠，何小海，等．基于交换．单亲遗传算法的 砂岩三位显微图像重建［Ｊ］．数据采集与处理，２０１０， ２５（３）：３６４—３６８．
