当前位置:
文档之家› 常规优化算法第九章现代智能算法
常规优化算法第九章现代智能算法
编码
解码
§9.1 遗传优化算法
四. 算法实现的几个技术问题 —— 编码和解码
几种常见的编码方式
编码方式
示例
二进制编码 1 1 0 1 0 0 1 1
实数编码 5.80 6.70 2.18 3.56
符号编码 A B C D E F
序列编码 1 3 5 7 9 2 4 6
说明
染色体中的基因值只能是二值符号集 {0,1}中一个
遗传算法通过优化目标构造适应函数以达到好的染色 体超过平均数的后代。 (3)染色体结合时(交叉),双亲的遗传基因结合使得子女 保持父母的特征。 (4)当染色体结合后,随机变异会造成子代与父代不同。
§9.1 遗传优化算法
优化问题 解
遗传算法 染色体
目标函数值 较好的解集 在较好的解集邻域内搜索
探索新领域 初始多个随机解
适应度函数(竞争能力高低) 选择过程(体现适者生存)
交配过程(竞争能力高,产 生后代的概率就高)
变异过程(有好、坏之分)
初始种群
§9.1 遗传优化算法
二. 基本思想:
开始
遗传算法在求解优化问题 时首先对求解空间的各个解进 行编码。在寻优过程中,通过 对染色体 进行结合(选择、 交配和变异),不断产生新的 解,进而根据适应函数在新解 中选择部分染色体继续进行结 合,直至最终找到最好的解。
S.7 以一个较小的变异概率 pm ,使得一个染色体的基因 发生变异,形成变异群体mutpop (k+1) ;
S.8 令 k= k+1 和 popi(k) = mutpop (k+1) ,返回S.3; S.9 终止计算,输出最优结果。
§9.1 遗传优化算法
四. 算法实现的几个技术问题 —— 编码和解码 编码——由设计空间向编码空间的映射。将设计解用字 符串表示的过程。编码的选择是影响算法性能和效率的 重要因素。 解码——由编码空间向设计空间的映射。
适于求解高度非线性、多约束、多极值问题
§9.1 遗传优化算法
一. 背景: 依据生物进化论的“适者生存”规律而提出:
群体
变异
子群
竞争
婚配
淘汰的群体
种群
生物进化基本循环图
§9.1 遗传优化算法
遗传算法的主要生物进化特征体现在: (1)进化发生在解的编码(染色体)上。 (2)适者生存决定优秀的染色体产生超过平均数的后代。
fi
i 1
S.5 以概率 pi 从 pop (k) 中随机选一些染色体构成一个新群体 (其中可以重复选 pop (k) 中的元素)
newpop(k+1)= { popi(k) , i=1,2,···,N }
§9.1 遗传优化算法配概率 pc 得到一个有 N 个染色体的 交配群体crosspop (k+1);
关系如下:
00000000…00000000=0 00000000…00000001=1 00000000…00000010=2
……
umin umin + umin + 2
11111111…11111111=2l–1
umax
其中, 为二进制编码的编码精度,其公式为:
=
umax umin
染色体的基因值是设计变量的真实值
每一位基因只能有代码含义,无数值 含义
例如在旅行商问题中,此编码表示按 顺序”1→3→5→7→9→2→4→6→8→1” 依次访问各个城市
二进制编码方法
假设某一变量的取值范围是[umin , umax],用二进制编码符号 串来表示该变量, 则可以产生2λ个编码,变量编码时的对应
常规优化算法
第九章 现代智能算法
9.1 遗传优化算法 9.2 模拟退火算法 9.3 粒子群算法 9.4 神经网络算法
导言
常规优化算法 Powell法、梯度法 随机方向法、复合形法、惩罚函数法
启发式算法(现代优化计算方法) 退火算法 ( Simulated Annealing Algorithm ,SA) 遗传算法(Genetic Algorithms,GA) 粒子群算法( Particle Swarm Optimization,PSO) …
一个解(个体的染色体)
N1: 1 0 1 1 N2: 1 1 0 1 N3: 1 0 0 0 N4: 0 1 1 0
00 1 1 11 1 0 11 0 1 01 0 1
适应函数 f (x1,x2)
14 27 21 11
若以这4个个体为群体,按求解的要求,适应函数值小的 染色体的生存概率较大,则能竞争上的是N1、 N3和N4点, 其交配方式如下:
编码、确定适应度函数 产生初始群体
计算各个体适应度值
满足终止条件?
是
确定最优个体 解码输出
结束
变异
交叉
否
选择
例 用遗传算法求min f (x1,x2)= x1 + x2 ,当x1和x2为整数时 的整数解,且0≤ x1 和x2≤15
解:若用4位二进制编码表示一个设计变量 xi,则一个 解(x1, x2)需用8位二进制编码表示:
2l 1
二进制解码方法
假设某一个体的编码是: x: bl bl-1 bl-2……b2b1
则对应的解码公式为:
x
umin
N4: 0 1 1 0 N1: 1 0 1 1 N4: 0 1 1 0 N3: 1 0 0 0
010 1 001 1 010 1 110 1
交配 交配
N1': 0 1 1 1 N2': 1 0 1 0 N3': 0 1 0 0 N4': 1 0 1 0
0 1 1 1 =14 0 0 0 1 =11 0 1 0 1 =9 1 1 0 1 =23
S.1 选择优化问题求解的一种编码;
S.2 随机产生N个染色体的初始群体{ pop(k) , k=0 } ;
S.3 对群体中的每个染色体popi(k)计算适应度函数
f i =fitness(popi(k))
S.4 若满足终止规则,则转向S.9,否则计算概率
pi
fi
N
i 1, 2,
,N
通过分别交换基因,实现了交配,得到了4个新个体N1'、 N2 ' 、 N3 '和N4 ' 。 若对某个体(例如N2 ' )的第一位进行基因变异(1→0), 可得N2": 0 0 1 0 0 0 0 1 (=3)
遗传算法4个组成部分: 编码和解码、适应函数、遗传算子和控制参数
§9.1 遗传优化算法
三. 算法的基本步骤: