混合算法(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来说,除了用甘特图表示解意外,还有一个很重要的表示解的结构:析取图。
析取图是一张有向图。图中的点表示工序,边代表工序加工的顺序。
图片新闻
最新活动更多
-
即日-11.13立即报名>>> 【在线会议】多物理场仿真助跑新能源汽车
-
11月28日立即报名>>> 2024工程师系列—工业电子技术在线会议
-
11月29日立即预约>> 【上海线下】设计,易如反掌—Creo 11发布巡展
-
11月30日立即试用>> 【有奖试用】爱德克IDEC-九大王牌安全产品
-
12月19日立即报名>> 【线下会议】OFweek 2024(第九届)物联网产业大会
-
即日-12.26火热报名中>> OFweek2024中国智造CIO在线峰会
发表评论
请输入评论内容...
请输入评论/评论长度6~500个字
暂无评论
暂无评论