改进遗传算法的支持向量机特征选择的设计和实现

 

　　支持向量机是由Vapnik领导的AT&TBell实验室研究小组在1963年提出的一种新的非常有潜力的分类技术，SVM是一种基于统计学习理论的模式识别方法，主要应用于模式识别领域。由于当时这些研究尚不十分完善，在解决模式识别问题中往往趋于保守，且数学上比较艰涩，这些研究一直没有得到充分的重视。直到90年代，统计学习理论 （Statistical Learning Theory，SLT）的实现和由于神经网络等较新兴的机器学习方法的研究遇到一些重要的困难，比如如何确定网络结构的问题、过学习与欠学习问题、局部极小点问题等，使得SVM迅速发展和完善，在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。从此迅速的发展起来，现在已经在许多领域（故障诊断、图像识别、回归预测等）都取得了成功的应用。

　　目前特征选择的方法主要有主成分分析法、熵原理、粗糙集理论等。然而由于这些方法主要依据繁复的数学理论，在计算过程中可能存在求导和函数连续性等客观限定条件，在必要时还需要设定用来指导寻优搜索方向的搜索规则。遗传算法作为一种鲁棒性极强的智能识别方法，直接对寻优对象进行操作，不存在特定数学条件的限定，具有极好的全局寻优能力和并行性；而由于遗传算法采用概率化的寻优方法，所以在自动搜索的过程中可以自主获取与寻优有关的线索，并在加以学习之后可以自适应地调整搜索方向，不需要确定搜索的规则。因此遗传算法被广泛应用在知识发现、组合优化、机器学习、信号处理、自适应控制和人工生命等领域。

　　基于改进遗传算法的特征选择

　　遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。图1中所示的是标准的遗传算法的流程框图。

 

 

　　传统的遗传算法存在早熟收敛、非全局收敛以及后期收敛速度慢的缺点，为此本文提出了一种能够在进化过程中自适应调节变异率，以及利用模拟退火防止早熟的改进遗传算法，同时该算法利用敏感度信息可以有效地控制遗传操作。图2是改进遗传算法的流程框图。

　　随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（Evolution Programming,EP）以及进化策略（Evolution Strategy,ES）等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的智能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。

 

 

　　染色体编码和适应度函数

　　所谓编码是指将问题的解空间转换成遗传算法所能处理的搜索空间。在特征选择问题中，常常使用二进制的编码形式，使得每个二进制就是一个染色体，其位数长度等于特征的个数。每一位代表一个特征，每位上的1表示选中该特征，0则表示不选中。每一代种群都由若干个染色体组成。

　　适应度函数是整个遗传算法中极为重要的部分[6]，好的适应度函数能使染色体进化到个体，它决定了在整个寻优过程中是否能够合理地协调好过早收敛和过慢结束这对矛盾。由于本文针对的是支持向量机的特征选择问题，所以考虑以分类正确率和未选择的特征个数这两个参数作为函数的自变量，将分类正确率作为主要衡量标准，未选择的特征个数为次要标准。由此建立以下的适应度函数：

　　式中C为分类正确率，为未选择的特征个数，a是调节系数，用来平衡分类正确率和未选择的特征个数对适应度函数的影响程度，同时该系数也体现了用少的特征得到较大分类正确率的原则，在本文中a取0.00077。由上式可知，分类正确率越高，未选的特征个数越多，染色体的适应度就越大。

　　选择操作

　　选择操作需要按照一定的规则从原有的种群中选择部分个体用来交叉和变异。选择原则建立在对个体适应度进行评价的基础上，目的是避免基因损失，提高全局收敛性和计算效率。本文首先将整个种群中的前40%的个体保留下来，以确保有足够的优良个体进入下一代，对剩下的60%的个体采用轮盘算法进行选择，这样做可以弥补保留前40%个体而带来的局部解不易被淘汰的不利影响，有利于保持种群的多样性。

　　基于敏感度信息量的交叉、变异操作

　　独立敏感度信息量Q（i）指的是对在所有特征都被选中时计算所得到的适应度值Allfitness以及只有特征i未被选中时计算得到的适应度值Wfitness（i）按式（2）进行计算得到的数值。独立敏感度信息量刻画了适应度对特征i是否被选择的敏感程度。

　　互敏感度信息量R(i，j)由(3)式可得，互敏感度信息量体现了特征i与特征j之间对适应度的近似影响程度。

　　交叉操作的作用是通过交换两个染色体之间的若干位从而生成含有部分原始优良基因的新个体。由式(3)可知互敏感度信息量可作为不同特征之间含有相似分类信息的一种度量，所以可以将互敏感度信息量代入式(4)计算出染色体在第位发生交叉的几率b(i)，在式(4)中i和j分别代表特征i和特征j，是染色体的长度。b(i)是特征i相对于其他所有特征在互敏感度信息量上的归一量，反映了特征与其余特征在相似信息量上的总和。由此对应到染色体上，b(i)就可以认为是染色体的第i位与整个染色体在基因信息上的相关性，b(i)越小则说明相关性越大，第i位与整个染色体所含的基因信息越接近，此位为分裂点的几率越小。由于b(i)是归一化量，故可采用轮盘算法来选择一个交叉点。

    变异操作是引入新物种的重要手段，可以有效地增加种群个体的多样性。本文中的变异率Pm采用相邻两代之间的适应度增幅比作为自变量进行自适应调节，如式(5)所示。当适应度增幅比正向增大时，较小的增幅比可以使变异率维持在中等水平，并且变异率随着增幅比的增大而缓慢降低，这样既能够拥有一定数量的新个体也可以抑制过多不良染色体的产生，保证染色体的进化足够稳定;而当适应度增幅比反向增大时，由较小增幅比则可以获得较高的变异率，并且变异率也伴随增幅比同比缓慢升高，确保有足够的染色体发生变异，稳定地加快进化速度。

　   式中dis指新生种群的适应度相对于原种群的适应度的增幅比，j与k均是区间(0，1)上的调节系数。文中的j与k分别取0.65和0.055。

　　独立敏感度信息量在一定程度上体现了单个特征所含有的分类信息量，如果独立敏感度信息量小，则说明该特征所含信息大部分对分类没有帮助，即该基因位发生突变后对整个染色体的优异性影响不大，突变的概率也就相应减小。因此将独立敏感度信息量归一化后所得到的q(i)作为特征i被选为变异点的概率。变异点的具体选择方法为：针对一个染色体按照染色体的位数进行循环遍历，在该循环中由变异率Pm判定是否产生变异位。若需要产生变异位，则依据q(i)按照轮盘算法进行选择。

　　模拟退火选群

　　在每一轮进化完成后都需要决定进入下一轮进化的种群。如果过多地将较优种群作为父代，就会使算法过早收敛或搜索缓慢。文献[7]中指出模拟退火算法能够以一定的概率接受劣解从而跳出局部极值区域并终趋于全局解，因此可以将上文提到的适应度增幅比作为能量函数，运用模拟退火的Meteopolis准则来选择待进化的种群。为了使每个种群得到充分地进化，预防解的丢失，这里采用设置退火步长的策略来实现模拟退火选群。该策略具体为：使退火步长对同一种群作为父代的次数进行计数，一旦产生更优种群则退火步长就置零并重新计数。若退火步长累计超过一定的阈值时，就进入模拟退火选群阶段。退火步长累计到一定数量意味着原有种群的进化已经停滞，需要用模拟退火算法摆脱这种停滞状态。如果增幅比大于零，则说明新生种群优于原有种群，这时完全接受新种群进入下一轮进化；否则新生种群劣于原有种群，并以一定的概率p接受较劣的新生种群[8]进入下一轮进化。接受概率p由式（6）和式（7）共同决定，其中dis为增幅比，T（s）指温度参数，T0和s分别是初始温度和迭代次数。

 

　　以上两式的参数要满足进化对接受概率的要求。即增幅比负增长越大，接受概率降低越迅速，但接受概率随迭代次数的增加应缓慢下降。这样做能够保证在有限的迭代次数内有一个适应度较优的新生种群进入下一轮进化，以达到减少计算量和优选待进化种群的目的。在本文中T0=0.2，A=0.9，m=0.5。

　　实例的验证与分析

　　UCI数据库常用来比较各种方法的分类效果，因此可以用其验证本算法对支持向量机作用后的分类效果[9][10]。文献[11]采用了UCI数据库中的German、Ionosphere和Sonar三种数据作为实验对象，为了便于与文献[11]中所用的几种方法进行对比，本文也采用这三种数据进行实验，并按照文献中所述的比例将各类数据分成相应的训练样本和测试样本。

　　在种群规模为30，交叉率为0.8，起始变异率为0.1的条件下使用支持向量机作为分类器（惩罚参数为13.7，径向基核函数参数为10.6）对所选数据进行分类，表1中显示了本文算法与文献[11]中几种算法在分类效果上的对比，表2给出了三种数据的终选择结果。表1中共出现了四种方法：方法1：使用本文算法；方法2：使用NGA/PCA方法；方法3：使用PCA方法；方法4：使用简单遗传算法。

 

 

　　由于本文算法旨在用少的特征个数化分类正确率，因此从表1中可以看出本文算法在特征选择个数和分类正确率上均比其他三种方法更具优势。由于NGA/PCA算法是针对简单遗传算法和主成分分析法的不足而做的改进，其性能优于简单遗传算法和主成分分析法，所以本文算法的分类效果优于NGA/PCA算法这一事实更能说明该算法可以较好地解决支持向量机的特征选择问题。

　　结语

　　本文针对主成分分析法在主成分特征选择中存在的不确定性，提出了以类内类间距离为适应度函数，利用遗传算法对主成分分析形成的综合特征变量进行选择。该方法充分利用遗传算法全局寻优、计算速度快的特点，能高效解决支持向量机的特征选择问题。仿真结果表明该方法适于不同规模的电力系统，能够处理大数据量样本，具有实用化价值。