进化计算2

遗传算法提供了一种在复杂解空间上进 行有向随机搜索的方法。遗传算子原则 上进行的是盲目搜索；选择算子有可能 将遗传搜索的方向引导到解空间的理想 区域中。现实要求对解空间进行深度搜 索和广度搜索中维持很好的平衡。为此 必须仔细考虑遗传算法的所有组成部分。 还需要结合附加的启发式方法增强其性 能。
五、遗传算法的基本实现技术
第5章 计算智能
遗传算法
主要内容

进化算法的概念和研究领域 遗传算法的机理 及求解问题的步骤、算法框架、主要应 用领域
5.4 遗传算法概述

生物种群的生存过程普遍遵循达尔文的物竞天择、 适者生存的进化准则。种群中的个体根据环境的适 应能力而被大自然选择或淘汰。


进化过程的结果是发生在个体结构上，其染色体包含若 干基因上，相应的表现型和基因型的联系体现了个体的 外部特征与内部机理间的逻辑关系。 生物通过个体间的选择、交叉、变异来适应大自然环境。 生物染色体用数学方式或计算机方式来体现就是一串数 码，仍叫染色体，有时也叫个体；适应能力用对应一个 染色体的数值来衡量；染色体的选择或淘汰问题是按求 最大还是最小问题来进行的。
1.编码方法 2.适应值函数 3.复制算子 4.杂交算子 5.变异算子 6.停止准则
1.编码方法与原则

编码方法


二进制编码 浮点编码 格雷编码 不冗余 合法性 完备性

编码规则


ห้องสมุดไป่ตู้
1.编码与解码


将问题结构变换为位串形式编码表示的 过程叫编码；而相反将位串形式编码表 示变换为原问题结构的过程叫解码或译 码。把位串形式编码表示叫染色体，有 时也叫个体。 遗传算法的编码方法有二进制编码、浮 点数编码方法、格雷码、符号编码方法、 多参数编码方法等。

5.4 遗传算法概述


人类不满足于模仿生物进化行为，希望能够建 立具有自然生命特征的人造生命和人造生命系 统。 人工生命是人工智能和计算智能的一个新的研 究热点。进化计算为人工生命研究提供了计算 理论和有效的开发工具。
5.4 遗传算法概述



遗传算法是模仿生物遗传学和自然选择机理， 通过人工方式所构造的一类优化搜索算法，是 对生物进化过程进行的一种数学仿真，是进化 计算的最重要的形式。 遗传算法为那些难以找到传统数学模型的难题 指出了一个解决方法。 进化计算和遗传算法借鉴了生物科学中的某些 知识，这也体现了人工智能这一交叉学科的特 点
00001 11100 01000 10011
2.计算适应度 3.复制
表1 复制操作之前的各项数据
串 号 1 2
初始 X值 适应值f 复制概率f（xi） 期望复制数 种群 （表 fi/fi均 （xi） / f（xi） （基因 现型） 型） 00001 1 40 0.071 0.283 11100 28 94 0.166 0.664
对交配池中指定百分比的个体应用杂交算子，假设杂交概率 pc＝50％，交配池中余下的50％个体仅进行复制运算，即复 制概率pr＝50％。
4.交换（杂交） 表2 复制操作之后的各项数据 复制 种群 （基因 型） 匹配 对象 （随 机选 取） 11100 4 01000 3 10011 10011 2 1
5.4.2 遗传算法的求解步骤
一、遗传算法的特点 二、基本遗传算法的构成要素 三、基本遗传算法的一般框架 四、遗传算法的基本实现技术 五、遗传算法性能 六、遗传算法的应用 七、用遗传算法优化ANN的结构
一、遗传算法的特点
(1) 遗传算法是对参数集合的编码而非针对参 数本身进行进化； (2) 遗传算法是从问题解的编码组开始而非从 单个解开始搜索； (3) 遗传算法利用目标函数的适应度这一信息 而非利用导数或其它辅助信息来指导搜索； (4) 遗传算法利用选择、交叉、变异等算子而 不是利用确定性规则进行随机操作。
5.4.1 遗传算法的基本机理

GA的算法过程简述如下。首先，在解空间中 选取一群点，作为遗传开始的第一代。每个 点（基因）用一个二进制数字表示，其优劣 程度用一个目标函数——适应度函数来衡量。
开始 (1) (2)
初始化种群 计算适应度值 选择操作
(3)
(4) (5)
交叉操作
变异操作
否
(7)
终止条件？
f ( w1 w2 ...wn ) 1
d (w
j 1
n
j
, w j 1 )
2.适应值函数
适应值函数必须是正数，出现负数时应进 行变换，常用变换方式有三种： 线性比例法：g（x）＝a f（x）＋ b ( b 大于0) 指数比例法：g（x）＝exp(a f(x))， (a不等于0) 幂指数比例法：g（x）＝ (f(x)) a (a为偶 数)
总和 最小值 平均值 最大值
盘赌选择
（1）将群体中所有串的适应值相加求总和 （2）产生一个在0与总和之间的随机数m （3）从群体中编号为1的串开始，将其适 应值与后继串的适应值相加，直到累加 和等于或大于m 随机数 5 2 12 9 选择的串110 011 010 110
二进制编码

最常用的编码方法 假设某一参数的取值范围是[A，B]，A<B。用长度 为l的二进制编码串来表示该参数，将[A，B]等分成 2l-1个子部分，记每一个等分的长度为δ。参数编码 的对应关系: 00000000 …… 00000000=0 ——→ A 00000000 …… 00000001=1 ——→A+δ … … … … …
6.迭代 表3 第一次迭代之后的各项数据
串 号 复制概率f （xi）/ f （xi） 期望复制数 复制 数 复制种群 （基因型） x值 交 （表 换 现型） 点 新种群 （基因型） x值 适应 度
1 2 3 4
0.014 0.311 0.338 0.338
0.054 1.243 1.352 1.351
基本的遗传算法
Procedure Genetic Alogorithm； begin k：=0； 初始化P（k）； {P（k）为第k代群体} 计算P（k）的适应值； while (不满足停止准则)do k：=k+1； 从P（k-1）中选择P（k）； {复制算子} 重组P（k）； {杂交和变异算子} 在上一代中随机选择个个体随机替换P（k）中的个体； 计算P（k）适应值 end
5.4 遗传算法概述

20世纪60年代，如何模仿生物来建立功能强大的 算法，进而将它们运用于复杂的优化问题成为研 究热点。

进化计算是一类借鉴生物界自然选择和自 然遗传机制的随机搜索算法。
进化计算包括： 遗传算法(genetic algorithms，GA) 进化策略(evolutionary strategies) 进化编程(evolutionary programming) 遗传编程(genetic programming)
3.复制算子

赌盘选择 确定性选择 有退还和无退还随机选择 有退还和无退还剩余随机选择
确定性选择方法
Fi 对群体中每个串e i 计算生存概率 pi Fi / , i 1 e 从而得到 i 的期望拷贝数 pi N ，仍记 为；根据 e i 值的整数部分，分配给每 个串一个拷贝数，并按照 e i 值的小数部 分对群体中的串进行排序；最后按排列 顺序从大到小选择串，直到填满暂时群 体。
串 号 1 2 3 4
交换点 新种群（基因 （随机）型） 3 2 2 3 总和 平均值 11111 01011 10000 10000
x值（表现型）
适应度
31 11 16 16
10 230 250 250 740 185
5.变异




以一个很小的概率pm随机改变染色体串上的某些位。 对于二进制串，随机选取的串位的代码由1变成0或由0 变成1 例如：选新种群池中编号为2的串进行变异，且变异点 在2，则 01011 00011 变异算子相对而言，是次要算子，但在恢复群体中失 去的多样性方面具有潜在的作用。 本例，若变异概率为0.001，对于种群4*5=20个基因， 期望的变异位数为20*0.001=0.02（位），所以本例 无变异位。
0 1 1 2
01011 10000 10000 10000
2 1 4 3
3 3 2 2
01000 10011 10000 10000
8 19 16 16
194 238 250 250
总和 平均值 最大值
932 233 250

从数学分析可知，函数f(x)=-x2+31x+10 的极值点为x=15.5，最大函数值为 max(f(x))=250.25,可见用遗传算法计算 的结果也是很精确的。
二、基本遗传算法的构成要素
1.染色体编码方法－问题的解的遗传表示
最常用的是二进制编码，对于离散性变量直接编码，对于连续性变 量先离散化后再编码
2.适应度函数
评估函数——用来评估一个染色体的优劣的绝对值 适应度函数——评估一个染色体相对整个群体的优劣的相对值的大小
3.遗传算子
复制算子、交叉算子、变异算子
复制数 0 1
3
4
01000
10011 总和 平均值 最大值
8
19
194
238 566 141.5 238
0.343
0.420 1.00 0.25 0.42
1.371
1.682 4.00 1.00 1.68
1
2 4 1 2
4.杂交算子：采用一点杂交
作用过程：a）产生一个在1到l－1之间的随机数i b）配对的两个串相互对应的交换从i＋1到l的位段 例如：从交配池中选择编号为2和3的串进行配对，且杂交点 选在2（用分隔符|表示），杂交算子作用的结果为： 01 000 01011 10 011 10000
4.基本遗传算法运行参数
•N：群体大小，即群体中所含个体的数量，一般取20～100 •T：遗传算法的终止进化代数，一般取100～500 • pc：杂交概率，一般取0.4～0.99 • pm ：变异概率，一般取0.0001～0.1 • pr ：复制概率
三、基本遗传算法算法过程
1.随机产生一个由确定长度的特征串组成 的初始群体 2.对串群体迭代地执行下面的步（i）和步 （ii），直到满足停止准则： （i）计算群体中每个个体的适应值 （ii）应用复制、杂交和变异算子产生 下一代群体 3.把在任一代中出现的最好个体串指定为 遗传算法的执行结果，这个结果可以表示问 题的一个解（或近似解）
W1 , W2 ,..., Wn

由于是回路，记wn+1= w1。它其实是 1，……，n的一个循环排列。要注意w1， w2，……， wn是互不相同的。
2.适应度函数


体现染色体的适应能力，对问题中的 每一个染色体都能进行度量的函数， 叫适应度函数（fitness function） 对优化问题，适应度函数就是目标函 数。TSP的目标是路径总长度为最短， 路径总长度可作为TSP问题的适应度 函数：
最优解输出
是
(6) 结束
算法框图
例子

寻找函数f(x)=-x2+31x+10,当自变量x在 0~31之间的取整数时函数值的最大值

1. 编码


用5位二进制代码串就可组成所有染色体的基因型， 即所有染色体的基因型在00000~11111之间。 随机取4个x值：1,28,8,19.相对应的4个基因型为：
N
复制算子：采用赌盘选择 使用复制算子后产生的交配池 i 1 2 3 4 串xi 011 001 110 010 第0代 适应值f（xi） 3 1 6 2 12 1 3.00 6
f（xi）/ f（xi）
0.25 0.08 0.50 0.17
交配池 串 f（xi） 011 3 110 110 010 6 6 2 17 2 4.25 6
解码 假设某一个体的编码是： X：xlxl-1xl-2…x2x1， 则上述二进制编码所对应的解码公式为：
B A l x B l bi 2 i 1 2 1 i 1
l 11111111 …… 11111111= 2 -1 ——→ B



二进制编码的最大缺点之一是长度较大，对 很多问题用其他主编码方法可能更有利 符号编码方法是指个体染色体编码串中的基 因值取自一个无数值含义、而只有代码含义 的符号集。 例如，对于TSP问题，采用符号编码方法， 按一条回路中城市的次序进行编码，一般情 况是从城市w1开始，依次经过城市 w2 ，……， wn，最后回到城市w1，我们就 有如下编码表示：