第五章 计算智能2课件.ppt

第5章 计算智能;　　　生物染色体用数学方式或计算机方式来体现就是一串数码，仍叫染色体，有时也叫个体；每个染色体的适应能力用某一个数值来衡量；染色体的选择或淘汰则按所面对的问题是求最大还是最小来进行。 　　　20世纪60年代以来，如何模仿生物进化来建立功能强大的算法，进而将它们运用于复杂的优化问题，逐渐成为一个研究热点。进化计算(evolutionary computation)正是在这一背景下蕴育而生。进化计算包括遗传算法(genetic algorithms，GA)，进化策略、进化编程和遗传编程。 　　　人类不满足于模仿生物进化行为，希望能够建立具有自然生命特征的人造生命和人造生命系统。对人工生命的研究，是人工智能和计算智能的一个新的研究热点。 ;5.4 遗传算法;　　　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的目标是路径总长度为最短，路径总长度的倒数就可以为TSP的适应度函数： 　其中　　　　，　　　　 表示两城市间的距离（路径长度）。 　　　适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距，一个染色体与问题的最优解染色体之间的差距小，则对应的适应度函数值之差就小，否则就大。;　　　3.遗传操作 　　　简单遗传算法的遗传操作主要有三种:选择、交叉、变异。改进的遗传算法大量扩充了遗传操作，以达到更高的效率。 　　　选择操作也叫复制操作，根据个体的适应度函数值所度量的优、劣程度决定它在下一代是否被淘汰。一般，选择将使适应度较大(优良)个体有较大的存在机会，而适应度较小（低劣）的个体继续存在的机会也较小。令　表示种群中第　个染色体的适应度值，　　表示群体的适应度值总和，它产生后代的能力正好为其适应度值所占份额　　　　。假设当前群体与下一代群体个数均维持在　，则个体　在下一代中再出现的个数为　　　　　。有的选择操作采用赌轮机制，每一个体对应旋转盘中一个以圆点为中心的扇形区域： 　　　　　，随机产生　　　 之间的值，根据该值所对应的区域，再生了一个对应个体，直到产生的个体数达到所需要的种群数目为止，就产生了下一代的种群。 ;　　　交叉操作通常采用的是单点位置交换，设串长为L，随机选择一个交换点（对应于1到L－1的位置序号），紧接着两串在交换点右边的子串互换，产生两个新串。 　　　假设有如下八