现代优化计算方法

第十章现代优化计算方法§10.1引言§10.2计算复杂性和启发式算法的概念§10.3模拟退火优化算法§10.4遗传优化算法§10.5神经网络优化算法§10.6混合优化算法§10.7多学科设计优化§10.1引言Powell法、梯度法随机方向搜索法、复合形法、惩罚函数法常规优化算法启发式算法适于求解高非线性、多约束、多极值问题——现代优化计算方法：模拟退火算法（Simulatedannealing）遗传算法（Geneticalgorithms）神经网络优化算法（Neuralnetworksoptimization）混合优化算法（Hybridoptimization）§10.2计算复杂性和启发式算法一.计算复杂性由于计算时间和存储空间的局限，某些算法在实践中不一定能得到解算法的复杂性算法的求解方法造成（例：求二阶导数）问题的复杂性问题本身求解的复杂造成求解问题的规模（维数）n对复杂性的影响§10.2计算复杂性和启发式算法是相对于有严格数学背景的数学规划优化算法提出的。二.启发式算法是基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）内寻找最好的解，但不能保证所得的解就是最优解，以及此解与最优解的近似程度。有严格数学背景——梯度法、坐标轮换法、Powell法通过揭示和模拟自然现象和过程，并综合数学、物理学、生物进化、人工智能、神经科学和统计学等所构造的算法。也称构造型算法、智能优化算法。§10.3模拟退火优化算法一.物理背景：固体退火的物理过程和统计性质：（1）加温：随温度升高，粒子能量增高，与平衡位置的距离增大（2）等温：温度升至熔解温度，固体的规则性被打破，成为液体，粒子可以自由运动和重新排序，消除系统中原先存在的非均匀状态（3）冷却：随着温度的下降，粒子能量减弱，运动减小粒子最终进入平衡态，固化为具有最小能量的晶体§10.3模拟退火优化算法1()P()exp()ErEErztkt其中：E(r)——状态r的能量k——常数E——分子能量的一个随机变量z(t)——概率分布的标准化因子D0——最低能量状态的个数D——状态空间中状态的个数相同温度下，分子停留在低能量状态的概率要更大随着温度t不断降低，分子停留在低能量状态的概率不断增大物理退火优化设计E（r）f（x）E（rmin）f（x*）温度t下，分子停留在某一状态r满足Bolztmann概率分布：分子停留在某种能量状态的概率与温度成反比§10.3模拟退火优化算法exprandom0,1ijEEkt状态迁移准则（Metropolis抽样稳定性条件）：若新状态j的能量满足条件，则被用来替代原状态i。高温下，接受能量差较大的新状态；低温下，只接受能量差较小的新状态。二.基本思想：基本思想：由某一较高的初始温度开始，利用上式在解域内随机搜索采样，随着温度不断降低，使系统的能量达到最低状态，即相当于能量函数的全局最优解。§10.3模拟退火优化算法min.nfRxx内循环外循环设求解优化问题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若Δf0则令x(k)=x’，转S.3；否则执行下一步S.2.4若状态接受函数min{1,exp(-Δf/tk)}random(0,1)，则令x(k)=x’，转S.3；否则转S.2.1S.3若满足算法收敛（退火结束）准则，则转S.4；否则令下一循环的退火温度tk+1=updat(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模拟退火优化算法'()1,2,,)kiixxin1,2,,)LUiiixxxin'()1()(21)1,2,,kULiiiixxxxrinK基本要求：应保证所产生的候选解可以遍及整个解域。一般形式：η为摄动幅度系数；ε为服从某种随机分布的变动量例：已知各变量的变动范围取式中：r——[0,1]之间均匀分布的伪随机数K——区域缩减系数，取K≥1α——分布系数，取正奇数1，3，5，7等四.算法实现的几个技术问题——新状态产生函数genete(x(k))§10.3模拟退火优化算法min{1,exp(-Δf/tk)}exprandom0,1ijEEkt基本要求1.在某个退火温度tk下，接受目标函数值下降的候选解的概率要大；2.随着退火温度的下降，使接受目标函数值下降的候选解的概率越来越大，且当退火温度接近于0时，概率接近于1，即只能接受目标函数值下降的候选解。一般形式四.算法实现的几个技术问题——状态接受函数§10.3模拟退火优化算法三.算法实现的几个技术问题——初始温度初温的选择方法：（初温大获得高质量解的概率大计算时间长）式中：K——一个充分大的数，可取K＝10，20，100，···等试验值；p——初始接受概率。1.均匀抽样一组状态，以各状态目标函数值的方差为初温t0；2.随机产生一组状态，确定两状态的目标函数差值然后根据差值，利用一定的函数产生初温，如取或()()maxmax()1,2,,min()1,2,,jjffjNfjNxx0maxtKfmax0ln()ftp§10.3模拟退火优化算法三.算法实现的几个技术问题——退温函数updat(tk)1,(0),01kkttk其中011,kkttkK常用的退温函数：退温慢，候选解数目多获得高质量解的概率大计算时间长退温快计算效率提高不能保证收敛到全局最优解1.，其大小可以固定（同比率下降）也可以不断变化（变比率下降）。α接近于1，温度下降得缓慢。此法简单易行，使用较多；2.，式中t0为初始温度；K为算法温度下降的规定总次数§10.3模拟退火优化算法四.小结优点：缺点：•可防止陷入局部最小点，获得全局最优解的可能性大；•对初始点的稳定性好；•无需求导，算法通用易实现。•为使获得全局最优解的可能性大，则所需花费的计算时间相对较长。§10.4遗传优化算法一.背景：生物进化基本循环图依据生物进化论中的“适者生存”规律而提出：§10.4遗传优化算法遗传算法的主要生物进化特征体现在：（1）进化发生在解的编码（染色体）上。优化问题通过编码来研究。（2）自然选择规律决定哪些染色体产生超过平均数的后代。遗传算法通过优化目标构造适应函数以达到好的染色体超过平均数的后代。（3）当染色体结合时，双亲的遗传基因的结合使得子女保持父母的特征。（4）当染色体结合后，随机的变异会造成子代与父代的不同。一.背景：§10.4遗传优化算法二.基本思想：遗传算法在求解优化问题时首先对求解空间的各个解进行编码。在寻优过程中，通过对染色体（解的编码，个体）进行结合（基因遗传、变异和交配），不断产生新的解，进而根据适应函数在新解中选择部分染色体继续进行结合，直至最终找到最好的解。遗传基因：字符串的每一位数编码：把解用字符串表示群体：个体的集合§10.4遗传优化算法二.基本思想：例6-1用遗传算法求minf(x1,x2)=x1+x2，当x1和x2为整数时的整数解，且12015xx和一个解（个体的染色体）适应函数（个体的表现型）f(x1,x2)N1：1011001114N2：1101111027N3：1000110121N4：0110010111解：若用4位二进制编码表示一个设计变量xi，则一个解(x1,x2)需用8位二进制编码表示：§10.4遗传优化算法二.基本思想：例6-1N4：01100101交配N1：10110011N4：01100101交配N3：10001101N1’：01110111=14N2’：10100001=11N3’：01000101=9N4’：10101101=23遗传算法的4个组成部分：编码和解码、适应函数、遗传算子和控制参数若以这4个个体为群体，按求解的要求，适应函数值小的染色体的生存概率较大，则能竞争上的是N1、N3和N4点，其交配方式如下：通过分别交换基因，实现了交配，得到了4个新个体N1’、N2’、N3’和N4’。若对某个个体（例如N2’）进行基因变异（1→0），可得N2”:00100001(=3)§10.4遗传优化算法三.算法的基本步骤：S.1选择优化问题求解的一种编码；S.2随机产生N个染色体的初始群体{pop(k),k=0}；S.3对群体中的每个染色体popi(k)计算适应函数fi=fitness(popi(k))S.4若满足终止规则，则转向S.9，否则计算概率S.5以概率pi从pop(k)中随机选一些染色体构成一个新群体（其中可以重复选pop(k)中的元素）newpop(k+1)={popi(k),i=1,2,···,N}11,2,,iiNiifpiNf§10.4遗传优化算法三.算法的基本步骤：S.6通过交配，按交配概率pc得到一个有N个染色体的交配群体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，二进制码与实际变量的最大误差为(b-a)/2l四.算法实现的几个技术问题——编码和解码122222llbababaxaaaa例：求maxf(x)=1-x2，x∈[0,1]。假设对解的误差要求为1/16,则可采用4个二进制编码（即l＝4），b-a=1，对照上式，有：331241241234234()222224816aaaaaaaaaaaa1137(0001),(0100),(0011),(1110)164168§10.4遗传优化算法几种常见的编码方式四.算法实现的几个技术问题——编码和解码§10.4遗传优化算法对于求极大化的目标函数（即max.f(x)），可通过下面转换建立与fitness(x)的映射关系:四.算法实现的几个技术问题——适应函数fitness(x)minminmin()()0fitness()0()0fxCfxCxfxC时时对于求极小化的目标函数（即min.f(x)），可通过下面转换建立与fitness(x)的映射关系:maxmaxmax()()fitness()0()CfxfxCxfxC－时时Cmin和Cmax为可调参数，所取的值应使适应函数fitness(x)恒大于0。适应函数——用于对个体进行评价，即反映个体对问题环境适应能力的强弱。是优化进程发展的依据。其值必须大于等于零§10.4遗传