学校代码 10126 学号 00708037 分类号密级
本科毕业论文
基于遗传算法的图像阈值分割
学院、系数学科学学院计算数学系
专业名称信息与计算科学
年级 2007级
学生姓名刘家祥
指导教师曹军
2011年 5月 20 日
内容摘要
图像分割就是指把图像分成各具特性的区域并提取出感兴趣目标的技术和过程。图像的分割是以灰度值作为分割的依据,通过各个像素的灰度值和事先确定的阈值的比较来分割图像。如何确定最合适的阈值是处理好图像分割的关键,这自然成为一直以来分割算法研究的焦点。
遗传算法是对生物进化论中自然选择和遗传学机理中生物进化过程的模拟来计算最优解的方法。遗传算法具有众多的优点,如鲁棒性、并行性、自适应性和快速收敛,可以应用在图像处理技术领域中图像分割技术来确定分割阈值。
本文主要介绍基于遗传算法的最小误差阈值法、最大类间方差法（Otsu法）以及最佳直方图熵法(KSW熵法)等三种方法分割图像。
关键词：图像分割，遗传算法，阈值分割
Abstract
Image segmentation refers to the image into regions each with characteristics and goals of the technology to extract and process of interest. Segmentation is a segmentation based on gray value, gray value of each pixel through the predetermined threshold value and comparing the image segmentation. How to determine the most appropriate threshold is the key to handling image segmentation, which has naturally become the focus of segmentation algorithms.
Genetic algorithm is a biological theory of evolution and genetic mechanism of natural selection in biological evolution simulation method to calculate the optimal solution. Genetic algorithm has many advantages, such as robustness, parallel, adaptive, and fast convergence, can be used in the field of image processing image segmentation technique to determine the split threshold.
In this paper, genetic algorithm based on minimum error threshold, the largest class variance (Otsu method) and the best histogram entropy (KSW entropy method) are three ways to split the image.
Keywords : Image segmentation, genetic algorithms, threshold
目录
第一章绪论 .................................................. - 1 - 第二章遗传算法概述 ........................................ . - 2 -
2.1遗传算法的研究历史....................................... - 2 -
2.2生物背景................................................. - 2 -
2.3遗传算法的基本思想....................................... - 3 -
2.4遗传算法的几个概念....................................... - 4 -
2.4.1适应度函数......................................... - 4 -
2.4.2遗传算法最常用的算子............................... - 4 -
2.5遗传算法运算的基本流程................................... - 5 - 第三章图像分割的现状 ........................................ - 7 -
3.1图像分割简介............................................. - 7 -
3.2图像分割方法............................................. - 8 -
3.2.1基于边缘检测的分割................................. - 8 -
3.2.2基于区域的分割..................................... - 8 -
3.2.3边缘与区域相结合的分割............................. - 9 -
3.3阈值选取................................................. - 9 - 第四章基于遗传算法的图像阈值分割 ........................... - 10 -
4.1图像阈值................................................ - 10 -
4.2阈值分割的原理.......................................... - 10 -
4.3最小误差阈值法.......................................... - 11 -
4.3.1最小误差法图像阈值分割............................ - 11 -
4.3.2 利用遗传算法来改进最小误差法...................... - 12 -
4.4 最大类间方差法（Otsu法）............................... - 13 -
4.4.1最大类间方差法（Otsu法）阈值分割.................. - 13 -
4.4.2 Otsu阈值分割的遗传算法设计........................ - 15 -
4.5 KSW熵法................................................ - 17 -
4.5.1 KSW熵阈值分割................................... - 17 -
4.5.2 KSW单阈值分割的遗传算法设计..................... - 18 -
4.5.3 KSW双阈值分割的遗传算法设计..................... - 19 - 第五章基于新的遗传算法的图像分割 ........................... - 25 -
5.1混沌遗传算法............................................ - 25 -
5.2量子遗传算法............................................ - 25 -
5.3免疫遗传算法............................................ - 25 - 结论 .......................................................... - 26 - 致谢 .......................................................... - 27 - 参考文献: ..................................................... - 28 -
基于遗传算法的图像阈值分割
第一章绪论
图像分割是图像处理与计算机视觉的基本问题之一，是图像处理到图像分析的关键步骤。图像分割方法（包括阈值法、边缘检测法、区域跟踪法)的研究始于上世纪50年代。随着越来越多人的研究，近年来涌现了许多新理论、新方法，但是没有一种方法能满足所有图像分割领域。
在众多的图像分割技术中，阈值化技术是基于区域的图像分割技术，是图像分割中最重要而有效的技术之一。阈值法是一种传统的图像分割方法，因其实现简单、计算量小、性能较稳定而成为图像分割中最基本和应用最广泛的分割技术。在实际应用中，分割是对图像进一步分析、识别的前提，分割的准确性将直接影响后续任务的有效性。其中阈值的选取是图像阈值分割方法中的关键技术。
遗传算法(genetic algorithm，GA)是基于进化论自然选择机制的、并行的、统计的、随机化搜索方法。使用遗传算法求解科学研究工作和工程技术中各种组合搜索和优化计算问题这一基本思想早在20世纪60年代初期就由美国Michigan
大学的Holland教授提出，其数学框架也于20世纪60年代中期形成。由于GA的整体搜索策略和优化计算不依赖于梯度信息，所以它的应用范围非常广泛，尤其适合于处理传统方法难以解决的高度复杂的非线性问题。
在分割复杂的图像时，人们往往采用多参量进行信息融合，在多参量参与的最优值的求取过程中，优化计算是最重要的，把自然进化的特征应用到计算机算法中，将能解决很多困难。遗传算法的出现为解决这类问题提供了新而有效的方法，它不仅可以得到全局最优解，而且大量缩短了计算时间。在图像分割过程中，最关键的就是找到最优的阈值，遗传算法的整体搜索策略和优化搜索方法能够快速准确地得到基于成个灰度图像的阈值最优解。
第二章遗传算法概述
1.遗传算法的研究历史
遗传算法是演化计算的一个分枝，也是人工智能发展的一个重要领域。它是受达尔文进化理论的思想而激发的一种用进化思想来解决问题的方法。遗传算法研究的兴起是在80年代末和90年代初期，但它的历史起源可追溯至60年代初期。早期的研究大多以对自然系统的计算机模拟为主。如Fraser的模拟研究，他提出了和现在的遗传算法十分相似的概念和思想；同时代，演化计算思想首先是由I.Rechenberg于20世纪60年代在他的著作《演化策略》(“Evolution strategies”)一书中提出来的，然后一些研究者发展了他们的思想。Holland和DeJong的创造性研究成果改变了早期遗传算法研究的无目标性和理论指导的缺乏。其中，Holland于1975年出版的著名著作《自然系统和人工系统的适配》系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论。这一理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。
同年，DeJong的重要论文《遗传自适应系统的行为分析》将Holland的模式理论与他的计算实验结合起来，并提出了诸如代沟等新的遗传操作技术。可以认为，DeJong所作的研究工作是遗传算法发展过程中的一个里程碑。
进入80年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。此后至今遗传算法的应用领域不断扩大，遗传算法应用研究已从初期的组合优化求解拓展到了许多更新，更工程化的应用方面。
2.生物背景
达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。这种学说认为，生物要生存下去，就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就
容易被淘汰，产生后代的机会也少得多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存，不适者淘汰的过程叫做自然选择。它表明，遗传和变异是决定生物进化的内在因素。自然界中的多种生物之所以能够适应环境而得以生存进化，是和遗传和变异生命现象分不开的。正是生物的这种遗传特性，使生物界的物种能够保持相对的稳定；而生物的变异特性，使生物个体产生新的性状，以致于形成新的物种，推动了生物的进化和发展。
遗传算法正是模拟达尔文的这种遗传选择和自然淘汰的生物进化过程的计算模型，是一种具有“生存+检测”的迭代过程的搜索算法。它以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索.其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容；作为一种新的全局优化搜家算法，遗传算法以其简单通用、稳定性强、适于并行处理以及高效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能算法之一。
3.遗传算法的基本思想
生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。遗传算法就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。
遗传算法受到达尔文进化论的影响很大。在遗传算法中，问题的解是逐渐进化得到的。遗传算法的计算从一组可能解开始，这组解被称作种群（Population），在算法中被表示成基因。我们又把种群中的解拿出来去构成新的一个种群，这是因为我们期望新的种群要比旧的种群要好。当然，新的种群中的解要有这样的性质，就必须按照它的适应度去选择，适应度越高，它参与构造新的种群的机会就
越大。这个过程一次又一次的重复，一直到我们所给的约束条件满足为止，比如说种群中解得个数或者种群的良好程度。
4．遗传算法的几个概念
4.1 适应度函数
在遗传算法中使用适应度来度量群体中各个个体在优化计算中有可能达到或接近或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率就较大；而适应度较低的个体遗传到下一代的概率就相对小一些。度量个体适应度的函数称为适应度函数。
评价个体适应度的过程为：
（1）对个体编码串进行解码处理后，可得到个体的表现型；
（2）由个体的表现型可计算出对应个体的目标函数值；
（3）根据最优化问题的类型，由目标函数按一定的转换规则求出个体的适应度。
4.2 遗传算法最常用的算子
(1)选择算子:选择算子从群体中按某一概率成对选择个体，某个体xi被选择的概率Pi与其适应度值成正比。
选择算子有很多，最常用的是比例选择算子。它是把当前的个体按与适应度成正比的概率复制到新的群体中去。比例选择实际上也是一种赌盘选择，其基本步骤为:
①先计算出群体中所有个体的适应度的总和；
②其次计算出每个个体的相对适应度的大小，它即为各个个体被遗传到
下一代群体中的概率；
③最后再使用模拟赌盘操作(即O和1之间的随机数)来确定各个个体被选中
的次数。
（2）交叉算子：交叉算子将被选中的2个个体的基因链按概率进行交叉，生成2个新的个体,交叉位置是随机的。
（3）变异算子:变异算子将新个体的基因链的各位按概率进行变异，对二值基因链来说即是取反。
在遗传算法中使用变异算子主要由以下两个目的:
①改善遗传算法的局部搜索能力；
②维持群体的多样性，防止出现早熟现象。
5.遗传算法运算的基本流程
(1)针对图像分割编写代码:遗传算法一般不直接处理空间的参数而是集进行编码,即用0和1构成的字符串形成矩阵。
(2)随机初始化像素群体X(0):=( x
1,x
2
,…,x
n
):遗传算法从这些群体出发，
模拟生物进化过程进行选择,最后得出需要的个体集合,满足优化搜索的要求。
(3)对当前像素群体X(t)中每个个体x
i 计算其适应度F(x
i
)，适应度表示了该
像素的灰度值:遗传算法不涉及问题的具体领域,只需依据适应度函数控制像素变化。根据适应度函数对每个像素计算其适应度，为选择提供依据。设计适应度函数的方法是把问题的目标函数转换成合适的适应度函数和辅助函数。
(4)应用选择算子产生Xr(t)。
(5)对Xr(t)应用其他的算子,产生新一代像素群体X(t+1)，应用其他的算子可以扩展图片像素的覆盖面，体现整体计算的策略。
(6)选择:这是是遗传算法的关键，它参照了适者生存的理论。
(7)变异:模拟了生物的基因突变现象。对像素进行重新评价、选择如此循环往复，使图像中目标物体平均适应度不断提高直到上限则迭代过程收敛，算法结束。
GA的计算过程流程图如下：
编码和种群生成
种群适应度估计
选择
交叉
变异
第三章图像分割的现状
1.图像分割简介
图像分割是一种重要的图像技术，它不仅得到人们广泛的重视和研究，也在实际中得到大量的应用。图像分割在不同领域有时也用其他名称，如目标轮廓(Object Delineation)技术，阈值化(Thresholding)技术，图像区分或求差(Image discrimination)技术，目标检测(Target Detection)技术，目标识别(Target recognition)技术，目标跟踪(Target tracking)技术等。这些技术本身或核心实际上也就是图像分割技术。图像技术在广义上是指与各种图像有关技术的总称。图像技术种类很多，跨度很大，但可以将它们归在一个整体框架—图像工程之下。图像工程是一个对整个图像领域进行研究的新学科。它的内容十分丰富，根据抽象程度和研究方法等的不同可分为三个各有特点的层次:图像处理、图像分析和图像理解(如下图所示)
图像处理着重强调在图像之间进行变换以改善图像的视觉效果。图像分析则主要是对图像中感兴趣的目标进行检测和测量，以获得它们的客观信息从而建立对图像的描述。图像理解的重点是在图像分析的基础上，进一步研究图像中各目标的性质和它们之间的相互关系，并得出对原始成像客观场景的解释，从而指导和规划行动。图像处理、图像分析和图像理解具有不同的操作对象。图像处理是比较低层的操作，它主要在图像象素级上进行处理。图像分析则进入了中层，它侧重于对象素集合—目标的表达、测量和描述。图像理解主要是高层操作，基本
上是对从描述中抽象出来的数据符号进行处理。
在对图像的研究和应用中，人们往往对图像中的某些部分感兴趣。这些部分常称为目标或前景(其他部分为背景)，它们一般对应图像中特定的、具有独特性质的区域。为了辨识和分析目标，需要将它们分离提取出来。在此基础上才有可能对目标进一步利用。图像分割就是指把图像分成各具特性的区域并提取出感兴趣目标的技术和过程。这里特性可以是象素的灰度、颜色、纹理等，预先定义的目标可以对应单个区域，也可以对应多个区域。
2.图像分割方法
图像分割方法有很多，常见的分割包括基于边缘检测的分割、基于区域的分割、边缘与区域相结合的分割等。
2.1基于边缘检测的分割
基本思想是先检测图像中的边缘点，再按一定策略连接成轮廓，从而构成分割区域。其难点在于边缘检测时抗噪性和检测精度的矛盾。若提高检测精度则噪声产生的伪边缘会导致不合理的轮廓；若提高抗噪性，则会产生轮廓漏检和位置偏差。为此，人们提出各种多尺度边缘检测方法，根据实际问题设计多尺度边缘信息的结合方案，以较好地兼顾抗噪性和检测精度，但仍不能从根本上克服此矛盾。
2.2 基于区域的分割
基本思想是根据图像数据的特征将图像空间划分为不同区域。常用的特征包括:直接来自原始图像的灰度或彩色特征，由原始灰度或彩色值变换得到的特征。方法有阈值法、区域生长法、聚类法、松弛法等。阈值法是通过设定不同的特征值，将象素点分为若干类。其难点在于阈值的设定方法。对传统阈值法的改进包括局部阈值法、模糊阈值法、随机阈值法以及引入新的理论来优选阈值；聚类法是在特征空间对象素进行聚类。它包括硬聚类、概率聚类和模糊聚类等。聚类准则是聚类分割的关键；松弛法是一种动态调优的标号方法。它包括概率松弛、模糊松弛等。其关键在于标号相容模型和迭代方法的收敛性。
2.3 边缘与区域相结合的分割
边缘检测能够获得灰度或彩色值的局部变化强度，而区域分割能够检测特征的相似性与均匀性。边缘与区域组合分割的主要思想是结合二者的优点，通过边缘点的限制，避免区域的过分割；同时通过区域分割补充漏检的边缘，使轮廓更加完整。
3.阈值选取
图像分割在图像识别和分析中具有重要意义，阈值选取是其关键技术，国内外学者从不同角度提出了许多种阈值选择的方法。
目前公认较好的几种方法如下所示:
（1）最佳熵法。最佳熵法对不同目标大小和信噪比的图像均产生很好的分割效果，且受目标大小的影响小，可用于小目标分割，但由于最大嫡法涉及对数运算，运算速度慢，不能用于实时处理。
（2）最大类间方差法。最大类间方差法对噪声和目标大小十分敏感，它仅对类间方差为单峰的图像产生较好的分割效果。当目标与背景的大小比例悬殊时，类间方差函数可能呈现双峰或多峰，此时用最大类间方差法选取的全局最大值并不一定是正确阈值，此方法失效。Reddi等提出了一种快速算法，提高了运算速度，但并没有解决准则函数极大值不唯一的缺陷。
（3）最小误差法。最小误差法受目标大小和噪声影响小，对小目标图像仍具。有较好的分割效果。但运算量较大，不利于实时处理。
第四章基于遗传算法的图像阈值分割
1.图像阈值
一幅图像通常包括目标物体、背景高斯噪声、运动模糊等,由于目标物体和背景的灰度有较大差异,和噪声产生的麻点的灰度值相差更多,要从多值的灰度图像中提取目标物体,常用的方法就是设定某一阈值,将图像像素分成2大部分:大于阈值的像素和小于阈值的像素即灰度图像的二值化。二值化处理主要功能就是把目标物体和背景灰度差异较大的图像分成2个部分。二值化是数字图像处理中一项最简单的变换方法,通过采用固定阈值、双固定阈值等不同算法,把一幅灰度图变成二值图像,将所需的目标物体从复杂的图像背景中脱离出来。具体的操作过程是先由通过算法找到一个合适阈值,要求是阈值处于目标物体阈值和背景阈值之间。若图像中的像素灰度值小于该阈值,则将该像素的灰度值设置为0或255，若图像中的像素灰度值大于该阈值,则将该像素的灰度值设置为255或0。也就是说通过一个以阈值灰度值为跳变点的阶跃函数来实现图像处理。
固定阈值法：固定阈值法就是为灰度图像设定一个阈值,把灰度值小于给定阈值的像素置为0(或者255)，大于阈值的像素置为255(或者0)，从而实现灰度图像到二值图像的变换。
双固定阈值法：双固定阈值法预先设置2个阈值,当对图像进行处理时,如果某个像素的灰度值在两者之间时置0(或者255)；其余情况则置255(或者置0)。应当根据具体情况选择双固定阈值法改变图像灰度值的方向。
2.阈值分割的原理
对灰度图像的阈值分割就是先确定一个处于图像灰度取值范围之中的灰度阈值，然后将图像中各个象素的灰度值都与这个阈值相比较，并根据比较结果将对应的象素分割为两类:象素的灰度值大于阈值的为一类，象素的灰度值小于阈值的为一类。这两类一般分属于图像中的两类区域:目标和背景。这样就可以将目标从背景中分离出来。由此可见，阈值化分割算法主要有两个步骤:
（1）确定需要的分割阈值；
（2）将阈值与象素比较以划分象素。
以上步骤中，确定阈值是分割的关键。确定阈值后就可以将阈值与象素值比较以对图像进行分割。分割的结果直接给出图像区域。假设一幅原始图像为f(x,y)，则分割后的图像g(x,y)可定义为:
1(,)(,)0(,)f x y T g x y f x y T
>?=?≤? 其中，T 为阈值。这样得到的g(x,y)是一幅二值图像，它相当于把原始图像用空间占有数组来进行表达。
3.最小误差阈值法
3.1 最小误差法图像阈值分割
最小误差法由Kittler 和Illingworth 于1986年提出,该分割方法受目标大小和噪声影响小,能较好地克服算法的不足,是一种理论严密,效果较佳的图像阈值分割方法。定义如下:
假设h(i)为图像的各级灰度值,0≤i ≤255,准则函数:
00110011()12[()ln ()()ln ()]2[()ln ()()ln ()]f t P t t P t t P t P t P t P t σσ=++-+
式中：
00
()()
t i p t h i ==∑，121()()L i t p t h i -=+=∑； 20
20
00[()]()()t i i t h i p t μσ=-=∑，1
2
22122[()]()()L i t i t h i p t μσ-=+-=∑；
*000()()()t
i h i i t p t μ==∑，1
*121()()()L i t h i i t p t μ-=+=∑；
则最佳阈值为: t=ArgminF(t),其中：
(0,1,2,...,t L ∈-，)(0t p 、1()p t 分别为灰度值在0～t 和t ～( L- 1) 之间的
像素数；
20σ、22σ分别为灰度值在0～t 和t ～( L- 1)之间的方差；
0()t μ 、1()t μ 分别为灰度值在0～t 和t ～( L- 1)之间
的平均灰度值。
3.2 利用遗传算法来改进最小误差法
由于最小误差法选取阈值的过程实质上是一种寻求最优解的过程，故可利用GA 所具有的快速寻优的特点对其进行优化，以达到提高效率的目的。其具体做法如下:
（1）编码和适应度函数的确定
对于具有256级灰度的图像，其侯选阈值在0～255之间，故可用一个8位二进制码进行编码，即把O ～255之间的值编码成00000000～11111111之间的一个码。
至于适应度函数，可用最小误差法的准则函数，即:
00110011()12[()ln ()()ln ()]2[()ln ()()ln ()]f t P t t P t t P t P t P t P t σσ=++-+
为了正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或零，不能为负数。为此，采用一种变换方法:
max max max ()()()0()C f t f t C F t f t C -
式中C max 为我们预先指定的一个较大的数。
（2）控制参数的确定
GA的控制参数主要包括群体规模、变异率和交换率等。这些参数的选择尚处于研究阶段，目前参数的选择主要靠实验确定，群体规模影响到遗传算法的最终性能和效率。若规模太小会过早收敛到局部最优解，然而群体规模太大，每一代需要的计算量也越多，这有可能导致无法接受的慢收敛率。
交叉率控制交叉算子应用的频率，交叉率越高，群体中个体的更新就越快，如果交叉率过高，相对选择能够产生的改进而言，高性能的个体被破坏的要更快。如果交叉率过低，搜索会因为太小的探查率而导致停滞不前。
变异是增加群体多样性的搜索算子，一个很小的变异率足以防止整个群体中任一给定位保持永远收敛到单一的值。
（3）选择方法的确定
采用比例选择的方法，其具体执行过程如下:
①先计算出群体中所有个体的适应度总和。
②其次计算出每个个体的相对适应度的大小，它即为每个个体被遗传到下一代群体中的概率。
③最后再使用模拟赌盘操作(即O到1之间的随机数)来确定各个个体被选
中的次数。
（4）停止准则的确定
根据最大迭代次数G和当前群体的平均适应度与上一代群体的平均适应度
值的差是否小于某一个较小的常数来确定是否终止运算。即当迭代次数大于G 或平均适应度的差小于某一个较小的常数时，终止运算。
4.最大类间方差法（Otsu法）
4.1最大类间方差法（Otsu法）阈值分割
Otsu 提出的通过求类间方差最大来选择阈值的方法是一种较为常见的方法。 它的基本原理为用最佳阈值将图像的灰度直方图分割成两部分，使两部分的类间方差取最大值、即分离性最大。
设图像的灰度范围为{o ，1，…，l 一l}，选择阈值t 将图像划分为两类：0C ：{o ，1，…，t}，1C {t+1，t+2，…，l —1}。对图像直方图归一化，且有概率分
布：
i i p n =/N ,i p ≥0, 1
01l i i p -==∑,
其中N 为总像素数，i n 为灰度为i 的像素数。0C 类和1C 类的类出现概率及均
值分别为：
000
()()t
r i i w P C p w t ====∑,
1111()1()t r i i t w P C p w t -=+==
=-∑。
令000/()/()t i i ip w t w t μμ===∑，1111()/1()l T i i t t ip w w t μμμ-=+-==
-∑，其中0()t i i w t p ==∑，0()t i i t ip μ==∑，10l T i i ip μ-==∑。
可以验证有下式成立：
0011T w w μμμ+=，011w w +=。
0C 和1C 类的方差分别为220000()/t i i i p w σμ==-∑，1
221111()/t i i t i p w σμ-=+=-∑。两类的类间方差2B σ为222200110110()()()B T T w w w w σμμμμμμ=-+-=-。
最佳阈值*t 应使类间方差最大，即
*201
B t l t Arg Max σ≤≤-= Otsu 最多用于双阈值分割，这是因为当阈值很多时，基于一维直方图的类间方差公式不再适用。将Otsu 法用于双阈值分割时，最佳阈值*t 应使三类间方差最大，即
2222001122()()()B T T T w w w σμμμμμμ=-+-+-
4.2 Otsu 阈值分割的遗传算法设计
（1）染色体的编码
通过编码将决策变量表示成串结构数据,采用最常用的二进制编码方案。由于图像灰度值在0～255之间，故可用00000000～11111111之间的一个八位二进制代码表示一个分割阈值。对于一维Otsu 分割,染色体串长为10,其中前八位为阈值的二进制编码，后两位为阈值真值和适应度。
（2）初始群体
采用逐个产生初始群体的方法，若产生一个不满足约束条件，则被淘汰，重新产生。直到产生popsize 个满足约束条件的初始群体为止。一维Otsu 法分割设置初始群体的个数为20。
（3）解码 对二进制染色体数组采用公式1max min min 11(2)2
l l i l i U U k U b --=-=+??
∑，min 0U =，max 255U =，某一个体K 的二进制编码为1221l l l bb b b b --Λ。
（4）适应度函数
遗传算法的执行过程中，每一代有许多不同的染色体同时存在，确定这些染色体中哪些遗传到下一代，是根据群体中各个个体的适应度大小决定的。适应度的大小是通过计算适应度函数的值，这个值称为适应度。适应度函数通常是根据 目标函数确定的，一维Otsu 法的类间方差函数就是所求目标函数，由于所求问题为最大值且为非负因此适应度函数可以直接等于目标函数。
（5）遗传算子和参数设定
主要的遗传算子有选择、交叉、变异3种。
①选择算子：先采用最优保存策略，然后采用赌轮法（比例选择）。
②交叉算子：它是遗传算法区别于其它进化算法的重要特征，是产生新个体的主要方法。交叉算子的设计和实现与所研究的问题密切相关，它决定了遗传算法的全局搜索能力。一般要求它既不要太多地破坏个体编码串中优良模式，又要能够有效地产生出一些较好的新个体模式。对一维Otsu 阈值分割法的染色体采用单点交叉的方式。分别在变量s ，t 的编码段内设定一个交叉点。
③变异算子：只是产生新个体的辅助方法，但它决定了遗传算法的局部搜索能力。在反复的试验时，发现基本位变异对结果的影响微乎其微，而一旦增大变异概率，算法又近似于随机搜索算法。所以采用下面的变异策略，把进化过程分为初期、中期和后期三个阶段，分别采用不同的变异方法。进化初期以小的概率1m P 在稍大的范围内变异，维持多样性而又不破坏好的模式；进化中期以稍大的
概率2m P 在中等的范围内变异，算法开始收敛；进化后期以大的概率3m P 在小的范围内变异,增加局部搜索能力。
(6)终止准则
设定停机准则为在达到最大进化代数50代之前，若当前群体的平均适应度值与上一代群体的平均适应度值与上一代群体的平均适应度的比值范围 为[1.000,1.005],则跳出循环。
(7)结果处理
由于在实际图像处理中。GA 寻优的解可能是最优解也可能是准最优解（即与最优解相差10%左右）。对于一个有256级灰度的图像，其准最优阈值与最优阈值的差值一般在25.5左右。为了适应不同图像的阈值选取，设定一个波动阈值A=25,在求出的阈值k 的基础上,在范围[k-A,k+A]内进行局部搜索,以求得最佳阈值。
下面是原图及用最大类间方差法(Otsu )分割的图像对比：
论文 题目：遗传应用算法 院系：计算机工程系 专业：网络工程 班级学号： 学生姓名： 2014年10月23日
摘要: 遗传算法是基于自然界生物进化基本法则而发展起来的一类新算法。本文在简要介绍遗传算法的起源与发展、算法原理的基础上,对算法在优化、拟合与校正、结构分析与图谱解析、变量选择、与其他算法的联用等方面的应用进行了综述。该算法由于无需体系的先验知识,是一种全局最优化方法,能有效地处理复杂的非线性问题,因此有着广阔的应用前景。 关键词: 遗传算法; 化学计量学; 优化 THEORY AND APPL ICATION OF GENETIC AL GORITHM ABSTRACT: Genetic Algo rithm( GA) is a kind of recursive computational procedure based on the simulation of principle principles of evaluati on of living organisms in nature1Based on brief int roduction of the principle ,the beginning and development of the algorithms ,the pape r reviewed its applications in the fields of optimization ,fitting an d calibration,structure analysis and spectra interpretation variable selection ,and it s usage in combination with othersThe application o f GA needs no initiating knowledge of the system ,and therefore is a comprehensive optimization method with extensive application in terms of processing complex nonlinear problems。 KEY WORDS : Genetic Algorithm( GA) Chemometrics Optimization 遗传算法是在模拟自然界生物遗传进化过程中形成的一种自适应优化的概率搜索算法，它于1962年被提出，直到1989年才最终形成基本框架。遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机化搜索算法, 由美国J. H. Ho llad教授提出, 其主要特点是群体搜索策略和群体中个体之间的信息交换。该算法尤其适用于处理传统搜索方法难以解决的复杂和非线性问题, 可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。 顾名思义,遗传算法(Genetic Algorithm ,GA)是模拟自然界生物进化机制的一种算法 ,即遵循适者生存、优胜劣汰的法则 ,也就是寻优过程中有用的保留 ,无用的则去除。在科学和生产实践中表现为 ,在所有可能的解决方法中找出最符合该问题所要求的条件的解决方法 ,即找出一个最优解。这种算法是 1960 年由
遗传算法入门到掌握 读完这个讲义，你将基本掌握遗传算法，要有耐心看完。 想了很久，应该用一个怎么样的例子带领大家走进遗传算法的神奇世界呢？遗传算法的有趣应用很多，诸如寻路问题，8数码问题，囚犯困境，动作控制，找圆心问题（这是一个国外网友的建议：在一个不规则的多边形中，寻找一个包含在该多边形内的最大圆圈的圆心。），TSP问题（在以后的章节里面将做详细介绍。），生产调度问题，人工生命模拟等。直到最后看到一个非常有趣的比喻，觉得由此引出的袋鼠跳问题（暂且这么叫它吧），既有趣直观又直达遗传算法的本质，确实非常适合作为初学者入门的例子。这一章将告诉读者，我们怎么让袋鼠跳到珠穆朗玛峰上去(如果它没有过早被冻坏的话)。 问题的提出与解决方案 让我们先来考虑考虑下面这个问题的解决办法。 已知一元函数： 图2-1 现在要求在既定的区间内找出函数的最大值。函数图像如图2-1所示。 极大值、最大值、局部最优解、全局最优解
在解决上面提出的问题之前我们有必要先澄清几个以后将常常会碰到的概念：极大值、最大值、局部最优解、全局最优解。学过高中数学的人都知道极大值在一个小邻域里面左边的函数值递增，右边的函数值递减，在图2.1里面的表现就是一个“山峰”。当然，在图上有很多个“山峰”，所以这个函数有很多个极大值。而对于一个函数来说，最大值就是在所有极大值当中，最大的那个。所以极大值具有局部性，而最大值则具有全局性。 因为遗传算法中每一条染色体，对应着遗传算法的一个解决方案，一般我们用适应性函数（fitness function）来衡量这个解决方案的优劣。所以从一个基因组到其解的适应度形成一个映射。所以也可以把遗传算法的过程看作是一个在多元函数里面求最优解的过程。在这个多维曲面里面也有数不清的“山峰”，而这些最优解所对应的就是局部最优解。而其中也会有一个“山峰”的海拔最高的，那么这个就是全局最优解。而遗传算法的任务就是尽量爬到最高峰，而不是陷落在一些小山峰。（另外，值得注意的是遗传算法不一定要找“最高的山峰”，如果问题的适应度评价越小越好的话，那么全局最优解就是函数的最小值，对应的，遗传算法所要找的就是“最深的谷底”）如果至今你还不太理解的话，那么你先往下看。本章的示例程序将会非常形象的表现出这个情景。 “袋鼠跳”问题 既然我们把函数曲线理解成一个一个山峰和山谷组成的山脉。那么我们可以设想所得到的每一个解就是一只袋鼠，我们希望它们不断的向着更高处跳去，直到跳到最高的山峰（尽管袋鼠本身不见得愿意那么做）。所以求最大值的过程就转化成一个“袋鼠跳”的过程。下面介绍介绍“袋鼠跳”的几种方式。 爬山法、模拟退火和遗传算法 解决寻找最大值问题的几种常见的算法： 1. 爬山法（最速上升爬山法）： 从搜索空间中随机产生邻近的点，从中选择对应解最优的个体，替换原来的个体，不断重复上述过程。因为只对“邻近”的点作比较，所以目光比较“短浅”，常常只能收敛到离开初始位置比较近的局部最优解上面。对于存在很多局部最优点的问题，通过一个简单的迭代找出全局最优解的机会非常渺茫。（在爬山法中，袋鼠最有希望到达最靠近它出发点的山顶，但不能保证该山顶是珠穆朗玛峰，或者是一个非常高的山峰。因为一路上它只顾上坡，没有下坡。） 2. 模拟退火： 这个方法来自金属热加工过程的启发。在金属热加工过程中，当金属的温度超过它的熔点（Melting Point）时，原子就会激烈地随机运动。与所有的其它的物理系统相类似，原子的这种运动趋向于寻找其能量的极小状态。在这个能量的变
遗传算法 遗传算法（Genetic Algorithm）是基于进化论的原理发展起来的一种广为应用，高效的随机搜索与优化的方法。它从一组随机产生的初始解称为“种群”，开始搜索过程。种群中的每个个体是问题的一个解，成为“染色体”是一串符号。这些染色体在每一代中用“适应度”来测量染色体的好坏, 通过选择、交叉、变异运算形成下一代。选择的原则是适应度越高,被选中的概率越大。适应度越低，被淘汰的概率越大。每一代都保持种群大小是常数。经过若干代之后，算法收敛于最好的染色体，它很可能是问题的最优解或次优解。这一系列过程正好体现了生物界优胜劣汰的自然规律。 比如有编号为1到10的特征，现在要选取其中的5个，基于遗传算法的特征选择可以如下这样直观的理解： 下续（表格） 下续……
即设有4个不同的初始特征组合，分别计算判别值，然后取最大的2个组合（[1,2,3,4,9]和[1,3,5,7,8]）进行杂交，即互换部分相异的特征（4和7），得到新的两个特征组合（[1,2,3,7,9]和[1,3,4,5,8]）,然后再计算这两个新的组合的判别值，和原来的放在一起，再从中选择2个具有最大判别值的组合进行杂交。如此循环下去，在某一代的时候就得到了一个最好的特征组合（比如第2代的[1,3,5,7,9]的特征组合）。当然，在实际中每代的个体和杂交的数量是比较大的。 遗传算法的具体的步骤如下：
1.编码：把所需要选择的特征进行编号，每一个特征就是一个基因，一个解就是一串基因的组合。为了减少组合数量，在图像中进行分块（比如5*5大小的块），然后再把每一块看成一个基因进行组合优化的计算。每个解的基因数量是要通过实验确定的。 2.初始群体（population）的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体。N个个体，构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。这个参数N需要根据问题的规模而确定。 3.交换(crossover)：交换（也叫杂交）操作是遗传算法中最主要的遗传操作。由交换概率( P)挑选的每两个父代 c 通过将相异的部分基因进行交换（如果交换全部相异的就变成了对方而没什么意义），从而产生新的个体。可以得到新一代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。 4.适应度值(fitness)评估检测：计算交换产生的新个体的适应度。适应度用来度量种群中个体优劣（符合条件的程度）的指标值，这里的适应度就是特征组合的判据的值。这个判据的选取是GA的关键所在。
摘要 随着科学技术和社会信息技术的不断提高，计算机科学的日渐成熟，其强大的功能已为人们深刻认识，它在人类社会的各个领域发挥着越来越重要的作用，给人们的生活带来了极大的便利，成为推动社会发展的首要技术动力。排课是学校教学管理中十分重要、又相当复杂的工作之一。解决好教学工作中的排课问题对整个教学计划的进行，有着十分重要的意义。首先对排课的已有算法作了相关的调查研究，决定采用遗传算法。通过设计实现基于遗传算法的自动排课系统，研究了遗传算法在排课系统中的应用。 关键词：遗传算法、自动排课、Java。
Abstract Along with science technical and community information technical increases continuously, calculator science is gradually mature, its mighty function has behaved deep cognition, and it has entered the human social each realm erupts to flick the more and more important function, bringing our life biggest of convenience. Curriculum arrangement is an important and complicated working in school,so solving the problem is of great importance for teaching programming.Investigated and studied the algorithm existed, determine that adoptgenetic algorithm. ThroughDesign Implementation theAuto CourseArrangementManagement System Base onGenetic Algorithm, researched the application of genetic algorithmin theCourseArrangementManagement System. Keywords: Genetic Algorithm Auto Course Arrangement ManagementJava.
论文 题目：遗传算法应用 院系：计算机工程系 专业：网络工程 班级学号：112055126 学生姓名：崔小杰 2014年10月23日
内容摘要 图像分割就是指把图像分成各具特性的区域并提取出感兴趣目标的技术和过程。图像的分割是以灰度值作为分割的依据,通过各个像素的灰度值和事先确定的阈值的比较来分割图像。如何确定最合适的阈值是处理好图像分割的关键,这自然成为一直以来分割算法研究的焦点。 遗传算法是对生物进化论中自然选择和遗传学机理中生物进化过程的模拟来计算最优解的方法。遗传算法具有众多的优点,如鲁棒性、并行性、自适应性和快速收敛,可以应用在图像处理技术领域中图像分割技术来确定分割阈值。 本文主要介绍基于遗传算法的最小误差阈值法、最大类间方差法（Otsu法）以及最佳直方图熵法(KSW熵法)等三种方法分割图像。 关键词：图像分割，遗传算法，阈值分割
目录 第一章绪论 .................................................. - 1 - 第二章遗传算法概述 ........................................ . - 1 - 2.1遗传算法的研究历史....................................... - 1 - 2.2生物背景................................................. - 2 - 2.3遗传算法的基本思想....................................... - 2 - 2.4遗传算法的几个概念....................................... - 2 - 2.4.1适应度函数......................................... - 2 - 2.4.2遗传算法最常用的算子............................... - 3 - 2.5遗传算法运算的基本流程 (4) 第三章图像分割的现状 ........................................ - 4 - 3.1图像分割简介............................................. - 4 - 3.2图像分割方法............................................. - 5 - 3.2.1基于边缘检测的分割 (6) 3.2.2基于区域的分割..................................... - 5 - 3.2.3边缘与区域相结合的分割............................. - 5 - 3.3阈值选取................................................. - 6 - 第四章基于新的遗传算法的图像分割 ............................ - 6 - 4.1混沌遗传算法............................................. - 6 - 4.2量子遗传算法............................................. - 6 - 4.3免疫遗传算法............................................. - 6 - 结论 ........................................................... - 7 - 参考文献: ...................................................... - 7 -
实验十遗传算法与优化问题 一、问题背景与实验目的 遗传算法（Genetic Algorithm—GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975年首先提出的．遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位． 本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题，使读者能够学会利用遗传算法进行初步的优化计算．1．遗传算法的基本原理 遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程．它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体．这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代．后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程．群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解．值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要（目前生物界对此学说尚有争议）． （1）遗传算法中的生物遗传学概念 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念． 首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系．这些概念如下： 序号遗传学概念遗传算法概念数学概念 1 个体要处理的基本对象、结构也就是可行解 2 群体个体的集合被选定的一组可行解 3 染色体个体的表现形式可行解的编码 4 基因染色体中的元素编码中的元素 5 基因位某一基因在染色体中的位置元素在编码中的位置 6 适应值个体对于环境的适应程度， 或在环境压力下的生存能力可行解所对应的适应函数值 7 种群被选定的一组染色体或个体根据入选概率定出的一组 可行解 8 选择从群体中选择优胜的个体， 淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解 9 交叉一组染色体上对应基因段的 交换根据交叉原则产生的一组新解 10 交叉概率染色体对应基因段交换的概 率（可能性大小）闭区间[0,1]上的一个值，一般为0.65~0.90 11 变异染色体水平上基因变化编码的某些元素被改变
遗传算法的特点及其应用 上海复旦大学附属中学张宁 目录 【关键词】 【摘要】 【正文】 §1遗传算法的基本概念 §2简单的遗传算法 1．选择 2．交换 3．变异 §3简单的遗传算法运算示例 1．计算机公司的经营策略优化问题 2．函数优化问题 §4遗传算法应用举例 1．子集和问题 2．TSP（旅行商）问题 §5结束语 【附录】 1．子集和问题源程序 2．TSP（旅行商）问题源程序 【参考文献】
【关键词】 遗传算法遗传变异染色体基因群体 【摘要】 遗传算法是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它根据适者生存，优胜劣汰等自然进化规则来进行搜索计算和问题求解。 文章的第一部分介绍了遗传算法的基本概念。第二部分介绍了遗传算法的原理以及三种运算：选择、交换、变异。第三部分着重介绍三种运算的具体实现，以及简单实例，主要体现遗传算法的实现过程。第四部分介绍了两个具体问题，都是属于NP-完全问题，如何用遗传算法来解决，以及实现时的一些基本问题。 文章在介绍遗传算法的原理以及各种运算的同时，还分析了一些应用中出现的基本问题，对于我们的解题实践有一定的指导意义。 【正文】 遗传算法作为一门新兴学科，在信息学竞赛中还未普及，但由于遗传算法对许多用传统数学难以解决或明显失效的复杂问题，特别是优化问题，提供了一个行之有效的新途径，且能够较好地解决信息学竞赛中的NP难题，因此值得我们进行深入的讨论。 要掌握遗传算法的应用技巧，就要了解它的各方面的特点。首先，让我们来了解一下什么是遗传算法。 §1遗传算法的基本概念 遗传算法（Genetic Algorithms，简称GA）是人工智能的重要新分支，是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它
北京师范大学珠海分校 本科生毕业论文（设计）开题报告
理论和实践的意义及可行性论述 (包括文献综述) 理论和实践的意义：当前，现代物流是企业继续降低物资消耗、提高劳动生产 率后的第三利润源泉。但我国物流企业的运输成本普遍偏高。其中很重要一个 原因就是对配送车辆运输路线规划不科学。要想降低运输成本，离不开对配送 路线的优化和配送车辆的合理安排。对物流配送车辆行驶路径进行优化，可以降低物流成本，节约运输时间，是提高物流经济效益的有效手段。 可行性论述：配送路径优化问题是典型的优化组合问题，具有很高的计算复杂 性。但遗传算法解决作为一种有效的全局搜索方法具有隐并行性和较强的鲁棒性，在解决非线性的大规模复杂问题上具有很好的适应性，适合于对VPR问 题进行优化求解。标准遗传算法虽然未必每次都能找到最优解，但通过对标准 遗传算法进行改进，完全可以在有限时间内对较复杂的VPR问题计算出次优 解或可行解。因此，用遗传算法来解决物流车辆调度问题还是完全可行的。 文献综述： [1]朱剑英?非经典数学方法[M].武昌：华中科技大学出版社，2001 [2]李敏强，寇纪淞，林丹，李书全?遗传算法的基本理论与应用[M].北京：科 学技术出版社，2002 [3]孙丽丽?物流配送中车辆路径算法分析与研究[D].上海：上海海事大学，2007 [4]盖杉.基于遗传算法的物流配送调度系统 [D].长春：长春理工大学，2007 [5]高运良，基于免疫遗传算法的物流配送V RP 求解[D].武汉：武汉科技大学， 2007 论文撰写过程中拟采取的方法和手段 本论文主要采用遗传算法作为解决物流配送路径优化问题的主要算法。但由于标准遗传算法具有“早熟收敛”的缺陷，有可能使算法陷入局部最优解。论文还将尝试通过把其他算法和遗传算法相结合，来有效控制早熟现象的发生。为了快速得到任意两个配送点之间的最优路线。本论文还拟采用佛洛依德 算法构造配送路线的地理数据库的方式来对路线网络进行预处理。从而减少整 个算法的时间复杂度和空间复杂度。
30维线性方程求解 摘要：非线性方程组的求解是数值计算领域中最困难的问题，大多数的数值求解算法例如牛顿法的收敛性和性能特征在很大程度上依赖于初始点。但是对于很多高维的非线性方程组，选择好的初始点是一件非常困难的事情。本文采用了遗传算法的思想，提出了一种用于求解非线性方程组的混合遗传算法。该混合算法充分发挥了遗传算法的群体搜索和全局收敛性。选择了几个典型非线性方程组，考察它们的最适宜解。 关键词：非线性方程组；混合遗传算法；优化 1. 引言遗传算法是一种通用搜索算法，它基于自然选择机制和自然遗传规律来模拟自然界的进化过程，从而演化出解决问题的最优方法。它将适者生存、结构化但同时又是 随机的信息交换以及算法设计人的创造才能结合起来，形成一种独特的搜索算法，把一些解决方案用一定的方式来表示，放在一起成为群体。每一个方案的优劣程度即为适应性，根据自然界进化“优胜劣汰”的原则，逐步产生它们的后代，使后代具有更强的适应性，这样不断演化下去，就能得到更优解决方案。 随着现代自然科学和技术的发展，以及新学科、新领域的出现，非线性科学在工农业、经济政治、科学研究方面逐渐占有极其重要的位置。在理论研究和应用实践中，几乎绝大多数的问题都最终能化为方程或方程组，或者说，都离不开方程和方程组的求解。因此，在非线性问题中尤以非线性方程和非线性方程组的求解最为基本和重要。传统的解决方法，如简单迭代法、牛顿法、割线法、延拓法、搜索法、梯度法、共轭方向法、变尺度法，无论从算法的选择还是算法本身的构造都与所要解决的问题的特性有很大的关系。很多情况下,算法中算子的构造及其有效性成为我们解决问题的巨大障碍。而遗传算法无需过多地考虑问题的具体形式，因为它是一种灵活的自适应算法，尤其在一些非线性方程组没有精确解的时候，遗传算法显得更为有效。而且，遗传算法是一种高度并行的算法，且算法结构简单，非常便于在计算机上实现。本文所研究的正是将遗传算法应用于求解非线性方程组的问题。 2. 遗传算法解非线性方程组为了直观地观察用遗传算法求解非线性方程组的效果，我们这里用代数非线性方程组作为求解的对象问题描述：非线性方程组指的是有n 个变量（为了简化讨论，这里只讨论实变量方程组）的方程组 中含有非线性方程。其求解是指在其定义域内找出一组数能满足方程组中的每 个方程。这里，我们将方程组转化为一个函数则求解方程组就转化为求一组值使得成立。即求使函数取得最小值0 的一组数，于是方程组求解问题就转变为函数优化问题 3. 遗传算子 遗传算子设计包括交叉算子、变异算子和选择算子的设计。
遗传算法经典学习Matlab代码 遗传算法实例: 也是自己找来的，原代码有少许错误，本人都已更正了，调试运行都通过了的。 对于初学者，尤其是还没有编程经验的非常有用的一个文件 遗传算法实例 % 下面举例说明遗传算法 % % 求下列函数的最大值 % % f(x)=10*sin(5x)+7*cos(4x) x∈[0,10] % % 将 x 的值用一个10位的二值形式表示为二值问题，一个10位的二值数提供的分辨率是每为 (10-0)/(2^10-1)≈0.01。 % % 将变量域 [0,10] 离散化为二值域 [0,1023], x=0+10*b/1023, 其 中 b 是 [0,1023] 中的一个二值数。 % % % %--------------------------------------------------------------------------------------------------------------% %--------------------------------------------------------------------------------------------------------------% % 编程 %----------------------------------------------- % 2.1初始化(编码) % initpop.m函数的功能是实现群体的初始化，popsize表示群体的大小，chromlength表示染色体的长度(二值数的长度)，
% 长度大小取决于变量的二进制编码的长度(在本例中取10位)。 %遗传算法子程序 %Name: initpop.m %初始化 function pop=initpop(popsize,chromlength) pop=round(rand(popsize,chromlength)); % rand随机产生每个单元 为 {0,1} 行数为popsize，列数为chromlength的矩阵， % roud对矩阵的每个单元进行圆整。这样产生的初始种群。 % 2.2 计算目标函数值 % 2.2.1 将二进制数转化为十进制数(1) %遗传算法子程序 %Name: decodebinary.m %产生 [2^n 2^(n-1) ... 1] 的行向量，然后求和，将二进制转化为十进制function pop2=decodebinary(pop) [px,py]=size(pop); %求pop行和列数 for i=1:py pop1(:,i)=2.^(py-i).*pop(:,i); end pop2=sum(pop1,2); %求pop1的每行之和 % 2.2.2 将二进制编码转化为十进制数(2) % decodechrom.m函数的功能是将染色体(或二进制编码)转换为十进制，参数spoint表示待解码的二进制串的起始位置
本科生毕业设计(论文) 论文题目：基于遗传算法的PID参数优化
毕业设计（论文）原创性声明和使用授权说明 原创性声明 本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。 作者签名：日期： 指导教师签名：日期： 使用授权说明 本人完全了解大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。 作者签名：日期：
学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 涉密论文按学校规定处理。 作者签名：日期：年月日 导师签名：日期：年月日
安徽大学 遗传算法期末小论文 题目：遗传算法的原理及其发展应用前景 学生姓名：朱邵成学号：Z15201030 院（系）：电气工程与自动化学院专业：模式识别教师姓名：吴燕玲 教师所在单位：安徽大学电气工程与自动化学院 完成时间：2016年6月
生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。 遗传算法的概念最早是由Bagley J.D在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由Michigan大学的J.H.Holland所实行。当时，其主要目的是说明自然和人工系统的自适应过程。遗传算法简称GA(Genetic Algorithm)，在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。 一、遗传算法的基本概念 遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。Darwin 进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下： 一、串(String) 它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。 二、群体(Population) 个体的集合称为群体，串是群体的元素 三、群体大小(Population Size) 在群体中个体的数量称为群体的大小。 四、基因(Gene) 基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。 五、基因位置(Gene Position) 一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。 六、基因特征值(Gene Feature) 在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。 七、串结构空间SS 在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。 八、参数空间SP
学校代码 10126 学号 00708037 分类号密级 本科毕业论文 基于遗传算法的图像阈值分割 学院、系数学科学学院计算数学系 专业名称信息与计算科学 年级 2007级 学生姓名刘家祥 指导教师曹军 2011年 5月 20 日
内容摘要 图像分割就是指把图像分成各具特性的区域并提取出感兴趣目标的技术和过程。图像的分割是以灰度值作为分割的依据,通过各个像素的灰度值和事先确定的阈值的比较来分割图像。如何确定最合适的阈值是处理好图像分割的关键,这自然成为一直以来分割算法研究的焦点。 遗传算法是对生物进化论中自然选择和遗传学机理中生物进化过程的模拟来计算最优解的方法。遗传算法具有众多的优点,如鲁棒性、并行性、自适应性和快速收敛,可以应用在图像处理技术领域中图像分割技术来确定分割阈值。 本文主要介绍基于遗传算法的最小误差阈值法、最大类间方差法（Otsu法）以及最佳直方图熵法(KSW熵法)等三种方法分割图像。 关键词：图像分割，遗传算法，阈值分割
Abstract Image segmentation refers to the image into regions each with characteristics and goals of the technology to extract and process of interest. Segmentation is a segmentation based on gray value, gray value of each pixel through the predetermined threshold value and comparing the image segmentation. How to determine the most appropriate threshold is the key to handling image segmentation, which has naturally become the focus of segmentation algorithms. Genetic algorithm is a biological theory of evolution and genetic mechanism of natural selection in biological evolution simulation method to calculate the optimal solution. Genetic algorithm has many advantages, such as robustness, parallel, adaptive, and fast convergence, can be used in the field of image processing image segmentation technique to determine the split threshold. In this paper, genetic algorithm based on minimum error threshold, the largest class variance (Otsu method) and the best histogram entropy (KSW entropy method) are three ways to split the image. Keywords : Image segmentation, genetic algorithms, threshold
遗传算法总结 遗传算法是借鉴生物的自然选择和遗传进化机制而开发出的一种全局自适应概率搜索算法。 一、遗传算法流程图 算法开始 原问题参数集 染色体编码，产生初始种群 计算种群中个体的适应值 终止条件判断 N 选择 交叉 Y 变异 新种群 输出结果 算法结束 图1 遗传算法流程图 二、遗传算法的原理和方法 1）染色体编码 把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法就称为编码。
De Jong 曾提出了两条操作性较强的实用编码原则：编码原则一：应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案；编码原则二：应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案。 编码方法主要有以下几种：二进制编码方法、格雷码编码方法、浮点数编码方法、符号编码方法、参数级联编码方法、多参数交叉编码方法。 2） 适应值计算 由解空间中某一点的目标函数值()f x 到搜索空间中对应个体的适应度函数值 (())Fit f x 的转换方法基本上有一下三种： a ． 直接以待解的目标函数值()f x 转化为适应度函数值(())Fit f x ，令 () (())=() f x Fit f x f x ?? -?目标函数为最大化函数 目标函数为最小化函数 b ． 对于最小值的问题，做下列转化max max () () (())0 C f x f x C Fit f x -
最新发布的MA TLAB 7.0 Release 14已经包含了一个专门设计的遗传算法与直接搜索工具箱（Genetic Algorithm and Direct Search Toolbox，GADS）。使用遗传算法与直接搜索工具箱，可以扩展MATLAB及其优化工具箱在处理优化问题方面的能力，可以处理传统的优化技术难以解决的问题，包括那些难以定义或不便于数学建模的问题，可以解决目标函数较复杂的问题，比如目标函数不连续、或具有高度非线性、随机性以及目标函数没有导数的情况。 本章8.1节首先介绍这个遗传算法与直接搜索工具箱，其余各节分别介绍该工具箱中的遗传算法工具及其使用方法。 8.1 遗传算法与直接搜索工具箱概述 本节介绍MATLAB的GADS（遗传算法与直接搜索）工具箱的特点、图形用户界面及运行要求，解释如何编写待优化函数的M文件，且通过举例加以阐明。 8.1.1 工具箱的特点 GADS工具箱是一系列函数的集合，它们扩展了优化工具箱和MA TLAB数值计算环境的性能。遗传算法与直接搜索工具箱包含了要使用遗传算法和直接搜索算法来求解优化问题的一些例程。这些算法使我们能够求解那些标准优化工具箱范围之外的各种优化问题。所有工具箱函数都是MATLAB的M文件，这些文件由实现特定优化算法的MATLAB语句所写成。 使用语句 type function_name 就可以看到这些函数的MATLAB代码。我们也可以通过编写自己的M文件来实现来扩展遗传算法和直接搜索工具箱的性能，也可以将该工具箱与MATLAB的其他工具箱或Simulink结合使用，来求解优化问题。 工具箱函数可以通过图形界面或MA TLAB命令行来访问，它们是用MATLAB语言编写的，对用户开放，因此可以查看算法、修改源代码或生成用户函数。 遗传算法与直接搜索工具箱可以帮助我们求解那些不易用传统方法解决的问题，譬如表查找问题等。 遗传算法与直接搜索工具箱有一个精心设计的图形用户界面，可以帮助我们直观、方便、快速地求解最优化问题。 8.1.1.1 功能特点 遗传算法与直接搜索工具箱的功能特点如下： 图形用户界面和命令行函数可用来快速地描述问题、设置算法选项以及监控进程。 具有多个选项的遗传算法工具可用于问题创建、适应度计算、选择、交叉和变异。 直接搜索工具实现了一种模式搜索方法，其选项可用于定义网格尺寸、表决方法和搜索方法。 遗传算法与直接搜索工具箱函数可与MATLAB的优化工具箱或其他的MATLAB程序结合使用。 支持自动的M代码生成。 8.1.1.2 图形用户界面和命令行函数 遗传算法工具函数可以通过命令行和图形用户界面来使用遗传算法。直接搜索工具函数也可以通过命令行和图形用户界面来进行访问。图形用户界面可用来快速地定义问题、设置算法选项、对优化问题进行详细定义。 133
数学建模论文 基本遗传算法的 MATLAB实现 一、问题的提出 遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，它借鉴了达尔文的进化论和孟德尔的进化学说。其本质是一种高效、并行、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应的控制过程以求的最优解。遗传算法操作使用适者生存的原则，在潜在的解决方案中逐次产生一个近似最优方案。在遗传算法的每一代中，根据个体在问题域中的适应度值和从自然遗传中借鉴来的再造方法进行个体选择，产生一个新的近似解。这个过程导致种群中个体的进化，得到新个体比原来个体更适应环境，就像自然界中的改造一样。 基本遗传算法，最重要的是产生随机数的过程，已知目标函数max f(x1,x2)=21.5+x1*sin(4*pi*x1)+x2*sin(20*pi*x2) 其中约束条件为： -3.0<=x1<=12.1 4.1<=x2<= 5.8 编程用matlab实现基本遗传算法。 二、问题的分析与模型的建立： 遗传算法是一种基于生物进化原理构想出来的搜索最优解的仿真算法，它模拟基因重组与进化的自然过程，把待解决问题的参数编成二进制码或十进制码即基因，若干基因组成一个染色体个体许多染色体进行类似于自然选择配对交叉和变异的运算，经过多次重复迭代直到得到最后的优化结果。习惯上，适应度值越大，表示解的质量越好。对于求解最小值问题，可通过变换转为求解最大值问题。遗传算法以群体为基础，不以单点搜索为基础，能同时从不同点获得多具极值，因此不易陷入局部最优；遗传算法是对问题变量的编码集进行操作，而不是变量本身，有效地避免了对变量的微分操作运算；遗传算法只是利用目标函数来区别群体中的个体好坏而不必对其进行过多的附加操作。 基本遗传算法 定义：基本遗传算法是一种群体型操作，该操作以群体中的所有个体为对象只使