求解大规模不对称指派问题的通用模拟退火算法.pdf

《求解大规模不对称指派问题的通用模拟退火算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第27卷第4期兰州交通大学学报Vol.27No.42008年8月JournalofLanzhouJiaotongUniversityAug.2008文章编号:100124373(2008)0420149203求解大规模不对称指派问题的通用模拟退火算法3吴艳群,董鹏(兰州交通大学交通运输学院730070)摘要:指派问题是运筹学中的一类经典问题,在生产实践中有广泛的应用.对于高效求解大规模尤其是人数与任务数不一致的指派问题,匈牙利算法存在一些不足之处.根据模拟退火算法的基本思想,设计了解的表示形式和邻域构造方法,实现了一种求解各种指派问题的通用的模拟退火算法.仿真实

2、验表示,该算法对可行解数量级在1080左右的指派问题进行求解时都有优异的性能.关键词:指派问题;匈牙利算法;模拟退火算法中图分类号:O221.1文献标识码:A指派问题是运筹学中的一类经典问题,在生产项任务,让xij=1,否则让xij=0,那么当指派问题实践中有广泛的应用,如:给工人分配工作,给工件要求极小化时的数学模型为nm分配机床,武器配置,供应商选择等.指派问题是0-minz=∑∑cxjxij,1规划的特例,也是运输问题的特例,可以用0-1i=1j=1n规划或运输问题的解法求解,但目前更有效的解法∑xij=1,i=1,2,⋯n;是库恩(W.W.Kuhn)于1

3、955年提出的匈牙利算i=1[1]4m法.然而,匈牙利算法的时间复杂度为O(n),只s.t.∑xij=1,j=1,2,⋯,m;能求解人数与任务数相同的指派问题,在实际问题j=1中存在很多人数和任务数比较大,尤其是人数与任xij∈{0,1},i=1,2,⋯,n,j=1,2,⋯,m.务数不一致的情况,运用上述算法来求解的效率并(1)不理想.本文将规模比较大而且人数与任务数不一实际上,指派问题的一个解就是从n个人中选致的问题称作大规模不对称的指派问题,设计实现出m个人的一个排列,第1个人去完成第1项任务,了一种通用的模拟退火算法,仿真实验表示该算法依此类推.人数为n任

4、务数为m的指派问题的可行m具有很高的实用价值.解数量为Pn.1指派问题及其数学模型2指派问题的算法指派问题通常可描述如下:某单位需要完成m匈牙利算法是求解标准指派问题(即人数和任项任务,现在恰好有n(n≥m)个人可承担这些任务数相等的指派问题)的通用算法,但步骤比较复4务.每项任务只能由一个人完成,每个人最多只能完杂,其时间复杂度为O(n).对于规模很大的指派问成一项任务,由于每个人的专长不同,各人完成不同题,匈牙利算法效率不高,不能解决不对称指派问题任务的费用(如时间)也不同.问应指派哪个人去完(即人数和任务数不相等,又称非标准指派问题).虽成哪项任务,使完成

5、n项任务的总费用最小?这类问然有许多改进匈牙利算法用于上述问题的求解,但题称为指派问题,其中人数与任务数相同的指派问都局限于人工求解规模很小的问题,而且由于实际题称为标准指派问题.上增加了许多步骤,导致其计算效率更差.在现实生如果用cij表示由第i个人完成第j项任务的费活中,不对称指派问题远比标准指派问题更加普遍,用,引入0-1变量xij,如果指派第i个人去完成第j而且通常情况下问题规模也很大,因此研究大规模3收稿日期:2008203210作者简介:吴艳群(19772),女,湖南邵阳人,讲师,硕士.150兰州交通大学学报第27卷指派问题特别是不对称指派问题的高效

6、算法十分必i:=i+1;END要.k:=0模拟退火算法是Kirkpatrick等于1983年首先WHILEk

7、k-1]);{交换team数组中第p个人使算法在多项式时间里给出一个近似最优解,比传和第n-k-1个人}统的局部搜索算法优越.在理论上业已证明,只要模k:=k+1;拟退火过程满足一定的要求,该算法将以概率1渐END[2]近收敛于全局最优解.根据标准模拟退火算法的其中每次交换两个人的位置可避免下次选取同原理,本文研究了指派问题的特点,设计了一种求解一个人,是该算法的关键.指派问题的通用模拟退火算法.3.4温度控制初始温度t0采用数值计算估计法确定,降温函3求解指派问题的模拟退火算法设计数选用tk+1=αtk.人数为n任务数为m时,由于对任3.1解的表示给的一个解,

8、通过交换任务产生的新解的