基于差分进化算法的图像聚类研究

贾紫娟，杨淑莹，王光彪

基于差分进化算法的图像聚类研究

贾紫娟，杨淑莹，王光彪

（天津理工大学智能计算及软件新技术重点实验室，天津300384）

将差分进化算法应用于图像聚类问题，对问题进行实数编码，采用群体智能模式实现问题解的搜索．利用差分进化算法的差分变异操作和群体分布特性有效提高算法的搜索能力，采用贪婪选择操作和竞争生存策略实现群体内个体之间的相互合作与竞争，降低了进化操作的复杂性，并通过仿真实验证明了该算法的有效性．

差分进化算法；群体智能；图像聚类；优化问题

差分进化算法是Storn和Price于1995年提出的一种随机并行搜索算法［1］，它与遗传算法和粒子群算法等算法一样是基于群体智能理论的优化算法，利用由群体内个体之间的相互合作与竞争产生的群体智能模式来指导优化搜索的进行．与其他进化算法不同，差分进化算法保留了基于种群的全局搜索策略，采用实数编码、基于差分的简单变异操作和一对一的竞争生存策略，降低了进化操作的复杂性［2－3］．差分进化算法特有的进化操作使其具有较强的全局收敛能力和鲁棒性，非常适于求解一些复杂环境中的优化问题．

1 差分进化算法的基本原理

差分进化算法（Differential Evolution，DE）采用实数编码方式，其算法原理和进化流程与遗传算法十分相似，如父代生成子代的操作均包括变异、交叉和选择［4－5］．

与遗传算法相比，差分进化算法具有如下特点：首先，差分进化算法的变异操作采用差分变异操作，即将种群中任意2个个体的差分向量加权后，根据一定的规则加到第3个个体上，再通过交叉系数控制下的交叉操作产生新个体，差分进化算法的这种变异方式有效利用了群体分布特性，提高了算法的搜索能力，避免了遗传算法中变异方式的不足；同时，差分进化算法的选择操作采用贪婪选择操作，即如果新生成个体的适应度值比父代个体的适应度值大，则用新生成个体替代原种群中对应的父代个体，否则原个体保存到下一代．差分进化算法通过变异、交叉和选择3个操作进行迭代寻优．

2 聚类算法的实现

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

（1）设置相关参数．

设置种群大小N、最大迭代次数Maxlter、交叉概率系数Pc和放大系数F．

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

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

（4）计算群体中每个个体的适应度（适应度值越大代表分类情况越准确）．

（5）采用差分变异算子，生成下一代群体．

目前，较为常见的差分算子有4种，分别为随机向量差分法（DE／rand／1）、最优解加随机向量差分法（DE／best／1）、最优解加多个随机向量差分法（DE／best／2）和最优解与随机向量差分法（DE／rand－to－best／1）。本研究采用最优解与随机向量差分法．

（6）进行进化算子的交叉操作．

随机选择一个基因位，并将该基因位设定为自变异后新生成的子代个体对应的基因位上的基因；对于其他基因位，产生0～1之间的随机数rand（i），i∈［1，patternNum］，通过与交叉概率系数Pc进行比较控制父代子代基因的选择，即当rand（i）＜Pc时，选择父代对应的基因值，否则选择子代（即通过差分变异后新产生的个体）对应的基因值．

（7）计算新生成的子代群体的适应度．

（8）执行贪婪选择．

比较对应的父代和子代的适应度值，选择适应度高的个体成为下一代的父代个体．

（9）保留精英个体，若在新生成的子代群体中，最优个体适应度值低于总的最优个体的适应度值，则用当前最好的个体替换总的最好的个体．

（10）若已经达到最大迭代次数，则退出循环，输出结果，返回各个样品的类别号；否则回到第（5）步，重新执行操作直至达到最大迭代次数．

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

3．1 解的编码设置

以含有10个数字的待聚类样品为例，如图1所示．采用实数编码，在每个样品的右上角编号，不同样品采用不同编号，但样品编号始终固定，即某个样品在每个解中的位置是固定的．位串长度L取10位，分类号代表样品所属的类号（1～4），每个样品的所属类别随时变化［6］．如果编号为n，则其对应第n个样品，而第n个位所指向的值代表第n个样品的归属类号．

图1 待聚类的样品数字Fig．1 Number samples for clustering

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

表1 初始解Tab．1 Initial solution

3．2 差分变异算子

本研究所采用的最优解与随机向量差分法（DE／rand－to－best／1）将当前种群的最优个体置于差分向量中，种群中除当前个体外，取最优解与随机选取的个体进行向量相差，并乘以贪婪因子，同时任意选取互不相同的2个个体，将二者的向量差分结果乘以放大因子，加到当前种群个体上．此种方法既利用了当前种群最优个体的信息，加快了搜索速度，又降低了优化陷入局部最优解的危险，即

式（1）中：λ为控制算法的“贪婪”程度，为了减少控制参数的数量，一般取λ＝F，则式（1）可改写为

3．3 交叉算子

交叉算子操作依据交叉概率（Pc），使当前父代个体m＿popt（i）和经过差分变异生成的子代个体newpopt（i，j）的部分基因位进行交换，从而生成新的子代个体．

为了保持种群的多样性，父代个体m＿popt（i，j）经过差分变异操作后，对新产生的个体newpopt（i，j）进行交叉操作

式（3）中：randi，j表示在第i个个体的第j位基因上产生的符合均匀分布的随机数，目的是为了与交叉概率Pc进行比较，Pc∈（0，1）．如果randi，j≥Pc，则保留newpopt（i，j）的基因值，否则，用m＿popt（i，j）代替newpopt（i，j）相应的基因值．这里引入一个随机基因位Jrand，并强制使该位的基因取自变异后的新个体，这样新个体newpopt（i，j）至少有一位基因由变异后产生的新个体提供，因此m＿popt（i，j）和newpopt（i，j）不会完全相同，从而更有效地提高种群的多样性，保证个体的进化．

3．4 贪婪选择算子

如前所述，比较经过变异和交叉操作后得到的子代个体newpopt和当前父代个体m＿popt的适应度，如果newpopt的适应度大于m＿popt的适应度，则选择newpopt成为下一代的父代个体m＿popt＋1，否则m＿popt将直接进入下一代．

4 实验结果

在Inter（R）Core（TM）2Duo T7200处理器的计算机上和Matlab环境下，应用差分进化算法对图像进行聚类操作，结果如图2所示．从图2中可以看出，差分进化算法实现了不同图像的聚类，取得了较好的实验效果．

图2 聚类结果Fig．2 Result of clustering

差分进化算法找到的最优解编码如表2所示．通过样品值与基因值比较对照可以发现，相同的数据被归为一类，分到相同的类号，而且全部正确．实验结果表明：利用差分进化算法有效地实现了不同图像的聚类，并且取得了较好的实验效果．

表2 差分进化算法最终找到的最优解Tab．2 Optimal Solution

5 结论

本研究在分析差分进化算法原理的基础上，详细分析了差分进化算法的3种操作算子，最后将差分进化算法应用到图像聚类研究．差分进化算法是基于群体智能理论的优化算法，它保留了基于种群的全局搜索策略，利用群体内个体之间的相互合作与竞争产生的群体智能模式来指导优化搜索，降低了进化操作的复杂性．

［1］ 王培崇，钱旭，王旭，等．差分进化计算研究综述［J］．计算机工程与应用，2009，45（28）：13－16．

［2］ 黄天辰，韩国栋．进化计算及应用［J］．四川兵工学报，2009（3）：119－121．

［3］ 谢金星．进化计算简要综述［J］．控制与决策，1997，12（1）：1－7．

［4］ 焦李成，保铮．进化计算与遗传算法—计算智能的新方向［J］．系统工程与电子技术，1995（6）：20－26．

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

［6］ 杨淑莹．图像模式识别—VC＋＋技术实现［M］．北京：清华大学出版社，北京交通大学出版社，2005：218－354．

（责任编校 亢原彬）

Research on image cluster based on differential evolutionary algorithm

JIA Zi－juan，YANG Shu－ying，WANG Guang－biao
（Key Laboratory of Intelligence Computing and Novel Software Technology，Tianjin University of Technology，Tianjin 300384，China）

Differential evolutionary algorithm is applied to image clustering problem．The problem is firstly encoded using real number，and swarm intelligent model is used for achieving the search for the solution．Through taking the best of features of the group distribution，the search capability of the algorithm is improved by using the operation of differential variation of the differential evolutionary algorithm．Mutual cooperation and competition among individuals within the group is achieved by adopting greed selection and survival strategies，and the complexity of the evolutionary operation is reduced．The simulation experiments show that the proposed algorithm for image cluster is correct and effective．

differential evolutionary algorithm；swarm intelligence；image cluster；optimization problem

book=2012,ebook=35

TP311

A

1671－1114（2012）02－0053－03

2012－01－10

国家自然基金资助项目（61001174）；天津市高校发展基金资助项目（20071308）

贾紫娟（1988－），女，硕士研究生．

杨淑莹（1964－），女，教授，主要从事计算机仿真、模式识别与智能系统和动态目标跟踪方面的研究．