上一篇文章我们讲解了优化算法学习|灰狼优化算法及Python实现，本日我们来学习一下改进稠浊灰狼优化算法求解作业车间调度问题。
01 数学模型作业车间调度问题（Job Shop Scheduling, JSP）常日以最小化最大落成韶光为优化目标，因此建立数学模型如下：
01 进化种群动态操作
Saremi 等人[1] 在GWO 算法中引入进化种群动态操作( EPD) ，便是将种群中差的个体移除，已有研究证明EPD 能够改进全体种群适应度的中值，是一种改进元启示式算法性能的大略有效方法。
在稠浊灰狼优化算法的每一次迭代中，通过EPD 操作将种群中差的一半个体位置打消，然后在α狼、β狼、γ狼以及局部随机点这四个位置以相等概率重新随机天生它们的新位置。
由于Saremi 等人提出的稠浊灰狼优化算法是针对连续函数优化问题设计，不能直接用于求解离散的组合优化问题。以是，须要对该操作进行改进，改进后的四个位置更新式如下:
02 反向学习初始化种群
对基于种群迭代的群体智能优化算法来说，初始种群的好坏直接影响着算法的全局搜索效率和解的质量，多样性较好的初始种群对提高算法的寻优性能有很大帮助。然而，标准GWO 算法在迭代开始前通过随机初始化产生种群个体，难以确保初始群体的多样性，从而在一定程度上影响了算法的搜索效率。Tizhoosh[2]在2005 年提出了反向学习策略，目前已在GA、DE、ACO 等群体智能优化算法中得到了成功的运用。采取反向学习策略产生初始种群个体的详细操作步骤如下:
（1） 在搜索空间中随机初始化N个灰狼个体的位置xi,j (i =1,2,…,D; j = 1,2,…,N)作为初始种群P1。在作业车间调度问题的编码中xi,j ∈[0,1]中的随机数，D 为每个灰狼个体的维数，即工序总数; N 为种群个数。
（2）天生初始种群P1中每个灰狼个体 xi,j 的反向个体 xi,j' 构成反向种群P2，xi,j'= 1 - xi,j 。
（3）合并种群P1和P2，将2N个灰狼个体按照适应度值进行升序排序，选取适应度值前N 个灰狼个体作为终极的初始种群。
03 变异算子
由于基于精英保存策略，在GWO 算法进化后期，群体中所有灰狼个体均向最优个体区域靠近，从而导致种群损失多样性，如果此时当前最优灰狼个体α 狼为局部最优解，则GWO算法将陷入局部最优，涌现早熟收敛征象，这也是很多群体智能优化算法的弊端。为了降落GWO 算法涌现早熟征象和陷入局部最优值的概率，本文对群体中当前最优灰狼个体α 狼进行多样性变异操作，其事理是: 对最优个体α 狼中的每一维元素以1 /D 的概率进行变异。变异操作公式为：
通过对标准GWO 算法进行进化种群动态、反向学习初始化种群，以及最优个体变异三方面的改进操作，改进后的稠浊灰狼优化算法拥有更佳的寻优性能，同时跳出局部最优解的能力更强。利用所提出的IGWO 算法求解作业车间调度问题的算法流程如图1 所示。
03 参考文献[1] Saremi S , Mirjalili S Z , Mirjalili S M . Evolutionary population dynamics and grey wolf optimizer[J]. Neural Computing & Applications, 2015, 26(5):1257-1263.
[2] Yang X . Nature-Inspired Metaheuristic Algorithms: Second Edition[J]. 2010.
[3]Tizhoosh, H. R . Opposition-Based Learning: A New Scheme for Machine Intelligence[C]// International Conference on International Conference on Computational Intelligence for Modelling, Control & Automation. IEEE, 2005:695-701.
[4]姚远远,叶春明.求解作业车间调度问题的改进稠浊灰狼优化算法[J].打算机运用研究,2018,35(05):1310-1314.
更多精彩内容关注公众年夜众号“土博在路上”~
算法学习、写作技巧、科研工具更多精彩内容等你来解锁~
