（基础数学专业论文）演化计算的若干算法及其应用研究.pdf

演化计算的若干算法及萁复用研究 0 1 中文摘要 本文系统的介绍了演化计算的原理、理论及应用，重点研究了 演化计算领域内的若干重要算法，将改进后的算法应用到函数优化、 符号化归及一些经典的组合优化问题上 分布估计算法( e s t i m a t i o no fd i s t r i b u t i o na l g o r i t h m s ，简 记为e d a s ) 是由m u h l e n b e i n 和p a a b 于1 9 9 6 年提出的一种演化优化 方法与传统的演化算法不同，e d a s 是通过对种群的概率分布模型采 样来生成新一代个体的，而上述的概率分布模型是通过对父代中一 部分个体进行概率估计得到的本文将互补机制引入到e d a s 中，并将 其应用到多维背包问题( m u l t i d i m e s i o n a lk n a p s a c kp r o b l e m ，简记 为m k p ) 的求解中 基因表达编程( g e n ee x p r e s s i o np r o g r a m m i n g ，简记为g e p ) 是由 葡萄牙的c a n d i d af e r r e i r 于2 0 0 1 年提出的将用线性的结构体存储 树形的表达式结构，算法简单高效目前，g e p 已经被广泛的应用到电 路设计、数据挖掘、时间序列预测等众多领域针对g e p 算法对个体 的评估时间过长问题，我们提出了一种并行的g e p 算法框架 关键词：演化计算g e p 多父体杂交互补机制 高授教师n ：职硕士学位论文 i l 0 2a b s t r a c t i nt h i sp a p e r , t h et h e o r ya n dp r a c t i c eo fe v o l u t i o n a r yc o m p u t a t i o n h a v eb e e ns y s t e m a t i c a l l yi n t r o d u c e d w ef o c u so u rr e s e a r c ho ns o m e n e w l y a n d i m p o r t a n te v o l u t i o n a r ya l g o r i t h m s ，a s w e l la st h e i r a p p l i c a t i o n i nf u n c t i o no p t i m i z a t i o n ，s y m b o l i cr e g r e s s i o na n dm k p p r o b l e m e s t i m a t i o no fd i s t r i b u t i o na l g o r i t h m s ( e d a s ) w e r ef i r s ti n t r o d u c e d b ym i i h l e n b e i na n dp a a bi n1 9 9 6 i nc o n t r a s tt ot r a d i t i o n a le v o l u t i o n a r y t e c h n o l o g y , e d a sr e p r o d u c e t h en e x t p o p u l a t i o nt h r o u g h t h ej o i n t p r o b a b i l i t y d i s t r i b u t i o na s s o c i a t e dw i t ht h ei n d i v i d u a l so fv a r i a b l e s s e l e c t e da te a c hg e n e r a t i o n t h ep r o b a b i l i t yd i s t r i b u t i o ni sc a l c u l a t e d f r o mad a t a b a s e o fs e l e c t e di n d i v i d u a l so fp r e v i o u sg e n e r a t i o n a r e l a x e dc o m p l e m e n t a lm e c h a n i s mw a sc o o r d i n a t e di n t oe d a si no u r r e s e a r c h g e n e e x p r e s s i o np r o g r a m m i n g ( g e p ) w a sf i r s tp r o p o s e db y c a n d i d af e r r e i ri n 2 0 0 1 e x p r e s s i o n sd i f f e r e n ti ns i z ea n ds h a p ew a s e n c o d i n gi nal i n e a rs t r u c ti ng e ei t sa p p l i c a t i o ni n c l u d ed i g i t a lc i r c u i t d e s i g n ，d a t am i n i n ge t c w ep r o p o s e dap a r a l l e lf r a m e w o r ko fg e pi n t h i sp a p e r k e yw o r d s ：e v o l u t i o n a r yc o m p u t a t i o n g e p m u l t i p a r e n tc r o s s o v e r c o m p l e m e n t a l m e c h a n i s m 演化计弊：的若干算法及其麻用研究 第一章绪论 1 1 引言 近年来演化计算已经在世界范围内形成了一股研究热潮，计算智 能已作为人工智能研究的一个重要方向，从1 9 8 5 年在美国卡耐基梅 隆大学召开第一届国际遗传算法会议至今，演化算法作为具有系统优 化、自适应和自学习特性的高性能计算和建模方法的研究渐趋成熟。 本章介绍演化算法的概况，以及一些较新的进展情况 1 2 演化计算概述 1 ，2 1 引言 演化算法是一类统计优化算法，它们是受自然界演化过程特别是 演化过程中生物个体对环境表现出的自适应性启发而产生的一类优 化技术自然界中个体对环境的自适应性主要表现在基因遗传和个体 对环境的适应能力上尽管物竞天择、优胜劣汰的原则是达尔文于几 个世纪前提出的，但它今天仍被普遍认为在许多生物领域是有效的， 而且这个原则还在不断被扩充与细化 演化算法的起源可以追溯到六十年代中期，j o h nh o ll a n d 在密西 根大学首先提出遗传算法、并将其应用到工程优化中l a w r e n c e f o g e l 和他在加利佛利亚大学的同事开创性的进行了演化规划方面的 研究工作i n g or e c h e n b e r g 在柏林技术大学在同一时间独立的进行 了演化策略方面的研究他们的开创性工作最终导致了演化计算这一 门新兴学科的产生基于演化计算的优化方法适合于求解较难的问 题，特别是那些搜索空间复杂的问题斯坦福大学的j o h nk o z a 教授将 高校搴堑师在职硕l ：擘位论文 演化算法的思想应用到自动程序设计，形成了演化算法的另一个分枝 遗传程序设计。 演化算法维护着一个由问题的待选解构成的种群，通过对种群迭 代的应用一系列的概率性算子如变异、杂交和选择等，使得种群不断 的向最优的方向进化 3 1 2 2 遗传算法 遗传算法中，待解的优化问题相当于自然演化过程中的环境，可 行解则被看作生存于环境中相互竞争的个体个体对环境的适应程度 在g a 中表现为可行解的目标函数可行解的一个集合则相当于自然界 中的一个种群 可行解被编码成一定的数据结构( 染色体) 存储于计算机内，选 择、变异、杂交算子的作用对象就是这些数据结构算法结束时这些 结构又被转换成原闯题的对应解。 尽管这只是对自然演化过程的一种最简单、最直接的模拟，但实 践表明遗传算法是求解复杂问题的一种行之有效的方法 1 0 ( 1 ) 染色体编码 闯题的解在遗传算法中往往被表示成一个二进制的位串，称为染 色体这是一种最普遍的编码方法，近年来随着遗传算法的发展出现 了实数编码、树形编码、整数编码的染色体有的研究者还提出了双 染色体编码的思想 ( 2 ) 进化迭代过程 在遗传算法中，由多个个体组成的初始种群一般是随机生成当 浈化计算的若干算法及其应用研究 然，也可以由领域专家手工生成初始种群或者通过某种启发式算法对 初始种群进行优化 一旦生成了初始种群，算法便进入了一个对种群进行优化的不断 代过程，直到种群内的个体满足停机条件或者达到预定的最大迭代 次数一次迭代过程由个体评价、选择、变异、杂交四个过程组成 个体评价的主要作用是确定染色体对环境的适应能力，称为适应 值函数适应值函数的设计是遗传算法的一个重要研究课题，它的合 理与否直接关系到算法的收敛与运行效率 当完成个体适应值的评价后，就进入了选择操作的过程选择的 主要功能就是根据优胜劣汰原理从种群选出一部分有可能生成更好 的下一代子个体的染色体个体的适应值越好被选择的概率就越大， 参加繁殖后代的机会就越多，它们的优秀基因被继承的也越多常用 的选择方法是按比例选择，即个体参加繁殖的概率与它的适应值成正 比近年来，又有许多学者提出了诸如基于排序的选择、锦标赛选择 等多种选择机制 1 0 遗传算法中新生代的产生是由变异、杂交和选择机制共同完成的 变异就是以一定的概率随机的改变染色体中的某个基因得到一个新 的个体，使得后者既保留了前者的大部分基因，又有不同于其父体的 地方，这为种群的进化创造了可能杂交分为单点、两点和均匀杂交， 杂交通过交换两条染色体的部分基因得到两个子个体杂交得到的子 个体往往具有更好的适应值 ( 3 ) 算法流程 4 高校教师积：职硕一k 学位论文 综上所述，遗传算法的一般流程可描述如下： g e n e r a t i o n = o s e e d9 0 p u l a t i o n w h i l en o tt e r m i n a t i o nc o n d i t i o nd o g e n e r a t i o n = g e n e r a t i o n + 1 c a l c u l a t ef i t n e s s s e l e c t i o n c r o s s o v e r ( p c ) m u t a t i o n ( p r o ) e n dw h i l e 1 2 3 遗传算法的理论背景 ( 1 ) 基本概念 优化问题的一般描述如下： r a i n c ( s ) s t s s 其中，s 是优化问题的可行解集，c 为目标函数，s 称为优化问题 的可行解 一般用r 表示基因型空间，基因型是对问题的解进行编码的数据 结构。简单的说基因型空间就是一个由这样的数据结构构成的集合。 在本文的讨论中我们均假定每一个基因型只能对一个问题的可行解 进行编码 与目标函数相关的一个概念是适应值函数： 演化计算的若干算法及其戊用研究 ，：f i o ，+ o ) 它一般通过某种转换函数f 作用在c 上得到即： ，( r ) 一f 【c ( 肘( r ) ) 】 这种转换一般要求满足下列条件： ，( ，) f ( k ) c ( m ( ，) c c ( m ( i ) ) ，v r ，k e f 种群是个体的集合，由于每个个体是一个基因型因此，种群也 有相应的基因型用r 表示所有与种群对应的基因型空间 ( 2 ) 主要理论 模式定理：一个模式是基因型空间的一个子集s e f ，表示为一个 长为l ，符号取自 0 ，1 ，爿c ) 的模板串其中木表示任意字符在基因空间 中有且只有3 f 个模式 9 可以证明：在遗传算子选择、杂交、变异的作用下，具有低阶、 短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指 数增长 这只是对遗传算法进行理论分析的工具之一，a d b e t h k e 应用 w a l s h 函数进行遗传算法的模式处理，并引入w a l s h 变换的概念，采用 w a l s h 函数的离散化形式有效地计算模式的平均适应度，从而对遗传 算法的优化过程的特征进行分析还可以用马氏随机过程对遗传算法 的收敛性进行分析 1 2 4 演化策略 ( 1 ) 演化策略 演化策略( e s ) 通过对实数编码的l 维函数参数优化来求解问题 高校教师在职硕i ：学位论文 在演化策略中，表现型空间是一个f 维的向量，而基因型空间则在该 向量，再加一个服从正态分布的扰动构成这个扰动以0 向量为期望， 其密度函数为： p 蜘辱掣。 其中c 一瓴) 是协方差矩阵 个体的适应值函数在演化策略中一般被转换成正数，有的时候还 可能加上一个随机噪声( 一个随个向量w ) ： ，( r ) - f c m ( r ) 】， 不妨将个体表示为r 一( 乙c ) ，演化策略的变异操作首先对c 进行一 个随机扰动，然后再根据c 对z 进行扰动： ，一0 ，c ) 其中 z - z + n ( o ，c ) n ( o ，c ) 表示一个服正太分布的随机向量，其期望为0 ，方差和协方差 矩阵为c 演化策略中还采用了多种杂交方法，例如多父体杂交就是其中的 一种，有的学者甚至在演化策略中一次让所有的父体都参与杂交过程 从而生成新个体 选择策略；演化策略采用了与其它演化算法不同的两类确定性选 择方法：( n ，m ) 选择和( n + m ) 选择( n ，m ) 选择从m 个子代个体( m ) n ) 保留1 3 个最好的作为下一代个体这m 个子代个体是由前一代的1 3 个父 演化计算的若干算法及其应用研究 代个体通过杂交、变异等遗传算子生成的在( 1 1 ，m ) 选择中，n 个父个 体被全部淘汰( n + m ) 选择从n 个父个体以及由它们生成的1 1 1 个子个体 中保留1 1 个最好的作为下一次迭代的种群这种选择始终保留着算法 到目前为止找到的最好解，即具有所谓的精英选择的功能它可以保 证演化以单调递增的方式进行但这种方法很难适应动态优化问题的 求解要求，当种群较小时，( n + m ) 也难于对策略参数进行演化目前， 常采用( t i ，m ) 选择，n 与m 的比例一般保持在1 7 左右 2 1 2 5 演化规划 演化规划的基本思想是利用有限状态自动机进行人工智能的研 究智能行为不仅表现在对环境的预测能力上，还表现为将预测转换 为对环境的自适应行为在计算理论中，环境可以描述一来自某一特 定集合的符号序列，这个集合称为输入字母表因此，人工智能的一 些问题可归结对输入符号进行预测，调整自身的行为从而获得某种意 义下的最优输出序列有限状态机便是完成这一工作的有力工具 一个有限状态机可表为一个五元组c q ，z ，口，珊，其中q 是内部 状态的集合，是输入字母表，z 是输出字母表o ：z x q q 是转换函 数：q z 是输出函数 演化规划的表现型空间一个有q 、和z 固定的所有有限状态自动 机构成的集合，这里的q 、和z q 、和z 由待求问题决定而基因型空 间则是由对有限状态自动机的转换与输出函数的描述构成的演化规 划的染色是一张f f z | l 的表格，表格中的每个单元都是一个有序对 高拨敦师在职硕j ：学位论文 心，砌，q e q ，a z 在演化规划的评估过程中，每次从输入序列中取一个符号，然后 将其输入到所有的有限状态自动机上，将各个自动机的输出与序列的 下一个符号比较，并按照一定的准则赋予该机一个的累积适应值，当 所有的输入序列都按照这种方法计算后，即可获得每个自动机的最终 适应值 新一代的自动机是由当前代的自动机通过变异生成的，这些变异 一般包括：替换某个输出符号、随机的替换状态转换函数的某个状态、 增加或减少一个内部状态等演化规划的选择策略与演化策略相似， 从n 个父代和n 个子代共2 n 个个体中选择出前n 个较好的个体作为下次 迭代的种群 d a v i db f o g e l 已经证明演化规划是依概率全局收敛的 1 ，3 演化计算的一些新进展 近年来，随着演化计算热潮的兴起，出现了一批新的计算方法与 技术，本节列举出了一些目前研究的热点算法 遗传程序设计( g e n e t i cp r o g r a m m i n g ) 机器学习的目标是只要告诉计算机去做什么，而不要求告诉计算 机怎么做。遗传程序设计( g e n e t i cp r o g r a m m i n g ) 便是在这个方面的 一次尝试目前，用遗传程序设计自动生成的程序已经能用来控制机 器人参加机器人足球比赛遗传程序设计也存在着许多尚待解决的问 题，如算法的正确性检验性问题没有解决前，遗传程序设计所自动生 演化计算的若千算注及其戍用研究 成的代码就难以得到验证。遗传程序设计还广泛的应用于自动数学建 模、硬件辅助设计等领域 8 基因表达程序设计 基因表达程序设计( g e n ee x p r e s s i o np r o g r a r 啪i n g 简记为 g e p ) 是由葡萄牙学者c a n d i d af e r r e i r a 在2 0 0 1 年提出的类似遗传程 序设计( g e n e t i cp r o g r a m i n g ) 的一种演化技术g e p 在短短的几年时 间内发展十分迅速，目前已广泛应用到符号化归( s y m b o l i c r e g r e s s i o n ) 、聚类分析、数据挖掘、时间序列推导、逻辑合成、参 数优化、神经网络设计、元细胞自动等众多领域。在这些领域的实验 结果表明g e p 往往要优于现今的大多数已有技术但由于g e p 提出的时 间不长，这种演化技术还不成熟，算法的运行开销大，收敛性也不稳 定 1 1 分布估计算法 p e d r ol a r r a n a g a 等人在研究遗传算法等传统的演化技术时 发现遗传算法中的参数本身就是一个优化问题，由此他们提出了分布 估计算法分布估计算法将种群的进化信息用概率图模型来存储，并 以概率图模型作为产生下一代种群的基础使得算法需要调整的参数 大量减少近年来，分布估计算法已经被应用到了函数优化、组合优 化、机器学习、数据挖掘等领域 1 量子进化算法 量子计算利用了量子理论中有关量子态的叠加、纠缠和干涉等特 性，通过量子并行计算有可能解决经典计算中的n p 问题量子计算以 高校救师在职硕t 学位论文 其独特的计算性能引起了广泛瞩目，迅速成为研究的热点n a r a y a n a n 和m a r k m o o r e 等人在1 9 9 6 年将量子多宇宙的概念引入遗传算法，提出 了量子衍生遗传算法( q u a n t u m - i n s p i r e dg e n e t i c a l g o r i t h m s ) 1 3 ， 并成功地用它解决了t s p 问题k u k h y u n h a n 等人在2 0 0 0 年提出了一 种遗传量子算法g q a ( g e n e t i c q u a n t u m a l g o r i t h m ) 2 ，他将量子的态 矢量表达引入遗传编码，后更名为q e a ( q u a n t u m i n s p i r e e v o l u t i o n a r y a l g o r i t h m ) 4 该算法最大的特点 是它的编码方式，能够用一个个体获得很好的结果。目前量子进化算 法已经应用数值计算、图形图象处理、c a i 、组合优化、通信、网络 服务质量( o o s ) 、信号处理( 滤波器设计) 等领域都有了发展但是 从实验结果表明o e a 目前还有很多缺点：适用于用二进制表示的问题、 收敛速度慢、容易陷入局部最优 2 群智能算法： 粒子群优化算法( p s o ) 最早是由美国的j a m e sk e n n e d y 和r u s s e l l e b e r h a r t 在1 9 9 5 年提出的它与其他计算智能的一个显著区别是所需 要调整的参数很少，算法本身简单、收敛快目前应用范围很广，主 要应用在：网络模型结构优化、多目标优化、自动目标检测、游戏训 练、信号处理、图象分割、分类等领域 蚁群算法( a c o ) 提出于1 9 9 2 年，由意大利d o r i g om ，m a n i e z z o v ，c o l o r n ia 等人提出，主要应用在：组合优化、网络路由优化、数 据挖掘等领域 演化计算的若干算法及其应用研究 1 1 1 4 本文的组织结构 论文第一章介绍了演化算法的起源、发展、现状及进展，第二章 简单介绍e d a 韵原理，并将互补机制引入到e d a 中第三章重着介绍了 g e p 的基本原理，并提出y g e p 的并行化框架最后，作者在第四章对 全文进行了总结 高校教师在职硕士学位论文 第二章松弛互补的分布估计算法解背包问题 2 1 引言 分布估计算法( e s t i m a t i o no fd i s t r i b u t i o na l g o r i t h m s ，简记 为e d a s ) 是演化计算内的一个全新领域在e d a sr 扣，既没有杂交也没有 变异算子e d a s 从父代种群中选出一部分个体作为样本点，然后根据 这些个体估计出种群的一个概率分布，最后对这个概率分布进行采样 或者模拟即可生成新一代的子种群根据概率模型和估计算法的不 同，e d a s 包含了u m d a 、p b i l 、c g a 、m i m i c 、c o m i t 、b m d a 、b o a 、e b n a 、 e c g a 、f d a 、l f d a 等多种算法本章将引入了互补机制的u m d a 应用到多 维背包问题的求解上 多维背包问题( m k p ) 又称为多维0 一i 背包问题( m k p 0 1 ) ，其描述 如下：给定n 个物品m 个背包，要求从这n 个物品里选择若干个出来， 使得从被选物品中获锝的总数最大，同时各物品的重量和又不超过背 包的容积该问题可形式化的描述为： m a x 删驴， ( 1 1 ) 满足： 荟勺并j s 魂( f 1 州 ( 1 2 ) 工，1 ( 1 3 ) 其中( 1 1 ) 是目标函数，( 1 2 ) 式中的每一个子式称为一个限制 条件令7 仉，胁 ，扎，n ，对所有的i e l ，6 f 之0 ，并且对所有的 7 ，j e j , r # 刈此外一个正确描述的背包问题还应该满足以下条件： 演化计算的若干算法及其应用研究 1 3 对所有的7 ，p 产o 且勺s 6 j s 荟勺，四月地肯上述任何条件将导致一 些x 固定为0 或者( 1 2 ) 中的限制条件被排除 可以看出经典背包问题只是m k p 问题当m = l 时的一个特例，m k p 是 一个n p 难问题工程应用中的许多问题如投资预算、货物装载、分布 式系统中处理器的分配等都可以被表述为多维背包问题因此，m k p 一直受到学者们的关注 与其它许多n p 难组合优化问题一样，对m k p 的求解存在着精确算 法与启发式算法两个方向已知的精确算法本质上都是 s h i h ，1 9 7 9 的分枝限界算法，这些算法的区别在于获得上下界的方法不同s h i h 首先分别求出m 个约束的线性松弛解，及对应的m 个目标函数，再将m 个目标函数中的最小值作为m p k 的一个上界g a v i s h 和p i r k u l 用 l a g r a n g e a n 或s u r r o g a t e 松弛解作为分析限界的上界精确算法一 般都具有指数级的时间复杂度，所以它们只能求解小规模的多维背包 问题 启发式算法主要用来求解大规模的m k p 的近似解贪婪算法按照 1 的贪婪准则每次向背包中增加一个物品，直到背包不能容纳任何 物品为止通过单纯形的方法求得m k p 的松弛解，在此基础上往往能找 到较好的近似甚至是精确解 o s o r i o ，2 0 0 d r e x l 用模拟退火算法( s a ) 求解m k p 也获得了较好的结果 d r e x l1 9 8 8 其它启发式算法包括：禁 忌搜索算法 g l o v e ra n dk o c h e n b e r g e r ，1 9 9 6 ：h a n a f ia n d f r e v ill e ，1 9 9 8 、遗传算法 c h ua n db e a sl e y ，1 9 9 8 、可变邻域搜 索算法 j a k o bp u c h i n g e ra n dr r a i d 、大规模邻域搜索算法 高校教师在职硕上学位论文 k a h u j aa n db c h u n h a 、混合搜索算法 m i c h e lv a s q u e za n d j i n k a oh a o 。2 0 0 1 这些算法都能求解较大规模的m k p f 匐题 本文章中我们提出了一种求解m k p 问题的分布估计算法，并得到 了较好的计算结果 2 2 分布估计算法 2 2 1 引言 遗传算法是一类基于选择与重组机制不断对候选解进行改进的 一类优化技术在遗传算法中不同候选解的集合称为种群，候选解有 时也称为个体或染色体每个个体都是问题解的一个编码个体中的 每个成分( 变量) 称为个体的一个基因遗传算法中，个体间通过选 择、重组、变异等操作交换信息这种信息的交换有助于将多个个体 中的部分优秀基因组合成一个适应值更好的个体一方面，遗传算法 的性能依赖于遗传算子的设计以及算法参数的设定，另一方面，许多 问题本身就是g a 难解问题从上一代一些较好的个体中估计出种群的 概率分布模型，通过对概率分布模型的采样得到下一代的新种群，这 就是e d a 的基本思想演化领域内首先提出e d a 思想的是m u h l e n b e i n 和p a a b ( 1 9 9 6 ) 2 2 2 基本概念 定义1 ：设x 。，以) 是一个n 维的随机向量，记五为x 的第i 个 随机变量的一个可能取值，y 。 ) t y 表示y x 的一个取值对x 的 广义联合概率分布( j o i n tg e n e r a l i a e dp r o b a b i l i t yd i s t r i b u t i o n ) 的一个图分解( g r a p h i c a lf a c t o r i z a t i o n ) 称为x 的一个概率图模型 演化计算的若千算法及其应用研究 1 5 记为p ( x - x ) 简l e a p ( x ) 一个概率图模型通常可表示为mi p ，s 是一个有向无环图 ( d a g ) ，它描述了置之间的条件依赖关系例如某随机向量的概率分 布可分解成如下概率图模型： p o 盼l = i p “i p a ( 1 4 ) 其中p i p 口；，只) 表示s 有向图中结点置的所有双亲结点取p 口j 的 条件下，置取薯的概率，护为参数 常见的概率图模型主要有两类：贝叶斯网络( b a y e s i a nn e t w o r k ) 和高斯网络( g a u s s i a nn e t w o r k s ) 贝叶斯网络主要用来表达离散随 机变量的分布情况，高斯网络主要用来表达连续型随机变量的分布情 况e d a s 中一般都是采用这两种模型 2 2 3 算法描述 e d a s 中主要包含两类数据结构，概率图模型s 和种群p 概率图模 型主要用来记忆问题变量的概率分布情况而种群p 的功能则是通过引 入竞争与演化机制不断的对s 进行修正s 是对上一代p 进行统计推断 的结果，而p 又是通过对本代s 进行随机模拟得到的 e d a s 的算法一般框架如下： e d a ( ) t = o 迭代次数 i n i t i a t e ( s ) w h i l e ( n o ts t o p ) t = t + l 只= s i m u l a t e ( s 一- ) s e l e c t ( 只) s = i n f e r e n c e ( c ) ) 其中s i m u l a t e ( ) 是对墨一t 进行随机的模拟， 面i n f e r e n c e ( ) 则 是从只推断出s 的数学模型s e l e c t ( ) 的主要作用是在p 中引入优胜 劣汰的竞争机制 2 3 松弛互补的分布估计算法 分布估计算法虽然有文献 1 中指出的诸多优点，但也还存在许 多有待进一步研究的地方例如，如何从现有种群只中有效的推断出 随机向量的概率图模m s , ，还没有十分有效的算法另外，文献 1 中的实验结果表明，分布估计算法的效率往往依赖于问题的概率图模 型s 本文正是从后者出发，对分布估计算法进行改进 2 3 1 互补机制 如上所述，由于分布估计算法的效率对概率图模型s 的依赖较 强，因此如果能够对概率图模型作一些改进必然会大大增加e d a s 的搜 索效率另一方面，互补是自然界中一种普遍存在的现象例如，生物 体的d n a 分子就是由两条互补的染色体构成的，有性生殖也是互补机 制的一种典型表现互补机制在演化计算领域内的研究最早可追溯到 g o l d b e r g 2 s h e n g x i a n gy a n g 和x i ny a o 8 等人在求解动态问题 的p b i l ( p o p u l a t i o n b a s e di n c r e m e n t a ll e a r n i n g ) 算法中也引入 演化计算的若干算法及其应用研究 1 7 了互补的机制，他们的实验表明互补的染色体表达，往往能增强算法 的鲁棒性为了在e d a s 中引入互补机制，我们首先提出随机向量互补 的概念，其定义如下： 定义2 ：设x - ( x 1 ，工：，以) 为一随机向量，岛( x ) ，见( x ) 为该随 机向量的两个概率图模型，若n ( x ) ，n o ) 满足关系一定的关系r ，则 称n ，戊为x 在关系r 下的一对互补概率图模型 可以看出s h e n g x i a n gy a n g 和x i ny a o 等人在文献 8 中提出 的d u a lp b i l 就是本节给出的互补概念的一个特例 2 3 2 松弛互补的概念 数学世界中的互补概念往往是对自然界中互补现象抽象的结果 然而需要指出的是自然界中的互补要求往往不如数学互补那样严格， 如果互补关系r 对互补的概率图模型岛，p 2 约束过于严格的话，势必 会限制e d a s 的搜索能力正如文献 8 所指出的那样互补机制的引入 大大增强了算法的鲁棒性，但同时也使得算法在搜索能力受到限制， 从而导致解的精度有所下降这正是互补关系r 对互补的染色体之间 约束过于严格的结果，基于上述分析，我们提出了松弛互补的的概念 定义3 给定随机变量x 及关系r ，若对任意的概率图模型n q 存 在唯一的概率图模型p z q 使得p l ，p 2 满足关系r ，则称r 为x 的一个 紧互补关系，n ，店为关系r 下的一对紧互补概率图模型否则称r 为x 的一个松弛互补关系，n ，岛为x 在r 下的一对松弛互补模型 2 3 3 松弛互补的分布估计算法 高投教师在职硕+ i + 学位论文 在提出了互补与松弛互补的概率图模型的基础上我们对e d a s 中 的概率图模型进行改进，随机向量的概率分布不再由单一的概率图模 型来记忆，而是由一对在一定关系r 下的一种松弛互补模型来储存。 这样既增强了算法的鲁棒性，又使得算法的搜索精度没有过大的损失 第5 节的实验结果也证实了算法的这些特点 改进后的分布估计算法的描述如下： r c e d a ( ) ( t = o i n i t i a t e ( 辞。酃) w h i l e ( n o ts t o p ) ( t = t + l c = s i m u l a t e ( 鞋- - ) s e l e c t ( 号) 霹：i n f e r e n c e ( 只) 牟：i n f e r e n c e ( 霉) ) ) 2 4 求解m k p 0 1 问题的分布估计算法 本章第1 节中已经指出目前已知的求解m k p 问题的启发式算法大 多先求得m k p 的松弛近似解，在此基础上再采用遗传算法或其它的智 能计算方法对松弛解做进一步的优化这主要涉及三个问题：松弛近 似解的获得、近似解到可行解的转化、演化或者迭代过程中如何充分 演化计算的若干算泣段其应用研究 1 9 利用近似解中的信息对搜索过程导向这些问题在参考文献中已经叙 述得比较清楚，本文不再赘述 2 4 1 求解m k p 问题的松弛互补概率图模型 文献 i o 中给出了f h m k p 的线性松弛解得到一个m k p 的整数解的 方法，设尸- ( 矿，矿) 为m k p 问题的线性松弛解而 一一“，t ，) 为该问题的一个可行的整数解，则由妒7 到z 7 转化过程 如下： f o r ( j = l ：j = n ：j 十+ ) i f ( 矿，q ) x ；：i i f ( 某个约束被违背) = 0 ) 其中弓是一个在 0 ，1 区间上服从均匀分布的随机数，这种方 法的实质是以线性松弛解作为背包被选择的概率然而，实际问题中 背包问题的最优整数解与线性松弛解之间往往存在很大的差别 2 因此，如果我们采用两个互补的概率图模型n ，以来共同决定物品是 否被选择必然会使算法在搜索的广度与精度之间取得很好的平衡其 中n 表示物品被选择的概率，物品是否被选择不再由 0 ，1 之间的均 匀分布的随机简单决定，而是由通过演化得到的n 来决定详细的选 择过程见下一小节 高校教师订：职硕j 。学位论文 2 4 2 求解m k p 问题的e d a s 的染色体编码 本文在求解m k p 问题时的染色体编码结构如下： 每个个体f h - - 部分组成： c 一吖，巧，) ，c 4 簖，c i d ，) ，c - 簖，e ，) 其中的f ( f1 1 ，厅) 【o ，1 】称为概率体，它表示物品i 被选择的概 率0 1 1 ，一) 【o ，1 】称为决定体，它最终决定物品i 是否被选 择一g1 1 ，n ) 0 ，1 称为选择体，它记录了物品i 的选择情况如果 01 1 表示物品i 被选入背包c r ，c 4 是分别对上一小节中概率图模型 n ，p 2 进行随机模拟得到的，反过来优良个体中的c r ，c 4 又通过统计 推断的方法产生下一代的概率图模型实际计算时我们对n ，p 2 采用 的都是u m d a 模型，由于文献 1 对该模型已经有较详细的讨论，本 文不再赘述具体的物品选择过程如下： f o r ( j = l ：j 一n ：j + + ) ( i f ( c j c ，) ( c l i f ( 某个约束被违背) c k o ) ) 2 4 3 其它问题 选择策略：为了验证互补机制的有效性，本文采用的是普通的辊 盘赌选择 适应值函数：出于同样的目的，本文采用了如下的适应值函数 演化计算的若干算法及其戍用研究 ，。著只一 ( 2 1 ) 算法流程：算法的流程与第3 节中的r c e d a 类似，在此略去 2 5 实验数据及结果分析 本文的工作环境为赛扬9 5 5 c p u ，5 1 2 m # j 存，操作系统为r e h l 4 0 u p d a t e 2 ，算法采用c + + 语言实现，用r h e l 自带的g c c 进行编译，未进行 任何的优化 实验的数据均来自于文献 3 ，对这些数据进行了两组实验，实 验一主要是为了验证r c e d a 的求精能力，在种群初始化之前，先利用 开源的l p _ s o l v e 求解各个问题的线性最优解，然后再利用文献 1 0 3 中的方法得到质量较高的初始种群实验- n 主要是为了验证算法的 鲁棒性，种群的初始化完全随机产生未利用任何的领域知识两组实 验的种群大小均为5 0 0 ，选取5 0 个最好的个体进行统计推断算法的终 止条件为找到目前已知的最好解或者演化代数大于1 0 0 每个问题分 别用。至, j l o o 作为随机数种子独立的求解1 0 0 次 2 5 1 实验结果 下面两表列出了实验一求解两组不同数据时的结果： 表一对k n a p l 5 ，k n a p 2 0 ，k n a p 2 8 ，i m a p 3 9 ，k n a p 5 0 求解时得到己知最好解的次数 己知最优 问题 m nr c e d ae d ag ah g a 解 k n a p l 5 1 0 1 54 0 1 51 0 02 08 31 0 0 k m a p 2 0 1 0 2 06 1 2 0 1 0 0 2 3 8 31 0 0 i z m a p 2 8 1 0 2 81 2 4 0 01 0 02 63 31 0 0 k n a p 3 9 5 x 3 91 0 6 1 81 0 01 747 5 k n a p s 0 5 5 01 6 5 3 7 1 0 0 9 1 9 9 表= 对s e n t o l - 6 0 ，s c t 0 2 - 6 0 , w e i n g t - 1 0 5 ，w e i n 9 8 1 0 5 求解时得到己知最好解的次数 已知最优 问题 m nr c e d ae d ag ah g a 解 s e n t 0 13 0 x 6 0 7 2 7 21 0 01 551 0 0 s e m 0 23 0 6 08 7 2 21 加 1 32 9 7 w c i n 9 7 2 1 0 51 0 9 5 4 4 51 0 089 9 w e i n 9 8 2 1 0 5 6 2 4 3 1 9 1 0 0 56 9 8 表中r c e d a 和e d a 列的数据均来自于实算，而g a 和h g a 列的数据 则直接取自于文献 9 下表给出了实验二的计算结果，这组实验中初始种群均随机生成 表出分别给出了用r c e d a 和e d a 求解上述问题时获得的最优结果的1 0 0 次平均值( a v gy o ) 和获得目前已知最好解的次数( b e s t 列) 表三鲁棒性对比实验结果 问题a b e s 爿p 玩c b e s t r c e d a s e n t 0 17 6 5 3 2 2 7 7 7 1 5 9 5 s e n t 0 28 5 8 2 338 7 2 0 99 3 w e i n 9 7 ； 9 9 3 6 6 2 721 0 9 5 4 2 2 69 0 w c i n 9 8 6 0 0 4 2 7 6l6 2 4 3 1 6 88 0 k n a p l 5 3 9 8 7 ，346 1 1 7 9 9 5 k n a p 2 0 5 9 9 2 431 2 3 8 9 49 7 k n a p 3 9 1 5 3 2 8 3 21 0 6 1 5 39 5 k n a p 2 8 1 6 4 3 2 8 2 1 6 5 3 6 7 9 8 2 5 2 实验分析 从表一和表二可以看出r c e d a 的求解能力要明显强于标准的e d a 和其它演化方法相比，表二的实验结果表明，标准e d a 受初始种群的 影响较大，而r c e d a 基本上不受初始种群的影响具有较强的鲁棒性 演化 十算的若干舅泣及其麻用研究 2 6 结语 文章首次将自然界的互补机制引入到分布估计算法中，并提出了 一种全新的互补机制一松弛互补的机制。并将这种机制引入到了对 m k p 问题的求解算法，得到了较好的结果应当指出的是本文的算法在 求解大规模m k p 时与目前已知的最好算法( h y b r i da p p r o a c h 文献 2 ) 还是存在一定的差距主要是因为r c e d a 并未引入任何局部搜索 的算子，这也是作者今后研究的方向同时，本文提出的松弛互补算 法在理论的分析与证明上还有待进一步研究 高校教师在职硕士学位论文 第三章基于m pi 的并行g e p 算法 3 1 引言 基因表达编程( g e n ee x p r e s s i o np r o g r a m m i n g ，简记为g e p ) 是由 葡萄牙的c a n d i d af e r r e i r 于2 0 0 1 年提出的基因程序设计( g e n e t i c p r o g r a m m i n g ) 中的表达树( e t ) 在g e p 被编码成了由多个域组成的线 性结构，实现了表现型与基因型之间的转换在g e p 中还引入了一些搜 索能力极强的基因操作算子，使得g e p 在解某些问题