4.遗传操作
遗传操作主要包括:选择(selection )、交叉(crossover)、变异mutation)三个操作数。
1)选择
选择过程是模仿自然选择现象，从父代种群中选出优良个体。个体的适应度值越大，在子代中将有更多的机会作为父代产生一个或多个子代个体。通常选用适应度比例法(轮盘赌方式roulette wheel )确定选择次数，该法中的各个体选择概率和其适应度值成比例。
2)交叉
最简单的交叉操作为单点交叉:首先，对父代个体进行随机配对;然后，配对个体随机设定交叉位置;最后，交换配对个体的部分信息。当染色体长度为l时，l-1有个交叉位置，单点交叉可实现l- 1种不同的交叉结果。
个体进行随机配对;然后，配对个体随机设定交叉位置;最后，交换配对个体的部分信息。当染色体长度为l时，l-1有个交叉位置，单点交叉可实现l- 1种不同的交叉结果。
父代个体a 10011|011 10011100 新个体a’
父代个体b 01101|100 01101011 新个体b’
3)变异
变异操作随机选择变异基因序号，根据一定的变异概率pm对该序号基因进行变异。www.lw881.com对于二进制编码个体通常采用0变为l， 1变为0。
1 0 0 1 1 0 1 1 0 1 1 0 1
变异位
5.控制参数
控制参数主要有:种群规模、迭代次数、交叉概率、变异概率等。对此标准遗传算法都设为固定值。标准遗传算法的特点是:
1)轮盘赌选择方法:
2)随机配对;
3)单点交叉，生成两个子代个体:
4)种群内允许相同个体出现。
可见，遗传算法从任一初始化种群出发，通过选择(使优秀个体有更多机会传给子代)，交叉(体现优秀个体间的信息交换)，变异(引入新的个体，保持种群的多样性)操作种群一代一代的进化到搜索空间中最优点附近，直至收敛到最优解点。遗传算法不是直接作用在问题空间中，而是编码空间中，而且遗传操作非常简单。这使得遗传算法具有了简单，通用，鲁棒性强的特点。
第六章 基于遗传算法的最大类间方差分割法 6.1 普通最大类间方差法（otsu法）简介
由 otsu于 1978 年提出的最大类间方差法以其计算简单、稳定有效而一直广为使用。该方法又称为大津阈值分割法，是在判决分析最小二乘法原理的基础上推导得出的，算法较为简单。此方法由于其简便性和分割准确性在图像分割中被大量采用，但是缺点在于与，与后文所述的基于遗传算法最大类间方差法相比，要求得最佳阈值，需要遍历灰度范围0~l-1内的所有像素并计算方差，最后比较得出最大方差，计算量大同时效率也很低，运算时间偏长。[25]。
基本思路：选取的最佳阈值t应当使得不同类间的分离性最好。首先计算基于直方图得到各分割特征值的发生概率，并以阈值变量t将分割特征值分为两类，然后求出每一类的类内方差及类间方差，选取使得类间方差最大，类内方差最小的t作为最佳阈值。具体步骤如下：
设原始灰度图像灰度级为l，灰度级为i的象素点数目为ni，则图像的全部象素数为
按阈值t可将所有象素划分两类：c0= (0,1,2,…,t)和c1 = (t +1,t + 2,…,l -1) 。而c0和c1类的类出现概率w及均值μ 分别由下列各式给出：
式中：
。
不难得出，对任何t值，下式都能成立：
c0和c1类的方差可由下式求得：
定义类内方差σw、类间方差σb、总体方差σt 为：
引入
则最佳阈值t*可选择为：
t* = maxη(t)
在图像处理过程中，原有的图像分割方法都不可避免的会产生误差，这些误差会影响到图像处理和识别的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法其固有的并行性和不易陷入局部最优的特点使之非常适于大规模搜索空间的寻优，因此，己广泛应用于图像处理领域。图像分割是一个在复杂的参量空间中寻找最优分割参量的问题，遗传算法可以有效的寻找参量空间的全局最优值，从而为解决图像分割中的参量选择难题提供了有力的保证。本章将着重讨论基于遗传算法的最大类间方差分割法在图像分割中的应用。
6.2 最大类间方差图像分割的遗传算法描述
正如前文所述，最大类间方差的求解过程就是在解空间中找到一个最优解，使得类间方差最大。为了改进普通最大类间方差法，采用遗传算法，求其寻找最优解的过程进行改进。遗传算法的最大类间方差法步骤如下:
1) 建立初始种群并编码。
在matlab中，通过函数crtbp建立初始种群，在0~255之间以同等概率随机产生初始种群，通常初始种群的规模选取不易过大。随机的在0~255之间以同等概率生成40个个体a 1 ~a40作为第一次寻优的初始的种群。通过函数bs2rv进行二进制码和实值的转变。因为图像的灰度级在0~255之间，所以将染色体编码成8位二进制码，它代表某个阈值。（函数源代码参见附录[二]、附录[三]）
2) 适应度函数计算各个体的适应度值。采用公式
p1=s1/i; p2=s2/j
f(k)=i*j*(p1-p2)* (p1-p2)/(256*256)
作为适应度函数对个体进行适应度计算。式中，f(k)为适应度函数；i为目标图像的像素数j为背景图像的像素数；s1 为目标图像的像素和，s2为背景图像的像素和。（函数源代码参见附录[四]）
3) 选择：:
与标准遗传算法略有不同，本例未采用轮盘赌方法进行选择操作，而是以matlab中的高级函数select作为选择程序。在这种方法中，需要设定代沟，即整个种群在每一代中没有完全被复制，有部分剩余。本例设代沟ggap=0.9，即每次遗传后子代数量为父代的90%。（函数源代码参见附录[五]）。
4) 交叉:
在matlab中使用高级函数recombin实现。即在当前种群中每次选取两个个体按设定的交叉概率（0.7）进行交叉操作，生成新的一代种群; （函数源代码参见附录[六]）。
5) 变异:
在matlab中使用函数mut实现。即根据一定的变异概率pm，选取当前种群的每一行对应一个个体并用概率pm变异每一个元素，从而形成新一代群体。（函数源代码参见附录[七]）
6) 终止
本程序中选择指定代数（50代）作为寻优循环跳出的判断条件。判断跳出条件是否满足，若不满足，则以新生成的群体作为第一代群体，转到步骤3继续寻优，否则转到步骤7。
7) 将最后一代群体中适应度最大的个体作为最优结果，将其反编码（采用bs2rv函数），即为所求的最佳分割阈值。
6.3 实验结果与效果对比图
为了验证算法的效果，选用一幅she的jpg图像进行实验，原始图像显示：
图6.1
原始图像
对上图进行灰度变化后的灰度图像如下：
图6.2
灰度图象
在对灰度图像转化为索引图像并将其数据类型转化为双精度型之后的图片如下：
图6.3
索引图像
此时，就可对上图进行基于遗传算法的最大类间方差分割法进行处理了。设定初始群体的数目n=40，交叉概率p c=0. 9，代沟为0.9，变异率为pm采用默认值。最大迭代数g=50。实验结果及数据如下：
通过50次迭代寻优后，找到最优化阈值m=162:
图6.4
基于遗传算法的最大类间方差法分割后图像
图6.5
直方图双峰法分割后的图像
