第二章 相关亚启发式算法

从第一章可以发现，无论是在求解无资源约束生产批量计划问题还是在求解有资源约束生产批量计划问题时，亚启发式算法都扮演了非常重要的角色，因此本章主要介绍求解生产批量计划问题的几种常用的亚启发式算法。

传统的优化方法是基于精确数学的方法，这类方法对数据的确定性和准确性有严格的要求。在实际生活中很多信息具有很高的不确定性，有些只能用随机变量和模糊集合，乃至语言变量来描述。虽然传统的随机规划或模糊优化方法有一定的处理数据不确定性的能力，但这些方法不外乎是用数学期望来替代随机变量，或是将模糊变量清晰化，而且计算的效能很低。实际中迫切希望能够直接对具有不确定性的数据进行计算的优化方法。实际生活中对最优化方法性能的需求促进了最优化方法的发展，于是一些新颖的优化算法——亚启发式算法或智能优化方法不断涌现出来。

1975年，Holland提出遗传算法（Genetic Algorithms, GA）。这种优化方法模仿生物种群中优胜劣汰的选择机制，通过种群中优势个体的繁衍进化来实现优化的功能。1977年，Glover 提出禁忌搜索算法（Tabu Search, TS）。这种方法将记忆功能引入到最优解的搜索过程中，通过设置禁忌区阻止搜索过程中的重复，从而大大提高了寻优过程的搜索效率。1983年，Kirkpatrick提出模拟退火算法（Simulated Annealing, SA）。这种算法模拟热力学中退火过程能使金属原子达到能量最低状态的机制，通过模拟的降温过程按波尔茨曼方程计算状态间的转移概率来引导搜索，从而使算法具有了很好的全局搜索能力。20世纪90年代初，Dorigo等提出蚁群优化算法（Ant Colony Optimization, ACO）。这种算法借鉴蚂蚁群体利用信息素相互传递信息来实现路径优化的机理，通过记忆路径信息素的变化来解决组合优化问题。

无论是在求解无资源约束生产批量计划问题还是在求解有资源约束生产批量计划问题时，亚启发式算法都扮演了非常重要的角色。亚启发式算法是近20年来在优化领域兴起的随机优化技术，在求解动态批量计划问题时，我们需要讨论如何进行算法各个组成部分的设计。在设计 SA算法和TS算法时，主要需要考虑的问题是：①如何表达一个解；②如何评价一个解；③如何定义邻域。此外，需要考虑初始解及控制参数的问题，比如SA算法的初始温度、降温比率以及停止准则等；对于 TS算法，需要考虑禁忌表的结构及长度、期望水平以及停止准则等。对于 GA算法来说，主要的决策问题包括：①解的表达；②解的评价；③如何构建基因算子来产生子代；④确定下一代种群的选择机制。此外，初始解问题、总迭代次数及修复算子等也需要进行考虑。

无论是TS算法、SA算法还是GA算法，在表达一个解的时候可以采用两种直接表达解的方式，一种是不但考虑整数形式（二进制）来表达，而且考虑连续变量（生产数量）形式来表达；另一种是只考虑整数形式，不考虑连续变量形式。在求解无资源约束问题时，采用的是第二种方式（以二进制矩阵形式）进行问题求解。与第一种表达方式相比，这种表达方式的复杂性降低了很多，但是需要求解额外的优化问题来获得一个完整的解。

在评价一个解的时候有多种方式，最明显的一种方式就是采用目标函数值。在GA算法中应用了基因算子之后，很有可能会产生不可行解。在TS算法和SA算法中，一个移动策略可能会产生不可行的邻域。那么如何来对待这些不可行解呢？第一种方式是放弃所有的不可行解或者给这些不可行解附加一个不可行的成本值。第二种方式是根据解的不可行程度，按比例分配一个惩罚成本值。第三种方式是针对不可行解，设计一些修复算子。

对于SA算法和TS算法来讲，邻域的定义需要基于当前的具体问题和解的表达方式。如果一个解的表达方式不但包括整数形式而且包括连续形式，移动策略可以基于这两种形式来进行。如果仅仅采用整数形式来表达解，最简单的机制是改变一个“产品—时段”组合的生产准备状态，这种方式是最普遍的邻域定义方式。

在GA算法中，我们采用基因算子来探索解空间。变异算子可以改变一个解，单点变异是最普遍的变异方式。如果采用批量大小来表达一个解，我们可以采用生成随机批量的方式来改变解的状态。交叉算子将几个解组合成了一个解。在单点变异过程中，两个解在随机点处被分割，之后被重新组合为一个新的解。选择算子中比较流行的是轮盘赌选择方式，它从当前种群和新生成的子代中选择一些染色体进入下一代。精英选择策略能够保留全局最优解。在一些采用多种群算子的 GA算法中，迁移算子允许两个来自不同种群的算子进行交叉操作。