第五章 计算能2.pptVIP

中南大学 智能系统与智能软件研究所 第5章 计算智能 　　生物种群的生存过程普遍遵循达尔文进化准则，群体中的个体根据对环境的适应能力而被大自然所选择或淘汰。进化过程中，物种每个个体的基本特征通过染色体中包含的特殊物质被后代所继承，通过个体之间的交叉、变异等遗传操作产生新的后代，只有适应自然环境的个体特征得以保存。这里，值得一提的还有孟德尔的遗传学说：认为遗传以密码方式存于细胞之中，并以基因形式包含在染色体内，每个基因有特殊的位置并控制物种的某种特征，并对环境具有某种适应性。 　　　生物染色体用数学方式或计算机方式来体现就是一串数码，仍叫染色体，有时也叫个体；每个染色体的适应能力用某一个数值来衡量；染色体的选择或淘汰则按所面对的问题是求最大还是最小来进行。 　　　20世纪60年代以来，如何模仿生物进化来建立功能强大的算法，进而将它们运用于复杂的优化问题，逐渐成为一个研究热点。进化计算(evolutionary computation)正是在这一背景下蕴育而生。进化计算包括遗传算法(genetic algorithms，GA)，进化策略、进化编程和遗传编程。 　　　人类不满足于模仿生物进化行为，希望能够建立具有自然生命特征的人造生命和人造生命系统。对人工生命的研究，是人工智能和计算智能的一个新的研究热点。 5.4 遗传算法 　　　遗传算法受进化论和孟德尔遗传学说启发，模仿生物遗传学和自然选择机理，通过人工方式构造的一类全局优化有哪些信誉好的足球投注网站算法，从某种程度上说它是对生物进化过程采取的数学仿真，是进化计算的一种重要形式。1975年霍兰德(Holland)在他的著作《Adaptation in Natural and Artificial Systems》中首次提出遗传算法，主要由他和他的学生发展起来，并且在实际中得到很好的应用。遗传算法本质上是不依赖于具体问题的直接有哪些信誉好的足球投注网站方法，已在模式识别、函数优化、机器学习、图形图像处理和机器人运动规划等领域有着十分广泛的应用。 　5.4.1 遗传算法的基本机理 　　　霍兰德遗传算法通常被称为“简单遗传算法”(SGA)，以此为主要讨论对象，加上适当改进，分析遗传算法的基本原理。 　　　1、编码与解码 　　　许多应用问题结构很复杂，但可以用简单的位串形式编码表示。将问题结构变换为位串形式编码表示的过程叫编码；而相反将位串形式编码表示变换为原问题结构的过程叫解码或译码。把位串形式的编码表示叫染色体，有时也叫个体。 　　　GA的算法的操作起点，首先在解空间中取一群点，作为遗传开始的第一代。每个点（基因）用一个二进制数字串表示，其优劣程度用一目标函数——适应度函数来衡量。 　　　遗传算法中最常用的编码方法是二进制编码。 　　　假设某参数的取值范围是［A，B］，A＜B。我们用长度为　的二进制编码串来表示该参数，将［A，B］分成 个子部分，记每一个等分的长度为　，则它能够产生　　个不同的编码，参数编码的对应关系如下： 　　…0　　　→A 　　…1　　　→A＋ 　　　…　…　…　…　…　…　…　…　… 　　…　　　 →B＝A＋ 　其中 　　　假设某一个体的二进制编码是： 　　　则上述二进制编码所对应的实数的解码公式为初始点加上单位区间长度乘以该点距初始点的区间个数： 　　 　　　二进制编码适宜机器表示和运算，其缺点是长度较大，对有些问题用其他编码方法可能更有利。其他编码方法主要有： 　　　浮点数编码，染色体用某一范围内的浮点数表示，对一些多维、高精度的连续函数优化问题用浮点数编码表示比较适用。 　　　格雷码是连续的两个整数所对应的编码值之间只有一个是不相同的，其余码位完全相同，可以减少染色体的差异。 　　　符号编码方法指染色体编码串中的基因取自一个无数值含义而只有代码含义的符号集（字母表、数字表或代码表等） 　　　举例：对于销售员旅行问题，可采用符号编码，按一条回路中城市的次序进行编码。例如码串134567829表示从城市1开始，依次是城市3,4，5,6，7,8，2,9，最后回到城市1。从城市　开始，依次经过城市　　　　　　，最后回到城市　，我们就有如下编码表示： 　　　由于是回路，记　　　　。它其实是1，……，　的一个循环排列。要注意　　　　　　　　是互不相同的。 　　　2.适应度函数 　　　为了体现染色体的适应能力，引入了对每一个染色体都能进行度量的函数，叫适应度函数。适应度函数表示了每个个体对环境的适应程度，适应度较大的个体有较高的概率得以生存，在一下代群体中再生。对优化问题，适应度函数就是目标函数。 TSP的目标是路径总长度为最短，路径总长度的倒数就可