基于遗传算法的集合覆盖问题scp

基于遗传算法的集合覆盖问题scp

20世纪70年代，美国密根大学的约翰霍拉德教授提出了一种算法，该算法用于研究自然和人工系统的自适应行为。在此基础上，通过学生knehdejang和大卫戈尔伯格在各种优化问题上的改进和普及，这种遗传统计方法可以广泛应用于各种优化问题。遗传统计作为一种新的优化搜索算法，与传统的优化算法相比，具有适应性强、抗干扰性强、鲁棒性强、适合执行和整体搜索等显著特征。近年来，它引起了许多科学家的注意，越来越多的科学研究和应用产生了很大的影响。它取得了许多良好的研究成果广泛应用于自动控制、计算机科学、机器人学、模式识别和神经网络等领域。集合覆盖问题(SCP)是经典组合优化问题之一,被广泛应用到航空的人员行程安排、电路设计、运输的车辆路线安排等领域.该问题已被证明是一个NP完全问题.集合覆盖问题形式上可以描述如下:令A=(aij)是一个m行,n列的0-1矩阵.C=(cj)是一个n维整数向量.令M={1,…,m},N={1,…,n}表示矩阵A的行向量和列向量.值cj(j∈N)表示列j的代价.不失一般性,我们假定cj>0,j∈N.如果aij=1,我们则认为列j∈N覆盖了行i∈M.集合覆盖问题(SCP)要求一个最小代价的子集合S⊆N,这样每一行i∈M至少被一列j∈S覆盖.SCP的一个自然的数学模型可以描述如下:v(SCΡ)=min∑j∈Νcjxj,(1)v(SCP)=min∑j∈Ncjxj,(1)服从于∑j∈Νaijxj≥1,j∈Μ,(2)xj∈{0,1},j∈Ν.ifj∈Sthenxj=1elsexj=0.(3)服从于∑j∈Naijxj≥1,j∈M,(2)xj∈{0,1},j∈N.ifj∈Sthenxj=1elsexj=0.(3)例如,上图中A为一个6×8矩阵,向量C为矩阵A的列向量代价值.向量x为矩阵A的一个集合覆盖,而本例的最小覆盖为x=(0,0,0,1,0,1,0,1),代价为15.1基于启发式遗传计算的方法1.1遗传算法步骤遗传算法是一种基于生物进化原理构想出来的搜索最优解的仿生算法,它模拟基因重组与进化的自然过程,把待解决问题的参数编成二进制码或十进制码(也可编成其它进制码),即基因,若干基因组成一个染色体(个体).许多染色体进行类似于自然选择、配对交叉和变异运算,经过多次重复迭代(即世代遗传)直至得到最后的优化结果.遗传算法的步骤如下:1)初始化第0代种群P0;2)对第i代种群Pi迭代执行步骤(i)～(v),直到满足停止准则;(i)计算Pi中每个个体的适应值,并按照适应值的大小对所有个体进行排序;(ii)将Pi中适应值最佳的个体加入Pi+1;(iii)按照适应值的大小顺序在Pi中选择两个父体;(iv)按概率选择杂交算子或变异算子对两父体进行遗传操作,将生成的个体加入Pi+1;(v)如果Pi+1的规模已经与Pi持平则i←i+1并转2,否则转iii;3)将最终种群中适应值最佳的个体作为遗传算法的结果.1.2基于遗传交叉的启动算法1.2.1优化染色体结构对于特殊应用问题的遗传算法的设计第一步是设计一种合适的表示方案.对于集合覆盖问题,因为矩阵A是0-1矩阵,向量x的元素也是0或1,因为用0-1二进制表示是一个显而易见的选择.这里我们用一个n位的二进制串作为染色体结构,这里n是矩阵A的列数,第i位的值“1”意味着第i列被选择.用二进制表示进行遗传操作有个重要问题要必须考虑,那就是可能产生不可靠的结果.产生的染色体并不能覆盖集合,这样就会影响遗传效率.有两种方法处理这种不可靠结果.一种方法是应用一个类似惩罚函数去处理不可行的解决方案,比如比较极端的惩罚方法是丢弃该染色体,并产生新染色体来代替这个不可靠染色体.另一个方法是设计一个启发操作算子,把不可行的染色体转变成可行的染色体.我们选择后一个方法,用启发式操作,因为一个好的惩罚函数经常很难定义.1.2.2性能代价比优先算法正如上边所提起的,由于变异操作引起的染色体并不适合问题集合(如,一些行没有覆盖),这导致遗传算法收敛的速度变慢,因此需要让所有染色体有个合理的补充操作.这里,我们提出一个启发式操作算子,这个算子不仅仅保持所产生的染色体的可靠性,而且提供一个额外的局部优化过程,目的使遗传算法更有效率.对于每个染色体所覆盖集合的情况不外乎两种情况:一种是染色体不覆盖集合,另一种是覆盖了集合,但有冗余,造成改染色体的代价不是较优.对于第一种情况的处理办法一种是丢弃,但有可能丢失最优解,导致收敛的速度变慢;本算法采用的是另一种解决方法,通过性能代价比较优的列来弥补该染色体,使该染色体以较优代价保留在种群中.性能代价比是指某列所能覆盖的行数与该列的代价比.对于第二种情况,本算法采用的是通过保留性能代价比较优且能覆盖集合的列,去除多余的冗余列来替代该冗余染色体,并保留在种群中.具体的算法如下.·修补染色体.对于一个染色体,很容易判断是否覆盖一个集合.如果不覆盖集合,染色体在遗传进化过程中不利于收敛,因此通过修补染色体使之能覆盖集合是一个很好的办法.修补染色的方法很多,如果修补后的染色体的代价过大,就会产生过多的冗余,就会造成另一个极端.早期有人提出用贪心算法来补偿染色体,但这种算法只考虑染色体中基因的代价而并没有考虑到染色体中的基因在集合中的性能.本算法采用一个性能代价比优先算法找出更适合的基因来补偿染色体,使得补偿后的染色体为较优的染色体.这里说的性能指染色体中的某位基因所对应集合中的列的含1的个数,如果该列含1的个数多,则该列覆盖的行数就多,说明该基因的性能比较高.采用同样的方法就可以找出其他位置的基因就可以覆盖集合.为了找出较优的染色体,还要考虑每个基因的代价,所以对于每个基因采用公式f(j)=(r∑i=0Aij)/cjf(j)=(∑i=0rAij)/cj来计算基因的性能代价比,其中r表示集合A的行数,cj为第j列的代价.性能代价比较高的基因优先选择,从而保证补偿后的染色体能覆盖集合且代价较优.该算法如下.令I:所有行的集合;J:所有列的集合;U:未覆盖A的行的集合;Col:集合A的列数;Pj:新增加一个染色体中的基因位置,j∈J对于每个新产生的未覆盖集合的染色体进行如下处理:1)产生该染色体的U;2)∀i‚i∈U,Ρ(k)=min(Col∑j=1Aij/cj),k∈J2)∀i‚i∈U,P(k)=min(∑j=1ColAij/cj),k∈J;3)对每一个k,修补该染色体;4)如果修补后的染色体不覆盖,转到1.·消除染色体的冗余.一个染色体含有“1”的基因的多少对该染色体覆盖集合A的状况有很大关系,如果含“1”不多,很可能不能覆盖集合A,如果含“1”过多,则该染色体的代价也相应过大.这样的染色体经过遗传操作后,并不利于收敛到较优解.为了使染色体在种群中的效率较高,一种采用的办法就是消除染色体中冗余基因,使得消除后的染色体还能覆盖集合A,并使该染色体的代价减小.本算法采用性能代价比优先方法.为了更有效率的找出冗余基因,我们根据集合A和染色体含“1”基因的位置产生两个中间向量,通过对该中间向量的操作找出其中较优的基因,并删除其余冗余的基因.一个中间向量a用染色体中含“1”基因的位置来表示,另一个中间向量b用来表示中间向量a中选中一个性能代价比较优的基因后没有覆盖集合A的行号.依次根据性能代价比找出较优的基因,计算中间向量b,中间向量a中的基因被选中后就在向量a中删除该基因,因随着中间向量a中被选种的基因增多,中间向量b的个数减少,直到中间向量b为空,表示所选的基因覆盖了集合A.1)计算向量a中每个基因的性能代价比;选出性能代价比最大的基因,记录该基因在染色体中的位置并初始化中间向量a;2)根据该性能代价比最大的基因计算出未覆盖集合A的行号,并初始化中间向量b;3)计算中间向量a中每个基因的性能代价比并选出最大的基因;4)计算该基因覆盖集合的行号,并在向量b中去除这些行号;5)在中间向量a中删除该基因;6)如果中间向量b不空,则跳转到3;7)如果中间向量b为空,则让未被选出的含“1”基因变异成“0”.2遗传参数的选择2.1种群数目的影响在应用遗传算法解决实际问题的过程中人们发现,种群对遗传算法所求得的解的质量有一定的影响,选择适当的种群大小可以提高算法的性能.种群数目如果过大,虽然可以在比较小的代数收敛到最优解,但会执行效率降低.种群数目如果过小,则收敛过慢.在集合覆盖问题中,本算法并没有采取对种群大小进行严格的限制,对于大多数情况,一般采用染色体的长度于集合密度的乘积作为种群的大小的一个大概范围.对于一些特殊情况,如集合行、列值较小,集合密度过大的情况,则再适当的调整.2.2种群中染色体被选择在父代的选择是在种群中每个个体赋予产生后代的机会,这有很多广泛的可用方法,包括按比例选择,锦标赛选择和轮盘赌选择.这里选择的是按比例选择.种群中每个染色体被选择的概率为pi=(1/fi)/Ν∑i=1(1/fi)pi=(1/fi)/∑i=1N(1/fi),其中fi为染色体的适应度,N为种群大小.用这种选择技术可以算出最大代价的染色体.但为了求最小代价,我们可以采用(Col∑i=1fi)-fi(∑i=1Colfi)−fi作为染色体的适应度,在根据按比例选择找出父代染色体.2.3交叉率的生成交叉(crossover)是引入新个体的主要方法,在被选择的染色体内产生一个随机数设为断点,将双亲在断点一侧的基因进行交叉交换,生成新的后代.设置一个交叉率(pc)用来控制交配池中参与交叉的染色体个数,一定的交叉率可以保证交配池中不断产生新个体,但又不至于新个体数目太多,导致遗传秩序遭到破坏.交叉的方法也有很多,不同的交叉方法对应的交叉率也是不一致的,因本算法是对染色体进行启发式修改,不同的交叉方法对种群的影响相近.因此本算法采用单点一致交叉,交叉率经测试采用0.6较为适宜.2.4变异率范围的确定变异(mutation)是产生新个体的另一种途径,它是染色体上的基因发生突变的过程,可以提供初始种群中不存在的基因,为种群提供新的内容.变异产生的是真正意义上的新个体,使得个体可以尽可能的覆盖整个搜索空间,保证遗传算法具有全局搜索功能.变异率是一个种群中发生变异的基因数目与全体基因数的比值.在应用遗传算法解决不同问题时,选取运行的变异率是影响算法效率的重要因素.控制一个合理水平的变异率既可获得新基因,又不会失去从双亲继承的好的特性.对于集合覆盖问题,采用对多个不同集合应用本算法求解,根据变异率和集合覆盖值建立坐标系,近似描绘变异率对集合覆盖影响的曲线.因为不同的集合对应的函数覆盖值的大小不同,为了显示方便,根据函数覆盖值范围转换成0,1之间.根据计算的离散点模拟曲线.如图1为测试几个不同集合的图象,这些集合在后边有说明,见图1.根据图1,对于不同的集合,都可用下边方程来模拟此曲线:其中r为集合的行数,Col为集合的列数当r≥Col则y=Col/r*x+1/Col*1/xr<Col则y=Col/r*(1-x)+1/Col*1/(1-x)从图像上可以看出,为了得到最优解的变化率范围就是在曲线的最小值附近,令y=0,解得当r≥Col‚x=√r/Colr≥Col‚x=r/Col−−−−−√,当r＜Col‚x=1-√r/Colr＜Col‚x=1−r/Col−−−−−√.可见,较优的变异率范围由上式确定.2.5是否收敛的理论的终止条件遗传算法在实际操作中都要经过多代进化,直到适应值趋于稳定,或者找到最优解或者达到规定的遗传代数,进化过程结束.由于遗传算法不包含目标函数的梯度等信息,所以在进化过程中无法确定个体在解空间的位置,也就无法给出是否收敛的理论判据.通常的做法是在达到预先规定的进化代数时停止进化,本文采用的就是这种做法,最大进化代数定为1000代.但是也可以采用其他的停止准则,例如当相邻两代的最佳适应值之差小于某个事先确定的阈值时停止进化.3测试集合的细节本文提出的算法用c语言进行编写,并在主频1G,内存2G的PC机上运行.被测试的集合采用JEBeasley在OR-Library提供的测试集合,地址在http://mscmga.ms.ic.ac.uk/info.html提供的.这些测试集合的细节在下表中给出.对于scpcyc06集合,采用的种群大小为10,通过采用不同的交叉率、变异率,计算出的最小代价值.根据下边的计算结果,我们发现较好的交叉率在0.6左右.scp42集合为行大于列的结合,scpcyc07集合为列大于行的集合,根据这两个集合测试,对于不同的种群大小,相同的交叉率,我们发现变异率和最小代价的关系符合图1的结果.下表为采用启发式遗传算法和未采用启发式遗传算法所计算最小代价