人工智能通识基础与应用课件

人工智能通识基础与应用第2章机器学习目录2.6进化计算2.7群体智能2.8知识发现2.6进化计算2.6进化计算2.6.1进化算法进化算法也被称作“演化算法”(EvolutionaryAlgorithms，EAs)，它属于一个“算法簇”。虽然它存在诸多变化，比如有着不同的遗传基因表达方式、不同的交叉和变异算子、会引用特殊算子，还有不同的再生和选择方法等，但这些不同形式的进化算法，其灵感统统都源自大自然中的生物进化。相较于传统的依靠微积分的方法以及穷举法等优化算法，进化算法已然是一种发展较为成熟的全局优化方法，它具备高鲁棒性以及广泛的适用性，同时还拥有自组织、自适应、自学习这些特性，能够突破问题性质的限制，对那些传统优化算法难以解决的复杂问题进行有效的处理。该算法的一般形式可以描述为(μ/ρ，λ)(μ/ρ＋λ)

进化算法的重要部分不是突变的范围不固定，而是继承。进化算法经常被用到多目标问题的优化求解中。2.6进化计算2.6.2遗传算法遗传算法(GeneticAlgorithms，CAs)是一类借鉴生物界的进化规律(“优胜劣汰”遗传机制)演化而来的随机化搜索方法。特点可以直接对结构、对象展开操作，不会受到求导以及函数连续性方面的限制；运用概率化的寻优方法，能够自动获取并引导优化的搜索空间，还能自适应地调整搜索方向，无须依靠确定的规则。2.6.2遗传算法运用基本遗传算法进行问题求解的过程如下：1.编码2.初始群体的生成。3.适应性值评估检测。4.选择5.杂交6.变异基本遗传算法可定义为一个八元组：SGA＝(C，E，P0，M，Φ，Γ，Ψ，Τ)遗传算法的优越性主要表现为以下两点：在搜索的过程中，它不易陷入局部最优的状况，即便所定义的适应函数呈现出不连续、非规则或者存在噪声等情况，其依旧能够以较高的概率寻找到整体最优解。鉴于遗传算法本身所固有的并行性特点，它十分适合在大规模并行计算机上应用。与传统的优化算法相比，遗传算法主要有以下几个不同之处。遗传算法不是直接作用在参变量集上的，而是利用参变量集的某种编码。遗传算法不是从单个点，而是从一个点的群体开始搜索的。遗传算法利用适应值信息，无须导数或其他辅助信息。遗传算法利用概率转移规则，而非确定性规则。2.6进化计算2.6.3进化策略进化策略(EvolutionaryStrategies，ESs)模仿自然进化原理作为一种求解参数优化问题的方法。进化策略强调在个体级上的行为变化。最简单的实现方法如下。(1)定义的问题是寻找n维的实数向量x，它使函数F(x):

→R。(2)双亲向量的初始群体从每维可行范围内随机选择。(3)子孙向量的创建是从每个双亲向量加上零均方差高斯随机变量。(4)根据最小误差选择向量为下一代新的双亲。(5)当向量的标准偏差保持不变或没有可用的计算方法时，处理结束。2.6进化计算2.6.4进化规划进化规划(EvolutionaryProgramming，EP)的过程可理解为从所有可能的计算机程序形成的空间里搜索那些具备高适应值的计算机程序个体，在进化规划当中，会有成百甚至上千个计算机程序参与到遗传进化之中。(1)产生初始群体。(2)迭代完成下述子步骤，直至满足选种标准。执行群体中的每个程序，根据它解决问题的能力，给它指定一个适应值。借助变异等操作来生成新的计算机程序群体。(3)在后代中适应值最高的计算机程序个体被指定为进化程序设计的结果。2.7群体智能Thoughtforcustomerservice"isthesacredmissionofhidesign。2.7群体智能2.7.1蚁群算法1蚁群算法模型蚁群算法起源蚁群算法(AntColonyAlgorithm)是由意大利学者多里科(M。Dorigo)等人在1991年的首届欧洲人工生命会议上提出的，它主要是运用群体智能解决组合优化方面的问题。蚁群算法原理蚂蚁在找寻食物的过程中，会在自己走过的路径上释放一种叫信息素（Pheromone）的物质，而信息素具有容易挥发的特性，随着时间不断流逝，遗留在路径上的信息素含量会变得越来越少。倘若蚂蚁从巢穴出发时，路径上已经存在信息素了，那么蚂蚁就会朝着信息素浓度比较高的路径前行，如此一来，它所经过的路径上的信息素浓度便会进一步升高，进而形成一种正向的催化作用。经过一定时长的搜索之后，蚂蚁最终能够找到一条从巢穴通往食物源的最短路径。2.7群体智能2.7.1蚁群算法食物BDCA1122巢穴蚂蚁觅食示意图蚁群算法的简单流程如下:(1)初始化。(2)为每只蚂蚁选择下一个节点。(3)更新信息素矩阵。(4)检查终止条件。(5)输出最优值。2.7群体智能基于群体智能的混合聚类算法主要思想：把待测对象随机地分布于一个二维网格的环境之中。像蚂蚁这类简单个体，会去测量当前对象在局部环境下的群体相似度，然后借助概率转换函数算出拾起或者放下对象的概率，再按照这个概率来采取相应的行动。经过群体之间大量的相互作用后，便能够得出若干个聚类中心。最终，运用递归算法来收集相应的聚类结果。群体相似度一个待聚类模式(对象)与其所在一定的局部环境中所有其他模式的综合相似度。概率转换函数概率转换函数是将群体相似度转换为简单个体移动待聚类模式(对象)概率的函数，它是以群体相似度为自变量的函数，函数的值域是[0，1]2.7群体智能基于群体智能的混合聚类算法CSIM主要包括两个阶段：第一阶段要完成的是基于群体智能的聚类过程；第二阶段会以第一阶段所获取的聚类中心均值模板以及聚类中心的个数作为参数，进而实现K均值聚类过程。需要注意的是，在收集第一阶段聚类结果的时候，那些由单个模式所形成的聚类中心并不会被列为第二阶段的初始聚类中心模板。2.7群体智能2.7.2粒子群优化算法粒子群优化(ParticleSwarmOptimization，PSO)算法属于一种基于群体智能的全局随机搜索算法，它因模拟鸟群在觅食过程中所展现出的迁徙以及群聚行为而被提出。粒子群优化算法和其他进化算法存在相同之处，它们同样都是基于“种群”和“进化”的概念，借助个体之间的协作与竞争，去实现对复杂空间中最优解的搜索。不过，粒子群优化算法也有其独特的地方，它是把群体中的个体视作在D维搜索空间里没有质量和体积的粒子，在这个空间中，每个粒子会以特定的速度在解空间进行运动，并且朝着自身历史最佳位置Pbest以及邻域历史最佳位置Nest聚集，进而达成对候选解的进化。2.7群体智能2.7.2粒子群优化算法基本粒子群优化算法的流程初始化个体极值与全局最优解更新速度和位置2.7群体智能2.7.2粒子群优化算法在全局最优模式中，每个个体被吸引到由种群任何个体发现的最优解。全局最优模式有较快的收敛速度，但容易陷入局部极值。而在局部最优模式中，粒子总是依据自身的信息和邻域内的最优值相关信息来对自身的运动轨迹进行调整，并非依据群体粒子的最优值信息。粒子群优化算法全局最优局部最优2.7群体智能2.7.2粒子群优化算法由两个粒子空间位置决定“邻居”，它们的远近用粒子间的距离来度量。编号方法，即粒子群中的粒子在搜索之前就被编以不同的号码，形成环状拓扑社会结构。局部模式第一种方式，在每次迭代之后都需要计算每个粒子与其他粒子间的距离来确定邻域中包括哪些粒子，这会导致算法的复杂程度增加，降低算法的运行效率。第二种方式由于事先对粒子进行了编号，因而在迭代中粒子的邻域不会改变，这导致在搜索过程中，当前粒子与指定的邻域粒子迅速聚集，而整个粒子群就被分成几个小块，表面上看似增大了搜索范围，实际上大大降低了收敛速度。虽然局部最优模式收敛速度较慢，但具有较强的全局搜索能力。2.7群体智能2.7.2粒子群优化算法

粒子群优化算法有着诸多优势，其算法较为简洁，易于操作实现，并且不需要对大量参数进行调整，同时也无须依赖梯度信息。它是解决非线性连续优化问题、组合优化问题以及混合整数非线性优化问题的有效优化工具。2.8知识发现Thoughtforcustomerservice"isthesacredmissionofhidesign。2.8知识发现

知识发现是从数据集中识别出有效的、新颖的、潜在有用的，以及可理解模式的非平凡过程。这里数据集是一组事实F（如关系数据库中的记录）。模式是一个用语言L来表示的表达式E，它可用来描述数据集F的某个子集FE，E作为一个模式，要求本身比数据子集FE的枚举要简单。有效性是指发现的模式对于新的数据仍保持有一定的可信度。新颖