二次分配问题

2024-07-25

二次分配问题（精选四篇）

二次分配问题篇1

关键词：二次分配问题,粒子群优化算法,禁忌搜索算法,交叉操作

0 引言

二次分配问题QAP(Quadratic Assignment Problem)是一个经典的组合优化问题[1],目的是寻找n个设备到n个位置的最优布局。该问题具有重要的理论与实用价值,许多实际的问题,如:大学校园中建筑物的布局、医院中科室的安排、键盘布局问题等都可以转化为QAP来解决[2,3]。其数学描述如下:给定n个设备和n个位置,两个n×n的矩阵A=[aij]和B=[brs], 其中aij 是设备i与j之间的信息流,brs是位置r与s之间的距离。QAP问题就是要寻找一个(1,2,…,n)的一个排列,使得总费用f最小:

f= $\sum_{i = 1}^{n} \sum_{j = 1}^{n} a i j \times b Μ (i) Μ (j) = \min (1)$

其中,M(i)指在当前解中,设备i所在的位置。aij×bM(i)M(j)表示同时将设备i放到位置M(i),设备j放到位置M(j)后所要的费用。

QAP是一个NP-Hard问题[4],无法寻找求解QAP的多项式时间算法。一般来说,当问题规模n>20时就很难找到最优解。为了实际可行地解决二次分配问题,人们不得不采用元启发式算法,以便在较短的时间内求得较优解。目前,遗传算法[5]、蚁群算法[6]、模拟退火算法[7]、禁忌搜索算法[8]等被广泛应用于求解QAP问题,并取得了优异的结果。

粒子群优化算法PSO(Particle Swarm Optimization)是1995年由Kennedy和Eberhart在鸟群、鱼群和人类社会的行为规律的启发下提出的一种基于群智能的演化计算技术[9],目前已在函数优化、神经网络训练、模糊系统控制等领域得到了广泛应用。但目前对PSO算法的应用主要集中在连续型优化问题,而对离散优化问题的研究甚少。本文根据文献[10]的方法,将遗传算法的交叉策略引入PSO算法中,同时采用禁忌搜索算法作为局部搜索算法,提出了一种求解二次分配问题的混合粒子群优化算法。实验结果表明,新算法比禁忌搜索算法具有更好的效果。

1 禁忌搜索算法简介

禁忌搜索算法模仿人类的记忆功能,使用禁忌表来封锁刚搜索过的区域以避免迂回搜索,同时赦免禁忌区域中的一些优良状态,进而保证搜索的多样性,从而达到全局最优。迄今为止,禁忌搜索算法已经成功应用于组合优化、生产调度、机器学习等领域。文献[11]利用一种改进的禁忌搜索算法求解QAP,取得了较好的效果,更新了tai80a、tai100a的最优解。其主要思想是对Tabu Search产生的解(1,2,…,n的排列)进行迭代扰动、优化。

本文采用Talliard的RO-TS[12]。算法描述如下:

s←getSolutionFromPSO();

InitializeTabuLists(TL1,…,TLr);

while 终止条件不满足 do

AllowedSet(s) ←{s’∈N(s)|s并不违反禁忌条件,或满足至少一条藐视规则};

s←ChooseBestOf(AllowedSet);

UpdateTabuListAndAspirationConditions();

end while

2 粒子群优化算法简介

PSO模拟鸟群的捕食行为。在PSO中,每个优化问题的解看作是搜索空间中的一只鸟,我们称之为粒子。粒子的位置代表优化问题在搜索空间中的潜在解,粒子的速度决定他们飞行的方向和距离,所有的粒子都有一个被优化的函数决定的适应值。假设在一个D 维的目标搜索空间中,m个粒子组成一个群落。第i个粒子的位置表示为矢量X(x1,x2,…,xD),飞行速度表示为V(v1, v2,…,vD)。每个粒子通过跟踪两个“最好位置”来更新自己,一个是粒子本身目前所找到的最好位置(pbest),另一个是目前整个群体中所有粒子发现的最好位置(gbest),gbest 是在pbest 中的最好值。对于第k次迭代,每个粒子是按照式(2)、(3)进行变化的[13]:

v $_{i d}^{k + 1}$ = w×v $_{i d}^{k}$ + c1× rand()×(pid-x $_{i d}^{k}$ ) + c2× rand()×(pgd-x $_{i d}^{k}$ ) (2)

x $_{i d}^{k + 1}$ = x $_{i d}^{k}$ +v $_{i d}^{k + 1}$ i=1,2,…,m (3)

式中,v $_{i d}^{k}$ ——第k次迭代粒子i飞行速度矢量的第d维分量;x $_{i d}^{k}$ ——第k次迭代粒子i位置矢量的第d维分量;pid——粒子i个体最好位置pbest 的第d维分量;pgd——群体最好位置gbest 的第d维分量;c1、c2——学习因子;w——惯性权重,为非负数;rand()——随机函数,产生[0,1]的随机数。

3 混合粒子群优化算法

由于目前对PSO算法的研究主要集中在连续型的PSO算法,即描述粒子状态及运动规律的量都是连续的,要将其应用于解决组合优化问题,存在着一定的困难。为此,将遗传算法的交叉操作及禁忌搜索算法引入粒子群优化算法中,采用混合算法求解二次分配问题。将(2)式中的c1×rand()×(pid-x $_{i d}^{k}$ )+c2×rand()×(pgd-x $_{i d}^{k}$ )看作是遗传算法的交叉操作,让当前解与个体极值和全局极值分别作交叉操作产生新的解;将(3)式用禁忌搜索算法替代,对交叉操作产生的新解用禁忌搜索算法进行局部寻优,产生的解为粒子新的位置。

对于QAP问题而言,解为(1,2,…,n)的一个排列。为了避免交叉后产生重复的基因码,采用如下的交叉方法:

1) 从第二个串old2中随机选择一个交叉区域。

2) 将old2的交叉区域加到old1前面,删除old1中已在old2的交叉区域中出现过的数字。

例如两父串为:

old1=12345678 odl2=87654321

假设交叉区域为654,则交叉后的串为:65412378。

求解QAP问题的混合粒子群优化算法如下:

(1) 设定粒子数iPSONum,规定迭代次数iStep,随机产生iPSONum个初始解dpos。根据QAP问题的解的特点,粒子位置dpos采用顺序编码方式,即(1,2,…,n)的一个排列。

(2) 根据式(1)计算当前位置的适应值m_dFitness,设置当前适应值为个体极值m_dBestfitness,当前位置为个体极值位置dpbest,根据各个粒子的个体极值m_dBestfitnesst,找出全局极值gBestFitnesst和全局极值位置gbest。

(4) 输出全局极值gBestFitnesst和全局极值位置gbest。

4 实验

实验中采用QAPLIB[14]数据作为测试实例。实验环境为:Intel Centrino Duo T2300E;内存1G;操作系统为WinXPSP2;开发软件为VC++6.0。程序中的参数设置为:禁忌搜索算法的迭代次数为1000×n(n为问题规模);混合粒子群优化算法的最大迭代步数为10,群体大小为10,每个粒子调用局部搜索算法的次数为10×n。这样,混合算法调用禁忌搜索算法的次数也为1000×n,从而将算法比较的逻辑计算时间统一到了一个计算代价上。

本文选取了QAP四种类型中比较典型的实例进行测试,每个实例独立运行10次后取最优解的平均偏离程度Davg,把Davg定义为:

Davg=[(Zavg-Zbks)/ Zbks] ×100% (4)

其中,Zavg是独立运行10次后的平均最优值,Zbks是来自QAPLIB的最优值。

实验结果如表1所示。表格第4列、第5列分别为两种算法独立运行10次后按照公式(4)求得的平均偏离程度Davg。

从实验结果分析,混合粒子群优化算法在类型(ⅳ)上的结果逊于禁忌搜索算法,特别是tai80b,其FDC(fitness-distance correlation)值比较低[15],组合解构造和局部搜索的算法不太可能获得较好的性能,故混合粒子群优化算法的优化结果相差比较大。在其余三类问题上,混合粒子群优化算法的效果均优于禁忌搜索算法。

5 结论

QAP问题是经典的NP-Hard问题,本文采用混合粒子群优化算法来求解该问题,并验证了算法的有效性。目前,应用粒子群优化算法求解QAP问题是一种崭新的尝试。本文进一步开拓了粒子群优化算法的应用领域,为进一步深入研究智能优化算法的融合奠定了基础。

科室二次分配方案篇2

财务人员月奖金以核算至科室扣除2%管理费部分参与科室人员之间的二次分配。具体核算办法如下：

一、门诊挂号及住院收费人员奖金分配

门诊收费人员以挂号人次、发票张数、病历卡本数计算业务量，工作时间以实际上班时间计算，白班算7小时，半天按3.5小时，值班按5.5小时，按每天7小时折算为上班天数。挂号、发票、病历卡按1：1：0.5比例确定总业务量后，计算出个人人均业务量，按完成全科日均量的百分比为分配率进行二次分配。住院处收费人员按核算至科室的0.87进行二次分配，附加0.05的欠费控制补贴。财务收费人员采取奖惩与服务质量和服务态度挂钩原则，100%参与业绩考核后按个人的打分情况1比1发放，如98分发放额为98%，具体扣分细则如下：

一)、劳动纪律、服务态度部分(总计30分)：

1．迟到、早退5分钟以内扣2分，10分钟以内扣5分，10分钟到30分钟扣10分，30分钟以上作旷工处理，报院办。旷工初次扣20分，第二次扣完40分，第三次待岗。按规定上班标准时间：夏令时值休人员7时30分前开窗，值班人员7时40分前接班，非夏令时值休人员7时35分前开窗，值班人员7时45分前接班，其余人员一律7时50分前开窗。值班人员应在规定时间内就餐,超出时间按迟到早退处理。上班时请自觉将个人信息牌放置窗前，不放置发现一次扣0.5分。

2．上班期间因工作事由离岗请做好离岗登记，不登记一次扣0.5分。如有私事外出应向科室领导人请假，并做好离岗登记，写明离开和回来的时间。如若无故脱岗，发现一次扣5分。无故脱岗时间超过30分钟以上作旷工处理，报院办。旷工处理同上。

3．坐在窗口要注意形象，不得从事非岗位内事务(如发现吃食物、看小说、长时间手机私聊等发现一次扣1分)；上班期间非特殊情况不得让无关人员进入收费处(如发现一次扣1分)；不经组长同意并报科室负责人批准私自调班，发现一次调换双方各扣2分。

4．窗口发生纠纷，查明原因，如因言辞不当，发生一次扣1分，如操作过错等失职行为造成的纠纷查明属实，发生一次扣2分。

二）、业务操作部分(总计60分)：

(1)、门诊收费人员

1．严格按照费用项目输入明细，如有疑问应及时告知科室负责人或联系相关科室，不明确前不可随意找项目代替，如发现检查单或其它联系单项目明细与发票明细不符每一项扣0.5分。

2．收费应严格按程序操作，发现以下操作错误一次扣1分：项目归属科室错误、医生业务量归属错误、收费错收、收费漏收、住院登记错误、作废和退废没有补齐手续、打错收费病人姓名。发现费用错、漏收要由收费员及时追回，如不能追回造成的医院损失由收费员承担。住院登记错误造成医护人员无法操作发现一次扣2分，造成医嘱错误发现一次扣2分，如因此错误造成医院的损失要接受处分。作废和退废没有补齐手续的，取消作废和退废操作，损失由收费员本人承担。由于收费员自身原因打错收费病人姓名，造成的纠纷发现一次扣1分，如收费员不能自行解决，需财务处理发现一次扣2分。

3．有明显医保不可报项目未作为自费项目另收，如造成医保部门扣款，除

1赔偿医院损失外，发生一次扣1分。

4．操作手续上错误造成病人投拆且已造成医院经济、声誉损失或病人的损失，除由当事人赔偿损失外扣5分。如发生以下几种操作错误除由当事人承担经济损失外，不论金额大小一律扣30分：无故不给病人付款凭据、对一些可操作的收款进行虚假作废、因需要使用手工票据时，采用大头小开或小头大开等虚假开票手段。

5．收费应做到日清月结，发现以下情况一次扣1分：没有按要求每日一结、发票整理不符合规定、发票未及时整理、帐款未按规定及时交清（发票要求当日或次日上交财务，遇节假日顺延，帐款除留不高于2000元的换零钞外，当日应全部缴入银行）。如私留帐款数超过规定数额10000元以内，发现一次扣2分，并罚5‰的滞纳金。如私留帐款数超过规定数额10000～20000元，发现一次扣5分，并罚5‰的滞纳金。如私留帐款数超过规定数额20000～30000元，发现一次扣10分，并罚5‰的滞纳金。如私留帐款数超过规定数额30000～50000元，发现一次扣15分，并罚5‰的滞纳金。如私留帐款数超过规定数额50000元以上，发现一次扣20分，并罚10‰的滞纳金，另处停职并报医院处理。

6．应妥善保管非电子凭证遗失发票一张扣2分。

7．不定期抽查监盘中如发现钱帐不符除个人弥补外扣20分。如数额超过1000元，停职，上报医院另行处理。

(2)、住院收费人员

1．如需住院处输入的费用应严格按照费用项目输入明细，如有疑问应及时告知科室负责人或联系相关科室，不明确前不可随意找项目代替，如发现检查单或其它联系单项目明细与发票清单明细不符每一项扣0.5分。属住院收费人员录入费用，不按明细输入或输入错误造成医保损失，每发现一项扣1分。

2．如需住院处冲销的费用应登记冲销原因及科主任签名，缺一项扣2分，如不能将记录补齐，已冲销的费用由收费员赔偿，并扣5分每次。

3．收费应严格按程序操作，发现以下操作错误一次扣1分：入院登记科室错误、入院登记住院号错误、收费错收、收费漏收。住院登记错误造成医护人员无法操作发现一次扣2分，造成医嘱错误发现一次扣2分，如因此错误造成医院的损失要接受处分。由于收费员自身原因打错收费病人姓名，造成的纠纷发现一次扣2分。

4．操作手续上错误造成病人投拆且已造成医院经济、声誉损失或病人的损失，除由当事人赔偿损失外扣5分。如发生以下几种操作错误除由当事人承担经济损失外，不论金额大小一律扣30分：无故不给病人付款凭据、无故漏记或冲减病人各项帐面费用。

5．收费应做到日清月结，不得私留帐款，发现私留处罚同门诊。

6．应妥善保管非电子凭证遗失发票一张扣2分。

7．如当月出院病人欠款率控制在0.5%以内，在院病人欠费控制在20%以内奖励附加0.05的欠费控制补贴。下例情况可除外：有本院职工提供担保、经批准由院方承担、统筹及公费结算、经院方批准可延期交款、经批准作为院绿色通道。

8、住院收费处应根据实际情况合理收取预缴款，对于可能欠费病人及时发放催缴通知书，不发放一次扣2分。本院职工担保必须有书面担保书，有关领导同意欠款应出具书面依据，无依据私自同意病人欠款，发现一次扣2分。

三）、环境卫生部分(总计10分)

科室内卫生保洁责任到人，每次卫生检查必须合格以上，不合格，当次打扫责任人扣完10分。每天由值班人员保持科室卫生整洁，不能保持扣1分。

二、财务人员奖金分配

一)、财务科长奖金分配

具体领导本单位财务会计工作，如以下执行正确奖金按核算至科室100%发放，每项执行有误扣2分：

组织编制本单位的财务计划、预算；负责审核对外提供的会计资料和会计报表；按时核算各月奖金；依法实行会计监督；按照物价局统一收费标准，合理组织收入。

二)、会计奖金分配

严格贯彻执行新修订的《会计法》、《医院会计制度》和各项财政法规，负责全院的会计核算，如以下执行正确奖金按核算至科室100%发放，每项执行有误扣2分：

科目运用正确，凭证填制准确及时；帐证、帐实相符；会计报表数字真实、编报及时；按时移交会计档案和会计资料文件。

三)、出纳奖金分配

严格遵守《现金管理暂行条例》和《银行结算制度》，如以下执行正确奖金按核算至科室100%发放，每项执行有误扣2分：

银行存款和现金的收、付结算帐实相符；不得挪用资金；按时发放工资、津贴、补贴、福利费；认真、及时、准确填写各类报表。

四)、明细帐会计奖金分配

严格执行医院资产管理的有关规定，如以下执行正确奖金按核算至科室100%发放，每项执行有误扣2分：

二次分配问题篇3

二次分配问题(quadratic assignment problem,QAP)是一个经典的优化问题,而且被认为是一种最难于求解的组合优化难题。许多实际问题,例如打字机键盘设计、校园和医院规划、背板配线和其他许多问题都可以归纳为二次分配问题。QAP可以描述成要将一个设备集合分配到一个位置集合上,给定了位置与位置间的距离和设备与设备间的流量,寻找这样一种分配方法,使得流量与距离乘积总和最小。

一般地,QAP可描述为:给定n台设备和n个位置,两个n×n的矩阵D=dij和F=fij,其中dij是位置i和j之间的距离,而fij是设备i和j之间的流量,目标函数是

$Ζ (φ) = \sum_{i = 1}^{n} \sum_{j = 1}^{n} f_{i j} d_{φ_{i} φ_{j}}$ 。

其中φi给出了设备i在当前解φ∈S(n)上的位置,S(n)是解空间,是整数集{1,2,…,n}的所有置换的集合。QAP的目标是找出一种把设备分配到位置上的分配方法,使得目标函数的值最小。

QAP是一个NP-难[1]的优化问题,当前精确算法求解QAP的规模不超过30[2]。因此,对于求解大规模的QAP,一种切实可行的方法就是应用元启发式算法[3],以便在较短的时间内找到高质量的解,如模拟退火算法、禁忌搜索算法、蚁群优化算法、遗传算法、粒子群算法、迭代局部搜索[4]等。在上述元启发式算法中,蚁群优化算法由于具有分布式计算,易于与其它算法相结合、鲁棒性强等优点,正受到越来越多的研究者的关注。当前,针对QAP的蚁群优化算法(ACO)包含了蚂蚁系统(AS)[5]、最大最小蚂蚁系统(MMAS)[6]以及受蚁群优化算法启发却又有着较大差异的算法如混合蚁群系统(HAS)[7]、快速蚁群系统(FANT)[8,9]等。

尽管已有许多ACO用于求解QAP,但FANT算法作为几个较好求解QAP的算法之一,一直以来受到较少的关注,最近关于FANT的讨论是邹鹏等[10]将骨架导向算法引入FANT,构造了近似骨架导向快速蚁群算法(ABFANT)。事实上,FANT算法具有收敛速度快、计算存储少等[9]优点,因此研究和改进FANT算法有着十分重要的意义。文章通过分析FANT算法信息素更新策略,改进算法中的参数R的设置,给出了针对求解QAP的新算法:变参数的快速蚁群系统(VPFANT)。在相同的迭代次数的条件下,利用二次分配标准问题库(QAPLIB)中的例子比较了VPFANT和FANT算法,测试结果表明:大约有90%的例子,VPFANT算法比FANT算法能够取得质量更好的解。本文的主要贡献在于进一步探索了元启发式算法中由搜索产生的问题解的存储和更新机制,为构建优良的元启发式算法,找到质量更优的QAP的解提供了可能。

1 快速蚂蚁系统

受早期AS研究成果的启发,E.D. Taillard开发了FANT算法。尽管它并不遵循ACO启发式算法的核心构建过程[11],总体上FANT算法也包含了解的构建、局部搜索、信息素更新三个步骤。FANT算法的基本理念是设计一种尽可能简单的方法,该方法能够整合解构建的探索性和重点搜索最优解的策略。这就意味着,一方面,通过更新信息素,要系统地加强选择最优解的权重;另一方面,如果算法出现停滞,重新设置信息素,清除那些最优解中含有较少权重的节点的信息素,提高这些节点的权重。在构建问题的解时,FANT不同于其他的ACO算法,它仅使用一个人工蚂蚁去构建问题的解,且和MMAS[6]一样,不使用任何启发式信息,在迭代过程中,蚂蚁通过概率选择规则pij把下一个还未被分配的设备i分配到一个空闲位置j上,其计算公式如下:

$p_{i j (t)} = \frac{τ_{i j}}{\sum_{l \in Ν_{i}} τ_{i l} (t)}$ 如果j∈Ni。

其中信息素τij指的是分配设备i到位置j上的权重,Ni表示设备i可分配的位置。人工蚂蚁通过不断地重复每一个设备的分配,最后得到一个分配方案,即构建了一个问题的解。

为了体现构建解的探索性和重点搜索最优解的策略,FANT设计了一种独特的信息素更新机制,它引入了一个固定参数R和可变量v。设信息素矩阵为Γ=(τij)n×n,初始地,令v=1,τij=v(i,j=1,2,…,n),迭代最优解为φib,则FANT重复执行如下步骤(算法1)。

(1.1)应用概率选择规则pij构建问题的当前解φ;

(1.2)利用局部搜索技术改进当前解φ,为方便计仍记为φ;

(1.3)如果φ=φib,则令v=v+1,τij=v(i,j=1,2,…,n);

(1.4)如果Z(φ)<Z(φib),则φib=φ,并设v=1,τij=v(i,j=1,2,…,n);

(1.5)τiφi=τiφi+1(i=1,2,…,n);

(1.6)τiφibi=τiφibi+R(i=1,2,…,n)。

为了加强迭代最优解φib邻近的搜索,迭代最优解φib对应的节点处的信息素在每次迭代时都增加R(步骤(1.6))。对于每次迭代产生的当前解φ,其对应的节点处的信息素加1[步骤(1.5)]。当迭代最优解φib目标函数值变少时,则可将变量v设为1,信息数矩阵元素τij重新初始化1[步骤(1.4)],此时相对地增加了迭代最优解φib节点的权重,问题的解着重在迭代最优解φib邻近搜索,体现了算法重点搜索策略。当构建问题的解出现φ=φib时,意味着迭代最优解φib对应的节点的权重太大,变量v将增加一个单位,元素τij重新初始化[步骤(1.3)],此时相对地减少了迭代最优解φib节点的权重,问题的解在较大的范围内搜索,体现了算法构建解的探索性。

2 变参数的快速蚂蚁系统

毋庸置疑,FANT算法针对ACO算法作了较大的改进,在信息素更新管理方面作了很大的探索。然而,从解的质量来看,FANT算法只是在较短的运行时间内总体上要优;在较长的运行时间内,尽管在少数问题上有优势,总体上并不比其它算法好[9],即FANT算法前期收敛速度快,后期容易出现停滞现象。究其原因,与FANT算法采用固定的参数策略有关,当参数取较小值时,迭代最优解φib的权重相对较少,算法探索的随机性增大,迭代最优解φib更新速度变慢,算法后期易发生停滞;当参数取较大值时,迭代最优解φib的权重相对较大,算法探索的随机性减少,问题的解在迭代最优解φib邻近搜索,迭代易陷入局部最优解,发生停滞。另外,E.D. Taillard[12]指出,启发式算法的性能依赖于所选择问题的类型,对于FANT算法而言,不同规模,不同类型的问题应选择不同的参数R,这样才能发挥FANT算法的最佳性能。图 1给出四个QAPLIB中的例子,利用FANT算法求解时相对误差百分比,参数R取值分别从1至10,算法每次迭代次数都是10 000次。

从图 1可以看出,对于不同的问题,FANT算法在不同值处取得迭代最优解,如Tai25a问题在R=4处取得迭代最优解;Tai40a在R=8处;ste36a在R=2,4,10处;sto49在R=5,8处。因此,对FANT算法来说,所有问题选择同一参数的策略是不明智和理性的,应根据不同规模、不同类型的问题选择不同的参数R,但是在算法求解具体问题的过程中,一般来说最优参数R预先是不知道的。为改善这一不利因素,可以设置参数随着迭代最优解的改变而发生变动来改进FANT算法,改进的FANT算法称为变参数的快速蚂蚁系统(VPFANT)。考虑到FANT算法在固定参数时前期收敛速度快,后期容易出现停滞现象,VPFANT算法在迭代开始时,参数R设为零,之后参数R在区间[Rmin,Rmax]取值。VPFANT算法描述如下,初始地,令R=0,v=1,τij=v(i,j=1,2,…,n),迭代最优解为φib,则VPFANT重复执行如下步骤(算法2)。

(2.1)应用概率选择规则pij构建问题的当前解φ;

(2.2)利用局部搜索技术改进当前解φ,为方便计仍记为φ;

(2.3)如果φ=φib,则令v=v+1,τij=v(i,j=1,2,…,n);

(2.4)如果Z(φ)<Z(φib),则φib=φ,并设v=1,τij=v(i,j=1,2,…,n),

(2.4.1) R=R+1,

(2.4.2)如果R>Rmax,则R=Rmin;

τiφi=τiφi+1(i=1,2,…,n);

τiφibi=τiφibi+R(i=1,2,…,n)。

从算法2可以看出,为了加强算法前期的搜索能力,初始的参数R设置为零。当迭代最优解φib目标函数值改善时,为了保持迭代最优解φib先进性,参数R将增加一个单位,加速算法的收敛[步骤(2.4.1)]。为了控制参数R过大而导致算法陷入局部最优解,当参数R大于Rmax,算法强制将参数R设为Rmin,增加算法的探索性[步骤(2.4.2)]。通过参数R在[Rmin,Rmax]之间来回的取值,既体现了算法的重点搜索策略,又保持了算法构建解的多样性,算法前期加强了解的搜索能力,后期减少发生停滞现象。

3 数值实验

这一部分我们选择QAPLIB中的问题做数值实验,测试了VPFANT和FANT算法。试验的硬件环境为Pentium(R)4 2.5 GHz,256 MB内存,80 GB硬盘,操作系统为Microsoft Windows SP3,开发工具为VC++6.0。对于FANT算法,参数R=6;VPFANT算法参数R的取值区间为[4]。作为迭代终止条件,当问题规模大于50时,迭代次数设为20 000次;问题规模小于等于50时,迭代次数设为10 000次。为了观测VPFANT和FANT算法的收敛行为,我们另外做了两组实验,对VPFANT和FANT算法分别测试了100次与500次迭代后算法的解。本实验采用的QAPLIB中的问题按文献[12]的分类分为四类。第一类,随机产生无结构问题,这类问题是根据均匀分布随机产生距离流量矩阵的问题。第二类,随机产生网格距离问题,这类问题的距离来源于一个网格,节点与节点的距离定义为网格上节点之间的曼哈顿距离。第三类,现实问题,这类问题是从实际问题抽象出来的。第四类,模拟现实问题,因为第三类现实问题规模较小,所以这类问题是根据现实问题的特点随机产生的较大规模的问题。另外,考虑到规模小于20的问题容易求解,这里只测试规模大于等于20的问题。数值实验结果见表1。

在算法运行的初期(100次迭代),由于FANT算法在每次迭代后都对迭代最优解φib增加较大的恒定信息素R,算法率先完成探索,开始了学习过程;而VPFANT算法由于参数R初始设为零,且迭代质量改善后每次才增加一个单位,故此时尚在探索阶段,算法解的质量无论从分类来看还是总体上都比FANT算法要劣在预料之中,例外只有Tai80a、sko42、ste36。随着迭代的进行(500次迭代),VPFANT算法完成探索过程,参数R逐渐增大,算法收敛速度加快,与FANT算法的差距逐渐缩小,且由于算法初期较多探索的积累,对于某些类问题或例子,其解的质量还要比FANT算法要优,如第四类模拟现实问题等。当算法运行结束时,总体上VPFANT解的质量比FANT算法要优,例外的例子只有Tai35a、sko72、kra30a。从分类来看,第一、二、四类问题VPFANT解的质量要优于FANT算法,第三类现实问题由于kra30a例子VPFANT解的质量比FANT算法差较多,加上这类问题例子较少,导致平均解的质量VPFANT要差一些。另外,值得注意的是,VPFANT算法在处理规模较大问题以及第二类随机产生网格距离问题和第四类模拟现实问题具有较大的优势,而且相对FANT算法而言,VPFANT算法还能在Tai80b、nug30、sko64问题取得已知最优解。

4 结论

尽管FANT算法在解的构建与信息素更新管理方面较其它ACO算法作了较大的改进,成为求解不规则QAP例子最具竞争性的算法之一[9], 但也有显著的缺点(即算法快速赋有侵略性、易发生停滞现象)。通过分析FANT算法的信息素更新机制,指出了FANT算法出现上述缺点的原因,给出了改进这些缺点的一个方法,提出了一种求解QAP的新算法—VPFANT算法。理论与实验分析表明,新算法较好地改进FANT算法的缺点,提高了QAP解的寻优能力,进一步改善了QAP解的质量。

摘要：二次分配问题(QAP)是经典的组合优化问题之一,广泛应用于许多领域中。通过分析快速蚂蚁系统(FANT)的信息素更新机制,引入一个变动的参数,提出了一种新的蚁群算法—变参数的快速蚂蚁系统(VPFANT)。该算法改进了FANT易发生停滞现象等缺点,拓宽了快速蚁群系统解的搜索范围,提高解的寻优能力。

关键词：二次分配问题,快速蚂蚁系统,停滞,变参数

参考文献

[1] Sahni S,Gonzalez T.P-complete approximation problems.Journal ofthe Association of Computing Machinery,1976;23(3):555—565

[2] Hahn P M,Hightower W L,Johnson T A,et al.Tree elaborationstrategies in branch and bound algorithms for solving the quadratic as-signment problem.Yugoslavian Journal of Operational Research,2001;11(1):41—60

[3] Nehi H M,Gelareh S.A survey of meta-heuristic solution methods forthe quadratic assignment problem.Applied Mathematical Sciences,2007;46(1):2293—2312

[4] Stutzle T.Iterated local search for the quadratic assignment problem.European Journal of Operational Research,2006;174(3):1519—1539

[5] Maniezzo V,Colorni A.The ant system applied to the quadratic as-signment problem.IEEE Transactions on Data and Knowledge Engi-neering,1999;11(5):769—778

[6] Stutzle T,Hoos H H.MAX-MIN ant system.Future Generation Com-puter Systems,2000,16(8):889—914

[7] Gambardella L M,Taillard E D,Dorigo M.Ant colonies for the quad-ratic assignment problem.Journal of the Operational Research Socie-ty,1999;50(2):167—176

[8] Taillard E D.FANT:fast ant system.Technical report IDSIA—46—98,Lugano:IDSIA,1998

[9] Taillard E D,Gambardella L M.Adaptive menories for the quadraticassignment problem.Technical Report,IDSIA—87—97,Lugano:ID-SIA,1997

[10]邹鹏,周智,陈国良,等.求解QAP问题的近似骨架导向快速蚁群算法.软件学报,2005;16(10):1691—1698

[11] Dorigo M,Stutzle T.Ant colony optimization.Boston:the MIT Press,2004

二次分配问题篇4

1 一般资料

我院是1所三级甲等综合医院, 住院病床1 200张。消毒供应中心实行集中管理的供应模式, 向全院及10个社区卫生服务站提供可复用医疗器材的回收、清洗、包装、灭菌、发放工作及一次性使用医疗用品的发放任务。消毒供应中心有工作人员23人, 其中护理人员5人, 工人18人 (含消毒员3名) ; 消毒供应中心的人力资源以经培训的工人为主, 护理人员为辅; 以工作区为单位, 3个工作区各配1名护理人员做质量监控, 护士长负责科室总的质量控制。工人在护理人员指导下从事可复用器械的回收、清洗、包装、消毒灭菌、发放工作及一次性使用医疗用品的发放任务。

2 方法

2.1 建立科室绩效考核小组

由护士长任组长, 每个工作区推荐2名人员, 共7名人员组成科室绩效考核小组。考核小组根据医院的考核方案, 结合科室情况, 制订本科绩效考核方案、绩效考核标准 (包括服务质量、工作质量、培训教学、协作精神及其他加分项) 及各工作岗位任职要求, 同时将绩效考核方案交科室全体人员讨论, 通过后上报护理部备案。

2.2 自主选择岗位, 竞争上岗

根据工作性质和要求, 科内设质量控制组长岗位、清洗岗位、包装岗位、灭菌岗位、无菌物品发放及保管岗位和辅助岗位。工作人员可根据工作岗位任职要求和自己的喜好, 选择工作岗位。岗位的确定需经个人申请及通过该岗位上岗前理论、相关技能考试合格后才能上岗。

2.3 分配系数设置

体现多劳多得、优劳优得, 向高技术、高风险岗位倾斜。设置岗位系数和班次系数。岗位系数由年资系数 (3个月～12个月为0.9, 1年～2年为1.0, 2年～3年为1.1, 3年以上为1.2) 、职称系数 (副主任护师为1.3, 主管护师为1.2, 护师为1.1, 护士为1.0, 消毒员为0.7, 无职称工人为0.6) 和能力系数 (顶固定班为1.0, 1个工作区顶班为1.2, 2个工作区顶班为1.7, 3个工作区顶班为2.2) 构成。班次系数 (主班、质量控制班为3.5, 无菌班为3.0, 分类班、炉班为2.5, 包2班为2.4, 包4班、包1班、洗班为2.2, 包3班为2.0, 下送、收送班为1.0, 其他班次为1.5) 。

2.4 计算方法

奖金由岗位奖金 (权重30分) 、班次奖金 (权重40分) 和质量奖金 (权重30分) 3部分组成。个人奖金=个人绩效总分×绩效分值奖+特殊奖;个人绩效总分= (年资系数×职称系数/岗位平均积分×岗位权重) +[ (班次1总数×班次1系数+班次2总数×班次2系数+……) /班次平均积分×班次权重]+ (质量分/质量平均积分×质量权重) ;绩效分值奖= (科室总奖-特殊奖) /全科人员总绩效积分;岗位平均积分=岗位总积分/考核人数;班次平均积分=班次总积分/考核人数; 质量平均积分=质量总积分/考核人数;将以上数据代入Excel表格, 奖金自动自成。

3 实施效果

在消毒供应中心按绩效考核成绩发放奖金实施1年, 临床科室对消毒供应中心满意度由92.84分±1.77分提高至96.89分±0.91分, 差异有统计学意义 (t=7.042, P<0.05) ;绩效考核前后护理缺陷发生率下降, 差异有统计学意义 (χ2=92.8, P<0.05) 。实施绩效考核前后护理缺陷发生情况见表1。

4 讨论

4.1 绩效考核激发工作人员工作积极性, 提高了临床满意度

建立管理科学的奖金分配制度是激发护士积极性的有效手段[3]。旧的奖金分配方案是按职称进行分配, 缺乏激励措施, 干好干坏一个样, 干多干少一个样。绩效考核的实施, 打破了传统的平均分配局面, 向责任性强、风险系数较高的岗位倾斜, 拉开了不同岗位之间的距离, 通过经济杠杆作用调整人员行为, 将服务质量、工作质量和数量与个人奖金挂钩, 调动了工作人员积极性和工作自律性, 提高了工作人员的组织意识和主人翁意识, 使工作人员转变了服务态度, 主动为临床提供全方位的服务, 结果显示, 虽然工作量增加了, 但临床科室对消毒供应中心满意度上升, 提高了临床服务满意度。

4.2 绩效考核促进了护理质量提高, 降低了护理缺陷的发生率

转变观念是消毒供应中心发展的关键[4]。传统的经验式管理方式和奖金分配方法已不能满足新形势下消毒中心的质量管理需要, 而落实绩效考核, 工作目标明确, 并把目标分解到每个人, 每个岗位及每件事, 这样每个人能找到自己具体工作, 对照标准积极认真完成。奖金分配时, 体现了奖勤罚懒, 奖优罚劣, 拉开了距离, 提高工作人员责任心及工作依从性, 从而减少了护理缺陷的发生。表1的结果表明, 在工作量增加的情况下护理缺陷发生率下降。绩效考核在消毒供应中心奖金分配中的应用为消毒供应中心的管理提供了有效的途径。

参考文献

[1]Garofalo G.中层主管成功宝典[M]//刘昕, 李原, 译.北京:经济管理出版社, 1998:143-144.

[2]陆小英, 张玲娟, 曹洁, 等.护理人员绩效考核评价方法研究现状与展望[J].中国护理管理, 2011, 11 (12) :46.

[3]冯艮娇, 罗思妮, 杨满青.绩效考核在奖金分配管理中的应用[J].现代临床护理, 2011, 10 (1) :60.

本文来自 360文秘网(www.360wenmi.com)，转载请保留网址和出处

【二次分配问题】相关文章：

分配问题分析06-18

订单分配问题07-29

分配制度问题04-19

生产任务分配问题07-13

选址与分配问题06-08

分配问题的求解06-13