PDF《自适应 GA SVM 参数选择算法研究》

第28卷第 4期哈尔滨工程大学学报Vo.

l

28 .

4 2007年 4月 Journal ofH arb in EngineeringU niversity Apr .

2007 自适应 GA SVM 参数选择算法研究 刘胜李妍妍 (哈尔滨工程大学 自动化学院, 黑龙江 哈尔滨 150001) 摘要: 支持向量机是一种非常有前景的学习机器, 它的回归算法已经成功地用于解决非线性函数的逼近问题. 但是, SVM 参数的选择大多数是凭经验选取, 这种方法依赖于使用者的水平, 这样不仅不能获得最佳的函数逼近效果, 而且采用人工的方法选择 SVM 参数比较浪费时间, 这在很大程度上限制了它的应用. 为了能够自动地获得最佳的 SVM 参数, 提出了基于自适应遗传算法的 SVM 参数选取方法. 该方法根据适应度值自动调整交叉概率和变异概率, 减少了遗传算法的收敛时间并且提高了遗传算法的精度, 从而确保了 SVM 参数选择的准确性. 将该方法应用于船用 锅炉汽包水位系统建模, 仿真结果表明由该方法所得的 SVM 具有较简单的结构和较好的泛化能力, 仿真精度高, 具 有一定的理论推广意义. 关键词: 机器学习;

支持向量机;

支持向量机回归;

自适应遗传算法;

非线性系统辨识 中图分类号: TP181 文献标识码: A 文章编号:

1006 7043( 2007)

04 0398

05 Para m eter selection algorithm for support vector machines based on adaptive genetic algorithm L I U Sheng , L IY an yan ( College of Auto m ation, H arb in Engineering University , H arb in 150001, Ch ina) Abstract : The support vectormachine ( SVM ) is a prom ising artificial intelligence technique , in w hich the regres sion algorithm has already been used to solve the nonlinear function approach successfully . Un fortunately, most us ers select parameters for an SVM by ru le of thumb, so they frequently fail to generate the opti mal approach ing effect for the function . Th is has restricted effective use of SVM to a great degree . In order to get opti mal parameters auto matically , a new approach based on an adaptive genetic algorithm ( AGA ) is presented , w hich automatically ad justs the para m eters for SVM. This method selects crossover probability and mutation probab ility accord ing to the fitness values of the object function , therefore reduces the convergence ti m e and i mproves the precision ofGA, in suring the accuracy of parameter selection . Th is method w as applied to modeling of w ater level system of a sh ip boilers '

drum. S i mu lation results reveal that th is method of parameter selection for SVM has a si mple structure and good generalization ability. Since si mu lation precision is high , this m ethod possesses certain practical application significance . K eywords : mach ine learn ing ;

support vectorm ach ine ;

support vectorm ach ine regression;

adaptive genetic algo rithm;

nonlinear syste m identification 收稿日期: 2006- 05-

29 . 基金项目: 黑龙江省自然科学基金资助项目 ( 2004- 19). 作者简介: 刘胜(1957- ), 男, 教授, 博士生 导师, E m ai: l liu. sch@ V I P163. com. 支持向量机 ( support vector machines , SVM )是20世纪 90年代由 Vapnik等人提出的一种新的学习 机[1] . 近年来, 由于其优越的学习能力, 受到了国际 学术界的广泛重视. S VM 是在统计学习理论的基础 上形成的, 力图实现结构风险的最小化, 从而提高了 学习机的泛化能力. 与人工神经网络相比, SVM 克 服了神经网络所固有的局部极小点、 过学习现象以 及结构和类型的选择过于依赖于经验等缺陷. 基于 SVM 方法的回归估计以可控制的精度逼近任一非 线性函数, 同时具有全局最优、 良好的泛化能力等优 越性能, 因此支持向量机回归 ( support vector ma ch ine regression, SVR)算法的应用非常广泛. 目前, SVR 算法已被成功地应用于时间序列的预测研 究[2] , 以及其他诸如在非线性建模与预测 [

3 9 ] 、 优化 控制 [

10 11] 等方面的研究. 但是, 和其他学习算法一 样, SVM 的性能依赖于学习机的参数, 且其参数的 选取对于经验的依赖性比较强, 到目前为止, 还没有 指导 SVM 参数选择的好方法. 遗传算法 ( genetic al gorith m, GA ) 是模拟生物进化过程中的自然选择和 遗传变异的一种随机优化方法. 它具有很强的全局 搜索能力, 并且这种搜索能力不依赖于特定的求解 模型. 传统的基本遗传算法 ( sample genetic algo rithm s , SGA)通常会带来遗传算法的欺骗问题 [

12 ] , 即早熟问题和进化缓慢问题. 针对基本遗传算法存 在的问题, 采用交叉概率和变异概率可以根据适应 度值进行自动调整的自适应遗传算法 ( adaptive ge netic algorith m, AGA )对SVM 中的参数进行自动选 取. 由于 AGA 有很强的搜索能力, 从而为寻找全局 最优解提供了保障, 为解决 SVM 的参数选取问题提 供了一条有效的途径.

1 SVR算法 设给定的输入样本 x 为n维向量, l 个样本及 其输出值可表示为 (x1, y1 ), (x2, y2 ), , (x1, y1 ) R n R. 对于回归问题, 它的基本思想是通过一个非线性映 射 将数据映射到高维特征空间 F, 并在这个空间 进行线性回归: f (x ) = w T (x) + b( : R n → F, w F ). (1) 式中: b是阈值. 这样, 在高维特征空间的线性回归 就对应于低维输入空间的非线性回归, 免去了在高 维空间 w 和(x )的点积计算. 这里, ( )是指由 输入空间到特征空间的非线性映射, f ( )在特征空 间中表示为一个线性函数. SVR 的目的是用函数 f ( )去拟合数据样本, 同时保证能得到很好的泛化 能力. 为了增加回归的鲁棒性, Vapn ik [

1 ] 提出了 不 灵敏损失函数, 其特点是忽略小于 的拟合误差. 综 合考虑拟合误差和函数复杂度, SVR 可以表示为如 下的约束优化问题: m in

1 2 w T w + C l i=

1 ( i + * i ) , yi - w T (xi ) - b + i, s . . t w T (xi ) + b - yi + * i , i, * i

0 ( 2) 式中: C >

0 是函数复杂度和损失误差的一个平衡 量. 式(2)的Lagrange函数为 L =

1 2 w T w + C l i=

1 ( i + * i ) - l i=

1 i (w T (xi ) + b - y1 + + i ) - l i=

1 * i (yi - w T (xi ) - b + + * i ) - l i=

1 ( i i + * i * i ) ( 3) KKT优化条件要求 Lagrange函数相对于变量 w, b, i, * i 的偏导数为 0. L w =

0 w = l i=

1 ( i - * i ) (xi ), ( 4) L b =

0 l i=

1 ( i - * i ) = 0, ( 5) L i =

0 i = C - i, ( 6) L * i =

0 * i = C - * i . ( 7) 把上述 KKT条件代入优化问题 ( 2)的目标函数中, 根据对偶原理和核函数技术, 可以得到式 ( 2) 的对 偶化问题: m in

1 2 l i=

1 l j=

1 ( i - * i ) ( j - * j )k(xi, xj ) + l i=

1 ( i + * i ) - l i=

1 yi ( i - * i ), s . . t l i=

1 ( i - * i ) = 0,

0 i, * i C, i =

1 ,

2 , , l . ( 8) 式中: k(xi, xj ) = (xi ) T (xj )称为核函数, 是满足 M ercer条件的任何对称的核函数. 这里采用径向基 ( RBF)函数 k(x, xi ) = exp( - x- xi

2 2

2 ). SVM 的输出为 f (x ) = l i=

1 ( i - * i )k(xi, x) + b, ( 9) b =

1 2 m in(yi - g i=

1 ( * i - i ) k(x, xi ) ) + m ax(yi - g i=

1 ( * i - i )k(x, xi ) ) . ( 10)

2 SVM 参数对网络性能的影响

399 第 4期 刘胜, 等: 自适应 GA SVM 参数选择算法研究

2 .

1 核函数作用及核参数的影响 V apn ik等人在研究中发现, 不同的核函数对 SVM 的性能影响不大, 反而核函数的参数是影响 SVM 性能的关键因素 [ 1] . 对于 RBF 核而言, 核函数 的参数主要是核的宽度

2 , 它主要影响样本数据在 高维特征空间中分布的复杂程度 [ 13] .

2 .

2 参数 C 的影响 式(2)中误差惩罚参数 C 的作用是在确定的数 据子空间中调节学习机器置信范围和经验风险的比 例以使学习机器的推广能力最好, 不同数据子空间 中最优的 C 不同. 在确定的数据子空间中, C 的取值 小表示对经验误差的惩罚小, 学习机器的复杂度小 而经验风险值较大;

反之亦然. 前者称为 欠学习 现象, 而后者则为 过学习 . 每个数据子空间至少 存在一个合适的 C 使得 SVM 推广能力最好. 当C超过一定值时, SVM 的复杂度达到了数据子空间允 许的最大值, 此时经验风险和推广能力几乎不再变 化. 然而, 目前还没有一个统一的方法来决定 C 的 最佳取值. 一般的方法是试凑, 通过不断实验来得到 满意的结果.

2 .

3 不敏感损失函数的影响 文献 [ 1]指出, 不敏感损失函数的大小决定了 支持向量的个数. 越大, 支持向量的个数越少, 函 数估计的精度越低;

越小, 则支持向量的个数越 多, 函数估计的精度越高. 但是 也不是越小越好, 因为虽然精度提高了, 但是算法所需要的时间也变 长了, 所以, 必须选择适当的 , 以保证 SVM 的速度 和精度. 同时, 不敏感损失函数 还反映了 SVM 对 数据噪声水平的预测, 噪声较大时选用较大的 值, 噪声较小时选用较小的 值.

3 算法的实现

3 .

1 编码方式 由于 SVM 参数的寻优过程是一个复杂的连续 参数优化问题. 所以算法采用浮点数编码方式, 这样 避免了二进制编码在遗传操作时反复译码、 编码的 操作以及二进制字符串有限的长度对进化算法性能 和求解精度的影响. 浮点数编码不受维数限制, 不需 要进行编码、 解码操作, 有效提高了计算速度和求解 精度, 并且浮点编码比二进制编码在变异操作上能 更好地保持种群多样性.

3 .

2 适应度函数 为了使支持向量机输出与目标函数之间误差的 平方和最小, 将适应度函数定义为 F ( , C, ) =

1 l i=

1 (yi - f (xi ) )

2 + e . ( 11) 式中: e为避免分母为零所加的一个小数.

3 .

3 遗传操作

3 .

3 .

1 选择操作 文中采用基于排序的适应度分派原则 ( rank based fitness assignmen t). 首先按照适应度值对种群 内的个体进行排序. 然后按下式确定第 i个个体被 选择的概率: Pi = c(

1 - c) i-

1 . ( 12) 式中: i为个体排序序号;

c为排序第一的个体的选 择概率. 选择概率仅仅取决于个体在种群中的序位, 而 不是实际的适应度值. 以概率 Pi 采取轮盘赌方法完 成........