人工智能 课件 第四章 进化算法和群智能算法

人工智能第四章进化算法和群智能算法本章提纲4.1概述4.2遗传算法4.3差分进化算法4.5蚁群算法4.4粒子群算法本章提纲4.1概述4.2遗传算法4.3差分进化算法4.5蚁群算法4.4粒子群算法4.1概述概述优化技术是指在满足一定条件下，在众多或参数中寻找最优化方案或参数值，以是的某个或多个功能指标达到最优，或使系统的某些性能指标达到最大值或最小值。在计算智能和人工智能交叉工程应用领域得到广泛重视，鉴于实际工程问题的复杂性、约束性、非线性、多极小、建模困难等特点，需要寻求适用于大规模并行且具有智能特征的算法。智能优化算法又称为现代启发式算法，受人类智能、生物群体社会性或自然现象规律的启发，为接近复杂问题提供了新的思路和手段。智能优化算法大体可以分为五类：进化算法、群智能算法、模拟退火算法、禁忌搜索算法和神经网络算法。其中，进化算法通过模拟自然界群体和个人间的进化机制、合作竞争来设计搜索策略；群智能算法则受到生物群体行为研究的启发，将模拟生物群体寻径行为融入到求解高度复杂的优化问题中。本章提纲4.1概述4.2遗传算法4.3差分进化算法4.5蚁群算法4.4粒子群算法4.2遗传算法遗传算法（GeneticAlgorithm，GA）是一种进化算法，其基本原理是仿效生物界中的“物竞天择、适者生存”的演化法则，它最初由美国Michigan大学的J.Holland教授于1967年提出。70年代，K.A.Dejong基于遗传算法的思想，在计算机上进行了大量的纯数值函数优化计算试验[2]；80年代，遗传算法由D.E.Goldberg在一系列研究工作的基础上归纳总结而成。90年代以后，遗传算法作为一种高效、实用、鲁棒性强的优化技术，发展极为迅速，在机器学习、模式识别、神经网络、控制系统优化及社会科学等不同领域得到广泛应用。进入21世纪，以不确定性、非线性、时间不可逆为内涵的复杂性科学成为一个研究热点。遗传算法因能有效地求解NP(Non-deterministicPolynomial)问题以及非线性、多峰函数优化和多目标优化问题，得到了众多学科学者的高度重视，同时也极大的推动了遗传算法理论研究和实际应用的不断深入与发展。1.基本概念4.2遗传算法个体（individual）：指染色体带有特征的实体；种群（population）：个体的集合，该集合内个体数称为种群的大小；进化（evolution）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化；适应度（fitness）：度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝。1.基本概念选择（selection）：指决定以一定的概率从种群中选择若干个体的操作；复制（reproduction）：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因;交叉（crossover）：在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。又称基因重组，俗称“杂交”;变异（mutation）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状;编码（coding）：表现型到基因型的映射；解码（decoding）：从基因型到表现型的映射。4.2遗传算法4.2遗传算法2.算法流程遗传算法包括三个基本操作：选择、交叉和变异。（1）选择（selection），用来确定重组和交叉个体，以及被选个体将产生多少个子代个体。选择操作首先要计算适应度值，通常可以采取按比例的适应度计算或基于排序的适应度计算。其次，按照计算出来的适应度值进行父代个体的选择，通常采用的选择方法包含：轮盘赌选择、随机遍历抽样、局部选择、截断选择和锦标赛选择。4.2遗传算法2.算法流程（2）交叉（crossover），结合来自父代遗传种群的信息来产生新的个体。依据个体编码表示方法的不同，可以选择不同的交叉算法，对于实值编码，可以选择离散重组、中间重组、线性重组、扩展线性重组。对于二进制编码，可以选择单点交叉、多点交叉、均匀交叉、洗牌交叉、缩小代理交叉。（3）变异（mutation），交叉之后的子代基因按一定概率产生变化，依据个体编码表示方法的不同，可以采取实值变异和二进制变异两种方法。4.2遗传算法3.遗传算法的参数设置在遗传算法程序设计与调试中，有几个重要的参数对于算法性能有着至关重要的作用。（1）种群规模（2）交叉概率（3）变异概率（4）终止条件判断的最大进化代数4.2遗传算法4.算法的改进算法改进的方向通常针对个体基因的操作、种群的宏观操作、基于知识的操作和并行化遗传算法方面进行。（1）算法结构和参数的改进（2）有约束优化问题的遗传算法（3）并行遗传算法4.2遗传算法5.遗传算法优化实例

4.2遗传算法5.遗传算法优化实例背包（0-1）问题。有N件物品和一个容量为V的背包。第i件物品的体积是c(i)，价值是w(i)。求解将哪些物品放入背包可使物品的体积总和不超过背包的容量，且价值总和最大。算法流程：（1）初始化种群数目为Np=50，染色体维数为L=10，最大进化代数为G=100。（2）产生二进制初始种群，其中1表示选择该物品，0表示不选择该物品。适应度值等于所有被选中物品的价值总和，计算种群中个体适应度值，当物品体积总和大于背包容量时，对适应度值添加惩罚项计算。（3）对适应度进行归一化，采用基于轮盘赌的选择操作、基于概率的交叉和变异操作，产生新的种群，并把历代的最优个体保留在新种群中，进行下一步遗传操作。（4）判断是否满足终止条件：若满足，则结束搜索过程，输出优化值；若不满足，则继续进行迭代优化。本章提纲4.1概述4.2遗传算法4.3差分进化算法4.5蚁群算法4.4粒子群算法4.3差分进化算法差分进化算法（DifferentialEvolutionAlgorithm，DE算法）是一种简单的进化算法，1995年，该算法由RainerStorn和KennethPrice为求解chebyshev多项式而提出。DE是一种随机的并行直接搜索算法，它可对非线性不可微连续空间函数进行最小化，以其易用性、稳健性和强大的全局寻优能力在多个领域取得成功。应用在约束优化问题、聚类优化计算、非线性优化控制、神经网络、滤波器设计、阵列天线及其他方面得到广泛应用。差分进化算法4.3差分进化算法DE算法有两个阶段：种群初始化和进化迭代。种群初始化是在可行域内采用均匀分布等概率的生成初始空间解向量，进化迭代过程的操作有差分变异、交叉和选择等主要步骤。首先随机选择种群中两个互异的个体，进行差分和缩放，再加上种群中第三个随机个体来产生变异个体，然后父代个体和变异个体采用交叉操作获得试验个体，最后将试验个体和父代个体的适应度值进行比较，选择适应度值较优的个体进入下一代继续迭代，直到满足终止准则，停止迭代。1.标准DE算法：2.差分进化算法的参数设置全局优化算法的性能可以通过控制参数的适当选取来提升，对于差分进化算法可以参照一些经验规则来选取控制参数。（1）种群规模（2）变异算子（3）交叉算子（4）最大进化代数G（5）终止条件4.3差分进化算法3.改进DE算法DE算法的变形形式实际应用中根据具体问题，在差分进化算法的操作流程中的变异操作进行变形操作。4.3差分进化算法4.差分进化算法优化实例用离散差分进化算法求函数f(x,y)=-[(x2+y-1)2+(x+y2-7)2]/200+10的最大值，其中x的取值为-100~100之间的整数，y的取值为-100~100之间的整数，其函数值图形如图4-12所示。4.3差分进化算法本章提纲4.1概述4.2遗传算法4.3差分进化算法4.5蚁群算法4.4粒子群算法4.4粒子群算法粒子群算法1995年Kennedy等人模拟鸟群觅食的过程，提出了粒子群（ParticleSwarmOptimization,PSO）算法，后来演变为一种很好的优化工具。基本思想源于在鸟类觅食过程中通过集体协作和竞争达到迁移和聚集，PSO算法就是从这种模拟中得到启示并应用到求解优化问题中，这里的“粒子”表示优化问题解搜索空间中的一只鸟，每个粒子都对应有一个适应度值（fitnessvalue）来判定被优化函数是否达到最优值。4.4粒子群算法粒子群算法社会认知学的角度从另一个侧面，也给出了PSO算法的理论解释，即，群体中的每个个体都可以从过往经验和邻近个体表现中获得有益信息，该理论基础由以下三个主要基本因素组成：外在刺激的评价、与近邻的比较、领先个体的模仿。根据邻近粒子的定义范围，PSO算法可以分为全局模式和局部模式。两种模式表现出不同的算法性能，前者收敛速度较快，但会陷入局部极值；后者算法收敛速度较慢，但极少陷入局部极值。粒子群算法是一种并行算法。4.4粒子群算法1.算法基本原理PSO算法在初始化环节，使得一群粒子处于初始状态，包括了各个粒子的随机位置和随机飞行方向。粒子根据如下公式来对其位置和速度进行更新：从上式可以看出，公式(4-15)表示，第i个粒子在各维度方向上以速度vi来更新位置；速度vi的更新受到当前个体最优值和全局最优值信息的影响，即公式(4-14)中。4.4粒子群算法1.算法基本原理基本PSO优化算法的流程图如图4-14所示，每个粒子的位置和速度都以随机方式进行初始化，而后粒子的速度就朝着全局最优和个体最优的方向靠近，位置的更新由粒子的速度和移动所花费的时间决定。在运动过程中（即每一次迭代），都对每个粒子位置的适应度不断进行评价，当如果某个粒子的适应度值优于全局最优位置的适应度，则该粒子所处的位置就成为种群最优粒子位置，这样全局最优解将不断更新。在整个粒子群群体的运动过程中，每个粒子也根据自身适应度来更新个体的最优位置。由此表明，粒子在向全局最优解转移的同时，也向个体最优解靠拢4.4粒子群算法2.粒子群优化算法的参数设置（1）惯性权重在粒子速度的更新方程式(4-16)中加入惯性权重w，通过惯性权重来控制当前速度对下一速度的影响。

4.4粒子群算法2.粒子群优化算法的参数设置（2）学习因子c1=0代表无私型粒子群算法，"只有社会，没有自我"，迅速丧失群体多样性，易陷入局部最优而无法跳出；c2=0代表自我认知型粒子群算法，"只有自我，没有社会"，完全没有信息的社会共享，导致算法收敛速度缓慢；当c1=c2=0时，粒子将一直以当前速度飞行，直至到达边界。c1和c2都不为0代表完全型粒子群算法，更容易保持收敛速度和搜索效果的均衡，是较好的选择。学习因子值太小使粒子在目标区域外徘徊，值太大导致粒子越过目标区域。一般在[0,4]上取值。4.4粒子群算法2.粒子群优化算法的参数设置（4）种群规模一般来说粒子群的规模在20~40个，可以视所要解决的具体问题来调整种群规模。（3）收缩因子在速度更新公式中引入收缩因子，令当前速度调整结束后整体收缩后再更新。4.4粒子群算法2.粒子群优化算法的参数设置（5）拓扑结构拓扑结构采用一些参数来表示其结构信息及节点间的信息流动速度，其中有三个重要的参数：平均距离：两个节点间的平均边数；直径：两个节点间的最大距离；分配序列<d1,d2,…,dn>，其中di表示从一个节点出发经过i条边（不循环）可以到达的节点个数的平均值。4.4粒子群算法3.改进粒子群优化算法(1)离散PSO算法(2)基于雁群启示的PSO算法(3)遗传PSO算法4.4粒子群算法4.粒子群优化算例

4.4粒子群算法4.粒子群优化算例配电网无功优化问题。对于第三章例题所示的无功优化问题，利用粒子群算法进行求解。利用罚函数法，将电压和功率约束与目标函数结合，建立适应度函数f，4.4粒子群算法4.粒子群优化算例

本章提纲4.1概述4.2遗传算法4.3差分进化算法4.5蚁群算法4.4粒子群算法4.5蚁群算法蚂蚁能够借助自身分泌化学物质来给同伴传递信息，这种化学物质被称为信息素（pheromone），遇到危险时，信息素可以刺激蚁群来传递警示信息，依靠这种特殊的通信，蚂蚁可以在运动过程中通过感知信息素来指导自己的运动方向，按计划执行一项任务，而这种控制自身环境的能力是在其社会行为不断发展的过程中获取的。大量的蚂蚁聚集成群的蚁群集体行为便表现出一种信息正反馈现象，比如某一条路径走的蚂蚁越多，则后来者选择该路径的概率越大。基于这种觅食行为的模拟，Dorigon等提出了蚁群优化（AntColonyOptimization,ACO）算法来解决复杂优化问题，算法表现较强的鲁棒性并支持灵活的分布式计算机制。蚁群算法4.5蚁群算法如图4-24（a）所示，食物源在D点，蚂蚁以相同的速度从A点出发，可随机选择路线a-ABD或路线b-ACD，假设初始时每条路线分配一只蚂蚁，每个时间单位走一步，从图中可以看出，经过9个时间单位，走路线a的蚂蚁已到达食物源D，而走路线b的蚂蚁才走到路程的中间C点处。如图4-24（b）所示，经过18个时间单位，走路线a的蚂蚁到达食物源D后拿着食物又返回了起点A，而走路线b的蚂蚁刚好走到D点。久而久之，在信息素指导下