所谓资源分配问题，就是将数量一定的资源(如机器设备、资金、原材料和人力等)恰当地分配给若干个使用者，使总目标函数值达到最优[1]．资源分配问题是典型的组合优化问题，在现实生活中广泛应用．如何对资源进行分配，直接影响各部门的生产效益．然而，随着任务数量及资源维数的增加，传统算法计算的时间及空间复杂度呈指数增长，将会增加求解时间和难度．当前在多维资源分配问题的求解算法上已有诸多研究成果．文献[2]针对云计算数据中心资源分配算法的资源利用率较低的问题，提出了一种基于改进遗传算法的云计算数据中心资源分配算法．文献[3]针对不可分物品的局部无嫉妒资源分配问题，转化为可满足性模块理论(satisfiability modulo theories，SMT)问题进行求解，对相关资源分配问题的研究主要集中在理论分析和复杂度证明上．文献[4]针对网络安全防御资源配置不合理的问题，提出了一种网络安全防御资源优化配置框架，建立了防御资源与网络脆弱性之间网络节点脆弱性幂函数模型求解．文献[5-6]分别提出了多维资源分配问题的M-best算法和LP-based算法．文献[7]研究了遗传算法在组织系统中的资源分配问题的应用．上述算法的求解精度偏低，且算法运行时间过长．基于此，本研究提出了一种启发式离散灰狼优化算法求解多维资源分配问题，通过数值仿真实例验证了算法的有效性和收敛性．1 资源分配问题假定有M种资源，数量总数分别为a1，a2，…，aM，每种资源须要分配用于生产n种产品．如果第一种资源a1以数量xi1为单位，第二种资源a2以数量xi2为单位，…，第M种资源aM以数量xiM为单位用于生产产品，所用总成本(或总收益)为z，那么此问题用数学语言描述如下：Μin(Max)   z=f(x11,x21,⋯,xn1,x12,x22,⋯,xn2,⋯,x1M,x2M,⋯,xnM);x11+x21  +⋯+xn1=a1;x12+x22+⋯+xn2  =a2;                                                    ⋮x1M+x2M+⋯+xnM  =aM;       xi1,xi2,⋯,xiM≥0     (xi1,xi2,⋯,xiM∈{0}⋃Z+,i=1,2,⋯,n);a1,a2,⋯,aM∈{0}⋃Z+. (1)由上可知：这是一个M维资源分配问题，当a2,a3,⋯,aM都为0时，是一维资源分配问题；当a3,a4,⋯,aM都为0时，是二维资源分配问题．目标函数总成本(或总收益)可以是线性或非线性函数，目标函数取最大值或最小值依具体情况而定．该方程包含M×n个变量，M个约束方程．显然，任意整数向量x=(x11,  x21 ,⋯,xn1,    x12,x22,⋯，xn2,⋯,x1M, x2M,⋯,xnM)只是一个潜在解，其中第j种资源对应的潜在解为(x1j，x2j,⋯,xnj) (j=1，2,⋯,M)，同时满足约束条件才是一个可行解．2 标准灰狼优化算法文献[8]提出了灰狼优化算法(grey wolf optimizer，GWO)，因其参数设置简单，优化能力强等优点，在交通工程等领域得到了广泛应用[9-15]．灰狼种群有一个非常严格的层次结构，居于金字塔顶端的灰狼称为α，对整个狼群进行管理；居于第二的灰狼称为β，主要辅佐α指挥和管理狼群，管理权仅次于α；居于第三的灰狼称为δ，是最后一位的狼群管理者；居于最低等级的灰狼称为ω，是灰狼种群中的基础，总要服从于α，β和δ．在GWO中，每只灰狼代表灰狼种群中的一个可行解，最优解为α，次最优解为β，第三最优解为δ，其余解为ω．在迭代搜索过程中，前面三个最优解α，β和δ指挥ω，将包围、追捕和攻击三个阶段的任务分配给灰狼群体以完成捕食行为，从而实现搜索过程的全局优化．2.1　包围猎物在狩猎过程中，狼群首先要发现并包围猎物，其数学模型为D=|C×Xp(t)-X(t)|；(2)X(t+1)=Xp(t)-A×D，式中：D为个体与猎物间的距离；A和C为系数向量；Xp为目标猎物的位置；X为灰狼的位置，依据猎物的位置改变而更新位置；t为目前迭代次数．式(2)为灰狼的位置更新公式，A和C的计算公式为A=2a×r1-a; (3)C=2r2,式中：收敛因子|a|在迭代过程中从2线性递减到0；|r1|和|r2|为[0,1]内的随机数．2.2　追捕猎物在狩猎过程中，居于领导层级的灰狼感受到猎物的位置时，会联合其他领导级别的灰狼对整个狼群进行管理，同时指挥整个狼群从四面八方向猎物靠近，最终达到捕食目的．这种行为在数学上描述为Dα=|C1×Xα-X|；Dβ=|C2×Xβ-X|；Dδ=|C3×Xδ-X|,式中：Xα，Xβ和Xδ分别为α，β和δ的当前位置；C1，C2和C3分别为对α，β和δ的随机扰动．定义ω狼向α，β和δ前进的方向和距离为X1=Xα-A1×Dα     ;X2=Xβ-A2×Dβ    ;X3=Xδ-A3×Dδ     ,式中X1，X2和X3分别为α，β和δ对ω指导后更新的位置．确定了子代灰狼的最终位置，即X(t+1)=(X1+X2+X3)/3．2.3　攻击猎物该过程主要通过式(3)中|a|的递减来实现，当|a|从2线性递减到0时，对应的|A|会在区间[-a，a]变化．此外，如果|A|1，那么下一代狼群位置会更加靠近猎物的位置；如果|A|1，那么狼群会朝远离猎物的方向分散，导致失去最优解位置，从而陷入局部最优．|a|的更新公式为|a|=2-2t/Τ，式中Τ为预设的最大迭代次数．3 离散灰狼优化算法3.1　编码转换方法原始GWO适合求解连续优化问题，迭代更新后的灰狼种群均为实数矩阵，实数矩阵的某一行代表灰狼个体，即连续优化问题的一个解，它们根据猎物的位置和距离不断更新，但这一机制在离散整数域上不适用，因此原始GWO不能直接用于求解资源分配问题．为求解资源分配问题，提出了一种编码转换方法，将在连续空间中的每个灰狼个体的元素xi映射为整数yi，即yi=   L     (xi≤L);[xi+0.5]    (LxiU); U    (xi≥U  ), (4)式中：[x]为取整函数，表示不超过实数x的最大整数；L和U分别为yi的下界和上界，即yi∈[L，  U]⋃Z+．3.2　基于马太效应的修复与优化算法灰狼群体实数矩阵经过编码转换方法映射后变成一个整数矩阵，此时整数矩阵的每一行都是一个潜在解，但不一定是可行解，因此须要对这些不可行解进行处理．目前主要有修复法、罚函数法和修复与优化算法3种方法处理不可行解[16]，为解决资源分配问题，提出了一种基于马太效应的修复与优化算法(Matthew effect and optimization algorithm，MEOA)．马太效应的修复与优化算法思路如下．以灰狼群体整数矩阵列向量元素的和为基准，动态调整每行元素，使第j种资源对应的潜在解的元素和等于aj，aj由式(1)给出．灰狼群体规模直接影响离散灰狼优化方法的性能，规模太小会使基于马太效应的修复与优化步骤中的判别依据不准，易陷入局部最优，规模太大会增加优化难度及算法时间，经多次测试，群体规模取30为宜．例如：若aj=10，则种群数量为30，采用编码转换方法后变成30个整数解，并求出此时矩阵每列元素的和，令矩阵列向量元素的和最小的列记为h1，第二小的列记为h2，…，第二大的列记为hn-1，最大的列记为hn．再求出每行矩阵元素的和，如果某行元素的和为8，那么将2加到该行第hn列(第hn列的矩阵元素和最大，表明此列首先加强，加2后若该行第hn列元素大于U，则将该行第hn列元素减去U的差加到该行第hn-1列，同时令第hn列的矩阵元素为U)，此时该行元素的和已等于10；如果某行元素的和为12，那么将-2加到第h1列(该行第h1列的矩阵元素和最小，表明此列首先减弱，加-2后若该行第h1列元素小于L，则将该行第h1列的元素减去L的差加到第h2列，同时令该行第h1列的矩阵元素为L)，此时该行元素的和已等于10；如果该行元素的和为10，那么已符合约束条件，不做变动．记灰狼种群规模为N，经过灰狼算法第t次迭代后的灰狼种群为X'(t)，经过式(4)编码转换方法处理后的灰狼种群为X(t)=[Dt1,Dt2,⋯,DtM]，式中：X(t)为N行M×n列的整数矩阵，每一行表示一个潜在解；Dtj (j=1,2,⋯,M)为N行n列的整数矩阵，其中，Dt1=x11t1,     x12t1,⋯,x1nt1x21t1,     x22t1,⋯,x2nt1⋮xN1t1,    xN2t1,⋯,xNnt1，Dt2=x11t2,     x12t2,⋯,x1nt2x21t2,     x22t2,⋯,x2nt2⋮xN1t2,    xN2t2,⋯,xNnt2，⋮DtM=x11tM,     x12tM,⋯,x1ntMx21tM,     x22tM,⋯,x2ntM⋮xN1tM,    xN2tM,⋯,xNntM，其中每个子矩阵Dtj对应的约束条件为x1j+x2j+⋯+xnj=aj．算法 马太效应的修复与优化算法(MEOA)输入 灰狼种群规模N，最小值L，最大值U，N个潜在解X(t)，维数为M×n输出 N个可行解Y(t)a. 计算整数矩阵Dtj的每列元素的和，列元素的和最小的列记为c1，和第二小的列记为c2，…，和第二大的列记为cn-1，和最大的列记为cn．为叙述方便，先介绍如何修复与优化一个解，其他N-1个解按同样方法处理．抽取Dtj的第一行，记为Ei，则有Ei=[x11tj, x12tj, ⋯,x1ntj ]．b. 计算行向量Ei=[x11tj, x12tj, ⋯,x1ntj ]的元素之和，记为s，同时令P=aj-s．若P为0，则Ei不做调整；若P小于0，则将P加到Ei的第c1列(若该行第c1列增加P后的元素值小于L，则将第c1列元素减去L的差加到第c2列，同时令第c1列元素为L，增加P后若第c2列的元素小于L，则按同样方法处理)，此时Ei的元素之和等于aj；若P大于0，则将P加到Ei的第cn列(若该行第cn列增加P后的元素大于U，则将超出U的整数部分加到第cn-1列，同时令第cn列元素为U，增加P后若第cn-1列的元素大于U，按同样方法处理)，此时Ei的元素之和等于aj，得到新的行向量Ei'，(E1',E2',⋯,En')为资源分配问题的一个可行解．c. 同理，可以得到其他N-1个可行解，N个种群可行解记为Y(t)．图1为离散灰狼算法流程图．10.13245/j.hust.210815.F001图1离散灰狼算法流程图4 实验结果与分析4.1　算例1Μin    f=3x1+4x2+5x3+6x4+7x5+8x6+9x7+10x8+9x9+ x10+x1x4x5+x1x2x3+x6x7x8+(x8-x9)2;s.  t.  x1+x2+x3+x4+x5=100;x6+x7+x8+x9+x10=120;xi∈{0}⋃Z+,i∈{1,2,⋯,10}.这是二维资源分配问题，对资源数100和120进行分配，自变量10个，维数为10，令种群规模为30，迭代次数为100．自变量的最小值均为0，U=[100,100,100,100,100,120,120,120 ，120,12 0]．用离散灰狼算法求解此二维资源分配问题，用Matlab编程求解得到x=(100,    0 ，  0,     0,   0,    0,    0,   0,   0,120)，目标函数值为420．用遗传算法求解，目标函数值为515．离散灰狼算法的运行效率和最优值均优于遗传算法．图2(a)为算例1用离散灰狼算法和遗传算法求解得到的迭代曲线比较图．10.13245/j.hust.210815.F002图2离散灰狼算法和遗传算法求解得到的最优值4.2　算例2Μin    f=x14+x23+2x3+3x4+x52+x62+x7+x1x8+x1x9;s.  t.   x1+x2+x3=20;x1+x4+x5+x6=30;x7+x8+x9=40;xi∈Z+⋃{0},i∈{1,2,⋯,9}.此模型可看成三维资源分配问题，对资源数20，30和40进行分配．对资源数20分配x1，x2和x3后，再对30-x1的资源数分配x4，x5和x6．自变量有9个，维数为9，令种群规模为30，迭代次数为100．自变量的最小值均为0，U=[20,20，20,30,30,30,40, 40, 40]．用离散灰狼算法求解此资源分配问题，用Matlab编程求解得到x=(0,1,19,28,1,1,0,37,77)，目标函数值为125．用遗传算法求解，目标函数值为130．离散灰狼算法的运行效率和最优值均优于遗传算法．图2(b)为算例2用离散灰狼算法和遗传算法求解得到的迭代曲线图，证明了本文算法求解资源分配问题的有效性和收敛性．5 结语针对多维资源分配问题，提出了一种基于马太效应的离散灰狼优化算法(DGWO)来求解．首先，基于映射思想，提出了编码转换方法；然后，采用马太效应的修复与优化方法处理不可行解，从而求解多维资源分配问题；最后，通过2个算例对离散灰狼算法与遗传算法的数值结果进行对比，发现离散灰狼算法能用更少的迭代次数获得更优解，证明了算法的收敛性和有效性．