人工智能原理及MATLAB实现 教案 第5章 计算智能

《人工智能算法》课程教案教学目的、要求：1.掌握进化算法、搜索算法、群智能算法、混合优化算法的基本概念和原理2.熟悉模糊计算基础知识3.理解算法的分析步骤、应用场景和优势4.能够实现简单的算法并进行实验验证教学重点及难点：重点：算法的原理难点：简单算法的实现和应用教学基本内容教学过程设计§5计算智能§5.1进化算法进化算法是一种模拟自然选择和遗传学机制的优化算法，用于解决复杂的搜索和优化问题，其应用广泛。进化算法包括遗传算法、遗传规划、进化策略和进行规划等，在此只介绍遗传算法和进化策略。遗传算法（GeneticAlgorithms，GA）：基本思想是基于达尔文（Darwin）的进化论和孟德尔（Mendel）的遗传学说；工作对象是字符串。对于整个遗传算法影响最大的是编码和适应度函数的设计。编码是应用遗传算法时要解决的首要关键问题。编码的方法也影响到遗传算子的计算方法。常用的编码方法有以下4种：（1）二进制编码。它是遗传算法编码中最常用的方法。（2）符号编码。（3）浮点数编码，也称为真值编码方法。适用于精度要求较高的遗传算法，以便于在较大空间进行遗传搜索。（4）格雷编码。为了体现个体的适应能力，引入了对问题中的每一个个体都能进行量度的函数，即适应度函数。适应度函数求取的是极大值，并且具有非负性。常见的几种变换方法：（1）线性变换：f(Z)=aZ+b（2）幂变换：f(Z)=Za（3）指数变换：f(Z)=exp(－βZ)对于有约束条件的极值，其适应度可用罚函数方法处理。遗传算子就是遗传算法中进化的规则。基本遗传算法的遗传算子主要有选择算子、交叉算子和变异算子。遗传算法的具体步骤：①对问题进行编码；②定义适应度函数后，生成初始化群体；③对于得到的群体进行选择复制，交叉，变异操作，生成下一代种群；④判断算法是否满足停止准则。若不满足，则从步骤③起重复；⑤算法结束，获得最优解。遗传算法中需要选择的参数主要有串长l、群体大小n、交叉概率pc以及变异概率pm等。与其他方法相比，遗传算法具有编码性、多解性和全局优化性、自适应性、不确定性、隐含并行性、智能性的优点。进化策略（EvolutionStrategies，ES）：20世纪60年代，德国柏林大学的因戈·雷切伯格（I.Rechenberg）和施韦费尔（H.P.Schwefel）等在进行风洞试验时，研究发展形成了进化策略方法。进化策略以其简单、通用、鲁棒性和适应性而闻名，是专门为求解参数优化问题而设计的，而且在进化策略算法中引入了自适应机制。算法的基本流程。算法的构成要素：染色体构造：（X,σ）=（（x1,x2,…,xL），（σ1,σ2,…,σL））算子：①重组算子。重组是将参与重组的父代染色体上的基因进行交换，形成下一代的染色体的过程。目前常见的有离散重组、中间重组、混杂重组等；②变异算子：③选择算子。在进化策略中，选择过程是确定性的。在不同的进行策略中，选择机制也有所不同。§5.2模糊计算1965年，美国控制论专家拉特飞·扎德（L.A.Zadeh）把模糊性和数学统一起来，提出了模糊集合理论与模糊逻辑，它采用精确的方法、公式和模型来度量和处理模糊、信息不完整或不太正确的现象与规律。模糊集是一种边界不分明的集合。隶属函数的表示方法：模糊系统中常用的隶属度函数有11种，例如高斯形、钟形等隶属度函数。模糊集运算：交集（逻辑与）、合集（逻辑或）/逻辑非（余）、模糊集的基。设A∈F(U)，对任意λ∈[0，1]，集合称为集合A的λ截集，λ称为阈值或置信水平。截集的概述描述了模糊集合与普通集合之间的转换关系。模糊度是模糊集合的度量，有以下几种计算方式：距离模糊度。设A0.5是A的λ＝0.5截集，有熵模糊度。如果令，则熵模糊度的定义为贴近度。用距离刻画模糊集的模糊度效果不是很理想，可以用贴近度来衡量两个模糊集之间的相近程度，贴近度越大，则表明这两者越接近。聚类分析就是将相似相像的事物归为一类。模糊聚类分析是利用模糊等价关系来实现的。基于模糊等价关系的聚类分析可分为三步：（1）建立模糊相似矩阵第一步是求样本集中任意两个样本Xi与Xj之间的相似系数rij，进而构造模糊相似矩阵R=(rij)n×n。①数量积法②相关系数法还包括绝对值减数法、算术平均法等。（2）改造模糊相似关系为模糊等价关系（3）聚类对求得的模糊等价矩阵求λ－截集Rλ，再将Rλ中为1的元素对应行和列的对象归并为一类，由Rλ的分类由细变粗，形成一个动态的分类图。§5.3搜索算法搜索过程有三大要素：搜索对象、搜索的扩展规则和搜索的目标测试。通过搜索求解问题的基本思想：（1）将问题中的已知条件看成状态空间中的初始状态；将问题中要求达到的目标看成状态空间中的目标状态；将问题中其他可能发生的情况看成状态空间中的任一状态。（2）设法在状态空间寻找一条路径，由初始状态出发，能够沿着这条路径达到目标状态。典型的搜索方法有：随机搜索算法（例如模拟退火算法）、演化搜索算法（例如人工免疫算法）、记忆型搜索算法（例如禁忌搜索算法、和声搜索算法）。§5.4群智能算法群智能（SwarmIntelligence，SI）的概念最早由贝尼（Beni）、哈克伍德（Hackwood）和王（Wang）等人在分子自动机系统中提出，指的是“无智能的主体通过合作表现出宏观智能行为的特性”。1999年，埃里克·博纳博（EricBonabeau）、马尔科·多里戈（MarcoDorigo）和盖伊·特络拉兹（GuyTheraulaz）在《SwarmIntelligenceFromNaturetoArtificialSystems》中对群智能进行了详细的论述和分析。群智能算法是一类基于群体行为原理的优化算法，其灵感来源于自然界中的群体行为，如蚁群觅食、鸟群迁徙等。这类算法通过模拟群体中个体的行为和相互作用，寻找满足某种优化目标的解。在构建一个群智能算法中，应满足五条基本原则：邻近原则、品质原则、多样性原则、稳定性原则、适应性原则。群体智能是用随机分布在搜索优化空间的点来模拟自然界中的个体，用个体的进化过程作为随机搜索最优解的过程，用求解问题的目标函数来判断个体对于环境的适应能力，根据适应能力而优胜劣汰，将整个群体逐步向最优解靠近。与传统的优化方法相比，群体智能算法具有简单的迭代式寻优、环境自适应性和系统自调节性、有指导的随机并行式全局搜索、系统通用性和鲁棒性强、智能性、易于与其他算法相结合的特点。一些典型的群智能算法：1.蚁群算法（AntColonyOptimization，ACO）：是一种基于种群寻优的启发式搜索算法。该算法受到自然界中真实蚁群通过个体间的信息传递、搜索从蚊穴到食物间的最短距离的集体寻优特征的启发，来解决一些离散系统中优化的困难问题。目前，该算法已被应用于求解旅行商问题、指派问题以及调度问题等，取得了较好的结果。作为一种随机优化方法，蚂蚁算法不需要任何先验知识，最初只是随机地选择搜索路径，随着对解空间的了解，搜索更加具有规律性，并逐渐得到全局最优解。各种形式的蚁群算法中，蚂蚁数量m、信息启发式因子α、期望值启发式因子β和信息素挥发因子ρ都是影响算法性能的重要参数。粒子群算法（ParticleSwarmOptimiztion，PSO）：是一种有效的全局寻优算法，最初由美国学者肯尼迪（Kennedy）和埃伯哈特（Eberhart）于1951年提出。它是基于群体智能理论的优化算法，通过群体中粒子间的合作与竞争产生的群体智能指导优化搜索。由于每代种群中的解具有“自我”学习提高和向“他人”学习的双重优点，从而能在较少的迭代次数内找到最优解。目前该方法已广泛应用于函数优化、数据挖掘、神经网络训练等领域。肯尼迪等通过观察鸟群觅食提出了两种粒子群算法模式即全局模式（globalversionPSO）和局部模式（localversionPSO）。3.人工鱼群算法（ArtificialFishSchoolAlgorithm，AFSA）：是由李晓磊博士于2002年首次提出。通过研究鱼群的行为，李晓磊总结并提取了适用于鱼群算法几种典型行为－鱼的觅食行为、聚群行为和追尾行为，并用之于寻优过程，进而形成了鱼群优化算法。4.人工蜂群算法（ArtificialBeeColonyAlgorithm，ABC）：是由卡拉伯卡（Karaboga）于2005年提出的基于蜜蜂群体的觅食行为的一种新的启发式仿生算法，它建立在蜜蜂群体生活习性模型基础上，模拟了蜂群依各自分工不同协作采蜜、交换蜜源信息以找到最优蜜源这一群体行为。ABC算法具有良好的优化能力，可以用来解决数值优化问题，在其他方面如生产调度、路径规划等方面也取得了良好的应用效果。ABC算法将全局搜索和局部搜索的方法相结合，从而使得蜜蜂在食物源的开采和探索这两方面取得了很好的平衡。ABC算法的寻优过程由四个选择过程构成：①局部选择过程；②全局选择过程；③贪婪选择过程；④随机选择过程。§5.5混合优化算法如今，算法混合（组合）的思想已发展成为提高算法优化性能的一个重要且有效的途径，其出发点就是使各种单一算法相互取长补短，产生更好的优化效率。该策略的关键问题是问题分解与综合的处理、子算法和领域函数的选择、进程层次上算法转换接口的处理、优化过程中的数据处理。目前混合算法的结构类型主要可归结为串行、镶嵌、并行及混合结构。串行结构是一种最简单的结构，它的混合算法就是吸收不同算法的优点，用一种算法的搜索结果作为另一种算法的起点依次来对问题进行优化。设计串行结构的混合算法需要解决的问题主要是确定各种算法的转换时机。镶嵌结构表示为一种算法作为另一种算法的一个优化操作或用操作搜索性能的评价器。设计镶嵌结构的混合算法需要解决的问题主要是子算法与嵌入点的选择。并行结构包括同步式并行，异步式并行和网络结构。问题分解与综合以及进程间的通信问题是设计并行结构的混合算法需解决的主要问题。§5.6计算智能的matlab实战算法例题讲解3min引入：通过生物界自然选择、变异和杂交等自然进化方式实例引入。内容设计思路：通过具体案例展示算法的应用，进行实验和分析，引导学生了解内