2012-3-22 8
其他编码方法
格雷编码
将二进制编码通过一个变换而得， 将二进制编码通过一个变换而得，目的是克服二进制编码 中的Hamming悬崖的缺点。 悬崖的缺点。 中的 悬崖的缺点 设二进制串b 对应的Gray码串为 1 a2 …al ，则 码串为a 设二进制串 1 b2…bl，对应的 码串为 二进制编码到Gray码的变换为 二进制编码到 码的变换为
0000100111 0100100010 0100100001 1000000111 1000000001 0000100111 0101100010 0100100001 1000000101 1000000001
6. 变异运算
重复3,4,5,6步骤
Y Y
y=x2
y=x2
1023
X
1023
X
第3代
i=l 1
Umax − umin 2l − 1
70352× = - 0.3 + 70352×(12.1+3)/(218-1) = 1.052426
二进制编码特点
二进制编码优点： 二进制编码优点： 1）简单易行 ） 2）便于模式定理进行分析 模式定理进行分析 ）便于模式定理 二进制编码缺点： 二进制编码缺点： 1）相邻整数的二进制编码可能具有很大的 ） Hamming距离，将降低遗传算子的搜索效率。 距离， 距离 将降低遗传算子的搜索效率。 2）缺乏精度可调功能。 ）缺乏精度可调功能。 3）对于高维优化问题，会导致很长的串长。 ）对于高维优化问题，会导致很长的串长。
第5步：适应度函数F(X) f(x)=x2 F(xi)=f(xi)/∑(f(xi) 第6步：设计遗传算子 1.选择算子：采用轮盘赌方式 2.交叉算子：概率pc=0.6 3.变异算子：概率pm=0.001
第7步：运行参数 1.种群大小 2.遗传代数 3.初始种群
开始运算 第4步：解的解码方案： x=b9*29+b8*28+…+b1*21+b0
Y
y=x2
4. 选择运算
x2=34： x4=295 x4=295 x5=513 x5=513 x2=34： x4=295 x4=295 x5=513 x5=513 x2=39： x4=290 x4=289 x5=519 x5=513
1023
X
5.交叉运算
x2=39： x4=290 x4=289 x5=519 x5=513 x2=39： x4=354 x4=289 x5=517 x5=513
Y Y
第5代
y=x2
y=x2
1023
X
1023
X
第15代
第30代
第1步：决策变量和约束条件 决策变量 x, 约束条件x整数且：0<=x<=1023 第2步：优化模型的目标函数 y=f(x)=x2 求其最大值 第3步：解的编码方案： 采用10位二进制编码，即 b9b8……b1b0 0：0000000000 1：0000000001 2：0000000010 3: 0000000011 … 1023: 1111111111
1.首先随机产生一组解，称为初始种群。种群大小为5. ｛2，34，47，295，513｝
1023 X
y=x2
2.根据设计的编码原则，把他们转换为二进制编码， 长度为10 x1=2： 0000000010 x2=34： 0000100010 x3=47： 0000101111 x4=295 0100100111 x5=513 1000000001
遗传算法例子
• 求解整数区间［0,1023］上的二次函数y=x2的最 大值。 解空间。 • 可能的解为：{0,1,2,…,1023}，称为解空间 解空间
Y
y=x2
1023
2012-3-22
X
1
遗传算法过程
求解整数区间［0,1023］上的二次函数y=x2的最大值。 可能的解为：{0,1,2,…,1023}，解空间 Y 解空间。 解空间
2012-3-22 2
3. 计算每个解的适应度 F(xi)=f(xi)/∑(f(xi)
F(2)=0.001% F(34)=0.327% F(47)= 0.625% F(295)=24.614% F(513)=74.433% 0000100010 0100100111 0100100111 1000000001 1000000001 0000100010 0100100111 0100100111 1000000001 1000000001 0000100111 0100100010 0100100001 1000000111 1000000001
初始化初始种群（编码成位串形式） 初始化初始种群（编码成位串形式）
计算每一个染色体（个体） 计算每一个染色体（个体）的适应值
是否满足 优化准则
Yes
输出结果
No 选择
遗 传 算 子
交叉
变异
产生新一代种群
遗传算法的处理流程图
举例 设 -3.0 ≤ x ≤ 12.1 , 精度要求 umax − umin δ=1/10000，由公式： ，由公式：
δ= 2l − 1 2l = Umax − umin +1 δ 12.1 + 3.0 +1 = 1/10000 = < 151001 < 218 x需要 位 {0/1} 符号表示。 如：010001001011010000 需要18位 符号表示。 需要 解码： 解码： x = umin + ( Σ bi · 2i-1) ·
b1, if i = 1 ai = bi −1 ⊕ bi , if i > 1
2012-3-22
9