论文部分内容阅读
摘 要：基因算法又叫遗传算法，是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。基因算法模型比较复杂，在针对具体问题时往往需要进行优化处理。本文主要基于基因算法讨论图像分割算法，以求找到最优的基因算法。
关键词：基因算法；图像分割算法
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] 陈国良，王煦法，庄镇泉，王东生.遗传算法及其应用[M].北京：人民邮电出版社，2001.
[4] 李辉，吕英华.在遗传算法基础上的自动阈值选取方法[M].长春：东北师大学报（自然科学版），2006年6月，第38卷第2期.
关键词：基因算法；图像分割算法
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] 陈国良，王煦法，庄镇泉，王东生.遗传算法及其应用[M].北京：人民邮电出版社，2001.
[4] 李辉，吕英华.在遗传算法基础上的自动阈值选取方法[M].长春：东北师大学报（自然科学版），2006年6月，第38卷第2期.