1、优化算法 1 1模退火算法 2 算法 3粒子群算法 2 1模退火算法 一、模拟退火算法概念 模拟退火算法来源于固体退火原理，将固体加温至充分高，再 让其慢慢冷却，加温时，固体内部粒子随温升变为无序状，内能增大， 而慢慢冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时 达到基态，内能减为最小。 用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T 演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i 和控制参数初值t开始，对当前解重复“产生新解计算目标函数差接 受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似 最优解 3 1模退火算法 二、模拟退火算
2、法模型 模拟退火算法可以分为解空间、目标函数和初始解三部分。 三、 模拟退火的基本思想 (1) 初始化：初始温度T(充分大)，初始解状态S(算法迭代的起点)， 每个T值的 迭代次数L ； (2) 对k=1，L做第(3)至第6步： (3) 产生新解S (4) 计算增量t=C(S)-C(S)，其中C(S)为评价函数 (5) 若t0，然后转第2步。 4 1模退火算法 四、模拟退火算法特点 1.最终求得的解与初始值无关，与初始解状态S无关； 2.具有渐近收敛性，在理论上是一种以概率1收敛于全局最优解的 全局优化算法； 3.具有并行性。 5 2 算法 一、遗传算法概念 遗传算法简称GA，是模拟自然界遗传
3、机制和生物进化论而成的一 种并行随机搜索最优化方法。遗传算法将“优胜劣汰，适者生存”的生 物进化原理引入优化参数形成的编码串联群体中，按所选择的适应度函 数并通过遗传中的复制、交叉及变异对个体进行筛选，使适应度高的个 体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优 于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定 的条件。 6 2 算法 二、遗传算法基本操作 （1）复制：复制操作可以通过随机方法来实现。首先产生01之间均匀分布 的随机数，若某串的复制概率为40%，则当产生的随机数在0.401.0之间时 ，该串被复制，否则被淘汰 （2）交叉：在匹配池中任选两个染色体
4、，随机选择一点或多点交换点位置 ；交换双亲染色体交换点右边的部分，即可得到两个新的染色体数字串。 （3）变异：在染色体以二进制编码的系统中，它随机地将染色体的某一个 基因由1变为0，或由0变为1。 7 2 算法 三、遗传算法特点 （1）对参数的编码进行操作，而非对参数本身； （2）同时使用多个搜索点的搜索信息； （3）直接以目标函数作为搜索信息； （4）使用概率搜索技术； （5）遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜 索； （6）对于待寻优的函数基本无限制，它既不要求函数连续，也不要求函数可 微； （7）具有并行计算的特点. 8 2 算法 三、遗传算法的应用 （1）函数
5、优化； （2）组合优化； （3）生产调度问题； （4）自动控制：利用遗传算法进行控制器参数的优化、基于遗传算 法的模糊控制规则的学习、基于遗传算法的参数辨识、基于遗传算法 的神经网络结构的优化和权值学习； （5）机器人； （6）图像处理； （7）人工生命； （8）遗传编程； （9）机器学习； 9 2 算法 四、遗传算法的应用步骤 一：确定决策变量及各种约束条件，即确定出个体的表现型X和问题的解空间； 二：建立优化模型，即确定出目标函数的类型及数学描述形式或量化方法； 三：确定表示可行解的染色体编码方法，即确定出个体的基因型x及遗传算法的搜索空 间； 四：确定解码方法，即确定出由个体基因型x到个
6、体表现型X的对应关系或转换方法； 五：确定个体适应度的量化评价方法，即确定出由目标函数值到个体适应度的转换规 则； 六：设计遗传算子，即确定选择运算、交叉运算、变异运算等遗传算子的具体操作方 法。 七：确定遗传算法的有关运行参数，即M,G,Pc,Pm等参数。 10 2 算法 四、遗传算法的应用步骤 11 3粒子群算法 一、粒子群算法（PSO）的基本思想 它是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随 机搜索算法。通常认为它是群集智能的一种。它可以被纳入多主体优化系 统。 搜寻目前离的食物最近的鸟的周围区域 根据自己飞行的经验判断食物所在 已 知 鸟的位置 鸟当前位置和食物之间的距离
7、求 解 找到食物的最优策略 12 3粒子群算法 q 每个寻优的问题解都被想像成一只鸟，称为“粒子; q 所有的粒子都由一个Fitness Function 确定适应值以判断目前的位置好坏; q 每一个粒子必须赋予记忆功能，能记住所搜寻到的最佳位置; q 每一个粒子还有一个速度以决定飞行的距离和方向，这个速度根据它本身 的飞行经验以及同伴的飞行经验进行动态调整。 13 3粒子群算法 二、粒子群算法求解最优解 q D维空间中，有m个粒子； 粒子i位置：xi=(xi1,xi2,xiD)，将xi代入适应函数F(xi)求适应值； 粒子i速度：vi=(vi1,vi2,viD) 粒子i个体经历过的最好位置：
8、pbesti=(pi1,pi2,piD) 种群所经历过的最好位置：gbest=(g1,g2,gD) 通常，在第d（1dD）维的位置变化范围 限定在Xmin,d ,Xmax,d内，速度变化范围 限定在-Vmax,d ,Vmax,d内。 pbest xi gbest vi 14 3粒子群算法 q 粒子i的第d维速度更新公式： q 粒子i的第d维位置更新公式： 第k次迭代粒子i飞行速度矢量的第d维分量 第k次迭代粒子i位置矢量的第d维分量 c1,c2加速度常数，调节学习最大步长 r1,r2两个随机函数，取值范围0，1，以增加搜索随机性 w 惯性权重，非负数，调节对解空间的搜索范围 pbest gbe
9、st 15 3粒子群算法 三、粒子群算法流程 16 3粒子群算法 1.群族初始化：以随机的方式求出每一粒子的初始位置与速度； 2.计算适应度：根据 适应度函数计算出其适应度值以作为判断每个粒子的好坏； 3.寻找Pbest：找出每个粒子到目前为止，搜寻过程中的最优解； 4.寻找gbest：找出所有粒子到目前为止所搜寻到的全体最优解； 5.更新速度与位置：根据速度和位移更新公式，更新每个粒子的移动方向与速度 ； 6.判断是否收敛：通常算法达到最大迭代次数Gmax或者最佳适应度函数值的增量 小于某个给定的罚值时算法停止。 17 3粒子群算法 四、粒子群算法构成要素 群体大小m：m很小：陷入局部最优解的可能性很大 ；m很大：PSO的优化能力 很好，计算量大；一般取10-30个。 权重因子惯性权重w： w=0：粒子很容易趋向于同一位置 w小：倾向于局部探索,精细搜索目前的小区域 w大：扩展新的搜索区域,利于全局搜索 一般取0.9,1.2即可。 权重因子学习因子c1，c2：一般c1等于c2,并且范围在0和4之间； 最大速度Vm： Vm较大时，探索能力增强，但粒子容易飞过最优解； Vm较小时，开发能力增强，但容易陷入局部最优 Vm一般设为每维变量的取值范围。 1 2 3 4 18 3粒子群算法 四、粒子群算法优点 1、参数较少，容易调整 2、局部与全局结合，收敛速度快 19
