遗传算法论文范文

中图分类号：TP311文献标识码：A文章编号：1009-3044(2012)12-2882-04

ThresholdCitrusimageSegmentationResearchandAnalysis

WANGJun,ZHOULi-juan

(CollegeofInformationScienceandTechnology,HunanAgriculturalUniversity,Changsha410128,China)

Abstract：Imagesegmentationisanimportantandprimaryprobleminthefieldofcomputervision.Thethesisputsforwardafullsetofcit?rusimagesegmentationalgorithm,whichadoptsimprovedgeneticalgorithmcombiningwithimprovedthresholdmethod.Thethesis,throughsimulationexperiment,bringsforwardthresholdscopewhichismorestable,andmakestheimagesegmentationedgesmorededi?cated.

Keywords:navelorange;thresholdsegmentation;classesdistance;improvedgeneticalgorithm

图像分割是计算机视觉领域的一个重要而且基本的问题。它在农产品无损检测方面得到了广泛的应用。图像分割算法好坏会直接影响检测系统的准确度。它是从图像处理到图像分析的一个关键步骤。对它的研究一直都是图像技术研究中的热点和焦点之一。但由于图像的特殊性，针对具体图像，针对具体问题，分割算法就不一样，至今还没有找到通用的分割理论，也没有找到对所有图像都适合的通用分割算法。

近几年来，基于遗传算法的图像分割方法得到了很多学者的研究。由于遗传算法在搜索方面具有很强的优势，而图像分割的实质是在众多的参量中去寻找一个最优参量，以此作为分隔的依据。于是如果在图像分割中引入遗传算法去求取最佳阈值，将会大大提高分割效率。

本论文重点对基于传统遗传算法的图像分割算法进行了比较系统的研究。针对传统遗传算法的不足，提出了一些改进措施，并且设计新的阈值确定方法——类类距离法，将两者结合共同运用到脐橙图像分割中，得到了比较好的效果。在最大程度上避免基本遗传算法收敛性差，容易早熟等问题。

1脐橙图像分割

对于脐橙出产大省湖南省，每年脐橙收获完后的分类，分等级进行销售是一项工作量庞大的任务。脐橙表面破损自动检测系统就是基于计算机视觉技术研发而成，其检测的精度较人工挑选有很大提高。该系统中脐橙图像分割算法好坏会直接影响系统检测脐橙表面是否破损的准确度。

通过特定装置获得比较清晰的彩色脐橙图像后，对于表面有破损的脐橙，要进行筛选清理。进行破损部分比对前，要对彩色脐橙图像先进行分割处理。把整幅图像分成脐橙和背景两部分，再提取脐橙部分的图像进行破损分析。这要求将脐橙的边缘和破损部分处理得非常清晰，最大可能的避免将破损区域误分割成图像背景。

2改进的遗传算法

2.1控制参数改进

在遗传算法中，直接影响到算法的收敛性的关键参数是：交叉概率与变异概率，它们的选取会影响到算法行为和性能。在适应度值变换的情况下将交叉概率与变异概率随之调整，以达到保证算法收敛性的目的。于是我们对交叉概率和变异概率按照如下公式进行自动调整：

图5本文提出的算法分割效果图

从表1，图2至图5可以得出以下结论：

1)脐橙图像利用遗传算法来分割，每次运行所得阈值都在变化，但变化的范围不是很大，只是在一定区域做细微波动。这种情况是正常的，也是完全可以接受的，其原因是由于遗传算法随机生产初始种群，这种随机性就带来了阈值的波动性。这也是遗传算法不稳定性的体现。但从表中数据看出采用本文所设计的改进的遗传算法，即交叉概率和变异概率随适应度自动调整，那么分割的图像所得到的阈值，其波动会限制在一个很小的范围以内（稳定在4个像素以内,阈值最大为60，最小为57），这样既保持了群体多样性，又保证了遗传算法的收敛性。同时其稳定性也明显地优于其他算法。

2)利用本文所设计的类类距离遗传算法进行图像分割可以极大减少阈值计算时间，平均运算时间比起其他几个常用方法都缩短了不少，平均仅在2.3s左右。在进化代数相同的条件下，本论文提出的图像分割算法较其他算法更有优势，收敛速度更快。

3)从图2至图5这几个图像分割结果图来看，本文所设计的分割方法中对脐橙图像中的破损部分，边缘轮廓等细节都有非常好的体现，可见结合遗传算法和类类距离法所设计出的图像分割新算法比其他常用算法有很大的优势。

本文通过改变的遗传控制参数结合类类距离法，把改进后的遗传算法应用到脐橙图像分割中去。仿真实验结果表明，此图像分割算法由于所设计的寻找最优阈值的方案比较合理，阈值的计算时间缩短了，使得最终图像分割所用时间明显减少了。同时此方法还做到了将阈值范围稳定在4个像素以内，大大提高了算法全局收敛的稳定性。而且从视觉角度来看，其分割效果更明显，图像边缘处理很细致、清晰。实验证明本论文设计的算法分割图像不仅快速准确，而且还能满足各种图像的实时处理、分析的需求。具有较高的通用性和实用性。

[1]姚敏.数字图像处理[M].北京:机械工业出版社,2006.

[2]孙艳歌,邵罕.基于改进遗传算法的最优阈值图像分割算法[J].信息系统工程,2010,10(6),26-27.

[3]童小念,刘娜.一种基于遗传算法的最优阈值图像分割算法[J].武汉理工大学学报：交通科学与工程版,2008,32(02),301-304.

[4]王强.图像分割中阈值的选取研究及算法实现[J].计算机与现代化.2006(10).54-56.

[5]左奇,史忠科.基于模糊理论的图像分割方法[J].西北工业大学学报,2003,(03):313-316.

[6]劳丽,吴效明,朱学峰.模糊集理论在图像分割中的应用综述[J].中国体视学与图像分析,2006,11(3):200-205.

[7]曹芳,吴迪.基于可见-近红外反射光谱技术的葡萄品种鉴别方法的研究[J].光学学报,2009,29(2),537-540.

遗传算法论文范文

关键词：基因算法；图像分割算法

1、引言

基因算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体（individual）组成。每个个体实际上是染色体（chromosome）带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。

图像分割即将图像分成互不重叠，具有各自特征的区域。这里的特性可以是灰度、颜色或纹理等。图像分割应满足：①分割后所得到的区域总和应覆盖整个图像；②各区域之间互不重叠；③同一区域的像元应具有某种共同特征，这些特征可以是像元值、颜色、纹理、形状等；④同一目标（类别）可以对应于一个区域，也可以对应于多个区域。图像分割是模式识别与图像分析的预处理阶段，是图像处理到图像分析的关键步骤，也是一种基本的计算机视觉技术，在图像识别与图像分析中具有重要的意义。本文介绍了图像分割的一般模型、基于阈值选取的图像分割方法，讨论了基因算法的概念、实现过程、数学理论基础、特点、应用及发展前景。

2、实现方法

2.1编码

编码是遗传算法的基础，编码的好坏直接影响选择、交叉、变异等遗传运算。编码方法也很多，有二进制编码、格雷码编码、浮点数编码、多参数级联编码、多参数交叉编码。本论文采用二进制编码。二进制编码使用的编码符号集是由二进制符号0和1所组成的二值符号集{0，1}，它所构成的个体基因型是一个二进制编码符号串。二进制编码符号串的长度与所要求的求解精度有关。

2.2初始种群

随机产生N个初始串结构数据，每个串结构数据称为一个个体，也称为染色体，N个个体构成一个种群。

2.3自适应函数

在遗传算法中使用适应度来度量群体中各个个体在优化计算中能达到或接近于或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率就较大，反之就小。度量个体适应度的函数称为适应度函数。

2.4基因操作

基因算法有三个基本操作：选择、交叉、变异。

2.4.1选择

基本遗传算法使用比例选择算子。比例选择因子是利用比例于各个个体适应度的概率决定其子孙的遗留可能性。若设种群数为M，个体i的适应度为fi，则个体i被选取的概率为Pi。当个体选择的概率给定后，产生[0，1]之间的均匀随机数来决定哪个个体参加。若个体的选择概率大，则能被多次选中，它的遗传基因就会在种群中扩大；若个体的选择概率小，则被淘汰。

经典遗传算法中常采用赌的选择方法，实际上也是比例选择算子。其基本步骤为：先计算群体中所有个体的适应度总和；再计算每个个体的相对适应度大小，即为各个个体被遗传到下一代群体中的概率；最后使用模拟赌盘操作（即0和1之间的随机数）来确定各个个体被选中的次数。

2.4.2交叉

遗传算法中所谓的交叉运算，是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其它进化运算的重要特征，它在遗传算法中起着关键作用，是产生新个体的主要方法。

遗传算法中，在交叉运算之前还必须先对群体中的个体进行配对。目前常用的配对算法是随机配对，即将群体中的M个个体以随机的方式组成M/2对配对个体组，其中X表示不大于X的最大整数。交叉操作是在这些配对个体组中的两个个体之间进行的。

交叉算子的设计和实现与具体问题有关，常见的交叉算子有：单点交叉、两点交叉、多点交叉、均匀交叉、算术交叉。

2.4.3变异

在生物的遗传和自然进化过程中，其细胞分裂复制环节有可能会因为某些偶然因素的影响而产生一些复制差错，这样会导致生物的某些基因发生变异，从而产生出新的染色体，表现出新的生物性状。

变异是以较小的概率对个体编码串上的某个或某些位值进行改变，如二进制编码中“0”变为“1”，“1”变为“0”，进而生成新个体。在遗传算法中也引入了变异算子来产生新的个体。遗传算法中所谓的变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其它等位基因来替换，从而形成一个新的个体。

2.5运行参数

遗传算法的运行参数选择非常重要，参数不同遗传算法的性能就不同。基本遗传算法有下列4个运行参数需设定，即M、T、Pc、Pm。

M为群体大小。群体大小直接影响到遗传算法的收敛性或计算效率。规模过小，容易收敛到局部最优解；规模过大，会造成计算速度降低。为此，群体大小一般取为10～200。

T为终止进化代数。它表示遗传算法运行到指定的进化代数之后就停止运行并将当前群体中的最佳个体作为所求问题的最优解输出。为此，终止进化代数一般取为100～500。

Pc为交叉概率。交叉概率控制着交叉操作被使用的频度。较大的交叉概率可使各代充分交叉，但群体中的优良模式遭到破坏的可能性增大，以致产生较大的代沟，从而使搜索走向随机化；交叉概率越低，产生的代沟就越小，这样将保持一个连续的解空间，使找到全局最优解的可能性增大，但进化速度变慢；若交叉概率太低，就会使得更多的个体直接复制到下一代，遗传搜索可能陷入停滞状态。为此，交叉概率一般取为0.4～0.99。

Pm为变异概率。变异概率控制着变异操作被使用的频度。变异概率取值较大时，虽然能够产生较多的个体，增加了群体的多样性，但也可能破坏很多好的模式，使得遗传算法的性能近似于随机搜索算法的性能；若变异概率取值太小，则变异操作产生新个体和抑制早熟现象的能力就会较差。实际中发现，当变异概率很小时，解群体的稳定性好，一旦陷入局部极值，易产生成熟收敛；而增大变异概率，可破坏解群体的同化，使解空间保持多样性，搜索过程可从局部极值点跳出来，收敛到全局最优解。为此，变异概率一般取为0.0001～0.1。

参考文献

[1]章晋.图象分割[M].北京：科学出版社，2001.

[2]徐宗本.计算智能――模拟进化计算[M].北京：高等教育出版社，2004.

遗传算法论文范文篇3

[关键词]生物进化遗传算法全局优化

遗传算法是模拟生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的一种重要形式。同时，遗传算法是一种通用的优化算法，其编码技术和遗传操作比较简单，优化不受限制条件的约束，不需要有先验条件。其搜索过程是从问题解的一个随机产生的集合开始的，而不是从单个个体开始的，具有隐含并行搜索特性，也就大大减少可陷入局部极小值的可能。

1.基本遗传算法

Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质，所以每个基因产生的个体对环境具有某种适应性。基因突变和基因交叉可产生更适应于环境的后代。经过优胜劣汰的自然选择，适应性高的基因结构得以保存下来。

在基本遗传算法的运行过程中，控制参数的选择对搜索性能产生非常大的影响。因此对参数的合理选择与控制是十分重要的，以使GA呈现最佳搜索轨迹最终得到最优解。主要的控制参数包括染色体的长度L,种群规模M，交叉概率pc，变异概率pm。

作为一个优化算法，基本遗传算法也具有一些缺点，主要体现在以下几个方面。

首先，基本遗传算法是一类随机搜索型算法，而非确定性迭代过程描述。这种广种薄收的算法计算效率较低。

其次，对基本遗传算法的数值试验表明，算法经常出现过早收敛的现象。

第三，基本遗传算法的遗传和变异的完全随机性虽然保证了进化的搜索功能，但是这种随机变化也使得一些好的优良个体的形态被过早破坏，降低了各代的平均适应值。

第四，Rudolph通过Markov链方法证明了基本遗传算法是不收敛到最优解的。

第五，基本遗传算法中常采用伪随机函数(rand)产生的“随机数”来生成初始种群和控制遗传算子的操作，这些“随机数”不具备真正的随机性和遍历性，很大程度上影响到最优解的出现。

基于这些局限性，本设计在下文中提出了一种改进的遗传算法，针对这些问题提出了几种有效的解决方案。

2.改进遗传算法的设计

2.1遗传算法的收敛性的定义

Rudolph给出了一种针对个体的收敛性定义：

设Zt为t时刻种群X(t)中所包含的个体的适应度值的最大值，f*为适应度值函数f(x)在所有可能的个体所组成的集合中所取的最大值，若Zt满足:

（2.1）

则称算法收敛到最优解。

2.2精英保留策略

针对基本遗传算法不能收敛到全局最优解的问题，本设计提出，在进行选择前用保留最优解的策略，使算法最终能以100%的概率收敛到最优解。

精英保留策略是改进的遗传算法收敛性的保证。

2.3引入混沌的遗传算子

⑴Logistic映射在交叉操作中的应用

用混沌序列来控制交叉点的选择的思想为:设染色体有L位长，先产生一个混沌序列，然后把序列。映射到染色体的基因位空间，并在相应的位置进行交叉操作。

⑵Logistic映射在变异操作中的应用

用混沌序列来控制变异位置的选择的思想为:设染色体有L位长，先产生一个混沌序列，然后把序列映射到染色体的基因位空间，并在相应的位置进行变异操作。

本设计中，采用Logistic映射产生混沌序列来控制遗传算子操作的策略称为混沌控制策略，它的优点在于在遗传进化的过程中充分利用了混沌所具有的随机性，尤其是混沌的遍历性，使交叉和变异操作具有内在的规律性，克服了简单遗传算法中伪随机所带来的缺点，充分发挥了遗传算法和混沌的各自优点。

2.4自适应交叉和变异率算子

本设计中提出自适应交叉和变异率算子：当适应度低于平均适应度值时对它就采用较大的交叉率和变异率；如果适应度高于平均适应度值，对它就根据其适应度值取相对应的交叉率和变异率。当适应度值接近最大适应度值时，交叉率和变异率就越小；当等于最大适应度值时，交叉率和变异率的值为零。为了保证每一代的优良个体不被破坏，采用精英选择策略，使它们直接复制到下一代中。

经过上述改进，pc和pm计算表达式如下：

（2.2）

（2.3）

上式中pc1，pc2，pm1，pm2的取值需要根据实际问题的规模，通过多数实验验证得到。

2.5灾变算子设计

设计中引用了灾变的思想：在种群适应值保持在一个稳定值一段时间后，发生灾变，杀掉最优秀的个体，这样才可能产生更优秀的物种。

3.实验环境

实验测试的环境和工具:

⑴硬件环境:IntelPentium®T4200@2.00GHz+2GRAM;

⑵操作系统:MierosoftWindowsxpProfessional;

⑶编译环境:microsoftvisualc++6.0;

⑷测试函数:

4.结论

⑴知道遗传算法的设计要从大体五个方面来设计：编码，初始种群的设定，适应度函数的设计，遗传操作的设计和控制参数的设定。在很好地设计一种遗传算法，且将其进行具体实际的应用，怎样去很好地选择、平衡这五个方面使算法得到更加理想的效果，这还需要继续进行试验研究，探讨。

⑵在进行遗传算法理论分析研究时，发现相关理论分析比较少。每一种设计的遗传算法都是将其进行具体的应用，所以算法的灵活性比较大，这样去寻求一种概括性的理论分析就存在一定的难度，且本设计提出的自适应遗传算法，从理论上分析研究其收敛到全局最优，仍然需要进一步的研究。

⑶关于遗传算法的定量分析和数学证明，仍需要进一步的研究。

参考文献:

[1]王小平，曹立明.遗传算法―理论应用与软件实现[M].西安：西安交通大学出版社，2002：21-22.

[2]张明辉，王尚锦.自适应遗传算法及其应用[J].机械工程学院学报，2002，20(1)：23-25.

[3]雷德明.多目标智能优化算法及其应用[M].北京：科学出版社，2009：67-78.

[4]李敏强，寇纪淞，林丹等.遗传算法的基本理论与应用[M].北京：科学出版社，2004：55-57.