遗传算法论文答辩.ppt

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