CN114118805B - 一种基于分层博弈的柔性制造车间需求响应调度方法 - Google Patents

Abstract

本发明涉及一种基于分层博弈的柔性制造车间需求响应调度方法，属于生产调度技术领域，首先构建一种基于分时电价的柔性制造车间生产调度管控模型，然后在NSGA‑II算法的基础上针对算法的收敛性和多样性问题，引入对立学习策略和自适应交叉、变异概率策略；针对机器负载平衡问题，采用平衡机器负载策略。本发明基于分时电价及需求响应下的柔性制造车间生产调度，对调节电网负荷以及提高电力系统的负荷率和运行稳定性起到了重要作用；通过生产调度还有效缩减了柔性制造生产的能耗成本。

Description

一种基于分层博弈的柔性制造车间需求响应调度方法

技术领域

本发明涉及一种基于分层博弈的柔性制造车间需求响应调度方法，属于生产调度技术领域。

背景技术

近年来，有关于需求响应的大部分研究工作都集中针对住宅和商业用户。然而，目前全球42.6％的电力消耗是由工业生产造成的，因此，工业部门的需求响应对于减少电网的峰值需求尤为重要。目前，多数研究都集中在连续的生产过程上，缺乏用于离散制造的通用需求响应模型，主要原因为离散模型的复杂性使具体通用的数学模型难以建立。

由于柔性制造的灵活性，考虑柔性制造生产车间作为工业用户去参与电网的调度过程，同时需要满足柔性制造车间的生产调度要求。此外，由于离散生产的复杂性，柔性制造车间需要考虑订单、工序和机器的对应关系，是典型的NP-hard问题。而研究基于电价的生产调度意味着要研究工序、机器和时间隙的匹配对应关系，使问题变的更为复杂，因此，如何选用合适的算法进行求解排产也变得至关重要。

发明内容

本发明的目的是提供一种基于分层博弈的柔性制造车间需求响应调度方法，对调节电网负荷、提高电力系统的负荷率和运行稳定性有重要作用，还可以有效缩减柔性制造生产的能耗成本。

为了实现上述目的，本发明采用的技术方案是：

一种基于分层博弈的柔性制造车间需求响应调度方法，包括以下步骤：

S1、建立基于分时电价的柔性作业车间生产调度管控模型，将电力公司的最大利润和工业用户的最大收益作为模型的目标函数；

S2、确定调度的约束条件，包括工序约束、机器约束、时间约束、功率总和上限约束；

S3、获取电力公司公告电价；

S4、初始化得到父代种群；

S5、根据父代种群获取子代种群；

S6、选择新的父代种群；

S7、如果满足终止条件，即迭代次数大于设定值，则输出最优个体对应的工序排列、机器选择、每个工序的开始时间序列和每个时间段的总能耗值并转到步骤S8，否则转到步骤S5；

S8、根据需求响应调度策略，计算电力公司的效用函数能耗最优值，如果此时工业用户在当前电价下的能耗值达到电力公司的效用函数能耗最优值或迭代次数达到设定值，则将计算电力公司的最大利润和工业用户的最大收益，并输出电力公司的最大利润和工业用户的最大收益，结束程序；如果此时工业用户在当前电价下的能耗值没有达到电力公司的效用函数能耗最优值且迭代次数没有达到设定值，转到步骤S9；

S9、根据需求响应调度策略，进行电价迭代，并转到步骤S3。

本发明技术方案的进一步改进在于：所述电力公司的最大利润为：

其中，W表示电力公司的最大利润，p(t)表示电力公司公布给工业用户每个时刻的电价，e(t)表示各时隙工业用户的生产所需能量消耗，a、b为电力公司的收益系数。

本发明技术方案的进一步改进在于：所述工业用户的最大收益为：

π＝max(log(α_t+β_t·e(t))-p(t)·e(t)) (2)

其中，π为生产该订单的最大总收益；p(t)表示电力公司公布给工业用户每个时刻的电价；e(t)表示各时隙工业用户的生产所需能量消耗；α_t、β_t为工业用户收益系数；j为工件序号；D为订单的总数量；h为工序序号；H_j为订单d_j的工序数量；i为机器序号；m_jh为工序d_jh可选择进行加工的机器数量；e_ijh为工序d_jh在机器m_i加工所需能耗；当工序d_jh在机器m_i加工时x_ijh值为1，否则x_ijh值为0；当工序d_jh在t时刻加工时z_jht值为1，否则z_jht值为0。

本发明技术方案的进一步改进在于：所述步骤S4的具体步骤为：

S4.1、初始化种群，采用两段式编码的方式表示染色体信息，第一段为工序编码OS，用来确定工件的加工顺序；第二段为机器编码串MS，用来表示工序分配到的机器，随机产生种群规模为N的种群；

S4.2、利用对立学习策略，产生一个相反种群；

S4.3、利用平衡机器负载策略，确保两个种群中所有机器的负载尽可能平衡；

S4.4、将初始种群与其对立学习后的种群进行合并，种群规模为2N；

S4.5、对合并后的种群进行快速非支配排序和拥挤度计算；

S4.6、采用锦标赛和精英选择策略选择得到父代种群，种群规模为N。

本发明技术方案的进一步改进在于：所述步骤S5的具体步骤为：

S5.1、计算自适应交叉、变异概率；

S5.2、进行选择、交叉、变异操作，得到子代种群，种群规模为N；

S5.3、利用对立学习策略，对子代种群进行对立学习，产生相反种群；

S5.4、在子代种群及其相反种群中实施平衡机器负载策略，确保两个种群中所有机器的负载尽可能平衡；

S5.5、将子代种群与其对立学习后的相反种群进行合并，种群规模为2N；

S5.6、对合并后的种群进行快速非支配排序和拥挤度计算；

S5.7、采用锦标赛和精英选择策略选择新的子代种群，种群规模为N。

本发明技术方案的进一步改进在于：所述步骤S6的具体步骤为：

S6.1、将新得到的父代种群和子代种群合并，种群规模为2N；

S6.2、对父子代合并后的种群进行快速非支配排序和拥挤度计算；

S6.3、用锦标赛和精英选择策略选择新的父代种群，种群规模为N。

本发明技术方案的进一步改进在于：所述步骤S5.1的具体步骤为：

首先选择设定交叉概率(CP)和变异概率(MP)的最大值(CP_max和MP_max)和最小值(CP_min和MP_min)；设Fitness_i是第i个个体的相对适应度值，Fitness_max和Fitness_min分别是种群中的最大相对适应度值和最小相对适应度值；然后，第i个个体的交叉概率计算方法为：

其中，ε是一个很小的实数，防止分母为零；第i个个体的变异概率计算方法为：

其中，设定CP_max＝0.9，CP_min＝0.6，MP_max＝0.25，MP_min＝0.06，设在进行快速非支配排序后，得到分配的等级个数为R，种群大小为Size_pop，每个等级的个体数为f_i(其中i＝0，1，…，R-1)；设相对适应度值为Ra_Fitness＝Size_pop，则每个个体的相对适应度值Fitness_i计算如下：

Ra_Fitness＝Ra_Fitness-Size_pop/R/f_i+ε (14)

Fitness_i＝Ra_Fitness (15)

按照i＝0，1，…，R-1的次序，依次计算每个等级的每个个体的相对适应度值Fitness_i。

由于采用了上述技术方案，本发明取得的技术效果有：

本发明基于分时电价及需求响应下的柔性制造车间生产调度，对调节电网负荷以及提高电力系统的负荷率和运行稳定性起到了重要作用；通过生产调度还有效缩减了柔性制造生产的能耗成本。

本发明为提高NSGA-II算法的收敛性和多样性，引入对立学习策略和自适应交叉、变异概率策略，针对机器负载平衡问题，采用平衡机器负载策略，使所有机器的负载尽可能平衡,有效缩减柔性制造生产的能耗成本。

附图说明

图1是本发明的流程图；

图2是本发明平衡机器负载策略的应用一流程图；

图3是本发明同一等级的个体间距离示意图；

图4是本发明平衡机器负载策略的应用二流程图。

具体实施方式

下面结合附图及具体实施例对本发明做进一步详细说明：

本发明提供了一种基于分层博弈的柔性制造车间需求响应调度方法，在传统的作业车间调度模型上构建一种基于分时电价的柔性制造车间生产调度管控模型；在NSGA-II算法的基础上针对算法的收敛性和多样性问题，引入对立学习策略和自适应交叉、变异概率策略，针对机器负载平衡问题，采用平衡机器负载策略。具体流程如图1所示，包括以下步骤：

S1、建立基于分时电价的柔性作业车间生产调度管控模型(FJSP模型)，将电力公司的最大利润和工业用户的最大收益作为模型的目标函数

假设有一组n个独立作业和一组m台独立机器。每个作业都有一个连续操作序列根据操作优先约束依次进行处理，每道工序可以在不同机器上进行加工，且在不同的机器上的加工时间是不相同的。将电力公司的最大利润和工业用户的最大收益作为模型的目标函数，并用数学函数进行如下描述，表1对FJSP模型以及下文所列约束条件和评价指标中所涉及的主要变量符号进行了定义和描述：

表1变量描述

电力公司的最大利润表示为：

式中，W表示电力公司的最大利润，p(t)表示电力公司公布给工业用户每个时刻的电价，由于考虑电力公司在每个时间隙{t,t+1}内的收益最大化问题，因此各时隙的电价值不一定相等；e(t)表示各时隙工业用户的生产所需能量消耗，a、b为电力公司的收益系数。

工业用户的最大收益表示为：

π＝max(log(α_t+β_t·e(t))-p(t)·e(t)) (2)

其中：

建立动态多目标柔性作业车间调度模型后，选取适当的初始参数，设立种群规模sizepop为100，算法最大迭代次数c为100。

S2、确定调度的约束条件，包括工序约束、机器约束、时间约束、功率总和上限约束

工厂的生产调度问题是一个约束优化问题，有以下约束条件：

(1)在同一个时间点，每一道工序只能选择一台机器进行加工：

给定一个0-1变量来确定各个工序在哪台机器上进行工作：当x＝0时，表明工件的工序不在机器h上工作，当x＝1时，表明工件的工序在机器h上工作。在一个时间点上每个工件的每个工序只能选择一台机器进行加工直至此工序加工完毕，当此工序加工完毕后不会进行第二次加工。

(2)给定一个0-1变量来确定某个工件的工序在某时刻是否处于加工状态。在总加工时间内，此变量在各时间点的值之和与该工序的加工时间相等。

(3)后续工序的开始时间不能早于先前工序的结束时间。

b_jh+x_ijh·t_ijh＜＝f_jh (6)

f_jh＜＝b_j(h+1) (7)

每个工件的工序严格按照一定的先后顺序进行生产，后续的工序不能在先前工序未完成的情况下提前生产。因此工序的生产时间必须有先后限制，式(6)和(7)共同构成此约束条件。

(4)同一时间一台机器只可以进行一道工序的加工。

b_jh+t_ijh＜＝b_kl+L·(1-y_ijhkl) (8)

f_kl＜＝b_j(h+1)+L·(1-y_iklj(h+1)) (9)

当每台机器开始加工生产某个工序时，在这道工序加工完成之前不能停止加工或者转而加工其他工序。因此给定一个0-1变量来确定两个不同工序之间的先后顺序，当y＝1时，表明工序d_jh先于d_kl在机器m_i加工，反之，y＝0。

(5)各工序生产的功率总和上限约束。

从电力公司购买的电量会受到配电线路、变压器额定值等物理限制，因此各工序生产的功率总和小于等于从电网购电的最大功率。

S3、获取电力公司公告(初始)电价

将时间窗口T(考虑T＝24h)标准的划分为3个不同时段即0时到8时，9时到16时，17时到24时，即P1、P2、P3(初始电价三个时间段相同)。其中，电力公司的收益系数a、b在各时段的值，如表2所示：

表2a、b各时段取值

S4、初始化得到父代种群

S4.1、初始化种群，采用两段式编码的方式表示染色体信息，第一段为工序编码OS，用来确定工件的加工顺序；第二段为机器编码串MS，用来表示工序分配到的机器，种群规模为N；

初始随机产生一个设定固定值的种群，则在该种群中，每一个个体都是一条染色体。每一条染色体都包含两部分信息，一部分是随机产生工序选择序列，其必须保证每个工序都要在序列内；另一部分是随机产生的机器选择序列，其必须保证每个工序都和一台机器进行对应。

S4.2、利用对立学习策略，产生一个相反种群

利用对立学习策略，计算每个个体工序序列的贪婪相反路径，根据该路径创建一个相反的工序序列，并随之调整机器序列，进而产生一个相反种群。

对离散域问题的反对方法采用开放路径反对。开放路径是指当我们到达路径上的最后一个顶点时完成它们的路径。开放路径反对的目标是通过分散相邻节点来最大限度地最大化路径中的总接近度。请注意，计算完全相反的情况本身就是一个组合问题，因此我们用开放路径贪婪反向算法定义一个贪婪的相反路径，该算法求解过程伪代码如表3所示，并且可以根据该路径创建一个相反的总体，以节省处理时间。例如，一个四节点的示例(1 2 34)，利用开放路径贪婪反向算法，计算出其贪婪相反路径为(1 4 2 3)。

表3开放路径贪婪反向算法求解过程伪代码

S4.3、利用平衡机器负载策略，确保两个种群中所有机器的负载尽可能平衡

利用平衡机器负载策略，首先找到最大负载机器，并重新分配最大负载机器上的操作，以减少最大负载机器上的负载，确保所有机器的负载尽可能平衡。

采用的机器负载平衡策略包括两种实际应用的情况。此处为第一种实际应用情况，当搜索处于初始化阶段时，初始化完成到每个粒子的初始位置后，通过解码初始化粒子的原始位置向量可以找到最大负载机器，然后对最大负载机器上的这些操作随机重新分配一次(包括当前的最大负载机器)，以减少其负载。应用过程的流程图如图2所示。

S4.4、将初始种群与其对立学习后的种群进行合并，种群规模为2N。

S4.5、对合并后的种群进行快速非支配排序和拥挤度计算

将将初始种群与其对立学习后的种群进行合并后得到一个规模为2N的种群R_t。这时候需要保留R_t中最好的N个成员进入下一代，为此首先使用快速非支配排序算法将R_t分为F₁、F₂、F₃等若干非支配层，再从上往下合并各非支配层的所有个体，直到产生一个规模刚超过或正好为N的种群S_t，假设S_t＝F₁∪F₂∪...∪F_v，其中F_v为最后能够接受的临界层。此时如果S_t规模刚好为N，则进行下一步骤，否则舍弃F_v中的部分个体，使得S_t大小为N。那么计算每个个体的拥挤度，在F_v中，拥挤度小的那部分个体被舍弃。图3为同一等级的个体间距离示意图，拥挤度计算公式为：

S4.6、采用锦标赛和精英选择策略选择得到父代种群，种群规模为N

将轮盘赌策略和精英策略相结合，以此来选择下一代的优秀个体，优秀个体的选择需要依靠每种策略下的适应度值。精英策略可以让种群进化的方向始终保持最优，而轮盘赌策略可以防止优化过程陷入局部优化，二者结合可以有效加速种群的迭代并获取最优解。

S5、根据父代种群获取子代种群

S5.1、计算自适应交叉、变异概率

首先选择设定交叉概率(CP)和变异概率(MP)的最大值(CP_max和MP_max)和最小值(CP_min和MP_min)；设Fitness_i是第i个个体的相对适应度值，Fitness_max和Fitness_min分别是种群中的最大相对适应度值和最小相对适应度值；然后，第i个个体的交叉概率计算方法为：

其中，ε是一个很小的实数，可以防止分母为零；第i个个体的变异概率计算方法为：

其中，设定CP_max＝0.9，CP_min＝0.6，MP_max＝0.25，MP_min＝0.06，设在进行快速非支配排序后，得到分配的等级个数为R，种群大小为Size_pop，每个等级的个体数为f_i(其中i＝0，1，…，R-1)；首先设相对适应度值为Ra_Fitness＝Size_pop，则每个个体的相对适应度值Fitness_i计算如下：

Ra_Fitness＝Ra_Fitness-Size_pop/R/f_i+ε (14)

Fitness_i＝Ra_Fitness (15)

按照i＝0，1，…，R-1的次序，依次计算每个等级的每个个体的相对适应度值，如等式(12)、(13)所示，如果一个个体比群体中其他个体有更高的适应度，那么它就会有较小的CP_i和MP_i值，即很难发生交叉和变异，这样的个体被直接保留给下一代。

S5.2、进行选择、交叉、变异操作，得到子代种群，种群规模为N

交叉运算是产生新个体的主要手段，决定了算法的全局搜索能力，在交叉之前先要把种群中的个体随机配对，然后让两个配对的染色体相互交换部分基因，从而生成两个新个体。

设P₁和P₂为配对的两个父代染色体，经过交叉产生两个子代染色体C₁和C₂，具体操作过程如下：

1)将一个个体的所有工序随机分成两部分J₁和J₂；

2)将P₁包含在J₁中的工序复制到C₁，将P₂包含在J₂中的工序复制到C₂，并保留位置不变；

3)将P₁包含在J₁中的工序复制到C₂，将P₂包含在J₂中的工序复制到C₁，并保留顺序不变；

变异运算是产生新个体的辅助手段，它只对染色体个别位置上的基因进行操作，因而决定了算法的局部搜索能力。对于工序排序部分采用互换变异算子，即随机选取两个位置上的基因进行交换。

S5.3、利用对立学习策略，对子代种群进行对立学习，产生相反种群。

S5.4、在子代种群及其相反种群中实施平衡机器负载策略，确保两个种群中所有机器的负载尽可能平衡

在子代种群及其相反种群中实施平衡机器负载策略，首先找到最小负载机器，并将候选机器集中包含当前最小负载机器的工序，暂时分配给当前最小负载机器，以帮助进一步平衡其他机器的负载，此处是平衡机器负载策略的第二种实际应用情况，在迭代过程中，一旦候选机器集包含当前的最小负载机器，暂时将操作重新分配到最小负载机器，以帮助进一步平衡其他机器的负载。应用过程的流程图如图4所示。

S5.5、将子代种群与其对立学习后的相反种群进行合并，种群规模为2N。

S5.6、对合并后的种群进行快速非支配排序和拥挤度计算。

S5.7、采用锦标赛和精英选择策略选择新的子代种群，种群规模为N。

S6、选择新的父代种群

S6.1、将新得到的父代种群和子代种群合并，种群规模为2N。

S6.2、对父子代合并后的种群进行快速非支配排序和拥挤度计算。

S6.3、用锦标赛和精英选择策略选择新的父代种群(下一次迭代的父代种群)，种群规模为N。

S7、如果满足终止条件，即迭代次数大于设定值，则输出最优个体对应的工序排列、机器选择、每个工序的开始时间序列和每个时间段的总能耗值并转到步骤S8，否则转到步骤S5。

S8、根据需求响应调度策略，将当前每个时间段的电价带入公式(16)计算电力公司的效用函数能耗最优值，如果此时工业用户在当前电价下的能耗值达到电力公司的效用函数能耗最优值或迭代次数达到设定值，则将根据公式(1)计算电力公司的最大利润，并根据公式(2)计算工业用户的最大收益，输出工业用户的最大收益和电力公司的最大利润，结束程序；如果此时工业用户在当前电价下的能耗值没有达到电力公司的效用函数能耗最优值且迭代次数没有达到设定值(100)，转到步骤S9；

电力公司的效用函数能耗最优值计算如下：

其中，x＝1,2,3表示三个时间段，b₁＝0.001，c₁＝0.00015。

S9、根据需求响应调度策略，进行电价迭代，并转到步骤S3。

需求响应调度策略具体如下：首先电力公司公告初始电价，工业用户根据此初始电价进行排产调度，排产得到每个时间段的能耗值，将当前每个时间段的电价带入公式(16)计算电力公司的效用函数能耗最优值，如果此时工业用户在当前电价下的能耗值达到电力公司的效用函数能耗最优值或迭代次数达到设定值，则将根据公式(1)计算电力公司的最大利润，根据公式(2)计算工业用户的最大收益，输出工业用户的最大收益和电力公司的最大利润，结束程序；如果此时工业用户在当前电价下的能耗值没有达到电力公司的效用函数能耗最优值且迭代次数没有达到设定值(100)，则通过价格迭代来调节自身的价格，价格迭代方程为：

式中，δ＞0表示电力公司的价格策略调节步长，E表示每次迭代过程中，工业用户产生的总能耗，表示当前电价下电力公司的效用函数能耗最优值。工业用户得到更新的电价，再进行排产调度，依次迭代，直到使工业用户和电力公司均达到纳什均衡，输出最优结果。

Claims (6)

1.一种基于分层博弈的柔性制造车间需求响应调度方法，其特征在于包括以下步骤：

S1、建立基于分时电价的柔性作业车间生产调度管控模型，将电力公司的最大利润和工业用户的最大收益作为模型的目标函数；

S2、确定调度的约束条件，包括工序约束、机器约束、时间约束、功率总和上限约束；

S3、获取电力公司公告电价；

S4、初始化得到父代种群；

S5、根据父代种群获取子代种群；

S6、选择新的父代种群；

S7、如果满足终止条件，即迭代次数大于设定值，则输出最优个体对应的工序排列、机器选择、每个工序的开始时间序列和每个时间段的总能耗值并转到步骤S8，否则转到步骤S5；

S8、根据需求响应调度策略，计算电力公司的效用函数能耗最优值，电力公司的效用函数能耗最优值计算如下：

其中，x＝1,2,3表示三个时间段，b₁＝0.001，c₁＝0.00015，表示电力公司的效用函数能耗最优值；

如果此时工业用户在当前电价下的能耗值达到电力公司的效用函数能耗最优值或迭代次数达到设定值，则将计算电力公司的最大利润和工业用户的最大收益，并输出电力公司的最大利润和工业用户的最大收益，结束程序；如果此时工业用户在当前电价下的能耗值没有达到电力公司的效用函数能耗最优值且迭代次数没有达到设定值，转到步骤S9；

S9、根据需求响应调度策略，进行电价迭代，并转到步骤S3。

2.根据权利要求1所述的一种基于分层博弈的柔性制造车间需求响应调度方法，其特征在于：所述电力公司的最大利润为：

其中，W表示电力公司的最大利润，p(t)表示电力公司公布给工业用户每个时刻的电价，e(t)表示各时隙工业用户的生产所需能量消耗，a、b为电力公司的收益系数。

3.根据权利要求1所述的一种基于分层博弈的柔性制造车间需求响应调度方法，其特征在于：所述步骤S4的具体步骤为：

S4.1、初始化种群，采用两段式编码的方式表示染色体信息，第一段为工序编码OS，用来确定工件的加工顺序；第二段为机器编码串MS，用来表示工序分配到的机器，随机产生种群规模为N的种群；

S4.2、利用对立学习策略，产生一个相反种群；

S4.3、利用平衡机器负载策略，确保两个种群中所有机器的负载尽可能平衡；

S4.4、将初始种群与其对立学习后的种群进行合并，种群规模为2N；

S4.5、对合并后的种群进行快速非支配排序和拥挤度计算；

S4.6、采用锦标赛和精英选择策略选择得到父代种群，种群规模为N。

4.根据权利要求1所述的一种基于分层博弈的柔性制造车间需求响应调度方法，其特征在于：所述步骤S5的具体步骤为：

S5.1、计算自适应交叉、变异概率；

S5.2、进行选择、交叉、变异操作，得到子代种群，种群规模为N；

S5.3、利用对立学习策略，对子代种群进行对立学习，产生相反种群；

S5.4、在子代种群及其相反种群中实施平衡机器负载策略，确保两个种群中所有机器的负载尽可能平衡；

S5.5、将子代种群与其对立学习后的相反种群进行合并，种群规模为2N；

S5.6、对合并后的种群进行快速非支配排序和拥挤度计算；

S5.7、采用锦标赛和精英选择策略选择新的子代种群，种群规模为N。

5.根据权利要求1所述的一种基于分层博弈的柔性制造车间需求响应调度方法，其特征在于：所述步骤S6的具体步骤为：

S6.1、将新得到的父代种群和子代种群合并，种群规模为2N；

S6.2、对父子代合并后的种群进行快速非支配排序和拥挤度计算；

S6.3、用锦标赛和精英选择策略选择新的父代种群，种群规模为N。

6.根据权利要求4所述的一种基于分层博弈的柔性制造车间需求响应调度方法，其特征在于：所述步骤S5.1的具体步骤为：

首先选择设定交叉概率CP和变异概率MP的最大值CP_max和MP_max和最小值CP_min和MP_min；设Fitness_i是第i个个体的相对适应度值，Fitness_max和Fitness_min分别是种群中的最大相对适应度值和最小相对适应度值；然后，第i个个体的交叉概率计算方法为：

式中，CP_i表示第i个个体的交叉概率；

其中，ε是一个很小的实数，防止分母为零；第i个个体的变异概率计算方法为：

式中，MP_i表示第i个个体的变异概率；

其中，设定CP_max＝0.9，CP_min＝0.6，MP_max＝0.25，MP_min＝0.06，设在进行快速非支配排序后，得到分配的等级个数为R，种群大小为Size_pop，每个等级的个体数为f_i(其中i＝0，1，…，R-1)；设相对适应度值为Ra_Fitness＝Size_pop，则每个个体的相对适应度值Fitness_i计算如下：

Ra_Fitness＝Ra_Fitness-Size_pop/R/f_i+ε (14)

Fitness_i＝Ra_Fitness(15)

按照i＝0，1，…，R-1的次序，依次计算每个等级的每个个体的相对适应度值Fitness_i。