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

《现代优化计算方法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章现代优化计算方法§6.1引言§6.2计算复杂性和启发式算法的概念§6.3模拟退火优化算法§6.4遗传优化算法§6.5神经网络优化算法§6.6混合优化算法§6.7多学科设计优化§6.1引言Powell法、梯度法随机方向搜索法、复合形法、惩罚函数法常规优化算法启发式算法适于求解高非线性、多约束、多极值问题——现代优化计算方法：模拟退火算法（Simulatedannealing）遗传算法（Geneticalgorithms）神经网络优化算法（Neuralnetworksoptimization）混合优化算法（Hybridopti

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

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

4、量的一个随机变量z(t)——概率分布的标准化因子D0——最低能量状态的个数D——状态空间中状态的个数相同温度下，分子停留在低能量状态的概率要更大随着温度t不断降低，分子停留在低能量状态的概率不断增大物理退火优化设计E（r）f（x）E（rmin）f（x*）温度t下，分子停留在某一状态r满足Bolztmann概率分布：分子停留在某种能量状态的概率与温度成反比§6.3模拟退火优化算法状态迁移准则（Metropolis抽样稳定性条件）：若新状态j的能量满足条件，则被用来替代原状态i。高温下，接受能量差较大的新状态；低温下，只接受能量差较

5、小的新状态。二.基本思想：基本思想：由某一较高的初始温度开始，利用上式在解域内随机搜索采样，随着温度不断降低，使系统的能量达到最低状态，即相当于能量函数的全局最优解。§6.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若

6、Δf<0则令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’)。三.算法基本步骤：§6.3模拟退火优化算法内循环终止条件1.规定产生有限个候选解；2.在连续若干步候选解的目标函数值变化很小：3.目标函数值的均

7、值已相当稳定。外循环终止条件1.设置一个终止温度te；2.规定外循环的最大迭代次数kmax：3.算法在每个tk值搜索到的最优解的值在若干次迭代内已保持不变。三.算法基本步骤：§6.3模拟退火优化算法基本要求：应保证所产生的候选解可以遍及整个解域。一般形式：η为摄动幅度系数；ε为服从某种随机分布的变动量例：已知各变量的变动范围取式中：r——[0,1]之间均匀分布的伪随机数K——区域缩减系数，取K≥1α——分布系数，取正奇数1，3，5，7等四.算法实现的几个技术问题——新状态产生函数genete(x(k))§6.3模拟退火优化算法m

8、in{1,exp(-Δf/tk)}基本要求在某个退火温度tk下，接受目标函数值下降的候选解的概率要大；随着退火温度的下降，使接受目标函数值下降的候选解的概率越来越大，且当退火温度接近于0时，概率接近于1，即只能接受目标函数值下降的候选解。一般形式四.算法实现的几