系统工程第4章系统优化

IntroductiontoSystemsEngineering石英武汉理工大学自动化学院E-mail:[e-mail]教学内容第一章绪论（1学时）第二章系统分析与系统建模（3学时）第三章最优化技术（24学时）第四章系统优化（2学时）第五章决策分析（2学时）系统工程概论第四章系统优化§4-1系统优化方法概述§4-2遗传算法E-mail:[e-mail]武汉理工大学自动化学院石英§4-1系统优化方法概述系统工程概论E-mail:[e-mail]武汉理工大学自动化学院石英系统优化方法概述概述遗传算法系统优化问题的应用场合：工程设计中参数的选择（既满足设计要求，又能降低成本）生产计划安排（采用合理的方案，提高产值和利润）城市建设规划（工厂、学校、医院、机关、商店、住宅和其他公共设施的安排，方便群众）系统工程概论E-mail:[e-mail]武汉理工大学自动化学院石英系统优化方法概述概述遗传算法•传统优化算法：必须定义被优化系统的性能指标和约束条件；必须选择代表优化因素的独立变量；写出表示个变量之间关系的数学模型。•现代优化算法：用来解决优化问题中的难解问题，对系统模型复杂而无法用明确解析方程来描述的问题有效。系统工程概论E-mail:[e-mail]武汉理工大学自动化学院石英系统优化方法概述概述遗传算法现代优化算法：是20世纪80年代初兴起的启发式算法，这些算法包括禁忌搜索(tabusearch)、模拟退火(simulatedannealing)、遗传算法(geneticalgorithms)、人工神经网络(neuralnetworks)。启发式算法是这样一种技术，它在可接受的计算代价内去寻找最好的解，但不能保证所得的解是最优的，所以有必要对算法进行评价。系统工程概论第四章系统优化§4-1系统优化方法概述§4-2遗传算法E-mail:[e-mail]武汉理工大学自动化学院石英系统工程概论E-mail:[e-mail]武汉理工大学自动化学院石英遗传算法概述遗传算法一．遗传算法中相关的遗传学基础二．遗传算法的原理和特点三．遗传算法的基本操作四．简单遗传算法的算法描述五．简单遗传算法举例§4-2遗传算法系统工程概论E-mail:[e-mail]武汉理工大学自动化学院石英遗传算法概述遗传算法§4-2遗传算法一．遗传算法中相关的遗传学基础遗传算法是根据生物进化的模型提出的一种优化算法。根据达尔文的进化论，生物的发展进化主要有三个原因：遗传、变异和选择。遗传：指子代总是和亲代相似。遗传性是一切生物所共有的特性，它使得生物能够把它的特性、性状传给后代。遗传是生物进化的基础。系统工程概论E-mail:[e-mail]武汉理工大学自动化学院石英遗传算法概述遗传算法选择：指具有精选的能力，它决定生物进化的方向。进化过程中，有的要保留，有的要被淘汰，即适者生存，优胜劣汰。生物就是在遗传、变异和选择三种因素的综合作用过程中，不断地向前发展和进化。变异：指子代和亲代有某些不相似的现象，即子代不会和亲代完全一样。它是生物个体之间区别的基础。生物的变异性为生物的进化和发展创造了条件。系统工程概论E-mail:[e-mail]武汉理工大学自动化学院石英遗传算法概述遗传算法二．遗传算法的原理和特点遗传算法的基本思想：首先将需要优化的参数进行编码，组成一个种群;按照一定的适值函数和一系列遗传操作对种群中的各个个体进行筛选，使适值(fitness也叫适应度)高的个体被保留，组成新的种群，新种群包含了上一代的大量信息，并且引入了新的优于上一代的个体。这样周而复始，种群中个体的适值不断提高，直至满足一定的极限条件。此时，种群中适值最高的个体即为需要优化参数的最优解。系统工程概论E-mail:[e-mail]武汉理工大学自动化学院石英遗传算法概述遗传算法由于遗传算法独具特色的工作原理，使它能够在复杂空间进行全局优化搜索，并且具有较强的鲁棒性。同常规优化算法比较，遗传算法有以下优点：1．遗传算法是对参数的编码进行操作，而非参数本身。这样算法的操作信息量大，优化效果好。2．遗传算法是从许多点开始并行操作，可以有效防止搜索过程收敛于局部最优解问题。系统工程概论E-mail:[e-mail]武汉理工大学自动化学院石英遗传算法概述遗传算法4．遗传算法的寻优规则是由概率决定的，而非确定性的。5．遗传算法在解空间进行高效启发式搜索，而不是盲目地穷举或完全随机搜索。6．遗传算法具有并行计算的特点，可以借助大规模并行计算来提高计算速度。3．遗传算法对所要解决的优化问题没有太多的数学要求。它通过目标函数来计算适值，并不需要其它推导和附加信息，因此对问题的依赖性较小。系统工程概论E-mail:[e-mail]武汉理工大学自动化学院石英遗传算法概述遗传算法三．遗传算法的基本操作一般的遗传算法都包含三个基本操作：复制、交叉和变异。1．复制（Reproduction）复制又称繁殖，也叫选择（selection），它是从一个旧种群中选择生命力强的个体位串，产生新种群的过程。也就是说，复制是个体位串根据目标函数（适值函数）计算适值，按照适值进行复制，具有较高适值的位串出现在下一代种群中的可能性就大。系统工程概论E-mail:[e-mail]武汉理工大学自动化学院石英遗传算法概述遗传算法例如，设有一个优化问题，在整数空间[0,31]上求函数f(x)=x2的最大值。首先把参数x编码为有限长度的字符串，一般使用二进制数串，设参数x的编码长度为5。则有：“00000”代表参数0，“11111”代表参数31，区间[0,31]上的数与编码之间采用线性映射方法。随机产生复制操作的初始种群。例如随机生成的有4个数的初始种群如下：01101110000100010011系统工程概论遗传算法概述遗传算法将初始种群中的个体视为长度为5位的无符号二进制数，每个位串可解码为一个十进制数：位串1：0110113位串2：1100024位串3：010008位串4：1001119对种群的各位串根据目标函数f(x)=x2计算相应的适值和比例，结果如表所示。系统工程概论遗传算法概述遗传算法复制操作可以用多种算法实现，其中最简单的方法是转轮法。转轮法：将种群中所有个体位串的适值的总和看作一个轮子的圆周，每个位串按照它的适值在总和中所占的比例，在圆周中用一个扇区表示。按照上表画出的转轮如图所示。系统工程概论E-mail:[e-mail]武汉理工大学自动化学院石英遗传算法概述遗传算法由于初始种群中的每个位串的适值不同，所占总数的百分比不一样，因此在转轮旋转时，被选中的概率就不一样。例如，本次产生的4个位串中，原初始种群中，有的位串被选中一次，有的被选中多次，而有的一次也没有选中，即该位串被淘汰。因此，适值最好的位串在新种群中就有较多的拷贝。产生的新种群的情况如下表所示。系统工程概论E-mail:[e-mail]武汉理工大学自动化学院石英遗传算法概述遗传算法系统工程概论E-mail:[e-mail]武汉理工大学自动化学院石英遗传算法概述遗传算法2．交叉（Crossover）遗传算法的有效性主要来自复制和交叉操作。复制操作虽然能够从旧种群中选择出优秀者，但不能创造出新的个体；交叉操作模拟了生物进化过程中的繁殖现象，通过两个个体的交换组合，来创造出新的优良个体。简单的交叉分两步实现：（1）将新复制产生的位串个体随机进行两两配对；（2）随机选择交叉点，对匹配的位串进行交叉繁殖，产生一对新的位串。系统工程概论E-mail:[e-mail]武汉理工大学自动化学院石英遗传算法概述遗传算法下面举例说明交叉实现过程。设位串的字符长度为l，在[1,l－1]的范围内，随机选取一个整数值k作为交叉点。将两个位串的第k位右边部分的所有字符进行交换，从而生成两个新的位串。b1b2b3b4b5a1a2a3a4a5b1b2b3a4a5a1a2a3b4b5新串1新串2交叉前交叉后例如，在前述表1中，l＝5，对两个随机配对的位串个体A1和A2，随机选取k＝4，经过交叉后产生的新串为A’1和A’2。系统工程概论E-mail:[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:[e-mail]武汉理工大学自动化学院石英遗传算法概述遗传算法3．变异（Mutation）变异也叫突变，尽管在遗传算法中，复制和交叉操作是最重要的，但它不能保证不会遗漏一些重要的遗传信息。在简单遗传算法中，变异就是指某个字符串中某一位的值偶然的（概率很小的）随机的改变，也就是说在某些特定位置上简单地把1变为0，或把0变为1。当有限制地将变异和交叉一起使用时，可以防止一些重要的遗漏。例如，对于上述例子，如果随机产生的种群为：01101110010010111100系统工程概论E-mail:[e-mail]武汉理工大学自动化学院石英遗传算法概述遗传算法在交叉过程中，无论如何在第4位上都不可能得到有1的位串。因此最终所得到的解只能是局部最优解。但结合变异操作就可以解决这个问题。变异运算是用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变，它以很小的概率随机改变位串个体中的某一位的值。从上面的简单例子分析中可以看出，虽然只进行了一代遗传操作，但所获得的新种群的适值的平均值和最大值却比初始种群有了很大的提高，平均值由293增到了439，最大值由576增加到729。这说明随着遗传运算的进行，种群正向着优化的方向发展。系统工程概论E-mail:[e-mail]武汉理工大学自动化学院石英遗传算法概述遗传算法四．简单遗传算法的算法描述简单遗传算法只使用了复制算子（选择算子）、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解．是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。系统工程概论E-mail:[e-mail]武汉理工大学自动化学院石英遗传算法概述遗传算法1．简单遗传算法的构成要素(1)染色体编码方法简单遗传算法使用固定长度的二址制位串来表示种群中的个体，初始种群中各个个体的位串值可用均匀分布的随机数来生成。如：X=100101011010001110这个个体的染色体长度为n＝18。系统工程概论E-mail:[e-mail]武汉理工大学自动化学院石英遗传算法概述遗传算法(2)个体适应度评价――适值（fitness）基本遗传算法按照与个体适值正比的概率，来决定当前种群中每个个体遗传到下一代的机会的大小。为了正确计算这个概率，要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题．必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。系统工程概论E-mail:[e-mail]武汉理工大学自动化学院石英遗传算法概述遗传算法(3)遗传算子简单遗传算法使用三种遗传算子：●复制运算使用复制算子；●交叉运算使用单点交叉算子；●变异运算使用基本位变异算子或均匀变异算子。系统工程概论E-mail:a_laly