上海大学毕业设计(论文)
表3.1 遗传学和遗传算法中基本用语对照表
遗传学 染色体（Chromosome) 基因（Gene） 等位基因（Allele） 基因座（Locus） 基因型（Genptype） 表现型（Phenotype） 个体（Individual） 适者生存 适应性（Fitness） 群体（Population） 复制（Reproduction） 交配（Crossover） 变异（Mutation） 遗传算法 解的编码（算法的操作对象） 解中每一分量 特性值 二进制串中位置 结构 参数集、候选解 解 在算法停止时，最优目标值的解有最大可能被留住 适应度函数值 选定的一组解 根据适应度函数值选取的一组解 通过交配产生一组新解的过程 编码的某一个分量发生变化的过程 3.2.5 遗传算法的研究方向
遗传算法是多学科结合和渗透的产物，它已经发展成一种自组织、自适应的综合技术，其研究方向主要有下述几个方面：
1．基础理论
遗传算法的数学理论并不完善，模式定理和隐性并行性存在不足。群体规模和遗传算子的控制参数选取也非常困难。另外，遗传算法还有一个过早收敛的问题，如何阻止过早收敛也是人们正在研究的问题之一。
2．分布并行遗传算法
遗传算法具有高度的并行性，许多研究人员都在探索在并行机和分布式系上高效执行遗传算法的策略。对分布遗传算法的研究表明，只要通过保持多个群体和恰当控制群体间的相互作用来模拟并发执行过程，即使不使用并行计算机，也能提高算法的执行效率。遗传算法的并行性主要从三个方面考虑，即个体适应度评价的并行性、整个群体各个个体适应度评价的并行性及子代群体产
26
上海大学毕业设计(论文)
生过程的并行性。
3．分类系统
分类系统属于遗传算法的机器学习中的一类，包括一个简单的基于串规则的并行生成子系统、规则评价子系统和遗传算法子系统。分类系统被人们越来越多地应用在科学、工程和经济领域中，是目前遗传算法研究中一个十分活跃的方向。
4．遗传神经网络
遗传神经网络包括连接级、网络结构和学习规则的进化。遗传算法与神经网络相结合，成功地用于从分析时间序列来进行财政预算。在这些系统中，训练信号是模糊的，数据是有噪声的，一般很难正确给出每个执行的定量评价，如果采用GA学习，就能克服这些困难，显著提高系统性能。Muhlenbein分析了多层感知网络的局限性，并猜想下一代神经网络就是遗传神经网络。
5．进化算法
模拟自然进化过程可以产生鲁棒的计算机算法——进化算法。遗传算法是其三种典型的算法之一，其余两种算法是进化规划和进化策略，这三种算法是独立发展起来的。
6．人工生命与遗传算法
近几年来，通过计算机模拟再现种种生命现象，以达到对生命更深刻理解的人工生命的研究正在兴起。已有不少学者对生态系统的演变、食物链的维持以及免疫系统的进化等用遗传算法做了生动的模拟。但是实现人工生命的手段很多，遗传算法在实现人工生命中的基本地位和能力究竟如何，这是值得研究的课题。
3.3 遗传算法的工作原理
遗传算法是一种基于生物进化原理构想出来的搜索最优解的仿生算法，它
模拟基因重组与进化的自然过程，把待解决问题的参数编码成基因，若干基因组成一个染色体（个体），染色体组（种群）进行类似于自然选择、配对交叉和变异的遗传操作，从而不断生成新种群。在每次遗传操作中，算法都按照所选适应度函数和一定的规则，对种群中的个体进行筛选，从而使适应度值高的个
27
上海大学毕业设计(论文)
体以较大的概率遗传到下一代。这样经过若干次迭代，种群的适应度值不断提高，最终收敛到满足要求的最优解或近似最优解。遗传算法的工作示意图如图3.1所示。
由图3.1可知，遗传算法的实现涉及的基本要素包括：参数的编码、初始群体的设定、适应度函数的设计、遗传基本操作、算法控制参数的设定和约束条件的处理。
1、编码
编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤，编码的好坏直接影响选择、交叉、变异等遗传运算。
编码就是把一个问题的可行解从解空间转换到遗传算法所能处理的搜索空间的转换，也就是解的遗传表示。迄今，人们总结出了三大类的编码方法：二
28
上海大学毕业设计(论文)
进制编码方法、符号编码方法和浮点数编码方法。其中，二进制编码方法是最主要且应用最广泛的一种编码方法。
二进制编码方法使用的编码符号集是由二进制符号0和1所组成的二值符号集{0,1}，它所构成的个体基因型是一个二进制编码符号串。二进制编码符号串的长度与问题所要求的求解精度有关。
例如，一个问题具有两个变量X1和X2，它们的染色体结构能用图3.2所示的方法描述。
1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 1 0 1 0 1 0 0 1 0 1 | X1 | X2 | 图3.2个体的染色体结构
X1被编码为10位，X2被编码为15位。这就是表现值（个体决策变量）的染色体编码。
2、初始种群
遗传算法中初始种群中的个体是随机产生的。一般来讲，初始种群的设定可采取如下的策略：
1)根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始种群。
2)先随机生成一定数目的个体，然后从中挑出最好的个体加到初始种群中。这种过程不断迭代，直到初始种群中个体数达到了预先确定的规模。
在试验研究中，我们常运用第一种策略，先将参数编码，并设定范围矩阵，利用计算机在范围内随机产生Nind个初始串结构数据，每个串结构数据称为一个个体，Nind个个体构成一个种群。
3、适应度评价
在遗传算法中使用适应度（Fitness）这个概念来度量种群中各个个体在优化计算中能达到或接近于或有助于找到最优解的优良程度。适应度较高的个体 遗传到下一代的概率就较大；而适应度较低的个体遗传到下一代的概率就相对
29
上海大学毕业设计(论文)
小一些。评价个体适应度的函数称为适应度函数（Fitness Function)。适应度函数总是非负的，任何情况下都希望其值越大越好，而目标函数可能有正有负，即有时求最大值，有时求最小值，因此需要在目标函数与适应度函数之间进行变换。
由解空间中某一点的目标函数值f(x)到搜索空间中对应个体的适应度函数值Fit(f(x))的转换方法基本上有以下两种：
① 直接以待解的目标函数f(x)转化为适应度函数Fit(f(x))，令
?f(x)目标函数为最大化问题Fit(f(x))????f(x)目标函数为最小化问题
这种适应度函数简单直观，但存在两个问题：一是可能不满足常用的轮盘赌选择中概率非负的要求；二是某些待求解的函数在函数值分布上相差很大，由此得到的平均适应度可能不利于体现种群的平均性能，而影响算法的性能。
② 对于求最小值问题，做下列转换：
?cmax?f(x)Fit(f(x))??0?f(x)?cmax其他
cmax为一个适当的相对比较大的数，是f(x)的最大值估计，保证适应度非负。
对于求最小值问题，做下列转换：
?cmin?f(x)Fit(f(x))??0?f(x)?cmin其他
cmin 为f(x)的最小值估计，可以是一个合适的输入值。 评价个体适应度的一般过程为：
1）对个体编码串进行解码处理后，可得到个体的表现型。 2）由个体的表现型可计算出对应个体的目标函数值。
3）根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度。
4、遗传操作
30