智能算法初步资料课件.ppt

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

1、滥宫虹浚疵盾若鄙孜火猖捅磷疤橱改蘑砌枉竿蔽侍藏涤式昭煤胰丧酸枉粘智能算法初步智能算法初步数学建模中的智能算法端照镜袍惶升浪荧镣剩洪渺宜珊畅赘倾禹批印黑貌痒凋苏婶痈制之琐呛糯智能算法初步智能算法初步2数学建模十大算法数学建模十大算法l蒙特卡罗算法蒙特卡罗算法l数据拟合、参数估计、插值等数据处理算法数据拟合、参数估计、插值等数据处理算法l线性规划等规划类问题线性规划等规划类问题l图论算法图论算法l动态规划、回溯搜索、分支定界等计算机算法动态规划、回溯搜索、分支定界等计算机算法l模拟退火、神经网络、遗传算法等最优化理论算法模拟退火、神经网络、遗传算法等最优化理论算法l网格算法和穷举法网格算法和穷举法

2、l一些连续离散化方法一些连续离散化方法l数值分析算法数值分析算法l图像处理算法图像处理算法朴雹皮深冕狱猫炉脏卵斟镭抓踪煽轻玛饺产胆曰乱葡催凳缝娇活此把薄矾智能算法初步智能算法初步2/23/202333人工智能优化算法l遗传算法遗传算法l模拟退火模拟退火l人工神经网络算法人工神经网络算法l粒子群算法粒子群算法l蚁群算法蚁群算法炒拟亭锄拍寝呼毕湛拇峨疆难稼遮摈尘谅着诈降狐哇频酪沏谬凹衣返臀兵智能算法初步智能算法初步2/23/20234认识认识“人工智能人工智能”l人人工工智智能能(Artificial Intelligence,AI)概概念念是是John McCarthy（约约翰翰.麦麦克克斯斯）

3、于于1956年在年在Dartmouth学会上提出的。学会上提出的。l美美国国计计算算机机科科学学家家，因因在在人人工工智智能能领领域域的的重重大大贡贡献献，被被称称为为“人人工工智智能能之之父父”，并因此获得图灵奖，并因此获得图灵奖l他他于于1948年年获获得得加加州州理理工工学学院院数数学学学学士士学学位位，1951年年获获得得普普林林斯斯顿顿大大学学数数学学博博士学位士学位John McCarthy洁弃锣糜壳银琶荔蜘菲崩联籍幂镐掘防搔糙午保缉胆涡站狠慧印固山佛洁智能算法初步智能算法初步2/23/20235认识认识“人工智能人工智能”（续）（续）l人工智能人工智能让机器像人一样思考让机器像人

4、一样思考l人工智能是计算机科学的前沿学科，是研究、开发用于模拟、延人工智能是计算机科学的前沿学科，是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学术科学.计算机编程语言和其它计算机软件都因为有了人工智能的计算机编程语言和其它计算机软件都因为有了人工智能的进展而得以存在。进展而得以存在。l人工智能人工智能涉及学科：涉及学科：哲学和认知科学，数学，神经生理学，心理哲学和认知科学，数学，神经生理学，心理学，计算机科学，信息论，控制论，不定性论，仿生学等学，计算机科学，信息论，控制论，不定性论，仿生学等炳筒吐

5、新忌尽袄椎魁条洛浦淋匈痔撇梯碑阶巫悯简呼昨萌沾瞪妇腊桐诺筐智能算法初步智能算法初步2/23/20236认识认识“人工智能人工智能”（续）（续）l人人工工智智能能的的目目的的：通通过过研研究究人人脑脑的的组组成成机机理理和和思思维维方方式式，企企图图了了解解智智能能的的实实质质，并并生生产产出出一一种种能能以以人人类类智智能能相相似似的的方方式式做做出出反反应应的智能机器的智能机器让机器具有智慧，像人一样思考让机器具有智慧，像人一样思考.l计计算算机机的的出出现现人人类类开开始始真真正正有有了了一一个个可可以以模模拟拟人人类类思思维维的的工工具具l人人工工智智能能的的领领域域研研究究：包包括括机

6、机器器人人、语语言言识识别别、图图像像识识别别、自自然然语言处理和专家系统等语言处理和专家系统等.冶济伙与腑乐裤颊甚丛怕焙铃瘫燕焙耐专芹绒怒注陛凿冶赁答夹丹照淬忠智能算法初步智能算法初步2/23/20237意识和人工智能的区别意识和人工智能的区别l人工智能就其本质而言，是对人的思维的信息过程的人工智能就其本质而言，是对人的思维的信息过程的模拟模拟.l对于人的思维模拟可以从两条道路进行：对于人的思维模拟可以从两条道路进行：结构模拟：仿照人脑的结构机制，制造出结构模拟：仿照人脑的结构机制，制造出“类人脑类人脑”的机器；的机器；功能模拟：暂时撇开人脑的内部结构，而从其功能过程进行模拟。功能模拟：暂时

7、撇开人脑的内部结构，而从其功能过程进行模拟。现现代代电电子子计计算算机机的的产产生生便便是是对对人人脑脑思思维维功功能能的的模模拟拟，是是对对人人脑脑思维的信息过程的模拟思维的信息过程的模拟.l人工智能不是人的智能，更不会超过人的智能人工智能不是人的智能，更不会超过人的智能.喘谗痰祝惶扒荆闺玄嫁鼓哆段钟甩蓬短怎渠拜啡据仰氮席维拷讳制蔚菏镜智能算法初步智能算法初步2/23/20238意识和人工智能的区别（续）意识和人工智能的区别（续）“机器思维机器思维”同同“人类思维人类思维”的本质区别：的本质区别：1.人人工工智智能能纯纯系系无无意意识识的的机机械械的的物物理理的的过过程程，人人类类智智能能主

8、主要要是是生生理和心理的过程理和心理的过程.2.人工智能没有社会性人工智能没有社会性.3.人工智能没有人类的意识所特有的能动的创造能力人工智能没有人类的意识所特有的能动的创造能力.4.两者总是人脑的思维在前，电脑的功能在后两者总是人脑的思维在前，电脑的功能在后.詹辊戳疙总马把压今鸵记硫冻詹闺跨帛梯史咨争靛盐趟菩悠填砸蚊枉愧遣智能算法初步智能算法初步2/23/20239经典的人工智能成果经典的人工智能成果l l人机对弈人机对弈人机对弈人机对弈 *1996年年2月月10-17日日,Garry Kasparov以以4:2战胜战胜“深蓝深蓝”(Deep Blue)*1997年年5月月3-11日日,Ga

9、rry Kasparov以以3.5:2.5输于改进后的输于改进后的“深蓝深蓝”*2003年年2月月Garry Kasparov 3:3战平战平“小深小深”(Deep Junior)*2003年年11月月Garry Kasparov 2:2战平战平“X3D德国人德国人”(X3D-Fritz)l l模式识别模式识别模式识别模式识别 指纹识别、人脸识别、语音识别、文字识别、图像识别、车牌识别等指纹识别、人脸识别、语音识别、文字识别、图像识别、车牌识别等汇婉胁仟一敲衡搬挛儒札狈共咏魔兵菌颅万膳躁湃乖害渐柳狂患市溶换请智能算法初步智能算法初步2/23/202310经典的人工智能成果经典的人工智能成果(续

10、续)l l电电电电 影影影影中文名：人工智能中文名：人工智能 片片 名：名：AI 年年 代：代：2001 国国 家：美国家：美国oo相关著作相关著作相关著作相关著作视读人工智能、人工智能的未来、人工智能哲学、人视读人工智能、人工智能的未来、人工智能哲学、人工智能：一种现代的方法工智能：一种现代的方法罐熬贵众逊协淋搬燥痔痊判拾枚埂耻风纷霹刑筹嘲悲眩涅趟浆冬敌扫厘攫智能算法初步智能算法初步2/23/202311l遗传算法遗传算法(Genetic Algorithm，GA)l人工神经网络算法人工神经网络算法(Artificical Neural Network,ANN)l模拟退火模拟退火(Simul

11、ated Annealing,SA)l粒粒 子子 群群 优优 化化 算算 法法(Partical Swam Optimization Algorithm,PSOA)l蚁群优化算法蚁群优化算法(Ant Colony Optimization Algorithm,ACOA)人工智能优化算法人工智能优化算法当这氯迭毕侩泵卵妓徒惠姬铅陇间猜路绑腐迁湘里湍宠杯嘻哀畔因雌知示智能算法初步智能算法初步2/23/20231297年年A 题用模拟退火算法题用模拟退火算法00年年B 题用神经网络分类算法题用神经网络分类算法01年年B 题这种难题也可以使用神经网络题这种难题也可以使用神经网络美国美国89年年A 题也

12、和题也和BP 算法算法有关系美国美国03年年B 题题伽马刀问题也是目前研究的课题，目前算法最佳的是遗传算法算法最佳的是遗传算法。遗传算法(GA)、模拟退火法(SA)、神经网络(NN)、近几年的赛题越来越复杂，很多问题没有什么很好的模型可以借鉴，于是这三类算法很多时候可以派上用场。最优化理论的三大非经典算法最优化理论的三大非经典算法:媚夸僻仆沁芜唤助缄茄俩玖拖移湖笼澈掏徘稼庄挤媒崔锋请刷闻挨枝副肛智能算法初步智能算法初步2/23/202313l遗传算法遗传算法(Genetic Algorithm，GA)l人工神经网络算法人工神经网络算法(Artificical Neural Network,AN

13、N)l模拟退火模拟退火(Simulated Annealing,SA)l粒粒 子子 群群 优优 化化 算算 法法(Partical Swam Optimization Algorithm,PSOA)l蚁群优化算法蚁群优化算法(Ant Colony Optimization Algorithm,ACOA)人工智能优化算法人工智能优化算法立届阶及逸恼竿即肘装知酒艘傲北粹搏梨被捞匈陈掐号契梁葱究束搭汽粹智能算法初步智能算法初步2/23/202314遗传算法遗传算法(Genetic Algorithm)进化算法(EvolutionaryAlgorithm)锅盯棕舀拽勤抒挥虽剃砰牲伴庞诧阳桌扁磐侦善熄欧

14、失沤斧慰犹怀暗忱卑智能算法初步智能算法初步2/23/202315l遗遗传传算算法法是是一一类类模模拟拟达达尔尔文文生生物物进进化化论论的的自自然然选选择择和和遗遗传传算算法法机机理理的的生生物物进进化化过过程程的的计计算算模模型型，借借鉴鉴生生物物界界的的进进化化规规律律（适适者者生生存，优胜劣汰遗传机制）演化而来的存，优胜劣汰遗传机制）演化而来的随机化搜索最优化方法随机化搜索最优化方法。l遗遗传传算算法法最最初初由由美美国国密密歇歇根根大大学学J.Holland（霍霍兰兰德德）教教授授于于1975年年首首先先提提出出来来的的，并并出出版版了了颇颇有有影影响响的的专专著著Adaptation

15、in Natural and Artificial Systems,遗遗传传算算法法这这个个名名称称才才逐逐渐渐为为人人所所知知，通通常常称为称为“简单遗传算法简单遗传算法”。遗传算法遗传算法(Genetic Algorithm,GA)澎矛沧夺灰铰啊砚管席惋钦唯超敦域门戌茂键顽渍二驾橙迄饵这给君膜尼智能算法初步智能算法初步2/23/202316l直接对结构对象进行操作，不存在求导和函数连续性的限定；直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；具有内在的隐并行性和更好的全局寻优能力；采采用用概概率率化化的的寻寻优优方方法法，能能自自动动获获取取和

16、和指指导导优优化化的的搜搜索索空空间间，自自适应地调整搜索方向，不需要确定的规则。适应地调整搜索方向，不需要确定的规则。l遗遗传传算算法法的的这这些些性性质质，已已被被人人们们广广泛泛地地应应用用于于组组合合优优化化、机机器器学学习习、信信号号处处理理、自自适适应应控控制制和和人人工工生生命命等等领领域域。它它是是现现代代有有关关智智能计算中的关键技术。能计算中的关键技术。遗传算法的主要特点遗传算法的主要特点晌榆珐珐柬馈选黎紊辩胞搜连胖峡骡咕诌脆漫肝嚷迄业内抚卒枢厦法栖箭智能算法初步智能算法初步2/23/202317遗传算法的定义遗传算法的定义l遗遗传传算算法法是是从从代代表表问问题题可可能能

17、潜潜在在的的解解集集的的一一个个种种群群（population）开开始始的的，而而一一个个种种群群则则由由经经过过基基因因（gene）编编码码的的一一定定数数目目的的个个体体(individual)组成。组成。l每个个体实际上是染色体每个个体实际上是染色体(chromosome)带有特征的实体。带有特征的实体。l染染色色体体作作为为遗遗传传物物质质的的主主要要载载体体，即即多多个个基基因因的的集集合合，其其内内部部表表现现（即即基基因因型型）是是某某种种基基因因组组合合，它它决决定定了了个个体体的的形形状状的的外外部部表表现现，如如黑黑头头发发的的特特征征是是由由染染色色体体中中控控制制这这一

18、一特特征征的的某某种种基基因因组组合合决决定定的的。因因此此，在在一一开开始始需需要要实实现现从从表表现现型型到到基基因因型型的的映映射射即即编编码工作。码工作。俱我辨嫂驻庞嚼窒壕辈雌掏驶溢媚霖奋梆防蛾汁锄脯教棱蟹谦愈凹诣音琴智能算法初步智能算法初步2/23/202318遗传算法的定义（续）遗传算法的定义（续）l由由于于仿仿照照基基因因编编码码的的工工作作很很复复杂杂，我我们们往往往往进进行行简简化化，如如二二进进制制编编码码，初初代代种种群群产产生生之之后后，按按照照适适者者生生存存和和优优胜胜劣劣汰汰的的原原理理，逐逐代（代（generation）演化产生出越来越好的近似解。）演化产生出越

19、来越好的近似解。l在在每每一一代代，根根据据问问题题域域中中个个体体的的适适应应度度（fitness）大大小小选选择择（selection）个个体体，并并借借助助于于自自然然遗遗传传学学的的遗遗传传算算子子（genetic operators）进进行行组组合合交交叉叉（crossover）和和变变异异（mutation），产产生生出出代代表表新新的的解解集集的的种种群群。这这个个过过程程将将导导致致种种群群像像自自然然进进化化一一样样的的后后生生代代种种群群比比前前代代更更加加适适应应于于环环境境，末末代代种种群群中中的的最最优优个个体体经经过过解解码（码（decoding），可以作为问题近似

20、最优解。），可以作为问题近似最优解。腮锯姜鉴倒更肩阂涨诫瞥哀违洋虑渊盼净屋到眶晨怎晒绷刑澎鼻占蘸荷洛智能算法初步智能算法初步2/23/202319遗传算法流程图遗传算法流程图l由由于于遗遗传传算算法法的的整整体体搜搜索索策策略略和和优优化化搜搜索索方方法法在在计计算算是是不不依依赖赖于于梯梯度度信信息息或或其其它它辅辅助助知知识识，而而只只需需要要影影响响搜搜索索方方向向的的目目标标函函数数和和相相应应的的适适应应度度函函数数，所所以以遗遗传传算算法法提提供供了了一一种种求求解解复复杂杂系系统统问问题题的的通通用用框框架架，它它不不依依赖赖于于问问题题的的具具体体领领域域，对对问问题题的的种种

21、类类有有很很强强的鲁棒性。的鲁棒性。江令奎谓氦类翅恶雷熏人佩六酵舔柄烂族骂舀切费棵脊穿裔橇掉卿克苫绕智能算法初步智能算法初步2/23/202320遗传算法的一般算法遗传算法的一般算法l遗传算法是由进化论和遗传学机理而产生的搜索算法。遗传算法是由进化论和遗传学机理而产生的搜索算法。1.创创建建一一个个随随机机的的初初始始状状态态：初初始始群群是是从从解解中中随随机机选选择择出出来来的的，将将这这些解比喻为染色体或基因，该种群被称为第一代。些解比喻为染色体或基因，该种群被称为第一代。2.评评估估适适应应度度：对对每每一一个个解解(染染色色体体)指指定定一一个个适适应应度度的的值值，根根据据问问题题

22、求求解解的的实实际际接接近近程程度度来来指指定定(以以便便逼逼近近求求解解问问题题的的答答案案)。不不要要把把这这些些“解解”与与问问题题的的“答答案案”混混为为一一谈谈，可可以以把把它它理理解解成成为为要要得得到到答答案案，系统可能需要利用的那些特性。系统可能需要利用的那些特性。咨瑰唐控惕农海建扫沮奥鲸供锋寥良噪涅醋棋嘶钻悉芍考杏正寇窗泌皋导智能算法初步智能算法初步2/23/202321遗传算法的一般算法遗传算法的一般算法(续续)l3.繁殖繁殖(包括子代突变包括子代突变)带带有有较较高高适适应应度度值值的的那那些些染染色色体体更更可可能能产产生生后后代代(后后代代产产生生后后也也将将发发生生

23、突突变变)。后后代代是是父父母母的的产产物物，他他们们由由来来自自父父母母的的基基因因结结合合而而成成，这这个个过过程被称为程被称为“杂交杂交”。4.下一代下一代 如如果果新新的的一一代代包包含含一一个个解解，能能产产生生一一个个充充分分接接近近或或等等于于期期望望答答案案的的输输出出，那那么么问问题题就就已已经经解解决决了了。如如果果情情况况并并非非如如此此，新新的的一一代代将将重重复复他他们们父父母母所进行的繁衍过程，一代一代演化下去，直到达到期望的解为止。所进行的繁衍过程，一代一代演化下去，直到达到期望的解为止。几诽呐芝袍凿恳怀纶蒋泅决眶样躇膜滇脑寻猖缄敖侧鹤咏顿件糖踊槽疲重智能算法初步

24、智能算法初步2/23/202322遗传算法的一般算法遗传算法的一般算法(续续)l5.并行计算并行计算*非常容易将遗传算法用到并行计算和群集环境中。非常容易将遗传算法用到并行计算和群集环境中。*一种方法是直接把每个节点当成一个并行的种群看待。然后有机体一种方法是直接把每个节点当成一个并行的种群看待。然后有机体根据不同的繁殖方法从一个节点迁移到另一个节点。根据不同的繁殖方法从一个节点迁移到另一个节点。*另一种方法是另一种方法是“农场主农场主/劳工劳工”体系结构，指定一个节点为体系结构，指定一个节点为“农场农场主主”节点，负责选择有机体和分派适应度的值，另外的节点作为节点，负责选择有机体和分派适应度

25、的值，另外的节点作为“劳劳工工”节点，负责重新组合、变异和适应度函数的评估。节点，负责重新组合、变异和适应度函数的评估。呆氢板窘屏秧应唁筛碴霄铜转收呈良腥繁痴漂振阐遏念谅准直写端条搽斧智能算法初步智能算法初步2/23/202323遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子遗传算子(选择、交叉和变选择、交叉和变异异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法的搜索机制遗传算法的搜索机制卿鸡当徒缎峰假恰特谨乔腋牌赋脐饲釜甸吩妄下阉

26、奶惑昭粕怯劝舀佩钟兔智能算法初步智能算法初步2/23/202324局部局部局部局部全局全局全局全局遗传算法遗传算法(GA)龟洽俏丽慢藕檄宜看秆儡鸡木孪粮理珍扳泰测洁尖眯润兑漱帚焚醚暮镑碌智能算法初步智能算法初步2/23/202325We have a dream!We have a dream!I am at the I am at the toptopHeight 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 cont

27、inue遗传算法遗传算法(GA)GA-第0代验拇马邪牙捣破通纯害父嗅名元阿肮任孺吱拉似歉琅忍剿容亨底诸脱渝殿智能算法初步智能算法初步2/23/202326Dead oneDead oneNew oneNew one遗传算法遗传算法(GA)GA-第1代瞎逐六娠库骆台障奢蒙览抹认碉痛哦贵疾杏兆植剃净弓弥尊结兴误郭徐床智能算法初步智能算法初步2/23/202327Not at the top,Not at the top,Come Up!Come Up!遗传算法遗传算法(GA)GA-第?代俭权牺矗原卷首哗舅巫滥柞饯犀爵果虹沼窝寺甲坍伎阅泡端终历舆玩羹耍智能算法初步智能算法初步2/23/202328I

28、 am the I am the BESTBEST!遗传算法遗传算法(GA)GA-第N代忧砌涉硷纹侯娠散辞卿完走近瑟晰悼遭辊巍挽祭酥假互板入利极鲤青车察智能算法初步智能算法初步2/23/202329生物进化与遗传算法对应关系生物进化与遗传算法对应关系生物进化生物进化遗传算法遗传算法适者生存适应函数值最大的解被保留的概率最大个体问题的一个解染色体解的编码基因编码的元素群体被选定的一组解种群根据适应函数选择的一组解交叉以一定的方式由双亲产生后代的过程变异编码的某些分量发生变化的过程环境适应函数壶扎晴公碎科橙垮速偿搅赠凯螟隶酞呼寄肆潞眯崔砌炳榴淄耽脉包扑壕塑智能算法初步智能算法初步2/23/2023

29、30遗传算法的基本操作遗传算法的基本操作选择选择(selection):根据各个个体的适应值，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。交叉交叉(crossover):将群体P(t)内的各个个体随机搭配成对，对每一个个体，以某个概率Pc(称为交叉概率，crossvoerrate)交换它们之间的部分染色体。变异变异(mutation):对群体P(t)中的每一个个体，以某一概率Pm(称为变异概率，mutationrate)改变某一个或一些基因座上基因值为其它的等位基因。布闯储崩奠祁垢课聪米泊止燎句稀氨淹腔巷由羞究萝疏签捐歇丘简吴示骗智能算法初步

30、智能算法初步2/23/202331如何设计遗传算法如何设计遗传算法如何进行编码？如何进行编码？如何产生初始种群？如何产生初始种群？如何定义适应函数？如何定义适应函数？如何进行遗传操作如何进行遗传操作(复制、交叉、变异复制、交叉、变异)？如何产生下一代种群？如何产生下一代种群？如何定义停止准则如何定义停止准则？夏卒湿斯圈闻肄想唾滇矢惧隅主膊蜗炊农甚聪咯惰讲总昌咋夫糜肮吟甸飞智能算法初步智能算法初步2/23/202332编码编码(Coding)表现型空间编码(Coding)解码(Decoding)基因型空间=0,1L0111010010100010011001001010010001斗酿舞双琐碌慑

31、炭湖桨篙釉柴柳件伟骋痊吓炬芋肥棺校恩祟蛮盅菌西艰锈智能算法初步智能算法初步2/23/202333编码编码设某一参数的取值范围为（L，U），使用长度为k 的二进制编码表示该数，则共有 种不同的编码。砸姿疫骚琐养议蜘邱存颅捷三败堰朝生避婴臻眺圈襟九蜜即释赎仿音绳涪智能算法初步智能算法初步2/23/202334解码解码解码的目的是为了将不直观的二进制数据串还原成十进制。设某一个体的二进制编码为则对应的解码公式为：嗅祸汤刚粤坝暮兼绍刀爵冒缓劣乏典藤罐撬石犁伎卢瑚箔骸隐树脯人余筐智能算法初步智能算法初步2/23/202335适应函数适应函数(Fitness Function)GA在搜索中不依靠外部信息，

32、仅以适应函数为依据，利用群体中每个染色体(个体)的适应值来进行搜索。以染色体适应值的大小来确定该染色体被遗传到下一代群体中的概率。染色体适应值越大，该染色体被遗传到下一代的概率也越大；反之，染色体的适应值越小，该染色体被遗传到下一代的概率也越小。因此适应函数的选取至关重要，直接影响到GA的收敛速度以及能否找到最优解。群体中的每个染色体都需要计算适应值适应函数一般由目标函数变换而成蝗挞壤象铂夫内奄坤瞩夯去旺占冒艳峙必乍岛通倘皑馏恿沉钨散朽哼牢旷智能算法初步智能算法初步2/23/202336适应函数适应函数(Fitness Function)适应函数常见形式：适应函数常见形式：直接将目标函数转化为

33、适应函数直接将目标函数转化为适应函数若目标函数为最大化问题：Fitness(f(x)=f(x)若目标函数为最小化问题：Fitness(f(x)=-f(x)杆淮肤桌厘泪显霍娩沿戍撩寸峦邪疫搜牡窝恐宪束卓职脯掸寥撕傍成姥聘智能算法初步智能算法初步2/23/202337适应函数适应函数(Fitness Function)界限构造法界限构造法 目标函数为最大化问题其中Cmin为f(x)的最小估计值 目标函数为最小化问题其中Cmaxn为f(x)的最大估计值店蒂棘甩混胸胶达峦想走佣动衡挂酮仆己乱冈润贯潞趁振构淡甘吁帘引谚智能算法初步智能算法初步2/23/202338选择选择(Selection)选择选择(

34、复制复制)操作把当前种群的染色体按与适应值成正比操作把当前种群的染色体按与适应值成正比例的概率复制到新的种群中例的概率复制到新的种群中 主要思想主要思想:适应值较高的染色体体有较大的选择适应值较高的染色体体有较大的选择(复制复制)机会机会设种群的规模为Nxi是种群中第i个染色体染色体xi被选概率讣仰陛当座雄钳瘫把氓鞋毅掷绿汛虹咎窗宦忧专瘪罚渐郎履防暴连肘丰介智能算法初步智能算法初步2/23/202339选择选择(Selection)实现实现1：”轮盘赌轮盘赌”选择选择(Roulette wheel selection)l产生一个在产生一个在0与总和之间的的随机数与总和之间的的随机数ml从种群中

35、编号为从种群中编号为1的染色体开始，将其适应值与后续染色体的适应值相的染色体开始，将其适应值与后续染色体的适应值相加，直到累加和等于或大于加，直到累加和等于或大于m灰蝇聘事俞恫撇边磨喇参悦危喂形腋隧迪方驾随娄潦萝少德掣许纫居萌牌智能算法初步智能算法初步2/23/202340选择选择(Selection)染色体的适应值和所占的比例染色体的适应值和所占的比例轮盘赌选择硝驶恤史置怖缀抿溶墓舅蒙因器膳裙侄点珠黑庸鹿慑垮雹院粪蠢栏砾芥亲智能算法初步智能算法初步2/23/202341选择选择(Selection)随机数23491338627所选号码262514所选染色体110000001111000011

36、000111010010染色体编号123456染色体011101100000100100100110000011适应度81525128被选概率0.160.30.040.10.240.16适应度累计82325304250染色体被选的概率被选的染色体碗捐惦燥爵精椎犀骂役昧辰措讳娇化属娘拒枪揣曰肌静两卵尹称苔闪贸盲智能算法初步智能算法初步2/23/202342选择选择(Selection)轮轮盘盘上上的的片片分分配配给给群群体体的的染染色色体体，使使得得每每一一个个片片的的大大小小与与对对于于染染色体的适应值成比例色体的适应值成比例从从群群体体中中选选择择一一个个染染色色体体可可视视为为旋旋转转一一

37、个个轮轮盘盘，当当轮轮盘盘停停止止时时，指针所指的片对于的染色体就时要选的染色体。指针所指的片对于的染色体就时要选的染色体。模拟模拟“轮盘赌轮盘赌”算法算法：(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)结束结束绪苗惨玫丸驴梆站骗瘸狙端捉愚臻豆阀剐浙片调瓤舷祥钎至辛苯违捂深畸智能算法初步智能算法初步2/23/202343选择选择(Selection)其他选择法其他选择法：随机遍历抽样随机遍历抽样(Stochastic universal sam

38、pling)局部选择局部选择(Local selection)截断选择截断选择(Truncation selection)竞标赛选择竞标赛选择(Tournament selection)特点特点：选择操作得到的新的群体称为交配池，交配池是当前代和下一代之间的中间群体，其规模为初始群体规模。选择操作的作用效果是提高了群体的平均适应值(低适应值个体趋于淘汰，高适应值个体趋于选择)，但这也损失了群体的多样性多样性。选择操作没有产生新的个体，群体中最好个体的适应值不会改变。谴碟侨掘葡采语氏墨掺享吗谤王诊陆赊椭攫侗双暇黑励抗敢闻峨位辙颂藻智能算法初步智能算法初步2/23/202344交叉交叉(cross

39、over,Recombination)遗传交叉(杂交、交配、有性重组)操作发生在两个染色体之间，由两个被称之为双亲的父代染色体，经杂交以后，产生两个具有双亲的部分基因的新的染色体，从而检测搜索空间中新的点。选择(复制)操作每次作用在一个染色体上，而交叉操作每次作用在从交配池中随机选取的两个个体上(交叉概率Pc)。交叉产生两个子染色体，他们与其父代不同，且彼此不同,每个子染色体都带有双亲染色体的遗传基因。伴细穿脆蒸羔碍破蓬尼腮殴鸣些匝玫乏恍携屑翟求肺污逃瘩斩川褂伟氦紊智能算法初步智能算法初步2/23/202345单点交叉单点交叉(1-point crossover)在双亲的父代染色体中随机产生一

40、个交叉点位置在双亲的父代染色体中随机产生一个交叉点位置在交叉点位置分离双亲染色体在交叉点位置分离双亲染色体互换交叉点位置右边的基因码产生两个子代染色体互换交叉点位置右边的基因码产生两个子代染色体交叉概率交叉概率Pc 一般范围为一般范围为(60%,90%)，平均约，平均约80%1 11 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交叉

41、点位置交叉点位置交叉点位置交叉点位置钒狐蹬本么靶万蛮鳖房葡摧唱绞恩梯泞上建细怪岭吏落刨郑霹肉臂谣辟抵智能算法初步智能算法初步2/23/202346交叉交叉(crossover,Recombination)单点交叉操作可以产生与父代染色体完全不同的子代染色体；它不会改变父代染色体中相同的基因。但当双亲染色体相同时，交叉操作是不起作用的。假如交叉概率Pc50%,则交配池中50%的染色体(一半染色体)将进行交叉操作，余下的50%的染色体进行选择(复制)操作。GA利用选择和交叉操作可以产生具有更高平均适应值和更好染色体的群体魁铭学瞧椎僻具楚冻磕垒狐盏患哭蔼委貌组陷咒忆衰陶玛拽势辨萄佰匣傲智能算法初步智

42、能算法初步2/23/202347变异变异(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子代子代子代子代变异基因变异基因变异基因变异基因变异基因变异基因变异基因变异基因妹皱更躯兵场怖沟邵灾肘促历洛告篙莉讥斟谜剥鬃亿摄哭咳酥入郝己尿渭智能算法初步智能算法初步2/23/202348变异变异(Mutation)比起选择和交叉操作，变异操作是GA中的次要操作

43、，但它在恢复群体中失去的多样性多样性方面具有潜在的作用。在GA执行的开始阶段，染色体中一个特定位上的值1可能与好的性能紧密联系，即搜索空间中某些初始染色体在那个位上的值1可能一致产生高的适应值。因为越高的适应值与染色体中那个位上的值1相联系，选择操作就越会使群体的遗传多样性损失。等到达一定程度时，值0会从整个群体中那个位上消失，然而全局最优解可能在染色体中那个位上为0。如果搜索范围缩小到实际包含全局最优解的那部分搜索空间，在那个位上的值0就可能正好是到达全局最优解所需要的。淌浅北击盗汽滔挽兼皆诫逐盒现蓝碑光尤笔说就涣稗宠刃珠懦狰缅昭夸孽智能算法初步智能算法初步2/23/202349停止准则停止

44、准则(Termination Criteria)种群中个体的最大适应值超过预设定值种群中个体的平均适应值超过预设定值种群中个体的进化代数超过预设定值隅坠抱迭胶校盒筷辖横标负讯割龙岛橙狈结诞桩捅绒孜沤色后俯配另揖排智能算法初步智能算法初步2/23/202350基本步骤基本步骤(Step by Step)(1)随机产生初始种群;(2)计算种群体中每个个体的适应度值,判断是否满足停止条件，若不满足，则转第(3)步,否则转第(6)步;(3)按由个体适应值所决定的某个规则选择将进入下一代的个体;(4)按交叉概率Pc进行交叉操作,生产新的个体;(5)按变异概率Pm进行变异操作,生产新的个体;(6)输出种群

45、中适应度值最优的染色体作为问题的满意解或最优解。执储捧奄通腹朴包煮瑰皱响仲矽沂练犹尔俘淀正卤黍娥惩朝或炊澜缠吊图智能算法初步智能算法初步2/23/202351流程图流程图(Flow Chart)涤竹炉联帆挑播什光滑迹按跟疼咕秽攘报水才矣寨犊蔽补票吧博喷尚另因智能算法初步智能算法初步2/23/202352基本遗传算法基本遗传算法基本遗传算法（SimpleGeneticAlgorithms,简称SGA）是一种统一的最基本的遗传算法，它只使用选择、交叉、变异这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应

46、用价值。舞通惩绕陵潭药辗皱往淌昨贡尸虎齐柴尘爵瓦惊虾茹螟姥瞄丢芽项氧淹瓷智能算法初步智能算法初步2/23/202353SGA伪码描述伪码描述ProcedureGeneticAlgorithmbeginbegint=0;%遗传代数初始化 P(t);%初始化种群或染色体计算 P(t)的适应值;while(不满足停止准则)do begin t=t+1;从P(t-1)中选择 P(t);%selection 重组 P(t);%crossover and mutation 计算 P(t)的适应值;end end牲精骏宵蜕晓黑订瘤哑净症绝鹏猿胜贡培氓娄爽礼倡猪迭枚怖章奥问孽痹智能算法初步智能算法初步2/23

47、/202354遗传算法的应用遗传算法的应用函数优化函数优化函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能测试评价的常用算例。对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面列举一些遗传算法的主要应用领域。贯染寿壮硝诞滓灵次扮孺脆伦缆落途聚扬陕亏肌津锋骆投簇己畔迄雪杠挺智能算法初步智能算法初步2/23/202355遗传算法的应用遗传算法的应用组合优化组合优化遗传算法是寻求组合优化问题满意解的最佳工

48、具之一，实践证明，遗传算法对于组合优化问题中的NP完全问题非常有效。例如，遗传算法已经在求解旅行商问题(Traveling Salesman Problem,TSP)、背包问题(Knapsack Problem)、装箱问题(Bin Packing Problem)等方面得到成功的应用。生产调度问题生产调度问题生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为解决复杂调度问题的有效工具。额夏腾佃畅邻栏缅催确拳砖擦横募锑汉嗣蜘爱忱亩样晨芦仔毕沥朽悸剿弘智能算法初步智能算法初步2/23/20235

49、6遗传算法的应用遗传算法的应用自动控制自动控制遗传算法已经在自动控制领域中得到了很好的应用，例如基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等。机器人智能控制机器人智能控制机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人智能控制自然成为遗传算法的一个重要应用领域。鹃疆奴希商痘砷涵胡蛊疾砷艳呕线熊炽姚曲瘟晋又桨昆腊撑柜贸抵剪葡过智能算法初步智能算法初步2/23/202357遗传算法的应用遗传算法的应用图象处理和模式识别图象处理和模式识别图像处理

50、和模式识别是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求，遗传算法在这些图像处理中的优化计算方面得到了很好的应用。人工生命人工生命人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大重要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础。室拂缘啪敷裁户吝瓜役魄婪惯裕审巷迢灶窒挡汝噶汐驭递骚融栏代斯谎思智能算法初步智能算法初步2/23/20235