专栏首页matlab爱好者模拟退火算法优化指派问题

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

1、引言

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

2、 数据结构及重点讲解

指派矩阵如图

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

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

还有一个属于模拟退火算法的特色概念,也就是它跳出局部极小值解的方法:将原有的目标函数值和新求出的目标函数值相减,得出一个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、直观理解

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

喜欢Python的狗子们可以留言,如果留言够多,二狗会出一期python实现模拟退火算法的文章。Matlab爱好者,期待您的参与~

本文作者:云屿

本文分享自微信公众号 - matlab爱好者(matlabaihaozhe),作者:matlab爱好者

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-03-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 让你的matlab代码计算速度提升百倍的技巧揭秘

    对于任何一款编程语言来说,提前分配变量的存储空间,对程序运行效率提升是显著的,这对matlab也不例外。对于matlab而言,在编程过程中遇到循环是最拖累代码运...

    matlab爱好者
  • 从泰勒级数说傅里叶级数

    泰勒中值定理:若函数f(x)在含有x0的某个开区间内具有直到(n+1)阶的导数,那么对于任一x∈(a,b),有:

    matlab爱好者
  • 一文教你搞懂图像相似度

    小编在浏览论坛的时候,发现网友糖心疼分享的一份用易语言编写的基于三原色原理来做图片相似识别的程序,下载使用后发现效果还不错,因此决定将他写的程序改编成matla...

    matlab爱好者
  • 不止面试—jvm类加载面试题详解

    总的来讲,这一步就是通过类加载器把类读入内存。需要注意的是,第三步虽然生成了对象,但并不在堆里,而是在方法区里。

    业余草
  • graftcp一种把指定程序的 TCP 流量重定向到代理的方法

    graftcp?可以把任何指定程序(应用程序、脚本、shell 等)的 TCP 连接重定向到 SOCKS5 代理。

    砸漏
  • Nginx的location匹配指令及常用内置变量

    luxixing
  • 云之手红外式测温计产品设计分享(基于合泰BH67F2752方案)

    今天,就来介绍下深圳市云之手科技有限公司的测温产品,出自陈工之手,这也是他个人目前开源的第二个项目,也是个非常成功的项目,产品已经实现大批量产。第一个开源DIY...

    morixinguan
  • 双休大作战|在《工作模拟器》续篇度假,Hunble Bundle推出最高85%折扣!

    到周末啦~大伙可有为这短暂的假期做好安排呢?闲着没事不如来看看最近有何新应用(游戏),找点乐子吧!

    VRPinea
  • Python环境搭建遇到问题及解决方案记

    新建用户,切换到新用户之后pip不能用了,还原/usr/bin/pip3的设置如下

    py3study
  • 一种把指定程序的TCP流量重定向到代理的方法

    graftcp 可以把任何指定程序(应用程序、脚本、shell 等)的 TCP 连接重定向到 SOCKS5 代理。

    七夜安全博客

扫码关注云+社区

领取腾讯云代金券