智能优化理论 课件 第18、19章 自然云与气象云搜索优化算法、智能优化方法的统一框架

第18章自然云与气象云搜索优化算法自然云搜索优化算法气象云模型优化算法复习思考题讨论题contents目录自然云搜索优化算法01自然云搜索优化（CloudsSearchOptimizatlon，CSO）算法是2011年由曹炬和殷哲提出的一种模拟自然云的搜索算法。该算法是基于云的生成、动态运动、降雨和再生成等自然现象建立的一种搜索优化算法。生成与移动的云可以弥漫于整个搜索空间，使得该算法具有较强的全局搜索能力。自然云搜索优化算法的提出收缩与扩张的云团在形态上会有千奇百怪的变化，使得算法具有较强的局部搜索能力。通过对13种测试函数的仿真结果表明，该算法具有精确、稳定的全局求解能力。降雨后产生新的云团可以保持云团的多样性，使搜索避免陷入局部最优。并证明了该算法能依概率1收敛于全局最优解。自然云搜索优化算法的提出

自然云搜索优化算法的基本思想地面上的水和江、河、湖泊中的水受太阳光照射变热而蒸发，在高空冷凝形成小水滴或小冰晶，混合后可统一称为小水滴。随着时间推移，小水滴会变多，当它的大小达到人眼可辨识的程度时就在天空形成朵朵云团。各朵云团不断运动，在高空形成有一定规律的飘浮移动。高低气压差会产生由高气压处流向低气压处的气流，气流运动产生风。云团即刻消失，在天空中的某个位置又会有新的云团产生。云团自身的形态也不断变化。新生云团中的水滴杂乱无章地飘散开，在周围气流、内部气压及不均匀温度分布的影响下，水滴慢慢聚集。之后有规律地收缩或扩张，形成千奇百怪的姿态。云团继续飘移时吸收小水滴、小冰晶及空气中的灰尘，待云团达到一定重量，若其温度过低，会形成降雨。自然云搜索优化算法的基本思想03摸拟云的生成、动态运动、降雨和再生成等自然现象，可以构建一种新的优化算法——自然云搜索优化箅法。01移动的云团可以覆盖整个地球的上空，具有较强的弥漫性，云团的动态运动又与鸟群、鱼群有类似的群体运动特性。02降雨再产生新云团的过程又与生物进化论中的优胜劣汰机制相似。自然云搜索优化算法的基本思想由水滴组成，带动水滴一起移动，其形状抽象为一个球。云团云团半径水滴云团球形体的半径，大小R为，其中为半径因子；和分别为优化问题搜索空间的上限和下限。优化问题的潜在最优解，云团的组成部分，第i朵云团的第j水滴在空间中的位置记为。030201自然云搜索优化算法的数学描述云团中心水滴01每朵云团都有一个处于云团中心位置的水滴，即云团球体形状的球心，第i朵云团的中心水滴的位置记为。水滴速度02水滴移动的速度，第i朵云团的第j水滴的移动速度记为。水滴适应度值03在求最大值的函数优化问题中为水滴坐标对应的函数值，在求最小值的函数优化问题中为水滴坐标对应的函数值的相反数，第i朵云团的第j水滴的适应度值记为。自然云搜索优化算法的数学描述云团平均适应度值云团中所有水滴的适应度值的均值，第i朵云团的平均适应度值记为。云团最优水滴云团中适应度值最大的水滴，第i朵云团最优水滴的位置记为。全局最优水滴所有云团的所有水滴中适应度值最大的一个水滴，其位置记为。自然云搜索优化算法的数学描述最优水滴云团云团气压云团温度最优云团自然云搜索优化算法的数学描述全局最优水滴所在的云团，该云团中第j个水滴的位置记为。每个云团都有自己的温度值，为处理问题方便，该值粗略地定为每个云团的平均适应度值。每个云团都有着自己的气压值，为处理问题方便，该值粗略地定为每个云团的平均适应度值的相反数。气压值最小的云团，该云团的第j水滴的位置记为。自然云搜索优化算法的实现步骤目标函数和解空间均为n维，空间中每一维限定在区间。云团的个数为，每个云团中的水滴数为。总的迭代次数为N，当前迭代次数为t。在空间中随机产生点，作为朵云团的中心水滴位置，当前的代数为云团生成时间。第i朵云团的生成时间记为，最后按公式计算云团半径R，其中。每个云团随机产生等参数次，用来产生除中心水滴外的个水滴。123第i朵云团中第j水滴的位置计算如下：其中，为第i朵云团的中心水滴位置。计算所有云团内部水滴的适应度值及云团气压值。找出云团最优水滴、全局最优水滴，最优水滴云团、最优云团，将最优解更新为全局最优水滴的函数值。飘动过程。用式更新非最优水滴云团和最优云团的位置；用式更新最优云团的位置；用式更新最优水滴云团位置。自然云搜索优化算法的实现步骤01计算所有云团内部水滴的适应度值及云团温度值，将云团按温度值由高到低进行排序，找出温度最低的rain%的云团。02降雨过程。步骤(5)找出的云团中飘移代数大于等于rt的即刻消失，并按照步骤(l)和步骤(2)产生新的云团。03收缩扩张过程。云团飘动代数达到s后，用式和式进行收缩或扩张。迭代次数t=t+l，若t≤N，返回步骤(3)；否则输出最优值。自然云搜索优化算法的实现步骤010405060302自然云算法的优点：无论计算单峰还是多峰函数的最优值，CSO算法都表现出了优秀的性能。与PSO算法的比较表明，新算法有更好的优化性能，且在整个优化过程中可以不断计算出更接近理论最优值的结果。CSO算法展现出解决全局优化问题的巨大潜力。自然云搜索算法的局限性：算法涉及的参数较多，自适应性较差，改进算法使其性能更好且自适应能力强是一项很有意义的工作。算法中的一些操作也有必要改进，如水滴沿坐标轴的扩散方式会随问题维数的增加而变复杂。完善各项操作，创造出更合理、应用更广泛的全局优化算法也是一项非常有意义的工作。自然云搜索算法的优缺点分析气象云模型优化算法02气象云模型优化算法是一种随机优化算法，由郝占聚在2013年提出。算法通过云的移动行为和扩散行为保证全局搜索，并通过生成行为在当前全局最优位置附近完成局部搜索。这一算法在保证收敛性的同时，也保证了在各种不同初始条件下都能得到满意的结果。气象云模型优化算法的提出CSO算法的整个搜索过程包括云团的生成漂移、降雨生云及内部水滴的抖动3个步骤。ACMO算法将整个搜索空间模拟成由不同区域组成的空间，每个区域有自己的湿度值和气压值。气象云模型优化算法与自然云搜索优化(CSO)算法相似，但是两种算法的演化机制完全不同。气象云模型优化算法的基本思想算法的优化过程是通过云的生成、云的移动和云的扩张3个部分完成的。在运行过程中，在湿度值高的地区产生云，而生成的云则根据当地的大气压值，由气压高的区域向气压低的区域移动，并在移动的过程中逐渐扩散、消亡或聚集。算法以逆向搜索为主、正向搜索为辅的搜索机制对于多模态函数的求解具有一定的优势，也是气象云模型与其他智能优化算法的最大区别。将搜索空各地区的湿度值类比于所求问题空间各地区的适应度值；用各地区的气压值模拟历史上云滴飘过的数量。气象云模型优化算法的基本思想正态云与云滴数气象云模型优化算法中云的概念是通过正态云（正态分布云）模型描述的，设U是一个用精确数值量表示的定量论域空间，云C是U上的定性概念，定量值x∈U是C的一次随机实现。每一个x称为一个云滴，众多云滴在U上的分布称为云。云的整体特性可以用3个数字特征（期望、熵、超熵）和云滴数n来反映，其中，期望、熵和超熵分别反映云的中心位置、云的覆盖范围及云的厚度特性。云的产生、扩散、聚集规则将搜索空间分割成一个个互不重叠的小区域，每个区域都有自己的湿度值和气压值。云的产生、扩散、聚集行为遵循下面的规则。气象云模型优化算法的数学描述输入标题02010403气象云模型优化算法的数学描述湿度值超过一定阈值的区域才能产生云。在每一次云的移动或扩散后都会及时更新各个区域的湿度值和气压值，为下一次云的各种动作做准备，同时确定最佳适应度值的位置。云在移动的过程中，根据前后两次经过区域的气压差值进行扩散或聚集；当云扩散到一定程度或其云滴数小于某一定值时，认为此云消失。云由气压值高的区域以一定速度飘向气压值低的区域。010203气象云模型优化算法的整个搜索过程主要分为三个部分：云的生成、云的移动和云的扩散。云的生成保证算法的局部搜索能力，而云的移动和扩散行为构成算法的“逆向搜索”方法，用于算法的全局搜索。初始化阶段主要用于完成区域分割、区域湿度值和气压值的初始化与参数的设置等。气象云模型优化算法的实现步骤及流程区域湿度值和气压值的初始化过程，通过在搜索空间随机散布整个种群并根据式和式来完成。云的生成包括云模型的3个数字特征(Ex，En，He)及云滴数的计算。在生成云之前确定4个参数：可以生成的云的区域，从而确定云的中心位置；熵，用于确定云覆盖的范围大小；超熵，用于确定生成云的厚度；云滴数。气象云模型优化算法的实现步骤及流程确定可以生成云的区域计算熵值和超熵值采取新生成云的熵值随迭代逐渐减小策略气象云模型优化算法的实现步骤及流程不同迭代次数下新生成云的熵值定义迭代初期生成云的熵值较大，可覆盖较大地区迭代后期保持较长时间的较小值，提高算法收敛精度气象云模型优化算法的实现步骤及流程复习思考题03复习思考题01自然云搜索优化算法的基本原理是什么？自然云搜索优化算法的实现步骤是什么？02讨论题：自然云搜索优化算法主要有哪些优缺点？针对其缺点，需要采取哪些措施进行补充和完善？03气象云模型优化算法的基本思想是什么？气象云模型优化算法的实现步骤是什么？讨论题04讨论题01讨论题：气象云模型优化算法主要有哪些优缺点？针对其缺点，需要采取哪些措施进行补充和完善？02气象云模型优化算法的优点包括能更好地模拟真实世界的气象情况、提高天气预报的准确性和可靠性等。03缺点包括无法处理复杂地形、对初始条件敏感、难以实现长时间跨区域等。04针对其缺点，可以采取一些措施进行补充和完善，如引入地形修正、增加初始条件稳健性、实现长时间跨区域等。THANKYOU感谢观看第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算法的一个重要控制参数。