Matlab--模拟退火算法优化指派问题

1、引言

之前二狗已经分别介绍过了，如何用模拟退火算法和遗传算法，进行背包问题的求解。其实背包问题是可以看成是一个可以看成是一个比较特殊的，有线性约束的，0-1规划问题。在数学中还有很多其他特殊的问题，比如指派问题。指派问题可以看成是更特殊的多个背包问题（很多个背包求优，每个背包只能装一样物品）。基本指派问题一般可以描述为有n个任务n个人。要求为n个任务分配给指定的人来完成。并且在这种基本情况下，人和任务需要是一一对应的关系。不能有重复，不能出现两个人做同一个任务，或者一个人同时做两个任务的情况。（这些情况也属于指派问题的范畴，但属于更加复杂的情况，今天就不做讲解）。指派问题已经有了明确可解的算法，也就是我们大家都知道的匈牙利算法。同样的，这个问题也可以使用模拟退火来解决。今天我们就使用模拟退火算法来为大家演示，如何在指派问题进行优化？

2、 数据结构及重点讲解

指派矩阵如图

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

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

3、代码

% 结束条件为两次差小于一个特定量
% MarkoveLength 马尔科夫链长度
% DecayScale 温度衰减参数

MarkoveLength=1000;
DecayScale=0.9;
Temperature=1000; % initial temperature
t = 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;
end
disp(BestCost);
disp(assingnMatrix);
disp(BestAssign);

4、直观理解

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

视频观看链接：链接：https://pan.baidu.com/s/1NoO2hx-py6pIw__n1bIGZw 提取码：ku5o

例如：想获得Python入门至精通学习资料，请回复关键词Python即可。