5遗传算法组合优化.docVIP

第五章 遗传算法与组合优化 5.1 背包问题（knapsack problem） 5.1.1 问题描述 0/1背包问题：给出几个尺寸为S1，S2，…，Sn的物体和容量为C的背包，此处S1，S2，…，Sn和C都是正整数；要求找出n个物件的一个子集使其尽可能多地填满容量为C的背包。 数学形式： 最大化 满足 广义背包问题：输入由C和两个向量C＝(S1，S2，…，Sn)和P＝(P1，P2，…，Pn)组成。设X为一整数集合，即X＝1，2，3，…，n，T为X的子集，则问题就是找出满足约束条件，而使获得最大的子集T，即求Si和Pi的下标子集。 在应用问题中，设S的元素是n项经营活动各自所需的资源消耗，C是所能提供的资源总量，P的元素是人们从每项经营活动中得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。 广义背包问题可以数学形式更精确地描述如下： 最大化 满足 背包问题在计算理论中属于NP—完全问题，其计算复杂度为O(2n)，若允许物件可以部分地装入背包，即允许X，可取从0.00到1.00闭区间上的实数，则背包问题就简化为极简单的P类问题，此时计算复杂度为O(n)。 5.1.2 遗传编码 采用下标子集T的二进制编码方案是常用的遗传编码方法。串T的长度等于n(问题规模)，Ti(1≤i≤n)＝1表示该物件装入背包，Ti＝0表示不装入背包。基于背包问题有近似求解知识，以及考虑到遗传算法的特点（适合短定义距的、低阶的、高适应度的模式构成的积木块结构类问题），通常将Pi，Si按Pi/Si值的大小依次排列，即P1/S1≥P2/S2≥…≥Pn/Sn。 5.1.3 适应度函数 在上述编码情况下，背包问题的目标函数和约束条件可表示如下。 目标函数： 约束条件： 按照利用惩罚函数处理约束条件的方法，我们可构造背包问题的适应度函数f(T)如下式： f(T) = J(T) + g(T) 式中g(T)为对T超越约束条件的惩罚函数，惩罚函数可构造如下: 式中Em为Pi/S(1≤i≤n)i的最大值，β为合适的惩罚系数。 5.2 货郎担问题（Traveling Salesman Problem——TSP） 在遗传其法研究中，TSP问题已被广泛地用于评价不同的遗传操作及选择机制的性能。之所以如此，主要有以下几个方面的原因： TSP问题是一个典型的、易于描述却难以处理的NP完全（NP-complete）问题。有效地解决TSP问题在可计算理论上有着重要的理论价值。 TSP问题是诸多领域内出现的多种复杂问题的集中概括和简化形式。因此，快速、有效地解决TSP问题有着极高的实际应用价值。 TSP问题因其典型性已成为各种启发式的有哪些信誉好的足球投注网站、优化算法的间接比较标准，而遗传算法就其本质来说，主要是处理复杂问题的一种鲁棒性强的启发式随机有哪些信誉好的足球投注网站算法。因此遗传算法在TSP问题求解方面的应用研究，对于构造合适的遗传算法框架、建立有效的遗传操作以及有效地解决TSP问题等有着多方面的重要意义。 问题描述： 寻找一条最短的遍历n个城市的路径，或者说有哪些信誉好的足球投注网站整数子集X＝{1，2，…，n}（X的元素表示对n个城市的编号）的一个排列π(X) = {v1，v2，…，vn}，使 取最小值。式中的d(vi, vi+1)表示城市vi到城市vi+1的距离。 5.2.1 编码与适应度函数 编码 以遍历城市的次序排列进行编码。 如码串1 2 3 4 5 6 7 8表示自城市l开始，依次经城市2，3，4，5，6，7，8，最后返回城市1的遍历路径。显然，这是一种针对TSP问题的最自然的编码方式。这一编码方案的主要缺陷在于引起了交叉操作的困难。 采用“边”的组合方式进行编码。 例如码串2 4 5 3 6 8 7 1的第1个码2表示城市1到城市2的路径在TSP圈中，第2个码4表示城市2到城市4的路径在TSP圈中，以此类推，第8个码1表示城市8到城市1的路径在TSP圈中。这一编码方式有着与前面的“节点”遍历次序编码方式相类似的缺陷。 间接“节点”编码方式。 以消除“一点交叉”策略（或多点交叉策略）引起的非法路径问题。码串长度仍为n，定义各等位基因的取值范围为（n – i + 1），i为基因序号，解码时，根据相应基因位的取值，从城市号集合中不回放地取一个城市号，直至所有城市号被取完。由于这种编码方式特征遗传性较差，因此现行的研究中很少采用。 适应度函数 适应度函数常取路径长度Td的倒数，即 f＝1/Td 若结合TSP的约束条件（每个城市经过且只经过一次），则适应度函数可表示为： f＝1/(Td +α*Nt)， 其中Nt是对TSP路径不合法的度量(如取付Nt为未遍历的城市的个数)，α为惩罚系数，常取城市间最长距离的两倍多一点(如