《知识工程与知识管理第4章（3遺传算法）》由会员分享，可在线阅读，更多相关《知识工程与知识管理第4章（3遺传算法）（49页珍藏版）》请在金锄头文库上搜索。
1、第4章计算智能的仿生技术(3)遗 传 算 法43 遗传算法431 遗传算法原理432 优化模型的遗传算法求解433 基于遗传的分类学习系统4.3.1 遗传算法原理n遗传算法（Genetic Algorithms,GA）是 模拟生物在自然环境中的遗传和进化过程 而形成的一种自适应全局优化搜索算法。n它模拟了生物的繁殖、交配和变异现象， 从初始的种群，产生一群更适应环境的后 代。 n1975年美国Michigan大学J.Holland教授 提出。n美国人De.Jong博士将遗传算法应用于函 数优化。nGoldberg完成了遗传算法的框架。 4.3.1.1 遗传算法概述n遗传算法（Genetic A
2、lgorithms，GA）是一 种基于遗传学的搜索优化算法。 n遗传是作为一种指令码封装在每个染色体（个 体）中，并以基因（位）的形式包含在染色体 （个体）中。n在遗传算法中，“染色体”对应的是数据或数组 ，通常是由一维的串结构数据来表现。串上各 个位置对应“基因”，而各位置上的值对应基因 的取值。基因组成的串就是染色体，或者叫做 基因型个体。一定数量的个体组成了群体。 遗传算法将问题的每个可能的解按某种 形式进行编码，编码后的解称作染色体（个 体）。随机选取N个染色体（个体）构成初始种 群，再根据预定的评价函数对每个染色体计 算适应值，使得性能较好的染色体具有较高 的适应值。选择适应值高的染
3、色体进行复制，通过 遗传算子：选择、交叉（重组）、变异，来 产生一群新的更适应环境的染色体，形成新 的种群。这样一代一代不断繁殖、进化，最后收 敛到一个最适应环境的个体上，求得问题的 最优解。 初始化初始种群（编码成位串形式）计算每一个染色体（个体）的适应值是否满足优化准则输出结果YesNo选择交叉变异产生新一代种群遗 传 算 子遗 传 算 法 的 处 理 流 程 图4.3.1.2遗传算法中的基本要素遗传算法中包含了如下五个基本要素： 1）问题编码 2）初始群体的设定 3）适应值函数的设计 4）遗传操作设计 5）控制参数设定（主要是指群体大小和使用遗传 操作的概率等）这五个要素构成了遗传算法的
4、核心内容。 （1）问题编码如何将问题描述成位串的形式，即问题 编码。一般将问题中各参数用二进制编码， 构成子串，再将子串拼接起来构成“染色体” 位串。不同串长和不同的码制，对问题求解的 精度和遗传算法收敛时间会有很多影响。目前也出现采用其它编码方式，如用向 量、规则来表示染色体。 （2）初始群体的生成n遗传算法是群体型操作，这样必须为遗 传操作准备一个由若干初始解组成的初 始群体。n初始群体的每个个体都是通过随机方法 产生的。（3）适应值函数的确定 n适应值函数是根据目标函数确定的。适应值总 是非负的，任何情况下总是希望越大越好。n适应值函数的选取至关重要，它直接影响到算 法的收敛速度即最终能
5、否找到最优解。n函数优化问题可直接将目标函数本身作为适应 值函数。（4）控制参数 n参数主要有个体编码长度、群体大小M 、交叉概率Pc、变异概率Pm、终止代 数T等n这些参数对遗传算法的运行影响很大， 需要认真选择。4.3.1.3 遗传算子1、选择(Selection)算子依据每个染色体的适应值大小，适应值越大， 被选中的概率就越大，其子孙在下一代产生 的个数就越多。选择操作是建立在群体中个体的适应值评估基 础上的，目前常用的选择算子有适应值比例 法、最佳个体保存法、期望值方法等。2、交叉(Crossover)算子通过染色体重组来产生新一代染色体。 如有两个用二进制编码的个体A和B。 交叉前后
6、为：A=a1a2a3a4a5 A=a1a2a3b4b5B=b1b2b3b4b5 B=b1b2b3a4a5(父代) (子代)3、变异(Mutation)算子 n变异增加了遗传算法找到接近最优解的能力。n变异就是以很小的概率，随机地改变字符串某个位 置上的值。把某一位的内容进行变异。n在二进制编码中，就是将某位0变成1，1变成0。 如：110010的第四位变异成110110（父代） （子代）4.3.1.4 遗传算法的理论基础1.模式定理遗传算法的理论基础是Holland提出的模式 定理。一个模式(Schema)就是一个描述种群 中在位串的某些确定位置上具有相似性的位串 子集的相似性模板(Simil
7、arity Template)。模式定理是遗传算法的理论基础，它说明：高适应值、长度短、阶数低的模式在后代中至 少以指数增长包含该模式H的位串的数目。原因在于遗传使高适应值的模式复制更多的后 代。2基因块假设高适应值、长度短、低阶的模式叫基因块 。基因块假说：长度短的、低阶的、高适应值的模式(基因 块)通过遗传操作繁殖、交换、变异，的逐渐 进化，形成潜在的适应性较高的位串。该假设指出，通过遗传算法能寻找到接近 全局最优解的能力。4.3.1.5 遗传算法的特点n遗传算法是进行群体的搜索。n它对多个个体进行群体搜索，构成一个 不断进化的群体序列，它能找到全局最 优解（优于爬山法）n遗传算法是一种随
8、机搜索方法，三个算 子都是随机操作，利用概率转移规则。n遗传算法的处理对象是问题参变量进行编码的个 体，而不是参变量自身。n参变量编码成位串个体，通过遗传算子进行操作 。不是对参数变量进行直接操作。n遗传算法利用适应值信息，而不需要导数或其它 辅助信息。n遗传算法用适应值评估个体，用遗传算子产生更 优后代，不需要像神经网络中用梯度公式引导。 n隐含并行性：n遗传算法是对N个位串个体进行运算， 它隐含了大量的模式（用通配符#包含 的个体）4.3.2 优化模型的遗传算法求解 遗传算法用于优化计算例例1：求发f(x)=x2 在0，31上的 最大值。一、初始种群1.编码：用五位二进制表示x，有x=0
9、0 0 0 0 0 x=31 1 1 1 1 1 2.初始种群随机产生4个个体：13 ， 24 ， 8 ，193.适应值fi直接用目标函数作为适应值：fi=xi2(1)非负 ; (2)逐步增大4.选择率ps和期望值(1)选择率： ps=fi/fi(2)平均适应值： f =fi/n(3)期望值： fi/f(4)5.实选值(5)期望值取整数 编编号初始种群位 串 参数值值x 值值目标标适 应值应值 f(x)=x2选择选择 率 fi/fi期望值值 fi/f实选值实选值1 2 3 40 1 1 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 1 113 24 8 9169 576 64 3
10、610.14 0.49 0.06 0.310.58 1.97 0.22 1.231 2 0 1总总和 平均值值 最大值值1170 293 5761.00 0.25 0.494.00 1.00 1.974.0 1.0 2.0初始种群参数计算二、遗传选择选择 后的交配 池（下划线线部 分交叉）交叉对对象 （随机选选 择择）交叉位置 （随机选择选择 ）新的种群xf(x)=x20 1 1 0 1 1 1 0 0 0 1 1 0 0 0 1 0 0 1 12 1 4 34 4 2 20 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 0 0 0 0 12 25 27 16144 625 72
11、9 256总总和 平均值值 最大值值1754 439 729说明：1.选择（繁殖）在种群众，实选值（期望值）高者多繁殖； 实选值（期望值）低者少繁殖或不繁殖。繁殖（复制）的个体放入交配池中。2.交叉随机选择交配对象（相同个体不交配），如 个体1和2，3 和4。随机选择交叉点进行交叉。3.变异取变异概率pe=0.01，表示每100个体中有一 个个体的一位发生变异。（暂不变异）新的种群，其平均值和最大值都有很大提高。均值：293 439最大值：576 729新种群中四个个体，有2个变好：25，25；2 个变坏：12，16。三、再遗传一代编编号初始种群位 串 参数值值x 值值目标标适 应值应值 f(
12、x)=x2选择选择 率 fi/fi期望值值 fi/f实选值实选值1 2 3 40 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 0 0 0 012 25 27 16144 625 729 2560.08 0.36 0.42 0.150.33 1.42 1.66 0.580 1 2 1总总和 平均值值 最大值值1754 439 7291.00 0.25 0.424.00 1.00 1.664.0 1.0 2.0选择选择 后的交配 池（下划线线部 分交叉）交叉对对 象 （随机 选择选择 ）交叉位置 （随机选择选择 ）新的种群xf(x)=x21 1 0 0 1 1 1 0 1 1 1
13、1 0 1 1 1 0 0 0 02 1 4 31 1 3 31 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 0 1 127 25 24 19729 625 576 361总总和 平均值值 最大值值2291 572 729单纯用交叉而没有用变异，则遗传多少代得 不到最优解31(1 1 1 1 1 )。主要是第三位所有 个体都是0，这样只能得到27（1 1 0 1 1） 次 优解。若在第四位中挑选一个个体进行变异，由0 变成1，在进行遗传将会得到最优解。说明：例2：旅行商路径问题（TSP）已知n个城市的地理位置（x,y），求 经过所有城市，并回到出发城市且每个城 市仅经过一次
14、的最短距离。这是一个NP完全问题，其计算量为城 市个数的指数量级。现用遗传算法来解决 这个问题。 1、编码 每条路径对应一个个体，个体形式地表示为 R=City_No|City_No互不重复n，n为城市数 。例如对于n=10的TSP问题，对其中一个个体它表示一条城市路径：3 1 5 7 8 9 10 4 2 63 1 5 7 8 9 10 4 2 62、适应值函数 每个个体代表一条可能的路径。个体n的适应值为：其中N为种群数，Dn为 沿个体标示的城市序列的所经过 的距离：其中ni表示个体中第i位的城市编号，n11=n1。 适应值为非负，且取值越大越好。 表示所有个体的 路径长度的总和3、交叉
15、随机地从种群中选出要交叉的两个不同个体，随 机地选取一个交叉段。交叉段中两个个体的对应部分通 过匹配换位实现交叉操作。对个体A和B：A9 8 4 |5 6 7| 1 3 2 10B8 7 1 |4 10 3| 2 9 6 5交叉段 对个体A，对交叉段中由B换位来的数，如4、10、3，在 A中其它位相同的数进行反交换，即4换为5，10换为6 ，3换为7；对个体B，相似处理，最后得到：A，9 8 5 |4 10 3| 1 7 2 6 B，8 3 1 |5 6 7| 2 9 10 44、变异 根据变异概率Pe，随机地从种群中选出要变异的 个体，随机地在该个体上选出变异两个位置，然后两 个位置上的城市序号进行交换。如：A =9 8 4 5 6 7 1 3 2 10下划线部分为要变异的两个位置。变异为：A=9 7 4 5 6 8 1 3 2 105、遗传算法结果计算结果表明：n个城市的最佳路径接近一个外圈无交叉 的环路。4.3.3 基于遗传的分类学习系统n分类器
