第七讲遗传算法

第七讲遗传算法第一页，共六十九页，2022年，8月28日英国的博物学家达尔文通过研究提出了被恩格斯赞誉为“19世纪自然科学三大发现”之一的生物进化学说。第二页，共六十九页，2022年，8月28日达尔文的“贝格尔号”考察路线太平洋印度洋亚洲欧洲非洲南美洲北美洲大洋州大西洋第三页，共六十九页，2022年，8月28日生物进化的过程和原因取食果实取食昆虫取食仙人掌取食种子取食昆虫喙凿状喙不变喙尖而长喙粗而尖加拉帕戈斯雀的进化第四页，共六十九页，2022年，8月28日长颈鹿的进化示意图第五页，共六十九页，2022年，8月28日环境实验灰色桦尺蛾黑色桦尺蛾未污染区放出只数496473重新捕捉只数6230重新捕捉百分比12.5%6.3%污染区放出只数201601重新捕捉只数32205重新捕捉百分比15.9%34.1%第六页，共六十九页，2022年，8月28日遗传算法（GeneticAlgorithm，简称GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算机算法，它由美国Holland教授1975年提出。遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适合并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位。一、遗传算法概述第七页，共六十九页，2022年，8月28日一、遗传算法概述基本思想：基于模仿生物界遗传学的遗传过程，把问题的参数用基因来表示，把问题的解用染色体来表示代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体。这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代，后代随机化地继承父代的最好特征，并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优解。第八页，共六十九页，2022年，8月28日一、遗传算法概述与传统的优化算法相比，遗传算法主要有以下几个不同之处遗传算法不是直接作用在参变量集上而是利用参变量集的某种编码遗传算法不是从单个点，而是从一个点的群体开始搜索；遗传算法利用适应值信息，无须导数或其它辅助信息；遗传算法利用概率转移规则，而非确定性规则。第九页，共六十九页，2022年，8月28日一、遗传算法概述遗传算法的优越性主要表现在：首先，它在搜索过程中不容易陷入局部最优，即使所定义的适应函数是不连续的、非规则的或有噪声的情况下，它也能以很大的概率找到整体最优解；其次，由于它固有的并行性，遗传算法非常适用于大规模并行计算机。第十页，共六十九页，2022年，8月28日一、遗传算法概述应用

遗传算法在自然科学、工程技术、商业、医学、社会科学等领域都有应用复杂数学函数的优化；半导体器件、飞行器、通信网络、天然气管道系统、汽轮机的设计；神经网络的设计与训练；生产的规划与排序；机器人的运动轨迹生成与运动学解；机器多故障诊断；自动装配系统的优化设计等。尤其适合于寻求多参数、多设计变量或多选择的复杂工程问题的最优数值解。第十一页，共六十九页，2022年，8月28日二、遗传学相关概念个体与种群●个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。

●种群(population)就是模拟生物种群而由若干个体组成的群体,它一般是整个搜索空间的一个很小的子集。第十二页，共六十九页，2022年，8月28日二、遗传学相关概念适应度与适应度函数●适应度(fitness)就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。●适应度函数(fitnessfunction)就是问题中的全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。

第十三页，共六十九页，2022年，8月28日二、遗传学相关概念染色体与基因

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

9----

1001（2，5，6）----010101110第十四页，共六十九页，2022年，8月28日二、遗传学相关概念遗传操作

亦称遗传算子(geneticoperator)，就是关于染色体的运算。遗传算法中有三种遗传操作:

●选择-复制(selection-reproduction)

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

●变异(mutation，亦称突变)第十五页，共六十九页，2022年，8月28日二、遗传学相关概念遗传学遗传算法数学1个体要处理的基本对象、结构也就是可行解2群体个体的集合被选定的一组可行解3染色体个体的表现形式可行解的编码4基因染色体中的元素编码中的元素5基因位某一基因在染色体中的位置元素在编码中的位置6适应值个体对于环境的适应程度，或在环境压力下的生存能力可行解所对应的适应函数值7种群被选定的一组染色体或个体根据入选概率定出的一组可行解8选择从群体中选择优胜的个体，淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解第十六页，共六十九页，2022年，8月28日二、遗传学相关概念遗传学遗传算法数学9交叉一组染色体上对应基因段的交换根据交叉原则产生的一组新解10交叉概率染色体对应基因段交换的概率（可能性大小）闭区间[0,1]上的一个值，一般为0.65~0.9011变异染色体水平上基因变化编码的某些元素被改变12变异概率染色体上基因变化的概率（可能性大小）开区间(0,1)内的一个值,一般为0.001~0.0113进化、适者生存个体进行优胜劣汰的进化，一代又一代地优化目标函数取到最大值，最优的可行解第十七页，共六十九页，2022年，8月28日三、简单遗传算法

选择-复制

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

这里的选择概率P(xi)的计算公式为第十八页，共六十九页，2022年，8月28日三、简单遗传算法s40.309s20.492s10.144s30.055指针轮盘法第十九页，共六十九页，2022年，8月28日三、简单遗传算法

交叉：就是互换两个染色体某些位上的基因。

s1′=01000101,s2′=10011011可以看做是原染色体s1和s2的子代染色体。

例如,设染色体s1=01001011,s2=10010101,交换其后4位基因,即第二十页，共六十九页，2022年，8月28日三、简单遗传算法变异：就是改变染色体某个(些)位上的基因。例如,设染色体s=11001101，将其第三位上的0变为1,即s=11001101→11101101=s′。s′也可以看做是原染色体s的子代染色体。第二十一页，共六十九页，2022年，8月28日三、简单遗传算法遗传算法基本步骤：把这些可行解置于问题的“环境”中，按适者生存的原则，选取较适应环境的“染色体”进行复制，并通过交叉、变异过程产生更适应环境的新一代“染色体”群把问题的解表示成“染色体”，在算法中就是以二进制编码的串，给出一群“染色体”，也就是假设的可行解经过这样的一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解第二十二页，共六十九页，2022年，8月28日三、简单遗传算法遗传算法具体步骤选择编码策略，把参数集合（可行解集合）转换染色体结构空间；定义适应度函数，便于计算适应值；确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数；随机产生初始化群体；第二十三页，共六十九页，2022年，8月28日三、简单遗传算法计算群体中的个体或染色体解码后的适应值；按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体；判断群体性能是否满足某一指标，或者已完成预定的迭代次数，不满足则返回第五步，或者修改遗传策略再返回第六步．第二十四页，共六十九页，2022年，8月28日遗传算法具体步骤产生初始群体是否满足终止条件得到结果是结束程序否计算每个个体的适应值以概率选择遗传算子选择一个个体复制到新群体选择两个个体进行

交叉插入到新群体选择一个个体进行变异插入到新群体得到新群体第二十五页，共六十九页，2022年，8月28日四、遗传算法应用举例1

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

y=x2

31

XY第二十六页，共六十九页，2022年，8月28日

分析

原问题可转化为在区间［0,31］中搜索能使y取最大值的点a的问题。那么，［0,31］中的点x就是个体,函数值f(x)恰好就可以作为x的适应度，区间［0,31］就是一个(解)空间。这样,只要能给出个体x的适当染色体编码,该问题就可以用遗传算法来解决。四、遗传算法应用举例1第二十七页，共六十九页，2022年，8月28日

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

(2)定义适应度函数,

取适应度函数：f(x)=x2

四、遗传算法应用举例1第二十八页，共六十九页，2022年，8月28日(3)计算各代种群中的各个体的适应度,并对其染色体进行遗传操作,直到适应度最高的个体(即31（11111）)出现为止。

四、遗传算法应用举例1第二十九页，共六十九页，2022年，8月28日

首先计算种群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四、遗传算法应用举例1第三十页，共六十九页，2022年，8月28日再计算种群S1中各个体的选择概率。选择概率的计算公式为

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31四、遗传算法应用举例1第三十一页，共六十九页，2022年，8月28日赌轮选择示意s40.31s20.49s10.14s30.06四、遗传算法应用举例1第三十二页，共六十九页，2022年，8月28日选择-复制

染色体适应度选择概率选中次数s1=011011690.141s2=110005760.492s3=01000640.060s4=100113610.311四、遗传算法应用举例1第三十三页，共六十九页，2022年，8月28日于是，经复制得群体：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）四、遗传算法应用举例1第三十四页，共六十九页，2022年，8月28日交叉

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

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

四、遗传算法应用举例1第三十五页，共六十九页，2022年，8月28日变异设变异率pm=0.001。这样，群体S1中共有5×4×0.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。四、遗传算法应用举例1第三十六页，共六十九页，2022年，8月28日

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

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

s3=11011（27）,s4=10000（16）四、遗传算法应用举例1第三十七页，共六十九页，2022年，8月28日

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

染色体适应度选择概率估计的选中次数s1=110016250.361s2=011001440.080s3=110117290.412s4=100002560.151四、遗传算法应用举例1第三十八页，共六十九页，2022年，8月28日假设这一轮选择-复制操作中，种群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）

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

四、遗传算法应用举例1第三十九页，共六十九页，2022年，8月28日于是，得第三代种群S3：s1=11100（28）,s2=01001（9）

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

四、遗传算法应用举例1第四十页，共六十九页，2022年，8月28日第三代种群S3中各染色体的情况

染色体适应度选择概率估计的选中次数s1=111007840.442s2=01001810.040s3=110005760.321s4=100113610.201四、遗传算法应用举例1第四十一页，共六十九页，2022年，8月28日设这一轮的选择-复制结果为：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）

这一轮仍然不会发生变异。四、遗传算法应用举例1第四十二页，共六十九页，2022年，8月28日于是，得第四代种群S4：

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

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

四、遗传算法应用举例1第四十三页，共六十九页，2022年，8月28日显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。

四、遗传算法应用举例1第四十四页，共六十九页，2022年，8月28日YYy=x2

8131924

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

12162527

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

9192428

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

16242831

X第四代种群及其适应度第四十五页，共六十九页，2022年，8月28日

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

由于其任一可能解——一个合法的城市序列，即n个城市的一个排列，都可以事先构造出来。于是，我们就可以直接在解空间（所有合法的城市序列）中搜索最佳解。这正适合用遗传算法求解。四、遗传算法应用举例2第四十六页，共六十九页，2022年，8月28日

（1）定义适应度函数我们将一个合法的城市序列s=（c1,c2,…,cn,cn+1）(cn+1就是c1)作为一个个体。这个序列中相邻两城之间的距离之和的倒数就可作为相应个体s的适应度，从而适应度函数就是四、遗传算法应用举例2第四十七页，共六十九页，2022年，8月28日

（2）对个体s=（c1,c2,…,cn,cn+1）进行编码。但对于这样的个体如何编码却不是一件直截了当的事情。因为如果编码不当，就会在实施交叉或变异操作时出现非法城市序列即无效解。例如，对于5个城市的TSP，我们用符号A、B、C、D、E代表相应的城市，用这5个符号的序列表示可能解即染色体。四、遗传算法应用举例2第四十八页，共六十九页，2022年，8月28日然后进行遗传操作。设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’’都是非法的城市序列。四、遗传算法应用举例2第四十九页，共六十九页，2022年，8月28日为此，对TSP必须设计合适的染色体和相应的遗传运算。事实上，人们针对TSP提出了许多编码方法和相应的特殊化了的交叉、变异操作，如顺序编码或整数编码、随机键编码、部分映射交叉、顺序交叉、循环交叉、位置交叉、反转变异、移位变异、互换变异等等。从而巧妙地用遗传算法解决了TSP。四、遗传算法应用举例2第五十页，共六十九页，2022年，8月28日为四个连锁饭店寻找最好的经营决策，其中一个经营饭店的决策包括要做出以下三项决定：（1）价格汉堡包的价格应该定在50美分还是1美元？（2）饮料和汉堡包一起供应的应该是酒还是可乐？（3）服务速度饭店应该提供慢的还是快的服务？目的：找到这三个决定的组合以产生最高的利润。上述问题的表示方案：共有8种表示方案用遗传算法解这个问题的第一步就是选取一个适当的表示方案。四、遗传算法应用举例3第五十一页，共六十九页，2022年，8月28日饭店编号价格饮料速度二进制表示1高可乐快0112高酒快0013低可乐慢1104高可乐慢010表1饭店问题的表示方案（其中的4个）群体规模N＝4四、遗传算法应用举例3第五十二页，共六十九页，2022年，8月28日第0代i串xi适应值f（xi）10113200113110640102总和12最小值1平均值3.00最大值6表2初始群体中经营决策的适应值一个简单的遗传算法由复制、杂交、变异三个算子组成四、遗传算法应用举例3第五十三页，共六十九页，2022年，8月28日第0代复制i串xi适应值f（xi）f（xi）/f（xi）串f（xi）101130.250113200110.081106311060.501106401020.170102总和1217最小值12平均值3.004.25最大值66表3使用复制算子后产生的交叉1.复制算子：采用赌盘选择第五十四页，共六十九页，2022年，8月28日2.杂交算子：采用一点交叉从交配池中选择编号为1和2的串进行配对，且杂交点选在2（用分隔符|表示），杂交算子作用的结果为：01|

101011|0111对交配池中指定百分比的个体应用杂交算子，假设交叉概率pc＝50％，交配池中余下的50％个体仅进行复制运算，即复制概率pr＝50％。第五十五页，共六十九页，2022年，8月28日第0代复制第1代i串xi适应值f(xi)f（xi）/f(xi)串f（xi）交叉点xif（xi）101130.25011320102200110.08110621117311060.501106－1106401020.170102－0102总和121717最小值122平均值3.004.254.25最大值667表4使用复制和杂交算子的作用结果遗传算法利用复制和杂交算子可以产生具有更高平均适应值和更好个体的群体第五十六页，共六十九页，2022年，8月28日课堂练习设有6个个体，分别具有满足度值5，10，15，25，50，100.试用指针轮盘法计算每个个体的复制次数。第五十七页，共六十九页，2022年，8月28日五、遗传算法的理论基础设满足度函数为f(x),在遗传算法中每一次迭代时，每一代个体的总数为m，每个个体的编码长度为n，第g次迭代中的个体j的编码为：遗传算法的数学描述Xg,j=(x1g,j,x2g,j,…xng,j),j=1,2,…m,g=0,1,…

第五十八页，共六十九页，2022年，8月28日复制第五十九页，共六十九页，2022年，8月28日基因交换第六十页，共六十九页，2022年，8月28日基因突变第六十一页，共六十九页，2022年，8月28日1、纲——是一个相同的构形，它描述的是一个串的子集，这个集合中串之间在某些位上相同。

例如，添加符号*表示不确定字母，即0或1，考虑串长为7的模式H＝*11*0**，则串A＝0111000是模式H的一个表示，对于基数为k的字母表，每一个串有（k＋1）l个模式。2、纲的阶数——出现在模式中确定位置的数目。在二进制中，一个模式的阶就是所有的1或0的数目。例如，模式H＝*11*0**的阶为33、纲的定义长度——模式中第一个确定位置与最后一个确定位置之间的距离例如，模式H＝*11*0**的定义长度r＝5－2＝3五、遗传算法的理论基础