《遗传算法论文答辩#上课课堂》由会员分享，可在线阅读，更多相关《遗传算法论文答辩#上课课堂（36页珍藏版）》请在金锄头文库上搜索。
1、遗传算法及其应用遗传算法及其应用 姓 名：车少帅 专 业：信息与计算科学 指导教师：武 斌 1优质课件2/20论文章节论文章节结论结论遗传算法求解函数优化问题遗传算法求解函数优化问题 遗传算法的实现技术遗传算法的实现技术 遗传算法的基本概念与原理遗传算法的基本概念与原理 研究目的与意义研究目的与意义2优质课件3/20论文主要工作论文主要工作第第1章章第第2章章第第3章章结论结论应用遗传算法应用遗传算法来解决几个函来解决几个函数优化问题以数优化问题以及用及用MATLAB编编程来实现遗传程来实现遗传算法解决函数算法解决函数优化的实例优化的实例 认识遗传算法认识遗传算法的基本概念，的基本概念，个体与
2、种群、个体与种群、适应度与适应适应度与适应度函数、染色度函数、染色体与基因、选体与基因、选择、交叉、变择、交叉、变异等概念，掌异等概念，掌握基本遗传算握基本遗传算法基本原理与法基本原理与步骤步骤研究一些遗研究一些遗传算法的基传算法的基本实现技术，本实现技术，如编码方法，如编码方法，适应度函数，适应度函数，选择算子，选择算子，交叉算子，交叉算子，变异算子等变异算子等 对整个毕业对整个毕业设计进行全设计进行全面的总结，面的总结，提出本人对提出本人对设计过程中设计过程中各个方面的各个方面的看法、建议看法、建议与心得体会。与心得体会。3优质课件4/20论文研究背景、目的与意义论文研究背景、目的与意义
3、研究背景研究背景: : 90 90年代，遗传算法迎来了兴盛发展时期，年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究格外门的课题。尤其是遗传算法的应用研究格外活跃，不但它的应用领域扩大，而且利用遗活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。高，同时产业应用方面的研究也在摸索之中。4优质课件5/20目的与意义目的与意义：遗传算法提供了一种求解复杂系统问题的通用框架，它遗传算法提供了一种求解复杂
4、系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以GA在函数优化，组合优化、生产调度问题、自动控制、机器人在函数优化，组合优化、生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。从遗传算法的理论和技术两方面概述目前的研究现状；泛的运用。从遗传算法的理论和技术两方面概述目前的研究现状；描述遗传算法的主要特点、基本原理；应用遗传算法来解决函数描述遗传算法的主要特点、基本原理；应用遗传算法来解决函数优化、组合优化等方
5、面的案例。优化、组合优化等方面的案例。 论文研究背景、目的与意义论文研究背景、目的与意义5优质课件6/20主要内容主要内容： 认识遗传算法的基本概念，掌握认识遗传算法的基本概念，掌握基本步骤。基本步骤。学习基本实现技术，学习基本实现技术， 应用遗传算应用遗传算法来解决函数优化问题。法来解决函数优化问题。论文研究背景、目的与意义论文研究背景、目的与意义6优质课件7/20遗传算法基本概念与原理遗传算法基本概念与原理 遗传算法是模拟达尔文的遗传选择和遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是自然淘汰的生物进化过程的计算模型，它是由美国由美国MichiganMichigan
6、大学的大学的J.HollandJ.Holland教授于教授于19751975年首先提出的遗传算法作为一种新的年首先提出的遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，强、适于并行处理及应用范围广等显著特点，奠定了它作为奠定了它作为2121世纪关键智能计算之一的地世纪关键智能计算之一的地位。位。7优质课件8/20遗传算法基本概念与原理遗传算法基本概念与原理 遗传算法的基本思想正是基于模仿生物遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程它把问题的参数用基界遗传学的遗传过程它把问题的参数用基因代表，把问
7、题的解用染色体代表（在计算因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体这个群体有不同染色体的个体组成的群体这个群体在问题特定的环境里生存竞争，适者有最好在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代后代随机化地继承的机会生存和产生后代后代随机化地继承了父代的最好特征，并也在生存环境的控制了父代的最好特征，并也在生存环境的控制支配下继续这一过程。支配下继续这一过程。8优质课件9/20遗传算法基本概念与原理遗传算法基本概念与原理序号遗传学概念遗传算法概念数学概念1 1个体个体要处理的基本对
8、象、结构要处理的基本对象、结构也就是可行解也就是可行解2 2群体群体个体的集合个体的集合被选定的一组可行解被选定的一组可行解3 3染色体染色体个体的表现形式个体的表现形式可行解的编码可行解的编码4 4基因基因染色体中的元素染色体中的元素编码中的元素编码中的元素5 5基因位基因位某一基因在染色体中的位置某一基因在染色体中的位置元素在编码中的位置元素在编码中的位置6 6适应值适应值个体对于环境的适应程度，或在环境压力下的个体对于环境的适应程度，或在环境压力下的生存能力生存能力可行解所对应的适应函数值可行解所对应的适应函数值7 7种群种群被选定的一组染色体或个体被选定的一组染色体或个体根据入选概率定
9、出的一组可行解根据入选概率定出的一组可行解8 8选择选择从群体中选择优胜的个体，淘汰劣质个体的操从群体中选择优胜的个体，淘汰劣质个体的操作作保留或复制适应值大的可行解，去掉小的保留或复制适应值大的可行解，去掉小的可行解可行解9 9交叉交叉一组染色体上对应基因段的交换一组染色体上对应基因段的交换根据交叉原则产生的一组新解根据交叉原则产生的一组新解1010交叉概率交叉概率染色体对应基因段交换的概率（可能性大小）染色体对应基因段交换的概率（可能性大小）闭区间闭区间0,10,1上的一个值，一般为上的一个值，一般为0.650.900.650.901111变异变异染色体水平上基因变化染色体水平上基因变化编
10、码的某些元素被改变编码的某些元素被改变1212变异概率变异概率染色体上基因变化的概率（可能性大小）染色体上基因变化的概率（可能性大小）开区间开区间(0,1)(0,1)内的一个值内的一个值, , 一般为一般为0.0010.010.0010.011313进化、进化、适者生存适者生存个体进行优胜劣汰的进化，一代又一代地优化个体进行优胜劣汰的进化，一代又一代地优化目标函数取到最大值，最优的可行解目标函数取到最大值，最优的可行解9优质课件10/20遗传算法基本概念与原理遗传算法基本概念与原理1. 1. 个体与种群个体与种群 个体就是模拟生物个体而对问题中的对象个体就是模拟生物个体而对问题中的对象（一般就
11、是问题的解）的一种称呼，一个个（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。体也就是搜索空间中的一个点。 种群种群(population)(population)就是模拟生物种群而由就是模拟生物种群而由若干个体组成的群体若干个体组成的群体, , 它一般是整个搜索空它一般是整个搜索空间的一个很小的子集。间的一个很小的子集。10优质课件11/20遗传算法基本概念与原理遗传算法基本概念与原理2. 2. 适应度与适应度函数适应度与适应度函数 适应度适应度(fitness)(fitness)就是借鉴生物个体对环就是借鉴生物个体对环境的适应程度境的适应程度, ,而对问题中的个体对象所设
12、而对问题中的个体对象所设计的表征其优劣的一种测度。计的表征其优劣的一种测度。 适应度函数适应度函数(fitness function)(fitness function)就是问题就是问题中的全体个体与其适应度之间的一个对应关中的全体个体与其适应度之间的一个对应关系该函数就是遗传算法中指导搜索的评价函系该函数就是遗传算法中指导搜索的评价函数。数。 11优质课件12/20遗传算法基本概念与原理遗传算法基本概念与原理3. 3. 染色体与基因染色体与基因 染色体（染色体（chromosomechromosome）就是问题中个体）就是问题中个体的某种字符串形式的编码表示。字符串中的的某种字符串形式的编码
13、表示。字符串中的字符也就称为基因（字符也就称为基因（genegene）。）。例如：例如： 个体个体 染色体染色体 9 - 1001 9 - 1001 （2 2，5 5，6 6）- 010 101 110- 010 101 11012优质课件13/20遗传算法基本概念与原理遗传算法基本概念与原理4. 4. 遗传操作遗传操作 亦称遗传算子亦称遗传算子(genetic operator)(genetic operator)，就，就是关于染色体的运算。遗传算法中有三种遗是关于染色体的运算。遗传算法中有三种遗传操作传操作: : 选择选择- -复制复制, ,交叉交叉( (亦称交换、交配亦称交换、交配或杂交
14、或杂交) ), ,变异变异( (亦称突变亦称突变) )。13优质课件14/20 选选择择- -复复制制通通常常做做法法是是：对对于于一一个个规规模模为为N N的的种种群群S S, ,按按每每个个染染色色体体x xi iS S的的选选择择概概率率P P( (x xi i) )所所决决定定的的选选中中机机会会, , 分分N N次次从从S S中中随随机机选选定定N N个个染染色色体体, , 并进行复制。并进行复制。 这里的选择概率这里的选择概率P P( (x xi i) )的计算公式的计算公式为为遗传算法基本概念与原理遗传算法基本概念与原理14优质课件15/20交叉交叉 就是互换两个染色体某些位上的
15、基因。就是互换两个染色体某些位上的基因。 s s1 1=01000101, =01000101, s s2 2=10011011=10011011 可以看做是原染色体可以看做是原染色体s s1 1和和s s2 2的子代染色体。的子代染色体。 例如例如, , 设染色体设染色体 s s1 1=01001011, =01001011, s s2 2=10010101, =10010101, 交换其后交换其后4 4位基因位基因, , 即即遗传算法基本概念与原理遗传算法基本概念与原理15优质课件16/20 变异变异 就是改变染色体某个就是改变染色体某个( (些些) )位上的基因。位上的基因。 例如例如,
16、 ,设染色体设染色体 s s=11001101=11001101将其第三位上的将其第三位上的0 0变为变为1, 1, 即即 s s=11=110 001101 01101 11111 101101= 01101= s s。 s s也可以看做是原染色体也可以看做是原染色体s s的子代染色体。的子代染色体。遗传算法基本概念与原理遗传算法基本概念与原理16优质课件17/20 遗传算法基本流程框图生成初始种群计算适应度选择-复制交叉变异生成新一代种群终止 ?结束遗传算法基本概念与原理遗传算法基本概念与原理17优质课件18/20基本遗传算法步骤基本遗传算法步骤 步步1 1 在搜索空间在搜索空间U U上定
17、义一个适应度函数上定义一个适应度函数f f( (x x) )，给定种群规模，给定种群规模N N，交叉率，交叉率P Pc c和变异率和变异率P Pm m，代数，代数T T； 步步2 2 随机产生随机产生U U中的中的N N个个体个个体s s1, 1, s s2, 2, , , s sN N，组成初始种群，组成初始种群S S=s s1, 1, s s2, 2, , , s sNN，置代数计，置代数计数器数器t t=1=1； 步步3 3 计算计算S S中每个个体的适应度中每个个体的适应度f(f(x x) ) ； 步步4 4 若终止条件满足，则取若终止条件满足，则取S S中适应度最大的中适应度最大的个
18、体作为所求结果，算法结束。个体作为所求结果，算法结束。 遗传算法基本概念与原理遗传算法基本概念与原理18优质课件19/20 步步5 5 按选择概率按选择概率P P( (x xi i) )所决定的选中机会，每所决定的选中机会，每次从次从S S中随机选定中随机选定1 1个个体并将其染色体复制，共个个体并将其染色体复制，共做做N N次，然后将复制所得的次，然后将复制所得的N N个染色体组成群体个染色体组成群体S S1 1； 步步6 6 按交叉率按交叉率P Pc c所决定的参加交叉的染色体所决定的参加交叉的染色体数数c c，从，从S S1 1中随机确定中随机确定c c个染色体，配对进行交叉个染色体，配
19、对进行交叉操作，并用产生的新染色体代替原染色体，得群操作，并用产生的新染色体代替原染色体，得群体体S S2 2；遗传算法基本概念与原理遗传算法基本概念与原理19优质课件20/20遗传算法的实现技术遗传算法的实现技术 编码方法编码方法 : : 二进制编码方法是遗传算法中最常用的一种二进制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符号集是由二进制符号编码方法，它使用的编码符号集是由二进制符号0 0和和1 1组成的二值符号集，它所构成的个体基因型是组成的二值符号集，它所构成的个体基因型是一个二进制编码符号串。一个二进制编码符号串。 格雷码，连续的两个整数所对应的编码值之格雷码，连续的两个
20、整数所对应的编码值之间只有一个码位不相同。格雷码有这样一个特点：间只有一个码位不相同。格雷码有这样一个特点：任意两个整数的差是这两个整数所对应的海明距任意两个整数的差是这两个整数所对应的海明距离。这个特点是遗传算法中使用格雷码进行个体离。这个特点是遗传算法中使用格雷码进行个体编码的主要原因。编码的主要原因。20优质课件21/20遗传算法的实现技术遗传算法的实现技术 符点数编码方法符点数编码方法: :指个体的每个基因值用某一指个体的每个基因值用某一范围内的一个浮点数来表示个体的编码长度等于范围内的一个浮点数来表示个体的编码长度等于其决策变量的个数，个体变量的长度等于去决策其决策变量的个数，个体变
21、量的长度等于去决策变量的真实值，所以也叫真值编码方法变量的真实值，所以也叫真值编码方法 . . 符号编码方法是指个体染色体编码串中的基符号编码方法是指个体染色体编码串中的基因值取自一个无数值含义，而只有代码含义的符因值取自一个无数值含义，而只有代码含义的符号集。这个符号集可以是一个字母表，如号集。这个符号集可以是一个字母表，如 A, A, B, C, D, B, C, D, ；也可以是一个数宇序号表，如；也可以是一个数宇序号表，如 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ；还可以是一个代码表，如；还可以是一个代码表，如 Al, A2, A3, A4, A5, Al, A2,
22、 A3, A4, A5, 等等。等等。 21优质课件22/20遗传算法的实现技术遗传算法的实现技术适应度函数适应度函数 : :适应度较高的个体遗传到下一代的概率就相对大一适应度较高的个体遗传到下一代的概率就相对大一些；而适应度较低的个体遗传到下一代的概率就些；而适应度较低的个体遗传到下一代的概率就相对较小一些。度量个体适应度的函数就称为适相对较小一些。度量个体适应度的函数就称为适应度函数。应度函数。根据个体的适应值，就可决定在此环境下的生存能根据个体的适应值，就可决定在此环境下的生存能力。个体适应度大小决定该个体被遗传到下一代力。个体适应度大小决定该个体被遗传到下一代群体中的概率。遗传算法仅使
23、用所求问题的目标群体中的概率。遗传算法仅使用所求问题的目标函数值就可以得到下一步的有关搜索信息。目标函数值就可以得到下一步的有关搜索信息。目标函数值的使用是通过评价个体适应度来体现的。函数值的使用是通过评价个体适应度来体现的。22优质课件23/20遗传算法的实现技术遗传算法的实现技术选择算子选择算子 : : 选择算子（也叫复制算子选择算子（也叫复制算子Reproduction Reproduction OperatorOperator）来对群体中的个体进行优胜劣汰）来对群体中的个体进行优胜劣汰操作：适应度较高的个体被遗传到下一代的操作：适应度较高的个体被遗传到下一代的概率较大；适应度较低的个体
24、被遗传到下一概率较大；适应度较低的个体被遗传到下一代的概率较小。选择操作建立在对个体的适代的概率较小。选择操作建立在对个体的适应度进行评价的基础上。选择的主要目的为应度进行评价的基础上。选择的主要目的为了避免基因缺失、提高全局收敛性和计算效了避免基因缺失、提高全局收敛性和计算效率。率。23优质课件24/20遗传算法的实现技术遗传算法的实现技术轮盘赌选择方法的实现步骤：轮盘赌选择方法的实现步骤：（1 1） 计算群体中所有个体的适应度函数值计算群体中所有个体的适应度函数值（需要解码）；（需要解码）；（2 2） 利用比例选择算子的公式，计算每个利用比例选择算子的公式，计算每个个体被选中遗传到下一代群
25、体的概率；个体被选中遗传到下一代群体的概率；（3 3） 采用模拟赌盘操作（即生成采用模拟赌盘操作（即生成0 0到到1 1之间之间的随机数与每个个体遗传到下一代群体的概的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下率进行匹配）来确定各个个体是否遗传到下一代群体中。一代群体中。24优质课件25/20遗传算法的实现技术遗传算法的实现技术最优保存策略选择：最优保存策略选择： 在遗传算法的运行过程中，通过对个在遗传算法的运行过程中，通过对个体进行交叉、变异等遗传操作而不断产生新体进行交叉、变异等遗传操作而不断产生新的个体，虽然随着群体的进化过程会产生出的个体，虽然随着群体的
26、进化过程会产生出越来越多的优良个体，但由于遗传操作的随越来越多的优良个体，但由于遗传操作的随机性，它们也有可能破坏掉当前群体中适应机性，它们也有可能破坏掉当前群体中适应度最好的个体。我们希望适应度最好的个体度最好的个体。我们希望适应度最好的个体要尽可能的保存到下一代群体中，为达到这要尽可能的保存到下一代群体中，为达到这个目的我们使用最优保存策略进化模型。个目的我们使用最优保存策略进化模型。25优质课件26/20遗传算法的实现技术遗传算法的实现技术具体操作过程：具体操作过程： （1 1）找出当前群体中适应度最高的个体）找出当前群体中适应度最高的个体和适应度最低的个体。和适应度最低的个体。 （2
27、2）若当前群体中最佳个体的适应度比）若当前群体中最佳个体的适应度比总的迄今为止的最好个体的适应度还高，则总的迄今为止的最好个体的适应度还高，则以当前种群中的最佳个体作为新的迄今为止以当前种群中的最佳个体作为新的迄今为止的最好个体。的最好个体。 （3 3）用迄今为止的最好个体替换掉当）用迄今为止的最好个体替换掉当前群体中的最差个体。前群体中的最差个体。26优质课件27/20遗传算法的实现技术遗传算法的实现技术交叉算子交叉算子 : : 所谓交叉运算，是指对两个相互配对的所谓交叉运算，是指对两个相互配对的染色体依据交叉概率染色体依据交叉概率 P Pc c 按某种方式相互交按某种方式相互交换其部分基因
28、，从而形成两个新的个体。交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。生新个体的主要方法。 SGASGA中交叉算子采用中交叉算子采用单点交叉算子。单点交叉算子。 27优质课件28/20遗传算法的实现技术遗传算法的实现技术单点交叉运算单点交叉运算交叉前：交叉前：00000|0111000000001000000000|0111000000001000011100|0000011111100010111100|000001111110
29、00101交叉后：交叉后：00000|0000011111100010100000|0000011111100010111100|0111000000001000011100|0111000000001000028优质课件29/20遗传算法的实现技术遗传算法的实现技术变异算子：变异算子： 所谓变异运算，是指依据变异概率所谓变异运算，是指依据变异概率 P Pm m 将个体将个体编码串中的某些基因值用其它基因值来替换，从编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局产生新个体的
30、辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。全局搜索和局部搜索。 SGASGA中变异算子采用基本中变异算子采用基本位变异算子。位变异算子。 29优质课件30/20Matlab遗传算法GUI求函数最大值函数：函数：30优质课件31/20Matlab遗传算法GUI求函数最大值步骤：步骤： 首先编写目标函数的首先编写目标函数的M M文件并以文件名文件并以文件名myfunmyfun存盘。存盘。 function y=myfun(x
31、) function y=myfun(x) if x(:,1)=-1 if x(:,1)=-1 y=-(x*sin(10*pi*x)+2.0); y=-(x*sin(10*pi*x)+2.0); else else y=0 y=0 end end 然后，在然后，在MATLABMATLAB工作窗口工作窗口 gatool gatool 打开遗传算法的打开遗传算法的GUIGUI，在，在“fitness functionfitness function”窗口输入窗口输入myfunmyfun，在，在“number of variablesnumber of variables”窗口输入变量数目窗口输入变
32、量数目1 1。然后，单击。然后，单击“startstart”运行遗传算法，得到如下图结果。运行遗传算法，得到如下图结果。31优质课件32/2032优质课件33/20结 论遗传算法的特点遗传算法的特点（1 1）群体搜索，易于并行化处理；）群体搜索，易于并行化处理； （2 2）不是盲目穷举，而是启发式搜索；）不是盲目穷举，而是启发式搜索；（3 3）适应度函数不受连续、可微等条件的约）适应度函数不受连续、可微等条件的约束，适用范围很广。束，适用范围很广。33优质课件34/20结 论遗传算法的应用领域遗传算法的应用领域（1 1）组合优化）组合优化 （2 2）函数优化）函数优化 （3 3）自动控制）自动
33、控制 （4 4）生产调度）生产调度 （5 5）图像处理）图像处理 （6 6）机器学习）机器学习 （7 7）人工生命）人工生命 （8 8）数据挖掘）数据挖掘34优质课件35/20结 论 先从遗传算法的基本概念入手，对个体与种先从遗传算法的基本概念入手，对个体与种群、适应度与适应度函数、染色体与基因、选择、群、适应度与适应度函数、染色体与基因、选择、交叉、变异等概念充分理解，通过对基本遗传算交叉、变异等概念充分理解，通过对基本遗传算法基本原理与步骤掌握，进而实现基本遗传算法，法基本原理与步骤掌握，进而实现基本遗传算法，然后再研究一些遗传算法的基本实现技术，如编然后再研究一些遗传算法的基本实现技术，如编码方法，适应度函数，选择算子，交叉算子，变码方法，适应度函数，选择算子，交叉算子，变异算子等，然后手工模拟遗传算法的计算过程，异算子等，然后手工模拟遗传算法的计算过程，从而更加深刻的了解其原理。最后再简单介绍一从而更加深刻的了解其原理。最后再简单介绍一下下GAGA工具箱，通过一维变量的函数优化问题来说工具箱，通过一维变量的函数优化问题来说明用明用MatlabMatlab程序来实现遗传算法对函数的优化工程序来实现遗传算法对函数的优化工程。程。35优质课件36/20谢谢大家！谢谢大家！谢谢各位老师谢谢各位老师给予指导！给予指导！36优质课件
