﻿ 改进猫群算法求解置换流水车间调度问题
«上一篇
 文章快速检索 高级检索

 智能系统学报  2019, Vol. 14 Issue (4): 769-778  DOI: 10.11992/tis.201804016 0

### 引用本文

PEI Xiaobing, YU Xiuyan. Improved cat swarm optimization for permutation flow shop scheduling problem[J]. CAAI Transactions on Intelligent Systems, 2019, 14(4): 769-778. DOI: 10.11992/tis.201804016.

### 文章历史

Improved cat swarm optimization for permutation flow shop scheduling problem
PEI Xiaobing , YU Xiuyan
School of Management, Tianjin University of Technology, Tianjin 300384, China
Abstract: The standard cat swarm optimization (CSO) has a slow convergence rate in solving the permutation flow shop scheduling problem (PFSP) to minimize the maximum completion time. Meanwhile, the "dimension disaster" is prone to occur when the scale of the problem is large. To speed up the optimization and avoid the "dimension disaster," a CSO algorithm based on the estimation of distribution algorithms is proposed in this paper. Based on the cat swarm algorithm, the distribution estimation algorithm is embedded. In the search mode, the probability matrix is used to mine the excellent gene chain combination blocks in the solution sequence, and the tracking mode in the cat swarm algorithm is used to update the speed and position of the cat, thus updating the excellent solution sequence to generate a subpopulation. Finally, through the simulation test and comparison result of Carlier and Reeves standard example set, the good robustness and global searching ability of the algorithm are verified.
Key words: permutation flow shop scheduling problem    cat swarm optimization    estimation of distribution algorithm    search mode    probability matrix    combination block    tracking mode    excellent solution sequence

1 置换流水车间调度问题数学模型

PFSP是许多生产调度问题的简化模型，该问题主要研究了n个工件 $\left\{ {{N}_{1}} \right.,\ {{N}_{2}}, \cdots ,\left. {{N}_{{n}}} \right\}$ m台机器 $\left\{ {{M_1}} \right.,{M_2},\cdots,\left. {{M_m}} \right\}$ 上加工，并且每个工件有m道加工工序，目标是求使某项生产指标达到最优的方案。相关约束条件如下：1)所有工件按照相同顺序，即1，2，···，m在机器上加工；2)某一时刻，任一机器只能加工一个工件；3)某一时刻，任一工件只能在一台机器上进行加工；4)任何工件在加工过程中不能中断；5)所有工件在初始时刻都可以加工。

 $C({{\pi} _1},1) = {{t}}\left({{{\pi} _1},1} \right)$
 $C({{\pi} _i},1) = C({\pi} {}_{i - 1},1) + t({{\pi} _i},1)\;\;\;i = 2,3,\cdots,n$
 $C\left({{{\pi} _1},j} \right) = C\left({{{\pi}_1},j{\rm{ - }}1} \right) + \left({{{\pi} _1},j} \right)\;\;\;j = 2,3,\cdots,n$
 \begin{align} C\left({{\pi}_i},{j} \right)=&\max \left\{ C\left({{\pi}_{{i}-1}},{j} \right),C\left({{\pi}_{{i}}},{j}-1 \right) \right\}+{t}\left({{\pi}_{{i}}},{j} \right) \\ & i=2,3,\cdots ,n;j=2,3,\cdots ,m \end{align}
 ${C_{{\rm{max}}}} = C\left({{{\pi} _n},m} \right)$

2 改进的猫群算法

1) 初始化种群；

2) 计算猫的适应度值；

3) 改进的猫群算法通过利用混合比率将猫群分为搜寻模式和跟踪模式的2个子群，对不同子群采取不同的方法处理；

4) 在搜寻模式下，利用概率模型更新记录可行解信息并更新可行解；

5) 先后运用区块挖掘及区块竞争来得到适应度较高的人工解；

6) 为提高人工解的质量和多样性，运用搜寻算子对人工解进行重组；

7) 在跟踪模式中利用基于二元竞赛法的速度−位移模型对猫的速度、位置更新，直至达到全局最优；

8) 算法终止条件判断。

2.1 复杂度分析

2.2 初始化种群

 \begin{aligned} {{x}_{{i,j}}}={{x}_{\min ,j}}+\frac{{{x}_{\max ,j}}-{{x}_{\min ,j}}}{n}\cdot ({{s}_{i,j}}-1+{{r}_{3}}), \\ j=1,2,\cdots ,m \qquad\quad\qquad\\ \end{aligned} (1)

 ${X_i} = {X_{\min }} + ({X_{\max }} - {X_{\min }}){r_1}$ (2)
 ${V_i} = {V_{\min }} + ({V_{\max }} - {V_{\min }}){r_2}$ (3)

2.3 基于混合比率的猫行为模式选择

 $M_R = {{M_{R_1}}} + \frac{{\left({{{M_{R_2}}} -{ {M_{R_1}}}} \right) \times T}}{{{T_0}}}$ (4)

2.4 搜寻模式 2.4.1 构建概率模型

 \begin{aligned} & B_{ij}^{k}=\left\{ {\begin{aligned} & 1,\ \ \text{如果工件}i\text{位于}j\text{位置上} \\ & 0,\ \ \text{否则} \end{aligned}}\right.\\ & i=1,2,\cdots, n; \,\, j=1,2,\cdots, m;\,\, k=1,2,\cdots, s \\ \end{aligned} (5)
 \begin{aligned} & {{T}_{{ij}}}\left({t} \right)={{T}_{{ij}}}\left({t}-1 \right)+\sum\limits_{{k}=1}^{{s}}{B_{{ij}}^{{k}}}, \\ & i=1,2,\cdots, n; \,\, j=1,2,\cdots, m; \,\, k=1,2,\cdots ,s \\ \end{aligned} (6)
 $\begin{array}{l} Y_{il}^{k}=\left\{ \begin{array}{l} \!\!\!\! 1,\ \ \text{如果工件}i\text{紧邻}l \\ \!\!\!\! 0,\ \ \text{否则} \\ \end{array} \right. \\ i=1,2,\cdots, n;\,\, l=1,2,\cdots, n;\,\, k=1,2,\cdots ,s \\ \end{array}$ (7)
 \begin{aligned} & {{T}_{{ij}}}\left({t} \right)={{T}_{{ij}}}\left({t}-1 \right)+\sum\limits_{{k}=1}^{{s}}{Y_{{ij}}^{{k}}}, \\ & i,l=1,2,\cdots ,n; \,\, j=1,2,\cdots ,m; \,\, k=1,2,\cdots ,s \\ \end{aligned} (8)

2.4.2 组合区块

 Download: 图 5 种群迭代复杂度比较 Fig. 5 The comparison of iterative complexity of population

1) 区块挖掘

 \begin{aligned} & {\rm C{{P}}}_{i}=({{W}_{\rm dom}}\times P_{i,j}^{\rm dom})+({{W}_{\rm \rm dep}}\times P_{i,\gamma }^{\rm dep}) \\ & i,\gamma =1,2,\cdots, n;\,\,j=1,2,\cdots ,m \end{aligned} (9)

2) 区块竞争

 $P_{{B^{{i}}}}^{\rm AVG} = \frac{{P_{B_l^h}^{{\rm{dom}}} + \sum\limits_{l = {\rm{2}}}^{{n_1}} {C{P_{B_l^h}}} }}{{{n_1}}}$ (10)

2.4.3 组合人工解

1) 从人工解的第一个位置开始挖掘，挖掘方法与上述区块挖掘相同，第一个位置利用位置矩阵中概率以轮盘赌的方式选择工件；

2) 其余N−1个位置以轮盘赌的形式对合并概率进行选择；

3) 每选出一个工件，将该工件与所有其他区块的起始位置进行比较，若与其他区块的位置及工件都相同，则将此区块直接复制到人工解中，然后从下个位置继续进行选择和比较，直至人工解组合完成。

 Download: 图 8 人工解组合过程 Fig. 8 The combination process of artificial solution
2.4.4 解序列重组

2.5 跟踪模式

1) 速度的更新。

 $V_i(n + 1) = {V_i}(n) \times w + c \times {\rm rand} \times [{X_{\rm best}}(n) - V(n)]$ (11)
 $w = {w_{\max }} - ({w_{\max }} - {w_{\min }}) \times (t/{t_{\max }})$ (12)

2) 位置更新。

 ${X_i}(n + 1) = {X_i}(n) + {V_i}(n + 1)$ (13)

3) 如果第i只猫分的新位置超出搜索空间，则将速度乘以−1，从反方向继续搜索。

4) 利用二元竞赛法更新解序列，即将母体种群与子群的适应度两两对比并将适应度最高的子群代替母体种群，进行下一次搜索。

3 仿真测试 3.1 参数设置

 ${\rm BRE} = \frac{({C_{\min }}{\rm{ - }}{C^ * })}{C^ * } \times 100\text{%}$ (14)
 ${\rm{ARE}} = {\rm{ }}\frac{{(\bar C{\rm{ - }}{C^*})}}{{{C^*}}} \times 100\text{%}$ (15)
 ${\rm WRE} = \frac{({C_{{\rm{max}}}}{\rm{ - }}{C^ * })}{C^ * } \times 100\text{%}$ (16)
3.2 实验测试与比较

 Download: 图 12 最差相对误差比较 Fig. 12 Comparison of the worst relative error