上海大学毕业设计(论文)
Holland的遗产算法，通常称为简单遗传算法。操作的简单和作用的强大是遗传算法的两大主要特点。一般得遗传算法都包含选择（复制）、交叉和变异三种基本操作。
1）选择
选择就是根据每个个体的适应度值，按照一定的规则从当前种群中选出优良个体，使它们有机会作为父代为下一代繁殖子孙。
遗传算法的每一代都是从选择开始的。常用的选择方法有：轮盘赌选择法（适应度比例法）、精英选择法、稳态复制法、排序选择法、联赛选择法等。其中轮盘赌选择法较为简单且常用。
对轮盘赌选择，每个个体进入下一代的概率就等于它的适应度值与整个种群中个体适应度值和的比例，适应度值越高，被选中的可能性就越大，进入下一代的概率就越大。每个个体就像圆盘中的一个扇形部分，扇面的角度和个体的适应度值成正比，随机拨动圆盘，当圆盘停止转动时指针所在扇面对应的个体被选中，轮盘赌的选择方法由此得名。一个个体被选择的概率由下式给出：
F(xi)?f(xi)Nind?i?1f(xi)
式中，
f(xi)是个体i的适应度，
xF(xi)是这个个体被选择的概率。
图3.3所示为轮盘赌选择示意图。
31
上海大学毕业设计(论文)
2）交叉
交叉就是将两个互相配对的个体按照某种方法相互交换部分染色体位串，从而形成两个新的个体。交叉操作是产生新个体的主要方法，它使GA的搜索能力得以本质提高，所以它在GA中起着核心作用。
基本的交叉操作分两步实现。在由等待配对的位串构成的匹配池中，第一步是将新复制产生的位串个体随机两两配对；第二步是随机地选择交叉点，对匹配的位串进行交叉繁殖，产生一对新的位串。目前，交叉的方法有很多，对于二进制编码而言，交叉都需要第一步，根据交叉点的不同，交叉方法又可分为单点交叉、两点交叉、多点交叉等。
3）变异
变异操作就是根据变异概率随机改变被选择染色体上一个或几个基因，以保持群体的多样性。变异可以起到恢复位串字符多样性的作用，并能适当地提高遗传算法的搜索效率。常见的变异方法有：点变异、插入变异、均匀变异、边界变异、非均匀变异等。
5、运行参数
遗传算法中的运行参数选择非常关键，运行参数的不同选取会对遗传算法的性能产生较大的影响，影响到整个算法的收敛性。这些参数包括种群规模Nind、个体编码长度Lind、交叉概率Pc、变异概率Pm、终止条件等。
种群规模Nind的大小直接影响到遗传算法的收敛性或计算效率。规模过大，会造成计算速度降低；规模过小，容易收敛到局部最优解。种群规模可以根据实际情况在1～200之间选定。
二进制编码位串长度Lind反映解的精确度水平或者个体决策变量的范围。 交叉概率Pc始终控制着遗传算法中起主导地位的交叉算子。不适合的交叉概率Pc会导致意想不到的后果。交叉概率Pc控制着交叉操作被使用的频度。交叉概率Pc较大，可使各代充分交叉，但群体中的优良模式遭到破坏的可能性增大，以致产生较大的代沟，从而使搜索走向随机化；交叉概率Pc越低，产生的代沟就越小，这样将保持一个连续的解空间，使找到全局最优解的可能性增
32
上海大学毕业设计(论文)
大，但进化的速度就越慢；若交叉概率Pc太低，就会使得更多的个体直接复制到下一代，遗传搜索可能陷入停滞状态。一般建议Pc取值范围是0.4～0.99。
变异运算是对遗传算法的改进，对交叉过程中可能丢失的某种基因进行修复和补充，也可防止遗传算法尽快收敛到局部最优解。变异概率Pm控制着变异操作被使用的频率。变异概率Pm取值较大时，虽然能够产生较多的个体，增加了群体的多样性，但也可能破坏很多好的模式，使遗传算法的性能近似于随机搜索算法的性能；若变异概率Pm取值太小，则变异操作产生新个体和抑制早熟现象的能力就会较差。一般建议Pm取值范围是0.0001～0.1。
终止的常用方法是采用达到预先设定的代数和根据问题定义测试种群中最优个体的性能。
3.4 遗传算法的模式定理
从上一节遗传算法的原理中，我们可以知道问题的性能是朝着不断改进的方向发展的。但是我们怎么知道对某一问题使用遗传算法会得到优化或接近优化的解呢？或者说，在仅仅利用适配值进行的搜索过程中，遗传算法到底是利用了包括在种群中多数位串及其相应的目标函数中的什么信息来引导和改善它的搜索呢？本节将以二进制串作为编码方式来介绍遗传算法的理论基础——模式定理(Pattern Theorem)。正是模式定理保证了较优的模式（遗传算法的较优解）的样本呈指数级增长，从而满足了寻找最优解的必要性。
所谓模式（Schemata)，就是一个描述种群中在位串的某些确定位置上具有相似性的位串子集的相似性模板。
为了描述一个模式，在用以表示位串的两个字符的字母表{0，1}中加入一个通配符“*”，就构成了一个表示模式用的三个字符的字母表{0，1，*}。用三元素字母表{0，1，*}可以构造出任意一种模式。模式和特定位串相匹配则是指：模式中的1与位串中的1相匹配，模式中的0与位串中的0相匹配，模式中的“*”可以匹配位串中的0或1。
引入模式后，我们看到一个串实际上隐含着多个模式（长度为n的串隐含着2个模式），一个模式可以隐含在多个串中，不同的串之间通过模式而相互联系。遗传算法中串的运算实质上是模式的运算。因此，通过分析模式在遗传操
n 33
上海大学毕业设计(论文)
作下的变化，就可以了解什么性质被延续，什么性质被丢弃，从而把握遗传算法的实质，这正是模式定理所揭示的内容。
在介绍模式定理前，我们先引入模式的阶数和定义距，它们描述了模式的基本性质。
所谓模式的阶数，就是一个模式中确定位置（0或1，*表示非确定性）的个数。模式的阶数越低，模式的样本数就越多，而确定性越低。
所谓模式的定义距，就是一个模式的第一个确定性位置和最后一个确定性位置之间的距离。模式的定义距表示模式的长短。
模式定理 在遗传算子选择、交叉和变异的作用下，具有阶数低、长度短、平均适应度高于群体平均适应度的模式在子代中将以指数级增长。
统计学的研究表明：在随机搜索中，要获得最优的可行解，则必须保证较优解的样本呈指数级增长，而模式定理保证了较优的模式（GA的较优解）的样本呈指数级增长，从而给出了遗传算法的理论基础。另外，由于遗传算法总能以一定的概率遍历到解空间的每一个部分，因此在选择算子的条件下总能得到问题的最优解。
3.5 小结
遗传算法是仿照生物进化自然选择过程中所表现出来的优化规律和方法，
解决高度复杂工程问题的一种计算方法。本章首先介绍了遗传算法的发展史、基本概念、研究方向等情况；接着，重点介绍了遗传算法的工作原理，并对其工作的各个步骤都做了简要论述；最后，阐明了遗传算法有效性的理论基础——模式定理。本章对遗传算法的详细阐述，将为后续章节提供重要的理论指导。
34
上海大学毕业设计(论文)
第四章 遗传算法工具箱
4.1 引言
根据前一章介绍的有关遗传算法的知识，可以知道遗传算法的核心在于初始群体的生成、操作算子的实现以及个体适配值与优化问题性能指标间的映射等，若要通过计算机实现遗传算法，这一个个核心步骤都需要繁琐的程序来支撑。对于遗传算法初学者，要做到遗传算法的计算机实现显得尤为困难。
MATLAB是国内最流行的科学计算软件，它对问题用M文件编码，其先进的数据分析、可视化工具、特殊目的的应用领域工具箱为使用者研究遗传算法提供了良好的环境。MATLAB遗传算法工具箱为遗传算法从业者和研究人员提供了广泛多样的有用函数，它为遗传算法的MATLAB实现带来了极大的便利。 遗憾的是，MATLAB环境没有自带的遗传算法工具箱，用户只能使用第三方的工具箱。虽然MATLAB第三方遗传算法工具箱并不是很多，但包含的函数并不统一，本节将详细介绍英国谢菲尔德大学开发的遗传算法工具箱。
4.2 遗传算法工具箱结构
遗传算法工具箱归纳了遗传算法及其各种改进算法的相同之处，建立了一个统一的遗传算法基本流程框架，并依据这个框架搭建了自身的结构，下图4.1即为遗传算法基本流程框架图。
35