遗传算法介绍专家讲座

第4章基于遗传算法随机优化搜索4.1基本概念4.2基本遗传算法4.3遗传算法应用举例4.4遗传算法特点与优势

遗传算法介绍专家讲座第1页

4.1基本概念

1.个体与种群

●个体就是模拟生物个体而对问题中对象（普通就是问题解）一个称呼，一个个体也就是搜索空间中一个点。

●

种群(population)就是模拟生物种群而由若干个体组成群体,它普通是整个搜索空间一个很小子集。遗传算法介绍专家讲座第2页

2.适应度与适应度函数

●

适应度(fitness)就是借鉴生物个体对环境适应程度,而对问题中个体对象所设计表征其优劣一个测度。

●适应度函数(fitnessfunction)就是问题中全体个体与其适应度之间一个对应关系。它普通是一个实值函数。该函数就是遗传算法中指导搜索评价函数。

遗传算法介绍专家讲座第3页3.染色体与基因

染色体（chromosome）就是问题中个体某种字符串形式编码表示。字符串中字符也就称为基因（gene）。比如：个体染色体

9----

1001（2，5，6）----010101110遗传算法介绍专家讲座第4页4.遗传操作亦称遗传算子(geneticoperator)，就是关于染色体运算。遗传算法中有三种遗传操作:

●

选择-复制(selection-reproduction)

●

交叉(crossover，亦称交换、交配或杂交)

●

变异(mutation，亦称突变)

遗传算法介绍专家讲座第5页

选择-复制通常做法是：对于一个规模为N种群S,按每个染色体xi∈S选择概率P(xi)所决定选中机会,分N次从S中随机选定N个染色体,并进行复制。

这里选择概率P(xi)计算公式为遗传算法介绍专家讲座第6页

交叉就是交换两个染色体一些位上基因。

s1′=01000101,s2′=10011011能够看做是原染色体s1和s2子代染色体。

比如,设染色体s1=01001011,s2=10010101,交换其后4位基因,即遗传算法介绍专家讲座第7页

变异就是改变染色体某个(些)位上基因。比如,设染色体s=11001101将其第三位上0变为1,即s=11001101→11101101=s′。s′也能够看做是原染色体s子代染色体。遗传算法介绍专家讲座第8页4.2基本遗传算法

遗传算法基本流程框图生成初始种群计算适应度选择-复制交叉变异生成新一代种群终止?结束遗传算法介绍专家讲座第9页

算法中一些控制参数：

■

种群规模

■

最大换代数

■

交叉率(crossoverrate)就是参加交叉运算染色体个数占全体染色体总数百分比，记为Pc,取值范围普通为0.4～0.99。

■

变异率(mutationrate)是指发生变异基因位数所占全体染色体基因总位数百分比，记为Pm，取值范围普通为0.0001～0.1。遗传算法介绍专家讲座第10页基本遗传算法

步1在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T；

步2随机产生U中N个个体s1,s2,…,sN，组成初始种群S={s1,s2,…,sN}，置代数计数器t=1；

步3计算S中每个个体适应度f()；

步4若终止条件满足，则取S中适应度最大个体作为所求结果，算法结束。遗传算法介绍专家讲座第11页

步5按选择概率P(xi)所决定选中机会，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得N个染色体组成群体S1；

步6按交叉率Pc所决定参加交叉染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生新染色体代替原染色体，得群体S2；遗传算法介绍专家讲座第12页

步7按变异率Pm所决定变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生新染色体代替原染色体，得群体S3；

步8

将群体S3作为新一代种群，即用S3代替S，t=t+1，转步3；

遗传算法介绍专家讲座第13页4.3遗传算法应用举例

例4.1利用遗传算法求解区间［0,31］上二次函数y=x2最大值。

y=x2

31

XY遗传算法介绍专家讲座第14页

分析

原问题可转化为在区间［0,31］中搜索能使y取最大值点a问题。那么，［0,31］中点x就是个体,函数值f(x)恰好就能够作为x适应度，区间［0,31］就是一个(解)空间。这么,只要能给出个体x适当染色体编码,该问题就能够用遗传算法来处理。遗传算法介绍专家讲座第15页

解(1)设定种群规模,编码染色体，产生初始种群。将种群规模设定为4；用5位二进制数编码染色体；取以下个体组成初始种群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)

(2)定义适应度函数,取适应度函数：f(x)=x2

遗传算法介绍专家讲座第16页

(3)计算各代种群中各个体适应度,并对其染色体进行遗传操作,直到适应度最高个体(即31（11111）)出现为止。

遗传算法介绍专家讲座第17页首先计算种群S1中各个体

s1=13(01101),s2=24(11000)

s3=8(01000),s4=19(10011)适应度f(si)。轻易求得f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361遗传算法介绍专家讲座第18页再计算种群S1中各个体选择概率。选择概率计算公式为由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31遗传算法介绍专家讲座第19页赌轮选择示意s40.31s20.49s10.14s30.06●赌轮选择法遗传算法介绍专家讲座第20页

在算法中赌轮选择法可用下面子过程来模拟:①在［0,1］区间内产生一个均匀分布随机数r。②若r≤q1,则染色体x1被选中。③若qk-1<r≤qk(2≤k≤N),则染色体xk被选中。其中qi称为染色体xi(i=1,2,…,n)积累概率,其计算公式为遗传算法介绍专家讲座第21页选择-复制

设从区间［0,1］中产生4个随机数以下:

r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503

染色体适应度选择概率积累概率选中次数s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001遗传算法介绍专家讲座第22页于是，经复制得群体：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）遗传算法介绍专家讲座第23页交叉

设交叉率pc=100%，即S1中全体染色体都参加交叉运算。设s1’与s2’配对，s3’与s4’配对。分别交换后两位基因，得新染色体：s1’’=11001（25）,s2’’=01100（12）

s3’’=11011（27）,s4’’=10000（16）

遗传算法介绍专家讲座第24页变异设变异率pm=0.001。这么，群体S1中共有5×4×0.001=0.02位基因能够变异。0.02位显然不足1位，所以本轮遗传操作不做变异。遗传算法介绍专家讲座第25页

于是，得到第二代种群S2：

s1=11001（25）,s2=01100（12）

s3=11011（27）,s4=10000（16）遗传算法介绍专家讲座第26页

第二代种群S2中各染色体情况

染色体适应度选择概率积累概率预计选中次数s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.001遗传算法介绍专家讲座第27页

假设这一轮选择-复制操作中，种群S2中4个染色体都被选中，则得到群体：

s1’=11001（25）,s2’=01100（12）

s3’=11011（27）,s4’=10000（16）

做交叉运算，让s1’与s2’，s3’与s4’

分别交换后三位基因，得

s1’’=11100（28）,s2’’=01001（9）

s3’’=11000（24）,s4’’=10011（19）

这一轮依然不会发生变异。

遗传算法介绍专家讲座第28页于是，得第三代种群S3：s1=11100（28）,s2=01001（9）

s3=11000（24）,s4=10011（19）

遗传算法介绍专家讲座第29页第三代种群S3中各染色体情况

染色体适应度选择概率积累概率预计选中次数s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.001遗传算法介绍专家讲座第30页设这一轮选择-复制结果为：s1’=11100（28）,s2’=11100（28）

s3’=11000（24）,s4’=10011（19）

做交叉运算，让s1’与s4’，s2’与s3’

分别交换后两位基因，得

s1’’=11111（31）,s2’’=11100（28）

s3’’=11000（24）,s4’’=10000（16）

这一轮依然不会发生变异。遗传算法介绍专家讲座第31页于是，得第四代种群S4：

s1=11111（31）,s2=11100（28）

s3=11000（24）,s4=10000（16）

遗传算法介绍专家讲座第32页显然，在这一代种群中已经出现了适应度最高染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终止果输出。然后，将染色体“11111”解码为表现型，即得所求最优解：31。将31代入函数y=x2中，即得原问题解，即函数y=x2最大值为961。

遗传算法介绍专家讲座第33页YYy=x2

8131924

X第一代种群及其适应度y=x2

12162527

XY第二代种群及其适应度y=x2

9192428

XY第三代种群及其适应度y=x2

16242831

X第四代种群及其适应度遗传算法介绍专家讲座第34页

例4.2用遗传算法求解TSP。分析

因为其任一可能解——一个正当城市序列，即n个城市一个排列，都能够事先结构出来。于是，我们就能够直接在解空间（全部正当城市序列）中搜索最正确解。这正适适用遗传算法求解。遗传算法介绍专家讲座第35页

（1）定义适应度函数我们将一个正当城市序列s=（c1,c2,…,cn,cn+1）(cn+1就是c1)作为一个个体。这个序列中相邻两城之间距离之和倒数就可作为对应个体s适应度，从而适应度函数就是遗传算法介绍专家讲座第36页

（2）对个体s=（c1,c2,…,cn,cn+1）进行编码。但对于这么个体怎样编码却不是一件直截了当事情。因为假如编码不妥，就会在实施交叉或变异操作时出现非法城市序列即无效解。比如，对于5个城市TSP，我们用符号A、B、C、D、E代表对应城市，用这5个符号序列表示可能解即染色体。遗传算法介绍专家讲座第37页然后进行遗传操作。设s1=（A,C,B,E,D,A），s2=（A,E,D,C,B,A）实施常规交叉或变异操作，如交换后三位，得s1’=（A,C,B,C,B,A），s2’=（A,E,D,E,D,A）或者将染色体s1第二位C变为E，得s1’’=（A,E,B,E,D,A）能够看出，上面得到s1’，s2’和s1’’都是非法城市序列。遗传算法介绍专家讲座第38页为此，对TSP必须设计适当染色体和对应遗传运算。实际上，人们针对TSP提出了许多编码方法和对应特殊化了交叉、变异操作，如次序编码或整数编码、随机键编码、部分映射交叉、次序交叉、循环交叉、位置交叉、反转变异、移位变异、交换变异等等。从而巧妙地用遗传算法处理了TSP