混合算法(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来说，除了用甘特图表示解意外，还有一个很重要的表示解的结构：析取图。
析取图是一张有向图。图中的点表示工序，边代表工序加工的顺序。
分享
图片新闻
发表评论
请输入评论内容...
请输入评论/评论长度6~500个字
暂无评论
暂无评论