用于图像分割的双变异遗传算法*

周 阳， 李晓春

(中南大学 物理与电子学院，湖南 长沙 410000)

用于图像分割的双变异遗传算法*

周 阳， 李晓春

(中南大学 物理与电子学院，湖南 长沙 410000)

针对遗传算法(GA)收敛结果不稳定、易陷入局部最优解等问题，提出了一种基于全局的改进双变异遗传算法(DMGA)，并应用于图像的灰度阈值分割；分析了仿真初始参数对于图像分割结果的影响。实验结果表明：图像分割精度高，效果好，结果可靠,相对于传统GA，DMGA具有更好的全局和局部搜索能力，收敛结果稳定。

双变异遗传算法； 图像分割； 灰度阈值

0 引 言

遗传算法(genetic algorithm,GA)模拟自然进化过程，从问题解的串集开始搜索最优解，相比于其它(如粒子群优化算法[1])单个初始值迭代求最优解的算法，它覆盖面大[2]，具有更佳的全局搜索能力。而且，GA具有自组织、自适应和自学习的优点，仅需适应度函数值来评估个体，因而广泛应用于图像分割[3]、复杂函数系统优化[4]、系统识别[5]、神经网络设计[6]等众多领域[7,8]。Zhou Wei等人[9]将GA运用于虚拟企业的合作伙伴的选择和优化；Teoh Yeong Yeap等人[10]将GA运用于低通滤波器的设计；Guo Pengfei等人[11]将GA用于离散变量的优化。

本文采用一种特别的双变异方法，使得种群个体的多样性以及父代优良基因的遗传得到了较好的处理，有利于全局搜索最优解，并且可以适当地降低杂交概率pc和变异概率pm值，提高种群的收敛性，较好地解决了收敛速度和全局搜索之间的平衡问题。

1 双变异遗传算法

双变异遗传算法(double-mutation genetic algorithm,DMGA)与传统GA的最大区别在于变异操作的处理。传统GA只采取一次变异，变异率一般由种群大小、染色体长度等因素所决定，取值通常很小；变异操作一般是从群体中某个个体染色体中随机挑选一个或多个基因座，并对选取的基因座进行变异。双变异在原有变异操作基础上，人为加上一次变异选择操作，变异概率可以人为给定，不受种群大小、染色体长度等因素的影响，如果得到更好后代，则取代原先最优个体，如果没有得到更好后代，则保留原先最优个体。双变异操作可以极大地丰富群体中个体的多样性，保留父代的优良基因，缩短寻找最优解的迭代次数。

1.1 双变异操作

图1为传统的变异操作示意图。

图1 传统单变异示意图

染色体长度V=8，每一条染色体均有8个基因座，图1中的一个正方形和一个圆形分别表示具体的某一个基因座。图中本代初始种群中圆形组合P1和正方形组合P2分别代表两个不同的父代种群，通过一次变异后得到子代种群P3和P4。其中 P3为优良种群，得以继承，P4成为淘汰种群，它们之间进行选择，就得到本代最优个体P5。

图2为文献[14]所述的一般双变异操作示意图。

5.仰口线虫病。剖检可见病牛尸体极度消瘦、水肿，皮下浆液性浸润，血凝不全，肠黏膜发炎，出血，内容物呈褐色或血红色。

图2 一般双变异示意图[16]

在第一次变异得到的子代种群P3(优良品种)、P4(淘汰种群)的基础上，将淘汰种群P4再次变异后进行优选，得到种群P5。P6为传统遗传算法(选择1)的最优个体。P5,P6经过再次选择(选择2)，得到文献[14]的最优个体P7。

相对于传统遗传算法(图1)，文献[14]的一般双变异操作中，本代最佳个体的选择范围多了淘汰种群P4的再次变异优选结果P5。本文的双变异操作算法如图3。

图3 本文双变异操作示意图

图3中，在一次变异后得到的子代种群P3、P4基础上，对优良品种P3、淘汰种群P4分别再次变异，得到种群P5、P6。P7仍为传统遗传算法(选择1)的最优个体。P5、P6、P7经过再次选择(选择2)，得到本文算法的最优个体P8。

图3的双变异操作可看成是一次“配种”过程。一次“配种”是否成功，取决于再次变异后得到的个体P5、P6是否优于本代中的最佳个体P7。如果优于，则“配种”成功；反之，“配种”失败。“配种”成功将为种群创造出更优良的父代基因，迫使种群向更加优良的方向发展，经过多代繁殖之后，种群进化到全局最优种群的机率与速度将大大提高。

因此，图3在图2的基础上，增加了优良品种P3的再次变异，并将其优选结果P5列入后续选择过程。本文相对文献[14]的一般DMGA，不仅扩大了种群选择范围，而且增加了优良品种在这个范围中的比重，从而扩大了全局搜索能力，加快了收敛到最优解的速度。

1.2 DMGA用于图像分割

将改进的遗传算法用于图像分割需要解决两个问题：一是选择怎样的分割方式；二是如何构造适应度函数来衡量每条染色体(基因串)对环境的适应能力。本文选择的分割方式是运用最为广泛的图像灰度阈值分割；适应度函数为最大类间方差法公式。

本文构造的DMGA用于图像分割的流程图如图4所示。

图4 DMGA用于图像分割流程图

2 仿真实验

为了验证本文算法对图像分割的有效性和准确性，选取三副图像分别在Matlab 7.0下进行分割对比实验，表1为两种算法的初始参数如下：初始种群数Q=6,染色体长度L=8,遗传代数G=150,杂交概率pc= 0.05,变异概率pm=0.01。

2.1 分割精度对比

图5(a1)，图6(a1)，图7(a1)都为选取的原始图像；图5(a2)，(b2)，(c2)为对应的传统算法的图像分割效果图；图5(a3)，(b3)，(c3)为本文改进算法的图像分割效果图。

图5 两种分割方法效果的对比

从图5(a2)，(c2)中可以看出，分割后的图像将背景物体过多地分割到了目标物体。图5(a2)中图像则过多地把目标物体当成背景物体给分割掉了。本文改进算法的结果图5(a3)，(b3)，(c3)，则对分割实现了较好的均衡，背景物体基本分割完全，目标物体图像清晰，轮廓分明，没有出现将背景物体错分为目标物体或将目标物体错当成背景物体的现象。

2.2 可靠性对比

表1、表2、表3为相同参数(表1)条件下，分别对图5(a1)，(b1)，(c1)采用传统GA和改进DMGA依次进行8次仿真得到的阈值结果图。

由表1、表2、表3可以看出:在Q=6，L=8，G=150，p=0.05，pm= 0.01情况下。传统GA得到的阈值跳动较大，表1为38～110，表2为55～188，表3为63～146，很不稳定。而本文改进的GA得到的阈值上下跳动不超过1，变动较少，基本趋于平衡；再结合图5的效果可知，采用DMGA仿真得到的阈值分割精度也非常准确。可见，采用本文改进的DMGA几乎全部可以分割到最佳阈值，是一种比较可靠的分割方法。

表1 对图5(a1)采用两种算法得到的阈值对比

算法12345678GA 94107 38755381110 60DMGA8383848583858485

表2 对图5(b1)采用两种算法得到的阈值对比

算法12345678GA 10762133955513018891DMGA111112 112112 112 112112113

表3 对图5(c1)采用两种算法得到的阈值对比

算法12345678GA 146 8791106 160 8463140 DMGA9393949393939294

2.3 搜索能力对比

图6为表2中第二次仿真得到的单变异与双变异最佳阈值进化曲线图。

图6 最佳阈值进化曲线的对比

由图6(a)可以看出，阈值的进化比较单一，搜索迟钝，易于早熟收敛，陷入局部最优，搜索到的最优解可靠性能差。对比图6(b)曲线波动明显加快，搜索反应迅速，无论前期后期曲线都有波动，很好地限制了传统GA易于早熟收敛、后期搜索迟钝等缺点。因此，搜索能力更强。

2.4 参数设置问题

为了验证参数对算法的影响， 本文从初始种群、遗传代数、杂交概率、变异概率四个方面分别对算法进行研究。以初始种群数Q=2，遗传代数G=10,杂交概率pc=0.01，变异概率pm=0.01为初始参数。

表4为初始种群数Q=2,6,10,12，G=10，pc=0.01，pm=0.01时；分别对图5(a1)进行10次GA与10次DMGA求阈值后得到的平均值与方差。

表4 初始种群数不同得到的阈值对比

Q2平均值方差 6平均值方差 10平均值方差 12平均值方差GA 124182081575872488535DMGA 87 2285 483 283 2

表5为初始种群数Q=2，G=20,50,100,150，pc=0.01，pm=0.01时；分别对图5(a1)进行10次GA与10次DMGA求阈值后得到的平均值与方差。

表5 遗传代数不同得到的阈值对比

G20平均值方差 50平均值方差 100平均值方差 150平均值方差GA 8337881253721873782913293DMGA83 4 85 985 484 3

表6为初始种群数Q=2，G=10，pc=0.02,0.06,0.1,0.14，pm=0.01时；分别对图5(a1)进行10次GA与10次DMGA求阈值后得到的平均值与方差。

表6 杂交概率不同得到的阈值对比

pc0．02平均值方差 0．06平均值方差 0．1平均值方差 0．14平均值方差GA 100387711128611053106994194DMGA 83 71 86 8 84 386 8

表7为初始种群数Q=2，G=10，pc=0.01，pm=0.02,0.06,0.1,0.14时；分别对图5(a1)进行10次GA与10次DMGA求阈值后得到的平均值与方差。

表7 变异概率不同得到的阈值对比

pm0．02平均值方差 0．06平均值方差 0．1平均值方差 0．14平均值方差GA1443742838228916488120DMGA 87 1884 984 484 2

由表4、表7可以看出：随着初始种群或变异概率的增多，GA与本文算法得到的阈值的平均值越来越靠近最佳阈值，方差越来越小，可见阈值的波动的幅度越来越小，可靠性增加。由表5、表6可以看出：两种算法的平均值与方差变化不大。

对于灰度图像识别来说，灰度值的选择范围在0～255之间，本算法中染色体位数取8位是足以满足灰度取值范围要求的。从图像分割的模拟结果看，无论初始种群数、遗传代数、杂交、变异概率如何变化，本文算法得到的阈值的平均值均与最佳阈值非常接近，并且方差较小，稳定性高，是一种比较可靠的图像灰度阈值分割方法。

3 结 论

模拟结果表明:与传统的GA相比，本文的改进DMGA，具有更好的全局和局部搜索能力，收敛结果稳定；在图像分割的具体应用上，图像分割[16,17]精度高，分割效果好，结果可靠，是一种实用的高效的图像灰度阈值分割方法。

[1] Rokbani N,Momasso A L,Alimi A M.AS-PSO,ant supervised by PSO meta-heuristic with application to TSP[C]∥Proceedings Engineering & Technology,2013:148-152.

[2] Aghaabbasloo M,Azarkaman M,Salehi M E.Biped robot joint trajectory generation using PSO evolutionary algorithm[C]∥The 5th RoboCup Iran Open International Symposium(RIOS) on Al & Robotics ,2013:1-6.

[3] Choong M Y,Liau C F,Mountstephens J,et al.Multistage image clustering and segmentation with normalised cuts[C]∥The 3rd International Conference on Intelligent Systems,Modelling and Simulation(ISMS),2012:362-367.

[4] Vellasco M B R,Cruz A V A,Pinho A G.Quantum-inspired evolutionary algorithms applied to neural modeling[C]∥IEEE World Conference on Computational Inteligence,Plenary and Invited Lectures,2010:125-150.

[5] Noshadi A,Shi J,Lee W S,et al.Genetic algorithm-based system identification of active magnetic bearing system:A frequency-domain approach[C]∥2014 IEEE International Conference on Control & Automation(ICCA),2014:1281-1286.

[6] Chagas S H,Martins J B,de Oliveira L L.An approach to localization scheme of wireless sensor networks based on artificial neural networks and genetic algorithms[C]∥2012 IEEE 10 th International Conference on New Circuits and Systems(NEWCAS),2012:1619-1622.

[7] Platel M D,Schliebs S,Kasabov N.A versatile quantum-inspired evolutionary algorithm[C]∥Congress on Evolutionary Computation,2007:423-430.

[8] Cam Z G,Cimen S,Yildirim T.Learing parameter optimization of multi-layer perceptron using artificial bee colony,genetic algorithm and particle swarm optimization[C]∥2015 IEEE the 13th International Symposium on Applied Machine Intelligence and Infomatics(SAMI),2015:329-332.

[9] Zhou Wei,Bu Yanping,Zhou Yeqing.Research on partner selection problem of virtual enterprise based on improved genetic algorithm[C]∥The 26th Chinese Control and Decision Conference,2014 CCDC,2014:1047-1052.

[10] Teoh Yeong Yeap,Neoh Siew Chin,Arau,Malaysia.A GA-based optimization for fourth-order sallen-Key low-pass filter[C]∥2012 the 4th Asia Symposium on Quality Electronic Design(ASQED),2012:164-167.

[11] Guo Pengfei,Wang Xuezhi,Han Yingshi.A hybrid genetic algorithm for structural optimization with discrete variables[C]∥2011 International Conference on Internet Computing & Information Services(ICICIS),2011:223-226.

[12] 刘荷花,崔 超,陈 晶,等.一种改进的遗传算法求解旅行商问题[J].北京理工大学学报,2013,33(4):390-393.

[13] 刘晓明，温福岳，曹云东，等.基于改进遗传算法的SF6断路器匀场设计[J].中国电机工程学报，2008,33(2):99-103.

[14] 方咸云,方千山,王永初.双变异率自适应遗传算法研究及其应用[J].南昌航空工业学院学报,2002,16(2):17-20.

[15] 曾 成,赵锡钧,徐 欣，等.PCB检测中图像分割技术研究[J].传感器与微系统,2011,30(2):26-28.

[16] 刘小霞,徐贵力,嵇盛育，等.一种改进的舰船红外图像分割算法[J].传感器与微系统,2008,27(6):37-39.

[17] 陈天炎,曾思通,吴海彬,等.基于YCbCr颜色空间的火焰图像分割方法[J].传感器与微系统,2011,30(10):62-64.

DMGA for image segmentation*

ZHOU Yang, LI Xiao-chun

(School of Physics and Electronic Engineering,Central South University,Changsha 410000,China)

Aiming at problem of unstable convergence result and easy to fall into locally optimal solution,present a global improved double-mutation genetic algorithm(DMGA),and apply to gray threshold image segmentation;analyze effect of simulation initial parameters on image segmentation result.Simulation results show that precision,effective and reliable of image segmentation is better,compared with the traditional GA,this algorithm has better global and local search capability,and convergence results are stable.

double-mutation genetic algorithm(DMGA)； image segmentation； gray threshold

10.13873/J.1000—9787(2017)02—0138—04

2016—03—11

国家自然科学基金资助项目(11264037)

TP 391.9

A

1000—9787(2017)02—0138—04

周 阳(1991-)，男，硕士研究生，主要研究方向为图像处理、智能算法。