基于改进灰熵并行优化量子状态转移算法求解MOJSP问题

吴贝贝 李喆

摘  要： 为了解决多目标作业车间调度问题（MOJSP），提出一种改进灰熵并行关联度的量子状态转移算法（QSTA）。構建以最大完工时间、最大拖期时间及总流程时间皆最短的多目标作业车间调度问题模型，利用灰熵权值计算适应度值来引导算法的进化，并将该方法应用于含容忍策略的QSTA中解决MOJSP问题。仿真结果表明，改进灰熵并行关联度引导QSTA求解MOJSP问题的可行性和有效性，其解优于其他三种智能优化算法，是解决作业车间生产调度问题的一种高效方法。

关键词： MOJSP; 量子状态转移; MOJSP建模; 灰色关联分析; 容忍机制; 仿真分析

中图分类号： TN911.2?34; TP301.06            文献标识码： A                       文章编号： 1004?373X（2020）10?0069?07

Quantum state transfer algorithm based on improved grey entropy parallel optimization for solving MOJSP

WU Beibei1， LI Zhe2

（1. College of Electrical Engineering， Xinjiang University， Urumqi 830047， China;

2. Center of Network and Information Technology， Xinjiang University， Urumqi 830046， China）

Abstract： A quantum state transition algorithm （QSTA） with improved gray entropy parallel correlation degree is proposed  to solve the MOJSP （multi?objective job?shop scheduling problem）. A MOJSP model is established with the maximum completion time， the maximum delay time and the total process time are the shortest， and the gray entropy weight is used to calculate the fitness value to guide the evolution of the algorithm. This method is applied into the QSTA with tolerance policy to solve the MOJSP. The simulation results show that the improved grey entropy parallel correlation degree guides QSTA is feasible and effective in solving the MOJSP， and its solution is better than that of other three intelligent optimization algorithms， which is an efficient method to solve the MOJSP.

Keywords： MOJSP; quantum state transition algorithm; MOJSP modeling; grey correlation analysis; tolerance mechanism; simulation analysis

0  引  言

作业车间调度问题（Job?shop Scheduling Problem，JSP）是一种典型的组合优化问题，属于NP难题[1]。其研究以求解单目标为主，但在实际生产制造过程中，生产者往往要求生产能够满足多个目标而非单一目标。因此，MOJSP更符合生产制造的实际情形，具有非常重要的现实意义。又因其各目标间存在复杂的制约关系，较难达到各目标皆最优，所以也成为一个研究的难点。

在优化MOJSP问题时，适应度值分配（Fitness Assignment）是一个关键问题。对单目标问题而言，解的适应度函数和目标函数是一致的，并且可以方便地进行比较和排序。但是当优化多目标问题时，由于多个目标之间存在冲突，仅通过简单的排序很难评估其解的质量，所以必须全面考虑多个目标。有学者为解决Patero前端的取舍及最优解集采用灰关联分析法[2?3]，然而，仅采用该方法会导致局部关联点存在倾向问题。李禾澍等人为求解多目标水文站网优化问题构建了一种基于信息熵的模型，对站网信息量进行定量分析并结合多目标优化方法，可有效地对站网进行优化[4]。郑斯斯等人为确定设备选型结果，采用将信息熵值法的效用值和多属性决策相结合的方法，对装卸设备进行综合排序[5]。然而，仅采用信息熵却不能有效利用各目标之间相关联的信息。状态转移算法（State Transition Algorithm，STA）是由周晓君等人于2012年提出的一种新型的随机性全局优化方法，因其结构简单、参数少、寻优效率高，得到广泛的应用[6]。阳春华等人为求解旅行商问题提出了离散状态转移算法[7];王聪等人提出一种原对偶状态转移算法用于分数阶多涡卷混沌系统的辨识[8]。然而，单纯的采用STA得到的工序缺乏多样性，因此引入量子旋转门操作以丰富工序的多样性。

本文针对多目标作业车间调度优化问题，构建以最大完工时间、最大拖期时间和总流程时间皆最短为优化目标的MOJSP数学模型。利用信息熵理論与灰色关联度分析并行地处理各目标函数，解决了仅采用单一分析策略存在的弊端问题，并利用改进灰熵并行关联度值评判解的优劣。在此基础上提出一种量子状态转移算法（Quantum State Transition Algorithm，QSTA），该算法以改进灰熵并行关联度作为适应度值求解MOJSP问题，通过仿真实例验证了所提方法的可行性和有效性。

1  作业车间调度模型的构建

1.1  问题描述

JSP问题的一般描述如下：在给定每个工件使用机器的序列、每个工件每道工序的加工时间和每个工件的加工工艺的情况下，设计一种合理的工件加工工序，可使n个待加工的工件在m台设备上进行加工，且满足某些性能指标最优化。

1.2  构建多目标作业车间调度模型

实际生产中，JSP问题具有多目标性。本文综合考虑工件加工的最大完工时间、最大拖期时间及总流程时间这三个目标，各目标的数学描述如下：

1） 最大完工时间

[f1=Cmax=max{Ci，k|i∈1，2，…，n;k∈1，2，…，m}] （1）

式中，[Ci，k]表示工件i在第k台设备上的加工完成时间，即工件i的完工时间。

2） 最大拖期时间

[f2=Tmax=max{（0，Li）|i∈1，2，…，n}]     （2）

式中，[Li=Ci，k-due（i）]，due（i）为工件i的交货期。式（2）表示工件i的最大拖期时间为工件i的完工时间减去交货期再与零之间取较大者。

3） 总流程时间

[f3=Smax=i=1nCi，k]            （3）

针对本文选择的三个子目标，多目标优化问题的模型可描述为：

[Y=（min f1，min f2，min f3）]        （4）

[Cjk-tik+M（1-aihk）≥Cih]        （5）

[Cjk-Cik+M（1-xihk）≥tjk]        （6）

[Cik≥0]                   （7）

[aihk，xijk=0，1]              （8）

[i，j=1，2，…，n;h，k=1，2，…，m]        （9）

式（4）为多目标函数;式（5）表示工序的前后约束关系;式（6）表示工序的非阻塞约束关系;式（7）表示工件的完工时间大于零;式（8）表示工序、机器约束;式（9）表示各下标变量的取值范围。式中：[tik]和[Cjk]表示工件i在设备k上的加工时间及完工时间;M是一个极大的正数;[aihk=1]表示机器h比机器k优先加工工件i;[xijk=1]表示工件i比工件j优先在设备k上加工;反之，二者皆为0。

2  基于改进灰熵并行优化QSTA求解问题

2.1  量子状态转移算法

根据量子叠加及量子跃迁理论的特点，通过变换量子旋转门来生成新的编码。根据薛定谔方程，量子旋转门必须为酉正矩阵，量子旋转门的构造直接影响算法性能。量子旋转门构造如下：

[cos θi-sin θisin θicos θi]           （10）

则量子位[αiβi]的量子旋转门更新过程为：

[αiβi=cos θi-sin θisin θicos θiαiβi]      （11）

式中：[θi]为量子旋转门的旋转角;[αiβi]为更新后的概率幅。

采用状态转移算法作为旋转角搜索策略，同时结合量子旋转门操作提升算法的全局搜索能力。使用状态转移算法中产生候选旋转角的统一框架可以描述为：

[θk+1=Akθk+Bkukyk+1=f（θk+1）]        （12）

式中：[θk，θk+1∈Rn]分别表示旋转角的当前状态与更新后的状态，当前状态对应优化问题的一个解，经过一次算子变换产生的[θk+1]将构成一个候选解集;[Ak，Bk∈Rn×n]为状态转移矩阵;[uk∈Rn]是关于历史状态和状态[θk]的一个函数表达式;[f（θk+1）]表示状态更新后的目标函数值。

为了使QSTA求解优化问题时量子旋转角状态转移过程具有可控性，依据传统状态转移算法设计了4种量子旋转角状态更新算子。

1） 量子旋转算子

[θk+1=θk+α1nθk2Rrθk]       （13）

式中：α是一个正的常数，称为旋转因子;[Rr∈Rn×n]是一个服从[-1，1]均匀分布的随机矩阵;[?2]是一个向量的二范数;利用旋转算子可以使产生的候选解落在半径为α的超球体内。

2） 量子平移算子

[θk+1=θk+βRtθk-θk-1θk-θk-12]     （14）

式中：β是一个正的常数，称为平移因子;[Rt∈R]是一个服从[0，1]均匀分布的随机变量;平移搜索是一种线搜索，它以[θk]为起点并沿着其指定的方向进行搜索，搜索的最大长度为β。

3） 量子伸缩算子

[θk+1=θk+γReθk]          （15）

式中：γ是一个正的常数，称为伸缩因子;[Re∈Rn×n]是一个服从高斯分布的随机矩阵。该算子主要用作整个空间内的全局搜索。

4） 量子坐标变换算子

[θk+1=θk+δRaθk]          （16）

式中：δ是一个正的常数，称为坐标因子;[Ra∈Rn×n]是一个服从高斯分布的随机对角稀疏矩阵，且矩阵中只有一个随机位置上的元素不为零。坐标算子有利于增强单维搜索能力。

对以上4种算子计算出的旋转角分别通过量子旋转门更新量子位，通过量子坍缩操作对量子位进行观测，生成二进制串通过相应的编码方式将其映射到解空间中。

2.2  容忍非局部最优解机制

量子状态转移算法每次迭代过程只考虑当前最优解，在此基础上进行状态转移，然而应用量子状态转移算法处理JSP问题时容易陷入局部最优。因此本文提出一种对非局部最优解的容忍机制，如表1所示，其能够有效避免加工序列处于局部最优状态无法收敛的情况。

本文考虑单次序列的局部变化，可能不会使新序列获得更好的适应度值，但对同一序列的连续局部变化形成的新序列也有可能导致更好的结果。所以本文设置非局部最优状态下的容忍次数，允许非局部最优解获得连续的状态变化，以此增加解的多样性，同时可有效地避免某一加工序列陷入局部最优。

2.3  适应度值分配策略

优化多目标问题的描述如下：确定由可行域中的决策变量所组成的向量，其满足所有约束并优化由多个目标函数组成的向量，但构成这些向量的多个目标通常彼此矛盾。所以，上述的“优化”是指找到一个或一组解向量以满足目标向量中的全部目标函数。

2.3.1  灰熵关联度适应度值分配策略

在多目标优化算法中存在多种适应度值分配策略，例如基于Pareto优先级关系排序的适应度值分配策略、基于随机权重求和的适应度值分配策略及基于选择性权重的适应度值分配策略等。熵是一种测量微观分布均匀性的方法，它代表了热力学系统的混沌状态和生态学中物种的多样性。本文借助熵值权重的思想，提出基于灰熵关联的适应度值分配策略，具体步骤如下。

步骤1：使用量子状态转移算法分别优化子目标，得到各子目标函数的最优解，构成参考序列[Y0={f1（0），f2（0），…，fM（0）}]，M为目标个数。此外，对于可行解[xi]，逐个对子目标函数值[fm（i）]进行计算，构成比较序列[Yi={f0（i），f1（i），…，fM（i）}]，m=1，2，[…]，M;i=1，2，[…]，N。

步骤2：对理想解和可行解的各目标函数值无量纲化处理。

[f′m（i）=max（Yi）-fm（i）max（Yi）-min（Yi）]       （17）

步骤3：计算灰关联系数。

[r=miniminmf′m（i）-f′m（0）+ρmaximaxmf′m（i）-f′m（0）f′m（i）-f′m（0）+ρmaximaxmf′m（i）-f′m（0）] （18）

式中，[ρ?（0，1）]为分辨系数，一般取0.5。

步骤4：求可行解各子目标的比重、信息熵及熵值权重。

[Pm（i）=f′m（i）m=1Mf′m（i）]        （19）

[em（i）=-1ln Mi=1N（Pm（i）·ln Pm（i））]  （20）

[Wm（i）=1-em（i）m=1M（1-em（i））]         （21）

步骤5：求可行解的灰熵关联度。

[R（Y0，Yi）=m=1MWm（i）·r（fm（0），fm（i））]  （22）

熵并行分析法是一种将动态灰过程变化趋势的整体性分析和信息熵相结合的方法，是一种全局性方法。把可行解的灰熵关联度作为多目标解的适应度值，能够客观地表示可行解与理想解之间的相近程度。通常，灰熵并行关联度的值越大，可行解就越逼近理想解。

2.3.2  改进灰熵关联度适应度分配策略

经试验验证分析，以灰熵并行关联度作为最终的优化目标引导智能算法进化，当比较序列与参考序列之间的差值相等时，r=1，则该适应度不能引导智能算法进化。

以算例FT06为例，使用灰熵关联度作为适应度值，同时优化最大完工时间和总流程时间。各目标优化的最优解所对应的目标函数值可构成参考序列：[Y0={55，228}]，由優化算法搜索得到的可行解所对应的目标函数值构成比较序列：[Yi={fCmax（i），fSmax（i）}，][i=1，2，…，N]。以灰熵关联度引导QSTA进化可以得到如图1、图2所示的结果。

从图中可以看出，以灰熵并行关联度作为适应度值存在2个问题：

1） 单目标收敛过程与灰熵关联度收敛过程不一致。

2） 比较序列（59，232）与参考序列（55，228）之间的的差值相等，大小为4，这导致灰熵关联度为1，即最大值，算法不再收敛。

以灰熵关联度作为适应度函数会存在上述问题，因此需要重新构造适应度函数。本文同时考虑灰熵关联度和序列绝对差，从而得到改进灰熵关联度适应度函数，且从式（23）中可以看出该值越接近0说明比较序列与参考序列的符合程度越高。