下载文档原格式
第五章现代优化计算方法§5.1 引言 §5.2 计算复杂性和启发式算法的概念 §5.3 模拟退火优化算法 §5.4 遗传优化算法 §5.5 神经网络优化算法 §5.6 混合优化算法§5.1常规优化算法 Powell法、梯度法引言随机方向搜索法、复合形法、惩罚函数法 启发式算法 适于求解高非线性、多约束、多极值问题现代优化算法：模拟退火算法（Simulated annealing） 遗传算法（Genetic algorithms） 神经网络优化算法（Neural networks optimization） 混合优化算法（Hybrid optimization）§5.2 计算复杂性和启发式算法一.计算复杂性 由于计算时间和存储空间的局限，某些算法在实践中不一 定能得到解 算法的复杂性 算法的求解方法造成（例：求二阶导数） 问题的复杂性 问题本身求解的复杂造成求解问题的规模（维数）n 对复杂性的影响二.启发式算法 是相对于有严格数学背景的数学规划优化算法提出的。
有严格数学背景——梯度法、坐标轮换法、Powell法 是基于直观或经验构造的算法，在可接受的花费（指 计算时间和空间）内寻找最好的解，但不能保证所得 的解就是最优解，以及此解与最优解的近似程度。
通过揭示和模拟自然现象和过程，并综合数学、物理 学、生物进化、人工智能、神经科学和统计学等所构 造的算法。
也称构造型算法、智能优化算法。
§5.3 模拟退火优化算法一. 物理背景： 固体退火的物理过程和统计性质： （1）加温：随温度升高，粒子能量增高，与平衡位置的距离 增大 （2）等温：温度升至熔解温度，固体的规则性被打破，成为 液体，粒子可以自由运动和重新排序，消除系统中原先存在的 非均匀状态 （3）冷却：随着温度的下降，粒子能量减弱，运动减小粒子 最终进入平衡态，固化为具有最小能量的晶体温度 t 下，分子停留在某一 状态 r 满足 Bolztmann 概率 分布：P E = E (r ) ={}1 ⎛ E (r ) ⎞ exp ⎜ − ⎟ z (t ) kt ⎠ ⎝其中： E(r) ——状态r的能量 k ——常数 E ——分子能量的一个随机变量 z(t) ——概率分布的标准化因子 D0 ——最低能量状态的个数 D ——状态空间中状态的个数 物理退火 E（r） E（rmin） 优化设计 f（x） f （x*）分子停留在某种能量状态的 概率与温度成反比随着温度 t 不断降低，分子停 留在低能量状态的概率不断增大 相同温度下，分子停留在低能量 状态的概率要更大二. 基本思想：状态 迁移准则（ Metropolis 抽样稳定性条件）：⎛ Ei − E j exp ⎜ ⎝ kt ⎞ ⎟ ≥ random ( 0,1) ⎠若新状态 j 的能量满足条件，则被用来替代原状态 i。
