（应用数学专业论文）迁移式并行遗传算法求解支持向量机反问题.pdf

摘要 摘要 支持向量机( s v m ) 反问题的研究内容是：给定一个未知类属性的事例集，可将其随 机分为二部分，如何划分才能使得这两部分之问的间隔最大。求解支持向量机反问题的 意义重大。比如，在决策树的学习算法中，使用s v m 的最大间隔替代最小信息熵，作 为启发式信息，这将大大改善决策树的泛化能力。求解支持向量机反问题，可得s v m 的 最大间隔。但是，其解法的时间复杂度较高。为在实际应用中得到有效的应用，必须提 高算法的求解效率。本文借助高性能计算集群，提出了一种用于求解s v m 反问题的迁 移式并行遗传算法。 本文首先探讨求解支持向量机反问题的基本遗传算法的串行处理过程，并分析了该 算法的时间复杂度及各算子的耗时情况；然后，通过分析串行处理过程中的可并行性， 结合集群系统，设计一种求解s v m 反问题的并行算法：迁移式并行遗传算法。最后， 给出了本文算法在集群系统上的实现过程及其测试结果，测试数据表明算法是可行的和 有效的。 关键词支持向量机；遗传算法：并行算法；集群系统 a b s t r a c t a b s t r a c t f o rag i v e nd a t a s e tf o rw h i c hn oc l a s sl a b e l sa r ea s s i g n e dt oi n s t a n c e s ，w ec a nr a j l d o m l y s p l i tt h ed a t a s e ti n t ot w os u b s e t s t h ei n v e r s ep r o b l e mo fs u p p o n v e c t o rm a c h i n e s ( s v m ) i s h o wt os p l i tt h ed a t a s e ts u c ht h a tt h em a 唱i nb e t w e e nt h et w os u b s e t sa t t a i n st h em a x i m u m i t i ss 追n i 6 c a n tt os o l v et h ei n v e r s ep r o b l e mo fs v m f o re x a m p l e ，t h em a x i m a lm a 昭i no fs v m i sc h o s e na sah e u r i s t i cs t r a t e g yt os u b s t i t u t em i n i m u me n t r o p yi nd e c i s i o nt r e el e 锄i n g a l g o r i t h m ，w h i c hc a na t t a i nb e t t e rg e n e r a l i z a t i o n t h em a x i m a lm a r g i nc a nb ea n a i n e dt o s o l v et h ei n v e r s ep r o b l e mo fs v m ，w h o s et i m ec o m p l e x i t yi sh i g h e r f o rt h ec o n v e n i e n c eo f 印p l i c a t i o n ，i ti sn e c e s s a 巧t oi m p r o v et h ee 币c i e n c yo fo u ra l g o r i t h m am 培r a t i o np 撇1 1 e l g e n e t i ca l g o r i t h mf o rs o l v i n gs v mi n v e r s ep r o b l e mi sp r o p o s e dw i t hh i g hp e r f 0 1 1 m a n c e c o m p u t i n gc l u s t e r f i r s t ，s e r i a lp r o c e s so fs i n l p l eg e n e t i ca l g o r i t h mt os o l v eo u rp r o b l e mi sd i s c u s s e da n di t s t i m ec o m p l e x i t ya n dt i m e - c o n s u m i n gs c a l eo fe a c ho p e r a t o ra r ea n a l y z e d s e c o n d ，a c c o r d i n g t op a r a h e l i z a b i l i t yo fs e r i a ip r o c e s s ，ap a r a l l e la l g o r i t h mi sd e s i g n e dw i t ho u rc l u s t e r ，w m c hi s am i g r a t i o np a r a l l e lg e n e t i ca l g o r i t h m f i n a l l y ，t h ep r o p o s e da l g o r i t h mi si m p l e m e n t e da n d s o m ee x p e r i m e n t sa r ep r e s e n t e d t h et e s t i n gr e s u l t ss h o wt h a tt h ep r o p o s e da l g o “t h mi s e f 矗c i e n ta n dr e a s o n a b l e k e yw o r d ss u p p o i r tv e c t o rm a c h i n e s ；g e n e t i ca l g o r i t h m s ；p a r a l l e la l g o r i t h m ；c l u s t e r 河北大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人己经发表或撰写的研究成果，也不包含为获得河北大学或其他教育机构的学位或证书 所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了致谢。 作者签名：日期：避尘月丛r 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留并向国 家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。学校可以公布 论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 本学位论文属于 1 、保密口，在年月同解密后适用本授权声明。 2 、不保密囚。 ( 请在以上相应方格内打“”) 作者签名：7 泓 刷程名0 臼一 日期：盈壁迸年i l 月z 丕日 日期：年月日 保护知识产权声明 本人为申请河北大学学位所提交的题目为( 迁移式并行遗传算法求解支持向量机反 问题) 的学位论文，是我个人在导师( 王熙照教授) 指导并与导师合作下取得的研究成 果，研究工作及取得的研究成果是在河北大学所提供的研究经费及导师的研究经费资助 下完成的。本人完全了解并严格遵守中华人民共和国为保护知识产权所制定的各项法 律、行政法规以及河北大学的相关规定。 本人声明如下：本论文的成果归河北大学所有，未经征得指导教师和河北大学的书 面同意和授权，本人保证不以任何形式公丌和传播科研成果和科研工作内容。如果违反 本声明，本人愿意承担相应法律责任。 声明人： 作者签名： 导师签名： 日期：丝擗妇上垒同 日期：酵望月丛同 日期：砂平年月丛同 第1 章绪论 第1 章绪论 1 1 课题来源及意义 人类在很多方面都已成功地采用机器来代替自己完成繁重的体力工作，人们也从没 有放弃用机器来实现人类的智能的努力。1 9 4 6 年计算机的诞生，使人们的这种设想有了 成为现实的可能。人工智能作为计算机技术的一个技术领域，自1 9 5 6 年诞生之后已取 得了重大进展，形成了诸多研究和应用领域，比如集成了知识表示与逻辑推理的专家系 统、机器学习、智能决策支持系统、人工神经网络等。几乎所有的智能技术，都要涉及 知识的获取。而机器学习的目标就是研究如何从各类数据中自动获取知识。 决策树学习作为机器学习领域的研究热点之一，是一种应用最广的归纳学习推理算 法n 1 。其基本算法采用自项向下的贪婪搜索遍历可能的决策空间，或者说，它以自顶向 下递归的各个击破方式构造决策树。最著名的决策树学习算法就是i d 3 算法。生成决策 树的一般过程是：首先，将所有训练事例作为树的根结点；然后根据某一启发式信息， 将根节点向下划分成两个子结点，若子结点的事例都属于同一类，则此结点就被看作成 一个叶子结点，否则继续划分下去，直到出现叶子结点为止。i d 3 算法选用最小信息熵 ( m i n i m u me n t r 叩y ) 作为启发式信息。这种方法一般可以得到较小的决策树，并且其计算 复杂度较小，但是它往往不能保证决策树有较好的泛化能力( g e n e r a l i z “o n ) 。 统计学习理论( s t a t i s t i c a ll e a m i n gt h e o 巧或s l t ) 是一种专门研究小样本情况下机器 学习规律的理论。v a p n i k 等人早在六、七十年代就丌始致力于此方面研究。随着时间的 推移，该理论得到了不断发展，逐渐成熟起来。9 0 年代中期，基于该理论设计的支持向 量机( s u p p o nv e c t o rm a c h i n e s ，简称s v m ) 在解决一系列实际问题中获得成功业1 ，表现出优 良的学习能力尤其是泛化能力，从而引起人们对这一领域的极大关注。支持向量机的基 本思想是，对于一个给定的具有有限数量训练样本的学习任务，如何在准确性( 对于给 定训练集) 和机器容量( 机器可无错误地学习任意训练集的能力) 进行折衷，以得到最 佳的泛化能力。 考虑到s v m 分类间隔与泛化能力的关系，可以设想使用s v m 的最大问隔替代最 小信息熵，作为决策树学习的启发式信息? ”，从而改善生成决策树的泛化能力。s v m 反 河北人学理学硕十学位论文 问题的研究内容是：将一个未知类别属性的事例集划分为两个子集，如何划分刁能使得 两个子集问的i 白j 隔最大。因此，我们可以通过求解s v m 反问题得到s v m 的最大间隔。 求解s v m 反问题的计算复杂度较高。如何提高该算法的求解效率，是一个值得研 究的问题。本文借助集群系统并行计算环境，提出并实现了一种用于求解s v m 反问题 的迁移式并行遗传算法。 1 2 国内外研究状况 1 2 1 支持向量机 统计学习理论是支持向量机的理论基础。统计学习理论是建立在一套较坚实的理论 基础之上的，为解决有限样本学习问题提供了一个统一的框架。它将很多现有方法纳入其 中并化为已用。早在2 0 世纪6 0 年代，作为s v m 的奠基人v a p n i k 就开始了统计学习理 论的研究h 。1 9 7 1 年，v a p n i k 和c h e n ，o n e n k i s 提出了s v m 中的一个重要理论一一v c 维理论。1 9 8 2 年，v a p n i k 进一步提出了结构风险最小化原理哺3 。1 9 9 2 年，b o s e r 、g u y o n 和v v a p n i k 提出了最优边界分类器m 1 。1 9 9 5 年，v a p n i k 完整地提出了s v m 分类h 1 。1 9 9 7 年，v a p n i k 和g o k o w i c h 、s m o l a 共同发表了文章：s u p p o nv e c t o rm e t h o df o rm n c t i o n a p p r o x i m a t i o n ，r e g r e s s i o ne s t i m a t i o n ，a n ds i g n a lp r o c e s s i n g m 1 ，该文详细介绍了基于s v m 方法的回归算法和信号处理方法。同一时期，支持向量机理论在解决一系列实际问题中 获得成功陋1 ，表现出优良的学习能力尤其是泛化能力。由于s v m 算法的潜在应用价值， 它吸引了国际上众多的专家学者。近几年，支持向量机在许多领域有了一些应用，比如 模式识别m m 3 、字符识别、文本自动分类1 、人脸检测“”、头的姿态识别。引、函数 逼近m 6 。、数据挖掘h 3 和非线性系统控制h 砌等等。 1 2 2 遗传算法 2 0 世纪6 0 年代期间，美国密西根大学的h o l l a n d 教授认识到生物的遗传和自然进 化现象与人工自适应系统的相似关系，提出在研究和设计人工自适应系统时，可以借鉴 生物的遗传机制，以群体的方式进行自适应搜索。1 9 6 7 年，h o l l a n d 的学生b a g l e y 发表 了关于遗传算法应用的论文n ，在该文中首次使用”遗传算法”一词。他所提出的选择、 交叉和变异操作已与目前遗传算法中的相应操作十分接近，尤其对选择操作做了十分有 意义的研究。1 9 6 8 年，h o l l a n d 教授提出的模式理论，成为遗传算法的主要理论基础。 第1 章绪论 1 9 7 5 年，h 0 1 l a n d 教授出版了第一部系统论述遗传算法和人工自适应系统的专著自 然界和人工系统的适配”j 下式出版，全面地介绍了遗传算法的基本理论和方法，并论 述了对遗传算法的理论研究和发展极为重要的模式理论( s c h e m a t at h e o r y ) ，人们常常把这 一事件视作遗传算法问世的标志，h o l l a n d 也被视作遗传算法的创始人。同年，d ej o n g 在其博士论文犯中结合模式定理进行了大量的纯数值函数优化计算实验，将选择、交叉 和变异操作进一步完善和系统化，同是又提出了诸如代沟( g e n e r a t i o ng a p ) 等新的遗传操 作技术，建立了著名的d ej o n g 五函数测试平台，定义了评价遗传算法性能的在线指标 和离线指标。 2 0 世纪8 0 年代，遗传算法迎来了兴盛发展时期。h 0 1 1 a n d 实现了第一个基于遗传算 法的机器学习系统( c l a s s i 6 e rs y s t e m ) ，丌创了基于遗传算法的机器学习的新概念，为分 类器的构造提出了一个完整的框架。1 9 8 5 年，作为h o l l a n d 的学生，g o l d b e r g 博士出版 专著遗传算法搜索、优化及机器学习1 ，全面、系统地介绍遗传算法，使这一 技术得到普及与推广。1 9 8 7 年，美国l a 岍e n c e 总结人们长期从事遗传算法的经验，公 开出版遗传算法和模拟退火乜3 1 一书，以论文集形式用大量实例介绍遗传算法。第一 届遗传算法国际学术会议( i n t e m a t i o n a lc o n f e r e n c eo ng e n e t i ca 1 9 0 “t h m s ，简称i c g a ) 于 1 9 8 5 年在美国举行，随后，每2 年左右都举行一次。 2 0 世纪9 0 年代，遗传算法不断地向广度和深度发展。我国丌展遗传算法研究，主 要是在这个时期。目前，遗传算法已成为继专家系统、人工神经网络之后有关人工智能 方面的第三个热点课题。这期间，有关遗传算法的国际会议也比较活跃。 随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗 传算法的机器学习；二是遗传算法正r 益和神经网络、模糊推理以及混沌理论等其他智 能计算方法相互渗透和结合；三是有关遗传算法并行分布处理的研究非常活跃；四是生 物进化与遗传算法的研究；另外，遗传算法和人工生命正不断渗透。 1 3 主要研究内容 本文的主要工作是：借助高性能计算机( 集群系统) ，在高性能并行软件环境的支 持下，设计并实现了一种求解支持向量机反问题的迁移式并行遗传算法。 具体章节结构安排如下： 第l 章介绍了课题的背景、意义以及相关的国内外研究状况。 3 - 河北人学理学硕十学伊论文 第2 章介绍了支持向量机的基本概念及其方法。 第3 章介绍了遗传算法的基本概念、算法描述及其并行化途径。 第4 章介绍支持向量机反问题的问题描述，剖析串行求解算法的流程及各算子耗时 情况，为并行化做铺垫。 第5 章设计并实现了一种求解支持向量机反问题的迁移式并行遗传算法( m i 伊a t i o n p a r a l l e lg e n e t i ca 1 9 0 r i t m 简称m p g a ) ；做了相关的测试实验，并对实验结果做了分析 和说明。 第6 章是结论与展望部分。 第2 章支持向封机 第2 章支持向量机 这罩先介绍最优分类超平面，然后介绍如何构建线性支持向量机来解决线性可分与 线性不可分的问题，最后将线性支持向量机推广到非线性支持向量机。 2 1 最优分类超平面 我们针对典型的二元模式识别问题进行讨论。假设一个两类训练样本集由，个样本 点组成，如果x ，r ”属于第l 类，则决策属性值为1 ；如果属于第2 类，则决策属性值 为一1 。即 ( _ ，m ) ，( 而，儿) ，( 一，乃) ，一r ”，只 + 1 ，一1 且该训练集可以被一个超平面线性分割，该超平面记为 ( w x ) + 6 = o( 2 1 ) 如果这个向量集合被超平面完全j 下确地分开，并且距离超平面最近的向量与超平面 之j 可的距离( 又叫做间隔( m a r g i n ) ) 是最大的，则我们说这个向量集合被这个最优分类超平 面( 或最大间隔超平面) 分开。其中，距离超平面最近的点，称为支持向量( s u p p o nv e c t o r ) 。 如图l 所示。 0 图l 线住町分时的最优分类超、i ，面，环绕的点为支持向量 对于线性可分的情形，不失一般性，我们可假定训练样本集中的向量满足下列不等式： ：二：；三二。孑；：三二。，= ，2 ， m ，x ，+ 6 一lf 厂y ，= 一1 河北人学理学硕十字1 市论文 我们称上述不等式为规范形式( c a n o n i c a lf o m ) 。写成紧凑形式如下： y ，( w x i + 6 ) l f _ 1 ， ( 2 2 ) 其中w x ，是两个向量( w 尺”，即w = ( w l ，w 2 ，w 。) ；x ，尺”，即x = ( _ ，x 2 ，x 。) ) 的 内积。 2 2 线性支持向量机解决线性可分问题 对于2 1 1 中提到的属于两类的训练集 ( 一，y 1 ) ，( x ：，y ：) ，( _ ， ) ，x ，r ”，y ， + 1 ，一1 其最大间隔超平面可以用 ( x ) = ( w x ) + 6 ( 2 3 ) 来描述。 那么，我们如何来求解最大间隔呢? 结合图1 ，先定义： p l u s p l a n e ：& ：w x + 6 = + 1 m i n u s p l a n e ： j ：w x + 6 = 一1 且有 + li fw x + 6 = + 1 1i fw x + 6 = 一1 不可分 i f 一1 w x + 6 一 c + + ) x w 认如 m 豇 河北人学理学硕十学何论文 ，竹a x ( a ) = ：。a ，一圭：，：a ，a ，y ，y ，( 妒( 一) ( x ，” ( 2 2 6 ) = o ；c a ，o ，江1 ，l 令 k ( x ，x j ) = ( x ，) + 妒( x ，) ( 2 2 7 ) 称k ( x ，x ，) 为核函数。将( 2 2 7 ) 代入( 2 2 6 ) 式，得 m a x 旷( a ) = ：；口，一三：，仅，a ，y ，y ，k ( 一，x ，) ( 2 2 8 ) s t ：l a ，y ，= o ；c a ，o ，f = 1 ， 参数6 和最优分类超平面分别如下： 6 = y ，一( ? ：l y ，a ，k ( 一，x 埘 ( 2 2 9 ) 厂( x ) = o ，a ? k ( 一，x ，) + 6 ( 2 3 0 ) 由以上三式可知，尽管我们利用非线性函数将原空间映射到高维甚至无穷特征空 间，并在特征空间上构建最优分类超平面，但是由于引入了核函数，因此不需要显式地 计算非线性函数，这就避免了特征空间灾难维数的问题。 下面给出目前常用的几种核函数： 线件s v m ：k ( x ，x ，) = x x ，( 2 3 1 ) 多项式s v m ：k ( x ，x ，) = 【( x x ，) + l 】“ ( 2 3 2 ) 径向摧s v m ：k ( x ，x ，) ：e x p 忙一一1 1 2 2 仃2 j ( 2 3 3 ) 神经州s v m ：k ( x ，x ，) = s 枷”d f j ( 甜( x x ，) 一6 ) ( 2 3 4 ) 第3 章遗传算法 第3 章遗传算法 在自然界中，生物群体的繁殖过程隐含着自然优化的机制，复杂的生物群体在自身 繁衍的过程中不断进化。生物的进化是一个奇妙的优化过程，它通过选择、淘汰、突然 变异、基因遗传等规律产生适应环境变化的优良物种。遗传算法是模拟达尔文的遗传选 择和自然淘汰的生物进化过程的计算模型，它由美国m i c h i g a n 大学的j h h o l l a n d 教授 于1 9 7 5 年在著作自然系统与人工系统的适配中首次提出口3 1 。 d a n ，i n 进化论最重要的是适者生存原理，它认为每一物种在发展中越来越适应环 境。物种每个个体的基本特征由后代所继承，但后代又会产生一些不同于父代的新变化。 在环境变化时，只有那些能适应环境的个体特征才能保留下来。m e n d e l 遗传学说最重 要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体 内。每个基因有特殊的位置并控制某种特殊性质，所以，每个基因产生的个体对环境具 有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然 淘汰，适应性高的基因结构得以保存下来。 在人工智能领域中，有很多问题需要在复杂而庞大的搜索空问中寻找最优解或近似 最优解。求解这些问题的计算复杂度，常随着规模的扩大呈指数级数的增长，或者说， 随着求解问题规模的扩大，搜索空间将出现组合爆炸。因此，研究能在搜索过程中自动 获取和积累有关搜索空间的知识，并自适应地控制搜索过程，从而得到最优解或近似最 优解的通用搜索算法，渐渐成为令人瞩目的研究课题。遗传算法就是其中一种特别有效 的算法，它通过模拟自然进化过程搜索最优解。 近几年来，基于模拟大自然演化过程的随机搜索算法，在优化领域和工业工程领域 取得的成功，引起了很多人的关注。遗传算法在工业工程领域的应用包括：最优控制、 运输问题、旅行商问题、调度、生产计划、资源分配、统计与模式识别等等。 3 1 基本概念及算法描述 3 1 1 基本概念 染色体( c h r o m o s o m e ) ：又称作个体( i n d i v i d u a i ) ，是生物遗传物质的主要载体。个体 1 1 河北人学理学硕十学侮论文 在算法中的表现形式为二进制串。用这种二进制串表示优化问题的满意解。 基因( g e n e ) ：是控制生物性状的遗传物质的功能单位和结构单位，若干个基因组成 一个染色体。基因在算法中的表现形式为二进制串的一位。比如有一个串s = 1 0 0 l ，其 中的基因就是：1 ，0 ，0 ，1 。 群体( p o p u l a t i o n ) ：一定数量的个体组成了群体，群体中个体的数目称为群体的大小 ( p o p u l a t i o ns i z e ) ，也叫群体规模。基于生物进化思想的遗传算法从本质上看是模拟生物 的一代群体向另一代群体进化的过程。 适应度( 6 t n e s s ) ：各个个体对环境的适应程度，它以数值方式来表征了个体的优劣程 度。在优化模型中，目标函数就是对设计解优劣进行比较的指标。而遗传算法用适应度 作为个体优劣评判的指标，因此遗传算法的适应度在一定意义上对应于优化模型中的目 标函数。 选择( s e l e c t i o n ) ：这是从当前群体中选择出较适应环境的个体，使它们有机会作为父 代，来繁殖下一代。因此，这一操作也称为再生( r e p r o d u c t i o n ) 。由于在选择用于繁殖下 一代的个体时，是根据个体对环境的适应度来决定其繁殖量的，故而有时也称为非均匀 再生( d i 髋r e n t i a lr e p r o d u c t i o n ) 。 交叉( c r o s s o v e r ) ：在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置 的基因进行交换，从而产生新的个体。在个体繁殖过程中，这个操作引起了基因模式的 重组，因此有可能产生性能更加优良的个体。常见的交叉方式有两种：( 1 ) 单点交叉( o n e p o i n tc r o s s o v e r ) 。其含义是：在两个父代个体的二进制串中，选择一个交叉点，并将交 叉点后的二进制串互相交换，产生下一代个体。( 2 ) 双点交叉( t w op o i n t sc r o s s o v e r ) 。其含 义是：在两个父代个体的二进制串中，选择两个交叉点，将两个点之间的二进制串互相 交换产生下一代个体。 变异( m u t a t i o n ) ：在选中的个体中，对个体中的某些基因执行异向转化。具体地讲， 对于二进制编码的个体而言，若某位原来是o ，则通过变异就变化成为l ，反之亦然。 一般地，各个基因发生变异的概率取值很小。 3 1 2 基本遗传算法描述 1 算法的构成要素 ( 1 ) 参数编码：由于遗传算法不能直接处理解空问的解数据，因此我们必须通过编码 1 2 第3 章遗传算法 将它们表示成遗传空间的基因型串结构数据。基本遗传算法使用固定长度的二进制符号 串来表示群体中的个体。 ( 2 ) 适应度评估检测：遗传算法在搜索进化过程中一般不需要其它外部信息，仅用目 标函数即评估函数值来评估个体的优劣，并作为以后遗传操作的依据。评估函数值也称 作适应度。遗传算法的目标函数不受连续可微的约束且定义域可以为任意集合。值得注 意的是，目标函数值要求是非负的。基本遗传算法按与个体适应度成正比的概率来决定 当前群体中的每个个体遗传到下一代群体中的机会的多少。针对不同的具体问题，必须 确定由目标函数值到适应度之间的转换规则，特别是要事先确定好当目标函数值为负数 时的处理方法。 ( 3 ) 遗传操作设计：共有选择、交叉和变异三个算子，参见3 1 1 节。 ( 4 ) 控制参数设定：基本遗传算法有以下几个运行参数需要提前设定： a ) p o p s i z e ：群体规模，即群体中染色体( 个体) 的总数； b ) m a x g e n ：遗传算法中进化的最大代数； c ) p c ：交叉概率； d ) p m ：变异概率； e ) n b ：变异比例。 2 算法的基本过程 遗传算法是具有“生成+ 检测”( g e n e r a t e a n d t e s t ) 的迭代过程的搜索算法盘引。该算 法是种群体型操作，操作对象是群体中的所有个体。选择( 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 ) 是遗传算法的三个主要操作算子，它们构成了所谓的遗传操作( g e n e t i c o p e r a t i o n ) 。它的基本处理流程如图3 所示： 可北人学理学硕十学何论文 基本遗传算法的伪码如下： p r o c e d u r es i m p l eg a b e g i n 图3 基奉遗传算法流程 ( 1 1 ) i n i t i a l i z ep o p u l “o n ( o ) ； ( 1 2 ) e v a l u a t ef i t n e s so fp o p u l a t i o n ( 0 ) ； w h i l e ( t = m a x g e n ) d o ( 2 1 ) f o r i = 1t op o p s i z ed o s e l e c to p e r a t i o nt op o p u l a t i o n ( t ) ； e n d f o r ( 2 2 ) f o r i = lt o p o p s i z e 2 d o c r o s s o v e ro p e r a t i o nt op o p u l a t i o n ( t ) ； e n d f o r ( 2 3 ) f b r i = 1t o p o p s i z e d o m u t a t i o no p e r a t i o nt op o p u l a t i o n ( t ) ； e n d f o r ( 2 4 ) f 0 r i = 1t op o p s i z ed o e v a l u a t e 行t n e s so fp o p u l a t i o n ( t ) ； e n d f o r ( 2 5 ) f o r i = 1t o p o p s i z e d o p o p u l a t i o n ( t + 1 ) = p o p u l a t i o n ( t ) ； 第3 章遗传第法 e n d e n d f o r t = c + l e n d w h il e 3 2 并行化途径 在自然进化过程的任何时刻，总是同时有大量的物种在彼此独立地向前进化。在同 一物种内部，也是同时存在着大量的个体在通过自然选择、交配和基因突变而进化。显 然，自然界的进化过程本身就是一个并行过程。遗传算法源于自然进化，自然也就继承 了自然进化过程所固有的并行性。遗传算法具有天然的并行性，这一点早在二十世纪六 十年代初期，遗传算法的奠基人h o l l a n d 口哪就做了具体的阐述。近年来，许多专家学者 对并行遗传算法做了大量的理论研究和应用研究。g r e f e n s t e t t e 全面研究了遗传算法并行 实现的结构问题。7 1 ，阐述了遗传算法的并行通常有三种模式：同步主从式、异步主从式 和网格式。t 锄e s e 3 和c o h o o n 3 描述了粗粒度并行遗传算法的例子。s p i e s s e n s & m a n d 甜c p 0 1 描述了细粒度并行遗传算法方面的例子。 基本遗传算法模型是一个反复迭代的进化计算过程，通过对一组表示候选解的个体 进行评价、选择、交叉、变异等操作，来产生新一代的个体( 候选解) ，这个迭代过程直 到满足某种结束条件为止。对应于这个进化计算过程，为实现其并行化要求，可以从下 面四种并行性方面着手对其进行改进和发展。“1 ，如图4 所示。 幽4 遗传算法的并行机制 并行性4 河北人。学理学硕十学位论文 并行性1 ：个体适应度评价的并行性 个体适应度的评价在遗传算法中占用的运行时问比较大。通过对适应度并行计算方 法的研究，可提高个体适应度评价的计算效率。 并行性2 整个群体各个个体适应度评价的并行性 群体中各个个体适应度的评价过程无相互依赖关系，这样各个个体适应度的评价或 计算过程就可以相互独立、相互并行地在不同的处理机上同时进行。 并行性3 子代群体产生过程的并行性 从父代群体中产生下一代群体所需进行的选择、交叉、变异等遗传操作可以独立并 行地进行。 并行性4 基于群体分组的并行性 群体中的单个或一组个体的进化过程可以相互独立地进行，在适当的时候，它们再 以适当的方式交换信息。即不同个体或不同组个体的进化过程是同时进行的。 在上述四种并行方式中，前三种方式并未从总体上改变简单遗传算法的特点，第四 种并行方式却对简单遗传算法的结构有较大的改变，并且这种方式也最自然，在并行机 或局域网环境下实现起来也最简单，所以受到了人们较大的重视。目前己开发出的并行 遗传算法基本上都是基于上述四种并行机制或其组合来实现的。 3 2 1 主从式并行化方法 当我们考察基本遗传算法时，发现该算法只有在最外层结构( 初始化部分) 上才是纯 串行的，而在内部层次上存在着许多潜在的并发性。例如，当施行适应度评估时我们可 以相互独立地评估群体内的每个个体的适应度，从通信量的角度来讲，这意味着在评估 进程之问无需通信，如单纯从减少通信量入手，也很自然地首先想到可将适应度评估等 局部操作交给从处理器网络( s l a v e s ) 并行执行，而将选择、交叉等全局操作留给主处理器 ( m a s t e r ) 串行执行，这就是所谓主从式并行化方法。主从式并行遗传算法( m 2 l s t e r - s l a v e p a r a l l e lg e n e t i ca l g o t h m 简称m s p g a ) ，也称作全局并行遗传算法。 主从式并行遗传算法的伪码和基本遗传算法的伪码基本一致，只是把第( 1 2 ) 步换 成： ( 1 2 ) f b ri = 1t op o p s i z ep a r - d o e v a lu a t et h e ，t hf i t n e s so fp o p u l a t i o n ( 0 ) ； 1 6 第3 章遗传赁= 法 e n d t - o r 把第( 2 4 ) 步换为： ( 2 4 ) f o ri = 1t op o p s i z ep a r d o e v a l u a t et h en hf i t n e s so fp o p u l a t i o n ( t ) ； e n d f o r 在上述算法的并行实现中，我们需要对整个群体的适应度有个全局的了解，这部分 决定了通信要求。主处理器必须知道每个个体的适应度，所以必须支持多到一的通信。 另外，因为无论当哪个处理器运行主算法时都要有同步机制，所以像这样来丌发存在于 遗传算法中的并发性效率不是太高的。这是负载不均衡所造成的。如果适应度评估检测 很耗时( 实际情况通常是这样的) ，则这么做就能获得令人满意的效率。 主从式比较直观且容易实现，它并没有对标准遗传算法的框架结构作任何改动，所 以不会影响其解决具体问题的效果。但是由于它存在有负载不均衡的问题，而且存在较 大的通信量，因此，这种算法值得进一步改进。 3 2 2 迁移式模型 如果将群体分成若干个子群体，并为每个子群体分配一个处理器。这些子群体互相 独立地同时繁衍进化，只是每隔几代就把其中的最佳个体迁移到相邻的子群体中去。这 种并行方式的遗传算法，即是迁移式并行遗传算法，也叫做粗粒度并行遗传算法。 迁移式并行遗传算法的伪码如下： p r o c e d u r em i g r a t i o np a r a l l e ig a b e g i n ( 1 ) i n i t i a l i z ep o p u l a t i o n ( o ) a n dd i v i d ei ti n t o ，s u b p o p u l a t i o n s ； ( 2 ) f o r f _ 1 t om p a r - d o ( 2 1 ) e v a l u a t ef i t n e s so fs u b p o p u l a t i o n ( o ) ； ( 2 2 ) t = l ； ( 2 3 ) w h i l e ( t = a 彳z g p 玎) d o ( a ) s e l e c to p e r a t i o nt os u b p o p u i a t i o n ( t ) ； ( b ) c r o s s o v e ro p e r a t i o nt os u b p o p u l a t i o n ( t ) ； ( c ) m u t a t i o no p e r a t i o nt os u b p o p u l a t i o n ( t ) ； ( d ) e v a l u a t e 行t n e s so fs u b p o p u l a t i o n ( t ) ： ( e ) s u b p o p u l a t i o n ( t + 1 ) 2s u b p o p u l a t i o n ( t ) ； 河北人学理学硕十学何论文 ( 2 4 ) t = t + l ( 2 5 ) i ft - e p o c h d o ( a ) a j l d ( b ) i np a r a l l e l ( a ) s e n de m i g r a n t s ； ( b ) r e c e i v ei m m i g r a n t s ； e n d w h i l e e n d t o r e n d 注：( 1 ) 为了避免通信过程的死锁，( 2 5 ) 中的( a ) 和( b ) 是并发执行的；( 2 ) 卅是子群体 的个数，也即，处理器的个数。 由于迁移式并行遗传算法每隔几代( e p o c h ) 才进行迁移操作( 结点问通信) ，而主从式 并行遗传算法每一代都要进行一次全局通信，因此，前者的通信量比后者有了很大的减 少。粗粒度并行遗传算法的迁移策略决定了其性能优劣。迁移策略表现为：拓扑结构( 定 义子群体间的连接结构) 、迁移率( 发生迁移的染色体的数目) 和迁移周期( 每隔几代发生 一次迁移) 。 3 2 3 细粒度模型 如果我们有足够多的处理器，就可以让每个个体分配到一个处理器，让它们相互独 立地并行进行进化，从而获得最大可能的并行性。相应地，这种算法就称为细粒度并行 遗传算法。显然，这种算法适合在大规模并行计算机系统上实现。 细粒度并行遗传算法与上面的粗粒度并行遗传算法的重要差别在于并行处理的外 层循环的次数不同，前者足子群体的个数，后者是整个群体的大小。 第4 章支持向节机反问题及其串行向? 法 第4 章支持向量机反问题及其串行解法 4 1 支持向量机反问题 对于给定的一个未知决策属性的样本训练集： ( x l ，少1 ) ，( 工2 ，y 2 ) ，( x f ，y ，) ，x ，r ”，= 1 ，2 ， 我们可以随机地将其分为两部分。此时，我们可以利用前面的s v m 理论来求出最 优分类超平面，并计算出相应的问隔( m a 画n ) 。并对问隔做如下规定：( 1 ) 若划分为两类 的样本点线性不可分，m a 唱i n 记为零；( 2 ) 若运用s v m 将两类的样本点完全j 下确地划分 开来，则m a r g i n 为实际计算的结果。显然，对训练集样本点的不同划分，会对应不同 的间隔，那么怎样划分才能使得间隔达到最大呢? 支持向量机反问题足一个优化问题，其数学描述如下： 设样本集s ： ( ，y i ) ，( x 2 ，j ，2 ) ，( z ，y ，) ，x f 尺”，f = l ，2 ， 另外， q = 扩 厂i s a f u n c t i o n f r o m s t o 1 ，1 羚 对于给定的一个函数厂q ，样本集s 被划分为两个子集，并可以计算出其相应的问 隔。我们用m a r g i n ( ) 表示由函数所决定的间隔( 泛函) ，那么s v m 反问题就是要求解 问题： m a x i m 啪r e n ( m a r g i n ( 厂) ) ( 4 1 ) 由于使用枚举算法求解上述问题，其计算复杂度将随问题规模增大呈指数级增长， 所以枚举出所有q 中的函数厂并计算其相应的间隔来求解问题( 4 1 ) 是不现实的。而且给 出一个求解问题( 4 1 ) 的严格算法也是十分困难的。但是我们可以求出其近似最优解或满 意解。所以可以利用遗传算法来求解( 4 1 ) 。”。 支持向量机反问题的研究内容：如何对样本点进行划分，爿。能使最优分类超平面的 间隔达到最大。 支持向量机反问题的研究动机：源自于设计一种新的决策树学习算法。现有的很多 决策树算法如c 4 5 ，生成的决策树的泛化能力往往不佳。支持向量机中最优分类超平面 一1 9 一 河北人学理学硕十学何论文 的问隔越大，其泛化能力就越强。因此，我们设想找到具有最大间隔的样本划分，并把 这个间隔看作生成决策树的新的启发式信息。 4 2 支持向量机反问题的串行求解算法 基于第三章的知识，设计一个遗传算法来解决问题( 4 1 ) ，即s v m 反问题。 4 2 1 算法流程及说明 研究对象：数据集( x l ，m ) ，( x 2 ，少2 ) ，( x ，j ，) ，x ，r ”，f - 1 ，2 ，。 编码机制：每一个函数厂q 对应于对训练样本集s 的一种划分，从而每一个函数厂 可以被视为一个，维向量，如1 0 0 0 1 1 1 0 1 o l ，其中某个基因只能是o 或1 ，对应于训练 集中的一个事例。当基因取1 表示相应的事例为f 例，取0 表示相应的事例为负例。这 样，由，个基因组成的一个染色体c = 口l 呸口，就表示了q 中的某一函数。每个染色体的 长度是固定的，即为初始数掘集事例的总个数。 适应度函数：由于每个染色体，可对应一个两类分类问题的训练集。于是，针对该 训练集求解s v m 反问题，便可得到一系列相应的间隔，并将其定义为相应染色体的适 应度。也即，式( 4 1 ) 中的m a r g i n ( 厂) 。