改进的GA－SVM在人脸识别中的应用

刘 冰，刘广璞

(中北大学机械工程与自动化学院，山西太原 030051)

0 引言

人脸识别是模式识别和机器视觉领域中最有挑战性的课题之一，同时也具有广泛的应用意义。它的重要性越来越引起人们的重视，所以在近几年研究学者们找到了许多人脸识别的方法。

支持向量机(Support Vector Machine，SVM)是由 AT＆T贝尔实验室的Vapnik及其研究小组于20世纪90年代中期提出的一种新的模式识别方法，具有很强的泛化能力，在解决小样本、局部极小点、非线性等问题上具有显著的优势，并且已经成功应用到了许多领域。经典的SVM训练是对若干个子问题的逐一优化，该方法可能会导致结果只有一个次优解，并且分类速度难以满足实验的要求。文献［1］提出一种基于遗传算法的SVM训练方法，文中通过遗传算法对SVM的参数进行优化。文献［2］提出了一种基于混沌搜索的遗传算法，此算法应用在短波通信控制器的诊断分类器中，得到了良好的分辨率。针对以上问题，作者受此启发，将此算法引进到人脸识别中，以改善传统遗传算法容易进入“早熟”等缺点，并提高计算速度和识别准确率。

1 支持向量机基本概念

假设一组训练样本{(x1+y1)，(x2+y2)，…，(xn+yn)}，其中 x∈R，类标签 y∈{－1，+1}，即只有两个样本。根据训练样本确定最大分类间隔的分割超平面，设最优超平面方程为w·x+b=0。其中w为分类超平面的权向量，b是分类阈值。对线性可分的情形，若得到这个超平面，需要求解下面的二次规划问题:

约束条件:yi［(xi·w)－b］≥1，i=1，2，…，n

此时，利用Lagrange优化方法把上述最优分类面问题转化为对偶问题:

其中，C是对现行不可分样本的分类错误代价系数，αi为拉格朗日乘数，k(xi，xj)为RBF核函数。

2 基本遗传算法与基于变尺度的混沌遗传算法

遗传算法是模仿生物遗传和进化机制的一种优化方法，能够实现全局的并行搜索，具有快捷、简单、鲁棒性好的特点，一般过程包含几个步骤:编码、生成初始群体、选择、交叉、变异等，通过迭代的方法产生新群体，进而得到最优解。但通过学者多年的实验研究表明，在实际的应用当中，遗传算法会出现局部寻优能力较差、出现“早熟”等现象。所以文献［2］提出了一种新的遗传算法——混沌遗传算法。

混沌(Chaos)是自然界中较为普遍的现象，它看似混乱无序，却有精致的内在结构，具有“遍历性”、“规律性”和“随机性”等特点，在一定范围内能按照自身的规律不重复地遍历所有的状态。计算机上，常用Logistic迭代方程来模拟混沌现象:xi+1=uxi(1－xi)(u为吸引子，0＜u≤4)，利用此方程进行迭代，能够得到混沌序列 X=［x1，x2，…，xn］(n为迭代次数)。

混沌遗传算法(CGA)，结合混沌现象的遍历性和遗传算法的反演性，利用混沌映射通过对原群体进行变换得到混沌群体，再进行遗传步骤，利用Logistic迭代方程进行迭代，得到混沌群体，实现对原群体的映射［3］。

2.1 变尺度操作

变尺度混沌算法利用混沌现象的特点，将混沌变量映射到待寻优变量区间，不断缩小优化变量的搜索范围并且提高搜索精度，所以具有较高的搜索效率［4］。

设当前待寻优变量C的搜索区间为［a1，b1］，在一次寻优过程后得到的最优值为C*，则利用下面的方程进行变尺度操作:

其中，μ为尺度参数，μ∈(0，0.5)，μ 越大，搜索区间缩减程度越小;i是变尺度的次数。

同时，设置μ的值为:

其中，r为当前已经进行变尺度操作的次数。

2.2 种群初始化

传统的遗传算法的初始种群是随机产生的，而初始种群的好坏直接影响进化过程的速度。本文提出了运用混沌搜索策略，对初始种群进行优化。首先，随机生成一个群体，再按照变尺度操作对最好的个体进行混沌遍历搜索，然后将经过混沌优化的最优个体加入到初始种群中。反复此过程，直到初始种群达到预先设定的规模。

2.3 染色体的编译码

染色体编码是由寻优问题得到的解空间转换为寻优方法所能处理的搜索空间。本文将人脸图像样本的SVM参数(错误代价系数C和核函数的参数γ)进行编码，采用二进制的编码。设第 t代染色体为 pt={β1t，β2t，…，βvt，θ1t，θ2t，…，θwt}，其中，βit(i=1，2，…，v)为错误代价系数位串，θit(i=1，2，…，w)为核参数位串。编码位串数的长度由参数的搜索精度决定。搜索精度为(b1－a1)/2v。本文设定v和w的长度均为16位。

染色体译码是编码的反过程，它将二进制位串转换为解空间的值。C和γ参数的解码方式相同，其转换方程的表达式为:

其中，C=［a1，b1］;dec(σ)为二进制位串 σ 的十进制数值;n是位串σ的长度。

2.4 定义适用度函数

适应度函数的设计对遗传算法尤为重要，因为种群泛化能力的适用度函数与提高遗传算法的寻优能力有直接的关系。定义如下SVM在训练样本集上的准确率:

则1－Caccuracy为错分样本率，从而可以定义适应度函数为:

2.5 交叉和变异

2.5.1 交叉操作

文献［5］提出的自适应交叉概率和相关性配对交叉，并采用“与/或”交叉法和单交叉法相结合的方式实现交叉操作。相对于传统的遗传算法，有利于优秀基因的保留和较差基因的淘汰。

(1)自适应交叉概率

不同的个体赋予不同的交叉概率，适应度高于群体平均适应度的个体，赋予比较低的交叉概率，最大程度的保留住优秀的基因;相反，适应度低于群体平均适应度的个体，赋予比较高的交叉概率。自适应交叉概率为:

其中，fmax为最大适应度值，favg为群体的平均适应度值。

(2)基于个体相关性的交叉配对

1)不相关指数

设两个染色体编码 A={a1，a2，…，an}和 B={b1，b2，…，bn}，其中 aibi∈{0，1}，i=1，2，3，…，n，若 A 和 B 相关性越小，则A和B交叉时出现无效操作的可能性就越小。所以首先要判断两个个体间的相关性，个体A、B之间不相关指数为:

2)配对概率

为了避免近亲繁殖所产生的无效后代，采取非等概率配对策略［6］，在种群中选取不相关性指数大的个体并赋予较大的被选概率。被选择的个体Bi和个体A交叉配对的概率定义为:

其中，σ为常数，0≤σ≤1;L为种群中不包含个体A的总个数。

(3)交叉方法

采用“与/或”的交叉法，即对父代按位“与”产生下一代X，按位“或”产生另一后代Y，确保了交叉操作的有效性。

2.5.2 变异操作

编码的每一位都以同样的变异概率进行位翻转。

3 基于变尺度的混沌遗传算法训练SVM

做好了上述的基础以后，就可以利用CGA对SVM模型的参数进行优化，具体算法如下:

(1)确定每个参数的范围并对其进行二进制编码并产生初始种群。

(2)利用以上介绍的方法优化初始种群，此时初始种群的每个个体表示优化问题的一个解。

(3)对每个个体进行编码。

(4)进行选择、交叉和变异的三种操作。

(5)对优化后的个体进行译码，根据适应度函数求出优化后的新种群。

(6)再次对此时适应度较高的个体进行变尺度混沌优化，来找到更为优化的值。

(7)跳到第(3)步，重复(3)－(7)，直到达到给定的要求。

4 仿真实验及结果分析

采用剑桥大学ORL人脸图像库作为实验数据，比较了本文算法训练SVM与基本遗传算法训练SVM的人脸识别性能。该图库有40人的正面灰度脸像组成，每个人有10幅不同的图像，每幅图像为256级灰度图，像素为92×112，每幅图的获取具有不同的时间、表情和环境。

随机选取10个人的前5幅图像共50幅作为训练样本，剩下的50幅作为测试样本。图1是其中两个人的10幅图像:

图1 ORL人脸库中的部分图像

本实验用机的PC配置:CPU为Core i5 2.2GHz，内存为1G，软件环境为MATLAB 2010b.本文算法的参数设置如下:初始种群规模为30，最大进化代数为20，C∈［1，1000000］，γ∈［0.01，1］，自适应交叉概率中，较高的交叉概率为 0.7，较低的交叉概率为0.3，变异概率为0.02。

表1 SVM参数选取结果和人脸识别正确率

表1实验结果表明，随着迭代次数的增加，误代价系数C和识别率也逐步提升到了一个稳定的值，同时识别正确率也比传统的训练算法的识别率高。

5 结束语

通过对遗传算法的改进，提出了基于变尺度的混沌遗传算法，对人脸识别中SVM参数的优化有了明显的改善。此算法中由于利用混沌映射，有效地避免了传统算法容易陷入局部最优解和“早熟”的现象;另外基于变尺度的混沌搜索，筛选出了优化种群，并在寻优过程中使搜索范围动态缩小，提高了搜索范围和精度。通过实际应用，该方法在人脸识别中可以获得较好的预测结果。

［1］汪世义，陶亮，王华彬.支持向量机和遗传算法的人脸识别方法［J］.计算机工程与应用，2010，46(28):175－177.

［2］杜占龙，谭业双，甘彤.基于混合核函数支持向量机和遗传算法的人脸识别［J］.计算机工程，2010，38(5):163－166.

［3］何仁芳，王乘，杨文兵.基于混沌遗传算法的图像匹配［J］.红外与激光工程，2003，32(1):13－16.

［4］张明火，杨建民.变尺度混沌优化方法的改进［J］.华东船舶工业学院学报，2004，18(4):21－26.

［5］卢厚清，陈亮，宋以胜，等.一种遗传算法交叉算子的改进算法［J］.解放军理工大学学报，2007，8(3):250－253.

［6］蔡良伟，李霞.遗传算法交叉操作的改进［J］.系统工程与电子技术，2006，28(6):925－928.