（管理科学与工程专业论文）基于遗传算法的混合学习和集成学习研究.pdf

中文摘要中文捅要 智能学习领域中，混合智能学习是目前研究的热点，倍受人们的关注。目 前这方面的研究已经取得了很多成果并得到了广泛应用。对于复杂系统，已经 推广到应用三种智能技术或更多混合来进行求解。此外，集成学习这一新提出 的学习思想，由于学习应用效果明显，引起了国内外广大学者的兴趣。本文正 是围绕这两种学习思想进行了一系列的研究。 本文基于混合学习和集成学习的思想，将两种学习理论应用于遗传算法， 分别来解决组合优化问题、遗传算法参数选择问题；基于遗传算法对集成学习 权重进行优化。 本文的主要工作包括： ( 1 ) 受混合学习的思想启发，提出了基于单亲遗传算法和模拟退火的混合优化算 法。针对单亲遗传算法解决序号编码问题提出了一种新的编码方案，大大避免 了不可行解的出现，缩小了搜索空间；同时在单亲遗传算法中加入了模拟退火 思想，增强了遗传算法的局部搜索能力，解决遗传算法群体退化的问题；最后， 对于一个物流运输过程中的车辆路径问题进行了仿真实验，验证了该算法的有 效性。 ( 2 ) 针对遗传算法参数难于选择的问题，我们将集成学习思想应用于求解遗传算 法的参数选择问题。本文主要是将不同的交叉概率、变异概率组合，形成不同 的遗传算法，最后将单个算法的预测准确度作为学习权重来进行集成。最后， 在u c i 数据库上进行了仿真实验。特别地通过对带噪声数据的模拟分类实验说 明了遗传算法在分类问题中的高预测准确度：并给出了一个度量算法差异性的 概率指标，通过该指标的分析，可以得出单个遗传算法之间差异性很小等特征。 ( 3 ) 对于集成学习的代表性算法b o o s t i n g 、b a g g i n g 进行了研究，并通过将两种 算法应用于神经网络对其有效性进行了验证。同时，为了进一步提高集成学习 的性能，我们在神经网络集成学习中引入了基于遗传算法的权重优化混合方法， 对神经网络集成学习的权重进行进化调整，以提高集成学习的预测精度。最后 在u c i 数据库上进行了仿真实验，验证了本方法的有效性。 关键词：混合学习集成学习单亲遗传算法模拟退火神经网络 b o o s t i n g & b a g g i n g a b st r a c t i nt h ef i e l do fi n t e l l i g e n c el e a r n i n g ，h y b r i di n t e l l i g e n c el e a r n i n gh a sb e e n t h er e s e a r c hh o tr e c e n t l y e n c o u r a g i n ga c h i e v e m e n t sa n de x t e n s i v ea p p l i c a t i o n s h a v eb e e nm a d ei nm a n yf i e l d s h y b r i dm e t h o d sw h i c hc o m b i n et h r e eo rm o r e i n t e l l i g e n c et e c h n o l o g i e s a r e d e v e l o p e d t os o l v et h e p r o b l e m s o f c o m p l e x s y s t e m s s i m u l t a n e o u s l y , a n o t h e rl e a r n i n gm e t h o d e n s e m b l el e a r n i n g ，w h i c h h a so b t a i n e dg o o dp r e d i c t i v er e s u l t si na p p l i c a t i o n ，d r a w sm o r ea t t e n t i o n t h i s p a p e rh a sf i n i s h e ds o m e r e s e a r c hw o r ka n de x p e r i m e n t sw i t ht h ea i do ft h et w o m e t h o d s 1 y b r i dl e a r n i n ga n d e n s e m b l e l e a r n i n g ， b a s e do nt h e s t u d y o f h y b r i dl e a r n i n g a n de n s e m b l e l e a r n i n g ，t w o a l g o r i t h m sh a v eb e e nd e v e l o p e dt o s o l v et h ec o m b i n e do p t i m i z a t i o np r o b l e m a n dt h ep a r a m e t e r s c h o o s i n gp r o b l e mr e s p e c t i v e l y a n d t h i sp a p e rh a se m p l o y e d t h e g e n e t i ca l g o r i t h m s t oe v o l v et h ew e i g h t so fe n s e m b l el e a r n i n g s o a st o i m p r o v et h ee f f i c i e n c yo f e n s e m b l el e a r n i n g t h em a i nw o r ko ft h i sp a p e ri s ： ( 1 ) b a s e d o n h y b r i dl e a r n i n g ，ah y b r i da l g o r i t h m w h i c hc o m b i n e st h e p a r t h e n o g e n e t i ca l g o r i t h m a n ds i m u l a t e d a n n e a l i n ga l g o r i t h m h a sb e e n d e v e l o p e dt os o l v et h ec o m b i n e do p t i m i z a t i o np r o b l e m t h es i m u l a t i n gr e s u l t s o ft h ev e h i c l e r o u t i n gp r o b l e m h a v e p r o v e d t h e e f f i c i e n c y o ft h e h y b r i d a l g o r i t h m ( 2 ) i no r d e r t od e a lw i t ht h e p a r a m e t r i c c h o o s i n gp r o b l e m ，m a n yg e n e t i c a l g o r i t h m s w i t hd i f f e r e n tc r o s s o v e ra n d m u t a t i o n p r o b a b i l i t i e s h a v e b e e n e m p l o y e d t oc o n s t r u c te n s e m b l ea l g o r i t h mg a e a n a l y s i so f t h el e a r n i n gr e s u l t s h a sa l s og i v e ni nt h ep a p e r ( 3 ) b o o s t i n ga n db a g g i n gw h i c ha r et h er e p r e s e n t a t i v ea l g o r i t h m so f e n s e m b l e l e a r n i n gh a v eb e e na p p l i e d t on e u r a ln e t w o r k ，a n de n c o u r a g i n gr e s u l t sh a v eb e e n o b t a i n e d t h i sp a p e ra l s ou s e sg e n e t i ca l g o r i t h mt oa d j u s tt h ew e i g h t so fs i n g l e a l g o r i t h m s i ne n s e m b l el e a r n i n g ，s i m u l a t i o nh a sb e e nm a d eb a s e do n u c i d a t a b a s es e t k e yw o r d s ：h y b r i dl e a r n i n g ，e n s e m b l el e a r n i n g ，p a r t h e n o g e n e t i ca l g o r i t h m s i m u l a t e da n n e a l i n g n e u r a ln e t w o r k ，b o o s t i n g & b a g g i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得鑫洼叁鲎或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示了谢意。 学位论文作者签名：司嚷t 坤签字日期： 年月日 学位论文版权使用授权书 本学位论文作者完全了解鑫生盘堂有关保留、使用学位论文的规定。 特授权墨洼盘茔可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：卿晚坤 导师签名：套硼 签字日期：年月日签字日期：年月 日 第一章绪论 1 1 研究背景 第一章绪论 智能学习计算就是人类受自然界( 生物界) 规律的启迪，根据其原理，设 计求解问题的学习算法。从8 0 年代末以来，发展非常快。目前这方面的研究成 果也很多，如人工神经网络技术、遗传算法、进化规划、模拟退火技术和群集 智能技术等。近几年来，混合智能技术又成为研究热点。混合智能技术集成各 个单个智能算法的优势，对问题进行模拟表示、推理和求解。这种“混合”求 解问题的能力就称之为混合智能。目前在研究“混合”求解的方法中，有串行 混合，即一个智能算法作为另一个智能算法的前序预处理过程或者后处理过程； 还有就是一种智能算法集成在另一种智能算法计算过程中，如模糊逻辑集成在 神经网络的输入层上等等。目前这方面的研究已经取得了很多成果并得到了广 泛应用。对于复杂系统，已经推广到三种智能技术或更多混合来进行求解。 同时，在智能学习领域，另一种学习方法，“集成学习”的研究，日渐受到 学者们的关注，相应的各种集成方法也应运而生。许多研究者在应用研究中发 现多个算法集成可以取得比单个学习算法更好的效果。集成学习就是通过将多 个算法学习的结果以某种方式集成，来提高预测的准确度。而且与单个算法相 比，集成学习不容易出现过适应的现象。虽然集成学习的构成方式有很多，但 是目前对于集成学习方法的研究主要集中在通过改变样本结构来学习的方式， 比如b o o s t i n g 和b a g g i n g 算法就是通过改变学习样本进行集成学习的代表性算 法。这两种算法分别由s c h a p i r e 【1 】和b r e i m a n 2 1 提出的，是目前应用比较广泛的 算法。集成学习在实际应用中确实能够取得很好的结果，但是集成算法能够比 单个算法有效的理论和实验解释仍然是目前研究的重点。 本文从混合学习和集成学习思想出发，研究了应用于具体问题的混合学习 算法和集成学习算法。首先是提出一种基于单亲遗传算法和模拟退火相结合的 混合算法，该算法利用单亲遗传算法的全局搜索策略和适于解决序号编码问题 的特点，结合模拟退火的局部微调技术成功解决了物流运输过程中的一个车辆 配载问题，实验模拟结果优于单个算法得到的结果；其次是总结了集成学习算 法的概念、构成方式和作用，探讨了不同参数设置下的遗传算法集成学习方法； 还深入分析了b o o s t i n g 和b a g g i n g 算法的理论思想，并提出了在b o o s t i n g 和 b a g g i n g 算法中引入遗传算法的思想，对集成学习的权重进行进化调整，通过 第一章绪论 实验模拟的方式对b o o s t i n g 、b a g g i n g 以及引入遗传算法的g e n e t i c b o o s t i n g 和 g e n e t i c b a g g i n g 进行了验证比较。这些探讨对混合学习和集成学习领域将具有 很大的理论意义和实用价值。 1 2 当前国内外研究现状 1 2 1 混合遗传算法的发展及研究现状 遗传算法是借鉴生物界自然选择和进化机制发展起来的一种高度并行、随 机、自适应搜索算法。由于遗传算法具有操作简单、易于实现、强搜索能力等 优点，遗传算法的应用不断扩大到诸如函数优化、自动控制、机器学习、图像 处理和模式识别、生产调度、人工生命等领域。 目前遗传算法和其他算法进行整合的研究，已经出现很多成果。如：国际 上，r u e y s h u nc h e n 等【3 】在遗传算法中加入了s e l f - t u n i n g 方法，用来提高染色 体模式的有效性。通过这种混合算法可以有效的解决多目标的装配计划问题， 提高解的质量，缩短计算时间。t h o m a s 等【4 】用遗传算法和粗糙集构成混合模型， 来对破产问题进行预测，同时指出遗传算法与粗糙集相比不能明确的指出数据 之间的关系，而粗糙集准确度没有遗传算法高，二者结合能发挥各自的优势， 形成有效的模型。m hf a t e m i n 【5 】将遗传算法和神经网络结合，对预测生物密 度因子问题进行了研究。而国内，李守智等【6 1 提出了遗传退火算法，在遗传算 法的局部加入模拟退火算法，利用模拟退火局部搜索能力强的特点，解决了遗 传算法中种群退化的问题。何仁芳等【7 】提出了混沌遗传算法，结合了混沌现象 的遍历性和遗传算法的反演性，在图像模型匹配方面取得了很好的效果。刘晓 霞【8 】在遗传算法中引入分枝定界算法保持对优化解有贡献的工件部分顺序，求 解三机f l o w - s h o p 调度问题，并通过大量的实验数据验证了遗传分枝定界算法 的有效性。乔建忠等【9 为了求解在实际工作中所建立的基于智能制造的生产计 划模型，提出了遗传算法和单纯形法相结合的混合算法。用遗传算法的染色体 来代表一个线性规划模型，然后用单纯形法对线性规划模型求解，简化了求解 的复杂性。同时通过实例验证，基于遗传算法和单纯形法的混合算法是解决该 类问题的一个有效的方法。 在用遗传算法求解组合优化问题的时候，采用序号编码比非序号编码更简 单、更直接。但对于序号编码的染色体，不能像非序号编码的染色体一样可以 在两条染色体的任意位置进行交叉( 因为序号编码的染色体中的每个基因都是 一个事物序号，随意交叉后的个体可能不再代表原问题的一个解) ，而必须使用 p m x 、o x 、c x 等特殊的交叉算子，这些交叉算子操作起来很不方便。针对这 2 第一章绪论 个问题，李茂军、童调生等【lo 】提出了一种不用交叉算子的特殊遗传算法。该算 法通过一条染色体中基因的换位操作来实现传统遗传算法中两条染色体之间基 因的交叉操作功，能，即通过单个个体繁殖后代，因此称之为单亲遗传算法 ( p a r t h e n o - g e n e t i c a l g o r i t h m ，简称为p g a ) 。李、童二人从编码、遗传算子、 运行机理、全局收敛性、计算效率等多个角度对单亲遗传算法进行了分析，并 且通过列车占线问题、f l o w - s h o p 问题验证了单亲遗传算法的有效性。 最早李茂军、童调生等人将单亲遗传算法应用于旅行商问题 1 o 】( t r a v e l l i n g s a l e s m a np r o b l e m ) 以及f l o w s h o p 调度问题l 】，证明了单亲遗传算法操作简 单，不要求初始群体具有广泛的多样性，不易陷入早熟收敛。随后，肖鹏、李 茂军等【l2 】在物流配送系统中也使用了单亲遗传算法，验证了单亲遗传算法在解 决优化问题上比传统的遗传算法方便、有效，同时指出单亲遗传算法在物流配 送系统等组合优化问题上极具潜力。方宝铬、徐汉忠【l 卅在复杂的有窗口式交货 期的多机加工排序问题中也做了相应的应用研究，指出单亲遗传算法计算复杂 性是易于接受的( 也就是具有可计算性) 。 1 2 2 集成学习的发展和研究现状 最早的集成学习方法是b a y e s i a n a v e r a g i n g 。在此之后，集成学习算法的研 究逐渐引起了人们的关注。到目前为止主要的集成方法有| - e r r o r c o r r e c t i n go u t p u t c o d i n g 、b o o s t i n g 、b a g g i n g 。其中最主要的、研究最多的是b o o s t i n g 和b a g g i n g 。 这两种方法都是通过改变训练样本来构造集成学习算法，但是两种方法各有不 同的理论框架。在后续的章节中我们会详细介绍。 k e a m s 和v a l i a n t 1 4 , 1 5 1 在提出了强学习和弱学习的概念之后，遗留下了强学 习和弱学习是否等价的问题。为了回答这个问题s c h a p i r e 提出了一个构造性 的过程，这个构造性的过程就是b o o s t i n g 算法的雏形。此后，f r e u n d i i 6 在1 9 9 1 年又提出了更有效的“b o o m b y m a j o r i t y ”算法。但是这两个算法都存在着一个 重大的缺陷，就是必须知道学习算法正确率的下限，这在实际中很难做到。在 1 9 9 5 年，f r e u n d 和s c h a p i r e i ”1 提出了a d a b o o s t 算法，该算法的效率和 “b o o s t b y m a j o r i t y ”算法的效率几乎一样，却可以非常容易的应用到实际的问 题中去。而且他们还提出了这个算法的扩展形式，用来解决分类问题和回归问 题。a d a b o o s t 算法最后结果的准确度依赖于弱学习返回的所有假设，而不是只 依赖于准确率最低的那个假设，因此可以全面开发弱学习的能力。在1 9 9 6 年， b r e i m a n 2 】提出了与b o o s t i n g 相似的技术，b a g g i n g 。b r e i m a n 2 1 强调学习算法的 稳定性对于最后的结果有很大的影响。对于不稳定的算法，如神经网络、决策 树，能提高预测的准确度。但是对稳定的学习算法效果不明显，有时甚至会降 第一章绪论 低预测准确度。 在提出这些集成算法的同时，人们也在寻求理论解释。f r e u n d 和s c h a p i r e 1 7 】 从训练误差和泛化误差的角度分析了b o o s t i n g 算法；b r e i m a n 2 1 从偏差和误差的 角度分析了b a g g i n g 的泛化误差；f r e u n d 和s c h a p i r e 等人【8 】也提出了m a r g i n 的概念来分析集成学习算法。 到目前为止，集成学习在多方面已经有所应用。e i j it a k i m o t o 掣1 9 】指出目 前的大多b o o s t i n g 算法局限于解决二分类问题，要解决多分类问题时需要将多 分类问题转换为二分类，过程比较繁琐。因此，他们提出了一种解决多分类问 题的b o o s t i n g 算法，并且应用于决策树，结果与a d a b o o s t 相比较差。在文章 的小结中，他们对失败的原因进行了分析。g r e 9 1 2 0 将b o o s t i n g 和b a g g i n g 用于 估计有噪声、高维数据的密度，并通过一些数据集合进行了仿真试验。s i m o n e 等1 2 l l 将b o o s t i n g 和b a g g i n g 应用于回归问题，旨在通过仿真实验来研究使用非 参数回归方法做预测，什么时候b o o s t i n g 和b a g g i n g 能够有效的减小训练误差 和泛化误差。t o r s t e n 等【2 2 】将b a g g i n g 用于树分类器，提出了一种b a g g e d - c t r e e 算法，用来解决医学当中激光扫描图像问题，并通过实验证明了该算法的有效 性。刁力力等人【2 3 用b o o s t i n g 算法应用于简单决策树s t u m p s 来进行文本分类， 取得了较好的效果，并且指出问题规模越大，学习效果越明显。 1 3 本文主要的研究内容 本文从混合学习算法和集成学习算法的角度出发，研究了基于单亲遗传算 法和模拟退火相结合的混合算法、基于集成学习思想的遗传算法参数调节算法、 基于遗传算法的b o o s t i n g 和b a g g i n g 集成权值优化混合方法等问题。这些学习 方法是对目前混合学习思想及集成学习思想在具体情况下解决具体问题的一种 有益探索，相信这些探索结果对混合学习和集成学习领域将具有很大的理论意 义和实用价值。 具体的研究内容如下： ( 1 ) 第一章中，对本文研究的工作背景进行了阐述；同时简单介绍了目前国内 外关于混合算法和集成学习算法的研究现状；最后给出了本文的主要工作。 ( 2 ) 基于研究生期间阅读的大量文献，在第二章中我们详尽的给出了本文工作 中进行研究探讨的理论基础，包括：构成混合算法的单亲遗传和模拟退火的算 法机制，集成学习算法的概念、构成方法、作用以及b a g g i n g 、b o o s t i n g 算法 的提出和发展情况等，总结了最近研究者对于两种算法的理论分析及其在分类 问题和回归问题上的应用。 ( 3 ) 在单亲遗传算法中加入模拟退火，增强遗传算法的局部搜索能力，解决遗 4 第一章绪论 传算法群体退化的问题是我们在第三章的主要内容。本文针对p g a 解决序号编 码问题提出了一种新的编码方案，避免了不可行解的出现，缩小了搜索空间。 最后，针对车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，简称v r p ) ，进行了仿真 实验并和其它方法进行了比较，得出本文方法是解决车辆路径问题的一种优选 方案。 ( 4 ) 在第四章中我们基于集成学习的思想，提出了一种遗传算法参数调节的集 成学习算法。该方法旨在解决实际应用中遗传算法参数难于选择的问题。本文 主要针对的是交叉概率和变异概率的选择问题。通过两种参数的不同组合，构 成多个相互独立的遗传算法，以单个遗传算法的准确度作为最后的权重，来进 行集成学习。在第四章的最后模拟实验中，我们通过u c i 数据库中i r i s 和 b a l a n c es c a l e 两个数据集合对遗传算法集成学习进行了仿真实验，同时 对结果进行了分析。 ( 5 ) 目前研究最多的集成学习算法就是b o o s t i n g 和b a g g i n g ，在第五章中我们 给出了b o o s t i n g 和b a g g i n g 算法的伪码形式。在研究文献的基础上，提出一种 基于集成技术和混合技术相结合的学习思想。整体采用基于神经网络的集成学 习，然后把遗传算法混合子集成学习中，即将集成学习最后的权重作为遗传算 法的初始群体，对于最后的权重进行调整，以便通过进化，将集成学习的准确 度进行提高。最后，通过u c i 数据库的仿真实验，我们对单个的神经网络、 n e t w o r k b o o s t i n g 、n e t w o r k b a g g i n g 及在b o o s t i n g 和b a g g i n g 算法中加入遗传算 法等方法进行了分析比较。 ( 6 ) 最后，我们对本文所做的研究工作进行了总结，同时提出了存在的问题和 未来的研究方向。 第二章混合算法及集成学习的理论基础 第二章混合算法及集成学习的理论基础 2 1 混合学习算法的理论基础 单个学习算法在解决问题的时候，总会出现收敛速度慢、全局搜索或者局 部搜索能力弱等自身难以克服的缺陷。为了解决上述问题，混合学习算法应运 而生，它通过将不同的算法结合，彼此优势互补来取得比单个学习算法更好的 学习效果。 在第三章中，我们提出一种基于单亲遗传算法( p a r t h e n o g e n e t i c a l g o r i t h m ， 简称p g a ) 和模拟退火( s i m u l a t e da n n e a l i n ga l g o r i t h m ，简称s a ) 相结合的 混合算法，并把该算法应用于车辆路径问题( v r p ) 。下面我们将单亲遗传算 法和模拟退火的机制分别简述如下： 2 1 1 单亲遗传算法机制 针对序号编码的优化组合问题，李茂军、童调生等1 0 l 提出了一种不用交叉 算子的特殊遗传算法。这种遗传算法仅通过单个个体繁殖后代，故称之为单亲 遗传算法。与传统的遗传算法( t r a d i t i o n a lg e n e t i c a l g o r i t h m ，简称t g a ) 相比， 取消了交叉算子，操作更为简单，而且不需要群体具有多样性，对于“早熟收 敛”问题也有一定的缓解。 2 1 1 1 单亲遗传算法的运行机理“1 在传统的遗传算法中，通过选择、交叉和变异等遗传算子的作用，使种群 的平均适应度值越来越高，最后找到最优解。在此过程中，交叉算子对种群的 进化起着决定性的作用。但是在单亲遗传算法中，为了遗传操作方便，取消了 两条染色体之间基因的交叉操作。那么，单亲遗传算法是如何确保种群朝好的 方向进化的昵? 实际上，单亲遗传算法的基因换位算子隐含了序号编码的传统遗传算法中 两条染色体之间基因的交叉操作。因此，单亲遗传算法就能像传统的遗传算法 一样确保种群朝好的方向进化。下面以传统遗传算法中的c x 算子【2 5 】为例说明 单亲遗传算法是如何隐含了交叉操作功能的。 在t g a 的c x 算子中，对于交叉的两个个体爿、b ，随机取位置r ，从位 6 第二章混合算法及集成学习的理论基础 置- 开始在彳、艿两位串上交替寻找相同的值，直到返回位置r 。例如对表中爿， b 取n = 3 ，即从染色体b 中基因为3 的位置开始，相应位置染色体a 的基因值 为2 ；再在染色体口中寻找值为2 的基因，找到以后，看相应位置的染色体一的 基因值是否等于所选的初始值3 ，如不相等，再重复上述过程，直到在染色体a 中找到值为3 的基因。然后将相应位置的基因互换，生成两个新串，详细过程 如表2 1 所示。 表2 - 1c x 算子的操作实例 a 9 $ ；t 74506 3 b 。2 + 7 仁3 亍二5 6 亭名下0 丑l 4r 89 ， 一82 一一一一0 3 占，一 23 一一一一80 彳 l8z 4567093 占923 1 74s8 60 在表2 1 中，通过c x 算子，使a 变为4 ，b 变为，相同的功能可以通 过单亲遗传算法的基因换位算子实现，如表2 2 所示。 表2 - 2 用p g a 的基因换位算子实现t g a 的c x 算子的功能 a 982l 745063 + 182 ； 5 o63 - ( _ 。l 8 24597063 。 + 省 l824567o6 3 丑 234567 8 i o + 。 l 马 923 ； 6 i 8 o ( b 92317 58 。 f92 3l745860 具体过程以表2 2 中a a 的变换过程为例进行说明。首先，我们从两个 染色体的第一位基因开始比较，爿的第一位基因为9 ，a 的第一位基因为1 ， 在爿中找到值为l 的基因，即第四位基因，将第一位基因与第四位互换，使得 第二章混合算法及集成学习的理论基础 第一位基因与中相同。依次再找与不相同的基因，重复上述步骤。直至爿 完全变换成a 。 2 1 1 2 单亲遗传算法的遗传算子“4 1 单亲遗传算法使用选择、基因换位、基因移位等遗传算子繁殖后代。 选择是从旧群体中选取适应性强的个体组成新群体的过程。选择反映自然 界适者生存的原则。单亲遗传算法的选择算子与传统遗传算法的相同。 定义1p g a 的基因换位算子是按一定的概率p 。交换条染色体中某些位置上 的基因的过程，被交换基因的位置是随机的。 基因换位可分为单点换位和多点换位。单点换位是一次只交换一对( 两个) 基因的位置；多点换位是对预先给定的正整数虬，取随机数f ( 1 s f “。) 一次交 换j 对基因。 定义2p g a 中的基因移位算子是按一定的概率p ，把条染色体中的一些子串 中的基因依次往后移位，并把该子串的最后一个基因移位到最前面的位置，在 一条染色体中进行基因移位的予串及其长度是随机选取的。 基因移位可分为单点移位和多点移位。单点移位是在一条染色体中只取一 个子串作基因移位操作；而多点移位是对预先给定的正整数“。，先取随机数 j 0 ，“。) ，然后在一条染色体中取，个子串作基因移位操作。 p g a 的基因移位算子在操作时也可使子串中的基因依次向前移动。 定义3p g a 中的基因倒位算子是按一定的概率p ，把一条染色体中的一些子串 中的基因依次倒位，在一条染色体中进行基因倒位的子串及其长度是随机选取 的。 基因倒位可分为单点倒位和多点倒位。单点倒位是在一条染色体中只取一 个子串作基因倒位操作；而多点倒位是对预先给定的正整数“，先取随机数 j ( 1s 2 。我们可以将这k 个分类简化为2 个分类a 、b ，也 就是我们输出结果为a 或者b 。然后再对a ( 或者b ) 中的实例进行进一步的 分类，直到最终得到了我们所要的足分类的分类结果。这种方法很适合解决多 分类问题。与多分类问题相比，二分类问题比较容易解决，通过改变输出变量 集，将多分类问题转换为二分类问题，问题就容易解决了。 4 、算法参数的改变 对于许多算法如神经网络、遗传算法来说，在算法应用的开始首先要解决 的就是要选择算法参数。而且，由于这些算法操作过程的解释性很差，对于算 法参数的选择没有确定的规则可依。在实际应用中，就需要操作者根据自己的 经验进行选择。在这样的情况下，不同的参数选择，最终的结果可能会有很大 的区别，具有很大的不稳定性。我们可以对采取不同参数的算法进行集成，这 样一方面可以提高稳定性，另一方面也避免了人为选择参数可能产生的误差。 l o 第二章混合算法及集成学习的理论基础 2 ，2 3 集成学习舫作用 集成学习主要用来解决以下的问题： 1 、过适应问题 在对已知的数据集合进行学习的时候，我们常常选择适应度值最好的一个 模型作为最后的结果。也许我们选择的模型能够很好的解释训练数据集合，但 是却不能很好的解释测试数据或者其他数据，也就是说这个模型过于精细的刻 画了训练数据，对于测试数据或者其他新的数据泛化能力不强，这种现象就称 为过适应。 为了解决过适应问题，按照集成学习的思想，可以选择多个模型作为结果， 对于每个模型赋予相应的权重，从而集合生成合适的结果，提高泛化能力。 2 、参数选择问题 对于一些算法而言，如神经网络、遗传算法，在解决实际问题的时候，需 要选择操作参数。但是这些操作参数的选取没有确定往的规则可以依据，只能 凭借经验来选取，对于非专业的一般操作人员会有一定的难度。而且参数选择 不同，结果会有很大的差异。通过建立多个不同操作参数的模型，可以解决选 取参数的难题，同时将不同模型的结果按照一定的方式集成就可以生成我们想 要的结果。 3 、提高预测结果的稳定性 有些算法单一的预测结果时好时坏，不具有稳定性，不能一直保持高精度 的预测。就拿全球气候预测系统来说，对于某一个地区，一个模型对于某一个 季节的气候可能预测的很好。但是，对于该地区的另外一个季节，可能别的模 型会预测的比较好。通过模型的集成，可以在全球范围内以较高的概率普遍取 得很好的结果。 2 3b o o s t i n g 和b a g g in g 的理论基础 2 3 1b o o s t in g 算法的提出 自从v a l i a n t 3 1 1 可学习性的文章发表以来，许多研究集中在了p a c 学习模 型上。在p a c 学习模型中，学习者试图基于随机选择的概念实例来识别一个未 知概念。学习者的任务是发现预测规则，可以将新的例子正确地划分为概念的 正例或者反例。该假设必须以很高的概率对除- - + 部分以外的所有实例判断正 确。 k e a r n s 和v a l i a n t t 4 , 1 5 1 指出，在p a c 学习模型中，如果存在一个多项式级算 第二章混合算法及集成学习的理论基础 法，这个算法对集合中所有的概念在高置信度下只发生很小的错误，那么这个 概念集合就是可学习的( 强学习) 。而弱学习的概念是由k e a r n s 和v a l i a n t 1 4 , 1 5 ( 1 9 8 8 ；1 9 8 9 ) 引入的，对于一个弱学习模型，它降低了学习者能够取得随机 高准确度的要求，一个弱学习算法只需要提出一个比随机猜测性能略好的假设 即可。但他们留下一个问题，即强学习是否与弱学习等价的问题。如果两者等 价，那么在学习概念时，只需找到一个比随机猜测略好的弱学习算法，就可以 将其提升为强学习算法，而不必直接去找通常情况下很难获得的强学习算法。 因为表明两个概念等价需要一个方法对弱学习算法假设的低准确度进行提升， 这个问题也被称为假设提升问题。 1 9 9 0 年，s c h a p i r e l l 通过个构造性过程对上述的等价性问题做出了肯定 性的回答，证明了强学习和弱学习的等价性。这个构造性过程给出一个精确的 方法，它可以直接将弱学习算法转化为可以得到较高准确度的强学习算法。构 造过程使用过滤取样来修改实例分布，以这样一种方式迫使弱学习算法集中学 习分布中难学习部分。这个构造性过程就是b o o s t i n g 算法的雏形。b o o s t i n g 算 法就是一个通过合并粗略的、不太准确的经验规则生成一个非常准确的预测规 则的学习过程。 具体介绍构造性过程之前我们首先描述一下分布自由学习模型。一个概念 c 是例子空间的布尔函数。一个概念集合c 是一个概念集合。c 用参数i 索引 分成几个子集c 。，也就是c = t _ j 。c 。巴中所有的个体有一个公共的领域 x 。我们假定z 。中每一个例子的编码长度用n 的多项式限定，令= u 。z 。 此处，用e x 表示实例的源，即通过e x 我们可以查询到实例的正确分类。 彳是以高概率提出假设盘接近目标概念c 的算法。我们设计一个算法爿， 爿在三种不同的分布下模仿一，提出明显接近于c 的假设。 ( 1 ) 令e x 为给定的实例的源，通过e x 我们可以查询到实例的正确分类。令d 为由腑引入的x 。的分布。算法a 在起始分布d = d 下模仿彳，使用给定的 e x ，= 日。令氟为彳提出的假设。 ( 2 ) 直观的，4 发现了原始分布的一些弱势，这些弱势用 表示。为了迫使4 学习分布中难于学习的这部分弱势，我们必须破坏这种弱势。于是，47 建立了 一个新的分布d ，在这个分布下，根据d ，选择的例子被甄正确分类和错误分 类的概率几乎是相同的。分布现是对e x 根据分布d 选择出来的实例进行过滤 得到的。为了模仿d ，建立了一个新的实例的e x ，。当需要例子的时候，戤， 首先抛硬币，如果是正面，e x ：就从e = | 中要求实例，直到找到一个h ，v ) = c v ) 的实例，否则的话，e ，等待选择一个h i ( v 一) c ( v ) 的实例。算法一被再度模仿， 这次提供给一的实例是e x ，根据n 选择的，h ，为所提出的假设。 第二章混台算法及集成学习的理论基础 ( 3 ) 第三步通过对分布d 过滤两和h 2 一致的建立了分布d ，。也就是第三个实 例的源根据b 选择，从e x 中要求实例，直到遇到一个h ( v ) v ) 的例子。第 三次，对e 墨中抽取的例子用算法a 模仿，产生假设甄。 ( 4 ) 最后，a 提出它的假设h ：给定个例子v ，如果忍v ) = h ，( v ) ，那么h 预 测一致的值；否则的话，h 预测h 3 ( v ) 。( 换句话浇，h 取曩，h ，h 3 中“多数票” 的值) 后面，表明了h 的误差可以用譬缸) = 3 6 2 2 6 3 来限定。这个数值明显的 比初始的误差口小，这可以从如图2 1 中的图示看出。( 实线是函数2 的图示) 后来，f r e u n d 1 6 1 提出了“b o o s t b y m a j o r i t y ”算法，比s c h a p i r e 的方法更有 效。两个算法都是通过多次调用给定的弱学习算法，每次提供给它一个不同的 分布，最后把提出的所有假设合并成一个单一的假设。这种直观的想法是以一 种方法分布，增加对“难学习”部分学习的可能性，迫使学习者提出新的假设 在这些部分少犯错误。但是这两个算法在解决实际问题的时候有一个重大的缺 陷就是他们都要事先知道弱学习算法学习正确率的下限，这个在实际的问题中 很难做到。 图2 1 误差函数9 0 ) = 3 6 2 2 6 3 19 9 5 年，f r e u n d 和s e h a p i r e 1 提出了a d a b o o s t ( a d a p t i v eb o o s t i n g ) 算法。 这个算法的效率和“b o o s t b y m a j o r i t y ”算法的效率几乎一样，却可以非常容易 的应用到实际的问题中去。新的算法生成的最后假设的准确度依赖于弱学习算 法w e a k l e a r n 返回的所有假设的准确度，而不像以前的b o o s t i n g 算法仅依赖于 准确率低的弱假设的准确度，因此可以全面的开发弱学习算法的能力。 目前a d a b o o s t 算法有：a d a b o o s t m 1 算法、a d a b o o s t ，m 2 算法和a d a b o o s t r 算法。a d a b o o s t m 1 算法主要是用来处理二分类的问题；随后f r e u n d 和s e h a p i r e 还将a d a b o o s t 算法扩展到了多分类问题和回归问题。a d a b o o s t m 1 就是对 第二章混合算法及集成学习的理论基础 a d a b o o s t 算法的一个直接扩展。这个算法要求弱学习者提出的假设的误差要小 于1 2 - 。只有满足这个条件，合并以后所得到的最后假设才能和二分类情况一样 误差呈指数级降低。直观上来看，这个要求对于弱学习者来说比较高。因为， 在二分类的情况下，随机猜测的正确率是l 2 。但是对于k 化 2 ) 分类问题，随 机猜测的准确率为1 k 1 2 。a d a b o o s t m 1 要求弱学习者所提出的假设的误差 要小于l 2 ，与a d a b o o s t 算法所提出的仅比随机猜测好来进行相比，就要严格 多了。 实际上，当弱学习者的性能只根据错误率度量，正如下面这个例子中所表 明的一样这个困难是不可避免的。考虑一个y = o ，1 ，2 的学习问题，假定很容易 预测是否标记为2 ，但是很难预测标记是0 或者l 。那么一个假设在无论标记是 2 还是其他0 或1 中任意一个预测的准确性保证至少为一半( 很明显超过了随 机猜测取得的的准确度) 。因为我们假定很难分辨0 标记和1 标记的例子， 将这个学习提升到高的准确度就是不可能的。 作为这个问题一个更自然的例子，考虑在光学字符识别( o p t i c a lc h a r a c t e r r e c o g n i t i o n ，简称o c r ) 应用中识别手写数字的问题。对于一个弱学习者来说， 很容易分辨一个特定的形状是“7 ”而不是0 ，但是很难确定它是“7 ”还是 “9 ”。这里所指的问题就是b o o s t i n g 算法可以把弱学习者的注意力集中到难学 习的实例，但是没有办法迫使弱学习者来识别不容易分辨的特定的标记。 为了解决上述的问题，f r e u n d 和s e h a p i r e 在第二个版本多分类的 a d a b o o s t ，m 2 算法中，通过扩展b o o s t i n g 算法和弱学习者之间的交流来克服这 个困难。尤其是有时候，当弱假设不能以大于1 2 的概率预测出正确的标记时， 仍可以使弱学习者对最后假设的正确性做出有用的贡献。 首先，允许弱学习者提出更具有表达性的假设，这个假设的结果是l o ，1 r 中 的一个向量，而不是】，中的单一的标记。直观的来说，这个向量的第y 个成员 代表了正确的标记是y 的“可信度”。具有较大值的成员( 接近于1 ) 相应的这 些标记被认为是可能的。同样的，分配了小值( 接近于0 ) 的标记是不可能的， 可疑的标记分配一个接近于坛的值。如果几个标记被认为是可能的( 或者不可 能的) ，那么它们都可能被分配一个大的值( 或者