遗传算法医学宣教专家讲座

第四章遗传算法（续）

智能优化计算数学与统计学院

2013年遗传算法医学宣教专家讲座第1页4.1遗传算法介绍

4.1.1遗传算法产生与发展

4.1.2生物进化理论和遗传学基本知识

4.1.3遗传算法思绪与特点

4.1.4遗传算法基本操作

4.1.5遗传算法应用4.2基本遗传算法

4.2.1简单函数优化实例

4.2.2遗传基因型

4.2.3适应度函数及其尺度变换

4.2.4遗传操作——选择

4.2.5遗传操作——交叉/基因重组

4.2.6遗传操作——变异

4.2.7算法设计与实现

4.2.8模式定理智能优化计算数学与统计学院

2013年遗传算法医学宣教专家讲座第2页4.3遗传算法改进

4.3.1CHC算法

4.3.2自适应遗传算法

4.3.3基于小生境技术遗传算法4.4遗传算法应用

4.4.1处理带约束函数优化问题

4.4.2处理多目标优化问题

4.4.3处理组合优化问题

4.4.4遗传算法在过程建模中应用

4.4.5遗传算法在模式识别中应用智能优化计算数学与统计学院

2013年遗传算法医学宣教专家讲座第3页4.2基本遗传算法

智能优化计算数学与统计学院

2013年问题提出一元函数求最大值：4.2.1简单函数优化实例

遗传算法医学宣教专家讲座第4页4.2基本遗传算法

智能优化计算数学与统计学院

2013年问题提出用微分法求取f(x)最大值：解有没有穷多个：4.2.1简单函数优化实例

遗传算法医学宣教专家讲座第5页4.2基本遗传算法

智能优化计算数学与统计学院

2013年问题提出当i为奇数时xi对应局部极大值点，i为偶数时xi对应局部极小值。x19即为区间[-1,2]内最大值点：此时，函数最大值f(x19)比f(1.85)=3.85稍大。4.2.1简单函数优化实例

遗传算法医学宣教专家讲座第6页4.2基本遗传算法

智能优化计算数学与统计学院

2013年编码表现型：x基因型：二进制编码（串长取决于求解精度）

串长与精度之间关系：若要求求解精度到6位小数，区间长度为2-(-1)＝3，即需将区间分为3/0.000001=3×106等份。所以编码二进制串长应为22位。4.2.1简单函数优化实例

遗传算法医学宣教专家讲座第7页4.2基本遗传算法

智能优化计算数学与统计学院

2013年产生初始种群产生方式：随机产生结果：长度为22二进制串产生数量：种群大小（规模），如30，50，…111101001110000101100011001100111010101011101010100011110010000100101111001001110011100100011001010011000000110000011010010000000000……4.2.1简单函数优化实例

遗传算法医学宣教专家讲座第8页4.2基本遗传算法

智能优化计算数学与统计学院

2013年计算适应度不一样问题有不一样适应度计算方法本例：直接用目标函数作为适应度函数①将某个体转化为[-1,2]区间实数：

s=<1000101110110101000111>→x=0.637197②计算x函数值（适应度）：

f(x)=xsin(10πx)+2.0=2.5863454.2.1简单函数优化实例

遗传算法医学宣教专家讲座第9页4.2基本遗传算法

智能优化计算数学与统计学院

2013年计算适应度

二进制与十进制之间转换：第一步，将一个二进制串（b21b20…b0）转化为10进制数：第二步，x’对应区间[-1,2]内实数：4.2.1简单函数优化实例

(0000000000000000000000)→-1(1111111111111111111111)→2遗传算法医学宣教专家讲座第10页4.2基本遗传算法

智能优化计算数学与统计学院

2013年遗传操作选择：轮盘赌选择法；交叉：单点交叉；变异：小概率变异4.2.1简单函数优化实例

遗传算法医学宣教专家讲座第11页4.2基本遗传算法

智能优化计算数学与统计学院

2013年模拟结果

设置参数：种群大小50；交叉概率0.75；变异概率0.05；最大代数200。

得到最正确个体：smax=<1111001100111011111100>;xmax=1.8506;f(xmax)=3.8503;4.2.1简单函数优化实例

遗传算法医学宣教专家讲座第12页4.2基本遗传算法

智能优化计算数学与统计学院

2013年模拟结果

进化过程：4.2.1简单函数优化实例

世代数自变量适应度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.8503遗传算法医学宣教专家讲座第13页4.2基本遗传算法

智能优化计算数学与统计学院

2013年编码标准完备性（completeness）：问题空间全部解都能表示为所设计基因型；健全性（soundness）：任何一个基因型都对应于一个可能解；非冗余性（non-redundancy）：问题空间和表示空间一一对应。4.2.2遗传基因型

遗传算法医学宣教专家讲座第14页4.2基本遗传算法

智能优化计算数学与统计学院

2013年各种编码方式二进制编码；浮点数编码；格雷码编码；符号编码；复数编码；DNA编码等。4.2.2遗传基因型

遗传算法医学宣教专家讲座第15页4.2基本遗传算法

智能优化计算数学与统计学院

2013年二进制编码与浮点数编码比较在交叉操作时，二进制编码比浮点数编码产生新个体可能性多，而且产生新个体不受父个体所组成超体限制；在变异操作时，二进制编码种群稳定性比浮点数编码差。4.2.2遗传基因型

遗传算法医学宣教专家讲座第16页4.2基本遗传算法

智能优化计算数学与统计学院

2013年适应度函数主要性适应度函数选取直接影响遗传算法收敛速度以及能否找到最优解。普通而言，适应度函数是由目标函数变换而成，对目标函数值域某种映射变换称为适应度尺度变换（fitnessscaling）。4.2.3适应度函数及其尺度变换

遗传算法医学宣教专家讲座第17页4.2基本遗传算法

智能优化计算数学与统计学院

2013年几个常见适应度函数直接转换若目标函数为最大化问题：Fit(f(x))=f(x)若目标函数为最小化问题：Fit(f(x))=-f(x)4.2.3适应度函数及其尺度变换

遗传算法医学宣教专家讲座第18页4.2基本遗传算法

智能优化计算数学与统计学院

2013年几个常见适应度函数界限结构法1若目标函数为最大化问题：若目标函数为最小化问题：4.2.3适应度函数及其尺度变换

遗传算法医学宣教专家讲座第19页4.2基本遗传算法

智能优化计算数学与统计学院

2013年几个常见适应度函数界限结构法2若目标函数为最大化问题：若目标函数为最小化问题：

c为目标函数保守预计值。4.2.3适应度函数及其尺度变换

遗传算法医学宣教专家讲座第20页4.2基本遗传算法

智能优化计算数学与统计学院

2013年适应度函数作用适应度函数设计不妥有可能出现坑骗问题：（1）进化早期，个别超常个体控制选择过程；（2）进化末期，个体差异太小造成陷入局部极值。4.2.3适应度函数及其尺度变换

遗传算法医学宣教专家讲座第21页4.2基本遗传算法

智能优化计算数学与统计学院

2013年适应度函数设计单值、连续、非负、最大化合理、一致性计算量小通用性强4.2.3适应度函数及其尺度变换

遗传算法医学宣教专家讲座第22页4.2基本遗传算法

智能优化计算数学与统计学院

2013年适应度函数线性变换法

f’=α*f+β系数确实定满足以下条件：①f’avg=favg②f’max=cmultf’avg

cmult=1.0~2.04.2.3适应度函数及其尺度变换

遗传算法医学宣教专家讲座第23页4.2基本遗传算法

智能优化计算数学与统计学院

2013年适应度函数幂函数变换法

f’=fk

k与所求优化相关4.2.3适应度函数及其尺度变换

k遗传算法医学宣教专家讲座第24页4.2基本遗传算法

智能优化计算数学与统计学院

2013年适应度函数指数变换法

f’=e-af

a决定了复制强制性，其值越小，复制强制性就越趋向于那些含有最大适应性个体。4.2.3适应度函数及其尺度变换

α遗传算法医学宣教专家讲座第25页4.2基本遗传算法

智能优化计算数学与统计学院

2013年几个概念选择压力（selectionpressure）:最正确个体选中概率与平均个体选中概率比值；偏差（bias）：个体正规化适应度与其期望再生概率绝对差值；个体扩展（spread）：单个个体子代个数范围；多样化损失（lossofdiversity）：在选择阶段未选中个体数目占种群百分比；4.2.4遗传操作——选择

遗传算法医学宣教专家讲座第26页4.2基本遗传算法

智能优化计算数学与统计学院

2013年几个概念选择强度（selectionintensity）:将正规高斯分布应用于选择方法，期望平均适应度；选择方差（selectionvariance）：将正规高斯分布应用于选择方法，期望种群适应度方差。4.2.4遗传操作——选择

遗传算法医学宣教专家讲座第27页4.2基本遗传算法

智能优化计算数学与统计学院

2013年个体选择概率惯用分配方法按百分比适应度分配（proportionalfitnessassignment）某个体i，其适应度为fi，则其被选取概率Pi为：4.2.4遗传操作——选择

个体ff2P12.56.250.1821.01.000.0333.09.000.2641.21.440.0452.14.410.1360.80.640.0272.56.250.1881.31.690.0590.90.810.02101.83.240.09遗传算法医学宣教专家讲座第28页4.2基本遗传算法

智能优化计算数学与统计学院

2013年个体选择概率惯用分配方法基于排序适应度分配（rank-basedfitnessassignment）线性排序（byBaker）

μ为种群大小，i为个体序号，ηmax代表选择压力。4.2.4遗传操作——选择

遗传算法医学宣教专家讲座第29页4.2基本遗传算法

智能优化计算数学与统计学院

2013年个体选择概率惯用分配方法基于排序适应度分配（rank-basedfitnessassignment）非线性排序（byMichalewicz）i为个体序号，c为排序第一个体选择概率。4.2.4遗传操作——选择

遗传算法医学宣教专家讲座第30页4.2基本遗传算法

智能优化计算数学与统计学院

2013年惯用选择方法轮盘赌选择法（roulettewheelselection）

4.2.4遗传操作——选择

个体1234567891011适应度2.01.81.61.41.21.00.80.60.40.20.1选择概率0.180.160.150.130.110.090.070.060.030.020.0累计概率0.180.340.490.620.730.820.890.950.981.001.00遗传算法医学宣教专家讲座第31页4.2基本遗传算法

智能优化计算数学与统计学院

2013年惯用选择方法随机遍历抽样法（stochasticuniversalsampling）

4.2.4遗传操作——选择

个体1234567891011适应度2.01.81.61.41.21.00.80.60.40.20.1选择概率0.180.160.150.130.110.090.070.060.030.020.0累计概率0.180.340.490.620.730.820.890.950.981.001.00遗传算法医学宣教专家讲座第32页4.2基本遗传算法

智能优化计算数学与统计学院

2013年惯用选择方法局部选择法（localselection）(1)线形邻集4.2.4遗传操作——选择

遗传算法医学宣教专家讲座第33页4.2基本遗传算法

智能优化计算数学与统计学院

2013年惯用选择方法局部选择法（localselection）(2)两对角邻集4.2.4遗传操作——选择

遗传算法医学宣教专家讲座第34页4.2基本遗传算法

智能优化计算数学与统计学院

2013年惯用选择方法局部选择法（localselection）(2)两对角邻集4.2.4遗传操作——选择

遗传算法医学宣教专家讲座第35页4.2基本遗传算法

智能优化计算数学与统计学院

2013年惯用选择方法截断选择法（truncationselection）个体按适应度排列，只有优异个体能够称为父个体，参数为截断阀值（被选作父个体百分比）。4.2.4遗传操作——选择

截断阀值1％10％20％40％50％80％选择强度2.661.761.20.970.80.34遗传算法医学宣教专家讲座第36页4.2基本遗传算法

智能优化计算数学与统计学院

2013年惯用选择方法锦标赛选择法（tournamentselection）随机从种群中挑选一定数目个体，其中最好个体作为父个体，此过程重复进行完成个体选择。4.2.4遗传操作——选择

竞赛规模12351030选择强度00.560.851.151.532.04遗传算法医学宣教专家讲座第37页4.2基本遗传算法

智能优化计算数学与统计学院

2013年实值重组离散重组子个体每个变量能够按等概率随机地挑选父个体。4.2.5遗传操作——交叉/基因重组

父个体112

25

5父个体2123

4

34子个体1123

4

5子个体212

4

34遗传算法医学宣教专家讲座第38页4.2基本遗传算法

智能优化计算数学与统计学院

2013年实值重组中间重组子个体＝父个体1＋α×（父个体2－父个体1）

α是百分比因子，由[-d,1+d]上均匀分布地随机数产生。

d=0时为中间重组，普通取d=0.25。子代每个变量均产生一个α。4.2.5遗传操作——交叉/基因重组

遗传算法医学宣教专家讲座第39页4.2基本遗传算法

智能优化计算数学与统计学院

2013年实值重组中间重组

4.2.5遗传操作——交叉/基因重组

父个体112255父个体2123434子个体1子个体2α值样本10.51.1-0.1α值样本20.10.80.512＋0.5×（123－12）=67.567.525＋1.1×（4－25）=1.91.92.112＋0.1×（123－12）=23.123.18.219.5遗传算法医学宣教专家讲座第40页4.2基本遗传算法

智能优化计算数学与统计学院

2013年实值重组中间重组

4.2.5遗传操作——交叉/基因重组

遗传算法医学宣教专家讲座第41页4.2基本遗传算法

智能优化计算数学与统计学院

2013年实值重组线性重组

4.2.5遗传操作——交叉/基因重组

父个体112255父个体2123434子个体1子个体2α值样本10.5α值样本20.112＋0.5×（123－12）=67.567.525＋0.5×（4－25）=14.514.519.512＋0.1×（123－12）=23.123.122.97.9遗传算法医学宣教专家讲座第42页4.2基本遗传算法

智能优化计算数学与统计学院

2013年实值重组线性重组

4.2.5遗传操作——交叉/基因重组

遗传算法医学宣教专家讲座第43页4.2基本遗传算法

智能优化计算数学与统计学院

2013年二进制交叉单点交叉

4.2.5遗传操作——交叉/基因重组

遗传算法医学宣教专家讲座第44页4.2基本遗传算法

智能优化计算数学与统计学院

2013年二进制交叉多点交叉

4.2.5遗传操作——交叉/基因重组

遗传算法医学宣教专家讲座第45页4.2基本遗传算法

智能优化计算数学与统计学院

2013年二进制交叉均匀交叉

4.2.5遗传操作——交叉/基因重组

父个体101110011010

父个体210101100101子个体11

11

011

11

1

1

1子个体20

01

100

00

0

0

0

样本101100011010样本210011100101遗传算法医学宣教专家讲座第46页4.2基本遗传算法

智能优化计算数学与统计学院

2013年实值变异普通采取：二进制变异

4.2.6遗传操作——变异

遗传算法医学宣教专家讲座第47页4.2基本遗传算法

智能优化计算数学与统计学院

2013年主程序

4.2.7算法设计与实现

%用遗传算法进行简单函数优化clearbn=22;%个体串长度inn=50;%初始种群大小gnmax=200;%最大代数pc=0.75;%交叉概率pm=0.05;%变异概率Continue…遗传算法医学宣教专家讲座第48页4.2基本遗传算法

智能优化计算数学与统计学院

2013年主程序

4.2.7算法设计与实现

%产生初始种群s=round(rand(inn,bn));%计算适应度,返回适应度f和累积概率p[f,p]=objf(s);Continue…遗传算法医学宣教专家讲座第49页4.2基本遗传算法

智能优化计算数学与统计学院

2013年主程序

4.2.7算法设计与实现

gn=1;whilegn<gnmax+1forj=1:2:inn%选择操作seln=sel(s,p);%交叉操作scro=cro(s,seln,pc);scnew(j,:)=scro(1,:);scnew(j+1,:)=scro(2,:);%变异操作smnew(j,:)=mut(scnew(j,:),pm);smnew(j+1,:)=mut(scnew(j+1,:),pm);endContinue…遗传算法医学宣教专家讲座第50页4.2基本遗传算法

智能优化计算数学与统计学院

2013年主程序

4.2.7算法设计与实现

s=smnew;%产生了新种群%计算新种群适应度[f,p]=objf(s);

%统计当前代最好和平均适应度[fmax,nmax]=max(f);fmean=mean(f);ymax(gn)=fmax;ymean(gn)=fmean;Continue…遗传算法医学宣教专家讲座第51页4.2基本遗传算法

智能优化计算数学与统计学院

2013年主程序

4.2.7算法设计与实现

%统计当前代最正确个体x=n2to10(s(nmax,:));xx=-1.0+x*3/(power(2,bn)-1);xmax(gn)=xx;

gn=gn+1endgn=gn-1;Continue…遗传算法医学宣教专家讲座第52页4.2基本遗传算法

智能优化计算数学与统计学院

2013年主程序

4.2.7算法设计与实现

%绘制曲线subplot(2,1,1);plot(1:gn,[ymax;ymean]);title('历代适应度改变','fonts',10);legend('最大适应度','平均适应度');string1=['最终适应度',num2str(ymax(gn))];gtext(string1);subplot(2,1,2);plot(1:gn,xmax,'r-');legend('自变量');string2=['最终自变量',num2str(xmax(gn))];gtext(string2);End遗传算法医学宣教专家讲座第53页4.2基本遗传算法

智能优化计算数学与统计学院

2013年计算适应度和累计概率函数

4.2.7算法设计与实现

%计算适应度函数function[f,p]=objf(s);r=size(s);%读取种群大小inn=r(1);%有inn个个体bn=r(2);%个体长度为bnContinue…遗传算法医学宣教专家讲座第54页4.2基本遗传算法

智能优化计算数学与统计学院

2013年计算适应度和累计概率函数

4.2.7算法设计与实现

fori=1:innx=n2to10(s(i,:));%将二进制转换为十进制xx=-1.0+x*3/(power(2,bn)-1);%转化为[-1,2]区间实数f(i)=ft(xx);%计算函数值，即适应度endf=f';Continue…遗传算法医学宣教专家讲座第55页4.2基本遗传算法

智能优化计算数学与统计学院

2013年计算适应度和累计概率函数

4.2.7算法设计与实现

%计算选择概率fsum=0;fori=1:innfsum=fsum+f(i)*f(i);endfori=1:innps(i)=f(i)*f(i)/fsum;endContinue…遗传算法医学宣教专家讲座第56页4.2基本遗传算法

智能优化计算数学与统计学院

2013年计算适应度和累计概率函数

4.2.7算法设计与实现

%计算累积概率p(1)=ps(1);fori=2:innp(i)=p(i-1)+ps(i);endp=p';Backtomain.m遗传算法医学宣教专家讲座第57页4.2基本遗传算法

智能优化计算数学与统计学院

2013年计算目标函数值函数

4.2.7算法设计与实现

%目标函数functiony=ft(x);y=x.*sin(10*pi*x)+2;Backtoobjf.m遗传算法医学宣教专家讲座第58页4.2基本遗传算法

智能优化计算数学与统计学院

2013年选择操作函数

4.2.7算法设计与实现

%“选择”操作functionseln=sel(s,p);inn=size(p,1);%从种群中选择两个个体fori=1:2r=rand;%产生一个随机数prand=p-r;j=1;whileprand(j)<0j=j+1;endseln(i)=j;%选中个体序号endBacktomain.m遗传算法医学宣教专家讲座第59页4.2基本遗传算法

智能优化计算数学与统计学院

2013年交叉操作函数

4.2.7算法设计与实现

%“交叉”操作functionscro=cro(s,seln,pc);r=size(s);inn=r(1);bn=r(2);pcc=pro(pc);%依据交叉概率决定是否进行交叉操作，1则是，0则否Continue…遗传算法医学宣教专家讲座第60页4.2基本遗传算法

智能优化计算数学与统计学院

2013年交叉操作函数

4.2.7算法设计与实现

ifpcc==1chb=round(rand*(bn-2))+1;%在[1,bn-1]范围内随机产生一个交叉位scro(1,:)=[s(seln(1),1:chb)s(seln(2),chb+1:bn)];scro(2,:)=[s(seln(2),1:chb)s(seln(1),chb+1:bn)];elsescro(1,:)=s(seln(1),:);scro(2,:)=s(seln(2),:);endBacktomain.m遗传算法医学宣教专家讲座第61页4.2基本遗传算法

智能优化计算数学与统计学院

2013年变异操作函数

4.2.7算法设计与实现

%“变异”操作functionsnnew=mut(snew,pm);r=size(snew);bn=r(2);snnew=snew;Continue…遗传算法医学宣教专家讲座第62页4.2基本遗传算法

智能优化计算数学与统计学院

2013年变异操作函数

4.2.7算法设计与实现

pmm=pro(pm);%依据变异概率决定是否进行变异操作，1则是，0则否ifpmm==1chb=round(rand*(bn-1))+1;%在[1,bn]范围内随机产生一个变异位snnew(chb)=abs(snew(chb)-1);endBacktomain.m遗传算法医学宣教专家讲座第63页4.2基本遗传算法

智能优化计算数学与统计学院

2013年运行程序

4.2.7算法设计与实现

遗传算法医学宣教专家讲座第64页4.2基本遗传算法

智能优化计算数学与统计学院

2013年运行程序

4.2.7算法设计与实现

遗传算法医学宣教专家讲座第65页4.2基本遗传算法

智能优化计算数学与统计学院

2013年运行程序

4.2.7算法设计与实现

遗传算法医学宣教专家讲座第66页4.2基本遗传算法

智能优化计算数学与统计学院

2013年运行程序

4.2.7算法设计与实现

遗传算法医学宣教专家讲座第67页4.2基本遗传算法

智能优化计算数学与统计学院

2013年模式将种群中个体即基因串中相同样板称为模式。在二进制编码串中，模式是基于三个字符集（0，1，*）字符串，符号*代表任意字符，即0或1。如模式*1*描述了一个四个元子集{010，011，110，111}。4.2.8模式定理

遗传算法医学宣教专家讲座第68页4.2基本遗传算法

智能优化计算数学与统计学院

2013年模式阶和定义距模式H中确定位置个数称为模式H模式阶，记作O(H)，如O(011*1*)=4。模式阶用来反应不一样模式间确定性差异，模式阶越高，模式确实定性就越高，所匹配样本个数就越少。4.2.8模式定理

遗传算法医学宣教专家讲座第69页4.2基本遗传算法

智能优化计算数学与统计学院

2013年模式阶和定义距模式H中第一个确定位置和最终一个确定位置之间距离称为模式定义距，记作δ(H)，如

δ(011*1**)=4。阶数相同模式会有不一样性质，定义距就反应了这种性质差异。4.2.8模式定理

遗传算法医学