基于进化规划算法的图像聚类研究

王兆珍，刘旭鹏，杨淑莹

（1.天津现代职业技术学院电子工程系，天津 300350；2.天津理工大学智能计算及软件新技术重点实验室，天津 300384）

图像聚类是指将图像中若干样品分成不同类，并将相同形状的物体归为一类的算法[1]，它在模式识别领域中占有重要地位，主要用于数据压缩、数据挖掘和图像检索等.图像聚类涉及特征提取和识别算法，它们直接影响聚类速度和识别精度.在图像聚类识别方法当中，常用的有遗传算法、k-means算法和粒子群算法等.其中遗传算法[2-3]在局部搜索过程中表现能力差，搜索速度相对较慢，容易出现早熟现象；k-means算法[4]对初始值的聚类中心较为敏感，容易陷入局部最优；粒子群优化算法[5]是一种基于群体的智能算法，但是后期具有收敛慢、搜索精度低和容易陷入局部极小等缺点.在图像聚类过程中，上述算法都不可避免地出现重复搜索的现象，如果样品的数目过多，则上述算法进行搜索的时间消耗将更为突出[6].

进化规划（evolutionary programming，EP）是为了求解预测问题而提出的一种有限机进化模型，是一种通过模拟自然进化过程得到的一种随机搜索方法，属于进化计算的分支.该算法在变异运算中引入正态分布技术，从而使进化规划成为一种优化搜索算法，可作为进化计算的一个分支在实际领域中得到广泛应用.进化规划可应用于求解组合优化问题和复杂的非线性优化问题，它只要求所求问题是可计算的，且使用范围较广，目前已应用于人工智能和机器人智能控制等诸多领域[9-10].与遗传算法相比，在模拟生物进化的过程中，进化规划主要着眼于物种的进化过程，不使用个体交叉算子和重组算子来操作[11].进化规划中的选择算子着重于群体中各个体之间的竞争选择，但是当竞争个体数目较大时，也就类似于进化策略中的选择过程.进化规划直接把问题的可行解作为个体的编码，无需再对个体进行编码处理，也无需考虑随机扰动因素对个体的影响，更便于应用.本研究将进化规划优化算法应用于图像聚类问题，并通过仿真实验检验算法的性能．

1 进化规划基本原理

进化规划的基本原理为：

（1）种群初始化(随机分布个体).

（2）变异(更新个体).进化规划中不使用平均变异方法，而使用高斯变异算子，以实现种群内个体的变异，保持种群中丰富的多样性.高斯变异算子可以根据个体适应度获得高斯变异的标准差，对于适应度低的个体，其变异范围大，高斯变异算子可扩大搜索的范围；对于适应度高的个体，其变异范围小.高斯变异算子可以在当前位置局部小范围的搜索，以实现变异操作.

（3）适应度计算(评价个体).

（4）选择(群体更新).在选择操作上，进化规划算法采用父代与子代一同竞争的方式，利用锦标赛选择算子，最终选择适应度较高的个体.

虽然进化规划算法同样是对生物进化过程进行模拟，且具有进化计算的一般流程，但进化规划算法具有其自身特点.与其他进化计算相比[12]，进化规划算法不使用遗传算法的交叉，也不使用进化策略算法的基因重组算子，而使用变异算子操作来体现个体之间相互作用[13].

2 聚类算法的实现

基于进化规划算法的聚类算法实现步骤如下：

（1）设置相关参数：初始化初始种群中的个体数Sizepop、最大迭代次数Itermax、聚类中心数目Numcenter以及进行锦标赛竞争时用于比较的个体数q.

（2）获得所有待聚类样品个数和特征.

（3）群体初始化，即随机分配每个个体基因位的值.

（4）计算每个个体的适应度值fitness.

（5）通过高斯变异算子，生成Sizepop个新个体：对所有个体循环每个基因位，对该位基因运用变异算子操作，按照高斯变异产生1个1～-Numcenter之间的数赋值给该位，生成子代群体.

（6）计算新生成的Sizepop个子代个体适应度值.

（7）令父代与子代个体（共2×Sizepop个）组成新群体totalpop，对新群体进行选择算子操作：随机从totalpop中选择q个个体，循环每个体，让每个个体与这q个个体逐个进行适应度值的比较，以q个个体中适应度值高于当前个体适应度值的个体个数作为当前个体的得分，最终选择评分最高的Sizepop个个体，作为下一代父代.

（8）记录种群中的最优解：若新生成的子代群体中，最优个体适应度值低于全体种群的最优个体的适应度值（相互之间距离越近，适应度值越小），则用当前最好的个体替换总的最好的个体.

（9）判断是否满足停止条件，即判断是否达到总的迭代次数.如果是，则输出最优解，即输出各个样品的类别号，并退出；反之，则跳转到步骤（4）继续迭代.

3 基于差分进化算法的图像聚类设计

3.1 特征提取

为更好地实现待测图像有效聚类，首先须对每个待测图像提取特征参数[14].本研究特征参数的提取方法为：在每个数字的外边缘划定1个矩形框，将矩形框的长和宽进行N×M分割，分割后的每个数字称为N×M模板[7]；然后计算每个小方格的黑像素个数在本方格内的比例，以此作为样品特征值.以图1为例.

将样品分割成7×5个小方格，在每1小方格中统计黑像素所占方格总面积的比例，即得特征值，根据实际问题的需要可适当修改N和M的值，其值越大，样品特征越多，聚类精度越高，算法收敛时间则会相应延长；其值越小，算法收敛速度加快，但聚类精度会有所下降.

3.2 解的编码

在进化规划中，采用符号编码，位串长度为L，搜索空间为1个L维空间，与其相对应，搜索点为1个L维向量.算法中，组成进化群体的每个染色体X可直接用这个L维向量表示.

图2为待聚类样品图.

图2中每个个体均包含1种分类方案.L取12位，基因代表样品所属的类号（1～4），基因位的序号代表样品的编号，基因位的序号是固定的，即某个样品在染色体中的位置是固定的，而每个样品所属的类别在随时变化.若基因位为n，则其对应第n个样品，而第n个基因位所指向的基因值代表第n个样品的归属类号.

每个解包含1种分类方案，某个个体的初始染色体编码为（1，3，4，1，2，4，2，3，1，3，2，1），其含义为：第1、4、9和12个样品被分到第1类；第5、7和11个样品被分到第2类；第2、8和10个样品被分到第3类；第3、6个样品属于第4类，此时还处于假设分类情况，不是最优解，如表1所示.

表1 初始染色体编码Tab.1 Code of initial chromosome

3.3 设置适应度函数

适应度函数代表每个个体优劣的程度，对初始群体中的每个染色体计算其适应度值fitnessm_pop（i），其实现步骤如下：

（1）通过人工干预获得聚类类别总数Numcenter.

（2）找出染色体中相同类别号的样品，X(i)表示第i个类的样品.

（3）统计每个类的样品个数n，ni为第i个类别的个数，样品总数为

（5）同一类内计算每个样品到相应的聚类中心的距离，并将其累加求和

（6）将不同类的Di求和，赋值给

将fitnessm_pop(i)作为最适应度函数，其值越小，说明这种分类方法的误差越小，即其适应度值越小.

3.4 变异算子

变异操作是进化规划算法中最重要的操作，也是唯一的搜索方法，这是进化规划的独特之处.在标准的进化规划中，变异操作应使用高斯变异（Gauss mutation）算子[8].变异过程中，计算每个个体适应度函数值线性变换的平方根，从而获得该个体变异的标准差si，将每个分量加上1个服从正态分布的随机数.

设X为染色体个体解的目标变量，s为高斯变异的标准差.每部分都有L个分量，即染色体的L个基因位.染色体由目标变量X和标准差s两部分组成，即（X，s）=［（x1，x2，…，xL），s］.

个体变异的形式为 X（t+1）=X（t）+N（0，s）.X和标准差s之间的关系是

式（1）和式（2）中：F（X（t））是当前个体的适应度值，越靠近目标解个体的适应度值越小；N（0，s）是概率密度为的高斯随机变量；b和g是待定参数，一般将b和g的值设为1和0；目标变量X的每个分量通过式（1）可以达到不同的变异效果.

3.5 选择算子

在进化规划中，选择机制的作用是根据适应度函数值从父代和子代集合的2×Sizepop个个体中选择Sizepop个较好的个体组成下一代种群，其形式化表示为：s：I2×Sizepop→ISizepop.选择操作按照一种随机竞争的方式进行，进化规划中选择算子主要通过概率选择、锦标赛选择和精英选择3种方式选取，其中锦标赛选择方法是进化规划中较为常用的方法.锦标赛选择操作的具体过程为：

（1）将由Sizepop个父代个体组成的种群P（t）和由种群P（t）经过1次变异运算后产生的由Sizepop个子代个体组成的种群P′（t）合并在一起，组成1个共含有2×Sizepop个个体的集合P（t）∪P′（t），记为I；

（2）每个个体xi∈I，从I中随机选择q个个体，并将q个个体的适应度函数值Fj（j∈(1，2，…，q))与xi的适应度函数值进行比较，计算出q个个体中适应度函数值比xi适应度差的个体的数目wi，并把wi作为 xi的得分，其中 wi∈（0，1，…，q）.

（3）在所有2×Sizepop个个体都经过比较后，按每个个体的得分wi进行排序，选择Sizepop个具有最高得分的个体作为下一代种群.

算法中，q≥1为选择算法的参数，为使锦标赛选择算子发挥更好的作用，需要设定适当的用于比较的个体数q.q的取值较大时，偏向确定性选择，当q=2×Sizepop时，则从2×Sizepop个个体中将适应度值较高的Sizepop个个体选出，容易带来早熟等弊端；相反，q的取值较小时，偏向于随机性选择，适应度的控制能力下降，导致大量低适应度的个体被选出，造成种群退化.因此，为了既能够保持种群的先进性，又避免确定性选择带来的早熟弊端，需要依据具体问题，合适地选取q值.

进化过程中，每代种群中相对较好的个体被赋予了较大的得分，能够被保留到下一代的群体中.

4 实验结果

在MATLAB 2008环境下，编程实现了基于进化规划的手写数字的聚类问题，并在Inter(R)Core(TM)i5 CPU处理器的计算机上对图2所示的待聚类图像进行相应的聚类实验，实验结果如图3所示.由图3可以看出，进化规划算法可以很好地实现不同手写数字的聚类，取得了较好的实现效果.

进化规划算法找到的最优解编码如表2所示.通过样品值与基因值比较对照可以发现，相同的手写数字被归为一类，分到相同的类号，而且全部正确.实验结果表明：进化规划算法可以有效实现不同图像的聚类.

表2 进化规划算法获得的最优解编码Tab.2 Optimal solution achieved by evolutionary programm ing

5 结论

本研究分析了进化规划算法的原理和仿生机制，并将其应用于图像聚类问题的求解，仿真实验结果表明，基于进化规划算法的图像聚类方法具有良好的可行性与准确性.

[1]杨淑莹．图像模式识别—VC++技术实现[M]．北京∶清华大学出版社，北京交通大学出版社，2005．

[2]张讲社，徐宗本，梁怡．整体退火遗传算法及其收敛充要条件[J]．中国科学：E 辑，1997，27（2）：154—164．

[3]张忠华，杨淑莹．基于遗传算法的图像聚类设计[J]．测控技术，2010，29（2）：4—46．

[4]郭庆锐，许建龙，孙树森，等．基于颜色重心和k-means的彩色图像聚类分割算法[J]．浙江理工大学学报，2010，27（4）：580—584．

[5]宋洁，董永峰，侯向丹，等．改进的粒子群优化算法[J]．河北工业大学学报，2008，37（4）：55—59．

[6]谢金星．进化计算简要综述[J]．控制与决策，1997，12（1）：1—7．

[7]LEECY，YAOX.Evolutionary programmingusingmutationsbased on the levy probability distribution[J].Transactions on Evolutionary Computation.2004，8（2）：1—13.

[8]IWAMATSU M.Generalized evolutionary programming with Levytypemutation[J].Computer Physics Communications，2002，147（8）：729—732.

[9]商允伟，裘隶皇．一种求解数值优化问题的快速进化规划算法[J]．系统仿真学报，2004，16（6）：1190—1192.

[10]王丽萍，董江辉．带有一种新的算子的进化规划算法的收敛性分析[J]．科学技术与工程，2009，9（6）：1428—1431．

[11]高永超，李歧强．退火进化规划算法及其收敛性[J]．系统仿真学报，2006，18（3）：577—580．

[12]王向军，嵇斗，张民．一种多群竞争进化规划算法[J]．电子学报，2004，32（11）：1824—1828．

[13]高玮．遗传算法与进化规划的比较研究[J]．通讯和计算机，2005，2（8）：10—15．

[14]杨淑莹．模式识别与智能计算-Matlab技术实现[M]．北京∶电子工业出版社，2011∶34—36．