演化计算专题讲座—1

―It is not the strongest of species that survive, nor the most intelligent, but the one most adaptБайду номын сангаасble to change.‖ ―适者生存”（Survival of the fittest） Charles Darwin(1809-1882)
2.2. 适应值函数(fitness function)
2.2.1 采用目标函数做适应值函数 2.2.2 通过对函数值进行变换得到适应值函数
2.3. 遗传操作
2.3.1 选择（selection）
• 精英选择（elitist selection） • 锦标赛选择（tournament selection） • 轮盘赌选择 （roulette wheel selection）
1. 什么是演化计算？
演化计算（ Evolutionary Computation，也称“进 化计算”,简称EC）是用计算机模拟大自然的演化过 程，特别是生物进化过程，来求解复杂问题的一类智 能计算系统。
2. 为什么要进行演化计算？
Many scientists and engineers now use the paradigms of evolutionary computation to tackle problems that are either intractable or unrealistically time consuming to solve through traditional computational strategies. ---------Baeck《 Handbook of Evolutionary Computation》
（1）.随机初始化种群（产生一组初始解）
V1 =[ 4.954222, 0.169225], V2 =[-4.806207,-1.630757] V3 =[ 4.672536,-1.867275], V4 =[ 1.897794,-0.196387] V5 =[-2.127598, 0.750603], V6 =[-3.832667,-0.959655] V7 =[-3.792383, 4.064608], V8 =[ 1.182745,-4.712821] V9 =[ 3.812220,-3.441115], V10=[-4.515976, 4.539171]
x1
x2
• Vi称之为个体,10称之为群体规模,x1,x2为基因
(2)计算群体中个体的适应值(fitness)
eval(v1)=f(4.954222, 0.169225)=10.731945, eval(v2)= f(-4.806207,-1.630757)=12.110259 eval(v3)= f(4.672536,-1.867275)=11.788221 eval(v4)= f(1.897794,-0.196387)=5.681900 eval(v5)= f(-2.127598, 0.750603)=6.757691 eval(v6)= f(-3.832667,-0.959655)=9.194728 eval(v7)=f( -3.792383, 4.064608)=11.795402 eval(v8)= f(1.182745,-4.712821)=11.559363 eval(v9)= f(3.812220,-3.441115)=12.279653 eval(v10)= f(-4.515976, 4.539171)=14.251764
by Institute of Physics Publishing; May 2003.
八阶非线性方程组: I1+I2+I3+I4=a(1); I1*cos(theta1)+I2*cos(theta2)+I3*cos(theta3)+I4*cos(theta4)=a(2); I1*sin(theta1)+I2*sin(theta2)+I3*sin(theta3)+I4*sin(theta4)=a(3); I1*cos(theta1)*cos(theta1)+I2*cos(theta2)*cos(theta2)+I3*cos(theta 3)*cos(theta3)+I4*cos(theta4)*cos(theta4)=a(4); I1*cos(theta1)*sin(theta1)+I2*cos(theta2)*sin(theta2)+I3*cos(theta3 )*sin(theta3)+I4*cos(theta4)*sin(theta4)=a(5); I1^2+I2^2+I3^2+I4^2=a(6); I1^2*cos(theta1)+I2^2*cos(theta2)+I3^2*cos(theta3)+I4^2*cos(theta 4)=a(7); I1^2*sin(theta1)+I2^2*sin(theta2)+I3^2*sin(theta3)+I4^2*sin(theta4) =a(8);
的演化算法的框架为
while (不满足停止准则) do
{由P(t)通过遗传操作并通过选择形成新的种群P(t+1)； 计算P(t+1)中个体的适应值； t := t+1; } END；
注：其中 N 为种群P(t )的大小，称为群体规模。
2.1. 编码(code)
2.1.1 二进制编码 2.1.2 实数编码 2.1.3其它编码
3. 演化计算的研究内容
• 演化算法 • 演化计算的应用 • 演化计算的理论
第二章 演化算法（Evolutionary Algorithm）
1. 演化算法
•
•
•
•
遗传算法（Genetic Algorithm，简称GA） J.H.Holland (1975) 演化规划（Evolutionary Programming，简称EP） L.J.Fogel (1966) 演化策略（Evolutionary Strategies，简称ES） I.Rechenberg,H-P.Schwefel (1963) 遗传程序设计（Genetic Programming，简称GP） J.R.Koza (1992)
2.3.3 变异（mutation）
2.3.3.1 二进制编码的变异策略 • 点变异（bitwise mutation） • 均匀变异（uniform mutation）
2.3.3.2 实数编码的变异策略 • 均匀变异（uniform mutation） • 高斯变异 （Gaussian mutation）
以上 几个分支在算法实现方面具有一些细微的差别，但它们具有一个共 同的特点，即都是借助生物演化的思想和原理来解决实际题，所以在90年代 ， 这些分支互相融合，就形成了一门新的学科—演化计算。
2. 演化算法的框架
求解优化问题
ALGORITHM: begin t:=0; 初始化群体P(t)={X1，X2，…，XN}； 计算P(t) 中的个体的适应值；
演化计算专题讲座
武汉大学数学与统计学院 2010.12
参考文献
一、可查阅的书籍 1、[美]Z.Michalewicz著.周家驹,何险峰等译,<<演化程序---遗传算法和数据编码的结合>>, 科学出版社,2000年. 2. [日]玄光男,程润伟著.汪定伟,唐加福黄敏译.<<遗传算法与工程设计>>, 科学出版社,2000 年. 3. 张文修 梁怡编著，遗传算法的数学基础，西安交通大学出版社，2000年. 4.李敏强 等著，遗传算法的基本理论与应用，科学出版社，2002年。 二. 网上可查询的资料 1. 武汉大学校园网电子资源 (1).中国期刊网 关键词:遗传算法,进化算法 (2)IEEE/IEE Electronic library Key word: Evolutionary Computation/Evolutionary algorithm Journals: IEEE Transactions on Evolutionary Computation， Evolutionary Computation， European Journal of Operational Research, Theoretical Computer Science International Conference： CEC, GECCO, PPSN, FOGA 2.宽带网
引言 什么是智能计算
• 智能计算（Intelligent Computing, IC) 或 计算智能 (Computational Intelligence, CI)： 主要指能解决大规模的复杂实际问题的有重大影响的几 类关键技术， 或者说当今国际上最流行、最热门的几种计 算方法。 其中有： （1）演化计算（Evolutionary Computation) ： 在微观或宏观 两个不同层次上模仿生物的演化过程。 （2）神经网络(Neural Networks)：在微观层次上模仿脑神经 的功能。 （3）模糊系统(Fuzzy Systems ，Fuzzy Computing)对人在 日常生活中进行近似或非精确推断、决策能力的模拟。
• 各种智能计算方法的共同特点： （1）它们大都引入了随机因素，因此具有不确定性，甚至同时 支持相互矛盾的途径去求解。 （2）它们大都具有自适应机制的动力体系， 有时在计算过程中 体系结构还在不断调整。 （3）这些算法都是针对通用的一般目标而设计的，他们不同于 针对特殊问题而设计的算法。
第一章 什么是演化计算
第三章 算 法 举 例
• 例1：Ackley函数：
1 2 2 1 2 min f ( x1 , x2 ) 20 exp(0.2 x j ) exp( cos(2x j )) 20 e n j 1 n j 1 5 x j 5, j 1, 2.
最优解为
• 这三种智能计算方法已成为目前智能技术的主流。 • 1994年， 关于演化计算、神经网络、模糊系统的三个 IEEE国际学术会议在美国FLORID州联合举行了“首届 计算智能世界大会” （The First IEEE World Congress on Computational Intelligence, WCCI’94), 把本来是不 同学科领域的专家们聚集在一起，进行了题为“模仿生 命：计算智能 （ Computational Intelligence： Imitating the Life)主题讨论会，取得了关于计算智能 的共识。以后每四年召开一次。
其中a(1),a(2),…,a(8) 有三组数据: • (1.804800000000000e+004 1.365736315298172e+004 5.497052905295088e+003 1.450829635946082e+004 3.157294805334107e+003 1.055437940000000e+008 9.159875125016867e+007 3.347057899613227e+007) • (1.624320000000000e+004 1.229162683768355e+004 4.947347614765579e+003 1.305746672351474e+004 2.841565324800696e+003 9.498941459999999e+007 8.243887612515180e+007 3.012352109651904e+007) • (1.985280000000000e+004 1.502309946827989e+004 6.046758195824596e+003 1.595912599540690e+004 3.473024285867518e+003 1.160981734000000e+008 1.007586263751855e+008 3.681763689574549e+007)
2.3.2 杂交（crossover）
2.3.2.1 二进制编码的杂交策略 • 单点杂交（one-point crossover） • 多点杂交（multi-point crossover） • 均匀杂交（uniform crossover）
2.3.2.2 实数编码的杂交策略 • 算术杂交（arithmetic crossover） • 多父体杂交（multi-parent crossover）