人工智能原理及MATLAB实现 课件 第5章 计算智能

第五章计算智能第五章计算智能5.1进化算法定义进化计算（EvolutionaryAlgorithm，EA）是通过模仿自然界生物基因遗传与种群进化的过程和机制，而产生的一种群体导向随机搜索技术和方法。进化算法是一种模拟自然选择和遗传学机制的优化算法，包括遗传算法、遗传规划、进化策略和进行规划等。第五章计算智能5.1进化算法5.1.1遗传算法遗传算法（GeneticAlgorithms，GA）的基本思想是基于达尔文（Darwin）的进化论和孟德尔（Mendel）的遗传学说。20世纪70年代初，美国Michigen大学的约翰·霍兰德（JohnHolland）教授受到达尔文进化论的启发，用数码串来类比生物中的染色个体，通过选择、交叉、变异等遗传算子来仿真生物的基本进化过程，利用适应度函数来表示染色体所蕴涵问题解的质量的优劣，通过种群的不断“更新换代”，从而提高种群的平均适应度，通过适应度函数引导种群的进化方向，并在此基础上，使得最优个体所代表的问题解逼近问题的全局最优解。第五章计算智能5.1进化算法5.1.1遗传算法

5.1.1.1

遗传算法的基本原理1．编码与解码将问题变换为位串形式编码表示的过程称为编码；相反地，将位串形式编码表示变换为原问题结构的过程称为解码或码。把位串形式编码表示称为染色体或个体。编码的方法影响到遗传算子的计算方法。常用的编码方法有以下4种：（1）二进制编码。它是遗传算法编码中最常用的方法。（2）符号编码。（3）浮点数编码，也称为真值编码方法。（4）格雷编码。第五章计算智能5.1进化算法5.1.1遗传算法

5.1.1.1

遗传算法的基本原理2.适应度函数为了体现个体的适应能力，引入了对问题中的每一个个体都能进行量度的函数，即适应度函数。适应度函数表明个体或解的优劣性。常见的几种适应度函数变换方法：（1）线性变换：f(Z)=aZ+b（2）幂变换：f(Z)=Za（3）指数变换：f(Z)=exp(－βZ)对于有约束条件的极值，其适应度可用罚函数方法处理。第五章计算智能5.1进化算法5.1.1遗传算法

5.1.1.1

遗传算法的基本原理3.遗传算子遗传算子就是遗传算法中进化的规则。基本遗传算法的遗传算子主要有选择算子、交叉算子和变异算子。（1）选择算子。也称复制算子，是GA的关键。常用选择算子的操作方法有赌轮选择方法、排序选择法、最优保存策略。（2）交叉算子。交叉算子体现了自然界信息交换的思想，其作用是将原有群体的优良基因遗传给下一代，并生成包含更复杂结构的新个体。交叉算子有一点交叉、二点交叉、多点交叉和一致交叉等。（3）变异算子。变异算子是遗传算法中保持物种多样性的一个重要途径，它模拟了生物进化过程中的偶然基因突变现象。第五章计算智能5.1进化算法5.1.1遗传算法

5.1.1.2遗传算法的求解步骤1.对问题进行编码；2.定义适应度函数后，生成初始化群体；3.对于得到的群体进行选择复制，交叉，变异操作，生成下一代种群；4.判断算法是否满足停止准则。若不满足，则从步骤③起重复；5.算法结束，获得最优解。流程图第五章计算智能5.1进化算法5.1.1遗传算法

5.1.1.3算法控制参数的选择1.对问题进行编码；2.定义适应度函数后，生成初始化群体；3.对于得到的群体进行选择复制，交叉，变异操作，生成下一代种群；4.判断算法是否满足停止准则。若不满足，则从步骤③起重复；5.算法结束，获得最优解。第五章计算智能5.1进化算法5.1.1遗传算法

5.1.1.4遗传算法的特点编码性4.多解性和全局优性自适应性5.不确定性隐含并行性6.智能性第五章计算智能5.1进化算法5.1.2进化策略

20世纪60年代，德国柏林大学的因戈·雷切伯格（I.Rechenberg）和施韦费尔（H.P.Schwefel）等在进行风洞试验时，研究发展形成了进化策略方法。进化策略以其简单、通用、鲁棒性和适应性而闻名，在确定了编码方案、适应度函数及遗传算法以后，算法将根据“适者生存，不适者淘汰”的策略，利用进化中获得的信息自行组织搜索，从而不断地向最佳方向逼近。第五章计算智能5.1进化算法5.1.2进化策略算法基本流程第五章计算智能5.2模糊计算1965年，美国控制论专家拉特飞·扎德（L.A.Zadeh）把模糊性和数学统一起来，提出了模糊集合理论与模糊逻辑，它采用精确的方法、公式和模型来度量和处理模糊、信息不完整或不太正确的现象与规律。第五章计算智能5.2模糊计算5.2.1模糊系统理论基础模糊系统是建立在自然语言基础上的。在自然语言中常采用一些模糊概念如“大约”、“左右”、“温度偏高”等来表示一些量化指标，如何对这些模糊概念进行分析、推理，是模糊集合与模糊逻辑所要解决的问题。第五章计算智能5.2模糊计算5.2.2模糊规则和推理在模糊逻辑中，模糊规则实质上指的是模糊蕴含关系，即在“如果x是A，则y是B条件下，若x是，则y是”。其中A、、B、均代表模糊语言，并用A→B表示该提出条件，即A与B之间的模糊关系。第五章计算智能5.2模糊计算5.2.3模糊聚类分析物以类聚，将相似相像的事物归为一类，这就是聚类分析。模糊聚类分析是利用模糊等价关系来实现的。基于模糊等价关系的聚类分析可分为如下三步：第1步：建立模糊相似矩阵第2步：改造模糊相似关系为模糊等价关系第3步：聚类第五章计算智能5.3搜索算法1.搜索对象2.搜索的扩展规则3.搜索的目标测试5.3.1搜索过程的三大要素第五章计算智能5.3搜索算法（1）根据问题定义相应的状态空间，确定状态的一般表示，它含有相关对象各种可能的排列。（2）规定一组操作（算子），能够作用于一个状态后过渡到另一个状态。（3）决定一种搜索策略，使得能够从初始状态出发，沿某个路径达到目标状态。5.3.2搜索算法的基本步骤第五章计算智能5.3搜索算法随机搜索算法－模拟退火算法演化搜索算法－人工免疫算法记忆型搜索算法－禁忌搜索算法、和声搜索算法5.3.3典型的搜索算法第五章计算智能5.4群智能算法群智能算法是一类基于群体行为原理的优化算法，其灵感来源于自然界中的群体行为，如蚁群觅食、鸟群迁徙等。这类算法通过模拟群体中个体的行为和相互作用，寻找满足某种优化目标的解。一些典型的群智能算法：1.蚁群算法2.粒子群算法3.人工鱼群算法4.人工蜂群算法第五章计算智能5.4群智能算法5.4.1群智能概述最优化问题是个古老的课题，早在17世纪欧洲就有人提出了求解最大值最小值的问题，给出了一些求解法则，并随着科学的发展，逐渐提出了许多优化算法，由此形成了系统的优化理论和算法，如无约束优化和约束优化、线性规划、非线性规划、整数规划和动态规划等。受算法原理的限制，这些传统的优化算法一般只适用于求解小规模问题，在计算速度、收敛性、初值敏感性等方面远远达不到实际问题的优化要求，不适合求解复杂的优化问题，弱化了其在实际工程中的应用。第五章计算智能5.4群智能算法5.4.2群智能的一般框架在构建一个群智能算法中，应满足以下五条基本的原则：（1）ProximityPrinciple（2）QualityPrinciple（3）PrincipleofDiverseResponse（4）Stabilityprinciple（5）AdaptabilityPrinciple第五章计算智能5.4群智能算法5.4.3群智能的共性要素不同个体的群智能种群的表现形式是多种多样的，其中一些共性要素及其在群智能中发挥的作用是在构建群智能需要完成的工作。1.确定时空环境2.确定组织结构3.确定通信与语言形式4.确定竞争与合作等个体关系5.确定记忆信息与学习内容方式6.确定综合决策第五章计算智能5.4群智能算法5.4.4构建有效的群智能优化算法群智能优化算法是通过模拟群智能群体中个体与群体的行为而抽象出来的一种数学求解过程。群体智能是用随机分布在搜索优化空间的点来模拟自然界中的个体，用个体的进化过程作为随机搜索最优解的过程，用求解问题的目标函数来判断个体对于环境的适应能力，根据适应能力而优胜劣汰，将整个群体逐步向最优解靠近。第五章计算智能5.4群智能算法5.4.5群体智能算法的特点与传统的优化方法相比，群体智能算法具有以下的特点。1.简单的迭代式寻优2.环境自适应性和系统自调节性3.有指导的随机并行式全局搜索4.系统通用性和鲁棒性强5.智能性6.易于与其他算法相结合第五章计算智能5.4群智能算法5.4.6群智能优化算法蚁群算法粒子群算法人工鱼群算法人工蜂群算法第五章计算智能5.5混合优化算法混合优化算法策略的关键问题是问题分解与综合的处理、子算法和领域函数的选择、进程层次上算法转换接口的处理、优化过程中的数据处理。目前混合算法的结构类型主要可归结为串行、镶嵌、并行及混合结构。第五章计算智能5.5混合优化算法5.5.1混合优化策略的关键问题1.问题分解与综合的处理2.