遗传算法-课外参阅资料.doc

遗传算法简介
遗传算法（Genetic Algorithm）起始于20世纪60年代，主要由美国Michigan大学的John Holland与其同事和学生研究形成了一个较完整的理论和方法。从1985年在美国卡耐基梅隆大学召开的第5届目标遗传算法会议（Intertional Conference on Genetic Algorithms:ICGA’85）到1997年5月IEEE的Transaction on Evolutionary Computation创刊，遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究逐渐成熟。
1.1遗传算法的产生与发展（略）
1.2遗传算法概要
1.2.1生物进化理论和遗传算法的知识
遗传：
变异：亲代和子代之间，子代和子代的不同个体之间总有些差异，这种现象称为变异，变异是随即发生的，变异的选择和积累是生命多样性的根源
生存斗争和适者生存：
下面给出生物学的几个基本概念知识，这对于理解遗传算法很重要。
染色体：是生物细胞中含有的一种微小的丝状化合物，是遗传物质的主要载体，由多个遗传因子—基因组成。
遗传因子（gene）:DNA长链结构中占有一定位置的基本遗传单位，也称基因。生物的基因根据物种的不同而多少不一。
个体（individual）:指染色体带有特征的实体
种群（population）:染色体带有特征的个体的集合
进化（evolution）;生物在其延续生命的过程中，逐渐适应其生存环境使得其品质不断得到改良，这种生命现象称为进化。生物的进化是以种群的形式进行的。
适应度（fitness）:度量某个物种对于生存环境的适应程度
选择（selection）:指以一定的概率从种群中选择若干个体的操作
复制(reproduction)
交叉(crossorer)
变异（musation）：复制时很小的概率产生的某些复制差错
编码（coding）:DNA中遗传信息在一个长链上按一定的模式排列，也即进行了遗传编码。遗传编码可以看成是从表现型到遗传子型的映射。
解码（decoding）：从遗传子型到表现型的映射
1.2.2 遗传算法的基本思想
遗传算法是从代表问题可能潜在解集的一个种群开始的。该种群是由经过基因编码的一定数目的个体组成，这需要实现从表现型到基因型的映射即编码。初代种群产生之后，按照适者生存、优胜略汰的原理，逐代进化产生出越来越好的近似种，即在每一代中，根据问题域中个体适应度大小挑选个体，并借助自然遗传学的遗传算子进行组合交叉和变异，产生出代表解的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码可以作为问题近似最优解。
采用多种群即有子种群的算法往往会获得更好的结果。每个子种群像单种群遗传算法一样独立地演算若干代后，在子种群之间进行个体交换。这种多种群遗传算法更加贴近于自然界中种族的进化，称为并行遗传算法。
1.2.3遗传算法的特点
* 自组织，自学习，自适应性
* 本质并行性
*不需要求导或其他辅助知识，而只要影响搜索方向的目标函数和相应的适应度函数
*强调概率转换规则，而不是确定的转换规则
*对给定问题可产生许多的潜存种，最终选择可以由使用者确定，因此对于确认可替代解集而言是特别适合的。（如多目标优化问题）
1.3遗传算法的基本操作
遗传算法包括三个基本操作：选择，交叉（基因重组），变异
这些基本操又有许多不同的地方。
1. 选择
按比例的适应度算法（proportional fitness assigment）
基于排序的适应度算法（rank-based fitness assignment）
轮盘赌选择（roulette wheel selection）
随机遍历抽样（stochastic universal sampling）
局部选择（lacal selection）
截断选择（tournament selection）
2. 交叉或基因重组（crossorer/recombination）
*实值重组（real value recombination）
离散重组（discrete ）、中间(intermediate)重组、线性(linear)重组、扩展线性(extended linear)重组
* 二进制交叉（binary valuel crossorer）
单点交叉、多点（multiple-poinrt）交叉、均匀(uniform)
交叉、洗牌(shuffle)交叉、缩小代理(crossover with reduced surrogate)
3. 变异（mutation）
变异实质上是子代基因按小概率扰动产生的变化，有两种算法，分别为实值变异和二进制变异
第二章 基本遗传算法
2.1 一个简单的遗传算法实例
本节介绍一个简单的实例，来考察一下二进制算法的轮盘赌选择、多点交叉和变异操作，以便对遗传算法的基本过程和基本操作有所了解。
表1是一组二进制基因构成的个体组成的初始种群，个体适应度是由某种算法计算得到的。适应度越大代表这个个体越好。这里为了能够符合优胜略汰的原则，个体适应度按照比例转化为选择概率，进而得到累积概率

个体

染色体li
适应度hi
（）
选择概率

累计概率

1
0001100000
8
0.086954
0.086957
2
0101111001
5
0.054348
0.141304
3
0000000101
2
0.021739
0.163043
4
1001110100
10
0.108696
0.271739
5
1010101010
7
0.076087
0.347826
6
1110010110
12
0.130435
0.478261
7
1001011011
5
0.054348
0.532609
8
1100000001
19
0.206522
0.739130
9
1001110100
10
0.108696
0.847826
10
0001010011
14
0.152174
1.000000
表1
轮盘赌选择方法类似于博彩游戏中的轮盘赌，将轮盘分成10个（即种群个体数目）扇区，并进行10次选择，从而产生10个[0,1]之间的随机书，图1的尖头表示被选中的染色体。

图1 轮盘赌选择
1到10代表染色体个体序号，扇区大小表示染色体选择概率的大小
假设产生的随机数序列为0.070221，0.545929，0.784567，0.44693，0.507893，0.291198，0.71634，0.272901，0.371435，0.854641，将随机数序列与计算获得的累积概率比较，则依次序号为1，8，9，6，7，5，8，4，6，10个体被选中。显然适应度高的个体被选中的概率大，在第一次生存竞争中，序号为2 和3的个体被淘汰，代之以适应度高的个体8 和6，这个过程被称为再生（reproduction）
再生之后重要的遗传操作是交叉， 这里仅以单点交叉为例。任意挑选经过选择操作后种群中的两个个体（该两个个体应是不同的）作为交叉对象，随机产生一个交叉点位置，将交叉点位置之右的部分基因进行交叉，如下图2

父个体1 1100000001
父个体2 0001010011
子个体1 1100000011
子个体2 0001010001
图2 单点交叉
如果只考虑交叉操作实现进化机制，在多数情况下是不行的，这与生物界近亲繁殖影响进化历程是类似的。因为种群的个体数是有限的，经过若干代交叉操作，源于一代较好祖先的子个体逐渐充斥整个种群，这样就会出现所谓早熟或过早收敛现象。这样最后获得的个体并非真正意义上的最优种群。为避免这种现象，有必要在进化过程中加入具有新遗传基因的个体， 解决方法是模仿生物变异的遗传操作。对于二进制基因码组成的个体种群，实现基因码的小概率翻转，即可达到此目的，如图3（第四位由1翻转为0）

图3 变异
变异总是小概率的，即只有个别个体发生变异。其翻转的位置及翻转个数可以是随机的，有时也可以是固定的。

遗传算法的一般流程如图4所示

图4 基于遗传算法流程图
2.2 简单函数优化的实例
前一节所讲的实例是没有真正对象的，只是将遗传算法操作过程结合最简单的轮盘赌选择，单点交叉，单点小概率变异介绍了一下，使学生对遗传算法有一个概要了解，本节结合函数优化问题，使学生了解如何对问题实现编码和解码，如何产生初始种群，如何针对函数优化问题确定适应度函数，将遗传算法的操作全过程表示出来。
考虑下列一元函数求最大值的优化问题：

由于在[-1，2]可微，可用微分法先求出其最值：

即

解得：

式中是一列接近于0的实数递减序列。

函数的曲线
最后得到

下面我们用遗传算法解决上述函数的最优问题（即求其最大值）
（1）编码
变量x作为实数，可以视为遗传算法的表现形式。从表现型到基因型的映射称为编码。通常采用二进制编码形式将某个变量值代表的个体表示为一个[0、1]二进制串。如果设定求解精确到6 位小数，由于区间长度为2-（-1）=3，必须将闭区间[-1，2]分为3*106等份。因为 2097152=221<3*106<=222=4194304
所以编码的二进制串长至少需要22 位
① 将一个二进制串（b21b20….b0）2代表的二进制数化为10进制数：

②对应的区间[-1，2]内的实数：

串[0………0]和串[1……1]（每个里都是22个数）分别表示区间的两个端点值-1和2。
（2）产生初始种群
一个个体由串长为22的随机产生的二进制串组成染色体的基因码，我们可以产生一定数目的个体组成种群，种群的大小（规模）就是指种群中的个体数目。
（3）计算适应度
适应度大的个体其存活和被选中的概率大。适应度的计算就是对个体的计算，考虑到本例目标函数在定义域内均大于0，而且是求函数最大值，所以直接引用目标函数作为适应度函数：

例如x1=0.637197通过编码得到的二进制串是s1=[1000101110110101000111]
这个串就是个体。个体的适应度就是

这里我们选择种群数量为3 ，每个个体为：
s1=[1000101110110101000111]
s2=[0000001110000000010000]
s3=[1110000000111111000101]
分别对应于数量值x1=0.637197,x2=-0.958973,x3=1.627888,三个个体
的适应度计算如下；

显然3 个个体中S3的适应度最大，为最佳个体。
（4）遗传操作
下面是经过选择操作后的两个个体：
s2=[0000 00111000000001000]
s3=[1110 000000111111000101]
首先执行单点交叉， 随机选择一个交叉点，将之后的串交叉
=[00000 00000111111000101]
=[11100 01110000000010000]
这两个个体的适应度分别为：

可以发现的适应度比S2和S3都高。
（问题：这样选择选出种群中个体数目不是越来越少吗）
下面考察变异操作，假定已经以一小概率选择了S3的第5个遗传
因子（即第5位）变异，遗传因子是由原来的0变为1，产生新的个
体=[1110100000111111000101]，计算该个体的适应度

可见该个体的适应度比它的父个体的适应度减小了，但如果选中第10个遗传因子变异，产生新个体为=[11100000001111111000101]

又发现的适应度比其父个体的适应度改善了。这说明变异操作的“扰动”作用。
（5）模拟结果
设定种群大小为50， 交叉概率PC=0.25，变异概率Pm=0.01,按照上述的基本遗传算法，在进行到89代时获得最佳个体：
Smax=[1101001111110011001111]
Xmax=1.850549 f(xmax)=3.850274
由于数学函数优化问题不需要专门领域的知识，且能较好的反映算法本身的实际效能，所以常用于 GA的测试问题。下面四个为具有相当复杂度的常用测试函数：
1） Shubert函数

此函数有760个局部极小点，其中只有一个（-1.42513，-0.80032）为全局最小点，最小值为186.7309，自变量的取值范围-10<x,y<10。此函数极易陷入局部积小值186.34。
2） Camel函数

此函数有6个局部极小点，其中有两个（-0.0898，0.7126）和(0.0898,-0.7126)为全局最小点，最小值为-1.031628，自变量的取值范围为-100<x,y<100。
3）De Jones’s F5函数

其中。
自变量取值范围为-65535<xi<65535。此函数有多个局部极大点，一般
其函数值大于1 即可认为收敛。
4） Shsffer’s F6函数

此函数有无限个局部极大点，其中只有一个（0，0）为全局最大，最大值为1。自变量的取值范围为-100<x,y<100。此函数最大值峰值周围有一个圆脊，它们的取值均为0.990283，因此很容易停滞在此局部极大点。

2.3遗传基因型
Holland提出的遗传算法是采用二进制编码来表现个体遗传基因型的，它使用的编码符号集由二进制符号0和1组成，因此实际的遗传基因是一个二进制符号串，其优点在于编码、解码操作简单，交叉、变异等遗传操作便于实现，而且便于利用模式定理进行理论分析等。其缺点在于，不便于反映所求问题的特定知识，对于一些连续函数的优化问题，也由于遗传算法的随机特征而使得其局部搜索能力较差，对于一些多维、高精度要求的连续函数优化，二进制编码存在着连续函数离散化时的映射误差，个体编码串较短时，可能达不到精度要求；而个体编码较长时，虽然能提高精度，但却会使算法的搜索空间急剧扩大，造成遗传算法的性能降低。为提高遗传算法的局部搜索能力，后来又陆续产生了：格雷码（Gray Code）等。为改善遗传算法的计算复杂性，提高算法效率提出了浮点码和符号编码。随着生物计算理论研究的兴起，有人提出DNA编码法，并在模糊控制器优化应用中取得很好的效果。
遗传算法的进化过程是建立在编码机制基础上的，编码技术对于算法性能如搜索能力和种群多样性等影响很大，例如二进制编码搜索能力强，而种群多样性弱，浮点编码则正好相反。二进制编码的种群稳定性比浮点编码差。
浮点编码对个体的第p个基因进行变异操作
（N为高斯噪声）
可见浮点数编码操作的变量可以任意地小，这样可以保证只要变异量是足够的小，产生的新个体可以与父个体充分的接近。而二进制编码的变异操作不能保证父个体与新个体的充分接近，因此其种群稳定性比浮点差。
一个好的编码方法应具有下面9个特征：
！）完整性（completeness）原则上，分布在所有问题域的解都可能被构造出来。
2）封闭性（closure）每个基因编码对应一个可接受的个体，封闭性保证系统从不产生无效的个体。
3）紧致性（compactness）若两种基因编码g1和g2都被解码成相同的个体，若g1比g2占的空间小，就认为g1比g2紧致。
4) 可扩展性（scalability）对于具体的问题，编码的大小确定了解码的时间，两者存在一定的函数关系，若增加一种表现型，作为基因的编码大小也相应增加。
5）多重性（multiplicity）多个基因解码成一个表现型，即从基因型到相应的表现型空间是多对一的关系，这是基因的多重性。 若相同的基因型被解码成不同的表现型， 这是表现型的多重性。
6）个体可塑性（flexibility）决定表现型与相应给定基因是受环境影响的。
7）模块性（modulatity）若表现型的构成中有多个重复的结构，在基因型编码中这种重复应当是避免的。
8）冗余性（redundancy）冗余性能够提高可靠性和鲁棒性
9）复杂性（complexity）包括基因型的结构复杂性，解码复杂性，计算时空复杂性（基因解码、适应值、再生等）
以上特性有时是相矛盾的。
2.4 适应度函数及其尺度变换
遗传算法在进化搜索中基本不利用外部信息，即以适应度函数（fitness function）为依据，利用种群中每个个体的适应度值来进行搜索。因此适应度函数的选取至关重要，直接影响到遗传算法的收敛速度以及能否找到最优解。一般而言，适应度函数是由目标函数变换而成的。 对目标函数值域的某种映射变换成为适应度的尺度变换（fitness scaling）
1. 几种常见的适应度函数
① 直接以待求解的目标函数转化为适应度函数，即
若目标函数为最大化问题 Fit(f(x))=f(x)
若目标函数为最小化问题 Fit(f(x))=-f(x)
这种适应度函数简单、直观，但存在两个问题，其一是可能不满足常用的轮盘赌选择中的概率非负的要求；其二是某些待求解的函数在函数值分布上相差很大，因此得到的平均适应度可能不利于体现种群的平均性，影响算法的性能。
② 若目标函数为最小问题，则

式中为f(x)的最大值估计。
反之，则
为f(x)的最小值估计
这种方法是第一种方法的改进，称为“界限构造法”，但的构造与选择困难。
③ 若目标函数取为最小问题：

若目标函数为最大问题：

这种方法与2相似，c为目标函数界限的保守估计值
2. 适应度函数的作用
在选择操作时会出现以下问题：
① 在遗传进化的初期，通常会产生一些超常的个体，若按照比例选择法，这些异常个体因竞争力太突出而控制了选择过程，影响算法的全局优化进程。
② 在遗传进化的后期，即算法接近收敛时由于种群中个体适应度较小时，继续优化的潜能降低，可能获得某个局部最优解。
上述问题我们称为遗传算法的欺骗问题。适应度函数设计不当有可能造成这种问题的出现。
3. 适应度函数的确定
主要满足以下条件：
① 单值、连续、非负、最大化
② 合理、一致性：要求适应度值反映对应解的优劣程度，这个条件的达成往往比较难以衡量
③ 计算量小
④ 通用性强：对某些具体问题，应尽可能通用
4. 适应度函数的尺度变换
1） 线性变换法：
的确定有多种方法，但要满足以下条件：
① 原适应度的平均值要等于标定后的适应度平均值，以保证适应度为平均值的个体在下一代的期望复制数为1，即

② 变换后的适应度最大值应等于原适应度平均值的最大倍数，以控制适应度最大的个体在下一代中的复制数。试验表明，指定倍数Cmult可在1.0-2.0范围内。即根据上述条件可确定线性比例的系数：

2） 幂函数变换法：
3） 指数变换法：
这种变换法的基本思想来源于模拟退火过程（simulated annealing,SA）,其中的系数决定了复制的强制性，其值越小，复制的强度就越趋向于那些具有最大适应度的个体。

2.5 遗传操作
本节将介绍轮盘赌和二进制编码以外的其他常用的遗传操作方法，并进行比较。
1. 选择（selection ）
选择过程第一步是计算适应度。在被选中集中的每个个体具有一个选择概率，这个选择概率取决于种群中个体的适应度。下面的一些概念可以用来比较不同的选择算法。
① 选择压力（selection pressure）最佳个体选中的概率与平均选中概率的比值：
SP越接近于1 表明选择压力越小，SP恒大于等于1。
② 偏差（bias）：个体正规化适应度与其期望再生概率的绝对差值
③ 个体扩展（spread）：单个个体子代个数的范围
④ 多样化损失(loss of diverisity)：在选择阶段未选中个体数目占种群的比例
⑤ 选择强度（selection intensity）：将正规高斯分布应用于选择方法，期望平均适应度。
⑥ 选择方差（selection cariance）：将正规高斯分布应用于选择方法，期望种群适应度的方差。
个体选择概率的常用分配方法有以下两种：
① 按比例的适应度分配(proportional fitness assignment)又称为选择的蒙特卡罗法。 即利用比例于各个个体适应度的概率决定其子孙的遗留可能性。 （M为个体总数目）
下面是一个经过幂变换的蒙托卡罗个体选择概率计算表。

个体选择概率计算表
个体
f
f2
pi
1
2.5
6.25
0.18
2
1.
1.00
0.03
3
3
9.00
0.26
4
1.2
1.44
0.04
5
2.1
4.41
0.13
63
0.8
0.64
0.02
7
2.5
6.25
0.18
8
1.3
1.69
0.05
9
0.9
0.81
0.02
10
1.8
3.24
0.09

② 基于排序的适应度分配（rank-based fitness assignment）：种群按目标值进行排序。适应度仅仅取决于个体在种群中的序位， 而不是实际的目标值。排序方法克服了比例适应度计算的尺度问题，引入种群均匀尺度，提供了控制选择压力的简单有效方法。
排序方法比比例方法表现出更为有效的鲁棒性，不失为一种很好的方法。
设定N为种群大小，Pos 为个体在种群的序位，SP为选择压力，个体的适应度可以计算如下：
线性排序：

非线性排序：
其中X是下列多项式方程的根：
选择强度：
多样化损失：
选择方差：
关于个体的选择概率计算，Baker提出了线性排序的计算公式：

上式中i为个体排序序号，
Michalewicz提出了线性排序的选择概率计算公式：

上式中i为个体排序序号，c为排序第一的个体的选择概率。
下面介绍几种常用的选择方法：
（1） 轮盘赌选择法
（2） 随机遍历抽样法（staochastic universial sampling）
设定npointer 为需要选择的个体数目，等距离选择个体，选择指针的距离为1/npointer.第一个指针的位置由[0，1/pointer]区间的均匀随机数决定。随机遍历抽取法提供了零编码和最小个体扩展。
（3） 局部选择法（local selection ）
在局部选择法中，每个个体处于一个约束环境中，称为局部邻集（其他选择方法中视整个种群为个体之邻集），个体仅与其邻近个体产生交互，该邻集的定义由种群的分布结构给出，邻集可被当作潜在的交配伙伴。
首先均匀随机地选择一半交配种群，选择方法可以是随机遍历方法也可以是截断选择方法，然后对每个被选个体定义其局部邻集，在邻集内部选择交配伙伴。邻集的结构可以是以下几种：①线性邻集（整环，半环）②两对角邻集（整对角型、半对角型、整星型和半星型
(4)截断选择法（truncation selection ）
前几种选择法是自然选择法，截断选择法是人工选择法。它适合于大种群。 在截断选择法中，个体首先按适应度排序，截断选择参数叫做截断域值Trunc,取值为50%-10%.它定义为被选作父个体的百分比。在域值之下的个体不能产生子个体。通常选择强度与截断域值的关系见下表：

截断域值
1%
10%
20%
40%
50%
80%
选择强度
2.66
1.76
1.2
0.97
0.8
0.34
选择强度与截断域值的关系
选择强度：
多样化损失：
选择方差：
上式中fc为下列高斯分布的积分下限：
(5)锦标赛选择法（tournament selection）
在锦标赛选择法中，随机地从种群中挑选一定数目（Tour）个体，然后将最好的个体作为父体。这个过程重复进行完成个体的选择。锦标赛选择的参数为竞赛规模Tour,其取值范围为[2， Nind]。下表给出了竞赛规模与选择强度之间的关系。
竞赛规模
1
2
3
5
10
30
选择强度
0
0.56
0.85
1.15
1.53
2.04
选择强度：
多样化损失：
当Tour为5 时，多样化损失大约为50%
选择方差：
上述几种算法均以适应度为基础进行选择，就可能导致下列问题。
① 在种群中出现个别或极少数适应度相当高的个体，采用这种选择机制就有可能导致这些个体在种群中迅速繁殖。经过少数几次迭代后占满了种群的位置。这样一串算法的求解过程就结束了，即收敛了。 但这样很有可能是收敛到局部最优解，即遗传算法的不成熟收敛，即早熟现象出现，这是因为搜索的范围很有限。因此一般不希望有个别个体在遗传 算法运算的最初几次迭代时就在种群中占主导地位。
② 当种群中个体适应度彼此非常接近时，这些个体进入配对集的机会相当，而且交配后得到的新个体也不会有多大变化。这样，搜索过程就不能有效地进行，选择机制有可能趋向于纯粹的随机选择，从而使进化过程陷于停顿的状态，难于找到全局最优解。
针对上述问题，可以采用适应度函数适度变换的方法来解决，另外，还可以采用以下的几种提高遗传算法性能的选择算法。
1） 稳态繁殖：在迭代过程中用部分优质新子个体来更新种群中部分父个体来作为下一代种群。
2） 没有重串的稳态繁殖：在形成新一代种群时，使其中的种群均不重复。（计算时间会增大）
2. 基因交叉重组（crossorer/recombination）
基因交叉（重组）是把两个父个体的部分结构加以替换重组而形成子个体的操作，重组的目的是为了能够在下一代产生新的个体。基因重组是遗传算法新优良个体的重要手段。
（1）实值重组
①离散重组
离散重组在个体之间交换变量的值，考虑如下三个变量的个体：父个体1 12 25 5
父个体2 123 4 34
子个体中每个变量可按等概率随机的挑选父个体，例如重组之后一个子个体为：子个体1 123 4 5
子个体2 12 4 5
②中间重组：只适用于实变量
子个体1=父个体1+（父个体2-父个体1）
上的均匀随机数产生。对于中间重组d=0; 一般选择d=0.25
例1 父1 12 25 5
父2 123 4 34
样本：样本1 0.5 1.1 -0.1
样本2 0.1 0.8 0.5
子个体1 12+0.5（123-12）=67.5 25+1.1（4-25）=1.9 5+（-0.1）（34-5）=2.1
③ 线性重组：与中间重组相似，也是对所有变量值有一个值。
例 父1 12 25 5
父2 123 4 34
样本1 0.5
样本2 0.1
子1：12+0.5（123-12）=67.5 25+0.5(4-25)=14.5 5+0.5(34-5)=19.5子2 ：12+0.1(132-12)=23.1 25+0.1(4-25)=22.9 5+0.1(34-5)=7.9
（2）二进制交叉
包括单点交叉，多点交叉和均匀交叉。前两种交叉点是随意设定的；均匀交叉将每个点都作为潜在交叉点，随机产生与个体等长的0-1掩码， 掩码中的片断表明了哪个父个体向子个体提供变量值。

例 父1 0 1 1 1 0 0 1 1 0 1 0
父2 1 0 1 0 1 1 0 0 1 0 1
掩码样本1 0 1 1 0 0 0 1 1 0 1 0
掩码样本2 1 0 0 1 1 1 0 0 1 0 1
子1 1 1 1 0 1 1 1 1 1 1 1
子2 0 0 1 1 0 0 0 0 0 0 0
3. 变异
重组之后是子代的变异，子个体变量以很小概率或步长产生变异，变量转变的概率或步长与维数（变量个数）成反比，与种群大小无关。据研究，对于单峰函数1/n是最好的选择，开始时增加变异率，结束时减小变异率可以改善搜索速度。但对于多峰函数变异率的自适应过程是很有益的选择。变异本身是一种局部随机搜索，与选择/重组算子结合在一起，保证了遗传算法的有效性， 使遗传算法具有局部的随机搜索能力，同时使遗传算法保持种群的多样性，以防止出现非成熟收敛。变异操作中变异率不能太大，否则就退化为纯随机搜索， 遗传算法的一些主要特征就不存在了。
（1）实值变异：

L:变量的取值范围；a(i)以概率1/m取值1，以1-1/m取值为0
通常=20
（2）二进制变异：此时变异即意味着翻转，其变异位是随机确定的。
例 变异前 0110011010
变异后 0111011010
另外还有换位、复制、插入、删除变异。
2.6 算法设计与实现
基本遗传算法（Simple Genetic Algorithm）可定义为一个8元组：
SGA=(C,E,P0,M, ,)
C—个体的编码方法，SGA使用固定长度二进制符号串的编码方法。
E—个体的适应度评价函数
P0—初始种群
M—群体大小，一般取20-100
—选择算子，SGA使用比例选择算子
—交叉算子，SGA使用单点交叉算子
—变异算子，SGA使用基本位变异算子
T—算法中止条件，一般终止进化代数为100—500
1. 问题的表示
对于一个实际待优化问题，首先要将其表示为适合遗传算法操作的形式。以二进制为例，主要包括：
（1） 根据具体问题确定待寻优的参数
（2） 对每个参数确定它的变化范围并用二进制表示

b为m位二进制数，m在满足精度要求的情况下应尽量小
（3） 将所有表示参数的二进制数串接起来组成一个长的二进制字串。 该字串的每一位只有0或1两种取值。该字串即为一串算法的操作对象。
2. 初始种群的产生
可以完全随即产生或由先验知识构造