最优化方法课程大作业实验课件.pptx

1、最优化方法登山搜索算法1、产生一个初始点2、向临域最高的方向移动伪代码问题:依赖于初始状态,容易陷入局部最优改进：1、局部束搜索：随机产生多个初始点，并行搜索（多几个人从不同位置开始爬山，能到达最高点的概率就大大增大）2、随机重启：在指定步以后，简单地随机选取一个状态在指定步以后，简单地随机选取一个状态重新开始登山搜索重新开始登山搜索.模拟退火算法模拟退火算法是对登山算法的一种改进，以一定的概率接受更差的解，从而跳出局部最优的限制采用传统的登山搜索策略，但是 不时朝产生改进解的方向移动，即下山移动(downhill moves).随着时间的推移,采取下山移动的概率逐渐降低，并且下山移动的步长逐

2、渐减小1、产生初始点2、随机向周边移动3、移动后结果更优则接受4、移动后结果更差，则以一定的概率接受模拟退火模拟的是高温物体自然降温的过程，当温度较高的时候，分子运动速度快，接受更差解的概率更大时间增加温度随时间变化的函数如果温度降为零，则跳出循环随机选择当前点周围的一个点群智能鸟群算法 SeparationSeparationavoid crowding local flockmates AlignmentAlignmentmove towards the average heading of local flockmates CohesionCohesionmove toward the

3、average position of local flockmates 模拟鸟群的三个性质：鸟群的个体之间不会相撞鸟群有一个共同的目标方向个体会向团体中心聚拢产生初始点阵，每个点都有自己的运动方向与速度，这些点总体向着历史最优解方向移动，并且向当前所有点中的最优点聚拢x*=PSO()P=Particle_Initialization();For i=1 to it_max For each particle p in P do fp=f(p);If fp is better than f(pBest)pBest=p;end end gBest=best p in P;For each par

4、ticle p in P do v=v+c1*rand*(pBest p)+c2*rand*(gBest p);p=p+v;endend伪代码初始化一粒子群初始化一粒子群时间时间对与每一个粒子对与每一个粒子计算该粒子所在位置的权值计算该粒子所在位置的权值找出此时所有粒子中最优的找出此时所有粒子中最优的pbest维护历史（全局）最优的粒子维护历史（全局）最优的粒子gbest对于每个粒子，速度（矢量）变化，并朝速度方向移动对于每个粒子，速度（矢量）变化，并朝速度方向移动蚁群算法模拟蚁群寻最短路的算法1、蚂蚁在行进的过程会留下信息素，当碰到分叉的时候，蚂蚁会倾向于走信息素浓度更大的路径（倾向于表示有

5、更大的概率而非一定）2、信息素会随着时间的延长而稀释（某些算法不会考虑）3、蚂蚁行进的速度是一样的，因此在单位时间内，短路径上的蚂蚁数量比长路径上的蚂蚁数量要多，从而蚂蚁留下的信息素浓度也就越高伪代码遗传算法DNA链上记载有信息模拟自然界生物的遗传基因会发生变异自然（人工）选择，适者生存0123456789初始化基因夏娃DNA链复制并发生变异0123456789父代012745389S1代0123456789父代012745389S1代0123546789S2代017245389P1代总量小于容量，指数繁殖依据规则进行选择0123456789012745389017245389继续繁殖与选择幸

6、存者Init();For icapability)kill();初始化夏娃DNA在规定的时间内活的基因进行繁殖DNA链的复制DNA链的突变与重组选择并杀死劣质基因伪代码伪代码元元启发式算法（启发式算法（metaheuristic）元启发式算法是一种寻优能力很强的启发式算法。元启发式算法一种智能搜索算法，它的搜索空间由问题问题实例的实例的解解构成，通常涵盖完整的问题解空间。如果问题有n个解，一个启发式规则只能对应于n个解中的一个。启发式规则既可能产生很好的解，也可能产生很差的解。元启发式算法原理元启发式算法原理1.从一个或多个候选解开始作为初始值(pop(t)；2.根据初始值计算目标函数值；3.

7、基于已获得的信息，通过个体变异、组合等方法不断更新候选解域；4.新的候选解域进入下一轮迭代(pop(t+1)。元启发算法相当于在整个解空间内搜索最优解，当运行时间无限大时，理论上可以得到全局最优解。但是当问题规模不断扩大，使用元启发算法的效率也会降低。超启发算法通过制定高层控制策略来操纵底层贪心策略，从而压缩解空间，达到剪枝的目的（最优解所在的空间有可能被剪掉）。可以这样理解：元启发算法是随机交换，而超启发算法交换的时候要从贪心策略库中随机选择一种规则，交换的部分满足交换规则超启发算法步骤：1、根据常识或计算制定贪心规则库：（比如时间小的优先或其他贪心策略）2、从贪心规则库里随机选择一条，交换的时候必须满足这一规则。