关于一种基于基因库和多重搜索策略求解tsp的遗传算法

1 / 12 关于一种基于基因库和多重搜索策略求解TSP 的遗传算法 论文 关键词：旅行商问题 遗传算法 基因库 多重搜索策略 论文摘要： TSP是组合优化问题的典型代表 ,该文在分析了遗传算法的特点后 ,提出了一种新的遗传算法 (GB MGA),该算法将基因库和多重搜索策略结合起来 ,利用基因库指导单亲遗传演化的进化方向 ,在多重搜索策略的基础上利用改进的交叉算子又增强了遗传算法的全局搜索能力。通过对国际 TTSP 库中多个实例的 测测试 ,结果表明 :算法 (GB MGA)加快 了了遗传算法的收敛速度 , 也加强了算法的寻优 能能力。 TSP(tra veling sal esman prob lem)可以简述为 : 有 n 个城市 1,2,n, 一旅行商从某 一一城市出发 ,环游所有 城城市后回到原出发地 ,且且各城市只能经过一次 , 要求找出一条最短路 线线。 TSP 的搜索空间 是是有限的 ,如果时间不 受受限制的话 ,在理论上 这这种问题终会找到最优 解解 ,但对于稍大规模的 TTSP,时间上的代价 往往往是无法接受的。这 是是一个典型的组合最优 化化问题 ,已被证明是 NP 难问题 ,即很可能不 存存在确定的算法能在多 项项式时间内求到问题的 解解 1。由于 TSP 在在工程领域有着广泛 的 应应用 ,如货物运输、加 工工调度、 网络 通 讯 、电气布线、管道铺设 等等 ,因而吸引了众多领 域域的学者对它进行研究 。 TSP的求解方法种 类类繁多 ,主要有贪婪法 、穷举法、免疫2 / 12 算法 22、蚂蚁算法 3、模拟退火算法、遗传 算算法等。 遗传算法是 一一种借鉴生物界 自然 选择和遗传机制的随 机机化搜索算法 ,其主要 特特点是群体搜索策略和 群群体中个体之间的信息 交交换 ,搜索不依赖于梯 度度信息 4。遗传算 法法主要包括选择、交叉 和和变异 3 个操作算子 ,它它是一种全局化搜索算 法法 ,尤其适用于传统搜 索索算法难于解决的复杂 和和 非线性问题。遗传算 法法虽然不能保证在有限 的的时间内获得最优解 ,但但随机地选择充分多个 解解验证后 ,错误的概率 会会降到可以接受的程度 。 用遗传算法求解 TSSP 能得到令人满意的 结结果 ,但是其收敛速度 较较慢 ,而且种群在交叉 算算子作用下 ,会陷入局 部部解。采用局部启发式 搜搜索算法等 ,虽然能在 很很短的时间内 计算 出出小规模城市的高质量 解解 ,一旦城市规模稍大 就就容易陷入局部最优解 。因此 ,为了能够加快 遗遗传算法的收敛速度 ,又又能得到更好的近似最 优优解 ,该文采纳了文 55中杨辉提出的基因 库库的想法 ,并结合文 66中 Cheng-Fa Tsai提出的多 重重搜索策略思想 ,使用 单单亲演化与群体演化相 结结合的方式来求解 TSP 问题。该文根据文 77中最小生成树 MST (minimum c ost spanni ng tree)的 应应用 ,由 MST建立 TSSP的基因库 ,保存有 希希望成为最优解的边 ,利利用基因库提高初始群 体体的质量进行单亲演化 , 然后利用改进后的交 叉叉算子和的多重搜索策 略略进行群体演化。 3 / 12 1 单亲演化过程 现有 的的大多数演化算法在整 个个演化过程中所涉及的 基基因 ,大多来源于个体 本本身 ,个体质量的高低 决决定了算法的全局性能 , 如果群体中初始个体 的的适应度都较差 ,肯定 要要影响算法的收敛速度 , 对于规模稍大的 TSP 尤其明显 8。该 文文为了克服上述弱点 ,首首先利用普里姆算法求 出出 TSP 中最小生成树 , 并将各个 MST中的 每每一条边都保存在一个 nn*(n-1)方阵里 面面 ,就构成了一个基因 库库 ,在生成初始群体的 时时候尽量使用基因库中 的的基因片段 ,来提高整 个个初始群体的适应度 ,从从而提高算法的效率。 TSP编码表示 设 n 个 个 城 市 编 号 为 1,2,n, 为 一 条 可 行 路 径径 ,Pk=Vk1Vk2 Vkn 为一条可行 路路径 ,它是 1,2, ,n 的一个随机排列 ,其其含意是第 k 条路径起 点点城市是 Vk1,最后 一一个城市是 Vkn,则 第第 k 条环路的总长度可 以以表示为 : 其中 ,d( Vki,Vkj)表 示示城市 Vki与城市 Vkkj之间的距离。在算 法法中环路 Pk 的总长 d(Pk)用来评价个体 的的好坏 9。适应度 函函数取路径长度 d(Pkk)的倒数 ,f(Pk) =1/ d(Pk)。 构建 TSP 基因库 对 n个编号为 1,2,n 的城市 ,根据它 们们的坐标计算各城市之 间间的欧氏距离 d(i,j ),i,j=1,2, ,n, 得到一个 n*n的方阵 D= d(i,j)。然后利 用用普里姆算法求得该 TSSP 的一棵4 / 12 MST,并 将将这棵 MST 中的每一 条条边 e(i,j)对应 地地存储在一个n*(n- 1)的方阵 M= e (i,j),即该 文文的基因库。由于一个 TTSP可能有多棵 MSTT,操作可以重复多次 , 这样生成的基因库中 的的基因就更多 ,增强了 初初始群体的全局性。具 体体算法如下 : Void MiniSpanT ree PRIM(M Graph G,Ve rtexTypeu) Struct VertexTyp e adjvex; VRType low cost; clo sedgeMAX VERTEX NUMM; k=Locat eVex(G,u); for(j=0;jj if(j!= k)closedge j=u,k j.adj; closedgek .lowcost=00; for(i=0; i k=min imum(close dge); prin tf(closedg ek.adjve x,k); cl osedgek. lowcost=0; for(j=0;j if( k j.adj closedge j=k, kj.adj; 单亲演 化化算法 5 / 12 单亲演化算法 是是利用遗传算法的优胜 劣劣汰的遗传特性 ,在单 个个染色体内以基因重组 的的方式 ,使子代在满足 TTSP 问题的限定条件 下下进行繁衍 ,然后保留 适适应度高的染色体种群 ,达到优化的目的。单 亲亲演化算法的基因重组 操操作包括基因换位、基 因因段错位和基因段倒转 三三种操作来实现。基因 换换位操作是将亲代的染 色色体基因进行对换后 ,形形成子代 ,其换位又分 为为单基因换位和基因段 换换位两种方式。基因段 错错位操作是随机确定基 因因段 ,也随机选定错位 位位置 ,整段错移。基因 段段倒转操作则是随机地 确确定倒转基因段的起止 位位置 ,倒转操作是对该 段段内基因按中垂线作镜 面面反射 ,若段内基因 数 为为奇数时 ,则中位基因 不不变。单亲演化时可以 是是单个操作用于单个父 代代 ,也可以是几种操作 同同时采用。为了编程方 便便 ,文中采用基因段倒 转转操作。 群体演化过 程程 在单亲演化算法求 得得的初始群体基础上 ,再再利用多重搜索策略并 行行地进行群体演化 ,这 样样在保证算法的快速收 敛敛的同时也注重了搜索 空空间的全局性。 .1 交叉算子 该文算子 采采用一种与顺序交叉 OX (order cro ssover)法类 似似的交叉方法 11, 即随机在串中选择一 个个交 配区域 ,例如以下 两两个父串及交配区域选 定定为 : P1=(12| 3456|789) P2=(98|765 4|321) 6 / 12 将 P2 的交配区域加到 P1 的的前面或后面 ,P1 的 交交配区域加到 P2的前 面面或后面 ,得 M1=( 7654|12345 6789) M2=( 3456|98765 4321) 在 M1 中中自交配区域后依次删 除除与交配区域相同的城 市市码 ,得到最终的两个 子子串 : S1=(765 412389) S2 =(34569872 1) 同时为了能更 好好地增强算子的全局搜 索索能力 ,对该算子作了 如如下的改进 。子代个体 的的新边来自 :随机生成 和和群体中其他个体 ,其 选选择比例由随机数 p和 阈阈值 P来决定。如果随 机机数 p 小于阈值 P,则 子子代个体的新边来自随 机机生成 ,否则就来自群 体体中的其他个体。 这 种种改进后的交叉算子在 父父串相同的情况下仍能 产产生一定程度的变异效 果果 ,这对维持群体的多 样样化特性有一定的作用 。实验结果也证实了这 种种改进算子对于种群的 全全局搜索能力有一定的 提提高 ,避免搜索陷入局 部部解。 .2 局部启 发发式算子 为了增强遗 传传算法的局部搜索性能 , 在算法中引入2-Oppt 局部搜索算子 122。该算子通过 比较 两两条边并交换路径以提 升升算法的局部搜索性能 , 示例见图 2。 比较 子子路径 ab+cd 和 acc+bd,如果 ab+c dac+bd 则交 换换 ,否则就不交换。考 虑虑到程序的运行效率 ,不不可能对每对边都7 / 12 做检 查查 ,所以选取染色体中 的的一定数量的边进行比 较较。 2-Opt搜索算 子子实际上进行的相当于 变变异操作 ,同时又不仅 仅仅是简单的变异 ,而是 提提高算法的局部搜索性 能能的变异操作。 .3 选择机制和收敛准则 为了限制种群的规模 13,该文采用了 联联赛选择法的淘汰规则 。联赛选择法就是以各 染染色体的适应度作为评 定定标准 ,从群体中任意 选选择一定数目的个体 ,称称为联赛规模 ,其中适 应应度最高的个体保存到 下下一代。这个过程反复 执执行 ,直到保存到下一 代代的个体数达到预先设 定定的数目为止。这样做 可可能导致种群过早收敛 , 因此在收敛准则上要 采采取苛刻的要求来保证 搜搜索的全局性。 遗传 算算法求 TSP 问题如果 不不设定终止条件 ,其演 化化过程将会无限制地进 行行下去。终止条件也称 收收敛准则 ,因为多数最 优优化问题事先并不了解 最最优的目标函数值 ,故 无无法判断寻优的精度。 该该文采用如下两条收敛 准准则 :在连续 K1 代不 再再出现更优的染色体 ;优优化解的染色体占种群 的的个数达 K2的比例以 上上。当两准则均满足时 , 则终止运算 ,输出优 化化结果和对应的目标函 数数值。由数值实验表明 , 添加第 2 条准则之后 , 全局最优解的出现频 率率将大为提高。 转贴 于于论文联盟 http:/ 基于多重搜索 策策略的群体演化算法 由于基因库的引 入入 ,可能降低初始种群 的的多样8 / 12 性 ,为避免算法 陷陷入局部最优解 ,因此 在在群体演化中采取多重 搜搜索策略。由 Cheng -Fa Tsai提 出出的多重搜索策略 6,就是把染色体集中 的的染色体分成保守型和 探探索型两种不同类型的 集集合 ,然后针对不同类 型型的染色体集合根据不 同同的交叉、变异概率分 别别进行交叉变异操作 ,对对保守型染色体集合就 采采用比较低的交叉变异 概概率 ,而对探索型染色 体体集合就采用比较高的 交交叉变异概率。这种策 略略对保守型染色体集合 的的操作最大限度地保留 了了父代 的优秀基因片段 , 另一方面对探索型染 色色体集合的操作又尽可 能能地提高了算法的全局 搜搜索能力。为了提高算 法法的收敛速度 ,初始染 色色体集合该文采用了前 面面单亲演化的结果中的 染染色体集合 ,交叉算子 则则利用的是前面介绍的 改改进后的算子 ,改进后 的的多重搜索策略见下。 实验结果与 分析 该 文文的 GB MGA 算法 由由 C#编程实现 ,所有 的的结果都是在微机上完 成成 ,并进行通用的 TSP 库实验 ,选用了具有 一一定代表性的 TSP 实 例例 ,并把该算法和其他 算算法做了一个对比。为 了了减少 计算 量 ,程 序序中的数据经过四舍五 入入整数化处理 ,与实数 解解有一定的偏差 ,下面 给给出图 Kroa100 的的示例。 为了证明该 文文提出的 GB MGA 算算法的有效性 ,将该文 算算法与典型的遗传算法 GGA、单亲遗传算法 PGGA以及文 5中杨 辉辉提出的 Ge GA(g ene pool g enetic alg orithm)算 法 和和文 129 / 12 中提出的 M MGA(modifi ed multiplle-searchin g genetic algorithm) 算法都进行了一个对 比比。 实验结果证明 ,该该文算法的求解质量要 优优于 GA、 PGA、MM GA 算法 ,而求解速 度度方面则优于 Ge GA 算法 ,特别是对于大 规规模城市的 TSP 问题 求求解效果尤其明显 ,具 有有快速收敛的特性。 Ge GA 算法对于中等 城城市规模的 TSP 实例 求求解 ,其运算时间就大 幅幅度增加 ,如果把该算 法法用于求解大规模和超 大大规模 TSP 问题 ,那 么么时间上的代价就让人 无无 法忍受。而该文的 GB MGA算法在单亲 遗遗传演化中就使用了基 因因库中的优质基因 ,使 得得单个个体的进化速度 大大大提高 ,从而为进一 步步的演化提供了条件 ,群群体演化过程的选择机 制制和收敛准则的恰当选 取取使得算法在注重 了求 解解质量的同时兼顾了算 法法的效率。 结束语 该该文在对 TSP 问题进 行行分析的基础上 ,通过 对对全局最优解和局部最 优优解中的边关系的分析 发发现 ,通过最小生成树 的的求解保存最有希望成 为为全局最优解的边 ,可 以以提高算法的效率 ,同 时时并不降低搜索的性能 。在实验中发现 ,通过 生生成基因库快速提高种 群群质量 ,虽然可以快速 收收敛 ,但是 TSP问题 的的求解质量并没有达到 一一个可以接受的程度 ,因因此在群体演化阶段中 又又加入了 2-Opt局 部部搜索算子和多重搜索 策策略 ,对不同类型的染 色色体以不同几率进行选 择择交叉操作。 用该算 法法测试 TSP库中的典 型型实例 ,结果显示 ,对 初初始种10 / 12 群运用单亲遗传 算算法 ,并引入基因库方 法法是可行的 ,有效地提 高高了算法的效率和收敛 速速度 ,在群体演化过程 中中引入多重搜索策略的 方方法 ,提高了算法的并 行行性和全局寻优性能 ,即即使在较少的寻优步数 也也能得到适应度不错的 局局部优化解。GB-MGGA 算法在提高 算法求 解解质量的同时兼顾了算 法法的效率 , 但是其中 还还有许多有待解决的问 题题 ,比如如何构建高质 量量的基因库 ,如何对现 有有基因库进行优化和扩 充充 ,以及算法中一些参 数数的选取问题等 ,这些 方方面 ,还需要进一步的 研研究。 参考 文献 1 Bck T B ,Hammel U, Schwefel H computat ion:Commen ts on the history an d current state J. lEEE Tran sactions O n Evolutio nary Compu tation,199 7,2(6):3117 王磊 , 潘进 , 焦 李 李成 . 免 疫 算 法 J. 电子 学报 ,200 0,28(7):74478 Dorigo M,Gambard ella L Co lony Syste m:A Cooper ativeLearn ing Approa ch to the Traveling Salesman P roblem J . IEEETran sactions o n Evolutio nary Compu tation,199 7,2(8):5366 Holland J H. Adap tation in Natural an d Artifici al Systems M.Ann A rbor:The U niversity of Michiga n,15 杨辉 ,康康立山 ,陈毓屏 .一种 基基于构建基因库求解 TSSP 问11 / 12 题的遗传算法 J .计算机学报 ,XX ,26(12):17 531758 Ts ai Cheng-F a, Tsai Chhun-WEi, Ya ng Tzer. A Modified Multiple-S earching M ethod to G enetic Alg orithms fo r Solving TravelingS alesman Pr oblem J. IEEE Trans actions on Systems,M an andCybe rnetics,20 02,3(10):6612 Baragl ia R,Hidal go J I, Pe rego R. A Hybrid Heu ristic for theTravel ing Salesm an Problem J. IEEEE Transacti ons on Evo lutionary Computatio n,2001,5(1 2):613622 Tsai Chenng-Fa, Tsai Chun-WEI. A New App roach for SolvingLar ge Trave