（计算机应用技术专业论文）多目标算法在多分类svm优化中的应用.pdf

武汉科技大学 硕士学位论文第1 页 摘要 基于p a r e t o 最优概念的多目标遗传算法是处理多目标优化问题的一个重要算法。遗传 算法的机理很适合多目标优化，因为遗传算法可以在一代模拟过程中找到多个p a r e t o 最 优解，通过适应度算法使种群收敛于p a r e t o 前沿。但是由于遗传算法在迭代过程中新个 体产生过程的随机性以及迭代过程中不接受局部劣解导致了搜索过程中丢失部分全局最 优解，使得多目标遗传算法在搜索效率上和精度上存在不足。 与遗传算法相比，禁忌算法中在局部最优解获取上性能更佳。禁忌算法利用禁忌表保 存搜索过程中的局部最优解，禁忌表可以控制搜索路径的选择，使得搜索的范围更大，同 时禁忌某些个体被选择，以避免陷入某个局部空间，禁忌表的使用增强了搜索算法获取全 局最优解的能力。禁忌算法中在利用禁忌表控制搜索路径的同时，采用。策略摆动 的策 略利用惩罚因子来控制劣解的选择，使得禁忌算法在选择过程中可以选择较差局部最优 解，该较差局部最优解再后经过若干代演化后，能够演化为全局最优解。禁忌算法的这些 特点可以弥补g a 算法在局部搜索中的缺点。本文根据遗传算法和禁忌的特点将遗传算法 和禁忌算法结合，提出了名为多目标遗传禁忌算法m o t s g a ( m u l t i o b j e c t i v eb a s e do n g e n e t i ca l g o r i t h ma n dt a b us e a r c h ) 的多目标优化算法。 为验证改进的多目标遗传禁忌算法的性能，本文将多目标优化算法应用到多类s v m 求最优参数的优化问题上。对于多分类s v m 参数优化问题，求解多类s v m 分类问题的 方法是将其转换为多个二分类s v m 问题，通过求解二分类s v m 来求解多分类s v m 。求 解分解后的多个二分类最优问题是多目标优化问题。将本文提出的m o t s g a 算法和传统 的m o g a 算法分别应用到多类s v m 分类问题，通过实验结果的对比，验证本文提出的 方法与传统的多目标遗传算法相比具有局部搜索能力强，不易陷入局部最优解的优点。 关键词：p a r e t o 多目标优化，遗传算法，禁忌算法，支持向量机，多类分类 第1 i 页武汉科技大学 硕士学位论文 a b s t r a c t m u l t i - o b j e c t i v eg e n e t i ca l g o r i t h mb a s e d o np a r e t o ( m o g a ) i so n eo ft h em o s ti m p o r t a n t a l g o r i t h m s t os o l v em u l t i o b j e c t i v ep r o b l e m s g e n e t i ca l g o r i t h mi s v e r y s u i t a b l ef o r m u l t i - o b j e c t i v ep r o b l e m s ，b e c a u s ea te a c hi t e r a t i o no fg e n e t i ca l g o r i t h m ，s e v e r a lb e s tp a r e t o r e s u l t sc a l lb es e l e c t e d ，a n db yu s i n gf i t n e s sf u n c t i o nt h eg e n e t i ca l g o r i t h mc a nc o n v e r g et ot h e p a r e t o - f r o n t b u tb e c a u s ed u r i n gt h ei t e r a t i o n so ft h eg e n e t i ca l g o r i t h m ，n e wg e n e r a t i o n s i t e m sa r ec r e a t er a n d o m l y , a n dg e n e t i ca l g o r i t h me x c l u d e sa l lt h ew o r s ci t e m so fe a c h g e n e r a t i o n , s o m eb e t t e rr e s u l t so ft h ep a r e t os e ta r el o s t t h i si st h ed i s a d v a n t a g eo ft h eg e n e t i c a l g o r i t h m b e c a u s et h em u l t i o b j e c t i v eg e n e t i ca l g o r i t h mu s e st h eg e n e t i ca l g o r i t h ma st h e s e a r c ha l g o r i t h m ，t h em u l t i - o b j e c t i v eg e n e t i ca l g o r i t h ma l s oh a st h ed i s a d v a n t a g ei ns e a r c h e f f i c i e n c ya n dp r e c i s i o n c o m p a r e 谢t l lg e n e t i ca l g o r i t h m ，t a b us e a r c ha l g o r i t h mh a st h ea d v a n t a g ei nl o c a ls e a r c h p r e c i s i o na n di n t e l l e c t i v es e a r c ha b i l i t y t a b us e a r c ha l g o r i t h mu s e st a b ul i s tt os a v et h el o c a l o p t i m a lr e s u l t sa n dt h es e a r c hr o u t e s t a b ul i s tc a l lc o n t r o lh o wt h er o u t ec a nb es e l e c t e d ，a n d t a b us o m ei t e m st oa v o i dt h es e a r c hp l u n g ei ns o m el o c a ls e a r c ha r e a t a b ul i s tc a nb u i l d u pt h e t a b us e a r c ha l g o r i t h m sa b i l i t yo ff i n d i n gt h eg l o b a l o p t i m a lr e s u l t s t h e “s t r a t e g i c o s c i l l a t i o n s t r a t e g yi nt h et a b us e a r c hu s e sp e n a l t yf a c t o rt oc o n t r o lw h e t h e ru s i n gs o m ew o r e r e s u l ta st h el o c a lo p t i m a lr e s u l t st og e tb e t t e rg l o b a lr e s u l t s t h e s ec h a r a c t e r so ft h et a b u s e a r c hc a l lr e m e d yt h ed i s a d v a n t a g eo ft h eg e n e t i ca l g o r i t h mi nt h el o c a ls e a r c h b a s eo nt h e c h a r a c t e r i s t i co ft h et a b us e a r c ha n dg e n e t i ca l g o r i t h m ，t h i st h e s i sc o m b i n et a b us e a r c ha n d g e n e t i c a l g o r i t h m t oc r e a t ean e wm u l t i o b j e c t i v e a l g o r i t h mn a m e d a sm o t s g a ( m u l t i - o b j e c t i v eb a s e do ng e n e t i ca l g o r i t h ma n dt a b us e a r c h ) i no r d e rt ov a l i d a t et h ea l g o r i t h mm o t s g ai se f f e c t i v e ，t h i st h e s i su s e st h em o t s g a a l g o r i t h mt of i n dt h eb e s tp a r a m e t e r sf o rt h em u l t i c l a s s e ss v mp r o b l e m t h em e t h o dt os o l v e t h em u l t i - c l a s s e s s v mp r o b l e mi s c h a n g et h em u l t i c l a s s e ss v mp r o b l e mt o s e v e r a l t w o - c l a s s e ss v m p r o b l e m s t h ep r o b l e mt of i n dt h eb e s tp a r a m e t e r so ft h eg r o u po f t h es e v e r a l t w o c l a s s e ss v m p r o b l e m si sam u l t i - o b j e c t i v ep r o b l e m t h ee x p e r i m e n ti su s e dm o t s g a a l g o r i t h ma n dm o g aa l g o r i t h mr e s p e c t i v e l yt os o l v et h em u l t i c l a s s e ss v mp r o b l e m t h e r e s u l t so ft h ee x p e r i m e n ts h o w e dt h a tt h em o t s g ah a st h ea d v a n t a g ei nt h el o c a ls e a r c ha b i l i t y , a n di se a s yt of i n dt h eg l o b a lb e s tr e s u l t k e yw o r d s ：p a r e t om u l t i - o p t i m i z a t i o n ；g e n e t i ca l g o r i t h m ；t a b us e a r c h ；s v m ；m u l t i - c l a s s c l a s s i f i c a t i o n 武汉科技大学 研究生学位论文创新性声明 本人郑重声明：所呈交的学位论文是本人在导师指导下，独立进行研 究所取得的成果。除了文中已经注明引用的内容或属合作研究共同完成的 工作外，本论文不包含任何其他个人或集体己经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文储豁哗晰幽 研究生学位论文版权使用授权声明 本论文的研究成果归武汉科技大学所有，其研究内容不得以其它单位 的名义发表。本人完全了解武汉科技大学有关保留、使用学位论文的规定， 同意学校保留并向有关部门( 按照武汉科技大学关于研究生学位论文收录 工作的规定执行) 送交论文的复印件和电子版本，允许论文被查阅和借阅， 同意学校将本论文的全部或部分内容编入学校认可的国家相关数据库进行 检索和对外服务。 论文作者签名： 指导教师签名： 露勉币 ， 弓 - 1 0 伤嵫臼 武汉科技大学硕士学位论文第1 页 1 1 本课题的研究背景和意义 第一章绪论 在科学和工程中存在很多针对多目标的优化问题m o p s ( m u l t i o b j e c t i v eo p t i m i z a t i o n p r o b l e m s ) ，例如：工作中，怎样安排能使所用时间最少，而产生的成果最多；股市中， 成本如何配置，才能使风险最小、收益最多等等，这些都是多目标优化问题。多目标优化 与单目标优化相比，复杂性更高，也更难于解决。单目标优化的最优解可以是一个或者几 个离散的解，但是多目标优化的最优解可能是一个连续的解集组，而且最优解集中的元素 ( 解) 之间没有可比性，各个目标之间可能存在着矛盾，即一个目标向其最优状态靠近了， 而另一个目标可能正远离自己的最优状态。 传统的多目标优化方法，如目标权重法、距离函数法以及转换为最小最大问题法【l 】 等都是通过特定的方式将m o p 转换成为单目标优化问题( s i n g l e - o b j e c t i v eo p t i m i z a t i o n p r o b l e m s o p ) ，这类方法需要比较多的先验知识，计算效率低，而且鲁棒性差，难以处 理目标噪声及变量空间不连续的情况，在运行中效果不佳。 进化算法( e a ，e v o l u t i o n a r ya l g o r i t h m ) ，也称演化算法采用种群搜索策略和群体间个体 间的信息交换的进化算法使得其进化结果不局限于单解，非常适合求解复杂的多目标问 题。而且进化算法不需要先验知识，能够快速解决传统方法难以解决的问题。1 9 8 4 年， s c h a f f e r 提出向量评估遗传算法( v e c t o re v a l u a t e dg e n e t i ca l g o r i t h m v e g a ) t 2 1 ，第一次实 现了将进化算法用在多目标问题。该算法采用传统的遗传算法实现多目标的选择和优化， 但是其本质上等同于将适应度向量线性组合为一个单值适应度函数，容易导致搜索向某个 特定的目标方向进行，产生遗传漂移现象。 以m o g a 3 】为代表的多目标优化算法在处理遗传算法中的种群问题时采取了p a r c t o 最优概念来选取所要优化的个体，同时采用自适应的小生境等技术来防止种群的过早收 敛。这些方法成为解决多目标优化的有效方法。 多目标优化算法的研究现状 基于p a r e t o 最优概念的进化算法克服了传统方法在计算效率低，鲁棒性差等缺点， 成为求解多目标优化问题的有效途径，也成为近年来多目标优化的研究热点。 进化算法( e a s ：e v o l u t i o n a r ya l g o r i t h m s ) 是一种模拟自然进化过程的随机优化方法。e a s 的起源可追溯至l j 2 0 世纪5 0 年代末，2 0 世纪7 0 年代以来产生了几种进化方法，如遗传算法 ( g a ：g e n e t i ca 1 9 0 r i t h i m ) 、进化规划( e p ：e v o l u t i o n a r yp r o g r a m m i n g ) 和进化策略( e s ： e v o l u t i o ns t r a t e g y ) 。进化算法是模拟多个体组成的群体的集体学习过程，其中每个个体表 示给定问题搜索空间中的一点，进化算法从任意个初始的群体出发，通过随机选择、变 异和交叉过程，使群体进化到搜索空间中越来越好的区域。目前在m o e a s ( m u l t i - o b j e e t i v e e v o l u t i o n a r ya l g o r i t h m s ) d p g a 作为主要进化模型被采用得最多，对它的研究与应用也最为深 第2 页武汉科技大学硕士学位论文 入。最近大量实例和迹象表明e a s 的机理最适合求解多目标优化，因为它们可在单轮模拟 过程中找到多个p a r e t o 最优解，通过逐代累积寻找具有某些特征的个体。甚至有的学者认 为，在多目标优化领域e a s 要优于其它盲目搜索方法】。虽然这种提法与最优化领域中的 “没有免费的午餐( n of r e el u n c h ) 定理【1 2 】不太吻合，但迄今为止还没有找到其它方法比e a s 更能有效地解决m o p s 。多目标进化算法在国外的许多应用案例和掀起的研究热潮已成为 事实。进化算法应用于多目标优化领域始于2 0 世纪8 0 年代中期。在1 9 9 1 1 9 9 4 年期间有几 种m o e a s 被提出来，后来这些方法及其变种在实际多目标优化问题中得到了成功的应用。 近年来一些学者集中研究了基于进化算法的多目标搜索中某些专门问题，如p a r e t o 最优前 端的收敛性、小生境技术和精英策略。 ， 代表成果有：f o n s e c a 和f l e m i n g t 3 】提出的基于排序的适应度赋值多目标遗传算法 ( m u l t i p l eo b j e c t i v eg e n e t i ca l g o r t h m ，m o g a ) ，h o r n ，n a f p l i o t i s 和g o l d b e r g t 4 j 提出的小生 境p a r e t o 遗传算法( t l l en i c h e dp a r e t og e n e t i ca l g o r i t h m ，n p g a ) ，s r i n i v a s 和d e b t 5 】提出的 非劣解排序遗传算法( n o n d o m i n a t e ds o r t i n gg e n e t i ca l g o r i t h m ，n s g a ) ，k n o w l e s 和c o m e t 6 1 提出的p a r e t o 解存档进化策略( t h ep a r e t oa r c h i v e de v o l u t i o ns t r a t e g y ，p a e s ) ，z i t z l e r 和 t 1 1 i e l e 【7 】提出的p a r e t o 浓度进化算法( t h es t r e n g t hp a r e t oe v o l u t i o n a r ya l g o r i t h m ，s p e a ) ， z i t z l e r ，l a u m a n n s 和t h i e l e 8 】提出的改进p a r e t o 浓度进化算法( s p e a 2 ) ，d e b ，p r a t a p ，a g a r w a l 和m e y a r i v a n 9 】提出的改进非劣解排序遗传算法( n s g a i i ) 。 1 3 本文的主要工作 本文首先对基于p a r e t o 的多目标优化算法的思想以及进化算法进行全面的介绍，之 后论述将g a 算法应用到多目标优化问题中存在的不足之处，针对g a 算法的不足之处提 出用禁忌算法与g a 算法相结合来弥补g a 算法局部搜索能力差，容易陷入局部最优解的 问题。用改进后的遗传禁忌算法应用在p a r e t o 多目标优化算法上，提出了多目标遗传禁 忌算法m o t s g a ( m u l t i p l eo b j e c t i v ea l g o r i t h mb a s e do ng e n e t i ca l g o r i t h ma n dt a b us e a r c h a l g o r i t h m ) 。并用改进的多目标优化算法m o t s g a 算法来解决多类s v m 中核参数和惩罚 函数的优化问题。通过实验表明，针对求解多类s v m 中核参数和惩罚函数优化的问题， m o t s g a 算法在搜索的精度上和搜索空间的覆盖方面都取得了较好的效果。 1 4 本文的结构安排 本文分为六章，各章内容组织如下： 第一章简要介绍了多目标优化的研究背景及意义、分析了国内外的研究现状，并 介绍了本文的主要工作及结构安排。 第二章介绍了多目标优化的基本知识，包括多目标优化的数学描述、经典的多目 标优化算法、多目标优化算法中存在的问题。 第三章首先介绍了简单禁忌算法的基本原理和算法的基本流程；其次针对多目标 武汉科技大学 硕士学位论文第3 页 优化中p a r e t o 集合的处理问题，将禁忌搜索算法引入到多目标遗传算法中 来，对多目标禁忌算法进行改进，提出了一些改进策略；最后对本文提出 的多目标遗传禁忌算法的具体步骤进行了阐述。 第四章介绍了r b f 核函数下的多类s v m 中优化过程中参数选择的原理，以及应 用多目标优化进行多类s v m 参数优化的优势所在，同时论述如何应用 m o t s g a 算法解决r b f 核函数下多分类s v m 算法参数优化问题。 第五章分别根据g a 算法、m o g a 算法和m o t s g a 算法分别进行多类s v m 参数 优化的实验，通过实验结果的比较，说明m o t s g a 算法的优势所在。 第六章总结了本文的创新点和不足之处，并对将来的工作做出了展望。 第4 页武汉科技大学硕士学位论文 第二章多目标优化算法 2 1 多目标优化问题的数学描述 定义lm o p ：一般m o p ( m u l t i o b j e c t i v eo p t i m i z e sp r o b l e m ) 由刀个决策变量参数、k 个目标函数和m 个约束条件组成，目标函数、约束条件与决策变量之间是函数关系。最 优化总目标如下： m 舣i m i 趵y = f ( x ) = ( z ( 工) ， ( 工) ， ( x ) ) ( 2 1 ) s u b 曩e c tt op ( 工) = ( p i ( 工) ，e 2 ( z ) ，e 。( 工) ) 0 ， 其中，x = “，而 ) 置j ，= ，咒以) z 这里x 表示决策向量，y 表示目标向量，x 表示决策向量z 形成的决策空间，y 表示 目标向量j ，形成的目标空间，约束条件e ( x ) o 确定决策向量可行的取值范围。 m o p 的本质在于大多数情况下各个子目标可能是相互冲突的，某个子目标的改善可 能引起其他子目标性能的降低，即同时使多个子目标均达到最优一般是不可能的，否则就 不属于多目标优化的研究范畴。解决m o p 的最终手段只能是在各个目标之间进行协调权 衡和折衷处理，使各个子目标函数均尽可能达到最优。因此m o p 的最优解与单目标最优 化问题的最优解有着本质的区别。为了正确求解m o p ，必须对其解的概念进行定义。 定义2 可行解集：可行解集x ，定义为满足式( 2 1 ) 9 约束条件e 的决策向量x 的集 合，即 x x = x x l e ( x ) o ) ( 2 2 ) 母的图形( 即可行区域) 所对应的目标空间的表示为： 弓= 厂( ) = k x ， 厂( x ) ) ( 2 3 ) 式( 2 2 ) 的物理意义是：对于可行解集x f 中的所有x ，经优化函数映射形成目标空间 中的一个子空间，该子空间的决策向量均属可行解集。 定义3 p a u r e t o 最优解：对于集合a x ，决策向量石x i 为非劣的当且仅当 刁口a ：a - j ( 即不存在向量a 优于向量力，x 是p a r e t o 最优解当且仅当工在琦中非 劣。求解这样一个p a r e t o 目标最优解的问题被称为p a r e t o 多目标优化问题。 2 2 传统的多目标优化方法及其局限性 传统的多目标优化方法是将各目标聚合成一个为正系数的单目标函数，系数由决策者 武汉科技大学 硕士学位论文第5 页 来决定，或由优化方法自动调整。为了获取近似p 删。最优解集，一些优化方法使用不同 的系数来实施动态优化。常见的方法有加权法、约束法、目标规划法和极小极大法。在本 文中对前两种方法进行简单介绍。 2 2 1 加权法 加权法是通过目标函数的线性组合将m o p 转换成单目标问题： m a x i l i l 娩ey = 厂( 功= ( 国l a ( x ) + 国2 a ( 工) + + q 以( x ) ) ( 2 4 ) 螂称为权重，不失一般性通常可正规化使q = 1 ，求解上述不同权重的优化问题后 输出一组解。 如果所有权重取值为正值，该方法可以获得一些p 础舶最优解，该方法是通过增加权重 后获得求解单一目标的函数，根据函数的数学特性获取其极大值，使得转化后的单目标函 数获得极大值的p 删。最优解可以通过该方法获得，但是不能使该转换函数取得极大值得 p 盯e t o 最优解就无法从该方法中得到，这是该方法的最大缺点即无法获取所以的p a r e t o 最优 解。 2 2 2 约束法 约束法是一种不局限于优化p a r e t o 最优前端凸部的方法，它将阶目标中的舡1 个目标转 换成约束条件，剩下的一个目标( 可随意确定) 作为单目标函数。其模型如下： m a x i m i z ey = f ( x ) = ( a ( 工) ) s u b j e c tt oe ( x ) = ：( x ) 占，( 1 f k ，f j 1 1 ) ，工j ， ( 2 5 ) 占；作为下界可在优化过程中取不同值，以发现多个p a r e t o 最优解。 该方法的缺点在于必须准确的确定s ，的取值范围，否则转化后的单目标函数可能出现 无解的情况，这就势必对s i 的取值范围进行多次优化，以求的合适的取值范围。另外无论 占：取何值，都会在一定程度上缩小了搜索空间的目标空间，即缩小了可行区域的范围，和 加权法一样，不能获得全部的p a r e t o 最优解。 2 2 3 传统多目标方法的分析 传统方法的优点在于继承了求解单目标优化的一些成熟算法韵机理。但对于大规模问 题，这些多目标优化方法很少真正能被使用。原因在于：( 1 ) 一些古典方法如加权法求解多 目标优化问题时，对p a r e t o 最优前端的形状很敏感，不能处理前端的凹部；( 2 ) 求解问题所 第6 页武汉科技大学硕士学位论文 需的与应用背景相关的启发式知识常常不能获得，导致无法正常实施优化。 传统方法共同存在的一个问题就是为了获得p a r c t o 最优解集则必须运行多次优化过程， 由于各次优化过程相互独立，往往得到的结果很不一致，令决策者很难有效决策，而且要 花费很多开销时间。d e b 曾研究过这些方法的一些其它潜在问题，如使用领域范围的限制 竺0 0 寸o 最近进化算法已经作为一种多目标优化方法崭露头角。它的优点在于可处理大规模的 搜索空间、在单轮优化期间产生多个均衡解，可有效克服古典方法的局限性。 2 3 多目标进化算法 e a s 的机理很适合求解多目标优化，因为它们可以在单论模拟过程中找到多个p a r e t o 最 优解，通过逐代组合寻求最具某些特征的个体，这些特征可以根据实际问题具体求得，甚 至有学者认为，在多目标优化领域e a s 要优于其他盲目搜索方法。在多目标进化算法中， 遗传算法g a 被采用的最多，对其研究和应用也是最为深入。 2 3 1 多目标进化算法及分类 通常利用进化算法求解m o p 期望实现的目标包括：( 1 ) 进化结果的非劣前端与p a r c t o 最 优前端的距离最短；( 2 ) 期望进化结果分布性能好( 通常为均匀分布) ；( 3 ) 获得的非劣前端范 围很大，即非劣解的值覆盖每个目标的尽可能宽的范围。 近年来众多学者研究如何基于进化算法实施多目标优化搜索，提出了各种方法。尽管 涌现出了许多种m o e a s ，但可依据某种特征将它们分f - j 另j 类。如果从决策的观点出发，可 以对现有的m o e a s 进行大致分类。依据最优解的形成与决策过程的交互方式，即先验方式、 交互式进程方式和后验方式，由此形成的m o e a s 层次分类如图2 1 所示。 l + 后验方式( 在后) + 协作搜索胁t o 选择 j ，一_ 捧序与小，扣境法 杂合选择； 类群法、排序法 图2 1 多目标进化算法的分类 武汉科技大学 硕士学位论文第7 页 先验方式是根据先验偏好知识将不同目标组合成一个标量代价函数，它在实施优化之 前将m o p 转换成单目标来求解。交互式进程方式是决策和优化过程同时进行，在实施优化 时使用部分偏好信息，优化过程则不断地为决策者提出更新的解集。后验方式是优化过程 在终止时向决策者提供一组p a r e t o 最优解，供其从中选择。目前基于p 盯e t o 的遗传算法在 m o e a 设计中占据主要地位。 2 4 多目标遗传算法应用 在目前多目标优化算法的研究中基于遗传算法的多目标优化在m o e a 中占主导地位， 所以在本节介绍多目标算法的应用前就遗传算法的思想介绍如下。 2 4 1 遗传算法 遗传算法是求解优化问题的一种现代方法，始于2 0 世纪7 0 年代，由美国密歇根 ( m i c h i g a l l ) 大学的j o h nh o l l 锄d 等人基于达尔文进化论和孟德尔的遗传学说创立的。 进化过程实现问题优化的基本原理描述如下： 1 利用一个种群表示问题的一组候选解，种群中每个个体的染色体代表问题的一个 解。采用某种编码方案( 如二进制数、浮点数或符号等) 对染色体进行编码。 2 利用目标函数计算种群中各个个体的适应值，以评价个体的优劣。通过一定的选择 策略从种群中挑选若干个体繁殖后代，种群中适应能力强的个体有较大的繁殖机会，劣质 的个体将被淘汰。 3 杂交( 即交叉) 和变异操作模拟生物繁殖中的重组和变异现象。经过若干代的进化后， 得到满足约束的个体。 这样，遗传算法采用启发式搜索能在一个较大的问题解空间中有效发现最优解或次优 解。 一个通常的遗传算法按如下过程进行( 如图2 1 所示) ( 1 ) 对待解决的问题进行预处理，通常是采用编码的方式重新将求解空间结构化： ( 2 ) 随机初始化种群坦o ) ：= o ，却，而) ： ( 3 ) 对当前种群讯f ) 中的每个个体而计算其适应度f ( x t ) ，适应度表示该个体的优劣 程度； ( 4 ) 应用选择算子产生中间代姒o ： ( 5 ) 对x r ( t ) 应用其他的算子，产生新一代种群坦f + 1 ) ，这些算子的目的在于扩展有 限个体的覆盖面，体现全局搜索的思想。 ( 6 ) f ：= f + 1 ；如果不满足终止条件继续( 3 ) g a 中常用的算子有如下几种： 1 ) 选择算子：选择算子从群体中按某一概率成对选择个体，某个体而被选中的概率 p f 与其适应度成正比。 第8 页武汉科技大学硕士学位论文 2 ) 交叉算子：交叉算子将被选中的两个个体的基因链按概率p c 进行交叉，生产两个 新的个体，交叉位置是随机的。 3 ) 变异算子：变异算子将新个体的基因链的各个按概率厶进行变异，对于二值基因 链( 0 ，l 编码) 来说既是对某一位取反。 上述各个算子的实现是多种多样的，而且许多新的算子正在不断地被提出，以便提供 其全局搜索的性能。系统参数( 个体数刀，基因链长度，交叉概率p c ，变异概率尸m 等) 对算法的收敛速度及结果有很大的影响，应视具体问题选择不同的值。 l 兰堕堡兰! ! ! 竺i 皇 产生初始种群 ! j = 0 2 4 2 多目标进化算法 图2 2 遗传算法流程图 如何求m o p 的p a r e ：t o 最优解，最近已经提出了多种基于遗传算法的求解方法。下面根 据它们使用的选择机制介绍几种主要方法。由于多目标进化算法产生的历史不长，只是最 近才兴起的一个研究领域，以下所述的几种方法代表了最新的潮流和研究情况。对于具体 的应用问题，如何选用哪种方法，则取决于对该问题的理解程度及决策人员的偏好。 ( 1 ) 并列选择算法 武汉科技大学 硕士学位论文第9 页 1 9 8 4 年，s c h a f “1 3 】提出的“向量评估遗传算法”( v e c t o re v a l u a t e dg e i l e t i ca l g o f i t h m ， v e g a ) 是一种非p 盯e t o 方法，但是第一种实现了用遗传搜索策略解决多目标优化问题。在 该算法中，先将群体中全部个体按目标函数的数目均等分成若干子群体，对各子群体分配 一个目标函数，各目标函数在其相应子群体中独立进行选择操作后再组成一新的子群体； 将所有新生成的子群体合并为一完整新群体再进行交叉和变异操作，如此循环执行“分割 并列选择合并 过程；最终求出问题的非劣解。此法可能产生某目标函数的极端最优解， 对所有目标在某种程度上较好地协调最优解较困难。 但是这种方法本质上仍然是加权和的非p 锄加方法，d s o n 1 4 】等人指出，将子种群 合并为一个新种群，本质上等同于将适应度向量线性组合为一个单值适应度的函数，容易 导致搜索向某个特定的目标方向进行，产生遗传漂移。 ( 2 ) 权重系数变化法 h a i e l a 和l i n 提出的“可变目标权重聚合法”【1 5 】是在适应度赋值时使用加权和法，对每 个目标赋一个权重。为了并行搜索多个解，权重本身并不固定，问题解和权重同时实施进 化操作。为了保证收敛速度和遗传搜索的稳定性，该方法需要使用配对约束来保证正常可 靠的进化操作。 ( 3 ) 排序选择法 f o n s e c a 和f l y i n g 提出的基于排序的适应度赋值多目标遗传算法( m u l f i p l e 蛳t i v e g e i l e t i ca l g o f i t h m ，m o g a ) t 3 】，以及s f i m v 嬲和d e b 提出的“非劣分类遗传算法【5 】，都是属 于排序选择法。它们根据“p a r e t o 最优个体的概念来对群体中所有个体进行排序，依据 这个排列次序来实施进化过程中的选择运算，从而使得排在前面的p 删。最优个体将有更 多的机会遗传到下一代群体。如此这样经过一定代数的循环之后，最终求出多目标优化问 题的p a r e t o 最优解。 这里所谓的p a r e t o 最优个体是指群体中的这样一些个体，群体中的其它个体都不比它 们更优越。需要说明的是，在群体进化过程中所产生的p a r e t o 最优个体并不一定就对应于 多目标优化问题的p a r e t o 最优解。当然，当进化算法经过足够的遗传代数后，我们需要取 排在前面的几个p a r e t o 最优个体，以它们所对应的解作为多目标优化问题的p a r e t o 最优解。 排序选择法仅仅度量了个体之间的优越次序，而未度量各个个体的分散程度，因此它易生 成很多个相似的p 蹦知最优解，而难以生成分布较广的p a r e t o 晟优解。 ( 4 ) 共享函数法 求解m o p 通常希望得到的解能够尽可能地分散在整个p a r e t o 最优解集合内，而不是集中 在其p a r e t o 最优解集的某一个较小的区域。为达到这个要求，利用小生境遗传算法的技术 来求解多目标优化问题，这种方法称为共享函数法。它将共享函数的概念引入求解m o p 的 进化算法，典型的算法是h o m 【4 1 等人提出的“小生境p 删。遗传算法”，还有一些其它变 形形式【16 1 。 在利用通常的进化算法求解最优化问题时，算法并未限制相同个体或类似个体的数量。 但当在进化算法中引入小生境之后，算法对它们的数量加以限制，以便产生种类较多的不 第1 0 页武汉科技大学硕士学位论文 同最优解。对于某个体f 而言，在它的附近还存在有多少种、多大程度相似的个体，这是可 度量的，这种度量值就是所谓的小生境数( n i c h ec o u n t ) 。计算出个体的小生境数，可使小 生境数较小的个体能有更多机会被选中遗传到下一代群体，即相似个体较少的个体有更多 机会被遗传到下一代，这样增加了群体多样性，相应地也增加解的多样性。共享函数法通 常综合运用联赛选择和共享函数的思想，选择优良个体遗传到下一代。该选择方法的优点 是能够得到多种不同的p a r e t o 最优解，但由于每次选择时都进行大量的个体之间优于关系 的评价和比较运算，使得算法的搜索效率较低。 ( 5 ) 外部辅助选择法 z i t z l e r 和1 1 1 i e l e 提出的浓度p a r e t o 进化算法( 1 1 1 es 仃饥g t l lp a r e t 0e v o l u t i o n a r ym g o d t h m , s p e a ) 【_ 7 】是一种典型的外部辅助选择法。它具有四个与众不同的特征：将每代的非劣个体 贮存在外部的一个附属可更新群体；群体中个体的适应度与外部辅助集中优于该个体的数 目相关联；利用p a u r e t o 优于关系来保持群体多样性；使用聚类方法保证外部集的非劣个体 数目不超过规定范围且又不破坏其特征。该算法效率高，缺点是外部辅助解集的规模要依 据试验经验来确定。目前利用外部辅助选择法进行工程应用越来越受到重视。 ( 6 ) 协同进化法 j e 衢e yh o m 1 7 】和h e l i o 1 8 】等人针对遗传算法的不足，提出基于生物种群模型的协同进化 思想用于解决多目标问题。通常的遗传算法只是采用基于个体自身适应度的进化模式，而 没有考虑其进化的环境和个体之间的复杂联系对个体进化性能的影响。协同进化借鉴了生 态学中对个体生存环境和种群竞争的认识，根据种群密度、种群自身及相作用种群的遗传 成分来确定适应度，充分考虑了种群与环境之间的相互作用和种群内个体在个体间和种群 间的协调。这种方法的特点是收敛速度较快。文献【1 9 】是另一种提高多目标进化算法收敛 速度的类似方法，它不是采用常规的两个体参与交叉，而是多个体交叉来产生p a r e t o 解， 使算法的速度得到提高。 2 5 多目标遗传算法的分析 利用g a 作为多目标搜索的方法的根据是利用了g a 算法的并行搜索能力，使得在搜索 过程中发现非劣解集合，即p a r e t o 集合。但是利用g a 作为全局搜索算法也有其严重的缺点， 这些缺点是g a 算法自身特点造成的。 g a 算法的特点为：1 ) 搜索过程是从一组解迭代到另一组解，这样可降低陷入局部最优 解的概率：2 ) 使用随机搜索过程而不是确定性搜索过程；3 ) 只利用目标函数和约束函数的 函数值信息，不需要导数等其他辅助信息，因此通用性更大，适用范围更广。4 ) 作为一种 优化算法，寻求最优点不是g a 的唯目的，更重要的目的是进步，即它的优化过程是一个 不断改进的过程。g a 具有并行搜索能力，从解空间中多点出发搜索问题的最优解，能在一 定程度上保留历史信息，适合求解大规模任意目标函数的全局优化问题。但它也有不足， 进行局部搜索能力差，导致发生早熟。这是因为算法的变异概率太小，引入新染色体的机 武汉科技大学硕士学位论文第1 1 页 会少。如果变异概率取大些，传统的变异算子将导致算法随机性很大，使搜索过程过于盲 目。 在上述列举的方法中，协同进化法就是针对g a 算法的不足，对收敛速度的一种改进方 法。但是在加强局部搜索的能力方面并没有得到提高，很容易导致早熟的发生。本文根据 遗传算法的以上特点，在解决多类s v m 分类参数优化的应用中提出了将禁忌算法引入到多 目标进化算法中来，目的用于改进遗传算法自身的不足而引起的问题。 2 6 本章小结 本章介绍了多目标优化的两类方法，传统的多目标优化算法和多目标进化算法。在目 前的研究中处理多目标优化问题时广泛使用的为多目标进化算法。在多目标进化算法中又 以多目标遗传算法为主。为能够详细说明多目标进化算法的原理，在本章中对基本遗传算 法的原理，算法流程进行了介绍。并针对近年来对多目标进化算法的研究应用，介绍了六 种不同的具有代表性的多目标遗传算。 第1 2 页武汉科技大学 硕士学位论文 3 1 基本禁忌