人工智能原理第8章-智能优化计算课件.pptx

1、第8章智能优化计算 8.1优化问题的分类 8.2优化算法分类 8.3梯度优化计算 8.4混沌优化 8.5模拟退火算法 8.6遗传算法 8.7蚁群算法 8.8粒子群算法及应用 8.9鱼群算法简介 8.10混合优化计算方法简介8.1优化问题的分类 优化问题分为函数优化和组合优化两大类。为便于测评各种优化算法的性能，人们提出了一些典型的测试函数和组合优化问题。组合优化问题是通过数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，可以涉及信息技术、经济管理、工业工程、交通运输和通信网络等许多方面。典型的组合优化问题有：背包问题、旅行商问题、装箱问题、皇后问题、可满足性问题、图的m着色问题8.2

2、优化算法分类 按照寻优机制来看，可分为串行优化算法和并行优化算法串行优化算法是指算法在每次优化迭代计算中，仅搜索解空间中的一个点（或状态）。并行优化算法是指算法的寻优机制通常采用类似于种群或群体的方式，在每次迭代计算中可同时完成对解空间的多点搜索，并提供多个备选可行解。下面将对各种优化算法做较为详细的介绍。8.3梯度优化计算 梯度优化计算方法是指算法所利用的启发式信息是按照优化函数梯度下降的方向实现优化计算的。典型的算法如第7章中所述的Hopfield神经网络、BP学习算法等。这类方法在优化过程中启发式信息发挥作用较大，算法收敛速度较快。但算法不具有全局寻优能力，所得优化解与初始解位置有直接关

3、系。8.4混沌优化1.基本混沌优化算法2.变尺度混沌优化算法3.双混沌优化搜索算法4.幂函数载波的混沌优化算法5.并行混沌优化算法1.基本混沌优化算法基本混沌优化算法思想比较简单，主要是采用混沌载波的方式将混沌状态引入到优化变量中，将混沌运动的遍历范围映射到优化变量的取值范围，然后利用混沌变量进行搜索。利用混沌运动的遍历性、随机性等特点提高搜索效率。混沌变量的发生机制选为式 的Logistic映射。该映射的混沌分叉及其对应的Lyapunov指数图如图所示。)1(1kkkxxux1.基本混沌优化算法图8-1Logistic映射分叉图图8-2Logistic映射Lyapunov指数图 当控制参数u

4、=4.0时，该映射是处于(0,1)之间的混沌满映射。由其产生的序列表现出了混沌系统的随机性、遍历性等基本特点，具有良好的搜索性能。混沌搜索虽然具有遍历性，但要在原始搜索空间内搜索到最优解可能需要较长的时间。因此基本混沌搜索算法中采用了二次载波技术来提高搜索效率。2.变尺度混沌优化算法变尺度混沌优化算法是在基本混沌优化算法的基础上提出的，主要特点是随着搜索进行，不断缩小优化变量的搜索空间，也可看成采用了多次二次载波搜索。该算法设定了细搜索标志r，只要在当前搜索空间内连续搜索一定次数后最优值未获得更新，则采用式(8-2)和式(8-3)缩小各变量的搜索范围。2.变尺度混沌优化算法在新空间内进行第k次

5、混沌搜索时，混沌搜索变量yik采用当前混沌变量xik与最优变量xi*的线性组合的形式得到，即kiikixxy*)1(111*riririiiabamxx3.双混沌优化搜索算法图8-3双混沌搜索算法示意图双混沌优化算法是结合了最大似然估计的思想，给出了缩小搜索空间的条件，从而提高了混沌优化算法的通用性。4.幂函数载波的混沌优化算法幂函数载波混沌优化算法采用幂函数载波的方式改善了logistic映射轨道的遍历性，混沌变量可在搜索区间内更均匀地遍历搜索。所采用的幂函数载波方式如下：图8-4Logistic 映射的遍历性 1,0,bzzbazzazzznqnnnnpnn5.并行混沌优化算法并行混沌优化

6、算法的主要思想是采用种群寻优的策略。通常对于中小规模的优化计算问题，串行混沌优化算法具有较高的寻优效率，而对于复杂度高的大型优化问题，采用并行混沌优化算法具有更好的寻优性能。8.5模拟退火算法模拟退火算法的来源是根据复杂组合优化问题与固体的退火过程之间的相似之处。该算法在系统向着能量减小的趋势变化过程中，偶尔允许系统跳到能量较高的状态，以避开局部最小，最终稳定在全局最小。8.6遗传算法8.6.1遗传算法中的关键参数与操作8.6.2遗传算法中的基本流程8.6.3遗传算法的改进8.6.4遗传算法的实现8.6.1遗传算法中的关键参数与操作GA是模拟遗传选择和自然淘汰的生物进化过程的计算模型。其所涉及

7、到的关键参数与操作主要有以下几点：1.编码 2.适应度函数：适应度函数主要用于对个体进行评价。3.算法参数：参数主要有种群数目、交叉概率、变异概率等。4.算法操作：包括选择（Selection，或复制Reproduction）、交叉（Crossover，或重组Recombination）和变异（Mutation）三种基本形式 5.算法终止条件：设定一定的算法终止条件来避免算法无停止的发展下去。图8-10标准遗传算法流程图标准的遗传算法主要步骤如下：标准的遗传算法主要步骤如下：8.6.3遗传算法的改进8.6.4遗传算法的实现 1.编码 2.目标函数以及适应度函数 3.遗传算子8.7蚁群算法蚁群算

8、法是受自然界中真实蚁群的集体觅食行为的启发而发展起来的一种基于群集智能的进化算法，属于随机搜索算法，它是由意大利学者Dorigo等人在二十世纪九十年代初首先提出来的。虽然蚂蚁本身的行为极其简单，但由这些简单个体所组成的蚁群却表现出极其复杂的行为特征。如蚁群除了能够找到蚁巢与食物源之间的最短路径外，还能适应环境的变化，即在蚁群运动的路线上突然出现障碍物时，蚂蚁能够很快地重新找到最短路径。8.7.1蚁群算法的研究现状 8.7.2基本蚁群算法的工作原理8.7.1蚁群算法的研究现状8.7.2基本蚁群算法的工作原理蚁群算法是一种基于群体的、用于求解复杂优化问题的通用搜索技术。与真实蚂蚁的间接通讯相类似，

9、蚁群算法中一群简单的蚂蚁(主体)通过信息素(一种分布式的数字信息，与真实蚂蚁的外激素相对应)进行间接通讯，并利用该信息和与问题相关的启发式信息逐步构造问题的解。所谓基本蚁群算法，指的是经典的ACS(Ant Colony System)算法，它具有当前很多种类的蚁群算法最基本的共同特征，后来一系列的改进蚁群算法都以此为基础。从中我们可以看出蚁群算法具有如下特征：(1)系统性。(2)分布式计算。(3)自组织性。(4)正反馈。8.8粒子群算法及应用粒子群优化（Particle Swarm Optimization,PSO）算法是由Kennedy和Eberhart于1995年提出的一种优化算法。PSO

10、算法的运行机理不是依靠个体的自然进化规律，而是对生物群体的社会行为进行模拟，它最早源于对鸟群觅食行为的研究。在生物群体中存在着个体与个体、个体与群体间的相互作用、相互影响的行为，这种行为体现的是一种存在于生物群体中的信息共享的机制。8.8.1基本粒子群优化算法 8.8.2粒子群优化算法的拓扑结构8.8.1基本粒子群优化算法 1.算法原理 2.算法流程 3.基本粒子群优化的参数 4.带惯性权重的粒子群算法 5.带收缩因子的粒子群算法1.算法原理1.算法原理2.算法流程 图8-11粒子群算法流程图(简化)3.基本粒子群优化的参数(1)种群大小(2)邻域大小(3)迭代次数(4)加速度系数(5)最大速

11、度(6)终止条件4.带惯性权重的粒子群算法为了更好的控制算法的探测(exploration)开发(exploitation)能力，Shi和Eberhart在1998年的IEEE国际进化计算学术会议上发表了题为“A Modified Particle Swarm Optimizer”的论文，在基本粒子群优化算法的速度更新公式(8-7)中引入了惯性权重W，将(8-7)式改变为：(8-9)惯性权重w的引入使得PSO算法的性能得到了很大提高，也使PSO算法应用到了很多实际问题中。在该算法中惯性权重w起着权衡PSO的全局寻优能力与局部寻优能力的作用，w值较大，全局寻优能力强，局部寻优能力弱，反之，则局部

12、寻优能力增强，而全局寻优能力减弱。图8-12表明粒子如何调整它的位置。)()(22111kidgdkkididkkidkidxprcxprcwvv图8-12粒子调整位置示意图刚开始惯性权重为常数，但后来的实验发现，动态惯性权值能够获得比固定值更为好的寻优结果。动态惯性权值可以在PSO搜索过程中线性变化，亦可根据PSO性能的某个测度而动态改变，比如模糊规则系统等。目前，采用较多的惯性权值是Shi建议的线性递减权值(linearly decreasing weight，简称LDW)策略，将惯性权重设为一个随时间线性减少的函数，惯性权重的函数形式通常为：)(maxmaxkKKwwwwiniendin

13、ik5.带收缩因子的粒子群算法Clerc建议采用收缩因子(constriction factor)来保证粒子群算法收敛，这也是另一个版本的标准算法。收缩因子是关于参数 和 的函数，一个简单的带收缩因子的粒子群算法定义为：(8-10)在使用Clerc的收缩因子方法时，通常取为4.1，从而收缩因子等于0.729。这相当于在速度更新公式中，使前一次速度乘0.729，并在其他两项中乘以0.7292.05=1.49445（还需乘以01之间的随机数）。对于Clerc设计的收缩因子法，不再需要设置最大速度限制，但是，后来研究发现设定最大速度限制()可以提高算法的性能。)()(22111kidkgdkidki

14、dkidkidxprcxprcvv422k21cc 4m axm axVx=8.8.2粒子群优化算法的拓扑结构(1)星形(star)(2)环形(ring)(3)轮式(wheel)(4)金字塔(pyramid)(5)四类(four clusters)(6)冯诺依曼(Von Nermann)(1)星形(star)(2)环形(ring)(3)轮式(wheel)(4)金字塔(pyramid)(5)四类(four clusters)(6)冯诺依曼(Von Nermann)8.9鱼群算法简介设向量Xi=(x1,x2,xn)表示人工鱼当前的状态；目标函数值Y=f(X)表示人工鱼当前状态的食物浓度；dij=D

15、istance(Xi,Xj)表示人工鱼Xi和人工鱼Xj之间的距离；Visual和分别表示人工鱼的视野范围和拥挤度因子，trynumber表示人工鱼每次觅食时最大的试探次数。算法描述如下：（1）觅食行为(Prey)（2）聚群行为(Swarm)（3）追尾行为(Follow)（4）行为的选择8.10混合优化计算方法简介1.混沌蚁群优化算法2.蚁群鱼群混合优化算法1.混沌蚁群优化算法针对函数优化问题，将搜索空间分成若干个子区域。利用混沌序列产生若干个测试点遍历在整个搜索空间，作为初始蚁群位置，初始蚁群根据各区域内的局部最优值确定各区域的初始信息素，然后利用混沌系统产生大量测试点作为工作蚁群，工作蚁群根

16、据不同区域内的信息素的含量，随机地选择不同的区域进行混沌搜索，根据搜索到的各区域内的新的局部最优值，不断更新各区域内的信息素含量，信息素含量越大的区域，混沌搜索的概率越大，也就越容易寻得更优解，从而信息素的含量就会进一步提高，这正是蚁群算法信息素正反馈的思想。将这种思想与混沌搜索相结合，最后利用工作蚁群不断地混沌搜索找到寻优函数的全局最优解。2.蚁群鱼群混合优化算法蚁群算法和鱼群算法都属于种群优化算法。他们的共同特点是，对于单个个体而言(蚂蚁或人工鱼)不存在智能行为，只是遵循某种规律而运动。但当个体数量达到一定程度时，整个种群将会表现出某种智能行为。蚁群算法是利用信息素正反馈的原理寻得最优路径

17、。人工鱼则按照“进步最快的原则”或者“进步即可的原则”从觅食、聚群和追尾三种行为选择一个合适的行为，最终实现寻优。由此可见，拥挤度是否在优化过程中起作用是这两种算法的核心区别。也就是说，鱼群算法相当于在蚁群算法中引入了拥挤度的概念，并且拥挤度在算法的寻优过程中始终起作用。拥挤度的引入，在算法的初期，可以避免算法的个体过早地集结到信息素高的路径上来，从而可避免算法出现早熟的现象，提高算法的全局寻优能力。但在算法后期，拥挤度将会对算法的收敛性以及收敛速度造成影响，例如，人工鱼最终不能够全部集结到最优值周围。也就是说，拥挤度在寻优初期可改善算法的寻优性能，在寻优后期则对寻优性能产生一定的负面影响。8.10混合优化计算方法简介