（计算机应用技术专业论文）遗传算法求解tsp问题的研究与改进.pdf

， 二- ； at h e s i sf o rt h ed e g r e eo fm a s t e ri nc o m p u t e ra p p l i c a t i o nt e c h n o l o g y r e s e a r c ha n di m p r o v e m e n to n g e n e t i ca l g o r i t h mf o rs o l v i n gt s p b yd e n gx i a n x i s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rd i n gs h u n l i n o r t h e a s t e r nu n i v e r s i t y j u n e2 0 0 8 舢7m 3 舢1躬舢8 删1胂y 一 卜 | 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 意。 学位论文作者签名：叉p 免习 日 期：加d g 7f 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年日一年口一年半口两年口 学位论文作者签名：叉个乞习 签字日期：知。男7 y - 导师签名： 签字日期： - ， 谚箩，7 ，ol u 东北大学硕士学位论文 摘要 遗传算法求解t s p 问题的研究与改进 摘要 遗传算法是模仿生物进化和自然选择机理，模拟生物在自然环境中的遗传和进化过 程而形成的一种自适应全局优化概率搜索算法。近年来，遗传算法由于在解决各类最优 化问题时表现出的鲁棒性、全局性、隐含并行性和自适应性而成为一种应用同益广泛的 智能优化算法。旅行商问题( t s p ) 是组合优化领域中的一个典型n p 完全问题，是诸 多领域内出现的多种复杂问题的集中概括和简化形式。快速、有效地解决t s p 问题有着 较高的理论意义和实际应用价值。 本文根据t s p 问题的特点和当前研究情况，选用遗传算法对它进行求解。介绍了 遗传算法的原理及基本实现技术，着重阐述了遗传算法的特性和影响遗传算法性能的因 素，针对t s p 问题对遗传算法进行相应的改进。首先针对传统遗传算法中初始种群平均 适度度低的缺点，设计了一种贪婪选择策略代替随机化生成初始种群，从而提高初始种 群的质量；然后根据t s p 问题种群个体编码的特点，结合贪婪算法，设计了一种贪婪交 叉算子，使之既能有效地保留父代个体的优良基因，又能以较大的概率产生新的优良个 体；在变异算子设计上，采用了两种变异算子相结合的方法，以提高种群的多样性；此 外，在进化过程中算法引入了自适应策略来控制遗传参数的变化。本文使用改进的遗传 算法对国际通用的t s p 测试库t s p l i b 中不同城市规模的数据进行测试，实验结果表明 了该算法具有较高的执行效率。 在以上改进遗传算法的基础上，结合主从式并行程序设计的特点，提出了工作站机 群环境中基于m p i 求解t s p 问题的并行遗传算法。该算法采用按城市结点编号分配种 群，并定期在主从进程中交换优良个体。最后利用v c + + 和m p i c h 并行库对算法进行 了实现，通过分析多组实验数据表明该算法在求解速度和精度上均有所提高。 关键词：遗传算法；t s p ；贪婪选择策略；并行遗传算法；m p i ，疗， 魏e 、i 东北大学硕士学位论文a b s t r a c t r e s e a r c ha n di m p r o v e m e n to ng e n e t i c a l g o r i t h m f o rs o l v i n gt r a v e l i n gs a l e s m a np r o b l e m a b s t r a c t g e n e t i ca l g o r i t h m ( g a ) i sa na d a p t i v e ，g l o b a la n ds t o c h a s t i c o p t i m i z a t i o n s e a r c h a p p r o a c hw h i c hs i m u l a t e st h eg e n e t i ca n de v o l u t i o n a r yp r o c e s s e so fb i o l o g i cl i f ei nt h e n a t u r a le n v i r o n m e n ta c c r o r d i n gt ob i o l o g i cl i f ee v o l u t i o n a r ya n dn a t u r es e l e c t i o nm e c h a n i s m i nr e c e n ty e a r s ，g ah a sf u n c t i o n e ds ow e l lw i t hr o b u s t n e s sa n d i n t e r o p e r a b i l i t y , h i d d e n p a r a l l e l i t ya n da d a p t a b i l i t yi nt h es e t t l e m e n to fa l lk i n d so fo p t i m i z a t i o np r o b l e m st h a ti t b e c o m e sa n i n c r e a s i n g l yw i d e s p r e a da p p l i c a t i o no f s m a r t o p t i m i z a t o na l g o r i t h m s t s p ( t r a v e l i n gs a l e s m a np r o b l e m ) i sac l a s s i c a ln o n d e t e r m i n i s t i cp o l y n o m i a lc o m p l e t e p r o b l e mi nt h ef i e l do fc o m b i n a t o r i a lo p t i m i z a t i o n ，a n di ti st h ec o n c e n t r a t e dg e n e r a l i t ya n d s i m p l i f i e df o r mo fm a n yc o m p l i c a t e dp r o b l e me m e r g i n gf r o ma l lk i n d so ff i e l d s o l v i n gi t f l e e t l ya n de f f e c t i v e l yh a sn o to n l yg r e a tt h e o r e t i c a lf u n c t i o n ，b u ta l s oi m p o r t a n tp r a g m a t i c v a l u e t h i sp a p e rc h o o s e sg at os o l v et s pp r o b l e ma c c o r d i n gt ot h ec h a r a c t e r i s t i ca n d r e s e a r c hs t a t u sn o w a d a y so ft s pp r o b l e m t h ep a p e ri n t r o d u c e st h ee l e m e n t sa n db a s i c i m p l e m e n tt e c h n o l o g yo fg a ，a n de x p a t i a t e st h es p e c i a l t yo fg aa n dt h ei m p a c tf a c t o r so fg a p e r f o r m a n c ee x p r e s s l y t h ep a p e rp u t su ps o m ei d i o g r a p h i ci m p r o v e m e n tt os t a n d a r dg a f i r s t l y , ag r e e d ys e l e c t i o ns t r a t e g yi si n t r o d u c e di n s t e a d i n go fr a n d o mm e t h o dt og e n e r a t e i n i t i a l p o p u l a t i o n ；t h e n ag r e e d yc r o s s o v e ro p e r a t o ri s d e s i g n e da c c o r d i n g t ot h e c h a r a c t e r i s t i c so fi n d i v i d u a le n c o d i n gm e c h a n i s mf o rt s pp r o b l e mc o m b i n e dw i t hg r e e d y a l g o r i t h m ，s oa st ob ee f f e c t i v et or e t a i nt h eg o o dg e n e si nf a t h e ri n d i v i d u a la n dt og e n e r a t e n e wi n d i v e d u a lw i t hg r e a t e rp r o b a b i l i t y ；a st ot h em u t a t i o no p e r a t i o n ，ac o m b i n a t i o no ft h e t w om u t a t i o no p e r a t o ri su s e dt oe n h a n c et h ed i v e r s i t yo ft h ep o p u l a t i o n ；i na d d i t i o n ，a n a d a p t i v es t r a t e g yi sp r o p o s e dt oc o n t r o lt h eg ap a r a m e t e r s t h em o d if i e dg aw a st e s t e do n v a r i o u si n s t a n c e si nt s p l i b ，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 et h ea l g o r i t h mi sv a l i da n d e f f e c t i v e o nt h eb a s i so ft h ei m p r o v e dg aa b o v e ，t h e p a p e rp r o p o s e sap a r a l l e lg e n e t i c l i l 一 一0，j a l g o r i t h m ( p g a ) t os o l v et s pp r o b l e mb a s e do nm p i i nc l u s t e ro fw o r k s t a t i o nc o m b i n e dw i t h t h ei d e a so fm a s t e r - s l a v ep a r a l l e lp r o g r a m m i n g t h ep o p u l a t i o na r e d i s t r i b u t e d t os l a v e p r o c e s s e sa c c o r d i n gt ot h ec i t yi dn u m b e r , a n dt h ef i n e i n d i v i d u a la r ee x c h a n g e dr e g u l a r l y b e t w e e nm a s t e ra n ds l a v ep r o c e s s e s t h ea l g o r i t h mi si m p l e m e n t e db yu s i n gv c ha n d m p i c h t h ea n a l y s i sa n dc o m p a r i s o no fm u l t i - g r o u pe x p e r i m e n td a t as h o wt h a t t h e a l g o r i t h mh a se n h a n c e dn o to n l yi ns o l v i n gs p e e db u ta l s oi ns o l v i n gp r e c i s i o n k e y w o r d s ：g e n e t i ca l g o r i t h m ；t s p ；g r e e d ys e l e c t i o ns t r a t e g y ；p g a ；m p i i v m i j | 东北大学硕士学位论文 目录 目录 摘要l i a b s t r a c t i i l 第1 章绪论l 1 1 研究背景1 1 2 研究意义3 1 3 国内外研究现状3 1 4 论文的主要工作4 1 5 论文的组织结构一4 第2 章遗传算法的基本理论7 2 1 基本概念7 2 2 基本原理8 2 3 遗传算法的结构8 2 3 1 编码机制8 2 3 2 控制参数8 2 - 3 3 适应度函数9 2 3 4 遗传算子一9 2 4 遗传算法的运行流程1 l 2 5 模式定理1 2 2 6 遗传算法的优缺点分析15 2 6 1 遗传算法的优点。1 5 2 6 2 遗传算法的缺点15 2 7 遗传算法的改进与发展趋势l6 2 8 本章小结17 第3 章改进的遗传算法求解t s p 问题1 9 3 1t s p 问题描述l9 3 2 传统遗传算法求解t s p 问题2 0 3 2 1 编码及适应度函数2 0 3 2 2 遗传算子2 0 3 3 改进的遗传算法主要操作2 2 3 3 1 编码及适应度函数2 2 3 。3 2 初始化种群2 3 一v 一 东北大学硕士学位论文目录 3 3 3 控制参数2 4 3 3 4 遗传算子2 4 3 4 改进的遗传算法主程序2 7 3 5 算法的实现与实验结果分析2 8 3 6 本章小结3 1 第4 章并行遗传算法3 3 4 1 并行计算和并行计算模型3 3 4 1 1 共享存储模型3 3 4 1 2 消息传递模型3 4 4 2 并行遗传算法的类型3 5 4 2 1 主从式并行遗传算法3 5 4 2 2 粗粒度并行遗传算法3 7 4 2 3 细粒度并行遗传算法3 9 4 3 并行遗传算法的性能分析与评价4 0 4 3 1 遗传代数和种群规模4 0 4 3 2 迁移率与迁移周期4 1 4 - 3 3 性能评价4 l 4 4 本章小结4 3 第5 章基于m p i 的并行遗传算法求解t s p 问题4 5 5 1 工作站机群4 5 5 2m p i 消息传递接口4 5 5 - 3 程序结构j 4 7 5 4 基于m p i 的并行遗传算法的实现一4 9 5 4 1 主进程的工作流程。4 9 5 4 2 从进程的工作流程5 0 5 4 3 算法说明5 1 5 5 实验结果分析5 1 5 6 本章小结5 4 第6 章结论与展望5 5 参考文献5 7 致谢一6 1 攻读硕士期间发表的论文一6 3 一v i 东北大学硕士学位论文第1 章绪论 第1 章绪论 1 1 研究背景 现代科学理论研究与实践中存在着大量与优化、自适应相关的问题，但除了一些简 单的情况之外，人们对于大型复杂系统的优化和自适应问题仍然无能为力。然而，自然 界中的生物却在这方面表现出了其优异的能力，它们能够以优胜劣汰、适者生存的自然 进化规则生存和繁衍，并逐步产生出对其生存环境适应性很高的优良物种。遗传算法j 下 是借鉴生物的自然选择和遗传进化机制而开发出的一种全局优化自适应概率搜索算法。 遗传算法是一类具有较强鲁棒性的优化算法，特别是对于一些大型、复杂非线性系 统，它更表现出了比其他传统优化方法更加独特和优越的性能。它使用群体搜索技术， 通过对当前种群施加选择、交叉、变异等一系列遗传操作，从而产生出新一代的群体， 并逐步使群体进化到包含或接近最优解的状态。由于其具有思想简单、易于实现、应用 效果明显等优点而被众多应用领域所接受，并在自适应控制、组合优化、模式识别、机 器学习、人工生命、管理策略等领域得到了广泛应用。 遗传算法的大致过程【l 】是这样的：将每个可能的解看作是群体中的一个个体或染色 体，并将每个个体编码成字符串的形式，根据预定的目标函数对每个个体进行评价，即 给出一个适应度值。开始时，总是随机的产生一些个体，根据这些个体的适应度利用遗 传算子选择( s e l e c t i o n ) 、交叉( c r o s s o v e r ) 、变异( m u t a t i o n ) 对它们重新组合， 得到一群新的个体。这一群新的个体由于继承了上一代的一些优良特性，明显优于上一 代，以逐步向着更优解的方向进化。 目前，遗传算法的研究内容主要有以下几个方面： ( 1 ) 遗传算法的适用范围问题。一般而言，对同一个问题，存在两种或两种以上的 解决方法，比如对同一个优化问题，即可以使用遗传算法，又可以使用模拟退火，到底 使用哪一种方法更好，现在通常是将两种实现进行比较才能得到结果，而很少能根据问 题的性质进行判断，同样，对于同一种方法，也存在适合应用在那些问题上的问题。遗 传算法虽然己经在很多领域得到了应用，研究工作者也做了很多遗传算法与其他算法计 算性能的比较分析研究，但是现在还没有一种理论能解决遗传算法的使用范围问题，即 哪些问题适用于用遗传算法解决，哪些问题用其他的优化算法更好。 ( 2 ) 遗传算法的数学基础【2 1 。遗传算法虽然已经得到了广泛的应用，但是遗传算法 的理论基础仍然很薄弱，收敛性分析，性能分析仍然是一个很困难的问题。遗传算法的 一1 一 东北大学硕士学位论文第l 章绪论 数学基础主要基于j h h o l l a n d 的模式理论，它是证明遗传算法的收敛性的传统手段， 模式定理中模式适应度难以计算和分析，b e t h k e 运用w a l s h 函数和模式转换发展了有 效的分析工具。但是随着遗传算法应用的广泛，它的应用方式也不断地发展，引进了一 些新的算子对这些新形式的遗传算法，模式理论已经很难提供理论分析的基础。近年 来m a r k o v 链在遗传算法的收敛性分析中得到了很广泛的应用，g o l d b e r g 和s e g r e s t 首 先使用m a r k o v 链分析了遗传算法，e i b e n 等用m a r k o v 链证明了保留最优个体的遗传算 法的遗传算法的概率性全局收敛，r u d o l p h 用齐次有限m o r k o v 链证明了带有复制、交 换、突变操作的基本遗传算法收敛不到全局最优解，不适合于静态函数优化问题，建议 改变复制策略以达到全局收敛。虽然m a r k o v 链在遗传算法的数学分析中应用较广，但 是它分析的对象基本上都是简单遗传算法模型，对于复杂的遗传算法，应用m a r k o v 链 依然是很困难的。 ( 3 ) 遗传算法性能的提高。对于遗传算法的性能分析，现在还没有理论上的方法， 一般是通过试验，对不同参数的计算性能进行比较来确定最后的参数，但是经过多年的 实践也总结出了遗传算法计算过程中的一些特性，如遗传算法的局部搜索能力差等，为 改善遗传算法的性能提供了一定的指导。遗传算法用于解决优化问题的效果较好，但是 随着遗传算法应用范围越来广泛，解决的问题越来越复杂，计算量也不断增大，如何提 高遗传算法的性能是近来研究的重点方向之一，另外，遗传算法有早熟的缺点，如何改 进遗传算法的收敛性也非常重要。提高遗传算法计算性能的方法较多，如调整计算参数， 设计新的算子，运用混合遗传算法，并行处理等。调整参数指调整遗传计算过程中群体 规模，适应度计算，交叉，变异等的计算参数，如增大群体规模，使用变化的交叉率变 异率等。混合遗传算法一般在遗传算法的某一计算过程中应用其他的优化算法，如将模 拟退火算法应用到遗传算法中调整交叉率。 传统的遗传算法虽然具有隐含的并行性，但其实现方法在本质上仍然是串行的。这 种串行的遗传算法在解决一些实际问题时，由于需要较多的个体数量和大量的计算，使 得进化过程比较缓慢，难以达到实时的要求。因此并行遗传算法( p g a ，p a r a l l e lg e n e t i c a l o g r i t h m ) 就受到了较大的重视，并且已经成为目前遗传算法研究的主要课题。遗传 算法与并行计算机相结合，能把并行机的高速性和遗传算法固有的并行性两者的长处彼 此结合起来。遗传算法本身就具有并行性，这种并行性不仅表现在遗传算法的隐并行性 上，而且遗传算法种群中各个个体之间，以及各个种群之间都具有并行性，如果在分布 式系统中利用遗传算法的这些特性，开发具有分布式并行计算能力的遗传算法，将大大 提高遗传算法的计算能力，解决更大、更复杂系统的优化和设计问题。 一2 一 东北大学硕士学位论文第l 章绪论 并行遗传算法利用遗传算法的并行性，使用多个处理器进行处理，可以处理更多的 群体，在更大的空间进行搜索，与调整参数的方法相比，它更简单，与混合遗传算法相 比，它更通用。大部分的并行遗传算法是用并行机实现的，并且得到了大量的理论结果 与实际应用。随着分布式计算的发展，利用分布式系统实现并行遗传算法越来越引起了 研究者的注意。分布式系统可以采用现在通用的p c 机，与并行机实现相比，分布式系 统具有经济性，但是另一方面，由于分布式系统的物理分散度较大，利用分布式系统进 行并行计算时要加入同步协调机制，系统中的处理器差别大，因此运行速度比并行机慢， 它目前主要应用在一些非实时性的问题上，如大型的系统设计与优化等。 1 2 研究意义 本文主要研究用遗传算法求解t s p 问题。t s p ( t r a v e l i n gs a l e s m a np r o b l e m ) 也称 为巡回旅行商问题，它是一个比较古老的问题。最早可以追溯到1 7 5 9 年e u l e r 提出的 骑士旅行问题。t s p 问题是一个典型的、容易描述但是难以处理的n p 完全问题，同时 t s p 问题也是诸多领域内出现的多种复杂问题的集中概括和简化形式。 目前求解t s p 问题的主要方法有启发式搜索法、模拟退火算法、遗传算法、h o p f i e i d 神经网络算法、二叉树描述算法。所以，有效解决t s p 问题在计算理论上和实际应用 上都有很高的价值，而且t s p 问题由于其典型性已经成为各种启发式的搜索、优化算 法的间接比较标准( 如遗传算法、神经网络优化、模拟退火法等) 。遗传算法就其本质 来说，主要是解决复杂问题的一种鲁棒性强的启发式随机搜索算法。因此遗传算法在 t s p 问题求解方面的应用研究，对于构造合适的遗传算法框架、建立有效的遗传操作以 及有效地解决t s p 问题等有着多方面的重要意义。 1 3 国内外研究现状 在遗传算法求解t s p 问题方面，g r e f e n s t e t t e 提出了基于顺序表示( o r d i n a l r e p r e s e n t a t i o n ) 的遗传基因编码方法【3 1 。周鹏设计了求解t s p 的启发式顺序交叉算子【4 l ： 王字平等人根据量子理论提出了求解t s p 的量子遗传算法【5 】；k o n s t a n t i nb o u k r e e v 采用 联赛选择方法和最优个体保存方法相结合的方法，通过在v c + + 6 0 环境下编程实现了 求解t s p 问题的遗传算法，取得了很好的效果；谢胜利等人提出浓度控制策略f 6 】，当 某种个体的浓度超过给定的浓度阀值时减少该种个体的数量，使之控制在给定的浓度阀 值之内，并随机产生新的个体以补足种群的规模，通过实验证明该策略很好的解决了遗 传算法中群体的多样性问题。 在并行遗传算法的研究方面，e a i b a 等人通过将并行机制加入到基本遗传算法中， 一3 一 东北大学硕士学位论文第1 章绪论 提高了算法的灵活性和效率 7 1 ；g r e f e n s t e t t e 全面研究了遗传算法并行实现的结构问题 1 8 ，提出把并行遗传算法按结构形式分为同步主从式、半同步主从式、异步分布式和网 络式等；张旭风等人对并行遗传算法的收敛性进行了分析，并对算法作了优化工作1 9 ； 张桂娟等人提出了一种基于学习机制的并行遗传算法【1 0 】；刘晓平等人设计了一种基于 m p i 的主从式并行遗传算法框架】，并将该框架应用于物理问题的求解，取得了良好 的效果。 1 4 论文的主要工作 本文从基本遗传算法的过程入手，通过分析影响遗传算法性能的因素，对个体的编 码、种群的初始化、选择、交叉和变异算子以及适应度评价函数逐一进行分析，设计出 改进的遗传算法求解t s p 问题。然后从遗传算法的并行性出发，设计出一种改进的并 行遗传算法，以提高算法的执行效率，防止算法的过早成熟收敛，从而得到最优解或满 意解。通过多组实验对算法进行了验证。具体研究内容如下： ( 1 ) 分析了遗传算法的基本原理以及使用它解决问题的方法； ( 2 ) 讨论了遗传算法在求解优化问题时的不足之处，进而引入更为有效的改进的 遗传算法； ( 3 ) 对遗传算法的各个环节加以分析，从而设计出改进的遗传算法： ( 4 ) 在v c + + 环境下实现了改进的遗传算法，并利用m p i 并行环境在简单机群中 实现了主从式并行遗传算法来求解t s p 问题，使用国际通用的t s p 测试库 t s p l i b 中的实例进行测试，并对实验结果进行了比较和分析。 本文的创新点在于： ( 1 ) 设计了一种贪婪选择策略代替随机化生成初始种群，从而提高初始种群的质 且 亘； ( 2 ) 根据t s p 问题种群个体编码的特点，结合贪婪算法，设计了一种贪婪交叉算 子，使之既能有效地保留父代个体的优良基因，又能以较大概率产生新的优 良个体； ( 3 ) 引入动态自适应策略控制相关参数，从而提高算法的执行效率和求解质量； ( 4 ) 在并行遗传算法的实现中采用按城市结点编号分配种群，并定期在主从进程 中交换优良个体，使算法具有较高的执行效率。 1 5 论文的组织结构 第一章：介绍了论文的研究背景和研究意义，对本文所做的工作作了说明； 一4 一 东北大学硕士学位论文 第1 章绪论 第二章：主要介绍了遗传算法的基本理论，并对遗传算法的优缺点作了分析； 第三章：利用改进的遗传算法求解t s p 问题，并对实验结果作了分析和比较； 第四章：介绍了并行计算和并行遗传算法的基本理论； 第五章：根据实验条件，利用m p i 对并行遗传算法作了实现，并对实验结果作了 分析和比较； 第六章：结论与展望。 一5 一 东北大学硕士学位论文 第l 章绪论 一6 一 东北大学硕士学位论文 第2 章遗传算法的基本理论 第2 章遗传算法的基本理论 2 1 基本概念 生命科学与工程科学的相互交叉、相互渗透和相互促进是近代科学技术发展的一 个显著特点，而遗传算法的蓬勃发展正体现了科学发展的这一特征和趋势。遗传算法是 仿真生物遗传学和自然选择机理，模拟生物在自然环境中的遗传和进化过程而形成的一 种自适应全局优化概率搜索算法。它最早由美国密歇根大学的h o l l a n d 教授为研究自然 与人工系统的自适应行为而提出的一种算法。2 0 世纪8 0 年代g o l d b e r g 和m i c h a l e w i c z 对遗传算法进行了大量的研究工作，并成功地将它应用到各种领域的优化问题。 遗传算法是多学科相互结合与渗透的产物，它已发展成一种自组织、自适应的综合 技术，广泛应用于计算机科学、工程技术、管理科学和社会科学等领域。遗传算法的早 期应用主要围绕组合优化问题求解，如煤气管道的最优控制，旅行商( t s p ) 问题等，近 年来迅速扩展到机器学习、设计规划、神经网络优化、核反应堆控制、喷气发动机设计、 通信网络设计、人工生命等领域，显示了遗传算法应用的巨大潜力。目前，遗传算法作 为一种基于统计理论的优化和搜索技术，在计算机视觉领域中的应用也正同益受到重 视，如：特征提取、图像匹配、图像分割中的应用。 由于遗传算法是一种模拟自然进化的现代搜索技术，所以它的很多术语都来源于遗 传学和进化论，下面给出一些常用术语及定义。 个体( i n d i v i d u a l ) ：待求解问题的一个可能解； 种群( p o p u l a t i o n ) ：当前所有的可能解的集合； 子种群( s u b p o p u l a t i o n ) ：种群的一个子集： 染色体( g e n o m e 或c h r o m o s o m e ) ：一个解的编码； 基因( g e n e ) ：个体的一个属性，一个个体包含有多个属性； 孩子( o f f s p r i n g 或c h i l d ) ：新产生的个体； 适应度( f i t n e s s ) ：个体的评价指标； 选择( s e l e c t i o n ) ：遗传算子之一； 交叉( r e c o m b i n a t i o n ) ：遗传算子之一； 变异( m u t a t i o n ) ：遗传算子之一。 一7 一 东北大学硕士学位论文第2 章遗传算法的基本理论 2 2 基本原理 遗传算法类似于自然进化，通过作用于染色体上的基因寻找好的染色体来求解问 题。与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产 生的每个染色体进行评价，并基于适应度来选择染色体，使适应性好的染色体有更多的 繁殖机会。在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体， 形成初始种群；根据适应度对各染色体进行选择复制、交叉、变异等遗传操作，剔除适 应度低( 性能不佳) 的染色体，留下适应度高( 性能优良) 的染色体，从而得到新的群 体。由于新群体的成员是上一代群体的优秀者，继承了上一代的优良形态，因而明显优 于上一代。遗传算法就这样反复迭代，向着更优解的方向进化，直至满足某种预定的优 化指标。 2 3 遗传算法的结构 遗传算法主要由四个部分组成：编码机制( e n c o d i n gm e c h a n i s m ) 、控制参数 ( c o n t r o lp a r a m e t e r s ) 、适应度函数( f i t n e s sf u n c t i o n ) 、遗传算子( g e n e t i c o p e r a t o r ) 。 2 3 1 编码机制 编码机制是遗传算法的基础。遗传算法不是对研究对象直接进行讨论，而是通过某 种编码机制把对象统一赋予由特定符号按一定顺序排成的串( s t r i n g ) 。正如研究生物 遗传是从染色体着手一样，染色体则是由基因排成的串。评估编码策略常采用以下三个 规范： 完备性( c o m p l e t e n e s s ) ：问题空间中的所有点都能作为遗传算法空间中的点的表 现； 健全性( s o u n d n e s s ) ：遗传算法中的染色体能对应所有问题空间中的候选解； 非冗余性( n o n r e d u n d a n c y ) ：染色体和候选解一一对应。 上述三个评估规范是独立于问题领域的普遍准则。对于某个具体的应用领域而言， 可以根据实际问题的特点选择合适的编码方法。 2 3 2 控制参数 在遗传算法的实际操作中，需要适当确定某些参数的值，以提高选优的效果。这些 参数包括： 染色体的编码长度，即串长。在标准遗传算法中，这一长度为常数，记为l ； 一8 一 东北大学硕士学位论文第2 章遗传算法的基本理论 每一代种群的大小，即所包含字符串的个数，也称种群的容量。记为n ； 交叉率( c r o s s o v e rr a t e ) ，即施行交换算子的概率，记为p c ： 变异率( m u r a t i o nr a t e ) ，即施行突变算子的概率，记为p m 。 此外还有遗传的代数，或其他可供确定终止算法的指标等。 2 3 3 适应度函数 优胜劣汰是自然进化的原则。优劣要有标准，在遗传算法中用适应度函数描述每一 个体的适宜程度。通常采用问题的目标函数作为个体的适应度函数。引进适应度函数 的目的在于可根据其适应度对个体进行评估比较来确定优劣程度。遗传算法在进化搜 索中基本上不用外部信息，仅用目标函数即适应度函数为依据。而对目标函数值的使 用是通过评价个体的适应度来体现的。 评价个体适应度的一般过程是： ( 1 ) 对个体编码串进行解码处理后，可得到个体的表现型。 ( 2 ) 由个体的表现型可计算出对应个体的目标函数值。 ( 3 ) 根据最优化问题的类型由目标函数值按一定的转换规则求出个体的适应度。 对于一个问题，定义适应度函数的方法可能不止一种，选择时要尽量反映问题本 身的整体特性，而不能只追求片面的目标。一般来说，适应度函数设计主要满足以下 条件： ( 1 ) 单值、非负、最大化。这个条件是很容易理解和实现的。 ( 2 ) 合理、一致性。要求适应度函数值反映对应解的优劣程度，这个条件达到往 往比较难以衡量。 ( 3 ) 计算量小。适应度函数设计应尽可能地简单，这样可以减少计算时间和空间 上的复杂性，降低计算成本。 ( 4 ) 通用性强。适应度函数对某类问题，应尽可能通用，最好无需使用者改变适 应度函数中的参数。 2 3 4 遗传算子 最重要的遗传算子有三种：选择、交叉和变异算子。这三个算子有如下特点： ( 1 ) 这三个遗传算子的操作都是在随机情况下进行的，即遗传操作是随机化操作。 因此，群体中个体向最优解迁移的规则是随机的； ( 2 ) 遗传操作的效果和上述三个遗传算子所取的操作概率、编码方法、种群大小及 适应度函数的设定密切相关； - 9 东北大学硕士学位论文第2 章遗传算法的基本理论 ( 3 ) 三个遗传算子的操作方法或操作策略随具体求解问题的不同而不同，它们与个 体的编码方式有关。 2 3 4 1 选择 在自然进化的过程中，对环境适应能力强的个体将有更多的机会产生下一代，适 应能力弱的个体产生后代的机会相对较少。模仿这个过程，在遗传算法中使用选择算 子对个体进行优胜劣汰。选择算子在避免基因损失，提高搜索速度和全局收敛方面有 着举足轻重的作用。 常用的选择方法有轮盘赌选择法、排序方法和锦标赛方法等。轮盘赌选择法的基 本思想是每个个体被选中的概率和其适应度值成正比。它把种群中所有染色体的适应 度的总和看作一个轮盘的圆周，而每个染色体按适应度值在总和中所占的比例占据轮 盘的一个扇区。设种群大小为m ，个体i 的适应度值为鼻，个体被选中的概率只可以表 示为： f ? p ，= i j ( 2 1 ) y ， 卜“7 y = l 显然，概率p i 反映了个体i 的适应度在整个群体的个体适应度总和中所占的比例。 个体适应度越大，其被选择的概率就越高，反之则被选择的概率越低。 排序选择方法是将所有个体按适应度值大小排列，然后用某个线性或非线性函数 对排好序的所有个体作映射，但要保证适应度值大的个体被选择的概率相对较大。 锦标赛选择法也是一种基于个体适应度之间大小关系的选择方法。其操作思想是从 群体中任意选择一定数目的个体( 称为竞赛规模) ，其中适应度最高的个体保存到下一 代，这一过程反复执行，直到保存到下一代的个体数达到预先设定的数目为止。锦标赛 选择法的具体操作过程是： ( 1 ) 从群体中随机选取n 个个体进行适应度大小的比较，将其中适应度最高的个 体遗传到下一代群体中。 ( 2 ) 将上述过程重复m 次，就可得到下一代群体中的m 个个体。 2 3 4 2 交叉 在自然界生物进化过程中起核心作用的是生物遗传基因的重组。同样遗传算法中 起核心作用的是交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组生 成新个体的操作。选择操作虽然能够从旧种群中选择出优秀者，但不能创造新的染色 一l o 东北大学硕士学位论文第2 章遗传算法的基本理论 体。交叉操作模拟生物进化过程中的繁殖现象，通过两个染色体的交换组合，来产生 新的优良品种，从而检测搜索空间中新的点。 交换算子有多种形式，最简单的是单点交换( s i n g l e p o i n tc r o s s o v e r ) ，即从群体中 随机取出两个个体串，随机设定一个交叉点，将该点分成两个串的右半段互换，从而生 成两个新的个体。下面是一点交叉的例子。 个体a1 1 0 0 i1 0 1 1 1 0 0 1 0 1 l 新个体a 个体b1 0 1 10 1 1 1 0 1 1 1 0 1 新个体b 7 其中交叉点位置在第4 和第5 个基因之间，交叉时，将交叉后面的半段互换，这 样就得到新个体a7 和b7 。交叉点位置是随机的，因此对于长度为l 的染色体，有 l 1 个交叉点位置，一点交叉可能产生l 1 种不同的结果。 除一点交叉外，还有两点交叉、多点交叉等，即设置两个或多个交叉点，将相应 的基因进行互换。此外，针对不同的具体问题，可以应用不同的交叉方法。例