《智能算法初步》PPT课件

数学建模中的智能算法,2020/5/16,数学建模十大算法,蒙特卡罗算法数据拟合、参数估计、插值等数据处理算法线性规划等规划类问题图论算法动态规划、回溯搜索、分支定界等计算机算法模拟退火、神经网络、遗传算法等最优化理论算法网格算法和穷举法一些连续离散化方法数值分析算法图像处理算法,2020/5/16,3,人工智能优化算法,遗传算法模拟退火人工神经网络算法粒子群算法蚁群算法,2020/5/16,认识“人工智能”,人工智能(ArtificialIntelligence,AI)概念是JohnMcCarthy（约翰.麦克斯）于1956年在Dartmouth学会上提出的。美国计算机科学家，因在人工智能领域的重大贡献，被称为“人工智能之父”，并因此获得图灵奖他于1948年获得加州理工学院数学学士学位，1951年获得普林斯顿大学数学博士学位,JohnMcCarthy,2020/5/16,认识“人工智能”（续）,人工智能让机器像人一样思考人工智能是计算机科学的前沿学科，是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学.计算机编程语言和其它计算机软件都因为有了人工智能的进展而得以存在。人工智能涉及学科：哲学和认知科学，数学，神经生理学，心理学，计算机科学，信息论，控制论，不定性论，仿生学等,2020/5/16,认识“人工智能”（续）,人工智能的目的：通过研究人脑的组成机理和思维方式，企图了解智能的实质，并生产出一种能以人类智能相似的方式做出反应的智能机器让机器具有智慧，像人一样思考.计算机的出现人类开始真正有了一个可以模拟人类思维的工具人工智能的领域研究：包括机器人、语言识别、图像识别、自然语言处理和专家系统等.,2020/5/16,意识和人工智能的区别,人工智能就其本质而言，是对人的思维的信息过程的模拟.对于人的思维模拟可以从两条道路进行：结构模拟：仿照人脑的结构机制，制造出“类人脑”的机器；功能模拟：暂时撇开人脑的内部结构，而从其功能过程进行模拟。现代电子计算机的产生便是对人脑思维功能的模拟，是对人脑思维的信息过程的模拟.人工智能不是人的智能，更不会超过人的智能.,2020/5/16,意识和人工智能的区别（续）,“机器思维”同“人类思维”的本质区别：1.人工智能纯系无意识的机械的物理的过程，人类智能主要是生理和心理的过程.2.人工智能没有社会性.3.人工智能没有人类的意识所特有的能动的创造能力.4.两者总是人脑的思维在前，电脑的功能在后.,2020/5/16,经典的人工智能成果,人机对弈*1996年2月10-17日,GarryKasparov以4:2战胜“深蓝”(DeepBlue)*1997年5月3-11日,GarryKasparov以3.5:2.5输于改进后的“深蓝”*2003年2月GarryKasparov3:3战平“小深”(DeepJunior)*2003年11月GarryKasparov2:2战平“X3D德国人”(X3D-Fritz)模式识别指纹识别、人脸识别、语音识别、文字识别、图像识别、车牌识别等,2020/5/16,经典的人工智能成果(续),电影中文名：人工智能片名：AI年代：2001国家：美国相关著作视读人工智能、人工智能的未来、人工智能哲学、人工智能：一种现代的方法,2020/5/16,遗传算法(GeneticAlgorithm，GA)人工神经网络算法(ArtificicalNeuralNetwork,ANN)模拟退火(SimulatedAnnealing,SA)粒子群优化算法(ParticalSwamOptimizationAlgorithm,PSOA)蚁群优化算法(AntColonyOptimizationAlgorithm,ACOA),人工智能优化算法,2020/5/16,97年A题用模拟退火算法00年B题用神经网络分类算法01年B题这种难题也可以使用神经网络美国89年A题也和BP算法有关系美国03年B题伽马刀问题也是目前研究的课题，目前算法最佳的是遗传算法。,遗传算法(GA)、模拟退火法(SA)、神经网络(NN)、,近几年的赛题越来越复杂，很多问题没有什么很好的模型可以借鉴，于是这三类算法很多时候可以派上用场。,最优化理论的三大非经典算法:,2020/5/16,遗传算法(GeneticAlgorithm，GA)人工神经网络算法(ArtificicalNeuralNetwork,ANN)模拟退火(SimulatedAnnealing,SA)粒子群优化算法(ParticalSwamOptimizationAlgorithm,PSOA)蚁群优化算法(AntColonyOptimizationAlgorithm,ACOA),人工智能优化算法,2020/5/16,遗传算法(GeneticAlgorithm),进化算法(EvolutionaryAlgorithm),2020/5/16,遗传算法是一类模拟达尔文生物进化论的自然选择和遗传算法机理的生物进化过程的计算模型，借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索最优化方法。遗传算法最初由美国密歇根大学J.Holland（霍兰德）教授于1975年首先提出来的，并出版了颇有影响的专著AdaptationinNaturalandArtificialSystems,遗传算法这个名称才逐渐为人所知，通常称为“简单遗传算法”。,遗传算法(GeneticAlgorithm,GA),2020/5/16,直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。,遗传算法的主要特点,2020/5/16,遗传算法的定义,遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。,2020/5/16,遗传算法的定义（续）,由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。,2020/5/16,遗传算法流程图,由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性。,2020/5/16,遗传算法的一般算法,遗传算法是由进化论和遗传学机理而产生的搜索算法。1.创建一个随机的初始状态：初始群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代。2.评估适应度：对每一个解(染色体)指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近求解问题的答案)。不要把这些“解”与问题的“答案”混为一谈，可以把它理解成为要得到答案，系统可能需要利用的那些特性。,2020/5/16,遗传算法的一般算法(续),3.繁殖(包括子代突变)带有较高适应度值的那些染色体更可能产生后代(后代产生后也将发生突变)。后代是父母的产物，他们由来自父母的基因结合而成，这个过程被称为“杂交”。4.下一代如果新的一代包含一个解，能产生一个充分接近或等于期望答案的输出，那么问题就已经解决了。如果情况并非如此，新的一代将重复他们父母所进行的繁衍过程，一代一代演化下去，直到达到期望的解为止。,2020/5/16,遗传算法的一般算法(续),5.并行计算*非常容易将遗传算法用到并行计算和群集环境中。*一种方法是直接把每个节点当成一个并行的种群看待。然后有机体根据不同的繁殖方法从一个节点迁移到另一个节点。*另一种方法是“农场主/劳工”体系结构，指定一个节点为“农场主”节点，负责选择有机体和分派适应度的值，另外的节点作为“劳工”节点，负责重新组合、变异和适应度函数的评估。,2020/5/16,遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。,遗传算法的搜索机制,2020/5/16,遗传算法(GA),2020/5/16,Wehaveadream!,IamatthetopHeightis.,Iamnotatthetop.Myhighisbetter!,Iwillcontinue,遗传算法(GA),GA-第0代,2020/5/16,Deadone,Newone,遗传算法(GA),GA-第1代,2020/5/16,Notatthetop,ComeUp!,遗传算法(GA),GA-第?代,2020/5/16,IamtheBEST!,遗传算法(GA),GA-第N代,2020/5/16,生物进化与遗传算法对应关系,2020/5/16,遗传算法的基本操作,选择(selection):根据各个个体的适应值，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。交叉(crossover):将群体P(t)内的各个个体随机搭配成对，对每一个个体，以某个概率Pc(称为交叉概率，crossvoerrate)交换它们之间的部分染色体。变异(mutation):对群体P(t)中的每一个个体，以某一概率Pm(称为变异概率，mutationrate)改变某一个或一些基因座上基因值为其它的等位基因。,2020/5/16,如何设计遗传算法,如何进行编码？如何产生初始种群？如何定义适应函数？如何进行遗传操作(复制、交叉、变异)？如何产生下一代种群？如何定义停止准则？,2020/5/16,编码(Coding),2020/5/16,编码,设某一参数的取值范围为（L，U），使用长度为k的二进制编码表示该数，则共有种不同的编码。,2020/5/16,解码,解码的目的是为了将不直观的二进制数据串还原成十进制。,设某一个体的二进制编码为,则对应的解码公式为：,2020/5/16,适应函数(FitnessFunction),GA在搜索中不依靠外部信息，仅以适应函数为依据，利用群体中每个染色体(个体)的适应值来进行搜索。以染色体适应值的大小来确定该染色体被遗传到下一代群体中的概率。染色体适应值越大，该染色体被遗传到下一代的概率也越大；反之，染色体的适应值越小，该染色体被遗传到下一代的概率也越小。因此适应函数的选取至关重要，直接影响到GA的收敛速度以及能否找到最优解。群体中的每个染色体都需要计算适应值适应函数一般由目标函数变换而成,2020/5/16,适应函数(FitnessFunction),适应函数常见形式：直接将目标函数转化为适应函数若目标函数为最大化问题：Fitness(f(x)=f(x)若目标函数为最小化问题：Fitness(f(x)=-f(x),2020/5/16,适应函数(FitnessFunction),界限构造法,2020/5/16,选择(Selection),选择(复制)操作把当前种群的染色体按与适应值成正比例的概率复制到新的种群中主要思想:适应值较高的染色体体有较大的选择(复制)机会,设种群的规模为Nxi是种群中第i个染色体,染色体xi被选概率,2020/5/16,选择(Selection),实现1：”轮盘赌”选择(Roulettewheelselection)产生一个在0与总和之间的的随机数m从种群中编号为1的染色体开始，将其适应值与后续染色体的适应值相加，直到累加和等于或大于m,2020/5/16,选择(Selection),染色体的适应值和所占的比例,轮盘赌选择,2020/5/16,选择(Selection),染色体被选的概率,被选的染色体,2020/5/16,选择(Selection),轮盘上的片分配给群体的染色体，使得每一个片的大小与对于染色体的适应值成比例从群体中选择一个染色体可视为旋转一个轮盘，当轮盘停止时，指针所指的片对于的染色体就时要选的染色体。模拟“轮盘赌”算法：r=rand(0,1)，s=0，i=0；如果sr，则转(4)；s=s+p(xi)，i=i+1,转(2)xi即为被选中的染色体，输出I结束,2020/5/16,选择(Selection),其他选择法：随机遍历抽样(Stochasticuniversalsampling)局部选择(Localselection)截断选择(Truncationselection)竞标赛选择(Tournamentselection)特点：选择操作得到的新的群体称为交配池，交配池是当前代和下一代之间的中间群体，其规模为初始群体规模。选择操作的作用效果是提高了群体的平均适应值(低适应值个体趋于淘汰，高适应值个体趋于选择)，但这也损失了群体的多样性。选择操作没有产生新的个体，群体中最好个体的适应值不会改变。,2020/5/16,交叉(crossover,Recombination),遗传交叉(杂交、交配、有性重组)操作发生在两个染色体之间，由两个被称之为双亲的父代染色体，经杂交以后，产生两个具有双亲的部分基因的新的染色体，从而检测搜索空间中新的点。选择(复制)操作每次作用在一个染色体上，而交叉操作每次作用在从交配池中随机选取的两个个体上(交叉概率Pc)。交叉产生两个子染色体，他们与其父代不同，且彼此不同,每个子染色体都带有双亲染色体的遗传基因。,2020/5/16,单点交叉(1-pointcrossover),在双亲的父代染色体中随机产生一个交叉点位置在交叉点位置分离双亲染色体互换交叉点位置右边的基因码产生两个子代染色体交叉概率Pc一般范围为(60%,90%)，平均约80%,交叉点位置,2020/5/16,交叉(crossover,Recombination),单点交叉操作可以产生与父代染色体完全不同的子代染色体；它不会改变父代染色体中相同的基因。但当双亲染色体相同时，交叉操作是不起作用的。,假如交叉概率Pc50%,则交配池中50%的染色体(一半染色体)将进行交叉操作，余下的50%的染色体进行选择(复制)操作。,GA利用选择和交叉操作可以产生具有更高平均适应值和更好染色体的群体,2020/5/16,变异(Mutation),以变异概率Pm改变染色体的某一个基因,当以二进制编码时，变异的基因由0变成1，或者由1变成0。变异概率Pm一般介于1/种群规模与1/染色体长度之间，平均约1-2%,变异基因,变异基因,2020/5/16,变异(Mutation),比起选择和交叉操作，变异操作是GA中的次要操作，但它在恢复群体中失去的多样性方面具有潜在的作用。在GA执行的开始阶段，染色体中一个特定位上的值1可能与好的性能紧密联系，即搜索空间中某些初始染色体在那个位上的值1可能一致产生高的适应值。因为越高的适应值与染色体中那个位上的值1相联系，选择操作就越会使群体的遗传多样性损失。等到达一定程度时，值0会从整个群体中那个位上消失，然而全局最优解可能在染色体中那个位上为0。如果搜索范围缩小到实际包含全局最优解的那部分搜索空间，在那个位上的值0就可能正好是到达全局最优解所需要的。,2020/5/16,停止准则(TerminationCriteria),种群中个体的最大适应值超过预设定值种群中个体的平均适应值超过预设定值种群中个体的进化代数超过预设定值,2020/5/16,基本步骤(StepbyStep),(1)随机产生初始种群;(2)计算种群体中每个个体的适应度值,判断是否满足停止条件，若不满足，则转第(3)步,否则转第(6)步;(3)按由个体适应值所决定的某个规则选择将进入下一代的个体;(4)按交叉概率Pc进行交叉操作,生产新的个体;(5)按变异概率Pm进行变异操作,生产新的个体;(6)输出种群中适应度值最优的染色体作为问题的满意解或最优解。,2020/5/16,流程图(FlowChart),2020/5/16,基本遗传算法,基本遗传算法（SimpleGeneticAlgorithms,简称SGA）是一种统一的最基本的遗传算法，它只使用选择、交叉、变异这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。,2020/5/16,SGA伪码描述,ProcedureGeneticAlgorithmbegint=0;%遗传代数初始化P(t);%初始化种群或染色体计算P(t)的适应值;while(不满足停止准则)dobegint=t+1;从P(t-1)中选择P(t);%selection重组P(t);%crossoverandmutation计算P(t)的适应值;endend,2020/5/16,遗传算法的应用,函数优化函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能测试评价的常用算例。对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。,遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面列举一些遗传算法的主要应用领域。,2020/5/16,遗传算法的应用,组合优化遗传算法是寻求组合优化问题满意解的最佳工具之一，实践证明，遗传算法对于组合优化问题中的NP完全问题非常有效。例如，遗传算法已经在求解旅行商问题(TravelingSalesmanProblem,TSP)、背包问题(KnapsackProblem)、装箱问题(BinPackingProblem)等方面得到成功的应用。生产调度问题生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为解决复杂调度问题的有效工具。,2020/5/16,遗传算法的应用,自动控制遗传算法已经在自动控制领域中得到了很好的应用，例如基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等。机器人智能控制机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人智能控制自然成为遗传算法的一个重要应用领域。,2020/5/16,遗传算法的应用,图象处理和模式识别图像处理和模式识别是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求，遗传算法在这些图像处理中的优化计算方面得到了很好的应用。人工生命人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大重要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础。,2020/5/16,遗传算法的应用,遗传程序设计Koza发展了遗传程序设计的概念，他使用了以LISP语言所表示的编码方法，基于对一种树形结构所进行的遗传操作来自动生成计算机程序。机器学习基于遗传算法的机器学习，在很多领域中都得到了应用。例如基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可以用于人工神经网络的网络结构优化设计。分类器系统在多机器人路径规划系统中得到了成功的应用。,2020/5/16,SGA实例1：函数最值,SGA参数:编码方式:二进制码e.g.000000;0110113;1111131种群规模:4随机初始群体“转盘赌”选择一点杂交,二进制变异,求函数f(x)=x2的最大值，x为自然数且0x31.,手工方式完成演示SGA过程,2020/5/16,SGA实例1maxx2:选择操作,2020/5/16,SGA实例1maxx2:交叉操作,2020/5/16,SGA实例1maxx2:变异操作,2020/5/16,SGA实例2:连续函数最值,求下列函数的最大值：,2020/5/16,SGA实例2:编码,高精度,编码,x,y0,1L必须可逆(一个表现型对应一个基因型),解码算子：:0,1Lx,y,染色体长度L决定可行解的最大精度,长染色体(慢进化),2020/5/16,SGA实例2:编码,设定求解精确到6位小数，因区间长度位2-(-1)=3,则需将区间分为3X106等份。因20971522211-7-8-9-4-6-2-3)。此向量是1到n的一个排列，即从1到n的每个整数在这个向量中正好出现一次,不能有重复。这样，基本遗传算法的基因操作生成的个体不能满足这一约束条件，需寻求其他遗传操作。,2020/5/16,TSP交叉,需其他方式的交叉(重组)操作,如部分匹配交叉(PartiallyMatchedCrossover,PMX)、顺序交叉(OrderedCrossover,OX)、循环交叉(CycleCrossover,CX)、边重组(EdgeRecombination)。,一般的交叉操作会产生不合适的解，如,2020/5/16,TSP交叉1:部分匹配交叉(PMX),双亲P1,P2随机选取两个交叉点，得到一个匹配段,根据交叉点中间段给出映射关系。,P1,P2,映射关系：48、52、75,c1,c2,交换两个交叉点之间的编码,(X表示未定码),2020/5/16,TSP交叉1:部分匹配交叉(PMX),子个体C1，C2分别从其父个体中继承未映射城市码,P1,P2,c1,c2,映射关系：48、52、75,c1,c2,再根据映射关系，对以上未定码，使用最初双亲码，得到子个体的对应码。映射关系存在传递关系，则选择未定码交换。,2020/5/16,TSP交叉2:顺序交叉(OX),双亲P1,P2随机选取两个交叉点,P1,P2,c1,c2,两个交叉点间的中间段保存不变,子个体C1的未定码的确定需要父个体P2的未选定城市码，子个体C2的未定码的确定需要父个体P1的未选定城市码。,2020/5/16,TSP交叉2:顺序交叉(OX),记取父个体P2从第二个交叉点开始城市码的排列顺序，当到达表尾时，返回表头继续记录，直到第二个交叉点。,P2,c1,c1,c2,得到父个体P2的排列顺序1-4-9-3-7-8-2-6-5,并将C1已有城市码4,5,6,7从中去掉，得到排列顺序1-9-3-8-2，再将此顺序复制到C1，复制点也是从第二个交叉点开始，得到C1。,同理的C2，,2020/5/16,TSP交叉3:循环交叉(CX),CX操作中子个体中的城市码顺序根据任一父个体产生确定循环编码,复制循环编码到子个体,2020/5/16,TSP变异,InsertMutation随机选取个体中两个编码，然后把第二个编码放在第一个编码之后，其他编码顺次调节位置。,Swapmutation随机选取个体中两个编码，然后交换它们的位置。,2020/5/16,TSP变异,Inversionmutation随机选取个体中一段编码，然后颠倒这段编码的顺序。,Scramblemutation随机选取个体上一段编码,然后打乱这段编码的顺序。,选取的编码不一定是邻接编码,2020/5/16,TSP的GA过程,从N个随机起点开始产生N条路径，N为种群的规模;利用最优方法搜索每条路径的局部最优解;选择交叉对使在平均性能之上的个体得到更多的子代;交叉和变异;搜索每条路径得到其极小解，如果不收敛，则回到第3步；否则，停止。,2020/5/16,GA的MATLAB实现,软件平台(SoftwarePlatforms):MATLAB7.xGeneticAlgorithmandDirectSearchToolbox2.0.1MATLAB6.x(or7.x)+GAOTGAOT:GeneticAlgorithmOptimizationToolbox美国NorthCarolinaStateUniversity开发MATLAB6.x(or7.x)+GEATbxGEATbx:GeneticandEvolutionaryAlgorithmToolbox英国TheUniversityofSheffield开发MATLAB遗传算法工具箱及应用(雷英杰等,西安电子科技大学出版社,2005)基于此工具箱,2020/5/16,GAOT工具箱,核心函数：pop=initializega(num,bounds,eevalFN,eevalOps,options)-初始种群的生成函数【输出参数】pop-生成的初始种群【输入参数】num-种群中的个体数目bounds-代表变量的上下界的矩阵eevalFN-适应度函数eevalOps-传递给适应度函数的参数options-选择编码形式(浮点编码或是二进制编码)与精度，如typeprec，type-为1时选择浮点编码，否