第3章优化算法1-遗传算法2014

12023/2/1系统工程第三章系统的优化算法第一节基于遗传算法的随机优化搜索1.1基本概念1.2基本遗传算法1.3遗传算法应用举例1.4遗传算法的特点与优势1.5基于实数编码的加速遗传算法2023/2/13遗传算法概述遗传算法（geneticalgorithm，简称GA）是由美国J.H.Holland于1975年提出的一种全新的优化搜索算法。GA发展初期，并没有引起学术界的关注，因而发展比较缓慢，直到八十年代，GA的研究才引起重视并逐步成熟起来，目前，已在组合优化、机器学习、自适应控制、模式识别、神经网络、经济预测等领域取得了令人瞩目的应用成果。2023/2/14算法的学说：（１）遗传:“种瓜得瓜，种豆得豆”，亲代把生物信息交给子代，子代按照所得信息而发育、分化，子代总是和亲代具有相同或相似的性状。（２）变异:

亲代和子代之间以及子代的不同个体之间总有差异。变异是随机发生的，变异的选择和积累是生命多样性的根源。（３）生存斗争和适者生存:由于弱肉强食和生存斗争不断进行，其结果是适者生存，不适者被淘汰，通过一代代的选择作用，物种变异朝着一个方向积累，演变为新的物种。2023/2/15基本思想——遗传进化，根据自然选择和适者生存原理，用简单的编码技术和繁殖机制，模拟自然界生物群体优胜劣汰的进化过程，实现对复杂问题的求解。把搜索空间（欲求解问题的解空间）映射为遗传空间，把每一个可能的解编码为一个向量（二进制或十进制数字串），称为一个染色体（或个体），向量中每一个元素称为基因。所有染色体组成群体（群体中染色体个数用POP表示），并按预定的目标函数（或某种评价指标）对每个染色体进行评价，根据其结果给出一个适应度值。遗传算法的实现2023/2/16算法开始时，先随机地产生一些染色体（欲求解问题的候选解），计算其适应度，根据适应度对诸染色体进行选择、交叉、变异操作，剔除适应度差的染色体，留下适应度较好（性能优良）的染色体，从而得到新的群体。新群体的染色体是上一代群体的优秀者，继承了上一代的优良性态，因而明显优于上一代，这样就能向着更优解的方向进化，直至满足某种预定的优化收敛指标。2023/2/171.1基本概念

1.个体与种群

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

●

种群(population)就是模拟生物种群而由若干个体组成的群体,它一般是整个搜索空间的一个很小的子集。2023/2/18

2.适应度与适应度函数

●

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

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

2023/2/193.染色体与基因

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

9----

1001

（2，5，6）----0101011102023/2/1104.遗传操作亦称遗传算子(geneticoperator)，就是关于染色体的运算。遗传算法中有三种遗传操作:

●

选择-复制(selection-reproduction)

●

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

●

变异(mutation，亦称突变)

2023/2/111

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

选择概率P(xi)的计算公式为父代个体的数量2023/2/112

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

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

染色体s1=01001011,s2=10010101,

交换其后4位基因,即2023/2/113

变异就是改变染色体某个(些)位上的基因。染色体s=11001101，将其第三位上的0变为1,即

s=11001101→11101101=s′。

s′也可以看做是原染色体s的子代染色体。2023/2/1141.2基本遗传算法

遗传算法基本流程框图生成初始种群计算适应度选择-复制交叉变异生成新一代种群终止?结束2023/2/115

算法中的一些控制参数：

■

种群规模：初始种群中染色体的数量

■

最大换代数

■

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

■

变异率(mutationrate)是指发生变异的基因位数所占全体染色体的基因总位数的比例，记为Pm，取值范围一般为0.0001～0.1。2023/2/116

基本遗传算法Step1

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

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

计算S中每个个体的适应度f(si)；Step4

若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。否则step52023/2/117

Step5

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

Step6

按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2(子代)

；2023/2/118

Step7

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

；

Step8

将群体S3作为新一代种群，即用S3代替S，t=t+1，转Step3，计算适应度；

2023/2/1191.3遗传算法应用举例

例1.1

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

y=x2

31

XY2023/2/120

分析

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

解

(1)

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

(2)定义适应度函数,

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

终止条件：x=31(11111)

若精度ε=1则区间长度Smax-Smin=31(Smax-Smin)/ε=31≤2L-1L=52023/2/122s1=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∑f=1170(3)计算各代种群中的各个体的适应度,并对其染色体进行选择、遗传、变异操作2023/2/123再计算种群S1中各个体的选择概率。选择概率的计算公式为

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.312023/2/124

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

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

设从区间［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.0012023/2/127于是，经复制得群体：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）S0的子代S12023/2/128交叉

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

s1’=11000（24）,s2’=01101（13）s3’=11000（24）,s4’=10011（19）

s1’’=11001（25）,s2’’=01100（12）s3’’=11011（27）,s4’’=10000（16）

S1的子代S22023/2/129变异设变异率pm=0.001。这样，群体S2中共有5×4×0.001=0.02位基因可以变异。显然不足1位，所以本轮遗传操作不做变异。

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

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

s3=11011（27）,s4=10000（16）2023/2/130

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

染色体

适应度选择概率积累概率

估计的选中次数s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.0012023/2/131

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

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

2023/2/132得第三代种群S3：

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

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

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

染色体

适应度选择概率积累概率

估计的选中次数s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.0012023/2/133

设这一轮的选择-复制结果为：

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）

这一轮仍然不会发生变异。2023/2/134得第四代种群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第四代种群及其适应度2023/2/136例1.2水电站厂内经济运行

水电站厂内经济运行准则是在满足电力系统负荷（日负荷图）要求的前提下，使各机组耗用的总流量最小，它是电力系统经济运行的重要组成部分。开停机计划问题在数学上表现为一个大规模的非线性整数规划问题。

目标：总流量最小2023/2/137用遗传算法寻求最优运行方式时，每个染色体表示某一时段各机组的组合状态，染色体中基因表示其对应机组的运行方式，1表示开机，0表示停机，如系统共有5台机组，染色体10011，表示在该时段第1，4，5台机组开机。适应度函数为：开开关关关…N个2023/2/138式中，Q0为一常数，Hit

为第i台机组在t时段的平均水头，Nit为第i台机组在t时段的平均出力，Qi

为第i台机组在水头Hit

、出力Nit下的发电流量，uit为t时段第i个基因的值，Pikt

为第i台机组的开停机罚因子，Qikt为第i台机组的开停机损耗流量。初始种群由满足约束条件的个体组成，然后对染色体利用适应度函数评价，根据给定的选择概率、交叉概率、变异概率进行选择、交叉、变异（1变0，0变1）操作，直到满足某种收敛准则。2023/2/139例1.3含沙量预报XX水库上游的A水文站至入库的B站区间，是该水库泥沙的主要来源，入库含沙量随着区间产流量的变化而变化，而A站以上地区的入库水沙则相对稳定。现有QB、QA资料，预测入库含沙量。水文站A水文站B水库Q区=QB-QAQB资料分析表明含沙量与两组数据相关性较高2023/2/140预报函数：式中

—入库含沙量的预报值，kg/m3;μ—含沙量的真值，kg/m3;Q1—B站流量，m3/s;Q2—区间流量，m3/s;a1,a2,b1,b2,c—模型参数。目标函数：若精度ε=0.01(cmax-cmin)/ε≤2L

-1得Lc则字符串长度为5参数之和2023/2/1411.4遗传算法的优缺点

◆优点:标准遗传算法（SGA）至今仍是国内外GA应用中常用的实施方案，它提供了遗传算法的基本框架，也解决了简单的函数优化问题：（1）解空间搜索遗传算法一般是直接在解空间搜索,而不像其它搜索那样一般是在问题空间搜索,最后才找到解。（2）不受导数的影响传统优化算法不仅需要利用目标函数值，往往需要函数的导数值等其他辅助信息才能确定搜索方向。无法或很难求导数的目标函数，或导数不存在，以及组合优化问题等，应用遗传算法时就显得比较方便。2023/2/142（3）并行搜索遗传算法的搜索过程是从空间的一个点集(种群)到另一个点集(种群)的搜索,而不像图搜索那样一般是从空间的一个点到另一个点地搜索。因而它实际是一种并行搜索,适合大规模并行计算,而且这种种群到种群的搜索有能力跳出局部最优解。（4）较强的适应性遗传算法的适应性强,除需知适应度函数外,几乎不需要其他的先验知识。2023/2/143（5）全局搜索遗传算法长于全局搜索,它不受搜索空间的限制性假设的约束,不要求连续性,能以很大的概率从离散的、多极值的、含有噪声的高维问题中找到全局最优解。

（6）决策变量的编码作为运算对象对决策变量的编码处理方式，借鉴了生物学中染色体和基因等概念，模仿自然界中生物的遗传和进化机理，对一些无数值概念或很难有数值概念，而只有代码概念的优化问题，编码处理方式更显示出了其独持的优越性。2023/2/144（7）使用概率搜索技术传统的优化算法往往使用的是确定性的搜索方法，一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系，这种确定性有可能使得搜索永远达不到最优点。遗传算法属于一种自适应概率搜索技术，选择、交叉、变异以一种概率的方式来进行的．虽然这种概率特性也会使群体中产生—些适应度不高的个体，但随着进化过程的进行，新的群体中总会更多地产生出许多优良的个体。（交叉和变异概率等参数会影响算法的搜索效率，如何选择是一个比较重要的问题。）2023/2/145但对于复杂的系统优化问题，SGA在使用时出现了一些困难和问题，（１）SGA收敛于最优解的概率小于1。（２）SGA在使用选择算子进行优胜劣汰时，要求个体的适应度均大于零，因此需考虑