第四章遗传算法与组合优化4.1背包问题(knapsack problem) 4.1.1问题描述0/1背包问题：给出几个尺寸为S1,S2,…,Sn的物体和容量为C的背包，此处S1,S2,…,Sn和C都是正整数；要求找出n个物件的一个子集使其尽可能多地填满容量为C的背包。数学形式：最大化满足

∑S Xi=1 i

n

i

∑S Xi=1 i

n

i

≤ C,

X i∈{0,1}, 1≤ i≤ n

4.1背包问题(knapsack problem)广义背包问题：输入由C和两个向量C=(S1,S2,…,Sn)和P=(P1,P2,…,Pn)组成。设X为一整数集合，即X=1, 2,3,…,n,T为X的子集，则问题就是找出满足约束条件，而使获得最大的子集T,即求Si和Pi的下标子集。数学形式：最大化满足

∑PXi=1 n i

n

i

∑S Xi=1 i

i

≤ C,

X i∈{0,1}, 1≤ i≤ n

4.1背包问题(knapsack problem)在应用问题中，设S的元素是n项经营活动各自所需的资源消耗，C是所能提供的资源总量，P的元素是人们从每项经营活动中得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。背包问题在计算理论中属于NP—完全问题，其计算复杂度为O(2n),若允许物件可以部分地装入背包，即允许X可取从0.00到1.00闭区间上的实数，则背包问题就简化为极简单的P类问题，此时计算复杂度为O(n)。

4.1背包问题(knapsack problem)4.1.2遗传编码采用下标子集T的二进制编码方案是常用的遗传编码方法。串T的长度等于n(问题规模),Ti(1≤i≤n)=1表示该物件装入背包，Ti=0表示不装入背包。基于背包问题有近似求解知识，以及考虑到遗传算法的特点 (适合短定义距的、低阶的、高适应度的模式构成的积木块结构类问题),通常将Pi,Si按Pi/Si值的大小依次排列，即P1/S1≥P2/S2≥…≥Pn/Sn。

4.1背包问题(knapsack problem)4.1.3适应度函数在上述编码情况下，背包问题的目标函数和约束条件可表示如下。目标函数： J (T )=∑ Ti Pi约束条件：n

∑T Si=1 i

n

i=1

i

≤C

按照利用惩罚函数处理约束条件的方法，我们可构造背包问题的适应度函数f(T)如下式： f(T)= J(T)+ g(T)式中g(T)为对T超越约束条件的惩罚函数。

4.1背包问题(knapsack problem)惩罚函数可构造如下:

式中Em为Pi/S(1≤i≤n)i的最大值，β为合适的惩罚系数。

4.2货郎担问题(Traveling Salesman Problem—— TSP)在遗传其法研究中，TSP问题已被广泛地用于评价不同的遗传操作及选择机制的性能。之所以如此，主要有以下几个方面的原因： (1) TSP问题是一个典型的、易于描述却难以处理的NP完全(NP-complete)问题。有效地解决TSP问题在可计算理论上有着重要的理论价值。 (2) T

SP问题是诸多领域内出现的多种复杂问题的集中概括和简化形式。因此，快速、有效地解决TSP问题有着极高的实际应用价值。

4.2货郎担问题(Traveling Salesman Problem—— TSP)(3)TSP问题因其典型性已成为各种启发式的搜索、优化算法的间接比较标准，而遗传算法就其本质来说，主要是处理复杂问题的一种鲁棒性强的启发式随机搜索算法。因此遗传算法在TSP问题求解方面的应用研究，对于构造合适的遗传算法框架、建立有效的遗传操作以及有效地解决TSP问题等有着多方面的重要意义。

4.2货郎担问题(Traveling Salesman Problem—— TSP)问题描述：寻找一条最短的遍历n个城市的路径，或者说搜索整数子集X={1,2,…,n}(X的元素表示对n个城市的编号)的一个排列π(X)={v1,v2,…,vn},使

取最小值。式中的d(vi, vi+1)表示城市vi到城市vi+1的距离。

4.2货郎担问题(Traveling Salesman Problem—— TSP)4.2.1编码与适应度函数编码 1.以遍历城市的次序排列进行编码。如码串1 2 3 4 5 6 7 8表示自城市1开始，依次经城市2,3, 4,5,6,7,8,最后返回城市1的遍历路径。显然，这是一种针对TSP问题的最自然的编码方式。这一编码方案的主要缺陷在于引起了交叉操作的困难。

4.2货郎担问题(Traveling Salesman Problem—— 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圈中。这一编码方式有着与前面的“节点”遍历次序编码方式相类似的缺陷。

4.2货郎担问题(Traveling Salesman Problem—— TSP)3.间接“节点”编码方式。以消除“一点交叉”策略(或多点交叉策略)引起的非法路径问题。码串长度仍为n,定义各等位基因的取值范围为(n–i+ 1),i为基因序号，解码时，根据相应基因位的取值，从城市号集合中不回放地取一个城市号，直至所有城市号被取完。由于这种编码方式特征遗传性较差，因此现行的研究中很少采用。

4.2货郎担问题(Traveling Salesman Problem—— TSP)适应度函数适应度函数常取路径长度Td的倒数，即 f=1/Td若结合TSP的约束条件(每个城市经过且只经过一次),则适应度函数可表示为： f=1/(Td+α*Nt),其中Nt是对TSP路径不合法的度量(如取Nt为未遍历的城市的个数),α为惩罚系数，常取城市间最长距离的两倍多一点(如2.05*dmax)。

4.2货郎担问题(Traveling Salesman Problem—— TSP)4.2.2交叉策略问题：基于TSP问题的顺序编码(其它编码如以边的组合

状态进行编码也呈现相似特性),若采取简单的一点交叉或多点交叉策略，必然以极大的概率导致未能完全遍历所有城市的非法路径。如8城市的TSP问题的两个父路径为 1234|5678 8765|4321

4.2货郎担问题(Traveling Salesman Problem—— TSP)若采取一点交叉，且交叉点随机选为4,则交叉后产生的两个后代为 87655678 12344321显然，这两个子路径均未能遍历所有8个城市，都违反TSP问题的约束条件。可以采取上述构造惩罚函数的方法，但试验效果不佳。

4.2货郎担问题(Traveling Salesman Problem—— TSP)可能的解释：这一方法将本已十分复杂的TSP问题更加复杂化了。因为满足TSP问题约束条件的可行解空间规模为n!;而按构造惩罚函数的方法，其搜索空间规模变为nn;随着n的增大n!与nn之间的差距是极其惊人的。解决这一约束问题的另一种处理方法是对交叉、变异等遗传操作做适当的修正，使其自动满足TSP的约束条件。