改进GA和SVM求解模型

首先，定义染色体；染色体为0-1二进制串，其长度为所提取特征序列的个数R。1表示该特征被选中，否则为没有被选中。其次，设定初始种群；随机生成长度为R的染色体N个，作为初始种群的个体；为了保证种群中个体的多样性，本例中取N=80。再次，设计适应度函数；适应度函数与SVM训练出的分类器的性能有关，其中包括敏感性和特异性；定义适应度函数为式（2-1）模型中的目标函数。在分类效果相同的情况下，特征组合中所含特征数越多，训练模型就越复杂，越容易引起过拟合问题。当两个染色体的适应度函数值相等时，染色体中所含被选中的特征个数少的优于所含被选中的特征个数多的染色体。然后，确定遗传算子产生下一代染色体；利用轮盘赌的方式选择适应度高的染色体并复制到中间种群，中间种群由概率p_c=0.1的“一点交叉”和概率p_m=0.05变异生成下一代种群。最后，设定终止条件。当GA的迭代次数等于最大迭代次数100时，程序终止。为了得到更优的解，加入了一个基于深度邻域的新改的方法。对于每一代的最好解C_b={…，1，…}，通过变异每一位基因，同时其他基因保持不变得到新的个体C_c={…，0，…}，如果f（C_c）>f（C_b）时，更新C_c为当前代的最好的解C_b。SVM是基于统计学习理论的VC维（Vapnik Cherovnenkis Dimension）理论和结构风险最小原理（Structural Risk Minimization Principle，SRM）^[15]，通过解决一个线性二次规划问题来求解决策面，目标是找到训练错误和泛化能力的平衡点。这也使得SVM方法比基于经验风险最小化（Empirical Risk Minimization Principle，ERM）的人工神经元网络等方法具有更好的泛化能力。SVM将非线性可分样本经非线性变换函数（核函数）映射到一个高维空间上，并在高维空间中构造最优分类超平面，这个超平面不但能将两类样本点正确分开，而且使分类间隔最大。SVM的基本思想可以用图2-2中的两维情况说明，即实心点和空心点分别代表两类样本，H为分类面，H₁和H₂分别为过各类中离分类线最近的样本且平行于分类线的直线，它们之间的距离叫作分类间隔（margin）。所谓最优分类面就是要求分类面不但能将两类正确地分开（训练错误率为0），而且使分类间隔最大。

图2-2 线性可分情况下的最优分类面

SVM的分类决策函数为

式中：a_i为支持向量；y_i取1或-1；b为分类的阈值；k（x_i，x）=ϕ（x_i）·ϕ（x_j）为核函数。(www.xing528.com)

这里的分类器类型用的是C-SVM，核函数包括有多项式核函数、高斯径向核函数和多层感知器核函数，这里用的是高斯径向核函数（RBF，Radial Basic Function）^[16]，即

k（x_i，x_j）=exp（-γ‖x_i，x_j‖²） γ>0 （2-3）

式中：γ通常取构造分类器训练样本的总个数的倒数。

SVM分类器有一个缺点，就是当训练样本集中的两类样本的数目相差很大时，分类结果总是偏向样本数目较大的类。为了避免这一问题，本书用相同数目的样本来训练分类器，而分类器的程序实现是基于LIBSVM[17]完成的。