模拟退火算法在指派问题优化中的应用实践

1、引言

之前二狗已经分别介绍过了,如何用模拟退火算法和遗传算法,进行背包问题的求解。其实背包问题是可以看成是一个可以看成是一个比较特殊的,有线性约束的,0-1规划问题。在数学中还有很多其他特殊的问题,比如指派问题。指派问题可以看成是更特殊的多个背包问题(很多个背包求优,每个背包只能装一样物品)。

基本指派问题一般可以描述为有n个任务n个人。要求为n个任务分配给指定的人来完成。并且在这种基本情况下,人和任务需要是一一对应的关系。不能有重复,不能出现两个人做同一个任务,或者一个人同时做两个任务的情况。(这些情况也属于指派问题的范畴,但属于更加复杂的情况,今天就不做讲解)。指派问题已经有了明确可解的算法,也就是我们大家都知道的匈牙利算法。同样的,这个问题也可以使用模拟退火来解决。今天我们就使用模拟退火算法来为大家演示,如何在指派问题进行优化?


2、 数据结构及重点讲解

指派矩阵如图

模拟退火算法优化指派问题的图1

每行代表每个人单独做每个工作的时间或费用(cost),每列代表每个工作分别由每个人完成时的cost。矩阵中位于(i,j)的元素是第i个人做第j个工作的cost。将这四个元素相加即为整个问题的最优解。由于是cost,当然越小越好。

模拟退火算法这个名称的来源大家已经知道了,我们就不再赘述。这里要提的是退火算法中的马尔可夫链。如果将每个特定时间序列上的解空间状态看成离散的,并将这些离散状态连成一条链的话。那么整个求解过程就是一条马尔可夫链,这一个时刻的状态,只和上一个相邻的时间点上的状态相关,而与之前的时间点状态都无关。这听起来有点像还钱。我不管谁欠你的钱,但是我只知道你欠我钱,我只管你要。SA中马尔可夫链的长度就是模拟退火中温度的变化。

还有一个属于模拟退火算法的特色概念,也就是它跳出局部极小值解的方法:将原有的目标函数值和新求出的目标函数值相减,得出一个delta值。如果这个值是小于零的,证明解优化,否则的话,就以一定的概率去接受它。这个概率是随着不同的温度和不同delta变化而变化的。


3、代码

% 结束条件为两次差小于一个特定量

% MarkoveLength 马尔科夫链长度

% DecayScale 温度衰减参数

MarkoveLength=1000;

DecayScale=0.9;

Temperature=1000;

% initial temperaturet = 1;

% final temperature%指派矩阵,每个人做每件事所需要的费用

assingnMatrix=[17,1,9,15,16;8,15,17,9,11;5,8,4,18,12;20,6,14,9,7;17,14,2,10,1];

% 初始解x=[1,2,3,4,5];

totalCost = 0;

for i=1:5  

totalCost=totalCost+assingnMatrix(i,x(i));

end

BestCost=totalCost;

BestAssign=x;while (Temperature > t || abs(deltaCost)<2)    

   for i = 1:MarkoveLength      

      r = randperm(5,2);

%产生两个随机数,用来交换x中的任务分配顺序        

       r1=r(1);    

   r2=r(2);    

   temp=x(r1);    

   x(r1)=x(r2);    

   x(r2)=temp;        

       %  计算        

       totalCost=0;        

       for k=1:4            

           totalCost=totalCost+assingnMatrix(k,x(k));        

       end        % 判断费用是否优化      

      deltaCost=totalCost-BestCost;      

       if deltaCost <= 0            

           BestCost = totalCost;

           % 若费用减少则无条件接受          

           BestAssign=x;        

       else            

           if (rand()<exp(-deltaCost/Temperature))              

               BestCost = totalCost;  %否则在一定概率下接受              

               BestAssign=x;          

           end      

       end  

   end  

   Temperature=Temperature*DecayScale;

   

enddisp(BestCost);

disp(assingnMatrix);

disp(BestAssign);

4、直观理解

说了这么多,初学的狗子们可能会有点不知所措。在看完了代码之后,不如看一下下面的二维曲面搜寻小动画。这里以一个二维寻优函数为例,不同的颜色代表着不同的温度。圆圈代表着在搜索范围内,计算和比较邻居中比当前解更好(或接受概率更大)的解。每次跳跃代表着取了更好的解,也就是用新解代替旧解。这个过程视不同目标函数及约束条件变化而变化,希望狗子们忽略细节,领会精神。


免责声明:本文系网络转载或改编,未找到原创作者,版权归原作者所有。如涉及版权,请联系删

QR Code
微信扫一扫,欢迎咨询~

联系我们
武汉格发信息技术有限公司
湖北省武汉市经开区科技园西路6号103孵化器
电话:155-2731-8020 座机:027-59821821
邮件:tanzw@gofarlic.com
Copyright © 2023 Gofarsoft Co.,Ltd. 保留所有权利
遇到许可问题?该如何解决!?
评估许可证实际采购量? 
不清楚软件许可证使用数据? 
收到软件厂商律师函!?  
想要少购买点许可证,节省费用? 
收到软件厂商侵权通告!?  
有正版license,但许可证不够用,需要新购? 
联系方式 155-2731-8020
预留信息,一起解决您的问题
* 姓名:
* 手机:

* 公司名称:

姓名不为空

手机不正确

公司不为空