随机优化问题常见方法.ppt

PPT模板下载 随机优化问题常见方法 基于假设检验的模拟退火 SA 算法 1 微粒群算法 PSO 2 差分进化算法 DE 3 社会认知算法 SCO 4 目录 几种常见方法 基于假设检验的模拟退火算法 SimulatedAnnealing SA 要点分析 针对随机优化问题的不确定性 提出一类基于假设检验的模拟退火算法 该方法通过多次评价来合理估计解的性能 利用假设检验减少重复性搜索 采用突跳性搜索避免局部极小 并通过温度控制调节突跳能力 算法原理 模拟退火算法来源于固体退火原理 将固体加温至充分高 再让其徐徐冷却 加温时 固体内部粒子随温升变为无序状 内能增大 而徐徐冷却时粒子渐趋有序 在每个温度都达到平衡态 最后在常温时达到基态 内能减为最小 根据Metropolis准则 粒子在温度T时趋于平衡的概率为e E kT 其中E为温度T时的内能 E为其改变量 k为Boltzmann常数 用固体退火模拟组合优化问题 将内能E模拟为目标函数值f 温度T演化成控制参数t 即得到解组合优化问题的模拟退火算法 由初始解i和控制参数初值t开始 对当前解重复 产生新解 计算目标函数差 接受或舍弃 的迭代 并逐步衰减t值 算法终止时的当前解即为所得近似最优解 这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程 基于假设检验的模拟退火 SA 算法 基本思想及模型 1 初始化 初始温度T 充分大 初始解状态S 是算法迭代的起点 每个T值的迭代次数L 2 对k 1 L做第 3 至第6步 3 产生新解S 4 计算增量 t C S C S 其中C S 为评价函数 5 若 t 0 然后转第2步 微粒群算法 ParticleSwarmOptimization PSO 算法原理 PSO算法是基于群体的 根据对环境的适应度将群体中的个体移动到好的区域 然而它不对个体使用演化算法 而是将每个个体看作是D维搜索空间中的一个没有体积的微粒 点 在搜索空间中以一定的速度飞行 这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整 第i个微粒表示为Xi xi1 xi2 xiD 它经历过的最好位置 有最好的适应值 记为Pi pi1 pi2 piD 也称为pbest 在群体所有微粒经历过的最好位置的索引号用符号g表示 即Pg 也称为gbest 微粒i的速度用Vi vi1 vi2 viD 表示 思维依据 1 认知 部分可以由Thorndike的效应法则 lawofeffect 所解释 即一个得到加强的随机行为在将来更有可能出现 这里的行为即 认知 并假设获得正确的知识是得到加强的 这样的一个模型假定微粒被激励着去减小误差 2 社会 部分可以由Bandura的替代强化 vicariousreinforcement 所解释 根据该理论的预期 当观察者观察到一个模型在加强某一行为时 将增加它实行该行为的几率 即微粒本身的认知将被其它微粒所模仿 3 心理学假设 在寻求一致的认知过程中 个体往往记住自身的信念 并同时考虑同事们的信念 当其察觉同事的信念较好的时候 将进行适应性地调整 微粒群算法 算法流程 1 初始化一群微粒 群体规模为m 包括随机的位置和速度 2 评价每个微粒的适应度 3 对每个微粒 将它的适应值和它经历过的最好位置pbest的作比较 如果较好 则将其作为当前的最好位置pbest 4 对每个微粒 将它的适应值和全局所经历最好位置gbest的作比较 如果较好 则重新设置gbest的索引号 5 根据方程 变化微粒的速度和位置 6 如未达到结束条件 通常为足够好的适应值或达到一个预设最大代数Gmax 回到b 差分进化算法 DifferentialEvolution DE 要点分析 DE是一种模拟生物进化的随机模型 通过反复迭代 使得那些适应环境的个体被保存了下来 DE保留了基于种群的全局搜索策略 采用实数编码 基于差分的简单变异操作和一对一的竞争生存策略 降低了遗传操作的复杂性 同时 DE特有的记忆能力使其可以动态跟踪当前的搜索情况 以调整其搜索策略 具有较强的全局收敛能力和鲁棒性 求解问题 由于该方法不需要借助问题的特征信息 适于求解一些利用常规的数学规划方法所无法求解的复杂环境中的优化问题 主要用于求解连续变量的全局优化问题 基本思想 从某一随机产生的初始群体开始 利用从种群中随机选取的两个个体的差向量作为第三个个体的随机变化源 将差向量加权后按照一定的规则与第三个个体求和而产生变异个体 该操作称为变异 然后 变异个体与某个预先决定的目标个体进行参数混合 生成试验个体 这一过程称之为交叉 如果试验个体的适应度值优于目标个体的适应度值 则在下一代中试验个体取代目标个体 否则目标个体仍保存下来 该操作称为选择 主要包括三个步骤 变异 交叉 选择 差分进化 DE 算法 算法流程 社会认知算法 SocialCognitiveOptimization SCO 算法认识 社会认知优化算法是一种基于社会认知理论的集群智能优化算法 它适合于大规模的约束问题的处理 该算法已经在非线性规划问题求解中表现出了良好的效果 在过去的几十年中 很多模拟生物的智慧开发出的优化算法被相继提出 如遗传算法 蚁群算法 粒子群算法等 这些都是基于生物或昆虫系统的 从现实上来看 很显然 人类社会比昆虫社会有更高的社会性和智能性 一个人可以借助观察他人的行为以及其后果来学习 人类学习是观察别人的行为及其行为后果 并将其符号化的过程 我们将这种通过观察和模仿他人行为而获得的学习称为观察学习 这种观察学习是发生在社会之中的 所以也叫做社会学习 基本概念 知识点 知识点是位于知识空间 例如搜索空间s 中对位置X和水平 例如适应度 的描述构成的点 库 库是 个包含一系列知识点的表 这个表是有大小的 学习代理 学习代理是一个行为个体 支配库中的一个知识点 领域搜索 有两个点X和X 对X 的领域搜索就是以X 作为参考选出一个新的点 对第D维的点 在这里Rand 是一个在 0 1 的随机值 和分别定义为参考点和中心点 社会认知算法 算法流程 1 初始化过程 1 在库中随机生成所有的 个知识点 包括生成每个知识点的位置和其水平 2 给每个学习代理随机分配库中的一个知识点 但不允许把一个知识点重复分配给多个学习代理 2 替代学习过程 对每个学习代理 1 模仿学习 从库中随机选择两个或者多个知识点 一般选择两个就可以 但这些选出的知识点都不能和学习代理自身的知识点重复 然后基于竞争选择的原则在这几个知识点之间选出一个好的知识点 2 观察学习 对比选择出来的知识点和代理自身的知识点的水平 选择水平较好的那个点作为中心点 用较差的那个点作为参考点 然后学习代理基于领域搜索的原则根据这两个点移动到一个新的知识点 并且将新的知识点储存在库中 3 库更新过程 从库中移去个具有最差的水平的知识点 4 重复步骤2到步骤4 直到满足停止条件 例如达到预先确定的迭代次数 或者结果达到预先设定的精度 整个优化过程由一系列学习代理来完成 Thankyou