第二章 基本遗传算法(GA) 2.1 基本遗传算法描述 基本遗传算法的构成要素 (1) 染色体编码方法

Slides:



Advertisements
Similar presentations
简单迭代法的概念与结论 简单迭代法又称逐次迭代法,基本思想是构造不动点 方程,以求得近似根。即由方程 f(x)=0 变换为 x=  (x), 然后建立迭代格式, 返回下一页 则称迭代格式 收敛, 否则称为发散 上一页.
Advertisements

完美殺人筆記簿 【爸!我受夠了!】 第七組組員: 林正敏 陳筱涵 李蓓宇 許純宜 羅玉芬 謝文軒.
第 4 章 基于遗传算法的随机优化搜索 4.1 基本概念 4.2 基本遗传算法 4.3 遗传算法应用举例 4.4 遗传算法的特点与优势.
2.5 微分及其应用. 三、可微的条件 一、问题的提出 二、微分的定义 六、微分的形式不变性 四、微分的几何意义 五、微分的求法 八、小结 七、微分在近似计算中的应用.
《公路纵断面设计》 —— 纵断面设计的要求 道桥系 二○○七年五月. 纵断面设计的一般要求 1 .纵坡设计必须满足《公路工程技术标准》中的各项规定。 2 .为保证汽车能以一定的车速安全舒顺地行驶,纵坡应具有 — 定 的平顺性,起伏不宜过大及过于频繁。尽量避免采用极限纵坡 值.缓和坡段应自然地配合地形设置,在连续采用极限长度的.
揭日本人让人理解不了的20件事 今天先来看看日本人的自我剖析︰日本人的20个“为什么”?这“20个为什么”的内容来源于日本影视名人北野武所主持的一个节目。虽然不是网友来信中提出过的问题,但看看日本人自己对自己的分析,是挺有意思的。而且,仔细看看下面这“日本人的20个为什么”,会发现其实有些东西对于中国人来说并不陌生。毕竟汉字圈里的文化,是有共融之处的。
第2章 证券市场的运行与管理.
科学就医健康教育核心信息 健康中国行·科学就医 一、倡导科学就医 二、遵从分级诊疗 三、定期健康体检 四、鼓励预约挂号 五、就医注意事项
從「穹頂之下」電影看環境議題 第六小組 4a 黃士齊 4a 吳承翰 4a 洪濬森 4a 郭哲宇 0a40f226 湯思祺 林喬舜.
★中国近代史: 1840年————1949年 鸦片战争 新中国诞生 ★历史线索: 1、资本主义列强对中国的侵略 2、中国人民的反抗和探索:
幾米 作業 1 飛上天空 我想飛上天空 遨遊在無際的天空 美麗的天空 漂亮的天空 這終究只是夢…… (李高仰)
窦娥冤 关汉卿 感天动地 元·关汉卿.
开启新征程 点燃中国梦 开启新征程 点燃中国梦 ——学习、领会2013年全国“两会”精神.
专利技术交底书的撰写方法 ——公司知识产权讲座
如何看懂孩子的 性向測驗與興趣量表 陳郁雯.
巫山职教中心欢迎您.
第四章 先秦说理散文.
清华大学出版社 北京交通大学出版社 吴柏林 编著
知其不可而为之.
中国画家协会理事、安徽省美术家协会会员、 工艺美术师、黄山市邮协常务理事余承平主讲
证券交易模拟 第2讲 交易规则与盘面术语.
第二章 语音 第六节 音变 轻 声1.
水仙电器财务失败案例.
敬业与乐业 梁启超.
學校:光春國中 班級:七年三班 製作團隊: 顏序芳 李邰岳 謝宜軒
103校務評鑑程序與注意事項
汉字的构造.
诵读欣赏 古代诗词三首.
宁波万里国际学校 陈湘龙
孟子名言 1. 幼吾幼,以及人之幼。 2.天时不如地利, 。 3. ,威武不能屈。 4.得道者多助, 。 5.穷则独善其身, 。 6.
寡人之于国也 《孟子》.
电话联系.
迎宾员礼仪 包头机电工业职业学校管理系 白琳 1.
第五章 遗传算法.
四种命题 班级:C274 指导教师:钟志勤 任课教师:颜小娟.
产后血晕.
第三章 搜索技术 第一节 引言 一、搜索 对于无成熟方法可用的问题求解,必须一步步地摸索求解,这种问题求解过程就是搜索。
足太阳膀胱经.
第五章 定积分及其应用.
财 务 会 计 第四篇:供应链会计实务 制作人:谌君、熊瑜.
消防产品监督管理规定 《消防产品监督管理规定》已经2012年4月10日公安部部长办公会议通过,并经国家工商行政管理总局、国家质量监督检验检疫总局同意,现予发布,自2013年1月1日起施行。 2013年3月17日.
高中算法与程 序设计 教学建议 ---循环结构部分
贴近教学 服务师生 方便老师.
六年级 语文 下册 第四单元 指尖的世界.
(浙教版)四年级品德与社会下册 共同生活的世界 第四单元 世界之窗 第二课时.
第六章 计算智能 6.1 概述 6.2 神经计算 6.3 进化计算 6.4 模糊计算 6.5 粗糙集理论 6.6 其他.
第六章 智慧型的行銷資訊系統 課程名稱 行銷資訊系統 進度 第六章 授課老師 總時數 3小時 線 行銷資訊系統 – E世代的行銷管理.
数学3(必修)—— 算 法 ALGORITHM 苏州大学数学科学学院 徐稼红
灵敏度分析 (what-if分析) 在实际问题中,我们首先收集有关数据,建立线性规划模型,用Excel求解.
猜一猜 身穿五彩衣, 头上一双大眼睛, 要问我从哪里来, 江河湖海是我家。.
遗传算法(Genetic Algorithm) Natural Computing
網路遊戲版 幸福農場168號.
导数的应用 ——函数的单调性与极值.
第二章 基本遗传算法(GA) 2.1 基本遗传算法描述 基本遗传算法的构成要素 (1) 染色体编码方法
浙江大学医学院公共技术平台 实验仪器预约管理系统系列培训 医学院公共技术平台 丁巧灵
四川省天全中学说课竞赛 多媒体演示课件 ★ ☆ 函数的单调性 天全中学数学组 熊 亮.
植物生理学 ——成花生理—— 任课教师: 张 鹏 生命科学与技术学院.
第 四 章 迴歸分析應注意之事項.
解難指導(第2章) 熱學實驗(推斷不同因素造成的影響).
解難指導(第2章) 從結果倒推成因(熱學實驗).
Xián 伯 牙 绝 弦 安徽淮南市八公山区第二小学 陈燕朵.
基于实数编码的遗传算法在饲料配方设计中的应用
第十一章 基因演算法 (Genetic Algorithms)
數學遊戲二 大象轉彎.
第三章 线性规划问题的计算机求解.
§3 函数的单调性.
三、 动量和角动量 1 、 质点动量定理 动量 冲量.
statistic 比較fitness的 max,min 如果新值小於最佳 值就將新值的chrom, Phynotype,fitness,
第三章 导数及其应用.
数字控制系统 与数字PID控制器 戴连奎 浙江大学控制学院 2017/04/06.
Presentation transcript:

第二章 基本遗传算法(GA) 2.1 基本遗传算法描述 2.1.1 基本遗传算法的构成要素 (1) 染色体编码方法 2.1 基本遗传算法描述 遗传算法在自然与社会现象模拟、工程计算等方面得到了广泛的应用。在各个不同的应用领域,为了取得更好的结果,人们对GA进行了大量的改进,为了不至于混淆,我们把Holland提出的算法称为基本遗传算法,简称 GA、SGA(Simple Genetic Algorithm )、CGA(Canonical Genetic Algorithm),将其它的“GA类”算法称为GAs(Genetic Algorithms),可以把GA看作是GAs的一种特例。 2.1.1 基本遗传算法的构成要素 (1) 染色体编码方法 基本遗传算法使用固定长度的二进制符号串来表示群体中的个体,其等位基 因由二值符号集{0,1}组成。 初始群体中各个个体的基因值用均匀分布的随机数来生成。如: x;100111001000101101 就可表示一个个体,该个体的染色体长度是 l=18。

(2) 个体适应度评价 基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传 到下一代群体中的机会多少。为正确计算这个概率,这里要求所有个体的适应 度必须为正数或零。这样,根据不同种类的问题,必须预先确定好由目标函数 值到个体适应度之间的转换规则,特别是要预先确定好当目标函数值为负数时 的处理方法。 (3) 遗传算子 基本遗传算法使用下述三种遗传算子: • 选择运算:使用比例选择算子; • 交叉运算:使用单点交叉算子; • 变异运算:使用基本位变异算子。 (4) 基本遗传算法的运行参数 基本遗传算法有下述4个运行参数需要提前设定: • M:群体大小,即群体中所含个体的数量,一般取为20 ~ 100。 • T:遗传运算的终止进化代数,一般取为100 ~ 500 • pc:交叉概率,一般取为0.4 ~ 0.99 • pm:变异概率,一般取为 0.0001 ~ 0.1

2.1.2 基本遗传算法的形式化定义 [说明] 这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响,但目前 尚无合理选择它们的理论依据。在遗传算法的实际应用中,往往需要经过多次试 算后才能确定出这些参数合理的取值大小或取值范围。 2.1.2 基本遗传算法的形式化定义 基本遗传算法可定义为一个7元组: GA= (M, F, s, c, m, pc, pm ) M——群体大小; F——个体适应度评价函数; s——选择操作算于; c——交叉操作算子: m——变异操作算于; pc——交叉概率; pm——变异概率;

2.1.3 基本遗传算法描述 Procedure GA Begin initialize P(0); t=0; 2.1.3 基本遗传算法描述 Procedure GA Begin initialize P(0); t=0; while (t<=T) do for i=1 to M do Evaluate fitness of P(t); end for Select operation to P(t); for i=1 to M/2 do Crossover operation to P(t); for i=1 to M do Mutation operation to P(t); P(t+1) = P(t); t=t+1 end while end

2.2 基本遗传算法的实现 根据上面对基本遗传算法构成要素的分析和算法描述,我们可以很方便地用计 算机语言来实现这个基本遗传算法。 2.2 基本遗传算法的实现 根据上面对基本遗传算法构成要素的分析和算法描述,我们可以很方便地用计 算机语言来实现这个基本遗传算法。 现对具体实现过程中的问题作以下说明: 2.2.1 编码与解码 (1) 编码 假设某一参数的取值范围是[umin , umax],我们用长度为l的二进制编码符号串来表示该参数,则它总共能够产生 2l种不同的编码,参数编码时的对应关系如下: 00000000…00000000=0 umin 00000000…00000001=1 umin +  00000000…00000010=2 umin + 2 …… 11111111…11111111=2l–1 umax

 = Umax  umin Umax  umin 其中, 为二进制编码的编码精度,其公式为:  = Umax  umin 2l  1 (2) 解码 假设某一个体的编码是: x: bl bl-1 bl-2……b2b1 则对应的解码公式为: x = umin + (  bi · 2i-1 ) · 1 i=l Umax  umin 2l  1

 = Umax  umin  Umax  umin + 1 1/10000 12.1 + 3.0 2l  1 [例] 设 -3.0 ≤ x ≤ 12.1 , 精度要求 =1/10000,由公式:  Umax  umin 2l = + 1 1/10000 12.1 + 3.0 = = 151001 得: 即: 217 < 151001 < 218 x需要18位 {0/1} 符号表示。 如:010001001011010000 解码: x = umin + (  bi · 2i-1) · 1 i=l Umax  umin 2l  1 = - 0.3 + 70352(12.1+3)/(218-1) = 1.052426

2.2.2 个体适应度评价 如前所述,要求所有个体的适应度必须为正数或零,不能是负数。 2.2.2 个体适应度评价 如前所述,要求所有个体的适应度必须为正数或零,不能是负数。 (1) 当优化目标是求函数最大值,并且目标函数总取正值时,可以直接设定个体 的适应度F(X)就等于相应的目标函数值f(X),即: F(X)=f(X) (2) 对于求目标函数最小值的优化问题,理论上只需简单地对其增加一个负号就 可将其转化为求目标函数最大值的优化问题,即: min f(X)=max ( - f(X)) 但实际优化问题中的目标函数值有正也有负,优化目标有求函数最大值,也有 求函数最小值,显然上面两式保证不了所有情况下个体的适应度都是非负数这个 要求。

基本遗传算法一般采用下面两种方法之一将目标函数值 f(x)变换为个体的适应度F(x): 方法一:对于求目标函数最大值的优化问题,变换方法为: 其中,Cmin为一个适当地相对比较小的数,它可用下面方法之一来选取: • 预先指定的一个较小的数。 • 进化到当前代为止的最小目标函数值。 • 当前代或最近几代群体中的最小目标函数值。 方法二:对于求目标函数最小值的优化问题,变换方法为: 其中,Cmax是一个适当地相对比较大的数,它可用下面几种方法求得: • 预先指定的一个较大的数。 • 进化到当前代为止的最大目标函数值。 • 当前代或最近几代群体中的最大目标函数值。 F(X) = f(X)+Cmin if f(X)+Cmin> 0 0 if f(X)+Cmin ≤ 0 F(X) = Cmax - f(X) if f(X)  Cmax 0 if f(X)  Cmax

2.2.3 比例选择算子 (1) 选择算子或复制算子的作用: 从当前代群体中选择出一些比较优良的个体,并将其复制到下一代群体中。 2.2.3 比例选择算子 (1) 选择算子或复制算子的作用: 从当前代群体中选择出一些比较优良的个体,并将其复制到下一代群体中。 (2) 最常用和最基本的选择算子: 比例选择算子。 (3) 比例选择算子: 指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。 (4) 执行比例选择的手段是轮盘选择。 轮盘法的基本精神是:个体被选中的概率取决于个体的相对适应度: pi = fi / fi ( i=1,2,…,M ) 式中 pi——个体i被选中的概率; fi——个体i的适应度; fi——群体的累加适应度。 显然,个体适应度愈高,被选中的概率愈大。但是,适应度小的个体也有可 能被选中,以便增加下一代群体的多样性。

轮盘选择的原理: 图中指针固定不动,外圈的圆环可以 自由转动, 圆环上的刻度代表各个个 体的适应度。当圆环旋转若干圈后停止, 指针指定的位置便是被选中的个体。 从统计意义讲,适应度大的个体,其 刻度长,被选中的可能性大;反之,适 应度小的个体被选中的可能性小,但有 时也会被“破格”选中。

[论盘选择示例] 上述轮盘选择过程,可描述如下: Ⅰ. 顺序累计群体内各个体的适应度,得相应的累计值Si,最后一个累计值为Sn; Ⅱ. 在[0, Sn]区间内产生均匀分布的随机数r; Ⅲ. 依次用Si与r比较,第一个出现Si大于或等于r的个体j被选为复制对象; Ⅳ. 重复 Ⅲ、Ⅳ 项,直至新群体的个体数目等于父代群体的规模。

2.2.4 单点交叉算子 (1) 交叉算子作用 通过交叉,子代的基因值不同于父代。交换是遗传算法产生新个体的主要手段。正是有了交换操作,群体的性态才多种多样。 (2) 最常用和最基本——单点交叉算子。 (3) 单点交叉算子的具体计算过程如下: Ⅰ. 对群体中的个体进行两两随机配对。 若群体大小为M,则共有 [ M/2 ]对相互 配对的个体组。 Ⅱ. 每一对相互配对的个体,随机设置某一基因座之后的位置为交叉点。 若染色体的长度为l ,则共有(l-1)个可能的交叉点位置。 Ⅲ. 对每一对相互配对的个体,依设定的交叉概率pc在其交叉点处相互交换两个个 体的部分染色体,从而产生出两个新的个体。 单点交叉运算的示例如下所示: 单点交叉 A;10110111 00 A’:10110111 11 B:00011100 11 B’:00011100 00

交叉概率 pc = Mc M 式中 M——群体中个体的数目; Mc——群体中被交换个体的数目。 [交叉操作示例] 交叉的个体是随机确定的,如下表所示。某群体有n个个体,每个个体含8 个等位基因。针对每个个体产生一个[0, 1] 区间的均匀随机数。假设交叉概率 pc = 0.6,则随机数小于0.6的对应个体与其随机确定的另一个个体交叉,交叉 点随机确定。 个体编号 个体 随机数 交叉操作 新个体 1 11011000 0.728 2 10101011 0.589 101010 11 101010 01 3 00101100 0.678 4 10001101 0.801 100011 01 100011 11 …

2.2.5 基本位变异算子 基本位变异算子是最简单和最基本的变异操作算子。 2.2.5 基本位变异算子 基本位变异算子是最简单和最基本的变异操作算子。 对于基本遗传算法中用二进制编码符号串所表示的个体,若需要进行变异操作 的某一基因座上的原有基因值为0,则变异操作将该基因值变为1,反之,若原有 基因值为1,则变异操作将其变为0。 基本位变异因子的具体执行过程是: Ⅰ. 对个体的每一个基因座,依变异概率pm指定其为变异点。 Ⅱ. 对每一个指定的变异点,对其基因值做取反运算或用其它等位基因值来代替, 从而产生出一个新的个体。 基本位变异运算的示例如下所示: A:1010 1 01010 A’:1010 0 01010 基本位变异 变异点

变异概率 变异是针对个体的某一个或某一些基因座上的基因值执行的,因此变异概率pm 也是针对基因而言,即: Pm = B M · l 式中 B——每代中变异的基因数目; M——每代中群体拥有的个体数目 l——个体中基因串长度。

[变异操作示例] 变异字符的位置是随机确定的,如下表所示。某群体有3个个体,每个体含4 个基因。针对每个个体的每个基因产生一个[0, 1] 区间具有3位有效数字的均 匀随机数。假设变异概率 pm = 0.01,则随机数小于0.01的对应基因值产生变 异。表中3号个体的第4位的随机数为0.001,小于0.01,该基因产生变异, 使3号个体由 0010 变为 0011 。其余基因的随机数均大于0.01,不产生变异。

2.2.6 算法流程图 Y N pm pc 开始 Gen=0 编码 随机产生M个初始个体 满足终止条件? 计算群体中各个体适应度 从左至右依次执行遗传算子 j = 0 根据适应度选择复制个体 选择两个交叉个体 选择个体变异点 执行变异 执行交叉 执行复制 将复制的个体添入新群体中 将交叉后的两个新个体添入新群体中 将变异后的个体添入新群体中 j = j+1 j = j+2 j = M? j = pc·M? j = pm·L·M? Gen=Gen+1 输出结果 终止 Y N pc pm 2.2.6 算法流程图

2.3 基本遗传算法应用举例 —— 基本遗传算法在函数优化中的应用。 [例] Rosenbrock函数的全局最大值计算。 max f(x1,x2) = 100 (x12-x22)2 + (1-x1)2 s.t. -2.048 ≤ xi ≤ 2.048 (xi=1,2) 如图所示: 该函数有两个局部极大点, 分别是: f(2.048, -2048)=3897.7342 和 f(-2.048,-2.0048)=3905.9262 其中后者为全局最大点。

下面介绍求解该问题的遗传算法的构造过程: 第一步:确定决策变量及其约束条件。 s.t. -2.048 ≤ xi ≤ 2.048 (xi=1,2) 第二步:建立优化模型。 max f(x1,x2) = 100 (x12-x22)2 + (1-x1)2 第三步;确定编码方法。 用长度为l0位的二进制编码串来分别表示二个决策变量x1,x2。 lO位二进制编码串可以表示从0到1023之间的1024个不同的数,故将x1,x2的定义域离散化为1023个均等的区域,包括两个端点在内共有1024个不同的离散点。从离散点-2.048到离散点2.048,依次让它们分别对应于从0000000000(0)到1111111111(1023)之间的二进制编码。再将分别表示x1和x2的二个10位长的二进制编码串连接在一起,组成一个20位长的二进制编码串,它就构成了这个函数优化问题的染色体编码方法。例如 X:0000110111 11011 10001 就表示一个个体的基因型。

第四步:确定解码方法。 解码时先将20位长的二进制编码串切断为二个10位长的二进制编码串,然后分别将它们转换为对应的十进制整数代码,分别记为y1和y2。 依据前述个体编码方法相对定义域的离散化方法可知,将代码yi转换为变量xi的解码公式为: xi = 4.096  yi 1023  2.048 ( i = 1,2) 例如,对前述个体 X: 0000110111 11011 10001 它由这样的两个代码所组成: y1= 55 y2 = 881 经上式的解码处理后,得到: x1= -1.828 x2= 1.476

第五步:确定个体评价方法。 由式 f(x1,x2) = 100 (x12-x22)2 + (1-x1)2 可知, Rosenbrock函数的值域总是非负的,并且优化目标是求函数的最大值,故这里可将个体的适应度直接取为对应的目标函数值,并且不再对它作其他变换处理,即有: F(x) = f(x1,x2) 第六步:设计遗传算子。 选择运算使用比例选择算子; 交叉运算使用单点交叉算子; 变异运算使用基本位变异算子。 第七步:确定遗传算法的运行参数。 对于本例,设定基本遗传算法的运行参数如下: 群体大小: M=80 终止代数: T=200 交叉概率:pc=0.6 变异概率:pm=0.001

下图为其进化过程示例及运行结果。 图中两条曲线分别为各代群体中个体适应度的最大值和平均值。

下图所示分别为初始群体、第5代群体、第10代群体和第100代群体中个体的分布情况。 在图(a)中各个个体分布得比较均匀。 (a)

在图(b)中大量的个体分布在最优点和次最优点附近。

从图(c) 中可以看出,次最优点也被淘汰。

(d) 从图(d)中可以看出,个体更加集中在最优点附近。 由该组图我们可以看出,随着进化过程的进行,群体中适应度较低的一些个体被逐渐淘汰掉,而适应度较高的一些个体会越来越多.并且它们都集中在所求问题的最优点附近,从而最终就可搜索到问题的最优解。