2.1 遗传算法理论
遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它最早由美国Michigan大学的Holland教授提出，起源于20世纪60年代对自然和人工自适应系统的研究。20世纪70年代De Jong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。在一系列研究工作的基础上，20世纪80年代由Goldberg进行归纳总结，形成了遗传算法的基础框架。
遗传算法作为一种新的全局优化搜索算法，它不仅包含了进化算法的基本形式和全部优点，同时还具备如下一些独特的特性。
（1）在求解问题时，遗传算法首先要选择编码方式，它直接处理的对象是参数的编码集而不是问题参数本身，搜索过程既不受优化函数连续性的约束，也没有优化函数导数必须存在的要求。通过优良染色体基因的重组，遗传算法可以有效地处理传统上非常复杂的优化函数求解问题。
（2）若遗传算法在每一代对群体规模为n的个体进行操作，实际上处理了大约Q（n3）个模式，具有很高的并行性，因而具有显著的搜索效率。
（3）在所求解问题为非连续、多峰以及有噪声的情况下，能够以很大的概率收敛到最优解或满意解，因而具有较好的全局最优解求解能力。
（4）对函数的性态无要求，针对某一问题的遗传算法经简单修改即可适应于其他问题，或者加入特定问题的领域知识，或者与已有算法相结合，能够较好地解决一类复杂问题，因而具有较好的普适性和易扩展性。
（5）遗传算法的基本思想简单，运行方式和实现步骤规范，便于具体使用。
鉴于遗传算法具有上述特征，一经提出即在理论上引起了高度重视，并在实际工程技术和经济管理领域得到了广泛的应用，产生了大量的成功案例。
遗传算法以群体中的个体为对象，并利用随机化技术对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的基本操作；参数编码、初始化群体的设定、适应度函数的设计、遗传操作的设计和控制参数的设定5个要素组成了遗传算法的核心内容，遗传算法的基本流程如图2-1所示。
2.1.1 遗传算法编码理论
编码是应用遗传算法时要解决的首要问题，编码方法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化运算的效率。针对一个具体应用问题，如何设计一种完美的编码方案一直是遗传算法的应用难点之一，也是遗传算法的一个重要研究方向，但目前还没有一套既严密又完整的指导理论及评价准则。De Jong曾提出了两条操作性较强的实用编码原则，即：①编码应使用易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案。②应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案。De Jong编码原则仅仅给出了设计编码方案时的一个指导性大纲，它并不适合于所有问题。所以对于实际应用问题，必须对编码方法、交叉运算方法、变异运算方法、解码方法等统一考虑，以寻求一种对问题的描述最为方便、遗传运算效率最高的编码方案。
图2-1 遗传算法基本流程框图
由于遗传算法应用的广泛性，迄今为止人们已经提出了许多种不同的编码方法。总的来说，这些编码方法可以分为3大类：二进制编码方法、浮点数编码方法和符号编码方法。但是由于二进制编码方法是遗传算法中最常用的编码方法，它使用的编码符号集是由二进制符号0和1所组成的二值符号集合{0，1}，它所构成的个体基因是一个二进制编码符号串。
二进制编码符号串的长度与问题所要求的求解精度有关。假设某一参数的取值范围是［Umin，Umax］，二进制编码符号串长度为l，则总共能够产生2l种不同的编码，编码时对应关系如下：
二进制编码具有编码、解码操作，操作简单易行，交叉、变异等遗传操作便于实现，符合最小字符集编码原则和利用模式定理对算法进行理论分析。
2.1.2 遗传算法群体设定
遗传操作是对众多个体同时进行的。这众多的个体组成了群体。在遗传算法处理流程中，继编码设计后的任务是初始群体的设计，并以此为起点一代代进化，按某种停止准则终止进化过程。其中有两个需要考虑的因素：①初始群体的设定。②进化过程中各代的规模如何维持。
群体规模影响遗传优化的最终结果以及遗传算法的执行效率。当群体规模n太小时，遗传算法的优化性能一般不会太好，而采用较大的群体规模可减少遗传算法陷入局部最优解的机会，但较大的群体规模意味着计算复杂度高。一般来讲，初始群体的设定可采取如下的策略。
（1）根据问题的固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后在此分布范围内设定初始群体。
（2）先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中。这个过程不断迭代，直到初始群体中个体数达到了预先确定的规模。
群体规模的确定受遗传操作中选择操作的影响很大。根据模式定理，若群体规模为M，则遗传操作可从这M个个体中生成和检测M3个模式，并在此基础上不断形成和优化积木块，直到找到最优解。群体规模越大，群体中个体的多样性越高，算法陷入局部解的危险越小。所以，从考虑群体多样性出发，群体规模应较大。但是，群体规模太大会降低计算效率；并且群体规模太小，会使遗传算法的搜索空间分布范围有限，因而搜索有可能停止在未成熟收敛现象。
群体多样性也可以作为算法迭代终止条件，当群体多样性降低到一定程度时，认为群体已经稳定，GA达到了收敛状态。GA的收敛性实际上等价于群体的收敛性，但事实上群体收敛并不保证GA已经收敛到了问题的全局最优解。
群体多样性的计算方法为：任意优化问题的二进制编码空间为{0，1}L，群体规模设定为n，群体所包含个体集合P={a1，a2，…，an}，其中aj=（a1j，a2j，…，aLj），j=1，2，…，n，其多样性测度可表达为
2.1.3 遗传算法适应度函数
遗传算法中使用适应度来度量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率就较大；而适应度较低的个体遗传到下一代的概率就相对小一些。
1.目标函数与适应度函数
遗传算法的一个特点是它仅使用所求问题的目标函数值就可得到下一步的有关搜索信息。而对目标函数值的使用是通过评价个体的适应度来体现的。评价个体适应度的一般过程：①对个体编码串进行解码处理后，可得到个体的表现型。②由个体的表现型可计算出对应个体的目标函数值。③根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度。
最优化问题可分为两大类，一类为求目标函数的全局最大值，另一类为求目标函数的全局最小值。对于这两类优化问题，可以由解空间中某一点的目标函数值f（X）到搜索空间中对应个体的适应度函数值F（X）转换，具体转换方法为
（1）对于求最大值的问题，可按下式转换：
式中：Cmin为一个适当地相对较小的数。
（2）对于求最小值的问题，可按下式转换：
式中：Cmax为一个适当地相对较大的数。
遗传算法中，群体的进化过程就是以群体中各个个体的适应度为依据，通过一个反复迭代过程，不断地寻求出适应度较大的个体，最终就可得到问题的最优解或近似最优解。
2.适应度尺度变换
在遗传算法中，个体被遗传到下一代群体中的概率是由该个体的适应度来确定的。应用实践表明，利用式（2-5）或式（2-6）来计算个体适应度时，有些遗传算法收敛得很快，也有些遗传算法收敛得很慢，由此可见，有时在遗传算法运行的不同阶段，还需要对个体的适应度适当地扩大或缩小。这种对个体适应度所做的扩大或缩小变换就称为适应度尺度变换（Fitness Scaling）。
目前常用的个体适应度尺度变换方法主要有3种：线性尺度变换、乘幂尺度变换和指数尺度变换。
（1）线性尺度变换。线性尺度变换的公式为
式中：F为原适应度；F′为尺度变换后的新适应度；a和b为系数。
系数a和b直接影响尺度变换的大小，所以对其的选择一般要满足两个条件：①尺度变换后全部个体的新适应度的平均值F′avg要等于其原适应度的平均值Favg。②尺度变换后群体中新的最大适应度F′max要等于其原平均适应度Favg的指定倍数。
（2）乘幂尺度变换。乘幂尺度变换的公式为
即新的适应度是原有适应度的某个指定乘幂。幂指数k与所求解的问题有关，并且在算法的执行过程中需要不断对其进行修正才能使尺度变换满足一定的伸缩要求。
（3）指数尺度变换。指数尺度变换的公式为
即新的适应度是原有适应度的某个指数。式中系数β决定了选择的强制性，β越小，原有适应度较高个体的新适应度就越与其他个体的新适应度相差较大，亦即越增加了选择该个体的强制性。
2.1.4 遗传操作
遗传操作是模拟生物基因遗传的操作。在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照它们对环境适应的程度（适应度评估）施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言，遗传操作可使问题的解一代一代地优化，并逼近最优解。遗传操作主要包括3个遗传算子：①选择（Selection）。②交叉（Crossover）。③变异（Mutation）。
1.交叉与变异
遗传算法中的交叉运算，是对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他算法的重要特征，它在遗传算法中起着关键作用，是产生新个体的主要方法。一点交叉的信息量比较小，交叉位置的选择可能带来较大偏差，故在本模型求解中，采用两点交叉，父代1与父代2两点交叉如图2-2所示。
图2-2 父代1与父代2两点交叉
从遗传算法产生新个体的能力方面来看，变异运算只是产生新个体的辅助方法，但也是必不可少的一个步骤，变异运算能改善遗传算法的局部搜索能力，维持群体的多样性，防止出现早熟现象。在遗传算法中，变异通过按变异概率Pm随机反转某位等位基因的二进制符值来实现。对于给定的染色体位串s=a1a2…aL，可表示为
生成新的个体s′=a′1a′2…a′L。式中，xi是对应于每一个基因位产生的均匀随机变量，xi∈[0，1]，为了保证个体变异后不会与其父代产生太大的差异，变异概率一般取值较小，以保证群体发展的稳定性。
2.选择算子与约束条件
在模型求解中，采用比例选择和最优保存策略相结合的选择运算，比例选择方法是一种回放式随机采样的方法，每个个体被选中的概率与其适应度大小成正比，对于给定规模为n的群体P={a1，a2，…，an}，∀aj∈P，其个体适应度为
实际应用中的优化问题一般都含有一定的约束条件，在遗传算法的应用中，必须对这些约束条件进行处理，目前没有一种能够处理各种约束条件的一般化方法。所以对约束条件进行处理时，只能针对具体应用问题及约束条件的特征，选用不同的处理方法。在构造遗传算法时，处理约束条件的常用方法主要有3种：搜索空间限定法、可行解变换法、罚函数法。在设计的模型中，采用罚函数法对在解空间中无对应可行解的个体惩罚来降低该个体的适应度，使该个体被遗传到下一代群体中的机会减少。