基于混合算法求解指派问题目标规划模型

2022-07-12王文璨刘林忠

计算机应用与软件 2022年6期

王文璨巩梨刘林忠

(兰州交通大学交通运输学院甘肃兰州 730070)

0 引言

在运筹学范畴当中，指派问题是一类很经典的问题，已经广泛应用于生产服务行业、运输、资源配送优化等科学研究领域，其目的是找出总成本最优的工作分配计划，是许多企业运营与管理优化的基础，与公司生产效益息息相关。指派问题是典型的NP难问题，因此利用高效的方法来求解该问题可以使得人力、财力、物力的有效节省，也可以降低企业成本、提高生产效率。对于确定收益的指派问题的理论与方法，国内外学者已经做了较为透彻的研究，并且解决此类问题也有了非常精确的算法。然而，生活总是充满各种不确定性，随机影响收益的因素也较为复杂，因此对于含有不确定因素的指派问题，其研究价值对于企业生产过程提高效率具有很大的经济意义。

Kuhn等[1]为了求解经典指派问题，提出著名的匈牙利算法。田倩男等[2]研究了将具有特殊属性的任务指派给有限数量的班次，以任务完成产生的效益总和最大化为目标建立数学优化模型,应用CPLEX软件对实际数据进行求解。肖继先等[3]对隐枚举法稍加改进再结合不确定函数法，设计了求解指派问题的不确定目标机会约束规划模型的混合智能算法。熊圣等[4]提出一种新的广义非线性整数规划模型，并利用LINGO进行求解，结果表明该模型在求解多人同时参与完成一项任务的指派问题上是有效的。Ding等[5]提出了一个不确定随机指派问题的α-optimistic模型，并设计了一种将随机模拟引入到分枝定界算法中的求解方案，但是该算法的局限性在于需要大量的存储空间和计算时间。董天雪等[6]在离散状态转移算法基础上，引入了二次状态转移和停滞回溯策略，结果表明离散状态转移算法具有相对较好的稳定性和全局搜索能力，优于经典的模拟退火算法。

本文针对利润矩阵和时间矩阵为随机的情形，以最大完工利润和最少耗费时间为优化目标，并结合不确定理论的特点，建立了任务分派问题的机会约束目标规划模型[7，11]，根据该模型的特点，利用随机模拟和非支配排序遗传算法融合而成混合智能算法进行求解，最后以实例为基础对模型的有效性和准确性进行检验。

1 指派问题模型

1.1 经典指派问题

某工厂有n台机器需要去完成n项生产任务，而且第i台机器完成第j项任务获得的利润为cij(cij>0)，因此该问题的核心就是找出任务分配的最优方案，使得最终完成所有任务后获得的利润最大[8]。则数学模型如下:

(1)

(2)

(3)

xij∈{0,1} 1≤i,j≤n

(4)

式中：xij=1表示第j项任务分配给第i个人去完成，否则任务j未分配给员工i。式(2)说明第j项生产加工任务只能由一台机器来完成；式(3)说明每台机器i至多只可以完成一项任务。

1.2 指派问题的目标规划模型

不确定因素在面临的绝大多数优化问题中普遍含有。本文的员工以及任务自身属性存在异质性，员工完成相应的任务获得的利润和耗费时间是随机的，所以要找出该问题的最优分派方案就会相当困难。针对本文的多目标优化问题(multi-objective optimization problem)，给出一个允许范围，即只要求使约束条件得到满足的机会测度不小于预先给定的置信水平，这就是由Charnes和Cooper所提出的第二类随机规划，即机会约束规划，其显著的特点是随机约束条件至少以一定的置信水平成立[9-10]。

某公司安排m个员工去完成n项作业(m

(5)

(6)

在第①优先级里，给定置信水平α1下，完工后获得的收益f1(x,c)应尽可能要大于等于事先给的限定值b1，因此有目标约束:

(7)

在第②优先级里，完工时间f2(x,t)尽可能以置信水平α2不超过事先给的限定值b2，因此有目标约束:

(8)

根据上述优先结构，得出的不确定环境下指派问题的机会约束多目标规划模型如下所示:

(9)

(10)

(11)

(12)

(13)

xij∈{0,1}i=1,2,…,m,j=1,2,…,n

(14)

(15)

2 混合求解算法

遗传算法是近几年来广泛被用来研究的搜索优化算法，由美国的Holland教授于1972年提出，其思想是基于“物竞天择，适者生存”的选择原理。目前它已经成为了一种通用的求解算法，具有很高的优化效率。对于上述机会约束目标规划模型，为了提高求解效率，利用随机模拟技术为利润函数和时间函数产生输入输出数据，然后来训练一个神经元网络逼近不确定函数，最后融入到非支配排序遗传算法(NSGA)中，产生一个效率高的混合智能优化算法。

2.1 编码设计

编码是遗传算法中的基础工作之一，它直接影响后续的遗传操作，本文采用实数编码规则，这种遗传编码方法操作简单灵活，译码过程也较为便捷。向量V1=(v1,v2,…,vk)表示一个染色体，其中1≤k≤n,1≤vk≤m，其长度为作业的数量，vk代表任务k被分配给员工的序列号。例如现有8项工作，需要5个职工来完成，如表1所示。

表1 染色体结构设计

即：职工1完成工作7，职工2完成工作2和工作8，职工3完成工作1，职工4完成工作5和工作6，职工5完成工作3和工作4。

2.2 初始化种群

良好的初始群体可以有效地节省进化的代数，避免过早地陷入局部最优，从而影响遗传算法的性能。一般采用随机选取的方式来产生初始群体，先给每个工人随机分配一个工作，然后再将剩余没被分配的工作随机的分配给任意员工。此方法生成的染色体V1,V2,…,VK避免了产生不可行的初始解，该过程不断循环，直到预先设定的规模被初始群体中染色体数填满。

2.3 遗传操作

2.3.1选择操作

适应度值最主要的作用是对染色体进行评价，以此作为遗传操作选优淘劣的依据，因此适应度函数对于种群的进化行为具有很大的决定作用。为了避免进化个体会偏向某一个目标，本文适应度函数利用非支配排序原理对种群首先进行分级，然后根据级别高低，赋予相应的虚拟适应度值，级别越低，适应值越高[12]。最后通过轮盘赌旋转法决定哪些染色体可以进行进一步的进化行为。

2.3.2交叉操作

例如C=5，则交叉过程如图1所示。

图1 交叉方法

2.3.3变异操作

例如V=4，temp=3，则变异过程如图2所示。

图2 变异方法

2.4 算法步骤

非支配排序遗传算法(NSGA)是由Srinivas和Deb提出的，常常用于求解多目标优化问题，该算法基于非支配排序原理对种群中的个体进行分级，对每一级分配虚拟适应度值，它是基于Pareto最优解讨论的多目标优化算法(MOGA)[13-14]。当问题含有多个目标函数时，它们之间相互制约，一个可行解对于其中一个目标函数是最优的，但对于剩余目标函数未必是最好，也有可能却是恶化的。因此对于多目标优化问题，往往存在一个Pareto最优解，这个解对于所有目标函数来说是个可“接纳”的均衡解，它不被其他决策变量所支配，Pareto最优解更好地协同了多个优化目标之间的不相容的问题。

算法步骤如下：

Step1根据Cij和Tij服从的概率分布，利用随机模拟技术为利润函数和时间函数产生输入输出数据[9]。

Step2根据Step 1产生的数据训练一个神经元网络逼近利润函数和时间函数[9]。

Step3根据初始条件随机生成符合约束的N个染色体，并通过训练好的神经元网络对染色体的可行性进一步进行检验[10]。

Step4利用非支配排序原理对种群染色体进行分级，然后给每一级按照规则指定一个虚拟适应度值，级别越高，赋予的适应值越小。

Step5通过轮盘赌选择法对染色体进行选择，以此进行后续的遗传操作。

Step6进行交叉和变异来更新染色体，并对子代染色体的可行性利用训练好的神经元网络进行检验[10]。

Step7利用训练好的神经元网络计算所有个体的函数值[10]。

Step8重复Step 4到Step 7，直到循环次数达到迭代终止次数。

Step9筛选出的最好的个体作为最优解。

3 实例分析

假设某工厂有8项生产任务待生产，而该工厂有5台机器可以用来加工，在完成所有任务的前提下，希望得到最优的分配方案。假设每台机器完成每项任务用图来表示，对每一条弧边，其权值利润Cij由正态分布N(μ,σ2)生成，其中u和σ分别从区间(16,25)和(1,4)中随机生成，耗费的时间Tij由均匀分布U(5,20)生成，i=1,2,…,5，j=1,2,…,8。

3.1 基本信息及参数选择

为验证该混合智能算法对以上机会约束规划模型(CCP)模型的合理性，采用C语言进行编程计算，程序中所采用的参数：迭代终止次数为50，种群规模为50，交叉概率由均匀分布U(0.7,0.9)随机生成，每5代进行一次变异,评价函数参数α=0.05，利润和时间得到满足的置信水平(α1,α2)=(0.9,0.9)下，利润和时间的目标水平为(b1,b2)=(200,100)。

3.2 结果分析

由于利润和时间为随机变量，结合本文多目标规划问题的特点，实例产生的解并不是唯一的，本算例将选择较为优良的一个解来进行说明。通过运行混合智能算法(循环模拟次数为100，遗传迭代次数为50)，经过29步迭代达到最优，得到的一个Pareto解方案为：生产任务4由机器1完成，生产任务8由机器1完成，生产任务3和生产任务5由机器3完成，生产任务1和生产任务2由机器4完成，生产任务6和生产任务7由机器5完成。其中，所有任务完工后获得的利润为208元，耗费的时间为65 min。