武汉大学选修课系统工程概论chap-8-优化技术的前沿教学课件

武汉大学选修课系统工程概论chap 8 优化技术的前沿41、实际上，我们想要的不是针对犯罪的法律，而是针对疯狂的法律。马克吐温42、法律的力量应当跟随着公民，就像影子跟随着身体一样。贝卡利亚43、法律和制度必须跟上人类思想进步。杰弗逊44、人类受制于法律，法律受制于情理。托富勒45、法律的制定是为了保证每一个人自由发挥自己的才能，而不是为了束缚他的才能。罗伯斯庇尔优优化化决决策策技技术术的的前前沿沿优优化化决决策策技技术术的的前前沿沿优优化化决决策策技技术术的的前前沿沿优优化化决决策策技技术术的的前前沿沿优优化化决决策策技技术术的的前前沿沿六峰值驼背函数Six-hump camel back function该函数有该函数有6个局部极小点，个局部极小点，其中全局最小点其中全局最小点(-0.0898,0.7126)T(0.0898,-0.7126)T全局最小值：全局最小值：-1.031628优优化化决决策策技技术术的的前前沿沿遗传算法遗传算法（遗传算法（Genetic Algorithms，简称，简称GAs）的的生物学背景生物学背景：Darwin的的进化论进化论和和Mendel的的遗传学说遗传学说 适者生存，劣质淘汰适者生存，劣质淘汰即优胜劣汰即优胜劣汰优优化化决决策策技技术术的的前前沿沿遗传算法的基本思想GAs是将是将问题的求解问题的求解表示成表示成“染色体染色体”，从而构成，从而构成一群染色体。一群染色体。将它们置于问题的将它们置于问题的“环境环境”中，根据适者生存的原中，根据适者生存的原则，从中选择出适应环境的染色体进行则，从中选择出适应环境的染色体进行复制复制，即，即再生（再生（Reproduction，也称，也称Selection），通过），通过交交叉叉（Crossover）、）、变异变异（Mutation）两种基因）两种基因操作产生出新的一代更适应环境的染色体群。操作产生出新的一代更适应环境的染色体群。这样一代代的不断进化，最后收敛到一个最适合这样一代代的不断进化，最后收敛到一个最适合环境的个体上，求得问题的最优解。环境的个体上，求得问题的最优解。优优化化决决策策技技术术的的前前沿沿自然进化与GAs的对应关系基因串基因串（染色体）（染色体）问题的问题的可行解可行解基因型基因型表现型表现型适应度适应度解码解码编码编码目标函数目标函数解码解码不同环境不同环境解的解的评价值评价值优优化化决决策策技技术术的的前前沿沿GAs的流程图实际问题参数集确定表示问题解答的染色体（串）生成初始染色体串群计算每个个体的适应度是否收敛选择高适应值的串进行复制交叉变异输出最优解是否优优化化决决策策技技术术的的前前沿沿遗传算法的基本概念遗传算法的基本概念个体和个体空间个体和个体空间适应度函数（适应度函数（F(t)）遗传算子遗传算子:选择、交叉和变异算子选择、交叉和变异算子 控制参数控制参数:种群规模种群规模 M、交叉概率、交叉概率Pc、变异概率变异概率Pm、进化代数、进化代数T优优化化决决策策技技术术的的前前沿沿基本遗传算法的构成要素（1）染色体编码方法）染色体编码方法采用采用固定长度的二进制符号串固定长度的二进制符号串来表示群体来表示群体的个体，其等位基因是的个体，其等位基因是0,1组成。如组成。如X100111001000101101该个体的染色体长度是该个体的染色体长度是n18优优化化决决策策技技术术的的前前沿沿基本遗传算法的构成要素（2）个体适应度评价）个体适应度评价基本遗传算法按与基本遗传算法按与个体适应度成正比个体适应度成正比的概的概率来率来决定决定当前群体中每个个体遗传到下一当前群体中每个个体遗传到下一代的机会的多少。代的机会的多少。必须预先确定好由目标函数值到个体适应必须预先确定好由目标函数值到个体适应度之间的度之间的转换规则转换规则。优优化化决决策策技技术术的的前前沿沿个体适应度评价优优化化决决策策技技术术的的前前沿沿基本遗传算法的构成要素（3）遗传算子）遗传算子基本遗传算法使用三种遗传算子：基本遗传算法使用三种遗传算子：选择算子（比例选择算子）选择算子（比例选择算子）交叉运算（单点交叉算子）交叉运算（单点交叉算子）变异算子（基本位变异或均匀变异算子）变异算子（基本位变异或均匀变异算子）优优化化决决策策技技术术的的前前沿沿比例选择算子也称也称赌盘选择赌盘选择，个体被选中并遗传到下一，个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成代群体中的概率与该个体的适应度大小成正比。正比。金银铜铁10203040优优化化决决策策技技术术的的前前沿沿单点交叉算子（1）对群体中的个体进行两两随机配对）对群体中的个体进行两两随机配对（2）对每一对相互配对的个体，随机设置某一）对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点基因座之后的位置为交叉点（3）对每一对相互配对的个体，依设定的交叉）对每一对相互配对的个体，依设定的交叉概率与其交叉点相互交换两个个体的部分染色体，概率与其交叉点相互交换两个个体的部分染色体，从而产生两个新的个体。从而产生两个新的个体。A:1 0 1 1 0 1 1 1 0 0 单点交叉单点交叉A:1 0 1 1 0 1 1 1 1 1 B:0 0 0 1 1 1 0 0 1 1 B:0 0 0 1 1 1 0 0 0 0优优化化决决策策技技术术的的前前沿沿基本位变异算子（1）对个体的每一个基因座，依变异概率指定）对个体的每一个基因座，依变异概率指定其为变异点；其为变异点；（2）对每一个指定的变异点，对其等位基因值）对每一个指定的变异点，对其等位基因值作作取反运算取反运算或用或用其他等位基因其他等位基因来代替，从而产生来代替，从而产生一个新的个体。一个新的个体。A:1 0 1 1 0 1 1 1 0 0 A:1 0 1 1 1 1 1 1 0 0基本位变异基本位变异变异点变异点优优化化决决策策技技术术的的前前沿沿基本遗传算法的构成要素（4）运行参数）运行参数群体大小群体大小M，即种群中所含个体的数量；，即种群中所含个体的数量；一般取一般取20100终止进化代数终止进化代数T：交叉概率交叉概率Pc：一般取：一般取0.40.99变异概率变异概率Pm：一般取：一般取0.00010.1优优化化决决策策技技术术的的前前沿沿遗传算法的数学基础遗传算法的数学基础模式定理：在遗传算子选择、交叉和变异的作用下，具有：在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的模低阶、短定义距以及平均适应度高于群体平均适应度的模式在子代中将得以指数级增长。式在子代中将得以指数级增长。积木块假设积木块假设：低阶、距短、高平均适应度的模式（积木：低阶、距短、高平均适应度的模式（积木块）在遗传算子作用下，相互结合，能生成高阶、长距、块）在遗传算子作用下，相互结合，能生成高阶、长距、高平均适应度的模式，可最终生成全局最优解。高平均适应度的模式，可最终生成全局最优解。隐含并行性隐含并行性：遗传算法有效处理的模式个数为：遗传算法有效处理的模式个数为 收敛性分析与证明收敛性分析与证明：基本遗传算法收敛于最优解的概率小：基本遗传算法收敛于最优解的概率小于于1；使用最佳保留策略的遗传算法能收敛于最优解的概；使用最佳保留策略的遗传算法能收敛于最优解的概率为率为1 优优化化决决策策技技术术的的前前沿沿遗传算法的特点遗传算法的特点（1）良好的并行性）良好的并行性（2）很强的通用性）很强的通用性（3）良好的全局优化性能和稳健性）良好的全局优化性能和稳健性（4）良好的可操作性与简单性）良好的可操作性与简单性优优化化决决策策技技术术的的前前沿沿函数优化的实例（1）个体编码，把编码为一种符号串。）个体编码，把编码为一种符号串。本例中本例中x1，x2可分别用可分别用3位无符号二进制整数表位无符号二进制整数表示，把它们连接在一起组成的示，把它们连接在一起组成的6位无符号二进位无符号二进制制整数就形成个体的整数就形成个体的基因型基因型，表示一个可行解。，表示一个可行解。优优化化决决策策技技术术的的前前沿沿函数优化的实例基因型基因型 X101110表现型表现型 X5,6T个体的表现型和基因型之间可通过个体的表现型和基因型之间可通过编码和编码和解码解码相互转换。相互转换。优优化化决决策策技技术术的的前前沿沿函数优化的实例（2）初始种群的产生）初始种群的产生群体规模的大小取群体规模的大小取4每个个体随机产生每个个体随机产生（3）适应度计算）适应度计算直接以目标函数值作为个体的适应度直接以目标函数值作为个体的适应度优优化化决决策策技技术术的的前前沿沿函数优化的实例（4）选择运算）选择运算先计算出群体中个体的先计算出群体中个体的适应度之和适应度之和其次计算每个个体的其次计算每个个体的相对适应度相对适应度的大小的大小最后产生一个最后产生一个01之间的之间的随机数随机数，依据该，依据该随机数出现在上述哪一个概率区间随机数出现在上述哪一个概率区间来确定来确定各个个体被选中的次数。各个个体被选中的次数。优优化化决决策策技技术术的的前前沿沿函数优化的实例（5）交叉计算）交叉计算先对群体进行随机配对先对群体进行随机配对其次随机设置交叉位置其次随机设置交叉位置最后在相互交换配对染色体之间的部分基最后在相互交换配对染色体之间的部分基因因优优化化决决策策技技术术的的前前沿沿函数优化的实例（6）变异操作）变异操作首先确定各个个体的基因变异位置；首先确定各个个体的基因变异位置；然后依据某一概率将变异点的原有基因值然后依据某一概率将变异点的原有基因值取反。取反。优优化化决决策策技技术术的的前前沿沿函数优化的实例个体个体编号编号初始群初始群体体P(0)x1x2f i(x1，x2)f i/f i101110135340.24210101153340.24301110034250.17411100171500.35 f i143fmax50faver=35.75优优化化决决策策技技术术的的前前沿沿函数优化的实例选择选择次数次数选择结选择结果果配对配对情况情况交叉点交叉点位置位置交叉结交叉结果果变异变异点点变异结变异结果果10111011212：201100140111011111001111101511111101010113434：4101001211100121110011110116111010优优化化决决策策技技术术的的前前沿沿轮盘赌规则00.240.480.65优优化化决决策策技技术术的的前前沿沿函数优化的实例子代群子代群体体P(1)x1x2f i(x1，x2)f i/f i01110135340.1411111177980.4211100171500.2111101072530.23 f i235fmax98faver=58.75优优化化决决策策技技术术的的前前沿沿考试方式开卷考试开卷考试题目形式：题目形式：名词解释名词解释简答简答计算建模题计算建模题66、节制使快乐增加并使享受加强。德谟克利特67、今天应做的事没有做，明天再早也是耽误了。裴斯泰洛齐68、决定一个人的一生，以及整个命运的，只是一瞬之间。歌德69、懒人无法享受休息之乐。拉布克70、浪费时间是一桩大罪过。卢梭