【硕士论文】基于遗传算法的旅行商问题仿真研究.pdf

西北工业大学 硕士学位论文 基于遗传算法的旅行商问题仿真研究 姓名：华灵群 申请学位级别：硕士 专业：系统工程 指导教师：周德云 20060401 摘要 旅行商是组合优化中最为著名的问题，它综合了一大类组合优化问题的典型 特征，并以不同的形式存在于超大规模集成芯片制造、印刷电路板设计、x 一射线结 晶学、机器人控制等高科技领域。 运用遗传算法和混合遗传算法对t s p 问题进行了研究。将免疫算法融入到遗 传算法当中，构成一种改进的遗传算法，与利用简单遗传算法的计算过程进行了 仿真和对比。应用结果表明，该算法简单、高效、稳定性好，能较好克服传统方 法和现有遗传算法的不足，性能得到了显著的提高，获得了满意的效果。 提出了一种混合分布式并行遗传算法，应用于求解旅行商( t s p ) i o 题。这种混 合算法主要由动态种群并行模型和2 0 p t 算法组成。程序由c 编制，运行环境是并 行虚拟机( p v m ) 。在这种混合并行遗传算法中，2 0 p t 算法取代变异操作，它逆转 t s p 个体的基因片段，改善t s p 个体的旅行距离。动态种群模型是一种由全局并 行模型和粗粒度并行模型结合而成的并行遗传算法模型，但它并没有迁移操作， 因为在进化过程中种群仅仅被当作是个体的集合。它的主要思想是通过动态分离 种群为子群从而减少最差个体的等待时间，使得子群的演化不被拖延。在处理速 度方面，它提供更高的效能，此外动态种群模型还具有完全的可扩展性。最后在 一组p c 机集群构成的网络环境下运用该混合算法求解t s p 问题，实验的数值结 果证明了该算法的有效性和可行性。 关键词：旅行商问题，遗传算法，免疫遗传算法，m p i 并行算法 a b s t r a c t t r a v e l i n gs a l e s m a np r o b l e m ( t s p ) i st h ew e l l k n o w nc o m b i n a t i o no p t i m i z i n g p r o b l e m ，i tc o l l i g a t e st h ec l a s s i c a lt y p i c a l i t yo fat y p eo fc o m b i n a t i o no p t i m i z i n g p r o b l e m ，a n d e x i s t s i nv l s ic h i p m a n u f a c t u r e ，p r i n t i n g c i r c u i t d e s i g n ，x r a y c r y s t a l l o g r a p h y , r o b o tc o n t r o la n dm a n yo t h e rh i g h t e c hf i e l d s a c c o r d i n g t on p - c o m p l e t e dt h e o r y , t s pb e l o n g st on p h ，i tc a n tb es o l v e db yr o u t i n es e a r c hm e t h o d s ， a n dd i f f e r e n tt y p e so fs o l u t i o n sm u s tb ee m p l o y e d g e n e t i ca l g o r i t h m ( g a ) i ss h o w i n g i t sp o t e n t i a li ns o l v i n gl a r g ec o m b i n a t i o no p t i m i z i n gp r o b l e mm o r ea n dm o r e c o n s i d e r i n ge x i s t e dp r o b l e m st s p , d i s p a t c hp r o b l e m so fs t a t i cs t a t ef o rp t va r e s t u d i e da n dd i s c u s s e dw i t hg e n e t i ca l g o r i t h m s ( g a ) a n dh y b r i dg a m a k i n gf u l lu s eo f i n t e l l i g e n tc h a r a c t e r i s t i c so fg a s t a t i cd i s p a t c ho fp t v i si m p r o v e de f f e c t i v e l y b a s e d o ng aa n dt h es t u d yo ft h ei m m u n ep r i n c i p l eo fc r e a t u r e ，i m m u n ea l g o r i t h mi sm i s s e d i n t og a ，a n dt h e yb e c o m ea ni m p r o v e dg a t h i sa d v a n c e da l g o r i t h m - - i m m u n eg a ( i g a ) i sa p p l i e dt os o l v es o m eo p t i m i z a t i o np r o b l e m s t h ec o m p u t i n gp r o g r a m s a p p l y i n gg aa n di g a a r es i m u l a t e da n dc o m p a r e d t h er e s u l t ss h o wt h a ti g ai ss i m p l e ， e f f i c i e n ta n dr o b u s t a h y b r i da l g o r i t h mu s i n g di s t r i b u t e dp g a b a s e do nt h ed d sm o d e la n dh e u r i s t i c m e t h o d ( 2 0 p t ) f o rr a p i ds o l u t i o no ft r a v e l l i n gs a l e s p e r s o np r o b l e m ( t s p ) i sp r e s e n t e d a cp r o g r a mb a s e do nt h i sa l g o r i t h mi np a r a l l e lv i r t u a lm a c h i n e ( p v m ) e n v i r o n m e n ti s d e v e l o p e d i nt h i sh y b r i dm e t h o d ，t h em u t a t i o ni sp r o v i d e db yt h e2 0 p tm e t h o d w h i c hi s o n eo f t h em o s tw e l l - k n o w nl o c a ls e a r c h e sa l g o r i t h m sa m o n gt s p s o l v i n ga l g o r i t h m s i t i m p r o v e st h et s pt o u ra n dr e v e r s e so r d e ro ft h es u b t o u r t h e d d sm o d e li s c o m b i n a t i o no fg l o b a lp a r a l l e l i s mw i mc o a r s eg r a i n e dp g a t h e r ei sh o we v e rn o m i g r a t i o no p e r a t o ra ss u c h ，b e c a u s et h ew h o l ep o p u l a t i o ni st r e a t e dd u r i n gt h ee v o l u t i o n a sas i n g l ec o l l e c t i o no fi n d i v i d u a l s t h em a i ni d e ao ft h em o d e li st oc u td o w nw a i t i n g t i m ef o rt h el a s ti n d i v i d u a l s ，b yd y n a m i cs p l i t t i n gt h ep o p u l a t i o ni n t od e m e s ，w h i c hc a n t h e nb ep r o c e s s e dw i t h o u td e l a y i tg i v e sm o r ee f f i c i e n c yi nt e r m so fp r o c e s s i n g s p e e d t h ea l g o r i t h mi sf u l l ys c a l a b l e t h ep r o p o s e dm e t h o di su s e dt os o l v et s p o np c c l u s t e r i n gc o m p u t i n gs y s t e m ，t h ee x p e r i m e n tr e s u l t sd e m o n s t r a t e st h a tt h en e w m e t h o d i se 髓c t i v ea n dv a l i d k e yw o r d s ：t r a v e l l i n gs a l e s p e r s o np r o b l e m ( t s p ) ，g e n e t i ca l g o r i t h m ( g a ) ，i m m u n e g e n e t i ca l g o r i t h m s ，m p ip a r a l l e la l g o r i t h m i l 西北工业大学硕士论义 第一章绪论 1 1 旅行商问题 第一章绪论 旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，简称t s p ) 是威廉哈密尔顿爵士和英国 数学家克克曼( t p k i r k m a n ) 于1 9 世纪初提出的一个数学问题。这是一个典型的n p 完 全性问题。其简单描述是：一名商人欲到n 个城市推销商品，每两个城市i 和，的之间的 距离为d o v i ，j ，如何选择一条路径使得商人每个城市走一遍后回到起点，且所走的路径 最短。相应的数学描述为： r a i n d i j x “ ( 1 1 ) i j 生 s t x “= 1 i = 1 , 2 ，h( 1 2 ) i = l 生 艺x “= 1 j = 1 , 2 ，( 1 3 ) j = l x “i s - i2 - l 时，根据最优性 原理，可将t s p 的动态规划方程写成c ( s ，k ) - n i n j 。s k c ( s - ( k j j ) + 4 k ) 按方程规划可迭代 求解。由于动态规划算法的时间复杂度为d 2 * 2 ”) ，空间复杂度为o ( n * 2 ”) ，故一般除了 很小规模的问题外，几乎不予采用。 3 分支定界算法 分支定界算法是一种应用范围很广的搜索算法，它通过有效的约束界限来控制搜索 进程使之能向着空间状态树上有最优解的分枝推进，以便尽快找出一个最优解。该方法 的关键在于约束界限的选取，不同的约束界限，可形成不同的分支定界法。但是分支定 界算法对于解大规模问题不是很有效。 二近似算法 由于精确式算法所能求解的问题规模非常有限，实际中使用的往往都是多项式阶数 的近似算法或启发式算法，算法的好坏用来c c 。占衡量，c 为近似算法所得到的总行 程，c 为最优总行程，s 为最坏情况下，近似解与最优解的总行程之比所不超过的上界 值。这类算法有： 1 插入算法 插入型算法可按插入规则的不同而分为若干类，其一般思想为： 步骤1 ：通过某种插入方式选择插入边( 巧) 和插入点k ，将k 插入i 和j 之间，形 成 o ，在1 + s 之内几乎处处解决t s p 。假定g 位于单位正 方形内，函数“n j 映射到正有理数，满足：f 斗1 0 9 ：l o g ：；对所有”，l f 是完全平 方，则有： 步骤1 ：以b g ) n 】。2 为尺寸构成网络，将单位正方形分成f o ) ，将g 也分成至多 n f ( h ) 个子图； 步骤2 ：用动态规划方法求解每个子图的最优回路； 步骤3 ：将h 肛b ) 个子图各自收缩为一点，其间距离定义为原子图的最优子回路间最 短距离，并对新构成的图求最小生成树t ； 步骤4 ：将t u o ，若某一代群体中最大的适应度值与已知的最大适应度值之 差小于e ，则终止运算。该代群体中具有最大适应度的个体即为所求最优解的近似 解； 3 ) 有些工程优化问题，最优解的适应度值不是己知的。这种情况下可以依据 人的经验或对问题的期望提出一个理想的适应度值，一旦某一代中最优个体的适 应度超过了这个理想值，则迭代运算停止； 4 ) 规定迭代次数，当迭代达到这个次数时即停止，在整个遗传操作中得到的 最好结果作为最优解。 2 3 5 遗传算法的控制参数性能分析 在标准的遗传算法中，算法的控制参数主要有群体规模n ，复制个体数目m ， 交叉概率鼠、变异概s p 。及迭代次数n ，参数的选择将影响到遗传算法的最终的 性能和效率。 一、群体规模n 的确定 群体是遗传算法的操作对象。如果群体的规模过小，群体所反映的信息不充 分。群体中个体的多样性有助于寻找全局的最优解，否则容易出现过早的未成熟 收敛，即收敛局部最优解。但是，群体规模的过大，也会导致每代群体的计算量 增大，可能使得收敛速度极其缓慢。因此，在实际的应用问题中，也可以将i “ 1 视为 一个可变的量。当群体中的多样性减少到某个阀值时，可是适当的增大规模r l 的数 目，解决的办法是减少群体中的死亡率。 二、复制个体数目m 的确定 通常每代群体中的个体复制概率都为0 1 0 2 ，即m 为0 1 n o 2 n 。复制可以 使品质优良的个体在群体中占有较高的比例，但是复制概率不能过高，否则也_ 会 导致群体多样性的破坏。 三、交叉概率p 的确定 在遗传算法中，交叉是产生新个体的主要手段，交叉概率决定了每代群体巾 西北工业大学硕士论文 第二章遗传算法 实施交换的个体数目。交叉概率大，则实施交换的个体数目多，个体更新就快。 但是，随之带来优良个体被破坏得快的弊端。如果交叉概率过低，则群体中的新 个体增加率也要减小，使得搜索渠道变窄，既影响了收敛速度，也失去了遗传算 法的优越性。通常，交叉概率取值为0 5 o 8 。 四、变异概率n 的确定 变异也是产生新个体的一种算子，比起交叉算子而言，变异算子的更重要的 作用是恢复群体失去的多样性，以避免陷入局部最优。较小的变异概率还会有利 于在当前解的附近寻找更好的解。如果变异概率过高，字符串中变异的字符太多， 可行解在搜索空间跳跃激烈，这会使搜索的随机性增大，也会失去遗传算法的优 越性。故变异概率常常取值很小，一般为0 0 0 1 0 o l 。 在标准的遗传算法中，复制概率、交叉概率和变异概率是事先确定的，并且 在遗传操作的整个过程中是不变的。考虑到三个主要算子对群体的多样性的不同 作用，为了防止遗传算法出现过早收敛，可以在整个遗传操作过程中将三个算子 的概率设定为与群体多样性及适应度有关的变量，如果群体多样性过早减小，则 可以通过减小复制概率或增大变异概率来扼制，并成这样的遗传算法为自适应遗 传算法。 2 4 基本遗传算法的改进 遗传算法( g e n e t i ca l g o r i t h m ) 是2 0 世纪7 0 年代j o h nh o l l a n d 教授为研究自然 与人工系统的自适应行为而提出的一种算法，后经其学生k e n n e t hd ej o g 年u d a v i d e g o l d b e r g 等人的改进推广得以广泛应用于各类优化问题：通过模拟生物界的自 适应过程，遗传算法为求解各类复杂问题提供了一种通用而易于实现的解决方案， 并以其简单、鲁棒性强以及不受搜索空间限制性条件约束等特点而日益受到人们 的关注。目前它在许多领域获得了成功应用。 遗传算法是具有“生成+ 检测”迭代过程的搜索算法，它以每个个体为对象对 整个群体进行操作，选择、交叉和变异是它的主要操作算子。与适应度值成比例 的选择操作既能使适应度函数值高的个体具有更多的生存机会，但也因此有可能 导致算法过早达到不成熟收敛；交叉和变异操作都可产生新的优良结构的个体， 西北工业大学硕士论文 第二章遗传算法 同时也存在把具有优良结构的个体破坏的能力。在基本遗传算法中，利用性和搜 索性是始终存在的影响遗传算法收敛速度和全局收敛性的一对矛盾。利用性主要 通过选择算子实现，搜索性主要通过交叉和突变算子实现。通过改变选择压力， 可以调整适应度高的个体被选中的机会。进化初期选择压力比较大，适应度高的 个体纷纷被选中，这些个体很快控制了进化过程，造成群体过早收敛。进化后期 群体中个体差异较小，选择压力减小，使收敛速度大大降低。交叉和变异是对解 空间新区域进行搜索的有效方法，交叉率高会使群体原有的高质量个体的淘汰速 度高于交叉产生高质量个体的速度，难以达到进化效果：交叉率低会使搜索过程停 滞不前。变异率低则算法搜索最优解空间的效率低，变异率高则趋于随机搜索。 因此，交叉率和变异率的选择是很微妙的。如果进化过程中这两个控制参数保持 个定值，则很容易导致过早收敛。 考虑到基本遗传算法存在优化结果具有随机性、易陷入局部最优点、收敛速 度慢甚至不收敛的缺点，应该对基本遗传算法进行改进，寻找一种更高级的遗传 算法。目前，对遗传算法进行改进的方法也有不少，经过大量的收集和比较，本 文试图将这些遗传算法的改进方法进行融合并融入自己的方法，形成一种薪得改 进遗传算法。最后的仿真结果表明了此种改进遗传算法基本克服了基本遗传算法 的优化结果随机性强及容易不收敛的缺点，即能稳定的收敛于全局最优点或某一 个较靠近全局最近点的局部最优点，优化结果虽未必是全局最优点但能保证优化 结果的唯一性且已明显强于基本的优化效果，具备一定的可行性和有效性，但收 敛速度仍然不够理想。下面介绍了本文对基本遗传算法进行改进的三个方面。 2 4 1 检测选优去劣策略 在遗传算法的运行过程中，通过对个体进行交叉、变异等遗传操作而不断地 产生出新的个体。虽然随着群体的进化过程会产生出越来越多的优良个体，但由 于选择、交叉、变异等遗传操作的随机性，它们也有可能破坏掉当前群体中适应 度最好的个体。而这却不是我们所希望发生的，因为它会降低群体的平均适应度 并且对遗传算法的运行效率、收敛性都有不利的影响。所以，我们希望适应度最 好的个体要尽可能地保留到下一代群体中。并且关于选择算子的己有研究，几乎 所以的都关注于从“选优”意义上模拟“适者生存”原理，而无人从“去劣”的 7 西北工业大学硕士论文 第二章遗传算法 意义上考虑选择算子的设计，虽然“选优”从当前种群选铎最优个体的同时也达 到了“去劣”的目的，但这种选择不能避免被抛弃的“劣质”个体被重复选择， 从而导致了现有遗传算法的低效率，所以同时考虑“去劣”选择策略。为达到这 两个目的，本文使用检测选优去劣来进行优胜劣汰操作，即当前群体中适应度最 高的个体不参与交叉运算和变异运算，将其完整的复制到下一代群体中，并用它 来替换掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体。 检测选优去劣策略的具体操作过程是： ( 1 ) 交叉操作完成之后，对新产生的个体进行适应度计算，并且和原群体 中的最优和最差的个体进行比较。 ( 2 ) 如果适应度高于最优个体，保存并替换当前群体中的适应度最优值；如 果适应度低于最差个体的适应度值，那么用原来最优的个体替换新产生的这个个 体。 ( 3 ) 变异操作完成之后进行同样的操作。 检测选优去劣策略的实施可保证迄今为止所得到的最优个体不会被交叉、变 异等遗传运算所破坏，它是遗传算法收敛性的一个重要保证条件。 定理1 使用保留最佳个体策略的遗传算法能收敛于最优解的概率为1 。 证明考察这样所组成的个体集合p + ( f ) = ( 爿( f ) ，p o ) ) ，其中a ( t ) 是当前群体中适 应度最高的个体。这一个体集合的状态转移规则是： ( 1 ) 依据定理1 中的状态转移矩阵r 由p ( f ) 产生p ( t + 1 ) 。 ( 2 ) a o + 1 ) 是从上一代群体中和本代群体中挑出的一个具有最大适应度的个 体，即： a ( t + 1 ) = m a x a ( t ) ，4 ( 2 3 ) 式中：4 是群体p ( t + 1 ) 中适应度最高的个体。 这样所构造出的随机过程 ( f ) ，t 0 ) 仍然是一个齐次m a r k o v 链，即有： p + ( ，) = p + ( o ) ( r + ) ( 2 4 ) 假设个体集合状态中包括有最优解的状态为i o ，则该随机过程的状态转移概 率为： 哆 o ( v f ，w i o ) ( 2 5 ) 苫= o ( v ix , v j i o ) ( 2 6 ) 两北工业大学硕士论文 第二章遗传算法 即从任意状态向含有最优解的状态转移的概率大于0 ，而从含有最优解的状态 向不含有最优解的状态转移的概率等于0 。 此时，对于v i ，v j 诬i o ，下式都成立： ( r + ) ：_ 0 o 一)( 2 7 ) f ) = 0( j 芒i o ) ( 2 8 ) 亦即个体集合收敛于不含有最优解的状态的概率为0 。换句话说，算法总能够 以概率1 找到最优解。 定理1 说明了这种使用保留最佳个体策略的遗传算法总能够以概率1 搜索到最 优解。这个结论除了理论上具有重要意义之外，在实际应用中也为最优解的搜索 过程提供了一种保证。 2 4 2 变交叉概率 在基本的遗传算法中交叉概率e 是固定不变的，这就给的选取带来困难。 本文采用了变交叉概率的方法：在算法的初期使用大的交叉概率来加剧种群的变 化，有利于加快寻找优良种群所处的区域，随遗传代数的增加只的值递减，从而 可以解决由于p 取值过大使得适应度高的代码串很快被破坏掉及取值过小使搜索 速度缓慢的矛盾。在本文中交叉概率取为p = o 3 5 1 n + 0 5 ，其中n 为进化代数。 在交叉算子中，确定交叉产生的新个体的适应度函数b s j ，若它优于当前的最 优个体的适应度函数b e s t s ，则保留并更新b e s t s ；若它比当前最劣个体的适应度 函数值还差，那么认为未产生优良个体，用当前的最优个体替换之。 2 4 3 概率不同的变异算子 从遗传运算过程中产生新个体的能力方面来说，交叉运算是产生新个体的主 要方法，它决定了遗传算法的全局搜索能力，而变异运算只是产生新个体的辅助 方法，但它也是必不可少的一个运算步骤，因为它决定了遗传算法的局部搜索能 力。交叉算子与变异算子的相互配合，共同完成对搜索空问的全局搜索和局部搜 索，从而使得遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。 在遗传算法中使用变异算子主要有以下两个目的： 西北工业大学硕士论文 第二章遗传算法 改善遗传算法的局部搜索能力。遗传算法使用交叉算子己经从全局的角度 出发找到了一些较好的个体编码结构，它们已接近或有助于接近问题的最优解。 但仅使用交叉算子无法对搜索空间的细节进行局部搜索。这里若再使用变异算子 来调整个体编码串中的部分基因值，就可以从局部的角度出发使个体更加逼迫最 优解，从而提高了遗传算法的局部搜索能力。 维持群体的多样性，防止出现早熟现象。变异算子用新的基因值替换原有 基因值，从而可以改变个体编码串的结构，维持群体的多样性，这样就有利于防 止出现早熟现象。 若变异概率取值较大的话，虽然能够产生出较多的新个体，但也有可能破 坏掉很多较好的模式，使得遗传算法的性能近似于随机搜索算法的性能：若变异概 率只取值太小的话，则变异操作产生新个体的能力和抑制早熟现象的能力就会较 差。一般建议的取值范围是o o o o l o 1 。 本文采用的是根据个体适应度的不同应用不同的变异概率，为了保留适应度 比较高的个体，同时改变适应度比较低的个体，我们采用随着个体的适应度的增 加而变异概率减小的变异算子。 具体的变异概率是根据下式来改变的： 只= o 1 叫1 ：1 ：s i z p 】 o e ( 2 9 ) 式中：s i z e 为群体规模，变异概率的最大值为0 1 。通过针对不同适应度个体的 选择不同的变异概率可以加快算法的寻优速度，同时避免寻优过程的过早收敛。 通过仿真实验，取得了很好的寻优效果。 总之，综合分析以上三种方法之后，本文将它们融入到基本遗传算法中，形 成了一种新的改进遗传算法，应用这种改进遗传算法，得到了很好的仿真效果。 2 0 西北工业大学硕士论文 第三章求解旅行商问题的遗传算法 第三章求解旅行商问题的遗传算法及仿真 3 1 求解旅行商问题的基本实现方法 旅行商问题常用的编码表达方式主要有近邻( a d j a c e n c y ) 表示、次序( o r d i n a l ) 表示、路径( p a t h ) 表示( 又叫序表达) 、矩阵表示和边( e d g e ) 表示等。 3 1 1 编码 采用十进制编码，每个染色体由按一定顺序排列的n 个城市的序号组成，表示 一条可能的旅行路径，其中每个基因表示一个城市。染色体的长度为n ，解空间为 n ! 。适应度为一条旅行路径对应的距离，路径越短的染色体适应度越高。例如：对 于一个1 0 个城市的t s p ：3 - - 2 - - 5 - - 4 - - 7 一卜一6 9 8 可简单表示为 32 5 47 15 98 ，表示从城市3 出发依次经过城市2 ，5 ，4 ，7 ，1 ，6 ，9 ，8 然后返回城市3 的 一条路径。并且这种表达方式满足t s p 问题的约束条件。保证了每个城市经过且只 经过一次，并且保证任何一个城市子集中不形成回路。这种编码方式在计算个体 的适应值无需解码，变异算子特别好设计。 3 1 2 生成初始群体 一般都是随机生成规模为n 的初始群体。 3 1 3 适应度函数 对于求解最小值问题 i f 厂( x ) c 。、 其中f ( z ) 是目标函数值，本文中厂( x ) = f ；= ( f ( c ，c 。) + d ( c ，) 。 f = l 2 西北工业大学硕士论文 第三章求解旅行商问题的遗传算法 3 2 遗传算子 3 。2 。1 选择算子 适应度比例法实现简单，缺点是选择过程中最好的染色体可能在下一代产 生不了子孙，可能发生随机错误。因此我们可以采用择优选择法，即对于群 体中最优秀( 适应度最高) 的染色体不进行交换和变异运算，而是直接把它 们复制到下一代。以免交换和变异运算破坏种群中的优秀解答。这种方法可 加快局部搜索速度，但又可能因群体中优秀染色体的急剧增加而导致搜索陷 入局部最优解。同时，我们也可以采用确定性选择法，使得选择不依靠随机 的好坏，先计算群体中每个串的生存概率只= 工乃，l 厂g ；。，) ，则选定最 优个体为圪：，否则最优个体为矗。，。 4 ) 重复执行步骤2 ) 和3 ) ，直至达到终止条件，这里t 取为1 0 0 ，选择最后代 的最优个体作为寻优的结果。 3 6 2 计算实例与结果分析 为了确定交叉概率、变异概率、进化代数等遗传算法参数，进行了许多实验 最终确定了效果较好的参数为：变异概率取0 0 0 0 5 ，交叉概率取为0 6 。另外 群体规模取2 0 0 ，遗传代数取为6 0 0 ，这样可以兼顾运算量和运算效果。 图3 - - 2 和图3 - - 3 是7 5 城市的t s p 问题免疫优遗传仿真示意图。 图3 - 2 免疫抗体 图3 - 3 最优化路径 图3 4 和图3 5 是4 4 2 城市的t s p i a 题免疫优遗传仿真示意图。 图3 6 和图3 7 分别画出了遗传算法和免疫遗传算法中各代个体目标平均值 和各代最优个体目标平均值随进化代数的变化规律，从图中明显可以看出，i g a 的 收敛速度要优于g a ，收敛更快。将i g a 应用于t s p 问题能够得到较好的结果，可 以迅速得到最优解。i g a 是对g a 的改进，从性能上也有了更大的进步。 西北工业大学硕士论文第三章求解旅行商问题的遗传算法 图3 4 免疫抗体 图3 5 最优化路径 图3 6 通用遗传算法计算曲线 图3 7 免疫遗传算法计算曲线 3 7 本章小结 本章在遗传算法的基础上采用了一种较新的混合遗传算法一免疫遗传算法对 t s p 问题进行了研究，并对二者的应用结果进行了仿真和比较，结果表明i g a 有 效的克服了简单g a 的不足之处，并提高了寻优过程当中目标函数的收敛速度。 西北工业大学硕士论文 第四章旅行商的并行遗传算法求解 第四章旅行商问题的并行遗传算法求解 在本章中，提出了一种求解t s p 问题的分布式并行演化算法，和其他的求解 t s p 问题的演化算法不同的是，算法只使用了变异算子。算法采用了主从 ( m a s t e r - s l a v e ) 分布式并行模式，主进程只完成选择淘汰、任务的分发和很少量 的遗传操作，大量的遗传操作以及个体的适应值的计算是由从进程完成的，算法 具有很高的并行度。在p v m 并行计算环境下，用实例k r o b l 5 0 和c h n l 4 4 对算 法进行了测试，所得的结果达到或好于已知最优解，所用的时间也较短。 4 1 并行平台 从2 0 世纪9 0 年代初期开始，从昂贵的、面向特定应用的并行超级计算机f 向 量机和大规模并行处理机) 向网络计算机( 计算机可以是p c 或者工作站或者s m p 机器) 转变的趋势越来越明显。这些技术使得计算机网络或者集群变成一个非常有 吸引力的工具，可以用在性价比要求高的并行处理中，同时还为实现低价的商用 超级计算机指明了方向。从p c 或工作站集群到s m p 集群的可扩展计算机集群很 快成为高性能计算的标准平台。这种系统最主要的优点是，它们建立在容易购买 且价格低廉的商品化硬件( 比如奔腾p c 机) 、快速局域网和标准软件组件( 比如 u n i x ，m p i 和p v m 并行编程环境) 之上。这些系统是可扩展的，也就是说，它们 可以根据预算和计算能力的要求做出调整，并且能够有效地运行高要求的并行和 串行程序。 有效地开发工作站集群计算能力的想法已经在高性能计算领域内得到高度重 视，当前的趋势也更倾向于这种商品化的超级计算机。出现这种现象的原因是：绝 大部分的科学团体希望减小经济上的风险，同时希望并行计算能建立在成熟的、 商品化的技术之上。集群计算在高性能并行计算领域中已经成为主流的解决方案。 集群是一种并行或者分布式处理系统，它由一组互连的单机组成，这些单机 协调工作提供一个单一的、完整的计算资源。一个计算机节点可以是一个具有存 储器、i o 设备和操作系统的单机或多处理器系统( p c 机、工作站或者s m p 机器) 。 一个集群一般指的是两个或者两个以上互相连接起来的计算( 节点) 。这些节点可以 3 2 阿北t 业大学硕十论文 第四章旅彳亍商的并行遗传算法求解 放在一个机柜中，也可以分弗在不同的地方并通过周域网连接。下面是集群的一 些显著特征： 多种高性能计算机( p c 机、工作站或者s m p 机器) ； 先进的操作系统； 高性能网络交换机； 网络接口卡( n i c ) ； 快速通信协议和服务； 集群中间件： 并行编程环境和工具； 应用程序。 网络接口硬件充当一个通信处理器并负责在集群各节点之间通过网络或者交 换机收发数据包。通信软件在集群各节点以及集群和外界之间提供一个陕捷、可 靠的数据通信手段。集群节点既可以作为一个完整计算机资源中的组成部分，也 可以作为单独的计算机使用。集群中间件负责提供单一系统镜像的虚拟环境，完 成互连功能，提供一个可用的独立计算机集合。编程环境能够给应用程序开发提 供可移植的、高效的并且容易使用的工具。包括消息传递库、调试器和描述文件。 4 2 并行程序 并行应用程序的开发是一个很复杂的任务。首先，它在很大程度上依赖于可 用软件l ：具和环境；其沃，并行软件开发人员必须面对串行程序开发中不会遇到的 问题，这些问题涉及不确定性、通信、同步、数据划分和分配、负载甲衡、容错、 异构、共享和分布存储、死锁以及竞争条件。这些对软件开发人员提出了新的重 大挑战。 4 21 开发并行程序的策略 并行程序的一个主要问题是决定到底是移植现确串行程序还是从头开发新的 并行程序。现在有三种方法用来开发并行程序。 第一种方法基十自动并行化，第二种建立在并行库的使用上，而第三种方法 类似于从头开发应用程序。 类似于从头开发应用程序。 西北工业人学硕士论文 第四章旅行商的并行遗传算法求解 自动并行化的目的是解除程序员的并行化任务。编译器接收带有并行化标记 的代码并且在不需要程序员干涉的条件下产生高效的并行目标代码。但要实现这 种方法非常困难。另外一个移植并行代码的可能途径是使用并行库，这种方法比 前种要成功得多，其基本思想是将一些并行应用程序经常使用的代码封装到一 个用高效代码实现的并行库中，这样一个库能够被许多代码重用。第三种策略， 也就是从头编写应用程序的策略，使得程序员有更多的自由来选择语言和编程工 具。 4 2 2 并行编程模型 目前两种最重要的并行模型是数据并行和消息传递。数据并行编程模型的编 程级别比较高，编程相对简单，但它仅适用于数据并行问题；消息传递编程模型的 编程级别相对较低，但消息传递编程模型可以有更广泛的应用范围。 数据并行即将相同的操作同时作用于不同的数据。这种模型是一种较高层次 上的模型，它提供给编程者一个全局的地址空间。一般这种形式的语言本身就提 供并行执行的语义，因此对于编程者来说，只需要简单地指明执行什么样的并行 操作和并行操作的对象，就实现了数据并行的编程。比如对于数组运算，要使数 组b 和c 的对应元素相加后送给a ，则通过语句a = b + c 就能够实现上述功能， 即并行机对b ，c 的对应元素并行相加，并将结果并行赋给a 。因此数据并行的表 达是相对简单和简洁的，它不需要编程者关心并行机是如何对该操作进行并行执 行的。 数据并行编程模型虽然可以解决一大类科学与工程计算问题，但是对于非数 据并行类的问题，如果通过数据著行的方式来解决，般难以取得较高的效率。 数据并行不容易表达甚至无法表达其它形式的并行特征。数据并行发展到现在， 高效的编译实现成为它面临的一个主要问题。有了高效的编译器，数据并行程序 就可以在共享内存和分布式内存的并行机上都取得高效率，这样可以提高并行程 序设计的效率和并行程序的可移植性，进一步推广并行程序设计技术。 消息传递即各个并行执行的部分之间通过消息传递来交换信息、协调步伐、 控制执行。消息传递一般是面向分布式内存的，但是它也可适用于共享内存的并 行机。消息传递为编程者提供了更灵活的控制手段和表达并行的方法，一些数据 西北一l 业大学硕十论文 第四章旅行商的并行遗传算法求解 并行方法很难表达的并行算法，都可以用消息传递模型来实现。 灵活性和控制手段的多样化，是消息传递并行程序能提供高的执行效率的重 要原因。 4 2 3 并行算法的分类 算法是解题方法的描述，以确定解决某一特征类型问题的运算顺序与规则。 根据所解决问题的类型不同或者是计算模型不同，相应的计算方法应有所不同。 并行算法主要有以下几类： ( 1 ) 数值并行算法，主要为数值计算方法而设计的并行算法。 ( 2 ) 非数值并行算法，如神经网络算法、遗传算法以及为符号计算而设计的并 行算法。 ( 3 ) 同步并行算法，是指某些进程必须等待其它进程的一种并行算法。要求所 有进程必须在一个给定的时刻同步。s i m d 以及共享型的m m d 并行机上通常运 行同步并行算法。分布式存储m m 并行机当计算需要等待通信结果的算法实际 上也是一种同步算法。 ( 4 ) 异步并行算法，是指进程执行相对独立，不要互相等待的一类并行算法。 通常是针对分布式存储m i m d 并行机设计的。异步并行算法的主要特征 是在计算的整个过程中都不需要等待，而是根据当前的最新信息决定进程的 继续或终止。 ( 5 ) 分布式算法，是指由包括网络在内的通信链路连接的多结点机或计算机 集群协同完成某个计算任务的算法。 根据并行计算任务的大小，并行算法还可以分为粗粒度并行算法、细粒度并 行算法以及介于二者之间的中粒度并行算法。一般而言，并行的粒度越小，越有 可能开发更多的并行性，提高并行度，这是有利的方面：不利的方a 是并行的粒度 越小，通信次数和通信量就相对增多，这样就增加了额外的开销。因此，合适的 并行粒度需要根据计算量、通信量、计算速度、通信速度等因素进行综合平衡， 这样才能够取得高效率。 3 5 苎型星兰些叁堂堡主堡壅 笙凹主堕堑塑塑茎i ! 垄堡塞鎏垄塑 4 3 消息传递并行编程 并行程序日益增强的简易性和灵活性增加了它对于科学家或工程师的吸引 力。在众多的消息传递库中，应用较广泛的有消息传递接口( m p i ) 标准和并行虚拟 机( p v m ) 环境。p v m 是o a kr i d g e 国家实验室和t e n n e s s e e 大学在1 9 8 9 年开发出 来的；m p i 诞生于数年之后，由几所大学和国家实验室出于创建消息传递库标准的 目的共同开发成功的。 4 3 1 消息传递方式 在消息传递系统中，通常用术语通信来表示所有交互操作，即通信、同步和 聚集。通信通常在同组的进程间发生。但是进程通信也得到某些系统的支持。在 当今的消息传递系统中所使用的通信方式有三种。下面我们从用户观点，使用发 送和接受对，以三种不同的方法来描述这些通信方式。我们使用以下的代码例子 来说明这些概念。 例2 1 消息传递中的发送和接受缓冲区 进程a 向进程b 发送包含在变量m 中的一个消息，b 将此消息接收到它的变 量5 中。 进程a进程b m = 1 0 ；s = 一1 0 0 ； l l ：s e n d m t o b ；l l ：r e c e i v es f r o m a ； l2：m=20；l2：x=s+i； g o t 0 l i ； 变量m 常称为发送消息缓冲区，而s 称为接收消息缓冲区。 1 同步消息传递 当进程a 执行同步发送m 到b 时，它必须等待直至进程b 执行了一个相应 的同步从a 接收s 两个进程将不会从发送或接收返回，直到消息m 己被发送和 接收。这意味着上面代码中的变量x 应赋值为1 1 。当s e n d 和r e c e i v e 返回后，在 随后的l 2 语句中，m 可立即为a 所重写，而b 可立即读s 。 2 锁定发送接收 西北j r 业大学硕士论文 第四章旅行商的并行遗传算法求解 当进程到达锁定发送语句嗣，就执行锁定发送。与同步发送不同，它的发送 不需要等待相应的接收。在消息被发出前，锁定发送不会返回。应注意当发送返 回时，相应的接收不一定要完成，甚至不一定要开始。我们要知道的只是消息己 离开m ，它可能还未被接收。它可能被暂时地缓冲在网络中某处的发送结点中， 或者已到达了接收结点的缓冲区。当进程到达锁定接收语句时，不用等待相应的 发送，就可执行锁定接收。然而在消息未被接收前，它不能返回。采用锁定发j 羞 接收时，上述代码中的x 应赋值为1 1 。 3 非锁定发送接收 当进程到达时，不必等待相应接收，就可执行非锁定发送。非锁定发送在告 知系统消息m 己发出后，便可立即返回。此时消息数据并不一定已离开m ，因此 重写m 将是不安全的。当进程到达时，不必等待相应发送，就可执行作锁定接收。 在告知系统准备要接收一个消息后，它就可立即返回。此时该消息可能己到达， 可能仍在发送之中，或者甚至可能还未发生。在非锁定方式中，依赖两个进程的 速度，在上述代码中的x 可能被赋值1 1 ，2 1 或一9 9 的值。 4 三种方式的比较 同步方式有以下两个主要优点：首先，同步语义学不但表述清晰且易于使用， 当进程从发送子程序返回时，它确切知道消息己被发送和接收：其次，用户和系统 不用设置分离的数据缓冲区，在接收进程的地址空间中，消息m 可直接拷贝到s 中。同步方式的缺点是，发送方必须等待接收方，这就会导致某些周期的浪费。 在实际的并行系统中，对同步方式有不同的定义。例如，在某些系统中，当相应 的接收己开始但还未完成时，同步发送就可返回。此外还可能使用不同术语来说 明同步方式术语异步用来说明非同步方式，如锁定或非锁定方式。 在几乎所有的现有消息传递系统中，都使用锁定和非锁定方式。但是对于异 步发送，必须具有足够的临时缓冲区空间，这是因为相应的接收可能还未开始， 因此无法知道存放所收到的消息需要多大的存储器空间。非锁定方式可使等待时 间减至最小。但这将引起附加问题。假设例2 1 中的代码使用作锁定发送接收。 语句m = 2 0 可能在消息m 发出前执行，因此新值2 0 将传送给b ，而不是所希望发 送的值1 0 。在接收方一边，语句x = s + 1 可能在来自a 的消息到达s 前被执行， 因此可能会使用s 原来的值一1 0 0 。为了纠正这神不希望的行为，消息传递系统提 供了状态检查或等待函数，它们可强制进程处于等待状态直到可安全地继续执行。 3 7 西北。r 业大学硕士论文 第四章旅行商的并行遗传算法求解 使用这一函数后，例2 1 中的代码就变为如下所示： 进程a进程b m = 1 0 ；s = 一1 0 0 ； l i ：s e n d m t o b ；l 1 ：r e