混合算法(GA+TS)求解作业车间调度问题(JSP)-禁忌搜索部分

程序猿声
关注

大家好,在上一篇文章中,我们介绍了FJSP问题以及HA算法的GA部分。这一篇文章主要介绍嵌套在其中的Tabu Search部分。

种群进化+邻域搜索的混合算法(GA+TS)求解作业车间调度问题(JSP)-算法介绍

Tabu部分原论文没有很详细的描述,因此很多内容是小编收集各方资料,查阅其他相关文献总结出的结论,小编自己编写了三个tabu search,在这里分别分享介绍一下。如有专门研究这块的同学,欢迎随时指点交流!

代码会在下一期统一给出,请关注我们!

Tabu1-基于编码

在之前的文章中说过,算法对每一代子代的每一个个体,都需要decode成可行解,然后运用禁忌搜索优化解,再编码回GA编码,进入下一代。可想而知,如果tabu写的不好,算法的耗时肯定会很高。

论文中的tabu其实是以第二种为主体的。基于编码的tabu相对而言比较盲目,当初编写时也是基于试一试的心态。

前文提到,对一串合法的OS序列,无论进行怎样的交换、插入运算,都可以解码成可行解;对MS序列,在同一工件范围内任意交换顺序,也可以保证得到可行解。

因此,小编在代码中简单设计了两种邻域:1. 对相邻的OS编码进行交换操作;2. 对MS编码的每个位置分别采用GA中的变异操作。

swap很简单,再重复一下MS的变异:

随机选择MS中一半的数字,随机换为对应操作可以选择的某个机器。例如图中长度为6的MS String,随机选择三个位置,对O11而言,共有三个机器可选择,则随机选择1,2,3中一个数字替换掉原先的2。

邻域部分代码(开启了一个50%的采样):

for (int i = 0; i < chromosome.gene_OS.length - 1; i += 2)

for (int j = i + 1; j < chromosome.gene_OS.length; j += 2)

if(r.nextDouble() < 0.5)

OSs.add(swap(chromosome.gene_OS, i, j));

for (int i = 0; i < chromosome.gene_MS.length; i++)

if(r.nextDouble() < 0.5){

int[] MS = chromosome.gene_MS.clone();

MSs.add(chromOps.machineSeqMutation(MS));

结论:这个邻域设计的比较随意,但经过小编的测试后发现效果不佳,小编在这里建议大家不要使用基于编码的邻域搜索。

Tabu2-基于析取图的k-insertion

析取图

对JSP和FJSP来说,除了用甘特图表示解意外,还有一个很重要的表示解的结构:析取图。

混合算法(GA+TS)求解作业车间调度问题(JSP)-禁忌搜索部分

析取图是一张有向图。图中的点表示工序,边代表工序加工的顺序。

声明: 本文由入驻OFweek维科号的作者撰写,观点仅代表作者本人,不代表OFweek立场。如有侵权或其他问题,请联系举报。
侵权投诉

下载OFweek,一手掌握高科技全行业资讯

还不是OFweek会员,马上注册
打开app,查看更多精彩资讯 >
  • 长按识别二维码
  • 进入OFweek阅读全文
长按图片进行保存