现代优化算法(数学建模).pptVIP

Algorithms in Mathematical Modeling Algorithms in Mathematical Modeling 数学建模现代优化算法 2014-7-20 目录 现代优化算法概论 模拟退火算法 遗传算法 蚁群算法 Part 1 概论 最优化问题(Optimization Problem) 最优化问题: 现代优化算法 现代优化算法 现代优化算法的特点 它们的共同特点：都是从任一解出发，按照 某种机制，以一定的概率在整个求解空间中探索 最优解。由于它们可以把有哪些信誉好的足球投注网站空间扩展到整个问 题空间，因而具有全局优化性能。 全局优化 (Rastrigin’s Function) 现代优化算法 特点： 1)不依赖于初始条件； 2)不与求解空间有紧密关系,对解域无可微或连续的要求;容易实现，求解稳健。 3)但收敛速度慢，能获得全局最优；适合于求解空间不知的情况。 4)SA、GA可应用于大规模、多峰多态函数、含离散变量等全局优化问题；求解速度和质量远超过常规方法。 Part 2 模拟退火法 模拟退火算法及模型 模拟退火算法及模型 模拟退火算法及模型 模拟退火算法及模型 模拟退火算法及模型 模拟退火算法及模型 组合优化与物理退火的相似性 SA算法描述 案例讲解 已知敌方100个目标的经度、纬度 我方有一个基地，经度和纬度为（70,40）。假设我方飞机的速度为1000公里/小时。我方派一架飞机从基地出发，侦察完敌方所有目标，再返回原来的基地。在敌方每一目标点的侦察时间不计，求该架飞机所花费的时间（假设我方飞机巡航时间可以充分长）。 算法描述(解空间与目标函数) 算法描述 算法描述 案例讲解 模拟退火算法及模型 模拟退火算法及模型 3.3 模拟退火算法关键参数和操作的设计 模拟退火算法关键参数和操作的设计 模拟退火算法关键参数和操作的设计 模拟退火算法关键参数和操作的设计 模拟退火算法关键参数和操作的设计 模拟退火算法关键参数和操作的设计 模拟退火算法关键参数和操作的设计 模拟退火算法的实现与应用 模拟退火算法的实现与应用 模拟退火算法的实现与应用 模拟退火算法的实现与应用 模拟退火算法的实现与应用 模拟退火算法的实现与应用 模拟退火算法的实现与应用 模拟退火算法的实现与应用 模拟退火算法的实现与应用 模拟退火算法的实现与应用 模拟退火算法的改进 模拟退火算法的改进 模拟退火算法的改进 模拟退火算法的改进 模拟退火算法的改进 Part 3 遗传算法 遗传算法(GA) Darwin(1859): “物竟天择，适者生存” John Holland (university of Michigan, 1975) 《Adaptation in Natural and Artificial System》 遗传算法作为一种有效的工具，已广泛地应用于最优化问题求解之中。 遗传算法是一种基于自然群体遗传进化机制的自适应全局优化概率有哪些信誉好的足球投注网站算法。它摒弃了传统的有哪些信誉好的足球投注网站方式，模拟自然界生物进化过程，采用人工的方式对目标空间进行随机化有哪些信誉好的足球投注网站。 遗传算法的有哪些信誉好的足球投注网站机制 遗传算法模拟自然选择和自然遗传过程中发生 的繁殖、交叉和基因突变现象，在每次迭代中 都保留一组候选解，并按某种指标从解群中选 取较优的个体，利用遗传算子(选择、交叉和变 异)对这些个体进行组合，产生新一代的候选解 群，重复此过程，直到满足某种收敛指标为止。 遗传算法(GA) 适者生存(Survival of the Fittest) GA主要采用的进化规则是“适者生存” 较好的解保留，较差的解淘汰 基本遗传算法 基本遗传算法（Simple Genetic Algorithms, 简称SGA）是一种统一的最基本的遗传算法，它只 使用选择、交叉、变异这三种基本遗传算子，其遗传 进化操作过程简单，容易理解，是其他一些遗传算法 的雏形和基础，它不仅给各种遗传算法提供了一个基 本框架，同时也具有一定的应用价值。 SGA实例1：函数最值 SGA参数: 编码方式: 二进制码 e.g. 00000?0; 01101 ? 13; 11111?31 种群规模: 4 随机初始群体 “转盘赌”选择 一点杂交, 二进制变异 SGA实例1 max x2 : 选择操作 SGA实例1 max x2 : 交叉操作 SGA实例1 max x2 : 变异操作 SGA实例2 : 连续函数最值 求下列函数的最大值： SGA实例2 : 编码 高精度 SGA实例2 : 编码 设定求解精确到6位小数，因区间长度为2-(-1)=3,则需将区 间分为3X106等份。因 2097