1.3　基于遗传算法的组合优化

组合优化问题指的是对离散变量最优化的一类问题，即在一定条件下，求解目标函数的最大解或最小解，解的形式可能是一个整数，也可能是一个集合或排列。解决这类问题的方法有遗传算法、线性和非线性规划、退火算法、神经网络等。遗传算法因其算法设计简单，功能强，不需要额外的处理目标函数等优点，被广泛地应用在组合优化问题的处理上。常见的组合优化问题有时间表问题（Time Table Problem，TTP）、旅行商问题（Traveling Saleman Problem，TSP）问题和0-1规划问题等，本节将从这三类问题入手，介绍遗传算法在组合优化问题上的具体方法。

1.3.1　基于遗传算法的TTP问题

TTP实际是一种调度问题，如在工厂中，如何合理设定机器的运行时间使得工厂效率最高；在医院中，如何调度护士排班问题；在学校中，如何安排教师和教室资源，以避免课程、教室冲突等。本节将以大学考试时间表调度问题为例详述遗传算法在TTP问题上的应用。

1．约束条件

没有座位容量约束的考试时间表问题，是假设学校教室所拥有的座位数量是无限多的，也就是在同时间段的考试中，只要各考试科目不冲突，就都可以安排在这个时间段中，不受座位数量的限制。该问题的约束条件包含硬约束条件和软约束条件。硬约束条件是该时间表必须满足的条件，软约束条件是指一些为了提高时间表质量需要尽量满足但非必须满足的条件。常见的硬约束条件有：

（1）同一个考生在同一时间段内不能同时参加多门考试；

（2）各门考试只能被安排一次；

（3）所有的考试都应被安排进时间表中。

软约束条件有：

（1）同一个考生尽量不连续地参加考试，即考生的各门考试时间间隔尽可能大；

（2）考生的所有考试在整个表中的分布尽量均匀；

（3）对于某些考试最好有固定的教室；

（4）为了获得较高的利用率，教室容量应尽量接近参考学生人数；

（5）某些考试需在同一天被安排；

（6）某些考试需被排在某特定时间段内；

（7）某些参考人数多的考试尽量早考（通常指公共课）；

（8）同一门考试，尽量将同系考生排在一起。

大学考试时间表问题研究的就是如何在满足硬约束条件的情况下，尽可能满足多的软约束条件。时间表质量的好坏就是由满足软约束条件程度的高低决定的，软约束条件的违反值越小，时间表的质量越高，反之则时间表的质量越低。

2．数学模型

大学时间表问题是一个离散优化问题，这里采用的数学模型是由Carter M. W.、Laporte G.和Lee S. Y.提出的。假设共有 E 门考试，分别表示为 ， 表示考试门数，要将它们安排到 P 个时间段中，则符合硬约束条件的数学模型为：

其中，若 e _i 被分到时间段 p ，则 a _ip 为1，否则 a _ip 为0； c _ij 表示同时要参加考试科目 e _i 和 e _j 的学生人数。式（1-2）和式（1-3）是两个硬约束条件，式（1-1）表示连续参加两门考试的学生人数，是一个需要优化的目标，称为冲突数。

式（1-1）只能评价相邻时间段内的目标质量，不能全面地描述时间表的好坏，为此，Carter发表了新的测度方法，简称为“平均冲突数”。该方法作用于每个学生，其规则为，对每个需要参加考试的学生，若连续参加两门考试，则对他设定一个惩罚值，该值表示为 W ₁ =16；若中间间隔一个时间段，则惩罚值为 W ₂ =8；若中间间隔两个时间段，则惩罚值为 W ₃ =4；若中间间隔3个时间段，则惩罚值为 W ₄ =2；若中间间隔4个时间段，则惩罚值为 W ₅ =1；其余的大于4个时间段间隔的惩罚值都为0。优化惩罚值使其变小就可以使科目分布得更均匀。假设 N _S 是每个惩罚值所对应的考生人数，总人数是 S ，则依然满足式（1-2）和式（1-3）的约束条件下的新优化目标为：

3．常用数据集

Toronto标准测试数据集是考试时间表问题的常用数据集，是由Carter统计美国、加拿大、英国、沙特阿拉伯等国家的大学的学生课表分布情况，得到实际应用的11个测试数据集，这些数据集是没有座位容量约束的。后来的研究者又对其进行了补充。

1.3.2　基于遗传算法的旅行商问题

TSP是受到广泛研究的一类组合优化问题，具体研究的是对于 n 个给定的城市，找到一个访问顺序使得路径最短，要求每个城市只能访问一遍。该问题是一个NP-hard问题，目前还没有一个精确求解的有效算法，所以经常使用遗传算法来找出一个相对较好的解，当城市规模较小的时候可以求得真实最优解。采用遗传算法求解TSP的思想是由Grefenstette J.提出的，在此之后，有学者陆陆续续提出了各种改进算法，并成功将其逐步应用到更大城市规模中。

根据TSP求解要求，一般可表述为如下形式：

其中， f 为目标函数， d _ij 为城市 i 到城市 j 的距离，若城市 i 到城市 j 的路径被选择，则 x _ij =1。

1．遗传算法求解TSP的算法步骤

表1.2给出了遗传算法求解TSP的算法步骤，参考该步骤，后面将详细介绍具体的编码方式、交叉算子以及变异算子。

2．编码方式

1）直接表示法

直接表示法是将城市按照它们被访问的顺序列出，所以基因的取值范围即为城市的编码范围，染色体长度为城市的个数。需要注意的是，因为每一个城市只能经过一次，所以不同基因位上的城市编号是不重复的。例如，解决一个9城市的TSP，将城市依次编号为1～9，则染色体可以表示如图1.3所示。

该染色体代表的访问城市序列为3-2-5-4-7-1-6-9-8，表1.3给出直接表示法编码和解码的一般过程。

2）随机数表示法

随机数表示法的基因位取值为（0，1）间的一个随机数，染色体长度依然为城市规模，解码时将每位上的随机数按从大到小排序，排数后的名次即代表城市的序号。随机生成的一个染色体如图1.4所示。

如第一位基因值0.23在排序后的名次为第6，则解码后代表编号为6的城市，依次解码可以得到该染色体对应的城市访问顺序为6-1-3-7-8-4-9-2-5。表1.4给出随机数表示法编码和解码的一般过程。

3．交叉算子

至今已经提出了很多适用于序列表示法的交叉算子，其中常见的算子有部分映射交叉（PMX）、顺序交叉（OX）、循环交叉（CX）、基于位置的交叉（PBX）和启发式的交叉。

这些算子可以分为两类：一类是规范方法，可以看作是二进制字符串的两点或多点交叉到序列表示的扩展；另一类是启发式方法，旨在产生性能提升的子代。

下面对上述提到的常见交叉算子分别作详细的介绍。

1）部分映射交叉

表1.5为部分映射交叉的运算过程。其中， v ₁ 、 v ₂ 代表两个父代染色体1和2， 、 代表产生的两个子代染色体， l 是染色体的长度， R 为两个父代染色体之间的映射关系， s 是交叉操作的在染色体上的起始位置， t 是交叉操作的终止位置，relation（ v ₁ ， v ₂ ）表示搜索 v ₁ 和 v ₂ 之间的关系，legalize（ v ₁ ， v ₂ ， R ）表示基于关系 R 改变 v ₁ 和 v ₂ 的基因值。

PMX交叉算子运算中主要涉及了4个运算步骤，举例详述如下：

（1）从给定的染色体中随机选取两个位置，给定如图1.5所示的两个父代染色体，染色体长度为9，选取交叉位置如下，分别是位置2和6。

（2）交换两个子字符串。选取交叉位置后，交换两个父代染色体交叉位置之间的子字符串，得到如图1.6所示子代染色体。

（3）产生映射关系。上述交叉操作产生的子代染色体并不是合法的，因此需要产生映射关系以使子代染色体合法化，具体如图1.7（a）所示。由此得到映射关系见图1.7（b），表示基因1和3相互映射，2和5相互映射，9和4相互映射。

（4）根据映射关系使子代合法化。由第（2）步得到的子代染色体可以看出，当前得到的染色体是不合法的，即不符合TSP中一个城市不能遍历多次的要求，由此需要根据第（3）步得到的映射关系对子代染色体进行调整，使其合法化。合法化后的子代染色体如图1.8所示。

2）顺序交叉

表1.6给出顺序交叉算子的运算过程。其中， v ₁ 、 v ₂ 代表两个父代染色体1和2， v' 是交叉后得到的子代染色体， l 是染色体长度， w 为工作数据， f _g 为标签， s 是交叉操作用于染色体上的起始位置， t 为终止位置。

OX交叉算子中主要涉及了3个步骤。

（1）选择两个父代个体，如图1.9所示，在父代个体1中选出 s 和 t 之间的字符串，也就是3 4 5 6。

（2）复制步骤（1）中得到的部分染色体产生子代 v' ，如图1.10所示。

（3）用parent2中未选择的子字符串基因填充proto-child以产生合法的子代个体，即用7 9 1 2 8基因依次填充，具体见图1.11。

3）循环交叉

循环交叉算子的运算过程见表1.7。其中， v ₁ 、 v ₂ 代表两个父代染色体1和2， v' 是交叉后得到的子代染色体， l 是染色体长度， w 为工作数据， N 为循环中值的数量。 T ={ t [ n ]}， n =1，2，…， N -1为proto-child中 S 的位置集合， S ={ s [ k ]}， k =1，2，…， N -1是循环中proto-child基因值的集合。 C ={ c [ j ]}， j =1，2，…， N -1是循环值集合。 f _g1 为标签1， f _g2 为标签2，cy（ v ₁ ， v ₂ ）表示搜索 v ₁ 、 v ₂ 之间的循环。

CX交叉算子中主要涉及3个步骤。

（1）寻找父代个体之间的循环，如图1.12所示。根据这两个父代染色体可以找到循环关系：1→5→2→4→9→1。

（2）复制从parent1中找到的循环基因，产生proto-child，如图1.13所示。

（3）用parent2填充proto-child的空白区域以产生子代。

4）基于位置的交叉PBX

PBX交叉的运算过程如表1.8所示。其中， v ₁ 、 v ₂ 代表两个父代染色体1和2； v' 是交叉后得到的子代染色体； l 是染色体长度； w 为工作数据； N 为选择的位置总数； T ={ t [ j ]}， j =1，2，…， N 为选择的位置集合； S ={ s [ m ]}， m =1，2，…， N 为选择位置的基因值集合； f _g1 为标签1； f _g2 为标签2。

PBX交叉算子中主要涉及3个步骤。

（1）如图1.15所示，从parent1中随机选择一些位置并用 j 标注。

（2）复制选择位置的基因值，产生如图1.16所示的proto-child。

（3）使用parent2填充proto-child的空白区域以产生子代个体，如图1.17所示。

4．变异算子

常见的用于序列表示的变异方法有相反变异（inversion mutation）、插入变异（insertion mutation）、交换变异（swap mutation）和启发式变异（heuristic operators），下面分别对这些变异算子做相应的介绍。

1）相反变异

相反变异的运算过程如表1.9所示。其中， v 是父代染色体； l 是染色体的长度； v' 是子代染色体； s 为子字符串的起始位置； t 为子字符串的终止位置； S 为子字符串的相反形式；invert（string）表示取string的相反顺序。

相反变异主要有两个运算步骤。

（1）随机选取一个子段，用 s ～ t 表示选择的子段，如图1.18所示。

（2）通过将选择的子段顺序反过来产生子代，如图1.19所示。

2）插入变异

插入变异的运算过程如表1.10所示，其中， v 是父代染色体； v' 是子代染色体； l 是染色体的长度； i 是在父代个体中选择的位置1； j 是在父代个体中选择的位置2； W 为工作数据集。

插入变异主要有两个运算步骤。

（1）从父代个体中随机选择一个基因位置，如图1.20所示。

（2）将随机选择的基因值插入到父代个体中另外随机选择的位置，该位置上及其后的基因全部后移一位，如图1.21所示。

3）交换变异

交换变异的运算过程如表1.11所示。其中， v 是父代染色体； l 是染色体的长度； v '是子代染色体； i 、 j 是随机选择的两个位置。

交换变异主要有两个运算步骤。

（1）从父代个体中随机选择两个位置 i 和 j ，如图1.22所示。

（2）交换父代个体中 i 和 j 位置上的基因产生子代，如图1.23所示。

4）启发式变异

启发式变异的运算过程如表1.12。其中， v 是父代染色体； v' 是子代染色体； l 是染色体的长度； m 为选择位置的总数； r 为选择的位置； N 是邻域染色体的总数； w 为工作数据； n 是在 P 中具有最好适应度值的染色体的位置； P { p [ i ]}， i =1，2，…， N 是邻域染色体的集合； nb （ v [ r ]）用于搜索第 r 个基因的邻域； F （ p [ i ]）为 p [ i ]的适应度值。

启发式变异主要有两个运算步骤。

（1）选择位置并产生邻域，如图1.24所示。

（2）计算邻域的适应度值选择子代，如图1.25所示。

5．选择算子

选择是从生成的新种群中选择合适的个体进入下一代循环，个体是否被选择取决于它的优劣，即适应度值的大小。常用的选择算法有轮盘赌选择、竞标赛选择、确定性选择等。其中轮盘赌选择是非常经典和常用的方法，它的机制是使优秀个体被选择的概率更大，同时差的个体也有被选择的可能，增加进入下一代种群的多样性。轮盘赌选择的算法流程见表1.13。

1.3.3　基于遗传算法的0-1规划

0-1规划问题是指决策变量只取0或1的一类特殊整数规划问题。因为0和1可以灵活地表示有与无，选择与放弃，开与关等，所以在实际生活中，很多问题都可以建模为0-1规划问题，如学校或工厂的选址、背包问题、装箱问题、TSP、人员安排等。0-1规划因其广泛的应用范围被众多学者研究，提出了很多方法，常见的方法有分支定解法、穷举法、隐枚举法、割平面法等。遗传算法也因自身强大的优化能力成为解决0-1规划的主流方法之一。下面就针对0-1背包问题详细描述遗传算法是如何应用于0-1规划中的。

背包问题可以描述为，给定一个背包和许多物品，然后从这些物品中选出一些物品放入背包中，假设每一个物品都有各自的重量 w _j 和利润 c _j ，目标就是如何选择放入背包的物品，使物品总重在背包承重范围内，利润最大。根据问题描述，给出0-1背包问题的数学公式：

其中， W 表示背包最大承重； w _j 为第 j 个物品的重量； c _j 为第 j 个物品的利润； x _j 即为决策变量，当该值为1时表示选择第 j 个物品放入背包，0时不放入。

现阶段，用于解决0-1背包问题的遗传算法主要分为3类，分别是二进制表示法求解0-1背包问题，序列表示法求解0-1背包问题和可变长度表示法求解0-1背包问题。

1．二进制表示法求解0-1背包问题

二进制字符串表示法是0-1背包问题编码中最简单易懂的表示方法，比如当物品总数为7，选择第2和第4个物品放入背包时，即编码为：

x =[0　1　0　1　0　0　0]

若7个物品的利润分别是40、5、20、30、30、10、60，质量分别是30、5、30、20、40、15、45，背包最大承重 W 为60，则根据式（1-7）即可算出：

总利润 f （ x ）=40 x ₁ +5 x ₂ +20 x ₃ +30 x ₄ +30 x ₅ +10 x ₆ +60 x ₇ =35

总重量 g （ x ）=30 x ₁ +5 x ₂ +30 x ₃ +20 x ₄ +40 x ₅ +15 x ₆ +45 x ₇ =25≤ W

算出的总重量为25，小于背包最大承重60，所以该解是可行解。反之，若解的总重量大于背包最大承重则是不可行解。对于不可行解，现已提出了两种处理方法：罚函数法和解码方法。

罚函数法由Gordon V.和Whitney D.提出，对于染色体的惩罚值就等于超出背包容量的总重量。

对于最大值问题，罚函数可以按如图1.26设置。其中

于是使用罚函数后的适应度函数为：

解码方法的步骤为：首先根据利润重量比将 x _j =1的物品按降序排列；然后使用第一拟合启发式算法选择物品，直到背包不能再放入物品；最后输出选择的物品并停止运算。

假设输入数据如表1.14所示，其背包容量 W =100，假定给定的染色体如图1.27所示。根据利润重量比将选择的物品按降序排序，因为2、3和7号基因位上对应的比值为1.2、0.33和2.0，所以排序后的染色体如图1.28所示。使用第一拟合启发式算法选择物品，直到背包不能再放入物品。选择过程如下：

依次选择7号、2号、3号基因所代表的物品，当选择7号和2号时， g （ x ）=80≤ W ， f （ x ）=120，符合要求；然而当再加入3号时， g （ x ）=110> W ，超出背包所能容纳的最大重量，不符合要求。所以，最终选择的是7号和2号物品，染色体修正为chromosome=[0100001]。

2．序列表示法求解0-1背包问题

Hinterding R.提出采用序列表示法求解0-1背包问题。对于含有 n 个物品的0-1背包问题，此时一个染色体包含 n 个基因，在每个基因位上用一个明确的整数数字表示一个物品，序列表示法中物品的顺序可以视为它放入背包中的优先顺序。此时对应的适应度函数为：

下面举例说明序列表示法的具体步骤，假设输入数据如表1.15所示，背包容量 W =100。假设给定的染色体为[1 6 4 7 3 2 5]，然后按照顺序放入物品，当物品1、6、4放入背包后，此时的物品总重量为90，再放入物品7、3、2中的任意一个都会使物品总重超过 W 值，只有加入物品5可以使总重为100= W ，符合要求。

3．可变长度表示法求解0-1背包问题

这种表示属于直接编码的方法，它不同于序列表示法，在序列表示法中，染色体基因位的顺序和值代表了物品加入背包的顺序，而该方法的基因位与物品放入背包的顺序无关，可以看作是将物品一起放入背包。依然采用表1.15中的数据，给出如图1.29所示的3个染色体，求出其中的最优解。

对于第一条染色体， g （ x ）=30≤ W ， f （ x ）=60；对于第二条染色体， g （ x ）=80≤ W ， f （ x ）=120；对于第三条染色体， g （ x ）=110> W ， f （ x ）=130。

可以看出，第三条染色体对应的物品总重量超过了背包最大承重值，是不可行解，第一条和第二条是可行解，且第二条染色体对应的物品总价值大于第一条，所以这3条染色体中，第二条最优。表1.16给出该方法的一般求解过程。