基于混沌机制的人工蜂群算法优化的支持向量机分类器

刘霞+张姗姗+胡铭鉴+庞永贵

（1.2. 东北石油大学 电气信息工程学院，黑龙江 大庆163318;3. 新疆石油勘探设计研究院，新疆 克拉玛依 834000;4. 大庆物探一公司，黑龙江 大庆 163357）

摘要：支持向量机的分类性能在很大程度上取决于其相关参数的选择，为了改善支持向量机的分类准确率，本文采用基于混沌机制的人工蜂群算法对其参数进行优化。在传统人工蜂群算法的基础上，采用Logistic混沌映射初始化种群和锦标赛选择策略，进一步提高人工蜂群算法的收敛速度和寻优精度。该方法采用分类准确率作为适应度函数，利用人工蜂群算法对支持向量机的惩罚因子和核函数参数进行优化。通过对多个标准数据集的分类测试，证明基于混沌机制的人工蜂群算法优化的支持向量机分类器能够获得更高的分类准确率。

关键字：人工蜂群算法，支持向量机，参数优化，混沌机制，锦标赛选择策略

中图分类号：TP311 文献标识码：A  文章编号：黑龙江省长江学者后备计划（2012CJHB005）

Artificial colony algorithm based on chaotic mechanism optimization of support vector machine classifier

LIU Xia1，ZHANG Shan-shan2，HU Ming-jian3，PANG Yong-gui4

（1.2.Northeast Petroleum University Electrical information engineering institute，Heilongjiang Daqing 163318;3.Xinjiang Design Institute，China Petroleum Engineering，Xinjiang Karamay 834000;4.Daqing Gepphysical Exploration Company of NO.1，Heilongjiang Daqing 163357）

Abstract： The classification performance of support vector machine （SVM） to a large extent depends on the selection of its parameters， in order to improve the classification accuracy of support vector machine （SVM）， using Artificial bee colony algorithm based on chaotic mechanism to optimize the parameters in this paper. On the basis of the traditional artificial colony algorithm， using the Logistic chaotic mapping initialization population and tournament selection strategy， further improve the artificial colony algorithm convergence speed and optimization precision.The method adopts the classification accuracy as fitness function， using artificial colony algorithm of support vector machine （SVM） penalty factor and the kernel function parameter optimization. By standard data sets with the classification of the test， prove that artificial colony algorithm based on chaotic mechanism optimization of support vector machine classifier can achieve higher classification accuracy.

Keywords： Artificial colony algorithm， Support vector machine （SVM）， parameters optimization， Chaotic mechanism， Tournament selection strategy

1 引言

支持向量机（Support Vector Machines， SVM）是以统计学习理论为基础，针对有限样本的一种通用学习方法，能有效解决小样本、高维数、非线性等问题[1-3]。因而被广泛应用在故障诊断、安全检测、图像处理等领域。由于模型参数包括惩罚因子C、核函数类型和核函数参数的选择会严重影响最终的分类结果[4]，因此在利用SVM进行分类时，需要研究的热点问题就是如何通过选择模型参数以获取最优分类结果。

实践证明，支持向量机的分类准确率、惩罚因子以及核函数参数之间存在多峰值函数关系[5]，而梯度下降算法、遗传（GA）算法、蚁群（ACO）算法及标准粒子群（PSO）算法这些目前常用的SVM参数优化方法，由于在寻优过程中会陷入局部最优解而使得分类效果不能达到最佳。2005年，Karaboga[6]提出了一种新的群集智能优化算法-----人工蜂群（Artificial bee colony，ABC）算法，并通过大量的标准函数测试证明[7，8]，ABC算法具有比传统方法更佳的优化性能，它通过蜜蜂之间的分工合作，同时兼顾了精密搜索已知解域和扩展新解域，从而降低了算法陷入局部最优解的概率。

本文使用的支持向量机采用RBF核函数，利用基于混沌机制的人工蜂群算法对模型参数进行优化，通过对CUI数据库中标准数据集的训练和分类测试实验证明，基于混沌机制的ABC算法能够克服局部最优解，在一定程度上加快搜索速度，优化后的SVM具有更高的分类准确率，从而验证了本文方法的可行性和有效性。

2 引入混沌机制的ABC算法

2.1 ABC算法优化原理

ABC算法模拟实际蜜蜂采蜜机制来处理函数的优化问题，人工蜂群分为以下三部分：引领蜂、跟随蜂和侦查蜂。ABC算法在求解最优问题时，食物源的位置对应优化问题的可能解，每个食物源的花蜜量对应每个解的适应度值。

一个非线性函数最小值问题可以表示为：

min f（X），XL≤ X≤XU，XL和XU分别是变量X取值的上界和下界，X=（x1， x2， x3…xn） ，n为变量的维数。利用ABC求解该最优问题的具体过程如下：

1、种群初始化

在取值范围内按（1）随机产生一个包含SN个个体的初始种群。

，

i=1，2…SN                     （1）

式中，表示初始种群中的第i个个体，它的维数n为优化参数的个数;rand（）表示在区间[0，1]上产生的随机数。

对初始种群的一半计算适应度值及可行解的质量，记录目前质量最好的解。

2、引领蜂阶段

引领蜂的数量等于食物源的一半，即SN/2，表示初始种群中适应度值较优的一半个体，与食物源的位置相对应。引领蜂随机选取食物源进行交叉搜索，按式（2）对食物源进行更新，即产生一个新解。

（2）

式中，k∈{1，2， …SN/2}，j∈{1，2， …n}，且k≠i，为[-1，1]之间的随机数。计算新解的适应度值，如果新解的适应度优于旧解，那么就用新解代替旧解;反之，保留旧解。

3、跟随蜂阶段

跟随蜂的数量跟引领蜂的数量是相等的，也是SN/2。跟随蜂根据引领蜂搜索的信息，按照一个与适应度相关的概率来选择一个食物源的位置，即解得位置，并像引领蜂一样按式（2）对食物源进行更新，若新解的适应度值优于旧解，用新解替代旧解;反之保留旧解。跟随蜂选择食物源的概率公式为：

4、侦查蜂阶段

经过引领蜂与跟随蜂的搜索以后得到与初始种群相同大小的新种群，为了避免随着种群的进化出现种群多样性丧失过多的问题，人工蜂群算法模拟侦查蜂搜索潜在蜜源的生理行为，提出了一种特有的搜索方式——侦查蜂搜索。如果某一个体（解）连续“Limit”代没有变化，与之对应的个体变异成侦查蜂，按式（2）搜索产生新个体，计算新个体的适应度值并与原个体比较，若优于原个体则代替原个体。

经过引领蜂、跟随蜂和侦查蜂三个阶段的搜索之后，整个种群进化到下一代，这个过程反复循还直至达到最大迭代次数MaxCycles或者误差达到预定的范围之内时结束算法。

2.2 基于混沌机制的ABC算法

1、混沌初始化

混沌看似混乱却有着精致的内在结构，是非线性系统中特有并普遍存在的一种现象。随机性、遍历性和规律性是混沌最典型的特点，使得它能够按照自身的某一“规律”不重复地遍历给定范围内的所有状态。本文采用Logistic混沌映射来初始化种群。Logistic混沌映射的方程如下：

（5）计算i=i+1，如果i大于种群个数SN，则结束，否则返回（2）继续循环。

经过以上步骤就可以产生SN个初始种群。

2、锦标赛选择策略

锦标赛是基于局部竞争机制的一种选择策略，它的基本思想是在种群中随机选出k个个体进行适应度值的比较，选择适应度值较优的个体。参数k是竞赛的规模，通常情况取默认值2。在ABC算法中，将第t代某个个体的适应度值与其它所有个体两两进行比较，对适应度值较优的个体授予一分，对每个个体重复这一过程，个体得分越高表示个体越优秀，被选择的概率越大。这种方式根据种群个体间适应度值的关系进行选择，与个体的适应度值无关，因此对适应值的正负没有要求，从而提高优秀个体被选择的概率，在一定程度上避免了比例选择策略可能出现的过早收敛和停滞现象。

3 基于混沌机制的人工蜂群算法优化的SVM分类器

3.1 SVM原理

SVM分类的过程就是在空间找到一个满足分类要求的最优分类超平面，该超平面在保证分类正确的基础上，还能够使两类数据集间的距离最大。将SVM的学习过程转化为优化问题，设有训练样本集{（xi，yi），i=1，2， ……l}，输入xiRn，期望输出yi{+1，-1}，其中+1，-1分别代表两类的类别标识，则这个数据集的分类超平面可描述为wgx+b=0。寻找最优超平面的公式如下：

为核函数，其值受核函数参数σ的影响，目前常用的核函数主要有多项式核函数、径向基函数、多层感知器和动态核函数等[9，10]。

综上可知，寻找最优超平面的关键在于选择最优核函数的前提下寻找最优的惩罚因子C和核函数参数σ，以使得SVM获得最大分类正确率。

3.2 基于混沌机制的ABC-SVM算法流程

1、算法初始化，设定最大迭代次数MaxCycles、种群个数SN、维数D（由于需要优化的参数有两个，所以D=2）、个体最大更新次数Limit、惩罚因子C和核函数参数σ的最大值（cmax，gmax）和最小值（cmin，gmin）。

利用式（5）产生混沌初始种群（即惩罚因子C和核函数参数σ的初值），将惩罚因子C和核函数参数σ的初值写入SVM模型，并对训练样本进行训练分类，准确率即为ABC的适应度值，记录最好的适应度值和对应的参数值。

2、引领蜂按式（2）搜索更新，计算适应度值，若新食物源的适应度值优于搜索前，则代替先前的食物源。

3、跟随蜂根据锦标赛选择策略选择食物源，并按式（2）在食物源附近进行搜索新的食物源。计算新食物源的适应度值，若新食物源的适应度值优于搜索前，则代替先前的食物源。

4、判断是否存在需要放弃的食物源。如果某个食物源进过Limit次循环之后没有改变，则放弃该食物源，同时对应的引领蜂变异为侦查蜂，按式（5）产生新的食物源。

5、迭代次数Cycles=Cycles+1，若Cycles达到最大迭代次数MaxCycles或分类准确率达到设定精度结束算法，输出最优值;否则返回步骤2。

3.3实验仿真与结果分析

为了验证本文算法的有效性和优越性，采用UCI数据库（http：//archive.ics.uci.edu/ml/）中的3个具有代表性的数据集Heart、Iris和Wine进行训练和分类实验，数据集详细信息如表1所示。ABC算法的控制参数设置如下：食物源数量SN设为20，最大迭代次数MaxCycles设为1000，个体最大更新次数Limit设为50，惩罚因子的搜索范围设为[0.1，100]，核函数参数的搜索范围设为[0.01，1000]。

表1 测试数据集说明

将传统SVM、ABC-SVM和基于混沌机制的ABC-SVM的测试结果进行比较，比较结果如表2所示。由这些实验结果可以看出，ABC算法能够兼顾全局最优解和局部最优解的搜索，对SVM进行参数优化后，可得到更高的分类正确率，而基于混沌机制的ABC算法能够进一步提高支持向量机的分类准确率。

表2  三种算法的分类测试结果

三种算法进行3次试验后得到的平均运行时间如表3所示，从表中的数据可以看出，对支持向量机进行参数优化，由于算法的复杂性增加从而使得运行时间增加，但是基于混沌机制的ABC算法优化的SVM在一定程度上缩短了运行时间，与传统ABC优化的SVM比较表现出更好的收敛性，有效地降低了搜索运行时间。

表3 三种算法的运行时间对比

4、结 语

支持向量机模型参数的选择在很大程度上影响支持向量机的分类准确率，为了找到最优的参数取值，采用人工蜂群算法优化支持向量机的方法，并在传统蜂群算法的基础上加入混沌思想及采用锦标赛选择策略，提出基于混沌机制的人工蜂群算法优化的支持向量机分类器。算法中，把支持向量机的分类准确率当做人工蜂群算法的适应度函数，采用RBF核函数，利用人工蜂群算法优化支持向量机的惩罚因子C和核函数参数σ。通过对UCI标准数据及的分类实验证明，基于混沌机制的人工蜂群算法具有较强的局部和全局搜索能力，在很大程度上克服了局部极值点的问题，其优化的支持向量机与传统的支持向量机相比，具有更高的分类准确率，并对于文中测试的数据集而言，有效地缩短了搜索时间。在本文的研究过程中发现，在人工蜂群算法初始化过程中，一些控制参数是通过多次试验得到较优的初值，因此，如何更快更有效地确定人工蜂群算法中的初始化参数对于进一步提高算法的效率有着不可忽视的作用。

参考文献：

[1] Vapnik V N. The nature of statistical learning [M].2nd ed. New York： Springer， 2000.

[2] CRISTIANINI N， et al. An introduction to support vector machines and other kernel-based learning methods [M]. Beijing： Mechanical industry press，2005.

[3] 杨志民，刘广利.不确定性支持向量机原  理及应用[M].北京：科学出版社，2007.

[4] SHAO Jun， LIU Jun-hua， QIAO Xue-guang，etal.Temperature compensation of FBG sensor based on support vector machine[J]. Journal of Optoelectronics Laser，2010， 21（ 6）： 803-807.

[5] 刘春波，王鲜芳，潘 丰. 基于蚁群优化算法的支持向量机参数选择及仿真[J]. 中南大学学报：自然科学版， 2008， 39 （6）： 1309-1313.

[6] Karaboga D. An Idea Based on Honey Bee Swarm for Numerical Optimization[R]. TECHNICAL REPORT-TR06，Erciyes University ， Engineering Faculty ，Computer Engineering Department，2005.

[7] Karaboga D，Basturk B. A powerful and efficient algorithm for numerical function optimization：Artificial bee colony （ABC） algorithm[J]. Journal of Global Optimiza- tion， 2007，39（3）：459-471.

[8] Karaboga D，Basturk B. A comparative study of artificial bee colony algorithm[J]. Applied Mathematics and Computation， 2009，214（1）：108-132.

[9] 史忠值.知识发现.北京：清华大学出版社，2002，203-207.

[10] Amari S，Wu S.Improving support vector machine classifier by modifying kernel

functions.Neural Networks，1999， 12（9）：

783-789.