智能优化理论-第19章智能优化方法的统一框架

第19章智能优化方法的统一框架引言混沌优化算法的迭代结构遗传算法的迭代结构模拟退火算法的迭代结构蚁群优化算法的迭代结构标准粒子群优化算法的迭代结构梯度下降法的迭代结构复习思考题contents目录01引言关于智能优化方法的统一框架，目前多数研究都是针对进化算法提出的。Eiben和Aarts等1995年提出一种通用搜索程序(GeneralSearchProcedure)，为描述遗传算法、模拟退火算法、爬山法、深度优先搜索和广度优先搜索等迭代搜索算法提供了一个统一框架，其中定义了7个要素。Eiben和Smith于2003年提出一种包含6个要素的通用框架，其中包括解的表示、解的评价、种群、父体选择机制、重组和变异算子、选择／替换机制。引言Taillard等通过对禁忌搜索、遗传算法、蚁群算法等元启发方法(Meta-heuristics)的分析发现，这些算法的实现非常相似，并提出一种叫做“适应性记忆规划”(AdaptiveMemoryProgramming，AMP)的统一算法框架。AMP框架通过记忆机制来构造新解，通过改进机制来搜索更优解，并利用改进的解产生的知识来更新记忆。Talbi从设计空间和实现空间两个角度出发，提出一种混合算法的通用分类方法。引言引言010203刘波等从社会协作、自适应和竞争3个层面为基于种群的元启发式算法建立一种统一框架，并采用Markov链对统一算法模型进行收敛性分析。辛斌等在对差分进化算法和粒子群优化算法的混合算法进行全面综述和分析的基础上，提出一种包含母体算法关系、混合层次、操作顺序、信息传递类型和传递信息类型5层次的通用混合策略分类法。把搜索优化算法产生的解视为采样点，那么搜索优化算法可以视为一种迭代生成新的采样点的过程，其中描述新采样点生成方法的迭代算子或迭代函数就是最能反映算法本质的要素。用G表示迭代算子或迭代函数，那么G的性质就决定了算法的性质。例如，如果G是确定性算子，那么迭代过程就是确定性的，相应的算法就是确定性算法；如果G是随机算子，那么迭代过程就是随机性的，相应的算法就是随机性算法。对于G的分析而言，更重要的因素是它的实现所需利用的信息。引言02混沌优化算法的迭代结构混沌优化算法的迭代结构01混沌搜索过程的采样只利用相邻次序采样的解信息，不包含评价值信息。02迭代过程包括两个阶段，第一阶段是在整个搜索空间中随机采样，找到当前最优解的邻域；03第二阶段是在第一阶段找到的当前最优解的邻域内执行小范围的混沌搜索。04搜索方法与第一阶段无实质性差异，故第二阶段在缩小搜索范围后仍然采用此式所示的迭代形式。03遗传算法的迭代结构经典遗传算法的迭代过程涉及交叉、变异和选择3种算予。对于任何一个新的解（个体），用于产生该解的信息来自于上一代种群（父代）。父代个体参与选择（复制）操作，然后随机选择的两个个体执行交叉操作，交叉后的个体继续变异产生新解。遗传算法的迭代结构由于父代个体是随机选择的，每个个体都可能被选中，因此迭代算子利用的信息为<Xk-1，F(Xk-1)>。Xk-1不是单个解，而是第k-l代的所有解，而F(Xk-1)对应于这些解的评价信息。如果分别用S、C、M表示选择算子、交叉算子和变异算子，那么遗传算法的迭代过程可以表示为如下形式：GAs是复合式算子，表示选择、交叉和变异算子依次作用于上一代生成的解；X0为算法初始种群中的所有解；Pk包含种群规模、交叉概率和变异概率3个基本参数。遗传算法的迭代结构种群规模是一个特殊参数，是所有群搜索算法的共有参数。与一般参数不同，种群规模的变化会明显改变迭代过程。由上式容易发现，遗传算法的迭代中并未包含PSI，因为遗传算法不依赖于问题的特定信息。大多数智能优化算法都具有这种特征，这是智能优化算法具有较好通用性的重要原因之一。经典遗传算法采用固定参数，而参数自适应遗传算法采用参数动态或适应性调节策略。遗传算法的迭代结构04模拟退火算法的迭代结构模拟退火算法的迭代结构01在经典模拟退火算法的迭代过程中，主要步骤包括产生新状态和状态更新。02产生新状态依赖于状态产生函数，通常在当前状态的邻域结构内以一定概率方式生成。状态更新依靠状态接受函数，也以概率的方式给出，并且与温度有关。03模拟退火算法的迭代结构参数空间的迭代简化为；为模拟退火算法的迭代算子；yk表示第k次迭代时的当前状态。分别以Tk和yk表示状态产生函数和状态接受函数，则模拟退火算法的迭代过程可以表示为如下形式：其中，Tk为第k次迭代时的温度值，常见的温度调控策略将Tk设为k的单调递减函数或指数函数。y0=x0，x0为初始解。05蚁群优化算法的迭代结构蚁群优化算法的4个主要参数构成一个向量，通常这些参数采用固定设置。GACO为蚁群优化算法的迭代算子，实质上是一种基于概率模型进行随机采样的算子，其中只包含生成算子，不包含选择算子。算法采用的概率模型蕴含了采样过程中产生的所有解的信息（即SIk），这是因为每只蚂蚁在产生新解的过程中都留下了“信息素”，信息量的更新公式中记忆了历史信息，历史采样点对应的适应值等信息都蕴含在概率模型中。由于挥发机制的作用（由挥发因子ρ控制），历史信息对概率模型与新解产生过程的影响会逐渐衰退。蚁群优化算法的迭代结构06标准粒子群优化算法的迭代结构GPSO为粒子群优化算法产生新解的迭代算子；SPB为更新粒子的个体最优解的选择算子；SLB为更新粒子的邻域最优解的选择算子。xi,k为第k次迭伐时种群中第i个粒子的位置；为第i个粒子执行第k次迭代时利用的解信息；pbi,k为到第k次迭代完成为止种群中第i个粒子找到的最优解。lbi,k为到第k次迭代完成为止种群中第i个粒子所在的种群邻域内所有粒子找到的最优解，如果种群邻域覆盖所有粒子，则lbi,k=gbk，gbk表示到第k次迭代完成为止所有粒子找到的最优解。标准粒子群优化算法的迭代结构标准粒子群优化算法的迭代结构在经典PSO算法中，所有粒子的邻域都覆盖了整个群体，因此lbi,k=gbk(∀i∈{1,2，…，PS})。02由于惯性项的存在，每个粒子的位置历史信息蕴含在粒子速度中，因此PSO算法中的迭代算子隐含地运用了这3种信息的历史记录。03由于惯性因子的作用，历史信息的影响逐渐衰退。这一点与ACO的利用信息范围特征非常相似。01标准粒子群优化算法的迭代结构01对于经典PSO算法而言，其控制参数包括种群规模PS、惯性权重w、个体认知因子c1和社会学习因子c2。02对于种群拓扑结构可变的PSO算法，我们可以用矩阵表示所有粒子的信息互联关系。03种群拓扑也是PSO算法的一个重要控制参数。07梯度下降法的迭代结构010203梯度下降法不属于智能优化方法，但上述统一模型对数学规划研究中的经典方法同样适用。在连续变量优化研究中，梯度下降法是针对可微函数的一种经典局部优化方法。梯度下降法沿着目标函数的负梯度方向搜索，因为目标函数沿负梯度方向下降最快。梯度下降法的迭代结构梯度下降法的迭代结构式中，H(xk)为目标函数在点xk处的Hessian矩阵。其迭代方式为式中，∇f(xk)为目标函数在点xk处的梯度；γk为正数，表示沿梯度方向的搜索步长。采用如下迭代方法与梯度下降法相比，NewtonRaphson方法还利用目标函数的曲率信息使搜索方向更快地趋向局部最优解。不同的梯度下降法往往采用不同的步长调节方法。例如，在…上述各种经典迭代方法通常采用确定性的步长调节方法，但大多数方法都需要利用目标函数的梯度信息或者对其进行近似。梯度下降法或拟牛顿法的迭代结构可以表示为：需要强调的是，如果梯度的计算直接利用显式的梯度函数，则意味着算法利用了目标函数的全局信息。由于Newton-Raphson方法对二阶导数信息存在较强的依赖性，很多学者提出了近似方法以避免直接计算Hessian矩阵。梯度下降法的迭代结构那么算法的迭代结构应表示为：显然，无论梯度下降法还是拟牛顿法，都只适于局部搜索，而在多模态函数的优化中，其收敛结果明显依赖于初始解的位置。故