第5卷第2期 智能系统学报 Vol.5 No.2 2010年4月 CAAI Transactions on Intelligent Systems Apr.2010 doi:10.3969/j.issn.16734785.2010.02.008 SVM性能的免疫鱼群多目标优化研究 刘胜，李高云12，江娜 (1.哈尔滨工程大学自动化学院，黑龙江哈尔滨150001；2.中国船舶重工集团公司第七0七研究所九江分部，江西 九江332007) 摘要：SVM算法的训练精度和训练速度是衡量其性能的2个重要指标.以这2个指标为目标变量建立SVM性能多 目标优化问题的数学模型，采用直接对多个目标同时进行优化的方法求得问题的Pareto近似解集.在求解Pa©to近 似解集时，将免疫原理中的浓度机制引入基本鱼群算法中，形成一种改进的免疫鱼群算法.以非线性动态系统仿真 数据为样本数据，并采用改进的免疫鱼群算法求解SVM性能多目标优化问题的Pareto近似解集.仿真结果表明，在 解决多目标优化问题时，免疫鱼群算法相对于基本鱼群算法和遗传算法具有更好的优越性。 关键词：支持向量机；多目标优化；Pareto近似解集；免疫鱼群算法 中图分类号：TP183文献标识码：A文章编号：16734785(2010)02-0144-06 Multi-objective optimization of an immune fish swarm algorithm to improve support vector machine performance LIU Sheng',LI Gao-yun'2,JIANG Na' (1.College of Automation,Harbin Engineering University,Harbin 150001,China;2.Jiujiang Branch of 707 Research Institute,China Shipbuilding Industry Corporation,Jiujiang 332007,China) Abstract:Accuracy and speed when training a support vector machine (SVM)algorithm provides critical measure- ments of the algorithms performance.To optimize performance,a mathematical model of multi-objective optimiza- tion with improvements in these two parameters as goals was established.A Pareto approximate solution set was ob- tained by optimizing multiple targets simultaneously.In the process of finding the Pareto approximate solution set,a concentration mechanism from an immune algorithm was introduced into the basic artificial fish swarm algorithm. This produced significant improvements and resulted in the proposed immune fish swarm algorithm.Taking the non- linear dynamic system simulation data as sample data,a Pareto approximate solution set of multi-objective optimiza- tion of SVM performance was obtained using the improved algorithm.Simulation results showed that,for solving multi-objective optimization,the immune fish swarm algorithm was superior to both a basic artificial fish swarm al- gorithm and to genetic algorithms. Keywords:support vector machines;multi-objective optimization;Pareto approximate solution set;immune fish swarm algorithm 支持向量机(support vector machine,SVM)Iu2] 目前，MO0问题的求解方法可以大致分为2类，一 算法的训练精度是最受关注的性能指标之一，同时 类是将MO0问题转化为单目标优化问题进行求 训练速度也是一个关键因素，尤其在学习速度要求 解，这种方法最终只能求出一个综合了各个目标分 较高的场合.本文综合考虑算法的训练精度和速度， 量信息的最优解，但各个目标的重要程度是在构造 从多目标优化(muli-objective optimization,MO0)的 相应的单目标问题时确定的，不具有普遍性.另一类 角度出发，对SVM回归算法的2个指标进行研究和 方法是直接对多个目标同时进行优化，即多目标问 探讨.Schaffer首次采用进化算法研究了MOO问题. 题的直接求解方法.MOO直接求解法多数为智能类 收稿日期：20090324. 算法，都是同时求出多目标规划问题的Pareto最优 基金项目：黑龙江省自然科学基金资助项目(A2004-19). 解集.Shelokar等人[3]提出了一种基于Pareto支配 通信作者：刘胜.E-mail:iu.sch@163.com
第2期 刘胜，等：SVM性能的免疫鱼群多目标优化研究 ·145· 概念的多目标蚁群算法；Coello等人[4提出了多目 果常收敛至单个解，有时甚至出现整个群体都趋同 标粒子群算法，将Pareto支配关系与粒子群优化相 的现象.显然，无论该单个解是否为全局最优解或近 结合，改善了算法的搜索能力.其方法都挺不错，但 似最优解，均未实现多目标优化的目的.因此必须采 算法比较复杂。 取措施保持进化群体的多样性，避免未成熟收敛产 如何求解Pareto最优解集仍是关键问题，本文 生局部劣解，使优化结果呈现为一组不同的Pareto 将免疫原理中的浓度机制引入基本人工鱼群算法 最优解。 (artificial fish swarm algorithm,AFSA)中，改进了基 本文深入分析免疫算法)的机理特征，以下2 本鱼群算法，即免疫鱼群算法，并采用该算法来求取 条免疫机理特征尤其值得借鉴 训练速度和训练精度的Pareto近似解集. 1)产生多样抗体的能力：通过细胞的分裂和分 1SVM性能多目标优化方法 化作用，免疫系统可产生大量的抗体来抵御抗原，对 应于鱼群算法中个体的多样性，这种机制可提高鱼 1.1 Pareto最优解集 群算法的全局搜索能力而不陷于局部解. 本文采用直接对多个目标同时进行优化的方法 2)自我调节机制：免疫系统具有维持免疫平衡 来求解SVM性能的MOO问题，其关键是求解Pare 的机制，通过对抗体的抑制和促进作用能自我调节 to最优解集.求解SVM性能多目标优化问题的Pa 产生适当数量的必要抗体，对应于鱼群算法中个体 reto最优解集，如图1所示.其中，r反映训练精度指 浓度的抑制和促进.模拟这一功能可提高鱼群算法 标，t反映学习速度指标. 的局部搜索能力. t 基于以上免疫机理的特点，将免疫原理中的浓 度机制引入到基于多目标优化的鱼群算法的适应度 函数设计中，旨在改进算法的群体多样性.免疫鱼群 算法流程图如图2所示. 系统初始化 (参数、初始抗体代数G=1) 计算抗体浓度和 聚合适应度 图1SVM性能的多目标Pareto解集 Fig.1 Sketch map of multi-objective Pareto solution set of 计算当代群休的 抗体平均浓度 SVM performance 根据算法的具体应用场合，即针对训练速度和 从当代群体选出 G=G+1 Pareto.近似解集 训练精度的不同要求，从Pareto解集中选择耗时与 精度适宜的解.同时，可以通过Pareto解集中解的分 人工鱼按聚合适应度游动 (觅食、聚群或追尾) 布情况来判断单个目标的变化趋势，在选择最优解 时以某个目标较小的牺牲来换取另一个目标较大的 产生新的抗体 性能提升，使得总体效益最大化： 1.2免疫鱼群算法 抗体平均浓度稳定？ 2002年李晓磊等提出了人工鱼群随机搜索优 G>截至代数？ 化算法，简称鱼群算法[56].该方法根据实际鱼的运 动、聚集等行为构造人工鱼，通过觅食、聚群及追尾 输出最终进化的 Pareto近似解集 行为等改变自身的位置，经过一段时间后，各人工鱼 在各极值处聚集，再由各人工鱼局部寻优找到全局 图2改进的免疫鱼群算法流程图 最优值 Fig.2 Flow chart of improved immune fish swarm algorithm 基本鱼群算法容易丧失群体的多样性，优化结 图2中，“抗体平均浓度稳定”是指在进化过程中
·146 智能系统学报 第5卷 的后若干代与前若干代的抗体平均浓度的差值不超过 计得到较高的拟合精度和较快的收敛速度.综合C、 一定的范围，则可以认为已趋于稳定.也可以使用传统 ε以及核函数参数，SVM多目标优化的决策变量为 的方法作为进化停止准则，即进化到规定代数 X={λ，o,d,C,8}, 在采用免疫鱼群算法求解多目标优化问题时， 0≤入≤1，g,d,C,e≥0. (4) 把目标函数和决策变量作为抗原，保证了所生成的 2.3目标函数 抗体直接与问题相关联；生成的抗体能有效地排除 SVM性能多目标优化问题中应使拟合精度r较 抗原，也就相当于求得了问题的最优解；对与抗原亲 高，而学习时间t较短；但在目标优化问题中是以函 和力高的抗体进行记忆，能促进快速求解，即当遇到 数值最小来建立目标函数的，所以以-「和t为目标 同类抗原时，可以快速生成与之对应的抗体 变量来建立目标函数，如式(5)所示： Min Y Mint,-r. (5) 2SVM性能多目标优化数学建模 3SVM性能多目标的免疫鱼群优化 2.1目标变量 SVM性能多目标优化问题的第1个目标是训 3.1算法步骤 练精度τ，如果拟合误差过大，则会对下一步的预报 1)抗原识别. 造成影响，形成更大的预报误差；第2个目标是反映 输入抗原，抗原即为待优化的目标函数及其约 学习速度的时间参数t,如果学习时间过长，即使达 束条件 到了较高的训练精度，也是得不偿失 2)初始抗体生成， 2.2决策变量 假设鱼群规模定义为100，在决策空间X中随机 影响SVM性能的参数主要包括惩罚因子C,损 产生100个不同的人工鱼抗体组成人工鱼初始群体 失函数参数B和核函数参数.参数C、B和核函数参 3)抗体适应度计算 数的选择，对于SVM回归估计的拟合精度和学习速 采用非劣分层算法进行个体适应度计算， 度影响很大， ①使用种群非劣分层算法将种群P进行非劣分 参数C可以根据样本数据的特性，决定模型的 层非劣分层的结果是将种群P分成p组非劣组P· 复杂度和对大于ε的拟合偏差的惩罚程度.C值过 P=U月1P (6) 大或过小，都会使系统的泛化能力变差，参数ε表明 第1组P的所有个体属于种群的最优非劣组， 了系统对估计函数在样本数据上误差的期望，其值 第2组P2的所有个体属于种群的次优非劣组，…， 影响了构造回归函数的支持矢量数目.核函数的参 最后一组P。的所有个体属于最劣组。 数反映了训练数据的特性，对于系统的泛化能力影 ②因为种群中最优非劣组的个体与种群中其 响较大.2种常见的核函数为 他的个体相比最接近真正的Pareto最优域，所以，分 多项式核函数： 配最高的适应值给最优非劣组的个体，然后逐步地 K(x,x）=(xx+1)4, (1) 分配较差的适应值给更劣层非劣组的个体，分配给 RBF核函数： 第1层最优非劣组的任一个抗体i的适应值方 Ksr=exp(-‖x:-x‖2/o2). (2) N=100(N为抗体种群大小). 式中：x:,为输人空间的2个向量，d和σ分别为 ③在每组内部使用共享函数法.P,组的每个 多项式和RBF核函数的参数.由于每一种核函数对 抗体i与同一组的另一个抗体j的标准化欧拉距离 提高SVM性能的能力有限，所以引用一个参数入来 d计算如下： 构造混合模型： Kt（,x)=入K（x:,x）+ di= (7) (1-入)KBr(x:,）, 式中：W为决策变量的个数 0≤入≤1. (3) ④利用式(8)计算共享函数值. 但是如何确定入，目前尚未找到一种有效的方法。 只有正确选择上述参数，才可以使SVM回归估
第2期 刘胜，等：SVM性能的免疫鱼群多目标优化研究 ·147 人工鱼下一步游动到的位置，处于该位置的人工鱼 Sh(d;) 8 即为产生的新抗体 其他 5)抗体记忆细胞的分化和更新. 式中：a=2,共享函数依据d在(0,1)之间取值， 自然免疫系统在第2次遇到某抗原时，免疫反 σh是人为设定的小生境半径，任何与抗体i的距 应能够迅速有效排除抗原，免疫学称为二次应答.自 离大于σm的抗体j对共享函数值不作贡献. 然免疫系统甚至能对以前从未遇到的抗原产生二次 ⑤在计算完1P,1个共享函数值以后，利用式 应答，二次应答具有时间短、高速率及合成抗体持续 (9)计算抗体i的小生境数E. 时间长等特点，二次应答反映了免疫具有系统的记 R(n) 忆功能，这里用记忆库存储高亲和度的抗体细胞来 nc:=∑sh(dg) (9) 模拟自然免疫的记忆功能.记忆库是适时更新的，用 ⑥依次类推，直到计算完第1层所有的抗体的 每次产生的具有更高亲和度的抗体细胞取代记忆库 小生境数.将抗体的适应度值调整为 中亲和度低的记忆细胞， fi=f/nci (10) 6)输出Pareto近似解集 ⑦再令第2层抗体的适应度值为f=N-p/N, 采用抗体的平均浓度稳定来结束迭代.即： 计算第2层所有抗体调整以后的适应度值.然后，令 1 Cke-Chve 1 第3层抗体的适应度值为f=N-2p/W,计算第3层 c 0,为调节系 用改进的免疫鱼群算法对这个MO0问题进行优 数，可根据群体规模和经验而定，本文取值为5. 化.所选取的非线性动态系统由式(16)所描述⑧] 4)产生新抗体 抗体即为鱼群中的人工鱼，第i条人工鱼（抗体 4+1)）=-0L》+1.51+u(e0. 1+y2(t)+y2(t-1) )的位置用向量x:表示，将抗体i的适应度值作 (16) 为该位置的食物浓度值Y:,人工鱼（抗体）通过觅食 对上述系统模型，进行仿真以收集数据样本来 行为、聚群行为或追尾行为游动，到达新的位置，即 训练网络.在系统的输入端加上一个随机信号得到 产生了新抗体 一组2000个输入一输出训练数据对，取前1000个 ①觅食行为： 作为训练样本，后1000个作为测试样本，采样周期 xo+rand·step xa-xe,Ya Yoi 0.15.结果曲线如图3和图4所示， dou 1.0 xn+rand·step, Ya Yo. (12) 0.8 ②聚群行为： 0.6 a=+rand·sep（3-) 0.4 (13) diceer 0.2 ③追尾行为： 40 80.120160200 ioam=+rand·step- 1/s di max (14) 图3输人数据曲线 式中：x为第i条鱼（抗体）当前的位置；x为该 Fig.3 Curve of input data
148 智能系统学报 第5卷 3.0 表1 Pareto近似解集的性能比较 25 Table 1 Performance comparison of Pareto approximate 2.0 solution set 代平均距离 均匀分布 前端范围 优化方法 1.0 GD UD FS 0.5 遗传算法 0.401 0.647 1287.6 0 40 80120160200 基本鱼群算法 0.320 0.591 1342.7 免疫鱼群算法 0.259 0.536 1394.2 图4输出数据曲线 从表1中可以看出，免疫鱼群算法相对于遗传算 Fig.4 Curve of output data 法和基本鱼群算法所求得的Pareto近似解集与Pare 采用改进的免疫鱼群算法求解训练精度和学习 to最优前端距离最近（代平均距离GD最小），分布性 速度，同时优化这一多目标优化问题的Pareto近似 能最好（均匀分布UD最小），分布范围也最广（前端 解集，图5是采用图形化方法表示所求得训练速度 范围FS最大).这说明免疫鱼群算法在SVM性能多 和训练精度的Pareto近似解集， 目标优化问题的求解中表现出更大的优越性， 1.0r 0.8 4结束语 0.6 综合考虑训练精度和学习速度2个目标变量， 0.4 0.2 从多目标优化的角度建立了SVM性能的多目标优 化模型，并针对基本鱼群算法的不足，将免疫原理中 50100150200250300 t/s 的浓度机制引入多目标优化的鱼群算法适应度函数 图5 Pareto近似解集结果 设计中，形成了一种改进的免疫鱼群算法.以 Fig.5 Results of Pareto approximate solution set 文献[8]非线性动态系统仿真数据为样本数据，采 下面从以下3个方面定量地对算法所求得的 用免疫鱼群算法优化SVM性能的多目标优化模型， 求得了训练精度和学习速度的Pareto近似解集.最 Pareto近似解集进行评估和比较： 后，将遗传算法、基本鱼群算法和免疫遗传算法优化 1)能否得到分布性能最好（尽量为均匀分布） 所得的Pareto近似解集的代平均距离GD、均匀分布 的近似集，采用均匀分布(uniform distribution,UD) UD、前端范围S进行比较，仿真结果表明，虽然免 作为评价指标 疫鱼群算法较之基本鱼群算法增加了算法复杂度， 2)能否进化得到最接近Pareto最优前端的近似 但所求得的Pareto近似解集与Pareto最优前端距离 集，采用代平均距离(generational distance,GD)作为 最近，分布性能最好，分布范围也最广，在SVM性能 评价指标。 多目标优化问题的求解中具有更大的优越性， 3)能否获得在目标空间分布范围最广的近似 集，即进化产生的非支配解集在每维目标空间能够 参考文献： 覆盖尽可能宽的区域范围，采用前端范围(front [1]刘胜，李妍妍.基于支持向量机的锅炉过热系统建模 spread,FS)作为评价指标， 研究[J].热能动力工程，2007,22(1)：3841 其中，均匀分布UD、代平均距离GD、前端范围 LIU Sheng,LI Yanyan.A study of the modeling of a boiler FS的求解方法见文献[9-11]. superheating system based on a supportive vector machine 为了验证免疫鱼群算法对SVM性能多目标优 [J].Journal of Engineering for Thermal Energy and Power, 化的有效性和优越性，同时将遗传算法和基本鱼群 2007,22(1):38-41. 算法对SVM性能多目标优化的结果与之对比，表1 [2]APNIK V N.The nature of statistical learning theory M]. 列出了以上3种方法所求得的Pareto近似解集的代 New York:Springer-Verlag,1995:24-35. 平均距离GD、均匀分布UD、前端范围FS。 [3]SHELOKAR P S,ADHIKARI S,VAKIL R,JAYARAMAN V K.Multi-objective ant algorithm:combination of strength
第2期 刘胜，等：：SVM性能的免疫鱼群多目标优化研究 ●149. Pareto fitness assignment and thermodynamic clustering[J]. [11]KAPUR J,KESAVAN H.Entropy optimization principles Foundations of Computing and Decision Sciences.2000.25 with applications[M].San Diego:Academic Press,1992: ④）213-229. 214-258. [4]COELLO C A C,PULIDO G T,LECHUGA M S.Handling 作者简介： muliple objectives with particle swam optimization[J]. 刘胜，男，1957年生，教授，博士 EEE Transaction on Evolutionary Computation,2004,8 生导师，黑龙江省教学名师，黑龙江省 ③，：256-279. 重点一级学科“控制科学与工程“学科 同]李晓磊.一种新型的智能优化方法-人工鱼群算法[D] 负责人.兼任教育部工程研究中心“船 洲州：浙江大学，2003 舶控制工程研究中心“主任，中国造船 LI Xiaolei.A new intelligent optimization method-artificial 学会仪器仪表学术委员会副主任，黑龙江省自动化学会副理 fsh school algorithm[D].Hangzhou::Zhejiang University, 事长主要研究方向为智能控制、鲁棒控制、船舶航行与姿态 2003. 控制.目前承担国家“973”计划项目，国防基础研究基金项 [6]张梅凤邵诚甘勇.基于变异算子与模拟退火混合 目、国防预研项目4项，省部级项目6项.曾获黑龙江省优秀 的人工鱼群优化算法[J].电子学报，2006,34(8)：1381- 教学工作者、中国船舶工业总公司优秀青年科技工作者、获 1385. 省部级科学技术奖7项、获省教学成果奖一等奖2项，二等 ZHANG Meifeng SHAO Cheng,GAN Yong.Hybrid artifi- 奖2项、获省教育科学研究成果一等奖4项、获省部级自然 cial fish swarm optimization algorithm based on mutation op- 科学技术学术成果奖8项.发表学术论文150余篇，被 erator and simulated annealing[J].Acta Eletronica Sini- SCI、EI、STP检索70余篇，出版学术著作3部. ca,2006,34(8):1381-1385. 门莫宏伟.人工免疫系统原理与应用[M们.哈尔滨：：哈尔滨 李高云，男，1981年生，博士研究 工业大学出版社，2002：27-58 生，主要研究方向为智能控制、故障诊 图]张浩然，韩正之，李昌刚.基于支持向量机的未知非线性 断与容错控制、船舶航行与姿态控制. 系统辨识与控制[].上海交通大学学报，2003,37(6)： 参与科研项目3项，获黑龙江省科学技 927-930. 术二等奖1项，黑龙江省高校科学技术 ZHANG Haoran,HAN Zhenghi,LI Changgang.Support 一等奖1项，发表学术论文近10篇，被 vector machine based unknown nonlinear systems identifica- EI、ISP检索4篇 tion and control[J].Journal of Shanghai Jiaotong Universi- ty,2003,37(6):927-930. 江娜，女，1981年生，博士研究 9VELDHUIZEN D A V.LAMONT G B.On measuring mul- 生，主要研究方向为故障诊断与故障预 tiobjective.evolutionary algorithm performance[C]//Pro- 报.参与科研项目2项，发表学术论文 eedings of the 200 Congress on Evolutionary Computation. 近10篇，被EI、ISTP检索5篇， California,CA,USA,2000:204-211. [10]'TAN K,LEE T,KHOR E.Evolutionary algorithms with dynamic population size and loal exploration for multiob- jective optimization[J].IEEE Transactions on Evolution- ary Computation,2001,7(3)):565-588
第2期 [10] TAN K,LEE T,KHOR E. Evolutionary algorithms with dynamic population size and loal exploration for multiobjective optimization[J]. IEEE Transactions on Evolutionary Computation,2001,7(3) :565-588. [6]张梅凤,邵 诚,甘 勇.基于变异算子与模拟退火混合 的人工鱼群优化算法[J] .电子学报,2006,34(8) :1381- 1385. LI Xiaolei. A new intelligent optimization method-artificial fsh school algorithm[ D] .Hangzhou: Zhejiang University, 2003. [11] KAPUR J,KESAVAN H. Entropy optimization principles with applications[ M]. San Diego: Academic Press,1992: 214-258. Pareto fitness assignment and thermodynamic clustering[J] . Foundations of Computing and Decision Sciences,2000,25 (4) :213-229. [8] 张浩然,韩正之,李昌刚.基于支持向量机的未知非线性 系统辨识与控制[J] .上海交通大学学报,2003,37(6) : 927-930. ZHANG Meifeng,SHAO Cheng,GAN Yong. Hybrid artificial fish swarm optimization algorithm based on mutation operator and simulated annealing[J] . Acta Eletronica Sinica,2006,34(8) :1381-1385. 作者简介: 刘 胜,等: 生导师,黑龙江省教学名师,黑龙江省 重点一级学科"控制科学与工程"学科 负责人.兼任教育部工程研究中心"船 舶控制工程研究中心"主任,中国造船 学会仪器仪表学术委员会副主任,黑龙江省自动化学会副理 事长.主要研究方向为智能控制、鲁棒控制、船舶航行与姿态 控制.目前承担国家"973"计划项目,国防基础研究基金项 目、国防预研项目4项,省部级项目6项.曾获黑龙江省优秀 教学工作者、中国船舶工业总公司优秀青年科技工作者、获 省部级科学技术奖7项、获省教学成果奖一等奖2项,二等 奖2项、获省教育科学研究成果一等奖4项、获省部级自然 科学技术学术成果奖8项.发表学术论文150余篇,被 刘 胜,男,1957年生,教授,博士 SCI、EI、STP检索70余篇,出版学术著作3部. SVM性能的免疫鱼群多目标优化研究 江 娜,女,1981年生,博士研究 生,主要研究方向为故障诊断与故障预 报.参与科研项目2项,发表学术论文 近10篇,被 EI、ISTP检索5篇. [9] VELDHUIZEN D A V,LAMONT G B. On measuring multiobjective. evolutionary algorithm performance[ C]//Proeedings of the 200 Congress on Evolutionary Computation. California,CA,USA,2000: 204-211. [7] 莫宏伟.人工免疫系统原理与应用[M].哈尔滨: 哈尔滨 工业大学出版社,2002: 27-58. ZHANG Haoran,HAN Zhenghi,LI Changgang. Support vector machine based unknown nonlinear systems identification and control[J].Journal of Shanghai Jiaotong University,2003,37(6) :927-930. ·149. 李高云,男,1981年生,博士研究 生,主要研究方向为智能控制、故障诊 断与容错控制、船舶航行与姿态控制. 参与科研项目3项,获黑龙江省科学技 术二等奖1项,黑龙江省高校科学技术 一等奖1项,发表学术论文近10篇,被 EI、ISTP检索4 篇. [4] COELLO C A C,PULIDO G T,LECHUGA M S. Handling muliple objectives with particle swam optimization[J]. EEE Transaction on Evolutionary Computation,2004,8 (3) :256-279. [5] 李晓磊.一种新型的智能优化方法-人工鱼群算法[D]. 杭州: 浙江大学,2003