基于遗传模拟退火算法的边缘检测研究

韩 兵,朱成杰

(安徽理工大学 电气与信息工程学院,安徽 淮南 232001)

0 引言

1 遗传算法和模拟退火算法

1.1 遗传算法

遗传算法(GA)通过种群进化寻找最优解,是一个模拟进化论和遗传学原理的计算模型。 根据适者生存的生物进化原理,该算法引入参数优化产生的编码,以群体中适应度函数选择个体,并通过遗传复制、交叉和变异等操作挑选个体,从而过滤较差个体,形成新的群体。 而后在经过一次次的重复操作后,提高种群中的适应度值,最后当符合约束条件,这种一次次的迭代就能够终止[8]。 其基本步骤如下。

(1)初始化每个个体并随机获得在范围内的每个染色体的每个基因值。

(2)根据适应度值函数计算种群中每个个体的适应值。

(3)选择:筛选群体中的个体,挑选合适的个体继承给下一代群体。

(4)交叉:交叉操作是指通过某种形式相互交换两对染色体的局部基因而形成新的个体。

(5)变异:对群体进行变异操作。 即使某些个体的基因座的基因值发生变动。

(6)若算法满足终止条件,则终止;不然,就到转第二步。

程序的停止条件:如果种群中的个体符合预设的适应度,或程序不再继续迭代执行算法,或种群已经达到最优,那么算法终止。

本部分主要对R&D投入与产出所选用的变量作稳健性检验，以支撑研究结果的可靠性和稳健性。考虑到企业R&D投入有较强的可逆性，管理层能够比较容易地操纵当期的R&D研发投入，造成研究结果的失衡。因此，笔者尝试采用企业技术人员数量作为替代指标来进一步分析。因为技术人员数量是企业R&D研发投入与科技专利产出的另一重要因素，且核心技术人员的离职容易造成核心技术的泄露，所以技术人员的聘任是比较稳定，是不易操控的R&D研发投入产出指标。为此，本文手工搜集了2010—2014年财务报告中的技术人员数量，数据来源于巨潮网，并构建如下模型进行考察:

1.2 模拟退火算法

模拟退火算法是一种来源于固体退火原理的概率算法,其中退火的过程有加热、等温和冷却3 个过程。当物体处于加热状态,则物体内能增加,且物体内的粒子做快速不规则移动,在物体处于冷却状态,则物体内能减少,物体内的粒子做规则移动,当物体处于室温时,能量是最小的,粒子实际上是最稳定的[9]。 该算法的过程为:初始化温度T0、初始解V0和降温方式;从当前解S0随机跳变生成一个新解S1;计算旧解和新解之间的变化ΔT;依据接受Metropolis 规则,确定是否可以取新的解,若ΔT ＜0 则接受S1作为新的当前解S0,不然就以概率exp(- ΔT/T) 取S1作为新的当前解S0;如果确定取新解,则替换当前解,完成新解生成对应的当前解的变换部分,并修改目标函数的值;最终算法在温度趋向于最低临界值时趋向于全局最优解。

因为算法在取新解时,即使得到的是差解,也有一定的概率接受该解,防止陷入局部最优,假定冷却过程足够慢,就能得到多数较好解,但弊端是收敛速度慢。

2 遗传模拟退火算法的图像边缘检测方法

具体算法步骤如下。

(1)染色体编码。 要初始化种群,首先要完成染色体编码,而传统的染色体编码方式为编码和解码两步,本文采用一种新的编码方法,该方法可省去解码,即种群中的每一个体配置结构集中的某一个边沿配置结构,对于一个为M×N大小的数字图像,每个染色体用M×N的二维矩阵表示,如此就可以将染色体与边缘配置结构对应起来,进而省略了解码,直接进行适应度的计算。

(2)种群S0初始化。 初始化的种群可随机生成,可保障种群的多样性,而根据数字图像的大小不同,种群规模的取值不同,例如对于256×256 大小的图像,取种群规模为512,512×512 大小的图像,取1024 规模的种群。

(3)通过选择、交叉、变异操作优化种群个体的染色体。 选择操作是为了保留适合度高的个体,将适应度低的个体舍去,保障种群向高适应度进化,而常用的选择方法包括轮盘赌法、随机遍历抽样法、锦标赛选择法等。 本文采用轮盘赌法使种群向高适应度发展。

交叉操作就是将优良个体的染色体片段遗传给后代,同时交叉算子具备全局搜索的功能。 本文使用简单交叉,即在单个编码字符串上定义一个随机节点,然后在此时将两个配体的局部染色体相互替换。

变异操作是指变换个体序列中基因座的基因值。虽然变异防止了种群单一化的长处,让种群适应度提高,但变异概率要适当选择,本文在边缘检测实验中采用0.01～0.05 的变异概率。

(4)模拟退火操作。 将通过遗传过程后的种群S1中的个体代入模拟退火操作中,使其经过Metropolis 准则的调整组成新的种群,即将经选择交叉变异的种群由状态函数跳变产生新种群S2,由Metropolis 准则进行判别操作,若(FS1-FS2)＜0(F 为种群适应度),则接受种群S2为当前解,不然,就以exp(-ΔF/t) 的概率接受S2。

(5)判别SA 抽样能否抵达稳定,如果不,则回到第四步;如果稳定,则往下进行退温过程。

(6)将模拟退火产生的新群体S2与之前产生的新群体S1放在一起,依照适应度进行排序,且将适应度较好的若干个体作为下一代的种群。

(7)判别程序是否抵达终止条件,如果不符合停止条件,则转第三步;如果符合终止条件,就令当前解为最终解。

3 仿真结果与分析

本文运用MATLAB 2018a 平台进行编程,本次仿真分别选用Canny 算子、Sobel 算子和遗传模拟退火算法进行对比实验。 实验结果如图1—2 所示。

图1 不同算法的边缘检测对比组1

图2 不同算法的边缘检测对比组2

从两组图像的对比仿真结果可以看到,本文算法的边缘检测是最清晰的,从肉眼可以看出,它的噪声最小,丢失的信息量最小,该算法更好地分析出了图像的边缘特征,体现特征区域与背景的边缘划分,图像的细节得到更多的体现,在对比算法中,Sobel 算子对边缘的位置判别稍差;Canny 算法检测出的图像有些边沿细节有一定检测失真。 但遗传模拟退火算法则不同,在遗传算法中结合模拟退火的过程能够保证种群的多样性,防止种群收敛于局部最优,使边缘特征提取更加具有准确性。

4 结语

边缘检测是图像特征提取的基础,但许多边缘检测算法都有一定弊端。 针对一些弊端,提出了结合遗传算法全局优化和模拟算法局部优化能力的边缘检测算法。 通过本次仿真实验对该算法的对比检测,表明相较于某些检测算法,本文利用模拟退火对遗传算法的“早熟”问题进行了很好的优化,从而防止了算法陷入局部寻化。 提高了实验结果精度和连续性,在实践运用过程中有很好的使用前景。 本文虽然使遗传算法对检测边缘有了一定的优化,但不论是遗传算法还是其他算法在边缘检测中都还有进一步研究和应用的可能。