《遗传算法组合优化》由会员分享,可在线阅读,更多相关《遗传算法组合优化(9页珍藏版)》请在金锄头文库上搜索。
1、.第五章 遗传算法与组合优化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为一整数集合,即X1,2,3,n,T为X的子集,则问题就是找出满足约束条件,而使获得最大的子集T,即求Si和Pi的下标子集。在应用问题中,设S的元素是n项经营活动各自所需的资源消耗,C是所能提供的资源总量,P的元素是人们从每项
2、经营活动中得到的利润或收益,则背包问题就是在资源有限的条件下,追求总的最大收益的资源有效分配问题。广义背包问题可以数学形式更精确地描述如下:最大化满足背包问题在计算理论中属于NP完全问题,其计算复杂度为O(2n),若允许物件可以部分地装入背包,即允许X,可取从0.00到1.00闭区间上的实数,则背包问题就简化为极简单的P类问题,此时计算复杂度为O(n)。5.1.2 遗传编码采用下标子集T的二进制编码方案是常用的遗传编码方法。串T的长度等于n(问题规模),Ti(1in)1表示该物件装入背包,Ti0表示不装入背包。基于背包问题有近似求解知识,以及考虑到遗传算法的特点(适合短定义距的、低阶的、高适应
3、度的模式构成的积木块结构类问题),通常将Pi,Si按Pi/Si值的大小依次排列,即P1/S1P2/S2Pn/Sn。5.1.3 适应度函数在上述编码情况下,背包问题的目标函数和约束条件可表示如下。目标函数:约束条件:按照利用惩罚函数处理约束条件的方法,我们可构造背包问题的适应度函数f(T)如下式:f(T) = J(T) + g(T)式中g(T)为对T超越约束条件的惩罚函数,惩罚函数可构造如下:式中Em为Pi/S(1in)i的最大值,为合适的惩罚系数。5.2 货郎担问题(Traveling Salesman ProblemTSP)在遗传其法研究中,TSP问题已被广泛地用于评价不同的遗传操作及选择机
4、制的性能。之所以如此,主要有以下几个方面的原因:(1) TSP问题是一个典型的、易于描述却难以处理的NP完全(NP-complete)问题。有效地解决TSP问题在可计算理论上有着重要的理论价值。(2) TSP问题是诸多领域内出现的多种复杂问题的集中概括和简化形式。因此,快速、有效地解决TSP问题有着极高的实际应用价值。(3) TSP问题因其典型性已成为各种启发式的搜索、优化算法的间接比较标准,而遗传算法就其本质来说,主要是处理复杂问题的一种鲁棒性强的启发式随机搜索算法。因此遗传算法在TSP问题求解方面的应用研究,对于构造合适的遗传算法框架、建立有效的遗传操作以及有效地解决TSP问题等有着多方面
5、的重要意义。问题描述:寻找一条最短的遍历n个城市的路径,或者说搜索整数子集X1,2,n(X的元素表示对n个城市的编号)的一个排列(X) = v1,v2,vn,使取最小值。式中的d(vi, vi+1)表示城市vi到城市vi+1的距离。5.2.1 编码与适应度函数编码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表示
6、城市1到城市2的路径在TSP圈中,第2个码4表示城市2到城市4的路径在TSP圈中,以此类推,第8个码1表示城市8到城市1的路径在TSP圈中。这一编码方式有着与前面的“节点”遍历次序编码方式相类似的缺陷。3 间接“节点”编码方式。以消除“一点交叉”策略(或多点交叉策略)引起的非法路径问题。码串长度仍为n,定义各等位基因的取值范围为(n i + 1),i为基因序号,解码时,根据相应基因位的取值,从城市号集合中不回放地取一个城市号,直至所有城市号被取完。由于这种编码方式特征遗传性较差,因此现行的研究中很少采用。适应度函数适应度函数常取路径长度Td的倒数,即f1/Td若结合TSP的约束条件(每个城市经
7、过且只经过一次),则适应度函数可表示为:f1/(Td +*Nt),其中Nt是对TSP路径不合法的度量(如取付Nt为未遍历的城市的个数),为惩罚系数,常取城市间最长距离的两倍多一点(如2.05*dmax)。5.2.2 交叉策略问题:基于TSP问题的顺序编码(其它编码如以边的组合状态进行编码也呈现相似特性),若采取简单的一点交叉或多点交叉策略,必然以极大的概率导致未能完全遍历所有城市的非法路径。如8城市的TSP问题的两个父路径为 1 2 3 4 | 5 6 7 8 8 7 6 5 | 4 3 2 1若采取一点交叉,且交叉点随机选为4,则交叉后产生的两个后代为 8 7 6 5 5 6 7 8 1 2
8、 3 4 4 3 2 1显然,这两个子路径均未能遍历所有8个城市,都违反TSP问题的约束条件。可以采取上述构造惩罚函数的方法,但试验效果不佳。可能的解释:这一方法将本已十分复杂的TSP问题更加复杂化了。因为满足TSP问题约束条件的可行解空间规模为n!;而按构造惩罚函数的方法,其搜索空间规模变为nn;随着n的增大n!与nn之间的差距是极其惊人的。解决这一约束问题的另一种处理方法是对交叉、变异等遗传操作做适当的修正,使其自动满足TSP的约束条件。常用的几种交叉方法:1部分匹配交叉(PMX,Partially Matched Crossover)法PMX操作是由Goldberg和Lingle于198
9、5年提出的。在PMX操作中,先依据均匀随机分布产生两个位串交叉点,定义这两点之间的区域为一匹配区域,并使用位置交换操作交换两个父串的匹配区域。实例:如两父串及匹配区域为 A9 8 4 | 5 6 7 | 1 3 2 0 B8 7 1 | 2 3 0 | 9 5 4 6首先交换A和B的两个匹配区域,得到 A9 8 4 | 2 3 0 | l 3 2 0 B8 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
10、8 4 | 2 3 0 | 1 6 5 7 同理可得: 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 0 B8 7 1 | 2 3 0 | 9 5 4 6并根据匹配区域的映射关系,在其区域外的相应位置标记H,得到 A9 8 4 | 5 6 7 | 1 H H H B8 H 1 | 2 3 0 | 9 H 4 H再移动匹配区至起点位置,且在其后预留相等于匹配区域
11、的空间(H数目),然后将其余的码按其相对次序排列在预留区后面,得到 A”5 6 7 H H H 1 9 8 4 B”2 3 0 H H H 9 4 8 1最后将父串A,B的匹配区域相互交换,并放置到A”,B”的预留区内,即可得到两个子代: A”5 6 7 | 2 3 0 | 1 9 8 4 B”2 3 0 | 5 6 7 | 9 4 8 1虽然,PMX法与OX法非常相似,但它们处理相似特性的手段却不同。PMX法趋向于所期望的绝对城市位置,而OX法却趋向于期望的相对城市位置。3循环交叉(CX,cycle crossover)法Smith等人提出的CX方法与PMX方法和OX方法有不同之处。循环交叉
12、的执行是以父串的特征作为参考,使每个城市在约束条件下进行重组。设两个父串为 C9 8 2 1 7 4 5 0 6 3 D1 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 0 D1 8 2 4 7 6 5 1 0 9 34基于知识的交叉方法这种方法是一种启发式的交叉方法,按以下规划构造后代: (1)随机地选取一个城市作为子代圈的开始城市。 (2)比较父串中与开
13、始城市邻接的边,选取最小的边添加到圈的路径中。 (3)重复第(2)步,如果发现按最小边选取的规划产生非法路径(重复经过同一城市),则按随机法产生一合法的边,如此反复,直至形成一完整的TSP圈。使用这一方法,可获得较好的结果。在200个城市的TSP优化方面,已产生接近由模拟退火程序计算出的最优结果。不过,这一方法使用了基于问题的一些知识,损失了遗传算法的通用性和鲁棒性。关于TSP问题的遗传交叉方法还有各种各样的变形方法,一般来说,交叉方法应能使父串的待征遗传给子串,子串应能部分或全部地继承父串的结构特征和有效基因。5.2.3 变异技术从遗传算法的观点来看,解的进化主要靠选择机制和交叉策略来完成,
14、变异只是为选择、交叉过程中可能丢失的某些遗传基因进行修复和补充,变异在遗传算法的全局意义上只是一个背景操作。针对TSP问题,主要的变异技术如下述。1位点变异变异仅以一定的概率(通常较小)对串的某些位作值的变异。2逆转变异在串中,随机选择两点,再将这两点内的子串按反序插入到原位置中,如串A的逆转点为3,6,则经逆转后,变为AA 1 2 3 | 4 5 6 | 7 8 9 0A1 2 3 | 6 5 4 | 7 8 9 0这种变异操作对于TSP问题,就调整前后引起的TSP圈的长度变化而言用于最细微的调整,因而局部优化的精度较高;但码串绝对位置所呈现的“模式”变化较大,所需的计算也稍为复杂一点。3对换变异随机选择串中的两点,交换其值(码)。对于串AA1 2 3 4 5 6 7 8 9若对换点为4,7,则经对换后,A为A1 2 3 7 5 6 4 8 9这种变异操作在求解TSP问题优化算法中常被采用。在遗传算法中,对换变异操作对码串绝对位置所呈现的“模式”变化影响较小,所需的计算也简单一些,但局部优化精度稍差。4插人变异从串中随机选择1个码,将此码插入随机选择的插入点中间,对于上述A而言若取插入码为5,选取插入点为23之间则A1 2 5 3 4 6 7 8 95.2.4 选择机制和群体构成在遗传算法中,最常见的选择机制是依据适应度的比例概率选择机制;在有限规模的群体中,适应度较