大连海事大学现代优化技术第9讲现代启发式算法之遗传算法

现代优化技术第9讲：现代启发式算法之遗传算法在生物细胞中，控制并决定生物遗传特性的物质是脱氧核糖核酸，简称DNA。染色体是其载体。DNA是由四种碱基按一定规则排列组成的长链。四种碱基不同的排列决定了生物不同的表现性状。例如，改变DNA长链中的特定一段（称为基因），即可改变人体的身高。细胞在分裂时，DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因。生物学中的遗传概念有性生殖生物在繁殖下一代时，两个同元染色体之间通过交叉而重组，亦即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉形成两个新的染色体。在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生新的染色体。这些新的染色体将决定新的个体（后代）的新的性状。生物学中的遗传概念在一个群体中，并不是所有的个体都能得到相同的繁殖机会，对生存环境适应度高的个体将获得更多的繁殖机会；对生存环境适应度较低的个体，其繁殖机会相对较少，即所谓自然选择。而生存下来的个体组成的群体，其品质不断得以改良，称为进化。遗传算法的基本思想和基本概念基本思想遗传算法GA把问题的解表示成“染色体”，在算法中即是以一定方式编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

现代启发式算法之遗传算法GeneticAlgorithm

(遗传算法)模仿生物遗传进化过程同时产生复数的可行解

（即，解集团

population）新的解集团的生成来自于两种基本操作：交叉(crossover)变异(mutation)．现代启发式算法之遗传算法遗传算法与生物遗传的对应关系现代启发式算法之遗传算法GeneticAlgorithmGeneticAlgorithm（粗略）选择(X)=在集団X中，通过自然淘汰，仅将优秀的子孙集団作为下一代．生成(X)=在集団X中，通过交叉或変異，生成新的集団．P(0):=初始解集团fort=0toTdoP(t+1):=选择(Y)Y:=生成(P(t))end现代启发式算法之遗传算法编码(code,representation)编码：在特定的数据结构下，

从可行解的状态空间到编码解的状态空间的一个映射。常规码：{0，1}1：包括该项；0：不包括该项。如背包问题非常规码：非{0，1}向量的表示。如TSP问题的一个都市排列针对问题设计编码编码与解码GA中的编码方法可分为三大类：二进制编码方法、浮点数编码方法和符号编码方法。二进制编码方案是GA中最常用的一种编码方法。它所构成的个体基因型是一个二进制编码符号串。GA的算法过程简述如下。首先在解空间中取一群点，作为遗传开始的第一代。每个点（基因）用一个二进制数字串表示，其优劣程度用适应度函数（fitnessfunction）来衡量

。二进制编码符号串的长度与问题所要求的求解精度有关。设某一参数的取值范围是[B,A]，B<A。则二进制编码的编码精度为：假设某一个体的编码是：X:blbl-1bl-2…b2b1，则对应的解码公式为：例如，对于x∈[0,1023]，若用10位长的二进制编码来表示该参数，则下述符号串：

X:0010101111

就可表示一个个体。它所对应的参数值是x=175。此时的编码精度为δ=1。二进制编码的特点

-编码、解码操作简单易行；

-交叉、变异等遗传操作便于实现；

-符合最小字符集编码原则；

-便于利用图式（模式）定理对算法进行理论分析。

-编码长度较大浮点编码所谓浮点数编码方法是指个体的每个染色体用某一范围内的一个浮点数来表示，个体的编码长度等于其决策变量的个数。因为这种编码方法使用的是决策变量的真实值，所以浮点数编码方法也叫做真值编码方法。符号编码方法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。这个符号集可以是一个字母表，如{A,B,C,D,…}；也可以是一个数字序号表，如{1,2,3,…}；还可以是一个代码表，如{A1,A2,A3,…}等等。例如：对于销售员旅行问题，按一条回路中城市的次序进行编码。从城市w1开始，依次经过城市w2，……，wn，最后回到城市w1，我们就有如下编码表示：

w1w2……wn由于是回路，记wn+1=w1。它其实是1，……，n的一个循环排列。要注意w1，w2，……，wn是互不相同的。现代启发式算法之遗传算法编码(code,representation)*常规码的优缺点：直观、容易表达问题特性及约束，探索高效、缺点为需解码*非常规码的优缺点：考虑问题特性及约束，探索浪费。交叉、变异操作设计复杂。现代启发式算法之遗传算法交叉与变异亲世代集团子孙世代集团交叉(crossover)变异

(mutation)现代启发式算法之遗传算法交叉操作（crossoveroperation）常规码的交叉操作（1）双亲双子法：1）单一交叉位：2）多交叉位：（交叉位间交互替代）（2）双亲单子法：1）随机选2）优胜劣汰（3）显性遗传法:每个基因优胜劣汰（4）单亲遗传法：交换两基因、两个交叉位间倒序等现代启发式算法之遗传算法交叉操作（crossoveroperation）非常规码的交叉操作（1）非重基因法：随机选取一个交叉位，两个后代在交叉位前的基因分别继承各自双亲的交叉位之前的基因、交叉位之后的基因分别按异方双亲的基因顺序选取不重基因。（2）不变位法：随机产生一个同染色体有相同维数的不变位的由0，1组成的向量，1表示不变、0表示变化。不变位的基因继承各自双亲的基因、变位的基因与（1）相同处理。现代启发式算法之遗传算法变异操作（mutationoperation）常规码：最常用的一种变异是指定一个基因从0反位为1、或从1反位为0的概率-变异概率。通常这种操作作用于每一个基因。非常规码：常用的方式为交换两个基因位置、或反序两个基因间的顺序等。

现代启发式算法之遗传算法初始参数的选取种群规模：1）通常取个体编码长度的整数倍2）可动态调整：扩大群体规现行最良解改善变慢模；减少群体规模

现行最良解改善快，加快探索速度

初始群体的选取：1）随机选取：多样性、探索效率低2）其他启发性算法所得到的近似解缺乏代表性、早熟免费午餐?现代启发式算法之遗传算法终止规则最大遗传代数：Max_Gen与下界值偏差：进程监控：根据监控结果，已经K代没有进化到一个更好的解组合终止规则：上述规则的组合现代启发式算法之遗传算法适应度函数适应度函数：评价进化解质量的唯一方式、决定探索的方向。设计适应度函数的原则：1）最优解应赋予最优的适应度2）适应度函数能引导探索向最优解方向进行现代启发式算法之遗传算法适应度函数(1)简单适应度函数：(2)线性加速适应度函数：线性放大目标函数的差异现代启发式算法之遗传算法适应度函数非线性加速适应度函数：如排序适应度函数：将同一代群体中的m个染色体按目标函数值从小到大排列、并依次取值为1,2,…,m.则直接得到相应的适应度（各个染色体分布概率）现代启发式算法之遗传算法选择操作（selectionoperation）确定性选择：现代启发式算法之遗传算法选择操作（selectionoperation）随机选择roulettewheelselection染色体的适应度和所占的比例用转轮方法进行选择现代启发式算法之遗传算法选择操作（selectionoperation）随机选择现代启发式算法之遗传算法选择操作（selectionoperation）随机选择现代启发式算法之遗传算法选择操作（selectionoperation）精英策略

（elitism,elitestrategy）

当前种群中最好的个体无条件保留到下一代选择过程监控

现代启发式算法之遗传算法GeneticAlgorithm（详细）

现代启发式算法之遗传算法遗传算法的评价纪录每一次迭代的最良解（best-so-far）在线比较（on-line）:离线比较（off-line）:现代启发式算法之遗传算法GeneticAlgorithm的弱点不具有集中化探索机制．可加入LocalSearch探索过早收敛(prematureconvergence)导入多样化探索通过交叉・变异操作极易产生非可行解。路径（Path）接续法隧道（tunnel）法等现代启发式算法之遗传算法交叉作用示意图现代启发式算法之遗传算法变异作用示意图遗传算法应用举例

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

y=x2

31

XY

分析

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

解

(1)

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

(2)定义适应度函数,

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

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

首先计算种群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再计算种群S1中各个体的选择概率。选择概率的计算公式为

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31

赌轮选择示意s40.31s20.49s10.14s30.06●赌轮选择法选择

染色体

适应度选择概率选中次数s1=011011690.141s2=110005760.492s3=01000640.060s4=100113610.311于是，得到群体：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）交叉

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

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

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

变异设变异率pm=0.001。这样，群体S1中共有

5×4×0.001=0.02位基因可以变异。

0.02位显然不足1位，所以本轮遗传操作不做变异。

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

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

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

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

染色体

适应度选择概率

估计的选中次数s1=110016250.361s2=011001440.081s3=110117290.411s4=100002560.151

假设这一轮选择操作中，种群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）

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

于是，得第三代种群S3：

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

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

第三代种群S3中各染色体的情况

染色体

适应度选择概率

估计的选中次数s1=111007840.442s2=01001810.040s3=110005760.321s4=100113610.201

设这一轮的选择结果为：

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）

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

于是，得第四代种群S4：

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

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

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

YYy=x2

8131924

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

12162527

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

9192428

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

16242831

X第四代种群及其适应度

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

由于其任一可能解——一个合法的城市序列，即n个城市的一个排列，都可以事先构造出来。于是，我们就可以直接在解空间（所有合法的城市序列）中搜索最佳解。这正适合用遗传算法求解。

（1）定义适应度函数我们将一个合法的城市序列s=（c1,c2,…,cn,cn+1）(cn+1就是c1)作为一个个体。这个序列中相邻两城之间的距离之和的倒数就可作为相应个体s的适应度，从而适应度函数就是

（2）对个体s=（c1,c2,…,cn,cn+1）进行编码。但对于这样的个体如何编码却不是一件直截了当的事情。因为如果编码不当，就会在实施交叉或变异操作时出现非法城市序列即无效解。例如，对于5个城市的TSP，我们用符号A、B、C、D、E代表相应的城市，用这5个符号的序列表示可能解即染色体。然后进行遗传操作。设

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’’都是非法的城市序列。遗传算法是并行算法一、模拟退火算法的基本思想启发注意到一个自然规则：物质总是趋于最低的能态。水总是向低处流。电子总是向最低能级的轨道排布。最低能态是最稳定的状态。物质会”自动”地趋向的最低能态。模拟退火算法（起源）物理退火原理模拟退火算法的设计与原理

猜想物质自动趋向的最低能态与函数最小值之间有相似性！！！我们能不能设计一种算法求函数最小值，就像物质”自动”地趋向最低能态？降温图像离散函数图像相似性?最小值最低能态模拟退火算法与物理退火过程的相似关系模拟退火物理退火解粒子状态最优解能量最低态设定初温熔解过程Metropolis采样过程等温过程控制参数的下降冷却目标函数能量模拟退火算法（Metropolis准则）Metropolis准则 假设在状态xold时，系统受到某种扰动而使其状态变为xnew。与此相对应，系统的能量也从E(xold)变成E(xnew)，系统由状态xold变为状态xnew的接受概率p：模拟退火算法（流程）随机产生一个初始解x0，令xbest＝x0，并计算目标函数值E(x0);设置初始温度T(0)=To;DowhileT>Tmin

//降温过程forj=1~k //等温过程对当前最优解xbest按照某一邻域函数，产生一新的解xnew。计算新的目标函数值E(xnew)，并计算目标函数值的增量

E=E(xnew)-E(xbest)

。如果

E＜0，则xbest=xnew；如果

E＞0，则p=exp(-

E/T(i));如果c=random[0,1]<p，xbest=xnew;否则xbest=xbest。Endfor按照温度控制策略更新T；EndDo输出当前最优点，计算结束。模拟退火算法（要素）1、状态空间与状态产生函数（邻域函数）搜索空间也称为状态空间，它由经过编码的可行解的集合所组成。状态产生函数(邻域函数)应尽可能保证产生的候选解能遍布全部解空间。通常由两部分组成，即产生候选解的方式和候选解产生的概率分布。候选解一般按照某一概率分布对解空间进行随机采样来获得。概率分布可以是均匀分布、正态分布、指数分布等等。模拟退火算法（要素）2、状态转移概率（接受概率）p状态转移概率是指从一个状态xold(一个可行解)向另一个状态xnew(另一个可行解)的转移概率;通俗的理解是接受一个新解为当前解的概率;它与当前的温度参数T有关，随温度下降而减小。一般采用Metropolis准则模拟退火算法（要素）3、冷却进度表T(t)

冷却进度表是指从某一高温状态To向低温状态冷却时的降温管理表。 假设时刻t的温度用T(t)来表示，则经典模拟退火算法的降温方式为：

而快速模拟退火算法的降温方式为： 这两种方式都能够使得模拟退火算法收敛于全局最小点。模拟退火算法（要素）4、初始温度T0 实验表明，初温越大，获得高质量解的几率越大，但花费的计算时间将增加。因此，初温的确定应折衷考虑优化质量和优化效率，常用方法包括： (1)均匀抽样一组状态，以各状态目标值的方差为初温。 (2)随机产生一组状态，确定两两状态间的最大目标值差|

max|，然后依据差值，利用一定的函数确定初温。比如，t0=－

max/pr，其中pr为初始接受概率。 (3)利用经验公式给出。模拟退火算法（要素）5、内循环终止准则 或称Metropolis抽样稳定准则，用于决定在各温度下产生候选解的数目。常用的抽样稳定准则包括： (1)检验目标函数的均值是否稳定； (2)连续若干步的目标值变化较小； (3)按一定的步数抽样。模拟退火算法（要素）6、外循环终止准则即算法终止准则，常用的包括：(1)设置终止温度的阈值；(2)设置外循环迭代次数；(3)算法搜索到的最优值连续若干步保持不变；(4)检验系统熵是否稳定。模拟退火算法的改进(1)设计合适的状态产生函数，使其根据搜索进程的需要表现出状态的全空间分散性或局部区域性。(2)设计高效的退火策略。(3)避免状态的迂回搜索。(4)采用并行搜索结构。(5)为避免陷入局部极小，改进对温度的控制方式(6)选择合适的初始状态。(7)设计合适的算法终止准则。模拟退火算法的改进 也可通过增加某些环节而实现对模拟退火算法的改进。主要的改进方式包括：(1)增加升温或重升温过程。在算法进程的适当时机，将温度适当提高，从而可激活各状态的接受概率，以调整搜索进程中的当前状态，避免算法在局部极小解处停滞不前。(2)增加记忆功能。为避免搜索过程中由于执行概率接受环节而遗失当前遇到的最优解，可通过增加存储环节，将“BestSoFar”的状态记忆下来。(3)增加补充搜索过程。即在退火过程结束后，以搜索到的最优解为初始状态，再次执行模拟退火过程或局部性搜索。(4)对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而非标准SA的单次比较方式。(5)结合其他搜索机制的算法，如遗传算法、混沌搜索等。(6)上述各方法的综合应用。算法实现与应用TSP问题的求解编码（城市编号顺序编码）状态产生函数（逆转算子）状态接受函数初温与初始状态，T0=－

max/pr

降温函数设计温度修改准则和算法终止准则运行过程

三、模拟退火算法的应用

3.130城市TSP问题（d*=423.741byDBFogel）

运行过程

三、模拟退火算法的应用

3.130城市TSP问题（d*=423.741byDBFogel）

运行过程

三、模拟退火算法的应用

3.130城市TSP问题（d*=423.741byDBFogel）

运行过程

三、模拟退火算法的应用

3.130城市TSP问题（d*=423.741byDBFogel）

运行过程

三、模拟退火算法的应用

3.130城市TSP问题（d*=423.741byDBFogel）

运行结果

三、模拟退火算法的应用

3.130城市TSP问题（d*=423.741byDBFogel）

92§1随机过程的概念

随机过程被认为是概率论的“动力学”部分，即它的研究对象是随时间演变的随机现象，它是从多维随机变量向一族(无限多个)随机变量的推广。

给定一随机试验，其样本空间，将样本空间中的每一元作如下对应，便得到一系列结果：随机过程的定义94例1：抛掷一枚硬币的试验，样本空间是，现定义：1234959697例5：考虑抛掷一颗骰子的试验：99随机过程的分类：随机过程可根据参数集T和任一时刻的状态分为四类，参数集T可分为离散集和连续集两种情况，任一时刻的状态分别为离散型随机变量和连续型随机变量两种：连续参数连续型的随机过程，如例2，例3连续参数离散型的随机过程，如例1，例4离散参数离散型的随机过程，如例5离散参数连续型的随机过程，如下例马尔科夫Markov链Markov原名A.A.Markov（俄，1856－1922）于1906年开始研究此类问题.1马尔可夫链的定义引例

假定某大学有1万学生，每人每月用1支牙膏，并且只使用“中华”牙膏与“黑妹”牙膏两者之一。根据本月（12月）调查，有3000人使用黑妹牙膏，7000人使用中华牙膏。又据调查,使用黑妹牙膏的3000人中，有60％的人下月将继续使用黑妹牙膏，

40％的人将改用中华牙膏；

使用中华牙膏的7000人中，

有70％的人下月将继续使用中华牙膏，

30％的人将改用黑妹牙膏。据此，可以得到如表所示的统计表

拟用黑妹牙膏中华牙膏现用黑妹牙膏60％40％中华牙膏30％70％基本概念状态和状态转移状态是指客观事物可能出现或存在的状况。如企业的产品在市场上可能畅销，也可能滞销。状态转移是指客观事物由一种状态到另一种状态的变化。客观事物的状态不是固定不变的，它可能处于这种状态，也可能处于那种状态，往往条件变化，状态也会发生变化。如某种产品在市场上本来是滞销的，但是由于销售渠道变化了，或者消费心理发生了变化等，它便可能变为畅销产品。转移概率与转移概率矩阵

假定某大学有1万学生，每人每月用1支牙膏，并且只使用“中华”牙膏与“黑妹”牙膏两者之一。根据本月（12月）调查，有3000人使用黑妹牙膏，7000人使用中华牙膏。又据调查,使用黑妹牙膏的3000人中，有60％的人下月将继续使用黑妹牙膏，

40％的人将改