基于蚁群算法的支持向量机参数优化


第 33卷 第 4期 2009年 8月 南京理工大学学报 (自然科学版 ) Journal of Nanjing University of Science and Technology (Natural Science) Vol. 33 No. 4 Aug. 2009  收稿日期 : 2008 - 07 - 24  修回日期 : 2009 - 04 - 27  基金项目 :国家自然科学基金 (50705097)  作者简介 :张培林 (1955 - ) ,男 ,教授 ,博士生 ,主要研究方向 :机械工程及自动化。 基于蚁群算法的支持向量机参数优化 张培林 1, 2 ,钱林方 1 ,曹建军 2 ,任国全 2 (1. 南京理工大学 机械工程学院 ,江苏 南京 210094; 2. 军械工程学院 火炮工程系 ,河北 石家庄 050003) 摘  要 :针对支持向量机的参数对分类性能的影响 ,探讨了基于蚁群算法的支持向量机参数优 化方法 ,建立了支持向量机参数优化模型 ,给出了基于网格划分策略的连续蚁群算法 ,并将其用 于优化模型求解 ,通过对支持向量机的惩罚因子和径向基核函数进行优化 ,使支持向量机的分 类性能最优。通过仿真和应用实例 ,验证了方法的有效性 ,得到了 95%以上的分类正确率。 关键词 :蚁群算法 ;支持向量机 ;参数优化 ;油液分析 ;故障诊断 中图分类号 : TH 113. 1; TK 41. 1  文章编号 : 1005 - 9830 (2009) 04 - 0464 - 05 Parameter Optim ization of Support Vector Machine Based on Ant Colony Optim ization Algorithm ZHANG Bei2lin1, 2 , Q IAN Lin2fang1 , CAO Jian2jun2 , REN Guo2quan2 (1. School ofMechanical Engineering, NUST, Nanjing 210094, China; 2. Department of A rtillery Engineering of O rdnance Engineering College, Shijiazhuang 050003, China) Abstract: Parameters of support vectormachine is the key factor that impacts its classifying perform2 ance. A parameter optim ization method for support vector machine using ant colony optim ization al2 gorithm is discussed. A parameter optim ization model is established. The continuous ant colony opti2 m ization method based on gridding partition is given and used to resolve the optim ization model. The classifying performance reaches the best state by optim izing the penalty factor and the radial basis function. The validity of the method is tested by simulation and application instances, and more than 95% classified right rate is obtained. Key words: ant colony optim ization algorithm; support vector machine; parameter optim ization; oil analysis; fault diagnosis   支持向量机建立在统计学习坚实的理论基础 之上 ,具有理论的完备性 ,但是在应用上仍然存在 一些问题 ,典型的问题之一就是模型参数的选择 , 针对此问题 ,尚无统一的模型选取标准和理论。 总第 167期 张培林  钱林方  曹建军  任国全  基于蚁群算法的支持向量机参数优化   具体应用中 ,对分类结果有重要影响的参数是 :惩 罚因子 C和核函数参数等。 惩罚因子 C 用于控制模型复杂度和逼近误 差的折中 , C越大则对数据的拟合程度越高 ,但泛 化能力将降低;对不同类型的核函数 ,所产生的支 持向量的个数变化不大 ,但是核函数的相关参数 , 如多项式核函数的多项式次数 ,径向基核函数的 σ值对模型的分类精度均有重要影响 [1 - 4 ] 。 蚁群算法是一种新型启发式进化算法 , 具有 很强的发现较好解的能力 ,较好的鲁棒性 ,信息正 反馈 ,并行分布式计算及易于与其他启发式方法 相结合等优点 [5, 6 ] 。本文提出了一种基于蚁群算 法的支持向量机参数选择算法 ,为支持向量机的 参数选择提供了新方法 ,并将其应用于发动机油 液故障诊断。 1 支持向量机参数优化模型 为了直观说明参数对分类结果的影响 , 对正 常和拉缸两种状态样本 (前 10个用来训练 ,后 30 个用来测试 ) ,分别考查确定 C,不同 σ值的分类 结果 (表 1) ; 确定 σ值 , 不同 C 的分类结果 (表 2) 。 表 1 C = 2时 σ对分类结果的影响 σ 正确率 /% 0. 01 63. 33 0. 1 76. 67 1 86. 67 10 73. 33 100 60. 00 表 2 σ = 2时 C对分类结果的影响 C 正确率 /% 0. 5 66. 67 1 73. 33 10 83. 33 100 90. 00 1000 56. 67   由表 1和表 2的分类结果可知 ,相同的训练 和测试数据集下 ,不同的支持向量机参数所得到 的分类精度不同 ,惩罚系数 C 和径向基函数的 σ 值对分类结果的影响均很大 ,因此 ,要获取支持向 量机的优越性能 ,需要选取合适的 C及 σ。 实际应用中的故障诊断 ,一般是多故障分类 问题 ,要通过优化分类器参数提高整个多分类器 的样本识别精度 ,首先要分别优化多分类器的每 个二分类器的参数 ,各分类器的参数是由该分类 器对应的样本分别决定的 ,各分类器之间的参数 具有独立性 ,可以分别进行优化。 对给定的二类样本集 ,对应的 SVM 的分类正 确率可以看成关于 C 及 σ的二元函数 , 记为 P (C,σ) ,则支持向量机参数优化数学模型为   maxP (C,σ) s. t. C∈(0, a) σ∈(0, b)  a, b > 0 (1) 即在限定的搜索区间内 ,求取 C及 σ,使通过 训练样本确定的 SVM,对测试样本的分类正确率 最大 ,模型 (1)中的 a, b值 ,根据具体样本进行估 计后 ,取足够大的值。 2 基于网格划分策略的连续蚁群算法 网格划分是指将变量区域网格化 ,在网格点 上求约束函数和目标函数值 ,对满足约束的点 ,比 较该点目标函数值 ,从中选择较优者 ,并把该点作 为一次迭代的结果;继续在求出的较好点附近将 分点加密 ,重复以上计算和比较 ,直到网格的间距 小于预先给定的精度。 以求解以下无约束非线性最优化问题为例 , 介绍基于网格划分的连续域蚁群算法设计。  m inf ( x1 , x2 , ⋯, xn ) (2) 基于网格划分策略的连续域蚁群算法 , 基本 思想为 [7 - 10 ] : (1)根据待求连续域优化问题的性质 , 估计 出各变量的取值范围 xiL ≤xi ≤xiM , i = 1, 2, ⋯, n。 (2)将变量区域网格化 , 空间的网格点上对 应一个状态 ,蚂蚁在各网格点之间移动 ,并根据各 网格点的目标函数值留下不同量的信息 ,以影响 下一批蚂蚁的移动方向。 (3)循环一段时间后 , 相邻节点间的目标函 数差值 (即评价函数值 ) 越小 , 网格点信息量越 大 ,对信息量较大的网格点 ,缩小变量范围 ,在该 点附近进行蚁群移动。 (4)不断重复上述过程 , 直到满足算法的停 止条件。 设将各变量均分为 N 等份 , n个变量的连续 函数优化问题变为 n级决策问题 ,每一级有 N + 1 564   南京理工大学学报 (自然科学版 ) 第 33卷第 4期 个节点 ,则从第 1级到第 n级之间共有 (N + 1) × n个节点连接在一起 ,构成解空间内的一个解 ,如 图 1所示。 图 1 连续优化问题的状态空间解 由图 1,状态空间所示的状态为 ( 1, 3, 2, ⋯, 4) ,则该状态所对应的解为 ( x1 , x2 , x3 , ⋯, xn ) =   x1L + x1M - x1L N × 1, x2L + x2M - x2L N × 3,  x3L + x3M - x3L N × 2, ⋯, xnL + 2nM - xnL N × 4 (3) 蚂蚁自第 1级到第 N 级之间的状态转移概 率为  Pij = tij ∑ N j = 1 tij (4) 式中 : tij为第 i级第 j个节点的信息量 ,其更新公 式为  tnew ij = (1 -ρ) told ij + Q f (5) 式中 : tnew ij 为更新后的信息素量 , told ij 为更新前的信 息素量 , f为目标函数值 ,Q为常数 ,用以调节信息 素增量。 基于网格划分的连续域蚁群算法描述如下 : B egin 确定各自变量的取值范围 : xiL ≤xi ≤xiM , i = 1, 2, ⋯, n; 将各自变量 N 等分 : hi = xiM - xiL N , i = 1, 2, ⋯, n; W hile(m ax ( h1 , h2 , ⋯, hn ) ≥ε) {初始化 :循环次数 CS = 0,给信息量矩阵 tij 赋相同的值 ,设置常数 Q,信息素挥发系数 ρ及最大循环次数 CSm ax的初始值 ; do{生成 Ma只蚂蚁 ; 每只蚂蚁按式 (4)选择节点 ; 记录本次迭代最好解 ; 更新当前搜索精度下最好解 ; 按式 (5)更新信息素 ; CS = CS + 1; }W hile(CS < CSm ax ) ; 找出 tij矩阵中每行最大元素所对应的列 ( r1 , r2 , ⋯, rn ) ; 更新变量取值范围 : xiL = xiL + ( ri -Δ) hi , xiM = xiL + ( ri +Δ) hi , i = 1, 2, ⋯, n; 将各自变量 N等分 : hi = xiM - xiL N , i = 1, 2, ⋯, n; } 输出最优解 : x3 i = xiL + xiM 2 , i = 1, 2, ⋯, n; End 3 算法仿真与应用 3. 1 支持向量机参数优化蚁群算法实现 通过以上分析 ,支持向量机模型分类精度与 惩罚因子 C和径向基核函数的 σ均存在一定的 关系 ,为了获取最佳分类性能的 SVM 模型 ,需要 得到最佳的 C和 σ值。显然这是一个优化问题 , 如果采取穷举的方式搜索最优值 ,计算量将十分 巨大以至于无法实现。由于蚁群算法具有并行性 和强大的全局搜索能力 ,可以在很短的时间内搜 索到全局最优点 ,因此 ,利用蚁群算法对模型 (1) 求解。 根据基于网格划分的连续蚁群算法 ,以及模 型 (1)的特点 ,将算法总停止条件调整为 : (m ax ( h1 , h2 , ⋯, hn ) ≥ε‖P = = 100% ) ,即若分类正 确率达到 100% (分类结果最优 ) ,则算法停止 ,对 有关参数作如下设定 :依据 3. 3节给定的样本 ,将 模型 (1)中的 a, b值分别设定为 5 000和 200;则 算法描述中 , i = 1, 2, x1L = 0, x1M = 5 000, x2L = 0, x2M = 500,取 N = 100,ε= 0. 5,Δ = 0. 5, CSm ax = 30, tij = [ 10 ],ρ= 0. 2,Q = 2,Ma = 20。 设定以上参数后 ,依据给定样本 ,对模型 (1) 求解 ,可以求得对测试样本分类正确率最高的支 持向量基对应的 C和 σ值 ,同时得到确定的对应 支持向量机分类器。 3. 2 算法仿真 为了验证支持向量机参数优化算法的效果 , 664 总第 167期 张培林  钱林方  曹建军  任国全  基于蚁群算法的支持向量机参数优化   首先对以下两个标准的数据集进行仿真实验。 3. 2. 1 圆分类问题 在直角平面 xoy上 ,将圆 x2 + y2 = 25内的点 定义为一类 ,将圆环 25 < x2 + y2 < 64内的点定义 为另一类 ,以上两类分别随机产生 20个训练样本 (如图 2所示 ) ,另外随机产生两类样本各 300个 进行分类精度测试。 图 2 圆分类问题训练样本 3. 2. 2 双螺旋问题 在直角平面 xoy上 ,由式 (6)生成训练样本   x( i) = r( i) × sin (θ( i) ) y( i) = r( i) × cos(θ( i) ) θ( i) = i ×π/16 r( i) = 6. 5 × (104 - i) /104 i = 0, 1, ⋯, 99 (6) 式 (6)生成的点 ,点 ( x ( i) , y ( i) )组成第一类 ,点 ( - x( i) , - y ( i) )组成第二类 ,记为 ,每类各 100 个点 (如图 3所示 ) ,测试样本数为每类 100个 , 由式 (7)生成。 图 3 双螺旋问题训练样本   x( i) = r( i) × sin (θ( i) ) y( i) = r( i) × cos(θ( i) ) θ( i) = ( i + 0. 5) ×π/16 r( i) = 6. 5 × (104 - i - 0. 5) /104 i = 0, 1, ⋯, 99 (7) 式 (7)生成的点 ,点 ( x ( i) , y ( i) )组成第一类 ,点 ( - x( i) , - y( i) )组成第二类。 为了更直观地说明支持向量机参数优化模型 的优越性 ,首先考查支持向量机参数对分类精度 的影响 ,结果列于表 3和表 4。 表 3 C = 2时 σ对分类结果的影响 σ 圆分类问题正确率 /% 双螺旋问题正确率 /% 0. 01 22. 33 48. 50 0. 1 58. 33 63. 00 1 92. 17 51. 00 10 64. 33 61. 50 100 49. 50 56. 00 表 4 σ = 2时 C对分类结果的影响 C 圆分类问题正确率 /% 双螺旋问题正确率 /% 0. 5 81. 00 67. 00 1 91. 15 52. 50 10 87. 67 43. 5 100 87. 00 43. 5 1000 84. 67 43. 5   利用 3. 1节的方法对支持向量机进行参数优 化和设计 ,参数优化结果和分类正确率列于表 5。 表 5 参数优化结果 数据集 (C,σ) 分类正确率 /% 圆分类问题 (0. 1, 0. 85) 96. 33 双螺旋问题 (110, 0. 25) 100   比较表 5和表 3及表 4的分类结果 ,表 5中 参数优化后的支持向量机的分类精度明显高于表 3及表 4中的支持向量机分类精度 ,特征是对经 典分类难题 —双螺旋问题 ,参数优化后的支持向 量机的分类正确率达到 100% ,而表 3及表 4所 列在人工选择参数的分类正确率均在 70%以下 , 而对圆分类问题 ,分类正确率改善不如对双螺旋 问题明显 ,一般而言 ,对区分难度大的样本集 ,参 数优化对分类精度的改善越明显。 3. 3 应用实例 对 6种故障状态样本 : (1)正常 ; ( 2)拉缸 ; (3)烧瓦 ; (4)轴承磨损 ; (5)主机油泵磨损 ; (6) 冷却液泄漏。由“one2versus2one”多分类器构造方 法 [ 4 ] ,共需要 6 × (6 - 1) 2 = 15 个二类分类器 ,将 15个分类器分别记为 SVM ij , i = 1, 2, ⋯, 5, j = 2, ⋯, 6, i < j,对应第 i类和第 j类样本 ,分类正确率 记为 Pij。 依据故障状态样本 (每类的前 10个样本用 764   南京理工大学学报 (自然科学版 ) 第 33卷第 4期 来训练 ,后 20个样本用来测试 ) ,利用 3. 1节的方 法对每个二分类器进行参数优化和设计 ,每个分 类器的的参数优化结果及分类正确率列于表 6。 表 6 分类器优化结果 SVM ij (C,σ) Pij /% SVM ij (C,σ) Pij /% SVM 12 (95, 1. 25) 96. 67 SVM 26 (374, 1. 80) 93. 33 SVM 13 (50, 10) 100 SVM 34 (93. 5, 3. 45) 93. 33 SVM 14 (250, 0. 95) 90. 00 SVM 35 (185. 0, 2. 25) 96. 67 SVM 15 (85, 2. 50) 93. 33 SVM 36 (50, 10) 100 SVM 16 (350, 5) 100 SVM 45 (75, 1. 75) 93. 33 SVM 23 (400, 1. 70) 100 SVM 46 (452. 5, 1. 10) 86. 67 SVM 24 (13. 5, 4. 1) 83. 33 SVM 56 (460. 5, 2. 30) 100 SVM 25 (94. 5, 2. 65) 96. 67   利用参数优化后的 15个二分类器构建“one2 versus2one”多分类器 ,将 180个测试样本输入分类 器测试 ,得到总分类正确率为 97. 22%。而用传 统方法 ,通过测试样本尝试选择统一的 C和 σ,得 到的测试样本的最好分类正确率仅为 86. 11%。 传统参数选择方法 ,不能兼顾各二类分类器的分 类性能 ,事实上 ,对多分类器而言 ,最终的分类性 能是由各分类器共同决定的 ,通过对每个支持向 量机进行参数优化 ,提高每个支持向量机的分类 精度 , 从而达到提高整个多分类器分类精度的 目的。 4 结束语 支持向量机的参数是影响支持向量机分类精 度的重要因素 ,为了克服因支持向量机参数选择 的随意性对分类器性能的不利影响 ,建立了支持 向量机参数优化模型 ,将问题转化为连续域优化 问题 ,设计了基于网格划分的连续蚁群算法 ,并将 其用于模型求解。仿真实验与应用实例表明 ,经 参数优化的支持向量机具有更高的分类精度 ,通 过优化参数达到提高支持向量机分类精度的目 的。并且参数优化在分类器设计阶段自动完成 , 没有增加分类器的分类运算复杂度 , 应用前景 良好。 参考文献 : [ 1 ]  VapN ik V N. An overview of statistical learning theory [ J ]. IEEE TransNeuralNetworks, 1999, 10 (5) : 88 - 999. [ 2 ] D rucker H, W u D, V ipnik V N. Support vector ma2 chines for spam categorization[ J ]. IEEE Transactions on Neural Networks, 1999, 10 (5) : 1048 - 1054. [ 3 ] 李盼池 ,许少华. 支持向量在模式识别中的核函数 特性分析 [ J ]. 计算机工程与设计 , 2005, 26 ( 2) : 302 - 304. [ 4 ] 张金泽. 支持向量机及其在智能故障诊断中的应 用研究 [D ]. 军械工程学院 , 2006: 32 - 38. [ 5 ] Stützle T, Hoos H. The MAX - M IN ant system and local search for the traveling salesman p roblem [ A ]. Proceedings of IEEE2ICEC2EPS’97 [ C ]. [ S. l. ]: IEEE Press, 1997: 309 - 314. [ 6 ] 段海滨. 蚁群算法原理及其应用 [M ]. 北京 :科学 出版社. 2005. [ 7 ] 汪镭 ,吴启迪. 蚁群算法在连续空间寻优问题求解 中的应用 [ J ]. 控制与决策 , 2003, 18 ( 1 ) : 45 - 48, 57. [ 8 ] W ang L, W u Q D. Ant system algorithm for op tim iza2 tion in continuous space[A ]. Proceeding of the 2001 IEEE International Conference on Control Application [ C ]. Mexico City, Mexico, 2001, 395 - 400. [ 9 ] 陈崚 ,沈洁 ,秦玲. 蚁群算法求解连续空间优化问 题的一种方法 [ J ]. 软件学报 , 2003, 13 (12) : 2317 - 2323. [ 10 ] W en Y, W u T J. Dynam ic window search of ant colo2 ny optim ization for complex multi2stage decision p rob2 lem s[A ]. Proceeding of 2003 IEEE International Con2 ference on System, Man and Cybernetics[ C ]. Hang2 zhou, China: Zhejiang Univ, 2003. 4091 - 4097. 864
还剩4页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享pdf获得金币 ] 2 人已下载

下载pdf

pdf贡献者

forestqqqq

贡献于2011-11-24

下载需要 5 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf