系统工程第四章系统优化

系统工程第四章系统优化教学内容第一章

绪论

（1学时）

第二章系统分析与系统建模（3学时）

第三章最优化技术（24学时）

第四章

系统优化（2学时）

第五章

决策分析（2学时）

系统工程概论第四章系统优化§4-1系统优化方法概述

§4-2遗传算法E-mail:武汉理工大学自动化学院石英§4-1系统优化方法概述系统工程概论E-mail:武汉理工大学自动化学院石英系统优化方法概述概述遗传算法系统优化问题的应用场合：工程设计中参数的选择（既满足设计要求，又能降低成本）生产计划安排（采用合理的方案，提高产值和利润）城市建设规划（工厂、学校、医院、机关、商店、住宅和其他公共设施的安排，方便群众）系统工程概论E-mail:武汉理工大学自动化学院石英系统优化方法概述概述遗传算法传统优化算法：必须定义被优化系统的性能指标和约束条件；必须选择代表优化因素的独立变量；写出表示个变量之间关系的数学模型。现代优化算法：用来解决优化问题中的难解问题，对系统模型复杂而无法用明确解析方程来描述的问题有效。系统工程概论E-mail:武汉理工大学自动化学院石英系统优化方法概述概述遗传算法现代优化算法：是20世纪80年代初兴起的启发式算法，这些算法包括禁忌搜索(tabusearch)、模拟退火(simulatedannealing)、遗传算法(geneticalgorithms)、人工神经网络(neuralnetworks)。启发式算法是这样一种技术，它在可接受的计算代价内去寻找最好的解，但不能保证所得的解是最优的，所以有必要对算法进行评价。系统工程概论第四章系统优化§4-1系统优化方法概述

§4-2遗传算法E-mail:武汉理工大学自动化学院石英系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法一．遗传算法中相关的遗传学基础二．遗传算法的原理和特点三．遗传算法的基本操作四．简单遗传算法的算法描述五．简单遗传算法举例§4-2遗传算法系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法§4-2遗传算法一．遗传算法中相关的遗传学基础

遗传算法是根据生物进化的模型提出的一种优化算法。

根据达尔文的进化论，生物的发展进化主要有三个原因：遗传、变异和选择。

遗传：指子代总是和亲代相似。遗传性是一切生物所共有的特性，它使得生物能够把它的特性、性状传给后代。遗传是生物进化的基础。

系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法选择：指具有精选的能力，它决定生物进化的方向。进化过程中，有的要保留，有的要被淘汰，即适者生存，优胜劣汰。

生物就是在遗传、变异和选择三种因素的综合作用过程中，不断地向前发展和进化。变异：指子代和亲代有某些不相似的现象，即子代不会和亲代完全一样。它是生物个体之间区别的基础。生物的变异性为生物的进化和发展创造了条件。

系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法二．遗传算法的原理和特点

遗传算法的基本思想：

首先将需要优化的参数进行编码，组成一个种群;

按照一定的适值函数和一系列遗传操作对种群中的各个个体进行筛选，使适值(fitness也叫适应度)高的个体被保留，组成新的种群，

新种群包含了上一代的大量信息，并且引入了新的优于上一代的个体。

这样周而复始，种群中个体的适值不断提高，直至满足一定的极限条件。此时，种群中适值最高的个体即为需要优化参数的最优解。

系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法由于遗传算法独具特色的工作原理，使它能够在复杂空间进行全局优化搜索，并且具有较强的鲁棒性。

同常规优化算法比较，遗传算法有以下优点：

1．遗传算法是对参数的编码进行操作，而非参数本身。这样算法的操作信息量大，优化效果好。

2．遗传算法是从许多点开始并行操作，可以有效防止搜索过程收敛于局部最优解问题。

系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法4．遗传算法的寻优规则是由概率决定的，而非确定性的。

5．遗传算法在解空间进行高效启发式搜索，而不是盲目地穷举或完全随机搜索。

6．遗传算法具有并行计算的特点，可以借助大规模并行计算来提高计算速度。

3．遗传算法对所要解决的优化问题没有太多的数学要求。它通过目标函数来计算适值，并不需要其它推导和附加信息，因此对问题的依赖性较小。

系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法三．遗传算法的基本操作

一般的遗传算法都包含三个基本操作：复制、交叉和变异。

1．复制（Reproduction）

复制又称繁殖，也叫选择（selection），它是从一个旧种群中选择生命力强的个体位串，产生新种群的过程。也就是说，复制是个体位串根据目标函数（适值函数）计算适值，按照适值进行复制，具有较高适值的位串出现在下一代种群中的可能性就大。

系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法例如，设有一个优化问题，在整数空间[0,31]上求函数f(x)=x2的最大值。

首先把参数x编码为有限长度的字符串，一般使用二进制数串，设参数x的编码长度为5。

则有：“00000”代表参数0，“11111”代表参数31，区间[0,31]上的数与编码之间采用线性映射方法。

随机产生复制操作的初始种群。

例如随机生成的有4个数的初始种群如下：

01101

11000

01000

10011系统工程概论遗传算法概述遗传算法将初始种群中的个体视为长度为5位的无符号二进制数，每个位串可解码为一个十进制数：

位串1：0110113

位串2：1100024

位串3：010008

位串4：1001119对种群的各位串根据目标函数f(x)=x2计算相应的适值和比例，结果如表所示。

系统工程概论遗传算法概述遗传算法复制操作可以用多种算法实现，其中最简单的方法是转轮法。

转轮法：将种群中所有个体位串的适值的总和看作一个轮子的圆周，每个位串按照它的适值在总和中所占的比例，在圆周中用一个扇区表示。按照上表画出的转轮如图所示。

系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法由于初始种群中的每个位串的适值不同，所占总数的百分比不一样，因此在转轮旋转时，被选中的概率就不一样。

例如，本次产生的4个位串中，原初始种群中，有的位串被选中一次，有的被选中多次，而有的一次也没有选中，即该位串被淘汰。因此，适值最好的位串在新种群中就有较多的拷贝。

产生的新种群的情况如下表所示。

系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法2．交叉（Crossover）

遗传算法的有效性主要来自复制和交叉操作。

复制操作虽然能够从旧种群中选择出优秀者，但不能创造出新的个体；

交叉操作模拟了生物进化过程中的繁殖现象，通过两个个体的交换组合，来创造出新的优良个体。

简单的交叉分两步实现：

（1）将新复制产生的位串个体随机进行两两配对；

（2）随机选择交叉点，对匹配的位串进行交叉繁殖，产生一对新的位串。

系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法下面举例说明交叉实现过程。

设位串的字符长度为l，在[1,l－1]的范围内，随机选取一个整数值k作为交叉点。将两个位串的第k位右边部分的所有字符进行交换，从而生成两个新的位串。

b1b2b3b4b5a1a2a3a4a5b1b2b3a4a5a1a2a3b4b5新串1新串2交叉前交叉后例如，在前述表1中，l＝5，对两个随机配对的位串个体A1和A2，随机选取k＝4，经过交叉后产生的新串为A’1和A’2。

系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法A1=01101A2=11000A’1=01100A’2=11001对两个随机配对的位串个体A3和A4，随机选取交叉点k＝2，经过交叉后产生的新串为A’3、和A’4。

A3=11000A4=10011A’3=11011A’4=10000经过交叉后的结果数据如下表所示。

系统工程概论遗传算法概述遗传算法在进行交叉时，如果交叉的位置只有一个称为单点交叉，对于位串长度为l的种群，单点交叉可能有l－1个不同的交叉。

交叉时也可以选择多点交叉，也称为复点交叉，即允许个体的切断点有多个，每个切断点在两个个体间进行个体的交叉，生成两个新个体。

系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法3．变异（Mutation）

变异也叫突变，尽管在遗传算法中，复制和交叉操作是最重要的，但它不能保证不会遗漏一些重要的遗传信息。

在简单遗传算法中，变异就是指某个字符串中某一位的值偶然的（概率很小的）随机的改变，也就是说在某些特定位置上简单地把1变为0，或把0变为1。当有限制地将变异和交叉一起使用时，可以防止一些重要的遗漏。例如，对于上述例子，如果随机产生的种群为：01101110010010111100系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法在交叉过程中，无论如何在第4位上都不可能得到有1的位串。因此最终所得到的解只能是局部最优解。但结合变异操作就可以解决这个问题。

变异运算是用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变，它以很小的概率随机改变位串个体中的某一位的值。

从上面的简单例子分析中可以看出，虽然只进行了一代遗传操作，但所获得的新种群的适值的平均值和最大值却比初始种群有了很大的提高，平均值由293增到了439，最大值由576增加到729。这说明随着遗传运算的进行，种群正向着优化的方向发展。

系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法四．简单遗传算法的算法描述

简单遗传算法只使用了复制算子（选择算子）、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解．是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。

系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法1．简单遗传算法的构成要素

(1)染色体编码方法简单遗传算法使用固定长度的二址制位串来表示种群中的个体，初始种群中各个个体的位串值可用均匀分布的随机数来生成。

如：这个个体的染色体长度为n＝18。

系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法(2)个体适应度评价――适值（fitness）

基本遗传算法按照与个体适值正比的概率，来决定当前种群中每个个体遗传到下一代的机会的大小。

为了正确计算这个概率，要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题．必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。

系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法(3)遗传算子

简单遗传算法使用三种遗传算子：

●复制运算使用复制算子；●交叉运算使用单点交叉算子；●变异运算使用基本位变异算子或均匀变异算子。

系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法(4)简单遗传算法的运行参数

简单遗传算法有以下4个运行参数需要提前设定：

●M：种群大小，即种群中所含个体的数量，一般取为20～100。●T：遗传运算的终止进化代数，一般取为100～500。●Pc：交叉概率，一般取为0.4～0.99。●Pm：变异概率，一般取为0.0001～0.1。

这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前还没有合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试算后，才能确定出这些参数合理的取值大小或取值范围。

系统工程概论遗传算法概述遗传算法2．简单遗传算法描述

下面给出简单遗传算法的伪代码描述。

简单遗传算法可定义为一个8元组：

SGA＝(C，E，P0，M，Φ,г,ψ，T)式中:C--个体的编码方法；

E--个体适值评价函数；

P0--初始种群；

M--种群大小;

Φ--复制算子；

г—交叉算子；

ψ—变异算子；

T—遗传运算终止条件。系统工程概论遗传算法概述遗传算法ProcedureSGABeginInitializeP(0);t=0;while(t≤T)dofori=1toMdoEvaluatefitnessofP(t);endforfori=1toMdoReproductionoperationtoP(t);endforfori=1toM/2doCrossoveroperationtoP(t);endforfori=1toMdoMutationoperationtoP(t);endfor系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法fori=1toMdoP(t+1)=P(t)endfort=t+1endwhileend系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法五．简单遗传算法举例

简单遗传算法是一个迭代过程，它模仿生物在自然环境中的遗传和进化机理，反复将复制算子、交叉算子子、变异算子作用于种群，最终可得到问题的最优解或近似最优解。

1．遗传算法的应用步骤

遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的领域和种类。

对一个需要进行优化计算的实际应用问题，一般可按以下步骤来构造求解该问题的遗传算法。

系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法第一步：确定决策变量及其各种约束条件，即确定出个体的表现型x和问题的解空间。

第二步：建立优化模型，即确定出目标函数的类型(是求目标函数的最大值还是求目标函数的最小值?)及其数学描述形式或量化方法。

第三步：确定表示可行的个体编码方法，也就是确定出个体的位串x及遗传算法的搜索空间。

第四步：确定解码方法，也就是确定出由个体位串x到个体表现型x的对应关系或转换方法。

系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法第五步；确定个体适值的量化评价方法，也就是确定出由目标函数值g(x)到个体适应度f(x)的转换规则。

第六步：设计遗传算子，即确定出复制运算、交叉运算、变异运算等遗传算子的具体操作方法。

第七步：确定遗传算法的有关运行参数，即确定出遗传算法的M、T、Pc、Pm等参数。

下图是应用遗传算法解决实际问题的流程。系统工程概论遗传算法概述遗传算法实际问题参数集编码成位串形式种群1计算适值选择和遗传统计结果种群2经过优化的一个或多个参数值改善或解决实际问题随机算子种群1<-种群2复制.交叉.变异系统工程概论遗传算法概述遗传算法2．简单遗传算法在函数优化中的应用举例

例

用简单遗传算法求解Rosenbrock函数的全局最大值。

f(x1,x2)＝100(x12－x2)2＋(1-x1)2（6-1-1）

-2.048<xi<2.048(i=1,2)（6-1-2）

系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法如图所示，该函数有两个局部极大点，分别是f(2.048,-2.048)=3897.7342和f(-2.048,-2.048)=3905.9296，其中后者为全局最大点。

系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法下面讨论求解该问题的遗传算法的构造过程.

第一步：确定决策变量和约束条件。

式（6-1-2）就是该问题的决策变量和约束条件。

第二步：建立优化模型。

式（6-1-1）就是该问题的数学模型。

第三步：确定编码方法。

用长度为10位的二进制位串来分别表示二个决策变量x1和x2。10位编码可以表示从0～1023之间的1024个不同的数。

系统工程概论E-mail:武汉理工大学自动化学院石英遗传算法概述遗传算法将x1和x2的定义域(-2.048~2.048)离散化为1023个均等的区域，包括两个端点在内共有1024个不同的离散点。依次让它们对应于从0000000000(0)到1111111111(1023)之间的二进制编码。

再将分别表示x1和x2的二个10位长的编码串连接在一起，组成一个20位长的编码，它就构成了这个函数优化问题的染色体（个体）编码方法。

系统工程概论遗传算法概述遗传算法第四步：确定解码方法。

解码时需要先将20位长的位串分割成二个10位长的位串，然后将它们分别转换为对应的十进制整数代码，分别记为y1和y2。

根据前面介绍的个体编码方法和对定义域的离散化方法，将代码yi转换为变量xi，解码公式为：

（6-1-3）

例如，对于个体X：00001101111101110001分解成两个代码：

y1＝55，y2＝881

经过式（6-1-3）解码处理后，可得到：

x1＝－1.828，x2＝1.476E-mail:武汉理工大学自动化学院石英系统工程概论E-mail: