模拟退火算法求解指派问题新探

第２８卷第４期　吉林建筑工程学院学报　Ｖ０Ｉ＿２８　Ｎｏ．４　２０１１年８月　Ｊｏｕｒｎａｌ　ｏｆ　Ｊｉｌｉｎ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ａｒｃｈｉｔｅｃｔｕｒｅ＆Ｃｉｖｉｌ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ａｕｇ．２０１１　模拟退火算法求解指派问题新探水　赵　越　（吉林建筑工程学院计算机科学与工程学院，长春１３０１１８）　摘要：模拟退火算法是一种随机搜索算法，能渐进地收敛干全局最优解．指派问题是组合优化问题中的一种，可用　模拟退火算法来解此问题．模拟退火算法解决指派问题时，需要考虑实现此算法的技术问题，例如解的形式、初始　温度的计算等．实验结果表明，该方法能够以一定的概率跳出局部最优。从而实现全局寻优．　关键词：模拟退火算法；指派问题；组合优化　中图分类号：ＴＰ　３９１　文献标志码：Ａ　文章编号：１００９—０１８５（２０１ｔ）０４—００６１－０３　Ａ　Ｎｅｗ　Ｗａｙ　ｔｏ　Ｓｏｌｖｅ　Ａｓｓｉｇｎｍｅｎｔ　Ｐｒｏｂｌｅｍ　Ｕｓｉｎｇ　Ｓｉｍｕｌａｔｅｄ　Ａｎｎｅａｌｉｎｇ　Ａｌｇｏｒｉｔｈｍ　ＺＨＡ０　Ｙｕｅ　（Ｓｃｈｏｏｌ　ｏｆＣｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｊｉｌｉｎ　Ｉｎｓｔｉｔｔｕｅ　ｏｆＡｒｃｈｉｔｅｃｔｕｒｅ　ａｎｄ　Ｃｉｖｉｌ　Ｅｎｇｉｅｎｅｒｉｇｎ，Ｃｈａｎｇｃｈｕｎ，Ｃｈｉｎａ　１３０１１８）　Ａｂｓｔｒａｃｔ：Ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ａ　ｒａｎｄｏｍ　ｓｅａｒｃｈ　ａｌｇｏｒｉｔｈｍ，ａｎｄ　ｉｔ　ｃａｎ　ｂｅ　ｇｒａｄｕａｌ　ｃｏｎｖｅｒｇｅｎｃｅ　ｉｎ　ｔｈｅ　ｇｌｏｂａｌ　ｏｐｔｉｍａｌ　ｓｏｌｕｔｉｏｎ．Ｔｈｅ　ａｓｓｉｇｎｍｅｎｔ　ｐｒｏｂｌｅｍ　ｉｓ　ｏｎｅ　ｏｆ　ｃｏｍｂｉｎａｔｏｒｉａｌ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍｓ．Ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ｂｅ　ｕｓｅｄ　ｔｏ　ｓｏｌｖｅ　ａｓｓｉｇｎｍｅｎｔ　ｐｒｏｂｌｅｍ．Ｗｈｅｎ　ｕｓｉｎｇ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ，ｖａｒｉｏｕｓ　ｔｅｃｈｎｉｃａｌ　ｉｓｓｕｅｓ　ｏｆ　ｔｈｅ　ａｌｇｏ—　ｒｉｔｈｍ　ｍｕｓｔ　ｂｅ　ｃｏｎｓｉｄｅｒｅｄ，ｓｕｃｈ　ａｓ　ｔｈｅ　ｆｏｒｍ　ｏｆ　ｓｏｌｕｔｉｏｎ，ｔｈｅ　ｉｎｉｔｉｌａ　ｔｅｍｐｅｒａｔｕｒｅ　ａｃｃｏｕｎｔ　ｅｔｃ．Ｅｘａｍｐｌｅｓ　ｓｉｍｕｌａｔｉｏｎ　ｓｈｏｗｓ　ｔｈａｔ　ｔｈｅ　ｍｅｔｈｏｄ　ｃａｎ　ｊｕｍｐ　ｏｕｔ　ｏｆ　ｌｏｃａｌ　ｏｐｔｉｍｕｍ　ｓｏｌｕｔｉｏｎ　ｗｉｈｔ　ａ　ｃｅｒｔａｉｎ　ｐｒｏｂａｂｉｌｉｔｙ　ｔｏ　ａｃｈｉｅｖｅ　ｇｌｏｂａｌ　ｏｐｔｉｍｉｚａ—　ｔｉｏｎ．　Ｋｅｙｗｏｒｄｓ：ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ａｌｇｏｒｉｔｈｍ；ａｓｓｉｇｎｍｅｎｔ　ｐｒｏｂｌｅｍ；ｃｏｍｂｉｎａｔｏｒｉａｌ　ｏｐｔｉｍｉｚａｔｉｏｎ　０　引言　在企业运营与管理中，管理者总是希望把人员最佳分派以发挥其优势，从而降低成本，提高效益．例如，　某公司需完成／／／，项任务，恰好有／／，名员工可承担这些任务（／／，≥ｍ）；每项任务只能由一名员工来做，每名员　工也只能做一项任务；不同的员工完成各项任务的成本不同．问怎样分配任务公司的花费最小…这类问题，　被称为标准的指派问题（Ａｓｓｉｇｎｍｅｎｔ　Ｐｒｏｂｌｅｍ）．模拟退火算法（Ｓｉｍｕｌａｔｅｄ　Ａｎｎｅａｌｉｎｇ，简称ＳＡ）的思想最早是由　Ｍｅｔｒｏｐｏｌｉｓ等（１９５３年）提出的，１９８３年Ｋｉｒｋ　Ｐａｔｉｒｃｋ等成功的将其用于组合优化问题中．模拟退火算法在某　初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即局部　最优解能概率性地跳出并最终趋于全局最优　Ｊ．本文将模拟退火算法应用于指派问题的求解过程中．　１指派问题模型　有　个人，ｍ项任务（ｎ≥ｍ），一个人最多可以完成一项任务，而一项任务只能由一个人做．ｃＯ－表示第ｉ个　人做第　项任务的费用，找出任务分配方案，使得总费用最小．首先引入一个０—１变量　：　收稿日期：２０１１一Ｏ１一ｌ３．　作者简介：赵越（１９８２一），男，吉林省通化市人，讲师．　｝基金项目：吉林省教育厅“十一五”科学技术研究项目（吉教科合字２０１０第３１４号）　６２　吉林建筑工程学院学报　Ａ　１０（第ｉ个人不做第Ｊ．项任务）　模型为：　ｙ　『１　（第ｉ个人做第　项任务）　（１）　ａｒｉｎ∑∑ｃ－　｛／　Ｈ　（２）　ｆ∑　（Ｊ．＝１，２，…，　）　．　（３）　【∑　（　＝１，２，…，ｎ）　２模拟退火算法　模拟退火算法的基本思想为：将组合优化问题比作一个热力学系统，将优化问题的费用函数　ｓ）比拟　成系统的能量Ｅ（ｉ），组合优化问题的解ｓ比拟成退火过程中能量的状态ｉ．把优化求解过程比拟成系统逐步　降温（迭代搜索）达到最低能量状态的退火过程．通过模拟退火过程获得优化问题的全局最优解，其算法先　确定一个能量函数即目标函数，求解最优化问题一般通过Ｍｅｔｒｏｐｏｌｉｓ抽样和退火两个过程实现．该算法在接　受较优解的同时，还在一定范围内接受差解，从而使模拟退火算法能跳出局部最优解而获得最优解　．　模拟退火算法步骤　Ｊ：　ＳＴＥＰ　１：任选一个初始解ｓ０；５：＝ｓｏ；ｋ：＝０；ｔ０：＝ｔ　（初始温度）；　ＳＴＥＰ　２：若在该温度达到内循环停止条件，则到ＳＴＥＰ　３；否则，从邻域Ｎ（ｓ）中随机选一个（新解）ｑ，计算　＝　ｓ）一　ｇ）；若　≤０，则ｓ：＝ｑ；否则若ｅｘｐ（一　／ｔ　）时，则ｓ：＝ｇ；重复ＳＴＥＰ　２．　ＳＴＥＰ　３：ｔ　＋１＝ｄ（ｔ　）；ｋ：＝ｋ＋１；若满足停止条件，终止计算；否则，回到ＳＴＥＰ　２．　２．１指派问题解　的形式　ｎ表示员工数目，ｍ表示任务数．在输出结果时，用一个２×ｍ的二维数组来表示解，即第一行表示各项　工作，由１到ｍ；第二行表示任务分配，即从ｎ个人中选择ｍ个做各项工作．　显然该解满足模型中的约束条件（３），如果此解还满足条件（１），（２），则为可行解，否则为不可行解．　２．２邻域的生成　模拟退火算法中，解的搜索过程是在一个能量状态点附近搜索另外一个能量状态点．在温度ｔ　时刻，指　定一个可行解ｓ，然后任意交换两个状态的量，生成一个新的解ｇ，如果满足模型的约束条件（１）和（２），则ｑ　就是ｓ邻域中的一个可行解．解ｓ的邻域就是由以上方法生成的可行解．　２．３新解的接受与淘汰　在当前解的邻域中搜索到一个新解，是否接受，要看新解的目标函数值（费用）和当前最优解的目标函　数值（费用）的差　，如果　≤Ｏ，则说明新解的目标函数值较小，当前值被新值代替；否则　＞０，看新解　的接受概率是否大于一个在０到ｌ之间的随机数　，若大于，则接收新解为当前最优解，否则舍弃该解．　２．４初始温度以及退温函数　初始温度ｔ。＝硒，Ｋ是充分大的数，其中　＝ｍａｘ｛　ｓ）ｌ　ｓ∈　｝一ｒａｉｎ｛ｆ（ｓ）Ｉ　ｓ∈Ｄ｝　，在实际计算中，可以　选取Ｋ＝１０，２０，１００…等试验值，ｍａｘ｛　ｓ）ｌ　ｓ∈Ｄ｝和ｒａｉｎ｛ｆ（ｓ）ｊ　５∈Ｄ｝是解空间随机取的两个解的目标函数　值．退温函数采用ｔ　＋１＝ｏｃｔ　，其中０＜　＜１，　越接近１，温度下降越慢．　２．５　内外循环中止条件　内循环是在温度￡　时，采用固定长度法结束内循环．因为，指派问题的邻域是两个状态的任务交换生产　新的解，其大小为ｎ（ｎ一１）／２，我们可以选取迭代步数为　（ｎ一１）／２．外循环采用零度法，模拟退火的最终温　度为零，因此可以给定一个比较小的正数　，当温度ｔ　≤　时，外循环停止．　３　仿真数据以及运行结果分析　假设人数Ｐ　＝６，工作　＝４，价值矩阵Ｃ（６，４）为：　第４期　赵越：模拟退火算法求解指派问题新探　６３　２６　４ｌ　２Ｏ　４１　１８　４３　７　２１　４９　４９　４　４０　１８　２７　２６　２６　１７　２ｌ　３８　２２　４７　３８　２３　１９　当ｒａｔｅ＝１０，Ｋ＝０．６时，算法仿真及所得最优分配方案如下．　总迭代步数：１６８　最终解：　工作：１　２　３　４　分配：２　５　３　６　最优解的目标值是：６２　由此可见，该算法可以实现全局寻优．其寻优过程中以一定的概率接受最优解，跳出局部最优，实现全　局寻优．　４　结语　应用模拟退火算法，能够找到指派问题最优解分配方案．仿真结果表明了该算法的有效性．从最优解可　以看到，该算法可以跳出局部最优，从而实现全局最优．　参考文献　［１］殷人昆，吴阳，张晶炜．蚁群算法解决指派问题的研究和应用［Ｊ］．计算机工程与科学，２００８，３０（４）：４３—４４　［２］王凌．智能优化算法及其应用［Ｍ］．北京：清华大学出版社，２００１，３５—３９．　［３］周晶，何建敏，盛昭瀚．一类新型的指派问题的多目标模型［Ｊ］．系统工程学报，１９９９（２）：１１９—１２１．　［４］邢文训，谢金星．智能优化算法及其应用［Ｍ］．北京：清华大学出版社，１９９９：９４—１２６．