现代优化计算方法ppt课件.ppt

《现代优化计算方法ppt课件.ppt》由会员分享，可在线阅读，更多相关《现代优化计算方法ppt课件.ppt（48页珍藏版）》请在三一办公上搜索。

1、第十章 现代优化计算方法,10.1 引言 10.2 计算复杂性和启发式算法的概念 10.3 模拟退火优化算法 10.4 遗传优化算法 10.5 神经网络优化算法 10.6 混合优化算法 10.7 多学科设计优化,10.1 引言,Powell法、梯度法随机方向搜索法、复合形法、惩罚函数法,常规优化算法,启发式算法,适于求解高非线性、多约束、多极值问题, 现代优化计算方法： 模拟退火算法（Simulated annealing） 遗传算法（Genetic algorithms） 神经网络优化算法（Neural networks optimization） 混合优化算法（Hybrid optimiz

2、ation）,10.2 计算复杂性和启发式算法,一.计算复杂性,由于计算时间和存储空间的局限，某些算法在实践中不一定能得到解,算法的复杂性 算法的求解方法造成（例：求二阶导数）问题的复杂性 问题本身求解的复杂造成,求解问题的规模（维数）n 对复杂性的影响,10.2 计算复杂性和启发式算法,是相对于有严格数学背景的数学规划优化算法提出的。,二.启发式算法,是基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）内寻找最好的解，但不能保证所得的解就是最优解，以及此解与最优解的近似程度。,有严格数学背景梯度法、坐标轮换法、Powell法,通过揭示和模拟自然现象和过程，并综合数学、物理学、生物进

3、化、人工智能、神经科学和统计学等所构造的算法。也称构造型算法、智能优化算法。,10.3 模拟退火优化算法,一. 物理背景：,固体退火的物理过程和统计性质：（1）加温：随温度升高，粒子能量增高，与平衡位置的距离增大（2）等温：温度升至熔解温度，固体的规则性被打破，成为液体，粒子可以自由运动和重新排序，消除系统中原先存在的非均匀状态（3）冷却：随着温度的下降，粒子能量减弱，运动减小粒子最终进入平衡态，固化为具有最小能量的晶体,10.3 模拟退火优化算法,其中： E(r) 状态r的能量 k 常数 E 分子能量的一个随机变量 z(t) 概率分布的标准化因子 D0 最低能量状态的个数 D 状态空间中状态

4、的个数,相同温度下，分子停留在低能量状态的概率要更大,随着温度 t 不断降低，分子停留在低能量状态的概率不断增大,温度 t 下，分子停留在某一状态 r 满足 Bolztmann 概率分布：,分子停留在某种能量状态的概率与温度成反比,10.3 模拟退火优化算法,状态 迁移准则（ Metropolis 抽样稳定性条件）：,若新状态 j 的能量满足条件，则被用来替代原状态 i。高温下，接受能量差较大的新状态；低温下，只接受能量差较小的新状态。,二. 基本思想：,基本思想： 由某一较高的初始温度开始，利用上式在解域内随机搜索采样，随着温度不断降低，使系统的能量达到最低状态，即相当于能量函数的全局最优解

5、。,10.3 模拟退火优化算法,内循环,外循环,设求解优化问题,S.1 任选一个初始解（初始状态） x(0) ， 并令 k=0 ， x(k) =x(0) 和 tk= t0（初始退火温度t0应取较高的值），计算 f (x(k)；S.2 在温度tk下做下面循环：S.2.1 在当前的tk下随机产生新状态（候选解）x=genete (x(k)S.2.2 计算 f (x) 值和 f = f (x)f (x(k)S.2.3 若frandom(0,1) ，则令x(k) =x，转 S.3 ；否则转 S.2.1 S.3 若满足算法收敛（退火结束）准则，则转 S.4 ；否则令下一循环的退火温度 tk+1= upd

6、at(tk) （退温函数）和 k=k+1，转向 S.2 ；S.4 终止计算，输出结果，即取 x* =x 和 f (x*)= f (x)。,三.算法基本步骤：,10.3 模拟退火优化算法,内循环终止条件,1. 规定产生有限个候选解 ；2. 在连续若干步候选解的目标函数值变化很小：3. 目标函数值的均值已相当稳定。,外循环终止条件,1. 设置一个终止温度 te；2. 规定外循环的最大迭代次数kmax：3. 算法在每个tk值搜索到的最优解的值在若干次迭代内已保持不变。,三.算法基本步骤：,10.3 模拟退火优化算法,基本要求：应保证所产生的候选解可以遍及整个解域。,一般形式：,为摄动幅度系数；为服从

7、某种随机分布的变动量,例：已知各变量的变动范围,取,式中：r 0,1 之间均匀分布的伪随机数 K 区域缩减系数，取K1 分布系数，取正奇数1，3，5，7等,四.算法实现的几个技术问题 新状态产生函数 genete (x(k),10.3 模拟退火优化算法,min1,exp(-f /tk),基本要求,在某个退火温度tk下，接受目标函数值下降的候选解的概率要大；随着退火温度的下降，使接受目标函数值下降的候选解的概率越来越大，且当退火温度接近于0时，概率接近于1，即只能接受目标函数值下降的候选解。,一般形式,四.算法实现的几个技术问题 状态接受函数,10.3 模拟退火优化算法,算法实现的几个技术问题

8、初始温度,初温的选择方法： （初温大 获得高质量解的概率大 计算时间长）,式中：K 一个充分大的数，可取K10，20，100，等试验值； p初始接受概率。,1. 均匀抽样一组状态，以各状态目标函数值的方差为初温t0 ；2. 随机产生一组状态，确定两状态的目标函数差值 然后根据差值，利用一定的函数产生初温，如取 或,10.3 模拟退火优化算法,算法实现的几个技术问题 退温函数 updat(tk),常用的退温函数 ：,退温慢，候选解数目多 获得高质量解的概率大 计算时间长 退温快 计算效率提高 不能保证收敛到全局最优解,，其大小可以固定（同比率下降）也可以不断变化（变比率下降）。 接近于1，温度下

9、降得缓慢。此法简单易行，使用较多； ，式中t0为初始温度；K为算法温度下降的规定总次数,10.3 模拟退火优化算法,四. 小结,优点 ：,缺点 ：,可防止陷入局部最小点，获得全局最优解的可能性大；对初始点的稳定性好；无需求导，算法通用易实现。,为使获得全局最优解的可能性大，则所需花费的计算时间相对较长。,10.4 遗传优化算法,一. 背景：,生物进化基本循环图,依据生物进化论中的“适者生存”规律而提出：,10.4 遗传优化算法,遗传算法的主要生物进化特征体现在：（1）进化发生在解的编码（染色体）上。优化问题通过编码来研究。（2）自然选择规律决定哪些染色体产生超过平均数的后代。遗传算法通过优化目

10、标构造适应函数以达到好的染色体超过平均数的后代。（3）当染色体结合时，双亲的遗传基因的结合使得子女保持父母的特征。（4）当染色体结合后，随机的变异会造成子代与父代的不同。,一. 背景：,10.4 遗传优化算法,二. 基本思想：,遗传算法在求解优化问题时首先对求解空间的各个解进行编码。在寻优过程中，通过对染色体（解的编码，个体）进行结合（基因遗传、变异和交配），不断产生新的解，进而根据适应函数在新解中选择部分染色体继续进行结合，直至最终找到最好的解。,遗传基因：字符串的每一位数 编 码： 把解用字符串表示 群 体： 个体的集合,10.4 遗传优化算法,二. 基本思想：,例6-1 用遗传算法求mi

11、n f (x1,x2)= x1 + x2 ，当x1和x2为整数时的整数解，且,解：若用4位二进制编码表示一个设计变量 xi，则一个 解(x1, x2)需用8位二进制编码表示：,10.4 遗传优化算法,二. 基本思想：,例6-1,遗传算法的4个组成部分： 编码和解码、适应函数、遗传算子和控制参数,若以这4个个体为群体，按求解的要求，适应函数值小的染色体的生存概率较大，则能竞争上的是N1、 N3和N4点，其交配方式如下：,通过分别交换基因，实现了交配，得到了4个新个体N1、 N2、 N3和N4 。,若对某个个体（例如N2 ）进行基因变异（10），可得N2”: 0 0 1 0 0 0 0 1 (=3

12、),10.4 遗传优化算法,三. 算法的基本步骤：,S.1 选择优化问题求解的一种编码；S.2 随机产生N个染色体的初始群体 pop(k) , k=0 ；S.3 对群体中的每个染色体popi(k)计算适应函数 f i=fitness(popi(k)S.4 若满足终止规则，则转向S.9，否则计算概率S.5 以概率 pi 从 pop (k) 中随机选一些染色体构成一个新群体（其中可以重复选 pop (k) 中的元素） newpop(k+1)= popi(k) , i=1,2,N ,10.4 遗传优化算法,三. 算法的基本步骤：,S.6 通过交配，按交配概率 pc 得到一个有 N 个染色体的交配群体

13、crosspop (k+1)；S.7 以一个较小的变异概率 pm ，使得一个染色体的基因发生变异，形成变异群体mutpop (k+1) ；S.8 令 k= k+1 和 popi(k) = mutpop (k+1) ，返回S.3；S.9 终止计算，输出最优结果。,10.4 遗传优化算法,四. 算法实现的几个技术问题 编码和解码,编码由设计空间向编码空间的映射。将设计解用字符串表示的过程。编码的选择是影响算法性能和效率的重要因素。解码由编码空间向设计空间的映射。,10.4 遗传优化算法,连续变量x，在给定区间a,b的二进制编码策略（长度为l）：其中，二进制编码的长度为l，a1,a2,al 取0或1

14、，二进制码与实际变量的最大误差为(b-a ) / 2l,四. 算法实现的几个技术问题 编码和解码,例：求max f (x)=1-x2，x0,1。假设对解的误差要求为1/16,则可采用4个二进制编码（即l4），b-a=1，对照上式，有：,10.4 遗传优化算法,几种常见的编码方式,四. 算法实现的几个技术问题 编码和解码,10.4 遗传优化算法,对于求极大化的目标函数（即max . f (x) ），可通过下面转换建立与fitness(x)的映射关系:,四. 算法实现的几个技术问题 适应函数 fitness(x),时时,对于求极小化的目标函数（即min . f (x) ），可通过下面转换建立与fi

15、tness(x)的映射关系:,时时,Cmin和Cmax为可调参数，所取的值应使适应函数fitness(x)恒大于0。,适应函数用于对个体进行评价，即反映个体对问题环境适应能力的强弱。是优化进程发展的依据。其值必须大于等于零,10.4 遗传优化算法,群体规模 N 是影响算法性能和效率的因素之一。规模太小，不能提供足够多的采样点；规模太大，计算量大，耗时长。通常取N介于n（编码长度）和2n之间，或依据经验在范围内取值。,四. 算法实现的几个技术问题 算法参数,交配概率 pc 用于控制交配操作的频率，通常取0.40.9之间。概率太大，种群更新过快，会使一下高适应函数值的个体过快被破坏；概率太小，交配

16、操作很少进行，搜索速度慢，耗时长。,变异概率 pm 加大种群多样性的重要因素，通常取0.10.3之间。概率太大，则使遗传算法退化成随机搜索算法；概率太小，产生新个体的机会太小。,10.4 遗传优化算法,复制、交配、变异,四. 算法实现的几个技术问题 遗传算子,复制（选择） 目的是选择用于繁殖后代的双亲。体现“适者生存”，适应度高，生存概率大。依据选择概率 pi= fi / fi 进行。,交配 两个相互配对的染色体（双亲）按某种方式相互交换其部分基因而生称两个新的个体。方法：对选择的双亲以交配概率 pc 判断是否交配，对发生交配的双亲，随机选择交配位置，彼此交换基因，产生新个体。既继承了双亲的个

17、体特性，也产生了新的个体特性。,10.4 遗传优化算法,四. 算法实现的几个技术问题 遗传算子,一点交配（二进制）：,多点交配（二进制）：,10.4 遗传优化算法,四. 算法实现的几个技术问题 遗传算子,变异 在交配之后进行。将个体染色体编码字符中的某些基因用其他等位基因替换，从而生成新的染色体。可起到恢复丢失或生成遗传信息的作用，保持群体中个体的多样性，有效地防止算法早熟收敛。方法：按位进行，以概率 pm 改变字符串上某一位基因。,例：变异（二进制）,10.4 遗传优化算法,四. 算法实现的几个技术问题 算法终止准则,事先规定出一个最大的进化步数，到达此步数时终止。判断当前最好的解已连续若干

18、步没有变化。算法已找到了一个可接受的最好解。,10.4 遗传优化算法,五. 遗传算法与其他传统搜索方法的比较,遗传算法不是直接作用在解空间上，而是作用在解的某种编码上遗传算法从一个群体解（即多个解）而不是一个解开始搜索，这是它能以较大概率找到全局最优解的主要原因。遗传算法对搜索空间无任何特殊要求（如连通性、凸性），只利用适应度信息，而传统搜索算法一般要使用导数等其他辅助信息。遗传算法使用随机转移规则而不是确定性的转移规则。,10.5 神经网络优化算法,一. 基本概念生物神经网络,神经网络由相互关联的神经元组成，每个神经元由晶枝、内核和轴突组成。神经元通过晶枝接受信息，通过内核进行信息处理，再通

19、过轴突及其终端的突触将信息传递给其他的神经元。,生物学中神经网络简图,“兴奋性”的神经元：神经元的晶枝接受兴奋性信息累计超出某一值时，神经元被激活并传递出一个信息给其他神经元。“抑制性”的神经元：神经元虽接受到了兴奋性信息，但未向外传递信息。,10.5 神经网络优化算法,一. 基本概念人工神经网络,假设一个神经元通过晶枝接受到 n 个信息x1，x2，xn 。i 表示第i 个晶枝接受到信息的感知能力。输出函数 f (z) 定义为：,认知网络,其中：为阀值；()称为作用函数或传递函数，为非线性的单调增函数，通常为符号函数（阀函数）或Sigmoid函数（S形函数）,10.5 神经网络优化算法,一.

20、基本概念人工神经网络,有指导学习：已知一组正确的输入和输出结果的条件下，调整并确定权系数i 的方法。无监督学习：在只有输入数据而不知输出结果的前提下确定权系数的方法。人工神经网络通常分为前向型和反馈型前向型神经网络的计算分为学习阶段和应用阶段,10.5 神经网络优化算法,二. 人工神经网络模型和学习算法,多层前向型神经网络 由输入层、输出层和一个或若干个隐含层组成。,10.5 神经网络优化算法,二. 人工神经网络模型和学习算法,多层网络的学习问题一般采用反向传播算法，即BP（Back Propagation）算法，因而又称它为BP网络。,10.5 神经网络优化算法,二. 人工神经网络模型和学习

21、算法,设网络有L层（图中L2，即为2层网络），Nl为第l层的神经元的个数(l=0,1,2,L)。lL为输出层，神经元数为NL；l0为输入层，神经元数为N0 。,10.5 神经网络优化算法,二. 人工神经网络模型和学习算法,对于每一个0层的输入 (i=0,1,2, N0)有N个样本，第k个样本表示为 (i=0,1,2, N0，k=0,1,2, N)。设第l1层第i个单元的输出为 ，第l层第j个单元的输入为 ，它们的连接权系数值为 ， 为第l层第j个神经元的阀值，各神经元采用S形函数，则,10.5 神经网络优化算法,二. 人工神经网络模型和学习算法,BP学习的目的就是通过调整阀值和连接权系数值，使

22、得对所有输入样本的能量函数达到最小。对第k个输入样本 的能量函数为：,对所有输入样本 (k=0,1,2, N)的能量函数为：,其中： 是最后一层（即L层）的实际输出 是期望输出 (p=0,1,2, NL，k=0,1,2, , N),10.5 神经网络优化算法,二. 人工神经网络模型和学习算法,BP学习的规则采用梯度下降法，即 ：,其中：,10.5 神经网络优化算法,二. 人工神经网络模型和学习算法,S.1 随机确定初始权 ；S.2 用学习数据 计算期望输出 ；S.3 工作阶段（正向传播过程）：对每一组数据用神经网络计算实际输出 ；S.4 学习阶段（反向传播过程）：反向修正权值 ，直至学习完所有

23、数据。,BP学习算法的基本步骤 ：,10.5 神经网络优化算法,三. 神经网络优化计算,基于神经网络的优化算法的出发点在于：（1）神经网络是一种非线性动力系统，而且通过学习机制趋于稳定，并收敛到渐近平衡稳定点（2）神经网络渐近平衡稳定点恰好是能量函数的极小点,要想将神经网络方法用来建立优化算法，主要的工作是要把优化的目标函数和神经网络的能量函数对应起来，这样，当神经网络从初始状态趋向平衡稳定状态，（能量函数趋于最小），即完成了优化问题从初始点向最优解逼进的过程。,10.6 混合优化算法,一. 遗传模拟退火优化算法步骤,每两个温度之间的状态点是无关的，具有突跳性，可有效地避免陷入局部极小点，最终

24、获得全局优化解。,概率意义下的“优胜劣汰”机制寻优，具有并行搜索的优势。但在交配中有可能遗失最好解。,遗传算法：,模拟退火算法：,10.6 混合优化算法,一. 遗传模拟退火优化算法步骤,S.1 给定群体规模 N，初始退火温度 tk= t0，初始群体 pop(k) , 令k=0 ；S.2 若满足终止规则，则输出优化结果，否则执行下一步；S.3 在群体 pop(k) 中的每个染色体 ipop(k) 的邻域中随机选择一状态 j，按模拟退火中的接受概率 接受或拒绝 j，其中 f (i) 为状态 i的目标函数值，这一步共N 次迭代，选出新群体newpop1(k+1)；,10.6 混合优化算法,一. 遗传

25、模拟退火优化算法步骤,S.4 对新群体newpop1(k+1)计算适应函数 其中 fmin是newpop1(k+1)中的最小值；S.5 根据适应函数决定的概率分布，从newpop1(k+1)中随机选出N 个染色体构成种群newpop2(k+1)；S.6 按遗传算法的常规方法对newpop2(k+1)进行交配操作得到crosspop (k+1)，再进行变异操作得到mutpop (k+1)；S.7 令tk+1= updat(tk) ，k=k+1， pop(k)mutpop (k)，返回S.2 。,10.6 混合优化算法,二. 模拟退火单纯形优化算法,在 n 维空间中，由n+1个点组成的图形称单纯形

26、。 以一个目标函数值较小的新点，代替原单纯形中目标函数值最大的顶点，组成新的单纯形，这样不断地迭代，单纯形逐渐逼近最优点。 计算量小，可以较快得到局部最优解。,单纯形算法：,每两个温度之间的状态点是无关的，具有突跳性，可有效地避免陷入局部极小点，最终获得全局优化解。,模拟退火算法：,10.6 混合优化算法,二. 模拟退火单纯形优化算法步骤,S.1 给定单纯形顶点 n1个，初始退火温度 tk= t0，初始群体 SM(k) , 令k=0 ；S.2 计算单纯形各顶点的目标函数值，确定最大值、次大值和最小值的点；S.3 若满足终止规则，则输出优化结果，否则执行下一步；S.4 用单纯形的搜索方法求出局部

27、极小点。从单纯形中的每一个顶点 iSM(k) 中随机选择一状态 jN(i) ，按模拟退火中的接受概率决定接受或拒绝 j。这一步共进行 n1次迭代，选出新单纯形SM1(k+1) ；S.5 对新群体SM1(k+1) 计算适应函数，由适应函数决定的概率分布从SM1(k+1) 中随机选出n1个顶点，构成新单纯形SM2(k+1) ；S.6 令tk+1= updat(tk) ，k=k+1， SM(k) SM2(k) ，返回S.2 。,10.6 混合优化算法,三. 模拟退火神经网络优化算法步骤,S.1 随机产生初始权值(0)，确定初始退火温度 tk= t0，令k=1 ；S.2 利用BP算法计算(k)， ；S.3 用模拟退火算法（SA）进行搜索，利用SA状态产生函数产生新权 (k)(k) -1,1 为随机扰动 ；S.4 计算 (k)的目标函数值与(k)的目标函数值之差f；S.5 若min1,exp(-f /tk)random(0,1) ，则取(k)(k)，否则(k)保持不变；S.6 退温，令tk+1= updat(tk) ；S.7 若(k)对应的目标函数值满足精度要求，则终止算法，否则kk+1,返回S.2 。,