（应用数学专业论文）求解背包问题的混合遗传算法.pdf

北京邮电人学硕+ 1 ：毕业论文摘要 求解背包问题的混合遗传算法 摘要 遗传算法是模拟自然界生物进化过程与机制求解极值问题的一 类自组织、自适应人工智能技术，遗传算法是在固定的种群模下，通 过按一定概率进行的选择、杂交和变异等遗传操作来完成群体的更新， 并逐渐使群体进化到包含或接近最优解的状态。由于其具有易于实现、 鲁棒性强、应用效果明显等优点而被众多应用领域所接受，在自适应 控制、组合优化、模式识别、机器学习、人工生命等领域得到了广泛 的应用。 背包问题( k n a p s a c kp r o b l e m ) 是运筹学中一个典型的组合优化难 题，广泛的应用在各种领域，因此研究遗传算法求解背包问题有着重 要的应用价值。 本文在利用遗传算法在小种群下求解背包问题方面做了研究与 分析，其内容主要如下： 首先，介绍了遗传算法的背景、运用到的领域。详细介绍了遗传 算法的基本原理和流程，以及常用的技术，对遗传算法的理论基础： 模式定理和积木块假设分别做了阐述。 然后，介绍了背包问题的相关信息，阐述遗传算法导致的早熟现 象，通过实验看出其对于求解背包问题的不足。 再对已有算法进行改进，主要体现在以下三个方面：第一，引进 一个参数用以衡量种群中的染色体的相似程度，有效地增加了种群的 多样性；第二，在杂交和变异运算过程中，混合了模拟退火思想用于 新个体的接受准则；第三，本文提出一种新的变异方式，大大提高了 算法搜索效率。 最后，通过实验对比得出改进后的算法在求解文中问题上具有 更好的稳定性、收敛性、计算效率。 关键字：遗传算法，背包问题，小种群，组合优化 北京邮电人学硕士毕业论文 摘要 t a c k l i n gk n a p s a c kp r o b l e mw i t hi m 田r o v e d g e n e t i ca l g o r i t h mw i t hs mai ，lp o p u l a t l 0 n o n a bs t r a c t g e n e t i ca l g o r i t h mi sas e l f - a d a p t i v ea n ds e l f - o r g a n i z a t i o n a la r t i f i c i a l i n t e l l i g e n c ew h i c hs i m u l a t e sn a t u r ee v o l u t i o nt oo b t a i nb e s ts o l u t i o na s p o s s i b l e i tr e g e n e r a t e sp o p u l a t i o nt h r o u g he x e c u t i n gg e n e t i co p e r a t i o n s s u c ha ss e l e c t i o n ，c r o s s o v e ra n dm u t a t i o n w i t hp r o b a b i l i t yt om a k e p o p u l a t i o n e v o l v e d b e c a u s ea l g o r i t h mi s e a s yt o b er e a l i z e da n d a p p l i c a t i o ne f f e c ti so u t s t a n d i n g ，g e n e t i ca l g o r i t h m i sa p p l i e di nal o to f d o m a i n sw h i c hc o n t a i ns e l f - a d a p t i v ec o n t r o l ，c o m b i n a t o r i a lc o m b i n a t i o n ， p a t t e r nr e c o g n i t i o n ，m a c h i n el e a r n i n g ，a n da r t i f i c i a ll i f e k n a p s a c kp r o b l e m ( k p ) i sat y p i c a ln p so p t i m i z a t i o np r o b l e ma n di s w i d e l yu s e di nm a n yf i e l d s s ot h er e s e a r c ho fg as o l v i n gk ph a st h e i m p o r t a n t v a l u eo fa p p l i c a t i o n t h er e s e a r c ho fg as o l v i n gk pw i t hs m a l lp o p u l a t i o ni sp r e s e n t e di n t h i sp a p e r t h em a i nc o n t e n ti sa sf o l l o w s ： f i r s t l y , i n t r o d u c et h eb a c k g r o u n da n dt h ea p p l i c a t i o n o fg e n e t i c a l g o r i t h m i n t r o d u c et h eb a s i ct h e o r y o fg e n e t i ca l g o r i t h mi nd e t a i l ， i n c l u d i n gi t sw o r k i n gf l o wa n dt h ec o m m o nt e c h n o l o g yt h a th a sb e e n u s e di nt h eo p t i m i z a t i o np r o c e s s t h es c h e m a t at h e o r e ma n db u i l d i n g b l o c kh y p o t h e s i sa r ea l s oe x p a t i a t e di nt h i sp a p e r s e c o n d l y , i n t r o d u c et h ek n a p s a c kp r o b l e ma n dt h ep r e m a t u r ei n g e n e t i ca l g o r i t h m f i n do u tt h es h o r t a g ew i t he x p e r i m e n t t h e n ，i m p r o v et h ea l g o r i t h ma sf o l l o w s ：i n t r o d u c ei n t oap a r a m e t e rt o w e i g ht h es a m e n e s so fc h r o m o s o m ew h i c hc a ni n c r e a s et h ev a r i e t yo f t h e p o p u l a t i o n s e c o n d l y , i nt h ep r o c e s so f c r o s s o v e ra n dm u t a t i o ns i m u l a t e d a n n e a l i n gi su s e dt oa c c e p tt h en e wi n d i v i d u a l t h i r d l y , an e wm e t h o di n m u t a t i o ni sg i v e nt oi m p r o v et h ee f f i c i e n c yi ns e a r c h i n g f i n a l l y , t r i e dw i t he x p e r i m e n t so fk n a p s a c kp r o b l e mi tc o n c l u d e s t h a tt h en e wg e n e t i ca l g o r i t h mh a sb e t t e rc o n v e r g e n c e ，s t a b i li t ya n d e f f i c i e n c yi ns m a l lp o p u l a t i o n 北京邮i u 人学顾i ：毕业论义摘要 k e y w o r d s ：g e n e t i ca l g o r i t h m ；k n a p s a c kp r o b l e m ；s m a l lp o p u l a t i o n ； c o m b i n a t o r i a lo p t i m i z a t i o n 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 隧! j 日期： 1 笸2 1 兰： 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： r 期： 2 竖竺l ：! ! ! 同期：乌b ，_ 北京邮电人学硕：l 二学位论文第一章 遗传算法的皋奉腺理和算法 第一章遗传算法的基本原理和算法 1 1 遗传算法概述 1 1 1 生物进化与遗传算法 生命自从在地球上诞生以来，就开始了漫长的生物进化历程。关于生物进化 的原因有多种解释，其中被人们广泛接受的是达尔文的自然选择学说。自然选择 学说认为，生物要生存下去，就必须进行生存斗争。生物斗争包括种内斗争、种 间斗争以及跟无机环境之间的斗争三个方面。在生存斗争中，具有有利变异的个 体容易存活下来，并且有更多的机会将有利变异传给后代：具有不利变异的个体 就容易被淘汰，产生后代的机会也少得多。因此，凡是在生存斗争中获胜的个体 都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存，不适者淘汰 的过程叫做自然选择。自然选择学说表明，遗传和变异是决定生物进化的内在因 素。 生命科学与工程科学的相互交叉、相互渗透和相互促进是近代科学技术发展 的一个显著特点，而遗传算法的( g e n e t i ca 1 9 0 i l i t h m g a ) 正是模拟达尔文的遗 传选择和自然淘汰的生物进化过程的计算模型。它是由美国m i c h i g a n 大学的 h o l l a n d 教授提出的【。 这种模拟生物界中自然选择和群体遗传机制的遗传算法，采用简单的编码技 术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣 汰的自然选择来指导学习和确定搜索的方向。由于它采用种群的方式组织搜索， 这使得它可以同时搜索多个域，而且用种群组织搜索的方式使得它特别适合大规 模并行。因此它能够解决许多常规方法尚无法处理的复杂优化问题【2 】。 遗传算法主要特点是直接对结构对象进行操作，不存在求导和函数连续性的 限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能 自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。 遗传算法的这些性质，己被人们广泛地应用于组合优化、机器学习、信号处理自 适应控制和人工生命等领域它是现代有关智能计算中的关键技术之一【”】。 近年来，商业、金融领域已成为遗传算法应用热点。遗传算法与现代计算机 强大的运算能力结合，使金融交易中瞬息万变的诸多因素能够为人理解并能加以 利用，使交易者更多地依赖于计算机的速度【5 1 。目前己经有许多基于遗传算法的 软件包应用于金融系统和股票投资分析【6 】。 北京邮i u 人学顾i ：学位论文第一章遗传算法的螭奉原理和算法 1 1 2 遗传算法的算法流程 遗传算法模拟了自然选择和遗传中发生的复制、交叉和变异等现象，从任意 一种初始种群( p o p u l a t i o n ) 出发，通过随机选择、交叉和变异操作，产生一群更适 应环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代接着一代地 不断繁衍进化，最后收敛到一群最适应环境的个体( i n d i v i d u a l ) ，求得问题的最优 解【7 。 遗传算法的运算流程包括编码、初始群体生成、适应度值的评价检测、选择、 交叉、变异六部分，下面分别做简要的介纠8 邶】。在1 3 章节中将对其作详细介绍。 ( 1 ) 针对问题的编码 编码的主要作用是把所求问题空间q 中的参数或解转化为遗传算法能操作 的染色体。编码是遗传算法实施的基础，遗传算法在进行搜索之前先将解空间中 的解的数据表示成遗传空间的基因型串结构数据，这些数据的不同组合就构成了 不同的点。只有把实际问题的解转化为遗传空间的基因型串结构数据，遗传算法 才可以运作。 编码应主要考虑到如下几点： 完全性：原则上，问题空间中的所有解的可能性都要构造出来 封闭性：每个基因编码对应一个种群中可接受的个体。 最小字符编码规则：使问题得到自然表示所需要的最小编码字符集的编码 方式。 模块性：若表现型的结构中有多个重复的结构，在基因型编码中这种重复 是应该避免的。 符合积木块规则：应使用易于产生与所求问题相关的低阶、短定义距模式 的编码方案。 目前常用的编码方式为二进制编码等，其中二进制编码方式最基本，易于操 作。 ( 2 ) 初始群体的生成 初始群体的生成：随机生成n 个串结构数据，每个串结构数据称为一个个体， n 个个体构成一个群体。遗传算法以这n 个串结构作为初始点开始迭代。设置进 化代数计数器t ( o ) ；设置最大进化代数t ；随机生成n 个个体作为初始群体p ( o ) 。 ( 3 ) 设置适应度函数 适应度函数表明个体或解的优劣性。对于不同的问题，适应度函数定义的方 式不同。根据具体的问题，计算群体p ( t ) 中各个个体的适应度。 ( 4 ) 选择 将选择算子作用于群体，根据适应度函数值的大小，选取适应度高的个体进 行下一步的操作。 北京邮电人学硕士学位论文第一章遗传算法的基本原理和算法 ( 5 ) 交叉 将交叉算子作用于群体，交叉操作以交叉概率p c 随机选取群体中的个体在 随机生成的位置进行交叉。其目的是把好的基因传给下一代的同时，能生成更复 杂基因结构的新个体。 ( 6 ) 变异 将变异算子作用于群体，变异操作以变异概率p m 随机选取个体中的基因进行 变异，得到新的个体。变异算子的主要作用是改善遗传算子的局部搜索能力维持 群体的多样性。 根据上述的流程，可以观察得出遗传算法存在初始种群个数n ，交叉概率p 。 和变异概率p m 这三个关键参数，这三个关键参数有如下的确定规n - ( 1 ) 初始群体规模n 群体规模影响遗传优化的最终结果以及遗传算法的执行效率。当群体规模n 太小时，遗传算法的优化性能一般不会太好，而采用较大的群体规模则可减少遗 算法陷入局部最优解的机会，但较大的群体规模意味着计算复杂度高。一般取n 从1 0 n 1 6 0 之间。 在本文接下来研究的问题中，便是基于小种群的情况来讨论的。 ( 2 ) 交叉概率p 。 交叉概率p 。控制着交叉操作被使用的频度。较大的交叉概率可增强遗传算法 开辟新的搜索区域的能力，但高性能的模式遭到破坏的可能性增大；若交叉概率 太低，遗传算法搜索可能陷入迟钝状态。一般取值从0 2 5 n1 0 0 之间。 ( 3 ) 变异概率p m 变异在遗传算法中属于辅助性的搜索操作，它的主要目的是维持解群体的多 样性。一般来说，低频度的变异可防止群体中重要的、单一基因丢失的可能性， 而高频度变异将使遗传算法趋于纯粹的随机搜索。通常取变异概率p m 为0 0 0 1 至u 0 1 之间的数。 1 1 3 遗传算法的基本操作1 1 - 1 6 】 遗传算法具有三个基本操作：选择( 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 ) 交叉 3 北京邮i u 人学硕1 ：学位论文第一章遗传算法的甚奉原理和算法 交叉操作是遗传算法中最主要的操作。通过交叉操作可以得到新一代个体， 新个体组合了父辈个体的特征。将群体内的各个个体随机搭配成对，对每一个个 体，以交叉概率( c r o s s o v e rr a t e ) p 。交换它们之间的部分染色体。 交叉算子体现了信息交换的思想。 ( 3 ) 变异 变异操作首先在群体中选择一个个体，对于选中的个体以变异概率凡随机改 变串结构数据中某个串的值，即对群体中的每一个个体以变异概率( m u t a t i o n r a t e ) p m 改变某一个或某一些基因座上的基因值为其他的等位基因。同生物界一 样，遗传算法中变异发生的概率很低。变异为新个体的产生提供了机会。 1 1 4 标准遗传算法 标准遗传算法( 也称为基本遗传算法或简单遗传算法，s i m p l eg e n e t i c a l g o r i t h m ，简称s g a ) 是一种群体型操作，该操作以群体中的所有个体为对象， 只使用基本的遗传算子( g e n e t i co p e r a t o o ：选择算子( s e l e c t i o no p e r a t o r ) ，交叉算 ：子：( c r o s s o v e ro p e r a t o r ) 和变异算子( m u t a t i o no p e r a t o r ) t 1 7 1 。 标准遗传算法遗传进化操作过程简单，容易理解，是其他遗传算法的基础， 它不仅给其他遗传算法提供了一个基本框架，同时也具有一定的应用价值。选择、 交叉和变异是遗传算法的三个主要操作算子，他们构成了遗传操作，使遗传算法 具有了其他算法没有的特点。 下面描述s g a 的数学模型。 基本遗传算法( s g a ) 可定义为一个八元组： s g a = ( c ，e ，p o ，m ，西，f ，、i ，t ) c ：个体的编码方法； e ：个体适应度评价函数； p o ：初始种群； m ：种群大小； m ：选择算子； r ：交叉算子： 甲：变异算子； t ：遗传算法迭代终止条件。 下图为s g a 的流程图： 4 北京邮电人学硕士学位论文 第一章 遗传算法的肇奉原理和算法 图1 - 1s g a 基本流程图 1 1 5 遗传算法的特点 遗传算法具有如下的优点： ( 1 ) 对可行解表示的广泛性 遗传算法处理的对象不是参数本身，而是针对那些通过参数集进行编码得到 的基因个体。此编码操作使得遗传算法可以直接对结构对象进行操作。 ( 2 ) 群体搜索特性 许多传统的搜索方法都是单点搜索，这种点对点的搜索方法，对于多峰分布 的搜索空间常常会陷于局部的某个单峰的极值点。相反，遗传算法采用的是同时 处理群体中多个个体的方法，即同时对搜索空间中的多个解进行评估。这一特点 使遗传算法具有较好的全局搜索性能，也使得遗传算法本身易于并行化。 ( 3 ) 不需要辅助信息 遗传算法仅用适应度函数的数值来评估基因个体，并在此基础上进行遗传操 作。更重要的是，遗传算法的适应度函数不仅不受连续可微的约束，而且其定义 域可以任意设定。对适应度函数的唯一要求是，编码必须与可行解空间对应，不 能有死码。由于限制条件的缩小，使得遗传算法的应用范围大大扩展。 ( 4 ) 遗传算法使用概率转换规则而不用确定性规划 遗传算法使用概率转换规则来调整其搜索方向，各代群体问没有统一的联系 规律。但使用概率转换规则并不意味着这种方法属于随机算法范畴，它只是使用 随机转换作为工具来调整搜索过程趋向于目标函数不断改进的区域。 5 北京邮i u 人学硕i ：学位论义第一章遗传算法的攮奉原理和算法 ( 5 ) 易扩充性 针对某一问题的遗传算法经简单修改即可适应于其他问题，或者加入特定问 题的领域知识，或者与已有算法相结合，能够较好地解决一类复杂问题，因而具 有较好的普适性和易扩充性。 总的来说，与传统方法相比，遗传算法的优越性主要表现在：首先，在遗传 算子的作用下，遗传算法具有很强的搜索能力，能以很大概率找到问题的全局最 优解；其次，由于它固有的并行性，能有效地处理大规模的优化问题l l 圳。 1 2 遗传算法的理论基础 遗传算法有效性的理论依据为模式定理和积木块假设。模式定理保证了较优 的模式( 遗传算法的较优解) 的样本呈指数级增长，从而满足了寻找最优解的必 要条件，即遗传算法存在着找到全局最优解的可能性。而积木块假设指出，遗传 算法具备找到全局最优解的能力，即具有低阶，短距、高于平均适应度的模式( 积 木块) 在遗传算子作用下，相互结合，能生成高阶、长距、高于平均适应度的模 式，最终生成全局最优解。 1 2 1 模式定理( s c h e m a t at h e o r e m ) 1 2 0 - 2 3 1 遗传算法的执行过程中包含了大量随机性操作，本身算法并不复杂，但却展 示出了强大的信息处理能力，因此有必要对其数学机理进行分析，模式( s c h e m a ) 在一定程度上对此作了解释，奠定了遗传算法的理论基础。模式是描述种群中任 意染色体之间相似性的一维符号串。它定义在符号表0 ，1 ，木之上，即由数字o ， 1 和通配符宰任意组合而成。模式的0 ，l 序列组成其固定部分，幸序列表示其变化 部分，整个模式表示有意义的匹配。例如：模式o l 木枣可和0 1 0 0 ，0 1 0 1 ，0 11 1 ，0 11 0 中的任何一个匹配。下面是模式的定义： 定义1 1 ：基于三值字符集 o ，l ， ) 所产生的能描述具有某些结构相似性的 0 ，l 字符串集的字符串称作模式。 根据模式的定义，长度为l 的二进制串隐含着2 l 个模式。一个模式可以隐含 在多个串中，不同的串之间通过模式而互相联系。遗传算法中串的运算，实际上 是模式的运算模式中包含两个重要参数：模式的阶( s c h e m ao r d e r ) 和定义距 ( d e f i n i n gl e n g t h ) 。 定义1 2 ：模式h 中确定的个数称为模式h 的模式阶，记做o ( h ) 。 比如模式0 1 1 宰1 ，i 的阶数为4 ，而模式o 宰幸枣木奉的阶数为l 。显然，一个模式的阶 数越高，其样本数就越少，因而确定性越高。 定义1 3 ：模式h 中第一个确定位置和最后一个确定位置之间的距离称为模式 6 北京邮l 乜人学硕士学位论文第一章遗传算法的基本原理和算法 的定义距。记做6 ( h ) 。 比如0 l l + l 幸的定义距为4 ，而模式0 幸木宰宰幸的定义距为0 。 模式阶和定义距描述了模式的基本性质。模式阶用来反映不同模式问确定性 的差异。如果模式阶越高，模式的确定性也就越高，所匹配的样本个数就越少。 在遗传操作中，即使是阶数相同的模式，也会有不同的性质，模式的定义距就反 映了这种性质差异。 下面讨论模式在遗传操作下的变化。首先令么( 力表示第t 代中串的群体，以 4 ( f ) ( ，_ l ，2 , - - - , n ) 表示t 代中第j 个个体串。 ( 1 ) 选择算子 设在第t 代种群a ( 力中模式h 所能匹配的样本数为m ，记为m f ) 。在选择 中，一个位串4 以概率p j = f j y f f 被选中并进行复制，其中厂，是个体a j ( t ) 的适 应度。假设一代中群体大小为n ，且个体两两互不相同，则模式h 在第什1 代中 的样本数为：m ( t t ，t + 1 ) = r e ( t ，c ) j 磐。 ( 1 1 ) 一l ji 式中，死日) 是在t 时刻对应于模式的位串的平均适应度。令群体的平均适应度为 7 = 厂；，则有 m ( h ，t + 1 ) = m ( h ，c ) 掣 ( 1 - 2 ) 现在，假设模式h 的平均适应度高于群体的平均适应度，且设高出的部分为c 厂， c 为常数，则有 m ( h ，t + 1 ) = r e ( t ，c ) ! 笋= ( 1 + c ) m ( t t ，t ) ( 1 3 ) 假设从t = - 0 开始，c 保持为常值，则有 m ( t t ，t + 1 ) = ( 1 + c ) 。m ( 4 ，o ) ( 1 - 4 ) 可见，在选择算子的作用下，平均适应度高于群体平均适应度的模式将呈指 数级增长，而平均适应度低于群体平均适应度的模式将呈指数级减少。 ( 2 ) 交叉算子 仅有选择操作，并不能产生新的个体，即不能对搜索空间中新的区域进行搜 索，因此引入了交叉操作。下面讨论模式在交叉算子作用下所发生的变化，这里 只考虑单点交叉的情况。 模式h 只有当交差点落在定义距之外才能生存，在单点交叉下h 的生存概率 p s = 1 6 ( h ) ( 1 1 ) ，其中，为二进制串的长度。交叉本身也是以概率只发生 的，所以模式h 的生存概率为： p 。= 1 一p 。6 ( h ) ( 1 1 ) ( 1 - 5 ) 考虑到若是交叉发生在定义距内，模式也有不被破坏的可能性，这种情况出 现在当两个个体交叉，相应模式中确定位对应相等的时候，此时模式便不被破坏。 因此，上式给出的生存概率是一个下界，即有： p 。1 一p c 6 ( h ) ( t 一1 ) ( 1 - 6 ) 7 北京邮l 【1 人学硕b 学位论文第一章遗传算法的辏奉原j 里和算法 再考虑到模式h 在选择和交叉算子的共同作用下的变化。参照上述( 1 2 ) 与 ( 1 6 ) 式，则有： m c n ，亡+ 1 ) m ( n ，c ) 木( 2 等堕) 幸 1 一尼木8 ( n ) c t 一1 ) 】 ( 1 7 ) 由式( 1 7 ) 可以看出，在选择和交叉算子的共同作用下，模式的增长或减少取 决于两个因素：第一，模式的平均适应度是否高于群体平均适应度；第二，模式 是否具有较短的定义距。显然，那些平均适应度高于群体平均适应度、具有短定 义距的模式将呈指数级增长。 ( 3 ) 变异操作 最后考虑变异操作。假定串的某一位置发生改变的概率为p m ，则该位置不 变的概率为1 - p m ，而模式h 在变异算子作用下若要不受破坏，则其中所有的确 定位置( 为“0 或“l 的位) 必须保持不变。因此模式h 保持不变的概率为 ( 1 一p m ) o c t o ，其中口d 倒为模式h 的阶数。当p m 1 时，模式h 在变异算子作 用下的生存概率为 p s = c 1 一p m ) o ( 月) 1 一o c h ) 木p m ( 1 - 8 ) 综上所述，模式h 在选择算子、交叉算予以及变异算子的共同作用下，其 子代的样本数为 m ( n ”1 ) m ( 肌) 木( 钥木【1 一足木矧吖1 0 ( - 0 木p m ( 1 - 9 ) 由式( 1 9 ) ，可以得出如下的定理，称为“模式定理 ： 定理1 1 ( 模式定理) ：在遗传算子选择、交叉和变异的作用下，具有低阶、 短定义距以及平均适应度高于群体平均适应度的模式在子代中将得以指数级增 长。 统计学研究表明：在随机搜索中，要获得最优的可行解，则必须保证较优解 的样本呈指数级增长，而模式定理保证了较优的模式( 遗传算法的较优解) 的样 本呈指数级增长，从而给出了遗传算法的理论基础。另外，由于遗传算法总是能 以一定的概率遍历到解空间的每一个部分，因此在选择算子的条件下总是能得到 问题的最优解。 h o l l a n d 的模式定理通过计算有用相似性，奠定了遗传算法的数学基础。该 定理是遗传算法的主要定理，在一定程度上解释了遗传算法的机理、数学特征以 及很强的计算能力等特点。 1 2 2 积木块假设【2 0 之3 】 由模式定理可知，具有低阶、短定义距以及平均适应度高于群体平均适应度 的模式在子代中将以指数级增长。这类模式在遗传算法中非常重要，我们给它们 一个特别的名字积木块( b u i l d i n gb l o c k ) 。 8 北京邮电人学硕二l 学位论文 第一章遗传算法的基本原理和算法 定义1 4 ：具有低阶、短定义距以及高适应度的模式称作积木块。 积木块假设( b u i l d i n gb l o c kh y p o t h e s i s ) - 低阶、短距、适应度高的模式( 积 木块) 在遗传算子作用下，相互结合，能生成高阶、长距、适应度高的模式，可 最终生成全局最优解。 与积木块一样，这些“好”的模式在遗传操作下相互拼搭、结合，产生适应 度更高的串，从而找到更优的可行解，这正是积木块假设所揭示的内容。模式定 理保证了较优的模式( 遗传算法的较优解) 的样本数呈指数级增长，从而满足了 寻找最优解的必要条件，即遗传算法存在着寻找到全局最优解的一可能性。 而本节的积木块假设则指出，遗传算法具备寻找到全局最优解的能力，即积 木块在遗传算子作用下，能生成高阶、长距、高平均适应度的模式，最终生成全 局最优解。 1 3 遗传算法的实现过程 遗传算法的每一步都与所求解的问题紧密相关，对于具体的问题，采用合适 的方法，有利于简化遗传算法，加速遗传算法收敛的功能。下面对遗传算法根据 具体问题的实现技术作简单的介绍1 2 4 - 2 7 】。 1 3 1 编码 编码是遗传算法首先要解决的问题，也是设计遗传算法的一个关键步骤。在 遗传算执行过程中，对不同的具体问题进行编码，编码的好坏直接影响选择、交 叉、变异等遗传运算。下面介绍几种常用的编码方法。 ( 1 ) 二进制编码 二进制编码方法是遗传算法中最主要的一种编码方法，它使用的编码符号集 是由二进制符号0 和1 组成的二值符号集 0 ，1 ) ，它所构成的个体基因型是一个二 进制编码符号串。二进制编码符号串的长度与问题所要求的求解精度有关。 假设某一参数的取值范围是【u m i n ，u m 戤】，可以用长度为z 的二进制编码符号串 来表示该参数，则它总共能够产生2 7 种不同的编码，若使参数编码是的对应关系 如下： 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 = 0一 u m i n 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 = 1一 u m i 。1 + 6 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 l = 2 l l u m 戤 则二进制编码的编码精度为： o ，m n x 一，m f 7 l d = 可丁 9 北京邮i u 人学硕一j 二学位论文 第一章遗传算法的基本原理和算法 假设某一个体的编码是：x ：b ，b ，1 b ：b l 则对应的解码公式为： x = + 匹b z 2 i - t ) 百u r e a x - u m i n一上 例如，对于xe o ，1 0 2 3 ，若用l o 位长的二进制编码来表示的话，则下述的符 号串x ：0 0 1 0 1 0 11 11 就可以表示一个个体，它所对应的参数值7 黾r = - 1 7 5 。此时的编 码精度为6 = 1 。 二进制编码方法有下面叙述的一些优点： 编码与解码操作简单易行； 交叉、变异等遗传操作便于实现； 符合最小字符集编码原则； 便于利用模式定理对算法进行理论分析。 ( 2 ) 格雷码编码 使用格雷码编码方法对整数进行编码，连续的两个整数对应的编码之间仅有 一个码位是不同的，其余码位都相同。格雷码编码方法是二进制编码方法的一种 变形。 十进制数、二进制编码与格雷码编码的0 至0 1 5 的表示方法如表( 1 1 ) 所示。 十进制数二进制码格雷码编码 o0 0 0 00 0 0 0 10 0 0 1 0 0 0 l 2o o l o0 0 1 1 30 0 1 10 0 1 0 40 1 0 00 1 1 0 5o l o l0 1 1 1 6 o l l o0 1 0 1 70 1 1l0 1 0 0 81 0 0 01 1 0 0 91 0 0 11 1 0 1 1 01 0 1 01 1 1 1 1 l 1 0 1 1 l l1 0 1 2 1 10 0 1 0 1 0 1 31 1 0 11 0 1 1 1 41 ll o1 0 0 1 1 5 1 11 l1 0 0 0 表( 1 1 ) 表中显示了十进制、二进制编码与格雷码编码对自然数0 到1 5 的不同表示方 ( 3 ) 浮点数编码 对于一些多维、高精度要求的连续函数优化问题，使用浮点数编码。所谓浮 点数编码，是指个体的每个基因值使用某一范围内的浮点数来表示，个体的编码 1 0 北京邮电大学硕l 二学位论文第一章遗传算法的皋奉原理和算法 长度等于其决策变量的个数。浮点数编码方法也叫真值编码方法。 ( 4 ) 符号编码方法 符号编码方法是指个体染色体编码串中的基因值取自一个无数值含义、而只 有代码含义的符号集。 ( 5 ) 多参数级联编码 对含有多个变量的个体进行编码的方法就称为多参数级联编码方法。多参数 级联编码最常用也是最基本的一种方法是：将各个参数分别以某种方法进行编码， 然后再将它们的编码按照一定的顺序连接在一起就组成了表示全部参数的个体 编码。 1 3 2 适应度函数 判断个体对环境的适应程度叫适应度，在进化中适应度是群体个体生存机会 选择的唯一指标，适应度大的个体遗传到下一代的概率大些，反之会被淘汰。遗 传算法在进化搜索中基本不利用外部信息，仅以适应度函数作为区分种群个体好 坏的标准。一般而言，适应度函数是由目标函数变换而来的。 适应度函数通常有以下三种： 直接以待求解的目标函数转化为适应度函数，即： 若目标函数为最大化问题：f i t ( 厂( x ) ) = 厂( x ) ； 若目标函数为最小化问题：f i t ( 厂 ) ) = - f ( x ) 界限构造法 若目标函数为最小化问题，则：f i t i f ( x ) ) = g 甜- f ( x ) ，c m 似- f ( x ) 其中c m 舛 为删的最大估计值； 一 若目标函数为最大化问题，则：f i t ( 厂0 ) ) = 厂( x ) 一g 蛾，c 卅。 = o ，c + f 【x ) = o 若目标函数为最大化问题，则： f i t ( 厂( z ) ) = i ( i + c 一厂( z ) ) ， c = o ，c f 【x ) = o 1 3 3 选择 从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。选择算子有时又称 为再生算子( r e p r o d u c t i o no p e r a t o r ) 。选择的目的是把优化的个体( 或解) 直接遗传 到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体 中个体的适应度评估基础上的，目f j 常用的选择算子有以下几种。 ( 1 ) 适应度比例方法 北京邮i u 人学硕i ：学位论义第一章遗传算法的基奉原理和算法 适应度比例方法是目前遗传算法中最基本也是最常用的选择方法。它也叫轮 盘赌或蒙特卡罗选择。在该方法中，各个个体的选择概率和其适应度值成比例。 这种方法能使优秀个体有更大的概率被保留下来，而较差个体得以延续的概率相 对较低。 ( 2 ) 最佳个体保存方法 该方法的思想是把群体中适应度最高的个体不进行配对交叉而直接复制到 下一代中。此种选择操作又称复f 1 l j ( e o p y ) 。 ( 3 ) 锦标赛选择方法 锦标赛选择方法操作思想是，从群体中任意选择一定数目的个体( 称为锦标 赛赛规模) ，其中适应度最高的个体保存到下一代。这一过程反复执行，直到保 存到下一代的个体数达到预先设定的数目为止。锦标赛规模一般取2 。 ( 4 ) 排挤方法 在自然界中，当种群中的个体大量繁殖生存时，为争夺有限的生存资源，群 体中个体之间的竞争压力必然加剧，因此，个体的寿命和出生率也因此而降低。 基于这种机制，d cj o n g 提出了排挤选择方法。采用该方法时，新生成的子代将 替代或排挤相似的父代个体，该方法可提高群体的多样性。 1 3 4 交叉 在自然界生物进化过程中起核心作用的是生物遗传基因的重组( 加上变异) 。 同样，遗传算法中起核心作用的是遗传操作的交叉算子。正如前面介绍的那样， 所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通 过交叉，遗传算法的搜索能力得以飞跃提高。下面是几种基本的交叉方法的介绍。 ( 1 ) 简单交叉 简单交叉又叫做一点交叉。具体操作是：在个体串中随机设定一个交叉点， 实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个体。 表( 1 2 ) 显示了基因在简单交叉的前后变化： 交叉前交叉后 0 1 0 1 1 0 1o l o t l l 0 1 0 1 1 1 1 01 0 1 1 1 0 1 f 交叉点 表( 1 2 ) 表中显示了简单交叉对基因的处理。 ( 2 ) 两点交叉 两点交叉的操作与上述的一点交叉类似，只是随机设置两个交叉点，交叉时 北京邮电大学硕士学位论文第一章遗传算法的基奉原理和算法 两个个体在这两个交叉点之间的编码串相互交换，分别生成两个新个体。 表( 1 3 ) 显示了基因在两点交叉的前后变化： 交叉前交叉后 o l o i l o l lm o l l l l l 1 0 1 1 1 l l o l o l l l o l o ft 交叉点 表0 - 3 ) 表中显示了两点交叉对基因的处理 ( 3 ) 一致交叉 所谓一致交叉是指通过设定屏蔽字( m a s k ) 来决定新个体的基因继承两个旧 个体中哪个个体的对应基因。 1 3 4 变异 变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。 就基于字符集 o ，1 ) 的二进制编码串而言，变异操作就是把某些基因座上的基因 值取反，即o l 或l o 。常用的变异方法有如下几种。 ( 1 ) 基本变异算子 基本变异算子是指对群体中的个体编码串随机挑选一个或多个基因并对这 些基因座的基因值做变动( 以变异概率p m 做变动) 。 ( 2 ) 逆转算子 随机挑选二个点，作为个体编码串中二个逆转点，然后将两个逆转点问的基 因值以逆转概率p i 逆向排序。 ( 3 ) 自适应变异算子 该算子与基本变异算子的操作内容类似，唯一的不同之处在于变异算子p m 不是固定不变，而是随着群体中个体的多样性程度而自适应调整。 1 4 小- 结 本章主要介绍了遗传算法的产生、目前应用的范围与价值做了阐述，随后介 绍了基本原理和方法、基本操作流程和遗传算法的特点，并且对遗传算法的框架 基本的遗传算法做了介绍，对遗传算法的三个关键操作：选择、交叉和变异 分别做了阐述。然后对遗传算法的理论基础：模式定理和积木块假设做了详细的 介绍。最后对遗传算法的几个基本步骤：编码、适应度函数、选择、交叉、变异 中所使用的各种技术做了简单的介绍。 本章是起到一个引入作用，在了解了遗传算法的背景以及基本相关知识过后， 在接下来的章节罩面，本论文将逐步对其算法进行较为深入的分析、讨论，并且 北京邮i b 人学顾l j 学位论义 第一章遗传算法的皋本原理和算法 进行改进工作，最后以实验验证结论。 1 4 北京邮 乜人学硕士学位论文第二章早熟现象对遗传算法的影响 第二章早熟现象对遗传算法的影响 2 1 早熟现象概述 遗传算法是一种全局搜索算法，在实际应用中，显示出了顽强的生命力，以 其突出的优点越来越受到重视。但遗传算法也存在着缺点，比如遗传算法仍然着 存在无法全局收敛的情况，发生这种情况较为典型的是“早熟 现象。 “早熟”现象是指遗传算法的群体多样性遭到破坏，算法搜索停滞不前，最 终收敛于一个局部最优解，而无法收敛于全局最优解。 本章首先讨论了遗传算法中的三个基本遗传算子对早熟现象的影响以及早 熟现象产生的原因，然后以背包问题为例体现了遗传算法的早熟现象，并且以一 种改进算法为例提出了对遗传算法的改进。 2 2 遗传算子对早熟现象的影晌 基本遗传算法中的遗传算子有三种：选择算子、交叉算子和变异算子。下面 将分别说明三种算子的作用以及对“早熟”现象的影响。 2 2 1 选择算子的作用 选择算子是遗传算法中环境对个体适应性的评价方式，也是实现群体优良基 因传播的基本方式。选择算子保证了遗传算法迭代中“适者生存”的群体进化现 象，在很大程度上决定了遗传算法收敛的效果和速度，其表现为优良个体在下一 代群体中具有较强的繁殖能力，而劣质个体则逐渐被淘汰，群体的整体品质得以 提高【2 8 】。 本节以比例选择算子为例讨论在选择算子作用下模式的生存能力。为方便讨 论，暂时不考虑其它算子的作用。洲种群中任意一个个体，p f 倒表示第玳 中个体日出现的概率，每个个体根据它的适应度值的大小决定其被选择的概率。 因此个体脏第t 代出现的概率可以表示为： p t ( h ) - - 1p t 一1 ( h ) 厂( h ) 厂 ( 2 - 1 ) 式中厅j 俐为个体在第卜代出现的概率，形砂表示个体的适应度值，瓦为 第f 代种群的平均适应度