采用遗传算法求单一规格矩形下料问题

yjch

厉害，好好学习天天向上

aimisiyou

根据蚁群算法，可以先设定每条节点间的信息素为t=1，节点总数为毛坯理论个数n=DA*DB/(a*b)，根据前一节点状态Ai，求出下一节点的转移概率（是横放还是纵放），完成一次路径后全局更新信息素，t=(1-p)*t+nk/n。p为信息素挥发系数，取p=0.9,nk表示完成一次路径后实际能排放的毛坯数量。
若放入aj后，Aj的水平线条数均不会减少，但Aj最低水平线处水平距离缩短，此时对应的aj的选取几率就高。
问题的关键是如何确定合理的节点转移概率公式？
采用剩余矩形法时，当Aj的凹处宽度小于毛坯长宽中较小值时，采取直接抹平方式更新Aj。

aimisiyou

;;;简单描述下流程图
n=DA*DB/(a*b);t=1;设置每条边信息素为1
(repeat   num    ;;;循环次数
（repeat  ants   ;;;蚂蚁个数
         i=0;
        lst=nil;
       ai=随机生成0或1；
       lst=(cons ai lst);
      while(i<=n)
     { Aj0=draw(reverse(cons 0 lst));j0=ti0/(n0*n0);
       Aj1=draw(reverse(cons 1 lst));j1=ti1/(n1*n1);
       对比Aj0和Aj1得出横放和纵放的概率p0=j0/(j0+j1)和p1=j1/(j0+j1);
       生成随机数rnd；
       若0<rnd<p0,setq j=0,否则setq j=1;
      setq lst (cons j lst)；
      i++;
   }
    Ank=draw(reverse(lst))=(nk nt ai…… aj);   ;;;实际能放下的个数nk,水平线条数nt;
    antslst=(cons Ank  antslst)
  ）
    p_best=nk取最大；
    t=(1-p)*t+nk/n;更新每条边上的信息素
）
draw(cdr(cdr(p_best)))    ;;; 画出图形

20180318

如能發展成3維,那就應能用在"貨櫃"的裝載排列了

lsthz

都是大神啊
来自: 微社区

liaotaofan

没有c++的代码吗？看不懂lisp。。。

aimisiyou

liaotaofan 发表于 2019-12-12 09:16
没有c++的代码吗？看不懂lisp。。。

语言只是一种表达方式，算法才是关键的。