智能算法初步.ppt

《智能算法初步.ppt》由会员分享，可在线阅读，更多相关《智能算法初步.ppt（104页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学建模中的智能算法2数学建模十大算法数学建模十大算法l蒙特卡罗算法蒙特卡罗算法l数据拟合、参数估计、插值等数据处理算法数据拟合、参数估计、插值等数据处理算法l线性规划等规划类问题线性规划等规划类问题l图论算法图论算法l动态规划、回溯搜索、分支定界等计算机算法动态规划、回溯搜索、分支定界等计算机算法l模拟退火、神经网络、遗传算法等最优化理论算法模拟退火、神经网络、遗传算法等最优化理论算法l网格算法和穷举法网格算法和穷举法l一些连续离散化方法一些连续离散化方法l数值分析算法数值分析算法l图像处理算法图像处理算法12/31/202233人工智能优化算法l遗传算法遗传算法l模拟退火模拟退火l人工神经

2、网络算法人工神经网络算法l粒子群算法粒子群算法l蚁群算法蚁群算法12/31/20224认识认识“人工智能人工智能”l人人工工智智能能(Artificial Intelligence,AI)概概念念是是John McCarthy（约约翰翰.麦麦克克斯斯）于于1956年在年在Dartmouth学会上提出的。学会上提出的。l美美国国计计算算机机科科学学家家，因因在在人人工工智智能能领领域域的的重重大大贡贡献献，被被称称为为“人人工工智智能能之之父父”，并因此获得图灵奖，并因此获得图灵奖l他他于于1948年年获获得得加加州州理理工工学学院院数数学学学学士士学学位位，1951年年获获得得普普林林斯斯顿顿

3、大大学学数数学学博博士学位士学位John McCarthy12/31/20225认识认识“人工智能人工智能”（续）（续）l人工智能人工智能让机器像人一样思考让机器像人一样思考l人工智能是计算机科学的前沿学科，是研究、开发用于模拟、延人工智能是计算机科学的前沿学科，是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学术科学.计算机编程语言和其它计算机软件都因为有了人工智能的计算机编程语言和其它计算机软件都因为有了人工智能的进展而得以存在。进展而得以存在。l人工智能人工智能涉及学科：涉及学科：哲学和认知科学，

4、数学，神经生理学，心理哲学和认知科学，数学，神经生理学，心理学，计算机科学，信息论，控制论，不定性论，仿生学等学，计算机科学，信息论，控制论，不定性论，仿生学等12/31/20226认识认识“人工智能人工智能”（续）（续）l人人工工智智能能的的目目的的：通通过过研研究究人人脑脑的的组组成成机机理理和和思思维维方方式式，企企图图了了解解智智能能的的实实质质，并并生生产产出出一一种种能能以以人人类类智智能能相相似似的的方方式式做做出出反反应应的智能机器的智能机器让机器具有智慧，像人一样思考让机器具有智慧，像人一样思考.l计计算算机机的的出出现现人人类类开开始始真真正正有有了了一一个个可可以以模模拟

5、拟人人类类思思维维的的工工具具l人人工工智智能能的的领领域域研研究究：包包括括机机器器人人、语语言言识识别别、图图像像识识别别、自自然然语言处理和专家系统等语言处理和专家系统等.12/31/20227意识和人工智能的区别意识和人工智能的区别l人工智能就其本质而言，是对人的思维的信息过程的人工智能就其本质而言，是对人的思维的信息过程的模拟模拟.l对于人的思维模拟可以从两条道路进行：对于人的思维模拟可以从两条道路进行：结构模拟：仿照人脑的结构机制，制造出结构模拟：仿照人脑的结构机制，制造出“类人脑类人脑”的机器；的机器；功能模拟：暂时撇开人脑的内部结构，而从其功能过程进行模拟。功能模拟：暂时撇开人

6、脑的内部结构，而从其功能过程进行模拟。现现代代电电子子计计算算机机的的产产生生便便是是对对人人脑脑思思维维功功能能的的模模拟拟，是是对对人人脑脑思维的信息过程的模拟思维的信息过程的模拟.l人工智能不是人的智能，更不会超过人的智能人工智能不是人的智能，更不会超过人的智能.12/31/20228意识和人工智能的区别（续）意识和人工智能的区别（续）“机器思维机器思维”同同“人类思维人类思维”的本质区别：的本质区别：1.人人工工智智能能纯纯系系无无意意识识的的机机械械的的物物理理的的过过程程，人人类类智智能能主主要要是是生生理和心理的过程理和心理的过程.2.人工智能没有社会性人工智能没有社会性.3.人

7、工智能没有人类的意识所特有的能动的创造能力人工智能没有人类的意识所特有的能动的创造能力.4.两者总是人脑的思维在前，电脑的功能在后两者总是人脑的思维在前，电脑的功能在后.12/31/20229经典的人工智能成果经典的人工智能成果l l人机对弈人机对弈人机对弈人机对弈 *1996年年2月月10-17日日,Garry Kasparov以以4:2战胜战胜“深蓝深蓝”(Deep Blue)*1997年年5月月3-11日日,Garry Kasparov以以3.5:2.5输于改进后的输于改进后的“深蓝深蓝”*2003年年2月月Garry Kasparov 3:3战平战平“小深小深”(Deep Junior

8、)*2003年年11月月Garry Kasparov 2:2战平战平“X3D德国人德国人”(X3D-Fritz)l l模式识别模式识别模式识别模式识别 指纹识别、人脸识别、语音识别、文字识别、图像识别、车牌识别等指纹识别、人脸识别、语音识别、文字识别、图像识别、车牌识别等12/31/202210经典的人工智能成果经典的人工智能成果(续续)l l电电电电 影影影影中文名：人工智能中文名：人工智能 片片 名：名：AI 年年 代：代：2001 国国 家：美国家：美国oo相关著作相关著作相关著作相关著作视读人工智能视读人工智能、人工智能的未来人工智能的未来、人工智能哲学人工智能哲学、人人工智能：一种现

9、代的方法工智能：一种现代的方法12/31/202211l遗传算法遗传算法(Genetic Algorithm，GA)l人工神经网络算法人工神经网络算法(Artificical Neural Network,ANN)l模拟退火模拟退火(Simulated Annealing,SA)l粒粒 子子 群群 优优 化化 算算 法法(Partical Swam Optimization Algorithm,PSOA)l蚁群优化算法蚁群优化算法(Ant Colony Optimization Algorithm,ACOA)人工智能优化算法人工智能优化算法12/31/20221297年年A 题用模拟退火算法题

10、用模拟退火算法00年年B 题用神经网络分类算法题用神经网络分类算法01年年B 题这种难题也可以使用神经网络题这种难题也可以使用神经网络美国美国89年年A 题也和题也和BP 算法算法有关系美国美国03年年B 题题伽马刀问题也是目前研究的课题，目前算法最佳的是遗传算法算法最佳的是遗传算法。遗传算法(GA)、模拟退火法(SA)、神经网络(NN)、近几年的赛题越来越复杂，很多问题没有什么很好的模型可以借鉴，于是这三类算法很多时候可以派上用场。最优化理论的三大非经典算法最优化理论的三大非经典算法:12/31/202213l遗传算法遗传算法(Genetic Algorithm，GA)l人工神经网络算法人工

11、神经网络算法(Artificical Neural Network,ANN)l模拟退火模拟退火(Simulated Annealing,SA)l粒粒 子子 群群 优优 化化 算算 法法(Partical Swam Optimization Algorithm,PSOA)l蚁群优化算法蚁群优化算法(Ant Colony Optimization Algorithm,ACOA)人工智能优化算法人工智能优化算法12/31/202214遗传算法遗传算法(Genetic Algorithm)进化算法(EvolutionaryAlgorithm)12/31/202215l遗遗传传算算法法是是一一类类模模拟

12、拟达达尔尔文文生生物物进进化化论论的的自自然然选选择择和和遗遗传传算算法法机机理理的的生生物物进进化化过过程程的的计计算算模模型型，借借鉴鉴生生物物界界的的进进化化规规律律（适适者者生生存，优胜劣汰遗传机制）演化而来的存，优胜劣汰遗传机制）演化而来的随机化搜索最优化方法随机化搜索最优化方法。l遗遗传传算算法法最最初初由由美美国国密密歇歇根根大大学学J.Holland（霍霍兰兰德德）教教授授于于1975年年首首先先提提出出来来的的，并并出出版版了了颇颇有有影影响响的的专专著著Adaptation in Natural and Artificial Systems,遗遗传传算算法法这这个个名名称称

13、才才逐逐渐渐为为人人所所知知，通通常常称为称为“简单遗传算法简单遗传算法”。遗传算法遗传算法(Genetic Algorithm,GA)12/31/202216l直接对结构对象进行操作，不存在求导和函数连续性的限定；直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；具有内在的隐并行性和更好的全局寻优能力；采采用用概概率率化化的的寻寻优优方方法法，能能自自动动获获取取和和指指导导优优化化的的搜搜索索空空间间，自自适应地调整搜索方向，不需要确定的规则。适应地调整搜索方向，不需要确定的规则。l遗遗传传算算法法的的这这些些性性质质，已已被被人人们们广广泛泛地

14、地应应用用于于组组合合优优化化、机机器器学学习习、信信号号处处理理、自自适适应应控控制制和和人人工工生生命命等等领领域域。它它是是现现代代有有关关智智能计算中的关键技术。能计算中的关键技术。遗传算法的主要特点遗传算法的主要特点12/31/202217遗传算法的定义遗传算法的定义l遗遗传传算算法法是是从从代代表表问问题题可可能能潜潜在在的的解解集集的的一一个个种种群群（population）开开始始的的，而而一一个个种种群群则则由由经经过过基基因因（gene）编编码码的的一一定定数数目目的的个个体体(individual)组成。组成。l每个个体实际上是染色体每个个体实际上是染色体(chromos

15、ome)带有特征的实体。带有特征的实体。l染染色色体体作作为为遗遗传传物物质质的的主主要要载载体体，即即多多个个基基因因的的集集合合，其其内内部部表表现现（即即基基因因型型）是是某某种种基基因因组组合合，它它决决定定了了个个体体的的形形状状的的外外部部表表现现，如如黑黑头头发发的的特特征征是是由由染染色色体体中中控控制制这这一一特特征征的的某某种种基基因因组组合合决决定定的的。因因此此，在在一一开开始始需需要要实实现现从从表表现现型型到到基基因因型型的的映映射射即即编编码工作。码工作。12/31/202218遗传算法的定义（续）遗传算法的定义（续）l由由于于仿仿照照基基因因编编码码的的工工作作

16、很很复复杂杂，我我们们往往往往进进行行简简化化，如如二二进进制制编编码码，初初代代种种群群产产生生之之后后，按按照照适适者者生生存存和和优优胜胜劣劣汰汰的的原原理理，逐逐代（代（generation）演化产生出越来越好的近似解。）演化产生出越来越好的近似解。l在在每每一一代代，根根据据问问题题域域中中个个体体的的适适应应度度（fitness）大大小小选选择择（selection）个个体体，并并借借助助于于自自然然遗遗传传学学的的遗遗传传算算子子（genetic operators）进进行行组组合合交交叉叉（crossover）和和变变异异（mutation），产产生生出出代代表表新新的的解解集

17、集的的种种群群。这这个个过过程程将将导导致致种种群群像像自自然然进进化化一一样样的的后后生生代代种种群群比比前前代代更更加加适适应应于于环环境境，末末代代种种群群中中的的最最优优个个体体经经过过解解码（码（decoding），可以作为问题近似最优解。），可以作为问题近似最优解。12/31/202219遗传算法流程图遗传算法流程图l由由于于遗遗传传算算法法的的整整体体搜搜索索策策略略和和优优化化搜搜索索方方法法在在计计算算是是不不依依赖赖于于梯梯度度信信息息或或其其它它辅辅助助知知识识，而而只只需需要要影影响响搜搜索索方方向向的的目目标标函函数数和和相相应应的的适适应应度度函函数数，所所以以遗遗

18、传传算算法法提提供供了了一一种种求求解解复复杂杂系系统统问问题题的的通通用用框框架架，它它不不依依赖赖于于问问题题的的具具体体领领域域，对对问问题题的的种种类类有有很很强强的鲁棒性。的鲁棒性。12/31/202220遗传算法的一般算法遗传算法的一般算法l遗传算法是由进化论和遗传学机理而产生的搜索算法。遗传算法是由进化论和遗传学机理而产生的搜索算法。1.创创建建一一个个随随机机的的初初始始状状态态：初初始始群群是是从从解解中中随随机机选选择择出出来来的的，将将这这些解比喻为染色体或基因，该种群被称为第一代。些解比喻为染色体或基因，该种群被称为第一代。2.评评估估适适应应度度：对对每每一一个个解解

19、(染染色色体体)指指定定一一个个适适应应度度的的值值，根根据据问问题题求求解解的的实实际际接接近近程程度度来来指指定定(以以便便逼逼近近求求解解问问题题的的答答案案)。不不要要把把这这些些“解解”与与问问题题的的“答答案案”混混为为一一谈谈，可可以以把把它它理理解解成成为为要要得得到到答答案案，系统可能需要利用的那些特性。系统可能需要利用的那些特性。12/31/202221遗传算法的一般算法遗传算法的一般算法(续续)l3.繁殖繁殖(包括子代突变包括子代突变)带带有有较较高高适适应应度度值值的的那那些些染染色色体体更更可可能能产产生生后后代代(后后代代产产生生后后也也将将发发生生突突变变)。后后

20、代代是是父父母母的的产产物物，他他们们由由来来自自父父母母的的基基因因结结合合而而成成，这这个个过过程被称为程被称为“杂交杂交”。4.下一代下一代 如如果果新新的的一一代代包包含含一一个个解解，能能产产生生一一个个充充分分接接近近或或等等于于期期望望答答案案的的输输出出，那那么么问问题题就就已已经经解解决决了了。如如果果情情况况并并非非如如此此，新新的的一一代代将将重重复复他他们们父父母母所进行的繁衍过程，一代一代演化下去，直到达到期望的解为止。所进行的繁衍过程，一代一代演化下去，直到达到期望的解为止。12/31/202222遗传算法的一般算法遗传算法的一般算法(续续)l5.并行计算并行计算*

21、非常容易将遗传算法用到并行计算和群集环境中。非常容易将遗传算法用到并行计算和群集环境中。*一种方法是直接把每个节点当成一个并行的种群看待。然后有机体一种方法是直接把每个节点当成一个并行的种群看待。然后有机体根据不同的繁殖方法从一个节点迁移到另一个节点。根据不同的繁殖方法从一个节点迁移到另一个节点。*另一种方法是另一种方法是“农场主农场主/劳工劳工”体系结构，指定一个节点为体系结构，指定一个节点为“农场农场主主”节点，负责选择有机体和分派适应度的值，另外的节点作为节点，负责选择有机体和分派适应度的值，另外的节点作为“劳劳工工”节点，负责重新组合、变异和适应度函数的评估。节点，负责重新组合、变异和

22、适应度函数的评估。12/31/202223遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子遗传算子(选择、交叉和变选择、交叉和变异异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法的搜索机制遗传算法的搜索机制12/31/202224局部局部局部局部全局全局全局全局遗传算法遗传算法(GA)12/31/202225We have a dream!We have a dream!I am at the I am at the toptopHe

23、ight is.Height is.I am not at the top.I am not at the top.My high is better!My high is better!I will continueI will continue遗传算法遗传算法(GA)GA-第0代12/31/202226Dead oneDead oneNew oneNew one遗传算法遗传算法(GA)GA-第1代12/31/202227Not at the top,Not at the top,Come Up!Come Up!遗传算法遗传算法(GA)GA-第?代12/31/202228I am the I

24、 am the BESTBEST!遗传算法遗传算法(GA)GA-第N代12/31/202229生物进化与遗传算法对应关系生物进化与遗传算法对应关系生物进化生物进化遗传算法遗传算法适者生存适应函数值最大的解被保留的概率最大个体问题的一个解染色体解的编码基因编码的元素群体被选定的一组解种群根据适应函数选择的一组解交叉以一定的方式由双亲产生后代的过程变异编码的某些分量发生变化的过程环境适应函数12/31/202230遗传算法的基本操作遗传算法的基本操作选择选择(selection):根据各个个体的适应值，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。

25、交叉交叉(crossover):将群体P(t)内的各个个体随机搭配成对，对每一个个体，以某个概率Pc(称为交叉概率，crossvoerrate)交换它们之间的部分染色体。变异变异(mutation):对群体P(t)中的每一个个体，以某一概率Pm(称为变异概率，mutationrate)改变某一个或一些基因座上基因值为其它的等位基因。12/31/202231如何设计遗传算法如何设计遗传算法如何进行编码？如何进行编码？如何产生初始种群？如何产生初始种群？如何定义适应函数？如何定义适应函数？如何进行遗传操作如何进行遗传操作(复制、交叉、变异复制、交叉、变异)？如何产生下一代种群？如何产生下一代种群？

26、如何定义停止准则如何定义停止准则？12/31/202232编码编码(Coding)表现型空间编码(Coding)解码(Decoding)基因型空间=0,1L011101001010001001100100101001000112/31/202233编码编码设某一参数的取值范围为（L，U），使用长度为k 的二进制编码表示该数，则共有 种不同的编码。12/31/202234解码解码解码的目的是为了将不直观的二进制数据串还原成十进制。设某一个体的二进制编码为则对应的解码公式为：12/31/202235适应函数适应函数(Fitness Function)GA在搜索中不依靠外部信息，仅以适应函数为依据，

27、利用群体中每个染色体(个体)的适应值来进行搜索。以染色体适应值的大小来确定该染色体被遗传到下一代群体中的概率。染色体适应值越大，该染色体被遗传到下一代的概率也越大；反之，染色体的适应值越小，该染色体被遗传到下一代的概率也越小。因此适应函数的选取至关重要，直接影响到GA的收敛速度以及能否找到最优解。群体中的每个染色体都需要计算适应值适应函数一般由目标函数变换而成12/31/202236适应函数适应函数(Fitness Function)适应函数常见形式：适应函数常见形式：直接将目标函数转化为适应函数直接将目标函数转化为适应函数若目标函数为最大化问题：Fitness(f(x)=f(x)若目标函数为

28、最小化问题：Fitness(f(x)=-f(x)12/31/202237适应函数适应函数(Fitness Function)界限构造法界限构造法 目标函数为最大化问题其中Cmin为f(x)的最小估计值 目标函数为最小化问题其中Cmaxn为f(x)的最大估计值12/31/202238选择选择(Selection)选择选择(复制复制)操作把当前种群的染色体按与适应值成正比操作把当前种群的染色体按与适应值成正比例的概率复制到新的种群中例的概率复制到新的种群中 主要思想主要思想:适应值较高的染色体体有较大的选择适应值较高的染色体体有较大的选择(复制复制)机会机会设种群的规模为Nxi是种群中第i个染色体

29、染色体xi被选概率12/31/202239选择选择(Selection)实现实现1：”轮盘赌轮盘赌”选择选择(Roulette wheel selection)l产生一个在产生一个在0与总和之间的的随机数与总和之间的的随机数ml从种群中编号为从种群中编号为1的染色体开始，将其适应值与后续染色体的适应值相的染色体开始，将其适应值与后续染色体的适应值相加，直到累加和等于或大于加，直到累加和等于或大于m12/31/202240选择选择(Selection)染色体的适应值和所占的比例染色体的适应值和所占的比例轮盘赌选择12/31/202241选择选择(Selection)随机数23491338627所

30、选号码262514所选染色体110000001111000011000111010010染色体编号123456染色体011101100000100100100110000011适应度81525128被选概率0.160.30.040.10.240.16适应度累计82325304250染色体被选的概率被选的染色体12/31/202242选择选择(Selection)轮轮盘盘上上的的片片分分配配给给群群体体的的染染色色体体，使使得得每每一一个个片片的的大大小小与与对对于于染染色体的适应值成比例色体的适应值成比例从从群群体体中中选选择择一一个个染染色色体体可可视视为为旋旋转转一一个个轮轮盘盘，当当轮轮

31、盘盘停停止止时时，指针所指的片对于的染色体就时要选的染色体。指针所指的片对于的染色体就时要选的染色体。模拟模拟“轮盘赌轮盘赌”算法算法：(1)r=rand(0,1)，s=0，i=0；(2)如果如果sr，则转则转(4)；(3)s=s+p(xi)，i=i+1,转转(2)(4)xi即为被选中的染色体，输出即为被选中的染色体，输出I(5)结束结束12/31/202243选择选择(Selection)其他选择法其他选择法：随机遍历抽样随机遍历抽样(Stochastic universal sampling)局部选择局部选择(Local selection)截断选择截断选择(Truncation sele

32、ction)竞标赛选择竞标赛选择(Tournament selection)特点特点：选择操作得到的新的群体称为交配池，交配池是当前代和下一代之间的中间群体，其规模为初始群体规模。选择操作的作用效果是提高了群体的平均适应值(低适应值个体趋于淘汰，高适应值个体趋于选择)，但这也损失了群体的多样性多样性。选择操作没有产生新的个体，群体中最好个体的适应值不会改变。12/31/202244交叉交叉(crossover,Recombination)遗传交叉(杂交、交配、有性重组)操作发生在两个染色体之间，由两个被称之为双亲的父代染色体，经杂交以后，产生两个具有双亲的部分基因的新的染色体，从而检测搜索空间

33、中新的点。选择(复制)操作每次作用在一个染色体上，而交叉操作每次作用在从交配池中随机选取的两个个体上(交叉概率Pc)。交叉产生两个子染色体，他们与其父代不同，且彼此不同,每个子染色体都带有双亲染色体的遗传基因。12/31/202245单点交叉单点交叉(1-point crossover)在双亲的父代染色体中随机产生一个交叉点位置在双亲的父代染色体中随机产生一个交叉点位置在交叉点位置分离双亲染色体在交叉点位置分离双亲染色体互换交叉点位置右边的基因码产生两个子代染色体互换交叉点位置右边的基因码产生两个子代染色体交叉概率交叉概率Pc 一般范围为一般范围为(60%,90%)，平均约，平均约80%1 1

34、1 11 11 11 11 11 11 1父代父代父代父代1 11 11 11 10 00 00 00 00 00 00 00 00 00 00 00 0子代子代子代子代1 11 11 11 10 00 00 00 00 00 00 00 00 00 00 00 01 11 11 11 11 11 11 11 1交叉点位置交叉点位置交叉点位置交叉点位置12/31/202246交叉交叉(crossover,Recombination)单点交叉操作可以产生与父代染色体完全不同的子代染色体；它不会改变父代染色体中相同的基因。但当双亲染色体相同时，交叉操作是不起作用的。假如交叉概率Pc50%,则交配池

35、中50%的染色体(一半染色体)将进行交叉操作，余下的50%的染色体进行选择(复制)操作。GA利用选择和交叉操作可以产生具有更高平均适应值和更好染色体的群体12/31/202247变异变异(Mutation)以变异概率Pm改变染色体的某一个基因,当以二进制编码时，变异的基因由0变成1，或者由1变成0。变异概率Pm 一般介于1/种群规模与1/染色体长度之间，平均约1-2%1 11 10 01 10 01 10 00 0父代父代父代父代0 01 10 01 10 01 10 01 1子代子代子代子代变异基因变异基因变异基因变异基因变异基因变异基因变异基因变异基因12/31/202248变异变异(Mu

36、tation)比起选择和交叉操作，变异操作是GA中的次要操作，但它在恢复群体中失去的多样性多样性方面具有潜在的作用。在GA执行的开始阶段，染色体中一个特定位上的值1可能与好的性能紧密联系，即搜索空间中某些初始染色体在那个位上的值1可能一致产生高的适应值。因为越高的适应值与染色体中那个位上的值1相联系，选择操作就越会使群体的遗传多样性损失。等到达一定程度时，值0会从整个群体中那个位上消失，然而全局最优解可能在染色体中那个位上为0。如果搜索范围缩小到实际包含全局最优解的那部分搜索空间，在那个位上的值0就可能正好是到达全局最优解所需要的。12/31/202249停止准则停止准则(Terminatio

37、n Criteria)种群中个体的最大适应值超过预设定值种群中个体的平均适应值超过预设定值种群中个体的进化代数超过预设定值12/31/202250基本步骤基本步骤(Step by Step)(1)随机产生初始种群;(2)计算种群体中每个个体的适应度值,判断是否满足停止条件，若不满足，则转第(3)步,否则转第(6)步;(3)按由个体适应值所决定的某个规则选择将进入下一代的个体;(4)按交叉概率Pc进行交叉操作,生产新的个体;(5)按变异概率Pm进行变异操作,生产新的个体;(6)输出种群中适应度值最优的染色体作为问题的满意解或最优解。12/31/202251流程图流程图(Flow Chart)12

38、/31/202252基本遗传算法基本遗传算法基本遗传算法（SimpleGeneticAlgorithms,简称SGA）是一种统一的最基本的遗传算法，它只使用选择、交叉、变异这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。12/31/202253SGA伪码描述伪码描述ProcedureGeneticAlgorithmbeginbegint=0;%遗传代数初始化 P(t);%初始化种群或染色体计算 P(t)的适应值;while(不满足停止准则)do begin t=t+1;从P(t-1)中选择

39、P(t);%selection 重组 P(t);%crossover and mutation 计算 P(t)的适应值;end end12/31/202254遗传算法的应用遗传算法的应用函数优化函数优化函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能测试评价的常用算例。对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面列举一些遗传算法的主要应用领域。12/31/202255遗传算法的应用遗传算法的应

40、用组合优化组合优化遗传算法是寻求组合优化问题满意解的最佳工具之一，实践证明，遗传算法对于组合优化问题中的NP完全问题非常有效。例如，遗传算法已经在求解旅行商问题(Traveling Salesman Problem,TSP)、背包问题(Knapsack Problem)、装箱问题(Bin Packing Problem)等方面得到成功的应用。生产调度问题生产调度问题生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为解决复杂调度问题的有效工具。12/31/202256遗传算法的应用遗传算法的应

41、用自动控制自动控制遗传算法已经在自动控制领域中得到了很好的应用，例如基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等。机器人智能控制机器人智能控制机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人智能控制自然成为遗传算法的一个重要应用领域。12/31/202257遗传算法的应用遗传算法的应用图象处理和模式识别图象处理和模式识别图像处理和模式识别是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地存在一些误差，

42、这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求，遗传算法在这些图像处理中的优化计算方面得到了很好的应用。人工生命人工生命人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大重要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础。12/31/202258遗传算法的应用遗传算法的应用遗传程序设计遗传程序设计Koza发展了遗传程序设计的概念，他使用了以LISP语言所表示的编码方法，基于对一种树形结构所进行的遗传操作来自动生成计算机程序。机器学习机器学习

43、 基于遗传算法的机器学习，在很多领域中都得到了应用。例如基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可以用于人工神经网络的网络结构优化设计。分类器系统在多机器人路径规划系统中得到了成功的应用。12/31/202259SGA实例实例1：函数最值：函数最值SGA参数:编码方式:二进制码 e.g.00000e.g.000000;0;01101 01101 13;1111113;111113131种群规模:4随机初始群体“转盘赌”选择一点杂交,二进制变异 求函数f(x)=x2的最大值，x为自然数且0 x31.o手工方式完成演示SGA过程12/31/202260SGA实例实例1 max x2

44、 :选择操作选择操作12/31/202261SGA实例实例1 max x2 :交叉操作交叉操作12/31/202262SGA实例实例1 max x2 :变异操作变异操作12/31/202263SGA实例实例2:连续函数最值连续函数最值求下列函数的最大值：12/31/202264SGA实例实例2:编码编码高精度高精度编码 x,y 0,1L 必须可逆(一个表现型对应一个基因型)解码算子解码算子：:0,1L x,y 染色体长度染色体长度L决定可行解的最大精度决定可行解的最大精度长染色体长染色体(慢进化慢进化)实数问题：变量z为实数，如何把a1,aL 0,1Lzx,y12/31/202265SGA实例

45、实例2:编码编码设定求解精确到设定求解精确到6位小数，因区间长度位位小数，因区间长度位2-(-1)=3,则需将区则需将区间分为间分为3X106等份。因等份。因 2097152221 3X1062224194304。故编码的二进制串长。故编码的二进制串长L=22。将一个二进制串将一个二进制串(b21b20b0)转化为转化为10进制数：进制数：e.g.-1;2 1.627 888 1.627888=-1+3x(1110000000111111000101)2/(222-1)=-1+3x3674053/(222-1)12/31/202266SGA实例实例2:初始化种群、适应函数初始化种群、适应函数随

46、机初始化种群随机初始化种群适应函数适应函数本实例目标函数在定义域内均大于0，且是求函数最大值，故直接引用目标函数作为适应函数：f(s)=f(x)其中二进制串s对于变量x的值。e.g.s1=x1=-0.958973适应值适应值:f(s1)=f(x1)=1.078878s2=x2=1.627888适应值适应值:f(s2)=f(x2)=3.25065012/31/202267SGA实例实例2:遗传操作遗传操作选择操作(“轮盘赌”选择)交叉操作(单点交叉)交叉前交叉前(父父):s1=s2=交叉后交叉后(子子):s1=s2=适应值适应值:f(s1)=f(-0.998113)=1.940865f(s2)=

47、f(1.666028)=3.459245s2的适应值比其双亲个体的适应值高。12/31/202268SGA实例实例2:遗传操作遗传操作变异操作变异前变异前(父父):s2=变异后变异后(子子):s2=适应值适应值 f(s2)=f(1.721638)=0.917743比f(s2)小变异前变异前(父父):s2=变异后变异后(子子):s”2=适应值适应值f(s”2)=f(1.630818)=3.343555比f(s2)大变异操作有变异操作有”扰动扰动”作用，同时具有增加种群作用，同时具有增加种群多多样性的效果。样性的效果。12/31/202269SGA实例实例2:模拟结果模拟结果遗传算法的参数:种群规

48、模种群规模:50 染色体长度染色体长度:L=22 最大进化代数最大进化代数:150 交叉概率交叉概率:Pc=0.25 变异概率变异概率:Pm=0.0112/31/202270SGA实例实例2:模拟结果模拟结果(最佳个体进化情况最佳个体进化情况最佳个体进化情况最佳个体进化情况)世代数染色体编码变量x适应值1411173440547189150100011100001011000111100000110110001010011110110101011100111001111111010101111110100111111000011011110110011111101001000100011001

49、11110001101101000110011110100110110001011001111110100111111001100111111010011111100110011111.8316241.8424161.8548601.8475361.8532901.8484431.8486991.8508971.8505491.8505493.5348063.7903623.8332863.8420043.8434023.8462323.8471553.8501623.8502743.85027412/31/202271最优化问题最优化问题(Optimization Problem)最优化问题

50、最优化问题:组合优化问题组合优化问题(Combinatorial Optimization Problem):最优化问题中的解空间X或S由离散集合构成。12/31/202272最优化问题算法最优化问题算法传统的优化方法传统的优化方法(局部优化方法局部优化方法)共轭梯度法、牛顿法、单纯形方法共轭梯度法、牛顿法、单纯形方法等特点:1)依赖于初始条件。2)与求解空间有紧密关系，促使较快地收敛到局部解，但同时对解域有约束，如连续性或可微性。利用这些约束，收敛快。3)有些方法，如Davison-Fletcher-Powell直接依赖于至少一阶导数；共轭梯度法隐含地依赖于梯度。12/31/202273最优