1、第四章 遗传算法与组合优化4.1 背包问题（knapsack problem）4.1.1 问题描述0/1背包问题：给出几个尺寸为 S1，S 2，S n 的物体和容量为 C 的背包，此处S1，S 2，S n 和 C 都是正整数；要求找出 n 个物件的一个子集使其尽可能多地填满容量为C 的背包。数学形式：最大化 niiXS1满足 ,1Cnii nii 1,0广义背包问题：输入由 C 和两个向量 C(S 1，S 2，S n)和 P(P 1，P 2，P n)组成。设 X 为一整数集合，即 X1，2，3，n，T 为 X 的子集，则问题就是找出满足约束条件 ，而使 获得最大的子集 T，即求 Si 和 Pi
2、 的下标子集。TiiCTiP在应用问题中，设 S 的元素是 n 项经营活动各自所需的资源消耗， C 是所能提供的资源总量，P 的元素是人们从每项经营活动中得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。广义背包问题可以数学形式更精确地描述如下：最大化 niiXP1满足 ,1CSnii nii 1,0背包问题在计算理论中属于 NP完全问题，其计算复杂度为 O(2n)，若允许物件可以部分地装入背包，即允许 X，可取从 0.00 到 1.00 闭区间上的实数，则背包问题就简化为极简单的 P 类问题，此时计算复杂度为 O(n)。4.1.2 遗传编码采用下标子集
3、T的二进制编码方案是常用的遗传编码方法。串 T 的长度等于 n(问题规模)，Ti(1i n) 1 表示该物件装入背包，T i0 表示不装入背包。基于背包问题有近似求解知识，以及考虑到遗传算法的特点（适合短定义距的、低阶的、高适应度的模式构成的积木块结构类问题） ，通常将 Pi，S i 按 Pi/Si 值的大小依次排列，即 P1/S1P 2/S2P n/Sn。4.1.3 适应度函数在上述编码情况下，背包问题的目标函数和约束条件可表示如下。目标函数： niiPTJ1)(约束条件： CSnii1按照利用惩罚函数处理约束条件的方法，我们可构造背包问题的适应度函数 f(T)如下式：f(T) = J(T)
4、 + g(T)式中 g(T)为对 T 超越约束条件的惩罚函数，惩罚函数可构造如下:式中 Em 为 Pi/S(1i n)i 的最大值， 为合适的惩罚系数。4.2 货郎担问题（Traveling Salesman ProblemTSP）在遗传其法研究中，TSP 问题已被广泛地用于评价不同的遗传操作及选择机制的性能。之所以如此，主要有以下几个方面的原因：(1) TSP 问题是一个典型的、易于描述却难以处理的 NP 完全（NP-complete）问题。有效地解决 TSP 问题在可计算理论上有着重要的理论价值。(2) TSP 问题是诸多领域内出现的多种复杂问题的集中概括和简化形式。因此，快速、有效地解决
5、 TSP 问题有着极高的实际应用价值。(3) TSP 问题因其典型性已成为各种启发式的搜索、优化算法的间接比较标准，而遗传算法就其本质来说，主要是处理复杂问题的一种鲁棒性强的启发式随机搜索算法。因此遗传算法在 TSP 问题求解方面的应用研究，对于构造合适的遗传算法框架、建立有效的遗传操作以及有效地解决 TSP 问题等有着多方面的重要意义。问题描述：寻找一条最短的遍历 n 个城市的路径，或者说搜索整数子集 X1，2，n（X 的元素表示对 n 个城市的编号）的一个排列 (X) = v1，v 2，v n，使取最小值。式中的 d(vi, vi+1)表示城市 vi 到城市 vi+1 的距离。4.2.1
6、编码与适应度函数编码1以遍历城市的次序排列进行编码。如码串 1 2 3 4 5 6 7 8 表示自城市 l 开始，依次经城市 2，3，4，5，6，7，8，最后返回城市 1 的遍历路径。显然，这是一种针对 TSP 问题的最自然的编码方式。这一编码方案的主要缺陷在于引起了交叉操作的困难。2采用“边”的组合方式进行编码。例如码串 2 4 5 3 6 8 7 1 的第 1 个码 2 表示城市 1 到城市 2 的路径在 TSP 圈中，第 2 个码4 表示城市 2 到城市 4 的路径在 TSP 圈中，以此类推，第 8 个码 1 表示城市 8 到城市 1 的路径在 TSP 圈中。这一编码方式有着与前面的“节
7、点”遍历次序编码方式相类似的缺陷。3间接“节点”编码方式。以消除“一点交叉”策略（或多点交叉策略）引起的非法路径问题。码串长度仍为 n，定义各等位基因的取值范围为（n i + 1） ，i 为基因序号，解码时，根据相应基因位的取值，从城市号集合中不回放地取一个城市号，直至所有城市号被取完。由于这种编码方式特征遗传性较差，因此现行的研究中很少采用。适应度函数适应度函数常取路径长度 Td 的倒数，即f1/T d若结合 TSP 的约束条件（每个城市经过且只经过一次） ，则适应度函数可表示为：f1/(T d + *Nt)，其中 Nt是对 TSP 路径不合法的度量(如取付 Nt为未遍历的城市的个数)， 为
8、惩罚系数，常取城市间最长距离的两倍多一点(如 2.05*dmax)。4.2.2 交叉策略问题：基于 TSP 问题的顺序编码（其它编码如以边的组合状态进行编码也呈现相似特性），若采取简单的一点交叉或多点交叉策略，必然以极大的概率导致未能完全遍历所有城市的非法路径。如 8 城市的 TSP 问题的两个父路径为1 2 3 4 | 5 6 7 88 7 6 5 | 4 3 2 1若采取一点交叉，且交叉点随机选为 4，则交叉后产生的两个后代为8 7 6 5 5 6 7 81 2 3 4 4 3 2 1显然，这两个子路径均未能遍历所有 8 个城市，都违反 TSP 问题的约束条件。可以采取上述构造惩罚函数的方
9、法，但试验效果不佳。可能的解释：这一方法将本已十分复杂的 TSP 问题更加复杂化了。因为满足 TSP 问题约束条件的可行解空间规模为 n!；而按构造惩罚函数的方法，其搜索空间规模变为 nn；随着 n 的增大 n!与 nn 之间的差距是极其惊人的。解决这一约束问题的另一种处理方法是对交叉、变异等遗传操作做适当的修正，使其自动满足 TSP 的约束条件。常用的几种交叉方法：1部分匹配交叉(PMX，Partially Matched Crossover)法PMX 操作是由 Goldberg 和 Lingle 于 1985 年提出的。在 PMX 操作中，先依据均匀随机分布产生两个位串交叉点，定义这两点之
10、间的区域为一匹配区域，并使用位置交换操作交换两个父串的匹配区域。实例：如两父串及匹配区域为A9 8 4 | 5 6 7 | 1 3 2 0B8 7 1 | 2 3 0 | 9 5 4 6首先交换 A 和 B 的两个匹配区域，得到A9 8 4 | 2 3 0 | l 3 2 0B8 7 1 | 5 6 7 | 9 5 4 6对于 A、B两子串中匹配区域以外出现的遍历重复，依据匹配区域内的位置映射关系，逐一进行交换。对于 A有 2 到 5，3 到 6，0 到 7 的位置符号映射，对 A的匹配区以外的2，3，0 分别以 5，6，7 替换，则得A”9 8 4 | 2 3 0 | 1 6 5 7同理可得
11、：B”8 0 1 | 5 6 7 | 9 2 4 3这样，每个子串的次序部分地由其父串确定。2顺序交叉法(OX，Order Crossover)法与 PMX 法相似，Davis(1985)等人提出了一种 OX 法，此方法开始也是选择一个匹配区域：A9 8 4 | 5 6 7 | 1 3 2 0B8 7 1 | 2 3 0 | 9 5 4 6并根据匹配区域的映射关系，在其区域外的相应位置标记 H，得到A9 8 4 | 5 6 7 | 1 H H HB8 H 1 | 2 3 0 | 9 H 4 H再移动匹配区至起点位置，且在其后预留相等于匹配区域的空间(H 数目)，然后将其余的码按其相对次序排列在
12、预留区后面，得到A”5 6 7 H H H 1 9 8 4B”2 3 0 H H H 9 4 8 1最后将父串 A，B 的匹配区域相互交换，并放置到 A”，B”的预留区内，即可得到两个子代：A”5 6 7 | 2 3 0 | 1 9 8 4B”2 3 0 | 5 6 7 | 9 4 8 1虽然，PMX 法与 OX 法非常相似，但它们处理相似特性的手段却不同。PMX 法趋向于所期望的绝对城市位置，而 OX 法却趋向于期望的相对城市位置。3循环交叉（CX，cycle crossover）法Smith 等人提出的 CX 方法与 PMX 方法和 OX 方法有不同之处。循环交叉的执行是以父串的特征作为参
13、考，使每个城市在约束条件下进行重组。设两个父串为C9 8 2 1 7 4 5 0 6 3D1 2 3 4 5 6 7 8 9 0不同于选择交叉位置，我们从左边开始选择一个城市C9 一一一一一一一一D1 一一一一一一一一再从另一父串中的相应位置，寻找下一个城市：C9 一一 1 一一一一一一一D1 一一一一一一一一 9 一再轮流选择下去，最后可得C9 2 3 1 5 4 7 8 6 1 0D1 8 2 4 7 6 5 1 0 9 34基于知识的交叉方法这种方法是一种启发式的交叉方法，按以下规划构造后代：(1)随机地选取一个城市作为子代圈的开始城市。(2)比较父串中与开始城市邻接的边，选取最小的边添
14、加到圈的路径中。(3)重复第(2)步，如果发现按最小边选取的规划产生非法路径(重复经过同一城市)，则按随机法产生一合法的边，如此反复，直至形成一完整的 TSP 圈。使用这一方法，可获得较好的结果。在 200 个城市的 TSP 优化方面，已产生接近由模拟退火程序计算出的最优结果。不过，这一方法使用了基于问题的一些知识，损失了遗传算法的通用性和鲁棒性。关于 TSP 问题的遗传交叉方法还有各种各样的变形方法，一般来说，交叉方法应能使父串的待征遗传给子串，子串应能部分或全部地继承父串的结构特征和有效基因。4.2.3 变异技术从遗传算法的观点来看，解的进化主要靠选择机制和交叉策略来完成，变异只是为选择、
15、交叉过程中可能丢失的某些遗传基因进行修复和补充，变异在遗传算法的全局意义上只是一个背景操作。针对 TSP 问题，主要的变异技术如下述。1位点变异变异仅以一定的概率（通常较小）对串的某些位作值的变异。2逆转变异在串中，随机选择两点，再将这两点内的子串按反序插入到原位置中，如串 A 的逆转点为 3，6，则经逆转后，变为 AA 1 2 3 | 4 5 6 | 7 8 9 0A 1 2 3 | 6 5 4 | 7 8 9 0这种变异操作对于 TSP 问题，就调整前后引起的 TSP 圈的长度变化而言用于最细微的调整，因而局部优化的精度较高；但码串绝对位置所呈现的“模式”变化较大，所需的计算也稍为复杂一点
16、。3对换变异随机选择串中的两点，交换其值(码)。对于串 AA1 2 3 4 5 6 7 8 9若对换点为 4，7，则经对换后，A为A 1 2 3 7 5 6 4 8 9这种变异操作在求解 TSP 问题优化算法中常被采用。在遗传算法中，对换变异操作对码串绝对位置所呈现的“模式”变化影响较小，所需的计算也简单一些，但局部优化精度稍差。4插人变异从串中随机选择 1 个码，将此码插入随机选择的插入点中间，对于上述 A 而言若取插入码为 5，选取插入点为 23 之间则A 1 2 5 3 4 6 7 8 94.2.4 选择机制和群体构成在遗传算法中，最常见的选择机制是依据适应度的比例概率选择机制；在有限规
17、模的群体中，适应度较高的个体有较大的机会繁殖后代，即生物进化论上的适者生存规则。在新一代群体构成方法方面存在：N 方式：全部替换上一代群体的全刷新代际更新方式。E 方式：保留一个最好的父串的最佳保留（elitist）群体构造方式。G 方式：按一定比例更新群体中的部分个体的部分更新方式（或称代沟方法，这种情况的极端是每代仅删去一个最不适的个体的最劣死亡方式） 。B 方式：从产生的子代和父代中挑选最好的若干个个体的群体构成形式。从群体规模来看，有变化规模的方式，也有恒定规模的群体构成方式等。一般讲，N 方式的全局搜索性能最好，但收敛速度最慢； B 方式收敛速度最快，但全局搜索性能最差；E 方式和
18、G 方式的性能介于 N 方式和 B 方式之间。在求解货郎担问题的应用中，多选用 E 方式。4.2.5 基于遗传算法求解 TSP 的算法实现1编码与适应度函数我们以 n 城市的遍历次序作为遗传算法的编码，由于在可行解群体的韧始化、交叉操作及变异操作中均隐台 TSP 问题的合法性约束条件，故适应度函数取为哈密尔顿圈的长度的倒数（无惩罚函数） 。2选择机制开始，我们用随机方法产生初始解群。随着遗传算法的执行，我们保留 M 个较优的个体作为样本群体，以供选择；在每一代运算过程中，个体被选中的概率与其在群体中的相对适应度成正比。3交叉方法我们选用的交叉方法与 OX 法有点类似，现介绍如下：(1)随机在串
19、中选择一个交配区域，如两父串及交配区域选定为A1 2 | 3 4 5 6 | 7 8 9B9 8 | 7 6 5 4 | 3 2 1(2)将 B 的交配区域加到 A 的前面或后面，A 的交配区域加到 B 的前面或后面得到A 7 6 5 4 | 1 2 3 4 5 6 7 8 9B3 4 5 6 | 9 8 7 6 5 4 3 2 1(3)在 A中自交配区域后依次删除与交配区相同的城市码，得到最终的两子串为A 7 6 5 4 1 2 3 8 9B3 4 5 6 9 8 7 2 1与其它方法相比，这种方法在两父串相同的情况下仍能产生一定程度的变异效果，对维持群体内一定的多样化持性有一定的作用，实验
20、中也显示了较好的结果。4变异技术由于在选择机制中采用保留最佳样本方式，以及引入了“进化逆转”操作技术，为保持群体内个体的多样化，我们采取连续多次对换的变异技术，使可行解有较大的顺序排列上的变化，以抑制“进化逆转”的同化作用。变异操作发生的概率取得比较小（1%左右） ，一旦变异操作发生，则用随机方法产生交换次数 K，对所需变异操作的串进行 K 次对换（对换的两码位也是随机产生的） 。5 “进化逆转”操作引入“进化逆转”操作的主要目的是改善遗传算法的局部搜索能力。所谓局部搜索通常指的是基于邻域的试探搜索方法。在基本遗传算法操作中，交叉操作在可行解空间今动作范围较宽，步伐较大；变异操作由于受“选择”
21、压力的作用，通常也难以发挥局部搜索的功效（特别在遗传算法趋向收敛的后期阶段） 。因此，在遗传算法框架中加入适当的、基于邻域的局部搜索机制，构成一种全局搜索和局部搜索相结合的优化搜索算法，对改进优化质量以及提高搜索效率都是很有意义的。在自然遗传和进化过程中， “逆转”也是一种常见的现象。如一染色体内各片断的正常顺序是(1 23456)，在区间 23 和区间 56 发生了两处断裂，断裂片断又以反向顺序插入，于是逆转后的染色体顺序变为(125436)。自然生物遗传上的“逆转”现象有消极的作用（如导致致死因素、不育因素等） ，也可能产生积极的作用(如导致生物的适应能力增强等)。从进化意义上讲，如果说交
22、叉、变异等遗传操作使子代趋向于拥有较优品质的基因型的话，那么逆转、对换等遗传操作的功能就是使这些基因型及其组合以较优的次序遗传给后代。在针对 TSP 问题的遗传算法中， “逆转”是一种常见的“变异”技术。我们使用的“进化逆转”是一种单方向的(朝着改进的方向)和连续多次的“逆转”操作，即对于结定的串，若“逆转”使串(可行解)的适应度提高，则执行逆转换作，如此反复，直至不存在这样的逆转操作为止。这一操作实际上使给定的串改良到它的局部极点，这种局部爬山能力与基本遗传算法的全局搜索能力相结合在实验中显示了较好的效果。6算法的流程框图7实验结果实验中，群体规模定为 100，交叉概率为 0.95，变异概率
23、为 0.003，初始可行解群体由随机法产生。实验结果表明：(1)当 n15 时，随机样本实验表明，本算法可 100搜索到用穷举法求得的最优解。(2)当 15M30 时，我们对一组样本进行了测试，结果表明本算法能收敛到一稳定的“最好解”(难以确认其最优性)；多次实验的误差结果为 0，模拟退火法也可找到相同的“最好解” ，但运行时间约为遗传算法的 6 倍。(3)对 n50，M 60，M80 及 M100 的测试结果表明，遗传算法在求解质量上略优于模拟退火法( 0.95) ，优化效率高于模拟退火法。表所示为遗传算法(GA)与模拟退火方法(SA 法) 的比较实验结果，表中所列 TSP 路径长度为相对长
24、度，其值由下式算出：上式中，T d 为实际路径的长度，X 为包含 TSP 所有城市的最小正方形的边长，N 为TSP 问题的城市数目。图为城市规模 N100 的 TSP 问题的初始群体中的最佳路径，图为经本算法优化得到的最佳路径。4.3 作业调度问题作业调度问题(Job Shop Scheduling Problem, JSP)是一种资源分配问题。这里的资源主要是指设备资源，问题的求解目标是要找到一个将一组工件安排到设备上去，以使作业可为“最优”完成的方案。每个作业可由一些任务组成，而每个任务必须由特定的设备处理。一个调度是按先后顺序条件将所有任务安排到设备上的一种方案。通常，约束的数目大，使JSP 成为一个非常难解的组合问题(NP 完全问题)。
