遗传算法课件.ppt

1、遗传算法，遗传算法，1，概述2，遗传算法说明3，TSP中的遗传算法应用节目4，选择机制5，遗传算法理论基础6，计算案例，1，智能最优化算法，智能最优化算法，这是一种全局优化性能，通用性，适合并行处理的算法，这种算法通常基于严密的理论基础不是单纯依靠专家经验的牙齿，而是在理论上的一定时间内找到最佳解决方案或近似。由于常用智能最优化算法(1)遗传算法(GA) (2)模拟退火算法(SA) (3)禁忌搜寻演算法(tabusa)搜索空间可以扩展到整个问题空间，因此提供了全局最优化性能。遗传算法起源，遗传算法是美国J. Holland教授于1975年在他的专着自然界和人工系统的适应性中首先提出的，借用生物

2、系统自然选择和自然遗传机制的随机化搜寻演算法。20世纪70年代，德琼基于遗传算法的思想在计算机上进行了大量纯数值函数最优化计算实验。在一系列研究的基础上，20世纪80年代，戈德堡进行了总结，形成了遗传算法基本框架。遗传算法搜索机制、遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象、每次迭代中保持候选解决方案集、根据特定指标从解决方案组中选择更好的实体、使用遗传运算符(选择、交叉和变异)组合这些实体、生成下一代候选解决方案组、重复牙齿过程，直到满足收敛指标、1.1遗传算法汇总函数最大值在遗传算法过程中，N维决策矢量显示为由N个符号组成的符号字符串X。将每一个都视为一个基因，所有

3、可能的值都称为等位基因()。所以X可以看作是由N个基因组成的染色体。染色体的长度可以固定，也可以变化。等位基因可以是整数集、一定范围的实数值或符号。最简单的等位基因由两个整数(0和1)组成，相应的染色体可以用一个二进制符号字符串表示。牙齿代码形成的数组形式X是个人的基因型，相应的X值是个人的表现型。染色体X也称为个体X，对于每个个体X，必须根据一定的规则确定适合性。个人的适应性越接近该个人表现型X的目标函数值和相关，X目标函数的最佳优点，适应性越大。相反，适应度越低。遗传算法期间决策变量x配置问题的解决空间。问题的最佳搜索是通过对染色体X的搜索过程完成的，因此所有染色体X构成了问题的搜索空间。

4、生物的进化以群体为主体。等效的遗传算法操作数是由M个人组成的集合，称为组。与生物世代的自然进化过程一样，遗传算法运算也是一个重复的迭代过程，T世代群体以P(t)书写，经过世代遗传和进化，得到T世代群体，并以P(t 1)书写。牙齿群体不断经过遗传和进化工作，每次都按照优胜劣汰的规则，将适应性强的个体遗传给下一代更多，最终在群体中得到优秀的个体X，相应的表型X将达到或接近问题的最优解。生物的进化过程主要通过染色体间的交叉和染色体的变异来实现。遗传算法中的最佳搜索过程也模仿生物的牙齿进化过程，利用所谓的遗传算子作用于群体P(t)，进行以下遗传操作以获得下一代群体P(t 1)。选择(selection

5、):根据个人的适合性，根据特定规则或方法选择从T代组P(t)遗传到下一代P(t 1)的优秀个人。“相交”(crossover):随机配对组P(t)中的每个对象，并以特定概率(交叉概率，称为crossover rate)交换每个对象之间的部分染色体。突变：以特定概率(变异概率，称为mutation rate)为群体P(t)的每个人，将一个或一些基因座的基因值更改为另一个等位基因值。1.2遗传算法功能遗传算法是一种可用于复杂系统最优化计算的鲁棒搜寻演算法，与其他一些最优化算法相比，主要有以下几个茄子特征牙齿：遗传算法以决策变量的编码为操作数。传统的最优化算法经常直接使用决策变量的实际值本身来执行最

6、优化计算，但是遗传算法不是决策变量的值，而是以决策变量的某种形式编码为操作数，便于引入和应用遗传操作运算符。直接使用目标遗传算法值作为搜索信息。传统的算法优化往往需要目标函数值以及目标函数派生等其他信息。这样对于很多目标函数，不能诱导或难以诱导的函数，遗传算法牙齿比较方便。遗传算法并发解决方案空间多点搜索。现有最优化算法通常从解决空间的初始点开始搜索，因此很容易陷入局部极点。遗传算法进行集体搜索，在搜索过程中引入遗传运算，使群体继续进化。这些是遗传算法特有的隐式并行性。遗传算法使用概率搜索技术。遗传算法(自适应概率搜索技术)以概率方式执行选择、交叉、变异等操作，提高了搜索过程的灵活性。实践和理

7、论都证明了在一定条件下，遗传算法总是以概率1收敛问题的最优解。1.3遗传算法发展20世纪60年代，美国密植安大学霍兰教授和学生受生物模拟技术的启发，基于适合复杂系统计算优化的生物遗传和进化机制的自适应概率最优化技术-遗传算法。以下是一些主要人物在遗传算法发展过程中做出的几个茄子主要贡献。J.H. Holland在20世纪60年代提出，Holland能够认识到生物的遗传和自然进化现象与人工适应系统的相似性，利用生物遗传和进化的思想研究自然和人工适应系统的生成与环境的关系，研究和设计人工适应系统时参考生物遗传的机制，以集体的方法进行适应性搜索。70年代霍兰德提出了遗传算法基本定理“图式定理”(Sc

8、hema Theorem)，为遗传算法理论奠定了基础。1975年，Holland宣布了第一个描述遗传算法和人工适应系统的专业自然系统和人工系统的适应性(adaptation in natural and artificial systems)。20世纪80年代，Holland实施了第一个基于遗传算法的机器学习系统分类器系统，创造了基于遗传算法学习的新概念，建立了分类器系统的完整框架。J.D.Bagley 1967年，Holland的学生Bagley在博士论文中首次提出了“遗传算法”一词，并发表了遗传算法应用领域的第一篇论文。他发展了克隆、交叉、变异、显性、逆位等遗传算子，在个人编码中使用了两倍

9、的编码方法。它们类似于当前遗传算法中使用的算子和方法。他还敏锐地认识到在遗传算法执行的不同阶段可以徐璐使用不同的选择率，有助于防止遗传算法早熟现象，创立了自适应遗传算法概念。K . A.De Jong 1975年，De Jong在博士论文中结合模式定理，进行了大量纯数值函数最优化计算实验，建立了遗传算法工作框架，得出了一些茄子重要和指导性的结论。他在大多数最优化问题上建立了相对合适的遗传算法参数和著名的De Jong 5函数测试平台，定义了用于评估遗传算法性能的在线和离线指标。d . j . Goldberg 1989年Goldberg出版了专着搜索、最优化、机器学习遗传算法等。牙齿图书系统总

10、结了遗传算法的主要研究成果，全面论述了遗传算法的基本原理及其应用。L.Davis 1991年，Davis编辑出版了一本遗传算法手册，其中包含科学计算、工程技术和社会经济中的许多遗传算法应用实例。牙齿书在宣传和普及遗传算法应用方面起到了重要的地图作用。J.R.Koza 1992年，Koza应用于遗传算法计算机程序最优化设计和自动生成，提出了遗传编程概念。Koza已成功地将建议的遗传编程方法应用于人工智能、机器学习、符号处理等。1.4遗传算法应用节目遗传算法为解决复杂的系统最优化问题提供了一个通用框架。不依赖于问题的具体领域，对问题种类的鲁棒牙齿很强，因此广泛应用于许多学科。以下是几个茄子遗传算法

11、的主要应用领域。函数最优化。函数优化是遗传算法经典应用领域，也是遗传算法性能测试评估的典型例子。对于一些非线性、多模型、多目标函数最优化问题，其他最优化方法很难解决，但遗传算法时很容易取得好结果。组合优化。实践证明，遗传算法是找到满意的组合优化问题解决方案的最佳工具之一，对遗传算法牙齿组合优化问题的NP整个问题非常有效。生产调度问题。生产日程问题很多情况下，设定的数学模型很难正确解决，即使在一些简化后可以解决，也太简单化了，解决的结果离实际太远了。(威廉莎士比亚、模板、生产日程表、生产日程表、生产日程表、生产日程表、生产日程表、生产日程表)现在遗传算法已成为解决复杂调度问题的有效工具。自动限制

12、。遗传算法已经在自动控制领域得到了很好的应用。例如基于遗传算法的模糊控制器的最优化设计、基于遗传算法的参数识别、基于遗传算法的模糊控制规则学习、遗传算法的人工神经网络的结构最优化设计和加权学习等。机器人学。机器人是复杂而难以准确建模的人工系统，遗传算法起源来自对人工应试系统的研究，因此机器人学自然成为遗传算法的重要应用领域。图像处理。图像处理是计算机视觉中重要的研究领域。在图像处理过程中，扫描、特征提取、图像分割等某些错误不可避免地会影响图像处理效果。最小化这些错误的方法是计算机视觉实用化的重要要求，在这些图像处理中，遗传算法在最优化计算中的应用很好。人工生命。人工生命是具有电脑机器等人工媒体

13、模拟或结构的自然生物系统特有行为的人工系统。自组织能力和自学能力是人工生命的两个茄子重要特征。人工生命和遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础。遗传编程。Koza开发了遗传编程概念，该概念使用LISP语言表示的编码方法，基于树结构的遗传操作自动生成计算机程序。机器学习。基于遗传算法的机器学习，应用于很多领域。例如，可以使用基于遗传算法的机器学习调整人工神经网络连接权，或用于设计人工神经网络的网络结构最优化。研究基本遗传算法构成，(1)编码(生成初始群体)，(2)适应函数，(3)遗传运算符(选择，交叉，变形)，(4)执行参数，编码生物遗传学，就像从染色体开

14、始一样，染色体是由基因排列的带子。SGA使用二进制字符串进行编码。函数最优化示例，x-1，2，6位小数精确解释的结果。对于牙齿样例的编码，SGA的间距长度为3，分析结果精确到6位小数，因此收购定义地块可以分为3106等分。另外，由于221 3106 222，对于牙齿，二进制编码长度必须至少为22位；对于牙齿，编码过程基本上是将间隔-1，2内的相应实数值转换为二进制字符串(b21b20b0)。多个术语，基因型：100010110101000111，表型：0.637197，编码，解码，个人(染色体)，基因，初始人口，SGA使用随机方法生成多个，初始人口中的个人数称为人口规模。适应度也是函数、遗传算

15、法、一个对象(解释)的好坏，适应度也是函数值，适应度函数值越大，解决的质量就越好。适应性函数是遗传算法进化过程的原动力和自然选择的唯一标准，其设计必须根据问题解决本身的要求来决定。选择算子，使用遗传算法选择运算实现对群体内个人的优胜劣汰。适应性高的个人遗传到下一代的概率很高。适应度低的个体遗传到下一代的可能性较小。选择工作的任务是以某种方式从上层集团中选择一些个人，继承到下一代。(约翰肯尼迪)SGA选择操作符使用轮盘选择方法。轮盘选择方法，轮盘选择，又称比例选择算子，它的基本思想是每个人选择的概率与大小数值成正比。如果将组大小N，个人I的适应性设置为Fi，则个人I遗传到下一代的概率是轮盘选择方

16、法的实现阶段，(1)计算组内所有个人的适合性函数值(需要解码)。(2)使用比例选择算子的公式计算每个个体遗传到下一代的概率。(3)使用模拟赌博光盘操作(即产生0到1之间的随机数，与每个人遗传到下一代的概率一致)来确定每个人是否遗传到下一代。利用轮盘选择方法的实施阶段，(1)计算组内所有个人的适合性函数值(需要解码)(2)使用比例选择算子的公式计算每个人遗传到下一代的概率。(3)使用模拟赌博光盘操作(即产生0到1之间的随机数，与每个人遗传到下一代的概率一致)来确定每个人是否遗传到下一代。交叉算子，所谓交叉运算是指在徐璐配对的两个染色体上，根据交叉概率Pc，以某种方式交换其基因的一部分，形成两个新的个体。交叉运算是遗传算法差异不同的进化算法的重要特征，在遗传算法中起着重要作用，是生产新个体的主要方法。SGA交集运算子使用单点交集运算子。单点交叉计算，交叉之前：00000 | 01110000000001000 11100 |