第一节 遗传算法

一、导言

遗传算法（Genetic Algorithms, GA或 GAs）是由美国密歇根大学的John H.Holland教授及其学生于20世纪60年代末到70年代初提出的。在1975年出版的《自然与人工系统的自适应性》（Adaptation in Natural and Artificial Systems）一书中，Holland系统地阐述了遗传算法的基本理论和方法，提出了对遗传算法的理论发展极为重要的模板理论（Schema Theory）。

后来De Jong和Goldberg等人做了大量的工作，使遗传算法更加完善。近年来，由于遗传算法求解复杂优化问题的巨大潜力及其在工业工程、人工智能、生物工程、自动控制等各个领域的成功应用，该算法得到了广泛的关注。可以说，遗传算法是目前为止应用最为广泛和最为成功的智能优化方法。

生物在自然界中的生存繁衍，显示了其对自然环境的优异的自适应能力。遗传算法所借鉴的生物学基础就是生物的进化和遗传。

（一）生物的进化

生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化（Evolution）。

（二）生物的遗传和变异

生物从其亲代继承特性或性状，这种生命现象就称为遗传（Heredity），研究这种生命现象就称为遗传学（Genetics）。生物进化的本质体现在染色体的改变和改进上，生物体自身形态和对环境适应能力的变化是染色体结构变化的表现形式。可见，生物进化过程本质上是一种优化过程，在计算科学上具有直接的借鉴意义。

二、遗传算法的基本原理

遗传算法在求解批量计划问题时的基本思想是根据问题的目标函数构造一个适值函数（Fitness Function），对一个由多个解（每个解对应一个染色体）构成的种群，进行评估、遗传运算、选择，经多代繁殖，获得适应值最好的个体作为问题的最优解。

具体可以描述如下。

Step 1：产生一个初始种群。

Step 2：根据问题的目标函数构造适应值函数（Fitness Function）。

Step 3：根据适应值的好坏，不断选择、繁殖。

Step 4：若干代后，得到适应值最好的个体即为最优解。

三、遗传算法的构成要素

（一）编码方法（Encoding Scheme）

编码方法也称为基因表达方法（Gene Representation）。在遗传算法中，种群中的每个个体，即染色体是由基因构成的。所以，染色体与要优化的问题的解如何进行对应，就需要通过基因来表示，即对染色体进行正确的编码。

（二）种群和种群大小

种群是由染色体构成的。每个个体就是一个染色体，每个染色体对应着问题的一个解。

（三）遗传算子（Genetic Operator）

遗传算子包括交叉（Crossover）和变异（Mutation）。遗传算子模拟了每一代中创造后代的繁殖过程，这是遗传算法的精髓。

（四）选择策略

选择策略一般为正比选择。

（五）停止准则（Stopping Rule/Criterion）

停止准则一般使用最大迭代次数作为停止准则。

四、生产批量计划问题的遗传算法

在现有的文献中，Dellaert等人及Xie and Dong采用遗传算法分别求解了无资源约束 MLLS问题以及带多资源约束的 MLLS问题。本书以Dellaert等人的算法为例介绍求解生产批量计划问题的遗传算法。

（一）二进制编码

由于生产批量计划问题可以用一个二进制矩阵表示，因此搜索生产批量计划问题的最优解等价于寻找一个最优的二进制决策矩阵 y=（（y1,1, …, y1, T）, …, （yN,1, …, yN, T）），这里yi, t∈{0,1}。

（二）初始种群

初始种群的产生不是通过完全随机的方式而是通过几个批量计划规则产生的。

（三）适值函数

适值函数的选择是根据目标函数值的相反值来选取的。

（四）变异操作

通常来说，变异操作定义为解向量中的某一单一位值的变化。

（五）累积变异

在对某种物料对应值进行变异时，最好同时改变该物料的前驱物料的对应值。这样做可以确保染色体的可行性，避免多余的修改调整策略。

（六）交叉操作

经典的交叉操作是单点交叉。单点交叉是基于一个随机选择的交叉位值，将两个染色体进行组合，通过交换各自的一部分来产生两个新的子代。

（七）交换

交换操作的对象是两个数对（i*, t*）以及（i*, t*+1）。如果数对（i*, t*）与（i*, t*+1）对应的染色体位置上仅有一个值为“1”且在时段i*和t*+1上的需求量都为正数，则交换两个数对的值（除非i*是第一个时段）。当交换发生时，前驱物料需要进行额外变异，变异的方式与累积变异的方式相同。

（八）通过RCWW产生子代

由于在预先的测试中，随机累积 WW规则（RCWW）展现出良好的性能，因此采用RCWW作为一个算子。算子的执行是将 RCWW算法应用于一个随机选择的物料以及比该物料具有更高的物料编号的物料上。最终的染色体是一个上部由原始染色体组成，下部由通过RCWW规则产生的部分组成的新染色体。

（九）选择与停止准则

由于几个染色体会具有相同的成本值，因此选择过程首先需要根据染色体的成本函数进行聚类。

停止准则由两种方式组成。一种是基于染色体的种群结构，另一种是基于算法预先设定的迭代次数。

以下给出了在某一次迭代结束后，染色体的选择过程。

当前种群大小比初始种群大小λ大时，将当前种群按目标函数值进行聚类，选择第y个染色体。

如果#Gy＞5且 y=1或者#Gy＞1且 y≠1，则第 y个染色体被淘汰。

否则，计算第y个染色体的存活概率：

均匀选择一个随机数r∈[0,1]，如果P（y）＜r，第y个染色体留在种群中，否则，染色体y被淘汰。