模式举例
模式 *10101110 与以下两个字符串匹配: 010101110 110101110 而模式 *1010*110 与以下四个字符串匹配: 010100110 010101110 110100110 110101110
遗传算法与自然进化的比较
自然界 染色体 基因 等位基因(allele) 染色体位置(locus) 基因型(genotype) 表型(phenotype) 遗传算法 字符串 字符,特征 特征值 字符串位置 结构 参数集,译码结构
新达尔文进化理论的主要论点
1) 个体是基本的选择目标; 2) 随机过程在进化中起重大作用, 遗传变异大部 分是偶然现象; 3) 基因型变异大部分是重组的产物, 部分是突变; 4) 逐渐进化可能与表型不连续有关; 5) 不是所有表型变化都是自然选择的必然结果; 6) 进化是在适应中变化的, 形式多样, 不仅是基因 的变化; 7) 选择是概率型的, 而不是决定型的.
智能计算
智能计算
计算智能是以数据为基础,通过训练建立联系, 进行问题求解,特点是: 1, 以分布式方式存储信息 2, 以并行方式处理信息 3, 具有自组织,自学习能力 4,计算智能适用于于解决那些难以建立确定性 数学/逻辑模型,或不存在可形式化的思想为基础,有众多发 展方向. 人工神经网络(ANN),遗传算法,蚁群算法, 人工免疫算法等都可以包括在计算智能中.
基本遗传算法的构成要素
4,运行参数 N:群体大小,即群体中包含的个体的数量. T:遗传算法终止的进化代数. Pc:交叉概率,一般取为 0.4～0.99. Pm:变异概率,一般取为 0.0001～0.1 .
基本遗传算法
1. 随机产生一个由固定长度字符串组成的初始群体; 2. 对于字符串群体,迭代地执行下述步骤,直到选种标准被 满足为止: 1) 计算群体中的每个个体字符串的适应值; 2) 应用下述三种操作(至少前两种)来产生新的群体: 复制: 把现有的个体字符串复制到新的群体中. 杂交: 通过遗传重组随机选择两个现有的子字符串, 产生新的字符串. 变异: 将现有字符串中某一位的字符随机变异. 3. 把在后代中出现的最高适应值的个体字符串指定为遗传算 法运行的结果.这一结果可以是问题的解(或近似解).
遗传算法的基础:孟德尔遗传学
在孟德尔遗传学中,基因型被详细模型化,而表型 和环境被忽略. 简单起见,假设一个基因具有n 等位基因a1,…,an. 二倍基因型以元组(ai,aj)为特征. 我们定义 pij 为 总群体中基因型(ai,aj) 的频度.假设基因型与表型 相等.质量函数给每个表型赋值. q(ai,aj) = qij qij 可以被解释为出生率减去死亡率
r
.
.
pi
.
p1
.. .
p2
单点一致交叉
首先以概率pc从种群中随机地选择两个个体 p1,p2.在{1, 2, . . . ,λ}内随机选择一个数ι, 作为交叉的位置,称为交叉点.然后将两个 个体交叉点后面的部分交换. 例如:
0110 101100 1100 011001 0110 011001 1100 101100
选择结果:01101,11000,11000,10011 (5)交叉操作:发生交叉的概率较大Pc = 0 . 8 , 0 . 9 ... 哪两个个体配对交叉是随机的 交叉点位置的选取是随机的(单点交叉) 0110 1 1100 0 01100 11001 11 000 10 011 11 011 10 000
p'i = pi Qi
Qi = ∑ qi , j p j
j
Q
遗传算法的基础:孟德尔遗传学
这个离散的选择方程可以用连续方程近似:
dpi = pi (Qi Q) / Q dt
如果 qi,j = qj,i, 那么
dpi = pi (Qi Q) dt
遗传算法的基础:孟德尔遗传学
可以证明:
2 dQ 2 = 2( E (Q ) Q ) = 2Var (Q) ≥ 0 dt
(6)变异:发生变异的概率很小 Pm = 0 . 0001 (7)新群体的产生: 保留上一代最优个体,一般为10%左右,至少1个 用新个体取代旧个体,随机取代或择优取代. 11000,11011,11001,10011 (8)重复上述操作: 说明:GA的终止条件一般人为设置; GA只能求次优解或满意解. 分析:按第二代新群体进行遗传操作,若无变异,永 远也找不到最优解——择优取代有问题. 若随机的将个体01101选入新群体中,有可能 找到最优解.
复制个体
i:=i+1 完成交叉
完成变异
把新的孩子加 入到群体中
把变异后个体 加入到群体中
把新的两个孩 子加到群体中
i:=i+1
1
轮盘式选择
首先计算每个个体 i 被选中的概 率 f (i )
pi =
∑ f ( j)
j =1
n
然后根据概率的大小将将圆盘分 为 n个扇形,每个扇形的大小 为 2π pi .选择时转动轮盘,参 考点r落到扇形i则选择个体i .
1) 确定表示方案; 2) 确定适应值的度量; 3) 确定控制该算法的参数和变量; 4) 确定怎样指定结果及程序运行结束的标准.
基本遗传算法
基本遗传算法(Simple Genetic Algorithm:SGA)又称为简单 遗传算法,只使用选择算子,交叉算子和变异算子这三 种基本的遗传算子.其遗传操作简单,容易理解,是其 它遗传算法的雏形和基础.
遗传算法的理论基础
11.5.1 模式的定义 遗传算法的理论基础是遗传算法的二进制表达式 及模式的含义.模式是能对染色体之间的相似性 进行解释的模板. l l S = {0,1,*} [定义1] 设GA的个体 p ∈ B ,记集合 则称 s ∈ S 为一个模式,其中*是通配符. 即模式(schema)是含有通配符(*)的一类字符串 的通式表达.每个"*"可以取"1"或者"0".
遗传算法的特点
特点: 通用 鲁棒 次优解,满意解 遗传算法能解决的问题: 优化 高度复杂的非线性问题
遗传算法
遗传算法先将搜索结构编码为字符串形式, 每个字 符串结构被称为个体. 然后对一组字符串结构(被称为一个群体)进行循环 操作.每次循环被称作一代,包括一个保存字符串 中较优结构的过程和一个有结构的,随机的字符 串间的信息交换过程. 类似于自然进化,遗传算法通过作用于染色体上 的基因寻找好的染色体来求解问题.
基本遗传算法的构成要素:
1,染色体编码方法:首先必须对问题的解空间进行编码, 使之能用遗传算法进行操作.较常用的是二进制编码方 法,现在使用非二进制编码的也逐渐增多. 2,适应度函数(fitness function,又称为适应值/适值函 数)用来评价一个染色体的好坏.
基本遗传算法的构成要素
3,遗传算子 选择算子(selection) :又称为复制算子.按照某种策略 从父代中挑选个体进入下一代,如使用比例选择,轮盘 式选择. 交叉算子(crossover):又称为杂交算子.将从群体中选 择的两个个体,按照某种策略使两个个体相互交换部分 染色体,从而形成两个新的个体.如使用单点一致交叉. 变异算子(mutation):按照一定的概率(一般较小),改 变染色体中某些基因的值.
遗传算法
与自然界相似,遗传算法对求解问题的本身一无 所知,它所需要的仅是对算法所产生的每个染色 体进行评价,并基于适应值来选择染色体,使适 应性好的染色体有更多的繁殖机会. 在遗传算法中,位字符串扮演染色体的作用,单 个位扮演了基因的作用,随机产生一个体字符串 的初始群体,每个个体给予一个数值评价,称为 适应度,取消低适应度的个体,选择高适应度的 个体参加操作. 常用的遗传算子有复制,杂交,变异和反转.
2
19 361
适应度: 169
(3)适应度评价: fitness ( x ) = x
(4)选择:选择概率 Pi = f i / ∑ f ∑ f = 1170 个体: 01101,11000,01000,10011 适应度: 169 选择概率:0.14 576 0.49 64 0.06 361 0.31
进化计算的三大主流板块
三种算法既有许多相似之处,同时也有很大的不同 进化规划和进化策略都把 变异 变异作为主要的搜索算子, 而在标准遗传算法中,变异只处于次要地位 交叉在标准遗传算法中起着重要作用,而在进化规划 交叉 中被完全省去,在进化策略中与自适应结合在一起使 用非常重要; 标准遗传算法和进化规划都强调 随机选择 随机选择机制的重要 性,而从进化策略的角度看,选择是完全确定的,没 有合理的根据表明随机选择原则的重要性; 进化规划和进化策略确定地把某些个体排除在被选择 复制之外,而标准遗传算法一般对每个个体都指定一 个非零选择概率.
基本遗传算法流程图
GEN=0 随机创建初始群体 是否满足选中标准? 否 计算群体中每个个体的适应值 i:=0 是 GEN:=GEN+1 (转下页) 是 显示结果
结束
i=N?
概率地选择遗传操作
1
(接上页) p(r)选择 根据适应值选 择一个个体
概率地选择遗传操作 p(c)交叉 基于适应值选 择两个个体 变异p(m) 根据适应值选 择一个个体
遗传算法发展历史
进化计算的研究起源于20世纪50年代. 1965年,Holland首次提出了人工遗传操作 的重要性,并把这些应用于自然系统和人 工系统中. 大约在同一时期: Rechenberg和Schwefel提出了进化策略. Fogel提出了进化规划.
遗传算法发展历史
1975年Holland出版了他的著名专著《自然系统和人 工系统的适应性》该书系统地阐述了遗传算法的基本 理论和方法,并提出了对遗传算法的理论研究和发展 极为重要的模式理论(schemata theory),该理论 首次确认了结构重组遗传操作对于获得隐并行性的重 要性. 同年,DeJong在论文《遗传自适应系统的行为分析》 中把Holland的模式理论与他的计算使用结合起来.