第四章遗传算法与组合优化

《第四章遗传算法与组合优化》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第四章遗传算法与组合优化4.1背包问题（knapsackproblem）4.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项经营活动各自所需的资源消

2、耗，C是所能提供的资源总量，P的元素是人们从每项经营活动中得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。广义背包问题可以数学形式更精确地描述如下：最大化满足背包问题在计算理论中属于NP—完全问题，其计算复杂度为O(2n)，若允许物件可以部分地装入背包，即允许X，可取从0.00到1.00闭区间上的实数，则背包问题就简化为极简单的P类问题，此时计算复杂度为O(n)。4.1.2遗传编码采用下标子集T的二进制编码方案是常用的遗传编码方法。串T的长度等于n(问题规模)，Ti(1≤i≤n)＝1表示该物件装入背包，Ti＝0表示不装入背

3、包。基于背包问题有近似求解知识，以及考虑到遗传算法的特点（适合短定义距的、低阶的、高适应度的模式构成的积木块结构类问题），通常将Pi，Si按Pi/Si值的大小依次排列，即P1/S1≥P2/S2≥…≥Pn/Sn。4.1.3适应度函数在上述编码情况下，背包问题的目标函数和约束条件可表示如下。目标函数：约束条件：按照利用惩罚函数处理约束条件的方法，我们可构造背包问题的适应度函数f(T)如下式：f(T)=J(T)+g(T)式中g(T)为对T超越约束条件的惩罚函数，惩罚函数可构造如下:式中Em为Pi/S(1≤i≤n)i的最大值，β为合适的惩罚系数。4.2货郎担问题（Tra

4、velingSalesmanProblem——TSP）在遗传其法研究中，TSP问题已被广泛地用于评价不同的遗传操作及选择机制的性能。之所以如此，主要有以下几个方面的原因：(1)TSP问题是一个典型的、易于描述却难以处理的NP完全（NP-complete）问题。有效地解决TSP问题在可计算理论上有着重要的理论价值。(2)TSP问题是诸多领域内出现的多种复杂问题的集中概括和简化形式。因此，快速、有效地解决TSP问题有着极高的实际应用价值。(3)TSP问题因其典型性已成为各种启发式的搜索、优化算法的间接比较标准，而遗传算法就其本质来说，主要是处理复杂问题的一种鲁棒性强

5、的启发式随机搜索算法。因此遗传算法在TSP问题求解方面的应用研究，对于构造合适的遗传算法框架、建立有效的遗传操作以及有效地解决TSP问题等有着多方面的重要意义。问题描述：寻找一条最短的遍历n个城市的路径，或者说搜索整数子集X＝{1，2，…，n}（X的元素表示对n个城市的编号）的一个排列π(X)={v1，v2，…，vn}，使取最小值。式中的d(vi,vi+1)表示城市vi到城市vi+1的距离。4.2.1编码与适应度函数编码1．以遍历城市的次序排列进行编码。如码串12345678表示自城市l开始，依次经城市2，3，4，5，6，7，8，最后返回城市1的遍历路径。显然，

6、这是一种针对TSP问题的最自然的编码方式。这一编码方案的主要缺陷在于引起了交叉操作的困难。2．采用“边”的组合方式进行编码。例如码串24536871的第1个码2表示城市1到城市2的路径在TSP圈中，第2个码4表示城市2到城市4的路径在TSP圈中，以此类推，第8个码1表示城市8到城市1的路径在TSP圈中。这一编码方式有着与前面的“节点”遍历次序编码方式相类似的缺陷。3．间接“节点”编码方式。以消除“一点交叉”策略（或多点交叉策略）引起的非法路径问题。码串长度仍为n，定义各等位基因的取值范围为（n–i+1），i为基因序号，解码时，根据相应基因位的取值，从城市号集合中

7、不回放地取一个城市号，直至所有城市号被取完。由于这种编码方式特征遗传性较差，因此现行的研究中很少采用。适应度函数适应度函数常取路径长度Td的倒数，即f＝1/Td若结合TSP的约束条件（每个城市经过且只经过一次），则适应度函数可表示为：f＝1/(Td+α*Nt)，其中Nt是对TSP路径不合法的度量(如取付Nt为未遍历的城市的个数)，α为惩罚系数，常取城市间最长距离的两倍多一点(如2.05*dmax)。4.2.2交叉策略问题：基于TSP问题的顺序编码（其它编码如以边的组合状态进行编码也呈现相似特性），若采取简单的一点交叉或多点交叉策略，必然以极大的概率导致未能完全遍

8、历所有城市的非法路径。如