（信号与信息处理专业论文）贝叶斯优化算法的研究及其在图像分割中的应用.pdf

c l a s s i f i e di n d e x ： u d c ： ad i s s e r t a t i o nf o rt h ed e g r e eo fm e n g r e s e a r c ho nb a y e s i a no p t i m i z a t i o n a l g o r i t h ma n d i t sa p p l i c a t i o ni ni m a g e s egmentatic3e g m e n t a t l o n c a n d i d a t e ：p e n gw e i s u p e r v i s o r ：p r o f b ix i a o j u n a c a d e m i cd e g r e ea p p l i e df o r ：m a s t e ro fe n g i n e e r i n g s p e c i a l t y ：s i g n a la n d i n f o r m a t i o np r o c e s s i n g d a t eo fs u b m i s s i o n ：m a r c h ，2 0 1 0 d a t eo f o r a le x a m i n a t i o n ：m a r c h ，2 0 1 0 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中己注明引用的内容外， 本论文不包含任何其他个人或集体己经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：彭7 尹 日期：2 0 o 年弓月z 娟 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 曰在授予学位后即可口在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：勿7 拳导师( 签字) ：中硒6 移 日期： 2 , o l o 年；月2 z 日2 0 t o 年；月2 z 日 哈尔滨工程大学硕士学位论文 摘要 分布估计算法是将概率模型引入到优化算法当中而形成的一种新型的优 化算法，它通过统计学习的手段来构建概率模型，并利用对模型的采样来实 现种群的进化，其中贝叶斯优化算法是分布估计算法中的典型代表，它定位 准确，且能有效地避免连锁问题，但是统计学习的引入会给算法带来新的时 间和空间上的开销，即贝叶斯优化算法在构建概率模型时，不但需要先验知 识，而且计算量很大，计算时间较长，这也是限制贝叶斯优化算法应用的主 要原因。 贝叶斯优化算法的核心是贝叶斯网络，其计算量也主要集中在贝叶斯网 络的构建上，为了降低贝叶斯优化算法的计算量，本文提出了一种基于免疫 算法的贝叶斯优化改进算法，通过减少贝叶斯网络的构建次数来降低算法的 计算量。免疫算法通过模拟人体的免疫机理，可以利用问题的先验知识和局 部特征来引导整个寻优过程，从而提高算法的收敛速度，因此本文将免疫算 法与贝叶斯优化算法相结合，利用免疫算法的导向性变异，对贝叶斯网络产 生的解进行变异，从而提高种群中个体的适应度，减少贝叶斯网络的构建次 数。仿真结果表明，与传统的贝叶斯优化算法相比，基于免疫算法的贝叶斯 优化改进算法可以有效地减少计算量，缩短运算时间，并且寻优能力也得到 了提高。 同时，针对遗传算法在图像分割中易于陷入局部最优的问题，本文将基 于免疫算法的改进贝叶斯优化算法应用于图像分割，利用其较好的寻优能力， 搜索到图像的最佳阈值，达到较好的图像分割效果。该算法利用贝叶斯网络 对像素进行编码，利用贝叶斯网络采样来产生新的像素值，并利用最大类间 方差法确定适应度函数，通过搜索适应度函数的最优解来确定图像的最佳分 割阈值。仿真结果表明，与遗传算法相比改进后的贝叶斯优化算法可以得到 更好的图像分割效果。目前国内外还没有将贝叶斯优化算法应用于图像分割 的论文发表，本文将贝叶斯优化算法引入到图像分割当中，不但拓展了算法 哈尔滨工程大学硕士学位论文 的应用领域，还可以为图像分割寻求新的解决途径。 关键词：贝叶斯优化算法；免疫算法；图像分割：计算量 哈尔滨工程大学硕士学位论文 a b s t r a c t 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 mf e n a s ) t h a ti n c o r p o r a t ep r o b a b i l i t y m o d e li n t oo p t i m i z a t i o na l g o r i t h m sh a v eb e c o m ean e wk i n do fo p t i m i z a t i o n a l g o r i t h m i tu s e ss t a t i s t i c a ll e a r n i n gt ob u i l dap r o b a b i l i s t i cm o d e l ，a n du t i l i z e s t h em o d e lo ft h es a m p l et oa c h i e v et h ee v o l u t i o no fp o p u l a t i o n s b a y e s i a n o p t i m i z a t i o na l g o r i t h m ( b o a ) i sar e p r e s e n t a t i v e o n ea m o n ge d a s i th a st h e a d v a n t a g e so fa c c u r a t ep o s i t i o n i n g ，a n dc a na v o i dl i n k a g ep r o b l e me f f i c i e n t l y h o w e v e r , t h ei n t r o d u c t i o no fs t a t i s t i c a ll e a r n i n gw i l lb r i n ga b o u tan e wt i m ea n d s p a c ec o m p u t a t i o n a lc o m p l e x i t y b a y e s i a no p t i m i z a t i o na l g o r i t h m h a sb e e n l i m i t e di ne n g i n e e r i n gp r a c t i c eb e c a u s ei tr e q u i r e sn o to n l yap r i o r ik n o w l e d g e ， b u ta l s oe x p e n s i v ec o m p u t a t i o n a lc o m p l e x i t yi nb u i l d i n gap r o b a b i l i s t i cm o d e l t h ec o r eo fb o ai sb a y e s i a nn e t w o r k ，a n di t sc o m p u t a t i o n a lc o m p l e x i t yi s a l s oc o n c e n t r a t e di nt h ec o n s t r u c t i o no fb a y e s i a nn e t w o r k i no r d e rt od e c r e a s e c o m p u t a t i o n a lc o m p l e x i t y , a ni m p r o v e db a y e s i a no p t i m i z a t i o na l g o r i t h mb a s e do n i m m u n ea l g o r i t h mi sp r e s e n t e d t h i sa l g o r i t h mi n t e n d st od e c r e a s ec o m p u t a t i o n a l c o m p l e x i t yo fb o ab yr e d u c i n g t h en u m b e ro fc o n s t r u c t i o no fb a y e s i a nn e t w o r k t h ei m m u n ea l g o r i t h mb ys i m u l a t i n gt h eb o d y si m m u n em e c h a n i s mc a nt a k e a d v a n t a g eo fap r i o r ik n o w l e d g eo ft h ep r o b l e ma n dl o c a lf e a t u r e st og u i d et h e o p t i m i z a t i o np r o c e s sa n di m p r o v et h ec o n v e r g e n c es p e e d t h e r e f o r e ，i m m u n e a l g o r i t h mi si n t r o d u c e di n t ob o a b yu t i l i z i n gt h ei m m u n ea l g o r i t h m sg u i d e d m u t a t i o n ，t h es o l u t i o n sg e n e r a t e db yb a y e s i a nn e t w o r ka r ei m p r o v e d ，a n dt h e c o n s t r u c t i o nt i m e so fb a y e s i a nn e t w o r ki sr e d u c e d e x p e r i m e n t a lr e s u l t ss h o w t h a t b yc o m p a r e d w i t ht h eb o a , t h ep r o p o s e da l g o r i t h mc a l lr e d u c et h e c o m p u t a t i o n a lc o m p l e x i t ye f f i c i e n t l y a n ds h o r t e nc o m p u t a t i o n a lt i m e ，a n dh a s s t r o n g e ra b i l i t yo fo p t i m i z a t i o n i no r d e rt os o l v et h ep r o b l e mo fl o c a lo p t i m u mi ni m a g es e g m e n t a t i o n ， i卜-，、 哈尔滨工程大学硕士学位论文 i m p r o v e db a y e s i a no p t i m i z a t i o na l g o r i t h mi si n t r o d u c e di n t oi m a g es e g m e n t a t i o n i tu s e st h eo p t i m i z a t i o nc a p a b i l i t yo fb o at os e e ko p t i m a li m a g es e g m e n t a t i o n t h r e s h o l d t h ep r o p o s e da l g o r i t h mu s e st h eb a y e s i a nn e t w o r kt oe n c o d et h ep i x e l ， a n dm a k e su s eo fb a y e s i a nn e t w o r ks a m p l i n gt og e n e r a t ean e wp i x e lv a l u e i t h s e st h em a x i m u mb e t w e e n c l a s sv a r i a n c em e t h o dt od e t e r m i n et h ef i t n e s s f u n c t i o n ，a n ds e a r c h e sf o rt h eb e s ts o l u t i o na st h eo p t i m a ls e g m e n t a t i o nt h r e s h o l d s i m u l a t i o nr e s u l t ss h o wt h a tb yc o m p a r e dw i t ht h eg a , t h ei m p r o v e db o a a l g o r i t h mh a v ea b e t t e ri m a g es e g m e n t a t i o nr e s u l t s i nt h ep r e s e n t ，t h ep a p e r so f a p p l i c a t i o n o fb a y e s i a no p t i m i z a t i o na l g o r i t h mi ni m a g es e g m e n t a t i o na r e p u b l i s h e da th o m ea n da b r o a d t h em e t h o dp r o p o s e di n t h i sp a p e rn o to n l yt o e x t e n dt h i sa l g o r i t h m sa p p l i c a t i o nf i e l d ，b u ta l s of o ri m a g es e g m e n t a t i o nt of i n d n e ws o l u t i o n s k e yw o r d s ：b a y e s i a no p t i m i z a t i o na l g o r i t h m ；i m m u n ea l g o r i t h m ；i m a g e s e g m e n t a t i o n ；c o m p u t a t i o n a lc o m p l e x i t y 一一r- ， 一- 哈尔滨工程大学硕士学位论文 目录 第1 章绪论l 1 1 课题研究的目的及意义1 1 2 课题的国内外研究现状。2 1 2 1 分布估计算法的国内外研究现状2 1 2 2 免疫算法的国内外研究现状6 1 3 课题研究内容及论文安排8 第2 章贝叶斯优化算法的基本原理1 0 2 1 连锁学习问题概述。1 0 2 2 传统的贝叶斯优化算法1 2 2 - 3 贝叶斯网络1 3 2 3 1d 分隔。1 5 2 3 2 贝叶斯网络的结构学习1 9 2 3 3 贝叶斯网络的参数学习2 3 2 3 4 贝叶斯网络采样2 6 2 4 本章小结2 7 第3 章人工免疫算法2 8 3 1 人工免疫算法综述2 8 3 2 免疫规划算法2 9 3 3 本章小结3 2 第4 章基于免疫算法的贝叶斯优化改进算法。3 3 4 1 确立节点顺序3 3 4 1 1 无向图的建立3 4 4 1 2 无向图的搜索3 4 4 2 基于免疫算法的贝叶斯优化算法具体实现流程3 6 4 3 实验仿真与结果分析。3 8 啥尔滨工程大学硕士学位论文 4 3 1 实验条件3 8 4 3 2 仿真结果分析3 8 4 4 本章小结4 2 第5 章改进贝叶斯优化算法在图像分割中的应用4 3 5 1 图像分割方法概述4 3 5 2 基于改进贝叶斯优化算法在图像分割中的具体流程4 7 5 3 实验仿真与结果分析4 8 5 4 本章小结5 2 结论5 3 参考文献5 5 攻读硕士学位期间发表的论文和取得的科研成果6 0 致谢6 1 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1 课题研究的目的及意义 分布估计算法的概念最初是由德国学者于1 9 9 6 年提出，2 0 0 0 年前后受 到广大学者的关注，成为进化算法领域一种新型的优化算法。它同遗传算法 类似，主要是将概率模型引入到遗传算法当中，它是采用统计学习的手段从 群体宏观的角度建立一个描述候选解在空间分布的一个概率模型，然后对概 率模型随机采样产生新的种群，如此反复进行，实现种群的进化，直到达到 终止条件循环结束。分布估计算法不使用交叉和变异等遗传算子产生新解， 而是从较优的解集中提取信息，利用信息构造合适的概率分布，然后再根据 概率分布产生新解，这样就不会破坏基因块的连锁依赖关系，从而避免连锁 问题。 分布估计算法已成为当前进化计算领域前沿的研究内容，2 0 0 5 年在进化 计算领域权威的国际期刊e v o l u t i o n a r yc o m p u t a t i o n 上出版了分布估计算法的 专刊，近年来国际上进化计算领域的各大学术会议，如a c m s i g e v o 、 i e e e c e c 等，都将分布估计算法作为重要专题予以讨论【1 】o 目前分布估计算 法已经应用到模式识别、整数规划、特征选择、路径规划、多目标的优化设 计及多维背包问题等【1 1 。 分布估计算法是一种新型的优化算法，在算法设计、理论研究和算法应 用方面还不完善，仍然有许多地方需要进一步研究，作为一种新型的优化技 术，分布估计算法的核心是解空间的概率模型，针对特定的优化问题，应综 合考虑搜索空间的结构、概率模型的学习算法、样本产生算法等【1 1 【2 】。但是， 统计学习的引入会给分布估计算法带来了新的时间和空间开销，在构建概率 模型时，它不但需要先验知识，而且计算量很大，因此如何降低计算量是分 布估计算法理论研究亟待解决的问题。 免疫算法是基于生物免疫系统理论而提出的多个算法的统称，它是在进 哈尔滨工陧大学硕士学位论文 化算法理论框架基础上引入免疫算子而形成的一种新的优化算法，因其具有 较好的种群多样性、记忆性及较好的稳定性而被广泛应用。 本文将以分布估计算法中的典型代表贝叶斯优化算法为研究重点，对各 种改进算法的优缺点进行对比分析，并针对算法的不足之处在深入理论分析 的基础上进行算法改进，旨在降低贝叶斯优化算法的计算量，提高算法性能； 同时由于贝叶斯优化算法不易陷入局部最优且具有连锁学习能力，本课题将 提出一种基于贝叶斯优化算法的图像分割方法。目前国内外还没有贝叶斯优 化算法在图像分割中应用的论文发表，本课题将在深入研究贝叶斯优化算法 原理的基础上探索其在图像分割领域的应用。 1 2 课题的国内外研究现状 1 2 1 分布估计算法的国内外研究现状 分布估计算法是利用概率模型来描述变量之间的相互关系，从而用其来 描述和表示每一代个体【3 】，因此可以用来解决传统遗传算法难以解决的问题， 特别是处理复杂多变量优化问题及不同编码位之间具有相互关系的问题上， 表现出了很好的性能1 4 j 。 在算法研究方面，国内外学者设计了许多种不同的概率模型来表示变量 之间的关系，从而演化成多种算法，主要可以归为以下几类： ( 1 ) 变量无关的分布估计算法 在分布估计算法领域的研究中，最简单的情况是假设所有变量之间相互 独立，即所有变量之间没有相互关系。在这种情况下，一般的可以用一个简 单的概率向量表示解的分布，即确定变量取“1 或取“0 的概率【习，因此 分布估计算法最初是针对变量无关的问题提出。美国卡耐基大学的b a l u j a 在 1 9 9 4 年提出的用于解决二进制编码优化问题的p b i l ( p o p u l a t i o n b a s e d i n c r e m e n t a ll e a m i n g ) 算法【6 | ，它被学术界公认为最早的分布估计算法。 在p b i l 算法基础上，美国u i u c 大学的h a r i k 等人提出了压缩遗传算法 ( c o m p a c tg e n e t i c a l g o r i t h m ，简称c g a ) 7 1 ，此算法的基本思想和p b i l 算 2 哈尔滨工程大学硕士学 立论文 法类似，但是随机变量的更新规则不同，压缩遗传算法实现更加简单方便， 并可快速判定问题的复杂程度，是一种适合于硬件实现的分布估计算法。 此外，1 9 9 7 年德国学者又提出了单变量边缘分布估计算法( u n i v a r i a t e m a r g i n a ld i s t r i b u t i o na l g o r i t h m ，简称u m d 算法【8 1 ，它是p b i l 算法的一种 特殊情况，即p b i l 算法中学习率口一1 的情况，该算法的优点是全局的搜索 能力较强，但局部搜索能力被适当的减弱。 ( 2 ) 双变量相关的分布估计算法 p b i l 、u m d a 和c g a 算法的前提是变量之间是相互独立的，因此它们 在处理变量独立或者线性问题时，具有和遗传算法相当甚至更好的性能，并 且算法中任意解向量的联合概率分布都可以通过各个独立分量的边缘概率密 度相乘得到，简单易于实现【1 1 。而在实际问题中，变量之间完全独立的问题 比较少，应用领域受到限制。而比变量相互独立相对宽松一点的假设是最多 有两个变量相关，因此分布估计算法最先考虑变量相关性的算法是假设变量 之间两两相关。 1 9 9 7 年，美国m r r 人工智能实验室的d eb o n e t 等人提出了相互信息最 大输入聚合的算法( m u t u a li n f o r m a t i o nm a x i m i z i n gi n p u tc l u s t e d n g ，简称 m i m i c 算法) 9 】，m i m c 算法是将所有随机变量之间的关系假设成链式关系， 即只有相邻节点之间存在关系。该算法首先根据选择的优势群体构造概率模 型，再通过逆序采样并根据各个节点的条件概率产生新的个体。 1 9 9 7 年，b a l u j a 也提出解决双变量相关的分布估计算法c o m i t 算 法【1 0 】，它用树状结构的概率模型来代替m i m i c 中的链式结构，使得树中父 子节点的相关信息达到最大。c o m i t 算法利用两个变量之间的互信息将构建 最优的概率模型过程转化为寻找使互信息达到最大的最优树结构的过程，然 后将得出的概率树按照由上到下的顺序进行采样，并利用采样得出的新个体 来构造新种群【1 1 l 。 1 9 9 9 年，p e l i k a n 等人提出了二次边缘分布算法( b i v a r i a t em a r g i n a l d i s t r i b u t i o na l g o r i t h m ，简称b m d a ) 算法 埘，它的概率模型变成了森林结构， 哈尔滨工程大学硕士学虚论文 即一个树结构的集合。在每一棵树中，每一个节点只与其父节点相关，不同 树之间是条件独立的。因为链式结构、树状结构都属于森林结构的特殊情况， 因此b m d a 算法的概率模型包括m i m i c 算法和c o m i t 算法的概率模型， 即b m d a 具有更一般的意义和更好的准确度。 ( 3 ) 多变量相关的分布估计算法 随着研究问题的逐渐深入，变量之间两两相关的关系已经越来越不能满 足实际应用的要求，因此最近几年研究更多的是多变量相关的分布估计算法。 在这种算法中，将使用更加复杂的图结构来描述变量之间的相互关系，构造 相应的概率模型。 为解决多变量相关的优化问题，德国学者于1 9 9 9 年提出了比例分布算法 ( f a c t o r i z e dd i s t r i b u t i o na l g o r i t h m ，简称f d a ) 算法【1 3 】，这种算法需要专家事 先给出变量之间的相互关系，但许多情况下，很难得到变量之间的相互关系 ( 比如说黑箱优化问题) ，这时就很难采用f d a 算法进行优化，同时也限制 了f d a 算法的应用范围。 1 9 9 9 年，美国u i u c 大学的h a r i k 等人提出的扩展压缩遗传算法( e x t e n d e d c o m p a c t e dg e n e t i ca l g o r i t h m ，简称e c g a ) 算法【1 4 】，e c g a 算法是c g a 算法 的扩展，它是将所有变量划分成一些彼此独立的变量组，即每组变量都与其 它组变量无关，这样就可以在每组上使用c g a 算法进行求解，而变量的联 合概率分布就是各组变量的边缘概率分布的乘积。e c g a 算法是将多变量相 关关系转化成单变量边缘分布计算问题，简单且易于实现，但对于现实中变 量组有交叠问题，e c g a 算法难以搜索到一个准确的概率模型，因此表现出 较差的性能【1 5 】。 美国u i u c 大学p e l i k a n 等人提出了贝叶斯优化算法( b a y e s i a n o p t i m i z a t i o na l g o r i t h m ，简称b o a 算法) ，并于2 0 0 5 年出版了第一本关于贝 叶斯优化算法的专著【1 6 1 。它首先通过选择优势群体来作为样本集，并利用样 本集的信息来构造贝叶斯网络，然后对贝叶斯网络进行采样从而产生新一代 种群，反复进行直到得到问题的最优解。b o a 算法的核心是贝叶斯网络，它 4 哈尔滨工陧大学硕士学位论文 是通过对贝叶斯网络的采样来实现种群的进化。 贝叶斯优化算法是一种新兴的优化算法，提出时间较短，有许多问题还 没有解决，因此近年来对贝叶斯优化算法的相关理论和应用研究很多，针对 贝叶斯优化算法的缺点和不足，提出了许多改进算法。为了使用更加复杂的 模型来描述问题，从而使问题描述的更加精确，有人提出了决策图贝叶斯优 化算法( b a y e s i a no p t i m i z a t i o na l g o r i t h mw i t hd e c i s i o ng r a p h s ，简称d b o a 算 法) ，它是采用局部结构决策图对贝叶斯网络结构进行学习，从而减少大量参 数，并提高局部搜索能力，但却增加了问题的计算复杂度【1 7 】。在d b o a 算法 的基础上引入了小生境技术和分块技术，从而提出了层次贝叶斯优化算法 ( h i e r a r e h i e a lb a y e s i a no p t i m i z a t i o na l g o r i t h m ，简称h b o a 算法) ，它不但解 决了层次陷阱问题还提高算法的求解效率【1 8 l 。多目标贝叶斯优化算法 ( m u l t i o b j e c t i v eb a y e s i a no p t i m i z a t i o na l g o r i t h m ，简称m b o a 算法) ，可对 多个目标同时优化，解决了贝叶斯优化算法在多目标中应用的问题。 此外，梁瑞鑫等人于2 0 0 4 年提出了一种混沌贝叶斯优化算法，该算法利 用混沌随机性、遍历性和对初始条件的敏感性的特点，提供给贝叶斯网络变 量空间丰富的信息，有利于建立接近最优的贝叶斯网络，并采用混沌搜索方 法对贝叶斯网络产生的新解进行变异寻优，以此增加群体的多样性【1 9 】。 钟小平等人于2 0 0 6 年提出了改进的贝叶斯优化算法，该算法引入了免疫 算法中的亲和度和浓度概念，将个体适应度概率和个体浓度概率相结合，形 成贝叶斯优化算法选择优良个体的依据。这样，由低浓度、高适应度个体组 成优良个体种群，能够保持种群的多样性，提高算法的性能【2 0 】。 分布估计算法在国内起步较晚，但目前也已经取得一些成绩。如：利用 最大熵原理降低算法的计算复杂度【2 l 】；利用小生境概率主成分分析的方法来 避免早熟收敛，提高算法的全局搜索效率【2 2 】；利用松弛互补的方法来提高分 布估计算法的搜索效率等。在应用领域，国内主要集中于多目标的优化设 计、故障诊断、非线性整数规划、输电网扩展规划、多维背包问题等领域。 近年来的实验分析表明，分布估计算法在求解问题时具有比遗传算法更 5 哈尔滨工程大学硕士学位论文 好的性能，在解决实际应用中的复杂优化问题具有很大的潜力。因此最近几 年来，越来越多的学者对分布估计算法的研究产生了兴趣，并逐渐成为当前 进化计算领域前沿的研究内容。而贝叶斯优化算法作为分布估计算法的典型 代表，在求解复杂问题时有其独特的优势，特别是针对n p 问题，它表现出 良好的性能。但在构建贝叶斯网络模型时需要较高的计算量，使贝叶斯优化 算法在求解复杂优化问题时需要较长的运算时间，从而限制了算法的应用。 1 2 2 免疫算法的国内外研究现状 免疫算法和免疫系统的理论与应用研究时间较短，最早与免疫算法相关 的理论可追溯到1 9 5 8 年澳大利亚学者b u m e t 提出的基于生物抗体的克隆选 择学说【2 4 1 。这一学说的基本观点是克隆是一种无性繁殖，在不发生基因突变 时具有完全相同的基因结构，能够在抗原入侵机体时迅速产生大量相应的免 疫细胞来消灭抗原，同时为了保持免疫细胞的多样性，又有一定的几率发生 基因突变，从而使机体内的免疫细胞的多样性达到一定程度。 在b u r n e t 克隆选择学说的基础上，j e m e 于1 9 7 3 年提出了独特型网络理 论，并给出了免疫系统的数学框架，该框架利用微分方程来仿真淋巴细胞的 动态变化，是最早的免疫系统数学模型【2 5 1 。此后，f a r m e r 、p e r e l s o n 和v a r e l a 等理论免疫学者分别在1 9 8 6 、1 9 8 9 和1 9 9 0 年发表了有关免疫系统实际应用 的论文，为人工免疫算法的应用做出了突出贡献【2 酬。2 0 0 1 年c o n g r e s so n e v o l u t i o n a r yc o m p u t a t i o n 国际学术会议组织了第一届免疫算法的相关专题讨 论会，并在今后每年都要举办一届，从而大大提高了国际学者研究和应用免 疫算法的热情，使免疫算法成为继模糊系统、人工神经网络和进化算法之后 在人工智能领域的又一个研究热点。 1 9 9 4 年，美国n e wm e x i c o 大学计算机科学系的f o r r e s t 博士通过研究免 疫系统中识别自我细胞和非我细胞的免疫机制而提出了否定选择算法，该算 法又被人称为阴性选择算法或负筛选算法。因为该算法可以通过匹配算法来 检测系统异常，因此常应用于计算机病毒检测和网络安全等问题上【2 7 j 团1 。 哈尔滨工程大学硕士学位论文 1 9 9 7 年c h t m 等人为了解决遗传算法的易陷入局部最优或早熟问题，将 免疫理论和遗传算法相结合，提出一种免疫遗传算法( i m m u n eg e n e t i c a l g o r i t h m s ) 2 9 1 。该算法综合了免疫算法与遗传算法的优点，尤其是对多峰值 的目标函数具有很好的性能。 2 0 0 0 年，d ec a s t r o 等人在克隆选择学说的基础上提出一种克隆选择算法 ( c l o n i n gs e l e c t i o n a l g o r i t h m ) 1 3 0 1 。该算法将问题的求解过程转换成免疫系统的 免疫过程，通过模拟免疫克隆中细胞的复制、变异等过程来搜索全局最优解， 该算法适用于求解复杂函数优化问题。 2 0 0 5 年，g o n z a l e z 等人为了解决解的准确率过度依赖于参数而提出了一 种自适应非选择算法，该算法采用自适应变异技术来调节进化过程中的变异 概率并取得了较好的效果【3 1 】。 虽然国内对免疫算法的研究较国外迟，但许多学者也都致力于免疫算法 理论和应用的研究。中国科学技术大学的王煦法教授等首先开始对免疫算法 进行研究，并于1 9 9 9 年提出了一种新的免疫遗传算法，他将免疫系统中的自 适应性及抗体浓度抑制原理引入遗传算法，并将其成功应用于t s p 问题，改 善了遗传算法中未成熟收敛问题【3 2 j 。 2 0 0 3 年，罗小平将免疫遗传学的基本思想引入到优化设计中，提出了一 种新的免疫遗传算法，并将其应用于多峰函数的寻优过程中，结果表明该算 法能有效地解决局部搜索能力和全局搜索能力的矛盾、有效维持种群多样性、 较好地防止早熟现象【3 3 】。 2 0 0 4 年，刘若辰等将多克隆算子应用于进化算法，提出了免疫多克隆策 略算法，并利用m a r k o v 链的相关性质，证明了该算法的收敛性，该算法与 传统的优化算法相比，既保持了抗体的多样性，而且收敛速度很快p 】。 2 0 0 6 年，王孙安等人通过对免疫算法性能的探讨提出了一种混沌免疫优 化组合算法，该算法综合了免疫进化算法全局搜索能力强与混沌优化算法局 部搜索能力强的优势，将混沌变量加载于免疫算法的变量群体，利用混沌搜 索的特点对记忆库群体进行优化，改善了免疫进化算法的收敛性能，搜索效 7 哈尔滨工程大学硕士学位论文 率也得到了提高【3 5 1 。 2 0 0 9 年，缑水平等人提出了一种基于免疫克隆选择的核匹配追踪集成图 像识别算法，该算法充分利用免疫克隆算法的快速收敛于全局最优解的特性， 对训练得到的多个子核匹配追踪分类器进行免疫克隆选择，从而得到一个具 有更好推广性能的集成系统，并对b r o d a t z 纹理图像库以及s a r 图像进行目 标识别，取得了令人满意的效果【3 6 1 。 免疫算法具有较好的种群多样性、记忆性等许多优秀性能，它作为一种 崭新的优化方法逐渐引起了众多学者的注意，最近几年在计算机、工业、军 事等多种领域都得到了广泛的应用，不过由于起步较晚，其理论研究及应用 还有待于进一步加强。同时国内外的研究成果显示了免疫算法对于信息处理 和优化问题求解具有广阔的应用前景，其与贝叶斯优化算法相结合，降低贝 叶斯优化算法的计算量尚未发表文献。 1 3 课题研究内容及论文安排 本课题将主要对分布估计算法中的典型代表贝叶斯优化算法进行研究， 归纳算法的成功应用领域和存在的不足，并针对贝叶斯优化算法高计算量的 问题，在深入理论分析的基础上应用免疫算法对概率模型产生的解进行进一 步优化，目的在于提高种群的平均适应度，降低计算量。此外，将改进后的 贝叶斯优化算法应用于图像分割，并利用计算机实现仿真。为此本论文的具 体内容安排如下： 第1 章为绪论。首先介绍了分布估计算法的研究目的、意义及目前国内 外研究现状，最后给出了本文的主要工作和内容安排。 第2 章主要介绍了分布估计算法的典型代表贝叶斯优化算法，首先介绍 了算法的提出背景和传统贝叶斯优化算法的基本框架，并重点介绍了贝叶斯 优化算法的核心贝叶斯网络的原理及实现过程，介绍了贝叶斯网络的几 种结构学习算法和参数学习算法，为后续算法改进做铺垫。 第3 章，介绍了免疫算法中四种主要算法，即否定选择算法、免疫遗传 哈尔滨工程大学硕士学位论文 算法、克隆选择算法及免疫规划算法，并分析各种算法的优缺点。 第4 章，详细介绍了改进贝叶斯优化算法的具体实现步骤，并通过实验 仿真验证了改进b o a 算法的优越性。 第5 章，将本文提出的基于免疫算法的贝叶斯优化改进算法应用于图像 分割，并进行了仿真实验，通过与传统的贝叶斯优化算法和遗传算法比较， 本文提出的改进算法具有理想的分割效果。 最后本文将总结归纳作者一年来在贝叶斯优化算法、免疫算法及改进算 法的研究及应用中所作的工作，并对其存在的不足和对未来的发展进行展望。 9 哈尔滨工程大学硕士学位论文 第2 章贝叶斯优化算法的基本原理 贝叶斯优化算法( b a y e s i a no p t i m i z a t i o n a l g o r i t h m ，简称b o a 算法) 是 分布估计算法中最典型的代表，为了表示多变量之间的相关性，它的概率模 型是更为复杂的贝叶斯网络。该算法的基本思想是利用贝叶斯网络的采样来 代替遗传算法中的交叉和变异，即利用较优解的联合概率分布构造出相应的 贝叶斯网络模型，然后对构造好的贝叶斯网络模型进行采样，生成新的候选 解。研究表明，贝叶斯优化算法具有较强的优化能力，其求解许多测试函数 都得到了很好的优化结果。因而，可应用贝叶斯优化算法来解决一些实际应 用中的n p 难或n p 完全问题。本章主要介绍b o a 算法的核心贝叶斯网 络的原理及其实现过程。 2 1 连锁学习问题概述 贝叶斯优化算法是为了解决连锁学习问题而提出来的一种新型的优化算 法，而连锁问题是人们研究遗传算法时发现的，普遍存在于传统优化算法当 中，它通常会造成算法早熟或达到局部最优，为了更好的理解贝叶斯优化算 法的优势，本章以遗传算法为例首先介绍一下什么是连锁问题。 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a 算法) 是基于染色体信息交换机 制和达尔文的“优胜劣汰”的生物进化理论而提出的一种优化算法，通 过模拟自然界中生物的选择、交叉和变异等遗传进化过程来搜索问题的 近似最优解，它最初由美国m i c h i g a n 大学j h o l l a n d 教授于1 9 7 5 年首先 提出来的，并出版了颇有影响的专著 a d a p t a t i o ni nn a t u r a la n da r t i f i c i a l s y s t e m s ) ) ，g a 这个名称才逐渐为人所知。遗传算法经过3 0 多年的发展已 取得了丰硕的应用成果和理论研究的进展，己经成功应用于工业、农业、自 动化等各个领域。但由于传统遗传算法一般都是采用固定的遗传操作来生成 子代，它的基本理论依据是“基因块”假设理论和模式定理【3 7 j 。 模式定理：在选择、交叉和变异的作用下，具有低阶、短定义距以及平 】0 哈尔滨工程大学硕士学位论文 均适应度高于群体平均适应度的模式在后代中将以指数级增长。 “基因块”假设理论：低阶、短定义距、高平均适应度的模式在遗传算 子的作用下，相互结合，能生成高阶、长定义距、高平均适应度的模式，最 终可生成全局最优解。 其中：模式阶是模式中确定位置的个数。比如模式料料书o 和1 0 0 1 ，它 们的模式阶分别是1 和4 ，其中水号表示该元素可以是1 也可以是0 ；定义距 是模式中第一个确定位置和最后一个确定位置之间的距离。比如模式书宰料o 和1 0 料o 宰，它们的定义距分别是o 和4 。 从统计理论可以看出，要获得最优的可行解，则必须保证较优解的数目 呈指数级增长。而模式定理保证了在一定的条件下较优模式的样本数呈指数 级增长，从而满足了寻找最优解的必要条件，即遗传算法存在找到全局最优 解的可能性。同时，基因块假设理论就是将这些好的模式看成一个个的积木， 在遗传操作下相互拼接、结合产生适应度更高的个体，即在遗传算子的操作 下，能生成高阶、长定义距、高平均适应度的模式，也就是数值越来越精确， 最终生成全局最优解。这也为遗传算法寻求最优解提供了理论依据。但由于 基因块( 也就是将可行解进行二进制编码的字符串) 的确定位之间可能存在 连锁依赖关系，而遗传