论文研究-多资源约束下改进NSGA-II算法的手术调度.pdf

所需积分/C币:9 2019-09-20 17:08:02 780KB .PDF

论文研究-多资源约束下改进NSGA-II算法的手术调度.pdf,  针对手术调度涉及因素众多难以优化的问题, 在考虑手术台、执刀医师等资源约束,构建了以病人满意度及手 术总流程时间为目标函数的模糊调度数学模型. 针对传统的加权系数方法不能很好地解决手术多目标优 化问题,提出改进的非支配排序遗传算法(non-dominated sorting genetic algorithm II, NSG
第6期 邓富民,等:多资源约束下改进 NSGA-II算法的手术调度 1339 在满足以上目标的同时,手术过程中还需要满足以下约束条件: 1)手术室约束:同一手术台上一个手术任务完成后才能开始另一个手术任务 Cabl-Ci-IL-Tabl2 Sabl, XiL=Xabi=l, RijabL=1 其中,CabL,C1(-1):表示执刀医师a()在第L个手术台为第b(-1)个病人实施手术的完成时间;Tab 执刀医师α在第个手术台为第b个病人实施手术的持续时间;Sab:表示执刀医师a在第L个手术台为第 b个病人实施手术的设置时间 1,执刀医师的第个病人在手术台L进行手术 5 其它 1,执刀医师讠的第j个病人和执刀医师a第b个病人在同一手术台L手术,若病人j先于病人b 0,其它 2)执刀医师约束:两个不同的手术不能同时分配给一名执刀医师,而且任何一名执刀医师在任何时候都 不能同时参与一个以上的手术 cQhl- Fpgsl h ZiQhpgsl +h(- XiQ(1-Xpa)> tighT Fpasl-FiQhl+ h(1-ZiQhpgsl)+H(1-XiQ)+h(1-Xpg)2 tpgsl (8) 其中,H为非常大的正数;TQhL和FQhL分别为执刀医师i的第Q个手术预案中的第h个病人在第L个 手术台实施手术的持续时间和手术完毕时刻;zQhm.为第L个手术台安排病人h和s的顺序判别条件, 当病人b和s都在第L个手术台手术时,如果执刀医师a的第Q个手术预案中的第h个病人先于执刀医 师p的第q个手术预案中的第6个病人实施手术,则 Ziqhpgsl=1,否则 Zighpgsl=0. 1,执刀医师讠选择第Q个预案 0,其 3)手术完工约束,执刀医师的第个病人手术完成时间满足如下约束 max STii+Tij+ 1<j≤l (10 其中,ST;为执刀医师i的第j个病人的手术可以开始时刻 然而.执刀医师i的第1个病人手术完成时间C1,满足如下约束 S⑦2+T1+S2 4)手术过程约束,每个执刀医师的每个病人在任何一个手术台手术时不允许中断 3改进NSGA-ⅠI算法 针对多资源约束的模糊手术调度问题,设计相应的改进NSGA-I算法;针对执刀医师和手术室可供选择 的间题,设计了二层编码体系;针对模糊信息处理需求,设计了基于梯形模糊数的病人满意度隶属函数.整个 算法的执行过程由三部分组成:1)首先对种群中的每个个体按 Pareto进行排序分级,所有非劣个体被分为 类,分配给这类个体一个秩号,秩号较小的个体优先被直接复制到下一代群体,若某些个体有相同的秩值, 则计算非劣解等级内个体拥挤密度;2)然后通过自适应遗传操作产生较优良的一个群体,再利用精英策略进 行基因个体的优化调整:3)运行过程反复迭代,直到满足终止条件为止.这种算法的思想策略是从全局最优 解搜索和算法进化速度的角度提高算法的性能,具体体现在以下两个方面: 1)算法结构的互补、引入自适应交叉和变异概率操作,通过赋予搜索过程一种时变的概率突跳性,自动 控制当前搜索行为,防止过早陷入精细搜索过程;引入精英策略,通过优秀个体的遗传进化,引导种群向全局 最优解聚集 ②)算法参数改进的结合引入基于小生境尺寸的拥挤密度排序法,在表现型目标空间上构建小生境环境, 以小生境尺寸内拥有的个休数量作为衡量个休进化的标准;采用改进精英保留策略,通过每一非劣等级个休 的不完全选择机制,保持种群的多样性,防止种群的早熟收敛;引入交叉和变异慨率的动态调整机制,感知并 自动调整局部搜索深度. 改进 NSGA-II算法流程图如图1所示 1340 系统工程理论与实践 第32卷 初始化 ‖随机产生初始化种群10 t+1 。对P解码 对种群各个体进行评价 一等级分类与圳挤密度>百一快速非文限排序对群体 得到子种群Q 算完成? 进行丰劣分层 合并:RPUQ, 锦标赛选择计算 Rank=Rank+1 算R;中各个体的目标倒 为行交叉操作 白适应交叉概率尺 计算拥挤密度 进行快返非支配排序 自 将所选中父代个体作为临时个体 先出前M个个体产生父代 种群各个休进行评价 种群NP 交 百适立变异概率P>0 变 →执行变异操作1 达到规定的最人代数 异 是 作 将所选中个体作为临时个体 结束 F价 对种群各个体进行评 图1改进NSGA-II算法流程图 改进NSGA-II算法步骤描述为 步骤1设置进化代数计数器t=1,随机产生含m个个体的初始种群P(t): 步骤2按照约束条件对染色体进行解码; 步骤3计算每个个体相应的分目标函数值f1(=1,2,…,m,=1,2,…,g)、9为目标个数; 步骤4判断等级分类与拥挤距离计算是否完成,如完成则转到步骤7,如未完成则转到步骤5; 步骤5快速非支配排序.根据目标函数值进行非劣分层,将当前种群中历有非劣解个体划分为同一等 级,令其等级为1;然后将这些个体从种群中移出,在剩余个体中找出新的非劣解、令其等级为2;重复上述过 程,直至种群中所有个体都被设定相应的等级 步骤6计算同一非劣等级内个体的拥挤密度; 步骤7锦标赛选择.随机选择两个个体,首先比较非劣前沿等级,如果非劣等级不同,则取等级级数较 小的个体,如果是在同一等级的个体,则再比较其拥挤密度,取密度较小的个体,形成种群Pop1(t); 步骤8采用自适应交叉、变异操作.生成群体Q; 1)采用自适应单点交叉算子对种群Pop1(t)进行交叉操作得种群Pop2(t) 2)采用自适应均匀变异算子对种群Pqp2(t)进行变异操作、得到种群Q 步骤9合并P和Q构成新群体R; 步骤10计算新种群中,各个个体对应分目标的函数值; 步骤11采用步骤5相同的方法,对新种群进行快速非支配排序; 步骤12选择前N个个体产生新一代种群NP; 步骤13判断是否达到最大迭代次数,如是,则结束运算输出结果,如否,则迭代次数加1,转到步骤2 31快速非支配排序 步骤1对当前种群P中的所有个体p作如下操作 ①初始化集合Sn=φ,该集合包含被个体p所支配的所有个体 ②初始化变量mp=0.该变量表示支配p的个体数日 ③计算支配与被支配关系,变量p,q∈P,如果p支配q,则Sp=Spu{q};如果q支配p,则mp=mp+1; 如果mn=0,表示p为无文配个体,属于第一层,即pamk=1,将他们存入当前集合F,F1=F1U{p} 第6期 邓富民,等:多资源约束下改进 NSGA-II算法的手术调度 1341 步骤2令=1,当F≠时,设Q=;对每个个体q∈Sn,令mq=mq-1,若m=0,则 grank=2+1 令Q=QU{q},2=1+1,F=Q; 步骤3若F=φ,则停止,否则转入步骤2 3.2改进的拥挤密度排序法 传统的NSGA-算法虽然在性能上比NsGA有较大改善,但是对于规模大、日标多、约束多的复杂调 度问题0,NSGA算法仍然需要花费较多的时间.特别是同一非劣等级内个体的排序,需要比较两两之 问的距离,计算量较大,为此提出基于小生境尺寸的改进拥挤密度排序法.具体是通过染色体的拥挤度CD 来实现的.某级非支配染色体集上第讠个染色体的拥挤度CDz可按式(12)计算. INF f2ax=fHk()=8东k()=f CD ∑ ∫k(2+1)-fk(-1) f0≠f1 (12) fmax-fh 式(12)中,m为优化目标数,fk为第k个目标 函数.当m-2时、拥挤度计算示意图如图2所 示,从式(12)及图2可见,拥挤度CDz越大,则说 明染色体周围的点越稀疏,在进行进化时应当给以 较大的生存穊率,从而保证种群多样性.例如图2中, CDA<CDB,应当给B点以相对较大的生存概率 通过这种小生境划分,就可以根据小生境中属于同 非劣前沿等级的个休密度的不同,选择相应的拥挤密 度较小的个体进入下一代进化,以此来维持分布的多 f 样性,确保算法的收敛到一个均匀分布的 Pareto曲 面 图2拥挤度计算示意图 33改进精英策略 精英策略即保留父代中的优良个体直接进入子代.采用的方法是:①将父代P和子代Q全部个体合 成为一个种群R1=PUQt,Rt的个体数为2N;②将种群Rt的每个个体按 Pareto进行排序分级,排序号 较小的个体被复制到下一代群体,若某些个体有相同的序值,则计算非劣解等级内每一个体与该等级其他个 体的距离,按照由疏到密的原则逐个将个体复制到下一代进化群体,此过程重复至下一代群体规模达到进化 群体规模为止.主要流程及改进表示如下: 步骤1对规模为N的种群P进化操作以后产生的新种群为P,新旧种群合并生成规模为2N的种群 Qt,Qt=Pt∪F 步骤2对种群Q进行快速非支配排序得到非支配解集{F1,F2,…},设Pt+1=9,i=0,、当|Pt+1+ F≤N时,P-1=P+1~F,i=i+1;否则计算F中个体的拥挤距离,首先,排序边缘上的个体具有 选择优势给定一个大数L口1D=L四D=M,以此保持种群多样性,其次,计算ma-2个个体中任意个 体;与其他个体的距离和d=√∑k=12k,并根据n关系按降序排列各,得到a1,12…,m P+1=P+1UE[1:(N-|Pt+1) 步骤3t=t+1,若t≥T(T为进化最大代数),算法终止,否则,进入步骤 3.4算法编码 编码就是解的基因表达,是目标空间到决策岑间表征的转化过程,是优化过程中遇到的首要问题.多名资 源约束手术模糊调度问题需要为每个病人选择手术台和执刀医师,因此,其相应的编码由三部分组成:第一部 分是病人染色体,即确定所要手术的病人,对应病人排疗问题;第二部分是手术台染色体,确定为病人实施手 术的手术台,对应手术台选择子问题;第三部分是执刀医师染色体,确定手术执刀医师,对应人员选择子问题 本文采用基于病人、手术台和执刀医师相结合的三层编码体系.整个编仍体系由三段染色体共3∑=1个 基因组成,第一层采用基于病人进行编码,给所有同一类新型的病人指定相同的符号,然后根据它们在给定 染色体中出现的顺序加以解释;第二层是手术台编号,根据病人类型选择可以手术的台进行手术;第三层是 执刀医师编号.这种三层编码方式满足手术台和执刀医师可选的约束条件,将三段染色体基因对应起来,总 能够保证产生可行调度.此外,它具有编码空间小,避免死锁、半 Lamarckian等特点. 1342 系统工程理论与实践 第32卷 病人 21 手术台室)M1M1M2M1M2M3M 执刀医师HnH21H2 图3染色体编码 35解码操作 从三层染色体编码中取出病人基因P(基因长度矩阵:1,∑-1)、手术台基因Ma(基因长度矩阵: (2=1j)+1:2(∑}=1)),执刀医师基因Pe(基因长度矩阵:P2∑=1)+1:302=1),读取病人类型 编号b,该类型下的病人排序编号a,对应手术台L,执刀恢师Per; 2)计算总生产流程时间: ①确定手术开始时间TMva,同一类型疾病的上一个病人手术完成时间 PVal,执刀医师完成手术时 间 PEnal; ②取最大时间,wl=max(TMvl,TPua, T Penal); ③计算相同类型下的病人手术开始和完成时间,Pva(1,i)-vl,Pal(2,;)-vl+t; ④记录病人手术占用手术台时间、手术完成时间和执刀医师完成手术时间, TMual= Pval(2,i), TPual= Pual(2, i). TPeval= Pval(2, i); ⑤计算全部手术完成总时间 f该类型的病人手术完成 Timefinish(b)=Pval (2, i) End ∑ Time,finish(b) b=1 3)计算病人满意度, F Dtime表示病人对手术的梯形模糊期望矩阵: TAll=0 for i=1: n ane Time finish(i) Ftime= FDtime(i, : if time Ftime(1), A-0 else if time x Ftime(2 ) &&time> Ftime(1) A=(tine- Fline(1))/(Fline(2)-Flirne(1)) else if time < Ftim. 3)&&time> Ftime(2) A=1 else if time Ftime(4)&&time> Ftime (3) A=l-(time- Ftime 3))/(Ftime(4)-Ftime 3)) ls en TVall=TVal1+A end 6自适应交叉变异操作 在进化过程中,P越大,产生新个体的速度就越快,然而,PC过大使得具有高适应度的个体结构很快就 会被破坏,若Pc过小会使搜索过程变得缓慢甚至停滞不前;如果PM过小,不能维持种群的多样性,造成算 法过早收敛;如果PM取值过大,接近最优解的遗传模式会被破坏.为了避免NSGA-I因选用固定交叉和变 第6期 邓富民,等:多资源约束下改进 NSGA-II算法的手术调度 1343 异概率带来的弊端,本文引入自适应策略,则既可以兼顾全局搜索和局部寻优,又可以动态地控制遗传操作 频率,提高搜索对空间变化的适应能力,具体方法如下: 1)自适应交叉算子 在进化的过程中,使交叉概卒随着适应度值自动地调整,既克服了不成熟的收敛,又避免优秀染色休被 破坏.交叉慨率的自适应调整公式为 x、W)(f-Jm,f2fag aUg Pcl 2)自适应变异算子 变异操作也是增加种群多样性的一种进化手段,适度的变异,既能保持种群内个体的多样化,又能提高 算法的效率,克服遗传操作可能限于局部解的弊端.变异慨率的自适应调整公式为: (PMI- PM2)(fmax-f M1 max (14) 式中,Jmax为群体中最大的适应度值,Jang为每代群体的平均适应度值,∫表示交叉的两个个体中较大的适 应度值,f*要变异的个体的适应度值 由公式(13)和(14)可知,引入自适应交叉和变异策略,解决进化过程中因交叉和变异概率固定不变所 导致的收敛速度缓慢的问题,克服了种群早熟化的固有弊端,改善算法收敛速度. 3)交叉操作 根据上述染色体编码方案,设计了相应的交叉变异操作.这里采用基于病人顺序的交叉、基于手术台分 配的交叉和基于执刀医师分配的交叉相结合的交叉方法.对于基于病人顺序的交叉,山现行的手术制度可知, 同一类型疾病的病人手术排序(由每个科室呈报)一旦预先确定就需要保证先后顺序,因此交叉时要保证相 同类型疾病的病人先后次序不变.对于基于手术台分配的交叉则采用单点交叉方法,对选定的两个父体,随 机选择一个交叉点,将位于交叉点前的两个父体都有的病人所分配的手术台进行交换.对于基于执刀医师分 配的交叉是将位于交叉点前的两个父体都有的手术台所分配的执刀医师进行交换 4)变异操作 对于基于病人顺序的变异,选定一个个体作为父体,然斤随机选择一个病人,由于同一类型疾病病人手 术先后顺序的限制,要在保证同类型疾病病人在手术过程中次序不变的前提下,使对应一个疾病类型手术次 序的某个基因插入到另外一个疾病类型手术对应的基因组中.对于基于手术台分配的变异,由于每个疾病类 型下的病人都可以选择多个手术台进行手术,可以把完成该疾病类型的手术台放在一个集合中,从中选择异 于先前进行该类型疾病的手术台.对于执刀医师的变异,采用与手术台相同的方式 4实例仿真 针对某三甲医院泌尿科和胆道外科手术调度问题,应用该算法进行优化,手术相关信息如表1所示.改 进算法参数设置如下: Maxgen=120、 Popsize=200、交叉率计算参数PC1=0.9,P2=0.6;变异率计算参数 P1=0.1,PM2=0.001 分别采用改进NSGA-II和NSGA-II算法对案例进行优化,运行120次,出现次数最多的 Pareto优化 结果如图4和5所示,其手术调度方案如表2所示 由图4和5对比分析可知,NsGA-Ⅱ算法种群分布表现在病人满意度上为3个层面,其中非劣解介于 病人最大满意度层面(4.4,46)与总流程时间(6000100交叉区间;改进NSGA-II算法种群分布范围更 加广泛呈现5个病人满意度层面其中绝大多数非劣解解集中在病人最大满意度层面(55.5]与总流程时间 (600012000)的交义区间;可见,改进NSGA-I算法保证了解的多样性,同时在保证总流程时间基木不变的 前提下、大幅提高了病人满意度.图中非劣解的分布所以出现断层分布是因为病人满意度是梯形区间,使得 落在满意度区间的解相对较少.表2为改进NSGA^算法输出的其中两个非劣解调度方案,调度管理人员 可以权衡总流程时间和病人满意度进行调度方案的选择.该方法为手术调度管理人员提供了多种决策方案, 能够满足医院的实际管理需求. 1344 系统工程理论与实践 第32卷 表1手术相关信息 科室疾病类型病人编号手术间代码手术台执刀医师准备时间手术时间清洗时间满意度区间 200700303005 15 10 200700453005 1.3 13 75 900,1050,1250,10000 200700353001 1,4 3:30 泌尿科2 20070087:002 1.2 1,5 100 50 15 900,1200,1500,7000 200701473004 2.3 4,5 120 510 50 200700553003 1,3 6,7 15 200701173002 7,8 900,10001009000 200700923001 1.3 6,7 15 5 15 200701641014 7,8 140 10 200701391046 6,3 95 20 900,100010,7000 200701291021 5,450 1305 200702611059 1.3 5,7 75 145 10 胆道科 200701561020 4,8 70 165 15 800,900,1100,12000 200701791057 ,57,2 130 10 200704081036 5,4 5 200700651013 4.5 1,7 10 20 950,10001100,9150] 200701761022 1,6 7,5 35 10 多日标解分布图 多日标解分布到 …命● ●●告命● 总流程时间 总流煋时叵 图4NSGA-II算法输出的非劣解 图5改进NSGA-II算法输出的非劣解 表2手术调度方案 5 病人排序 4 2 3 5 4 6 64622122 53532121 2 6 手术台 1 2 1 2 5 3 执刀医师 5 3 21 5 4 4 4 3 第6期 邓富民,等:多资源约束下改进 NSGA-II算法的手术调度 1345 5结论 作为医疗服务中的关键环节,手术室的有效利用是医院管理水平的重要体现之一.针对手术调度优化模 型这一前沿硏究冋题,建立∫基于改进NSGA-Ⅱ方法的多目标模糊调度模型.该模型采用改进的拥挤密度排 序法改善同一非劣等级内个体的排序,并提岀釆用自适应交叉和变异策略和改进精娛簧略改善算法性能.从 而,为手术调度研究领域提出一套量化可行的参考排序方法.论文主要研究结论如下: 1)构建了以病人满意度及手术总流程时间为目标函数的模糊调度数学模型,同时考虑手术台、执刀医师 等资源约束,提出一套与手术调度实践比较接近的应用理论模型 2)提出了改进非支配排序遗传算法,采用染色体拥挤度的计算代替染色体两两之间的距离的比较,减少 算法计算复杂度;引入自适应交叉和变异策略,动态调整交叉和变异概率改善算法收敛速度;采用改进精英 策略,对同一非劣解等级中的边界个体赋予较大的拥挤距离,使其能够进入下一代进化群体,以此保持种群 的多样性,拓宽搜索范围,改善」算法搜索性能 3)建立基于病人、手术台和执刀医师相结合的三层编码休系,实现了多层约束问题的基因表达,任意编 码并总能产生可行调度 4)将改进的非支配排序遗传算法应用于本文提岀的手术调度模型求解,以6种疾病类型、18台手术、6 个手术台的一个具体事例验证了调度模型的有效性、可行性和先进性,证明该方法能够提供一套可供参考的 手术调度解决方案 进一步的研究将细化病人于术需求约束,综合考虑手术时间窗、于术成本、于术准备等影响因素的于术 调度模型,提出更为完善的手术排序解决方案 参考文献 1]舒文,罗利基于目标规划的外科手术调度研究[.技术与市场,2008(2):4243 Shu w, luo L. Surgical operation scheduling based on the object programmingJ. Technology and Market 2008(2):4243 2贾清萍,贾仁安,甘筱青.江西新型农村合作医疗制度实施效应反馈仿真分析「J.系统工程理论与实践,2010,30(5): 888898 Jia Q P, JiaR A, Gan X Q. Feedback simulation analysis on the effect of the implemented new rural cooperative medical policy in Jiangxi ProvinceJ. Systems Engineering Theory Practice, 2010, 30(5):888 898 3 LaIniri M, Xie X L, Dolgui A, et al. A stochastic Inodel for operating rooInl planning with elective and energency demand for surgery J. European Journa l of Operational Research, 2008, 185: 1026-1037 L Blake J T, Dexter F, Donald J Operating room managers'use of integer programming for assigning block time to surgical groups: A case study J. Anesth Analg, 2002, 94(1): 143-148 5 Jebalia A, Hadj Alouane A B, Ladeta P. Operating rooms scheduling J. Int J Production Economics, 2006, 99 52-62. 6 Cardoena B, Demeulemeester F, Beliena J. Sequencing surgical cases in a day-care environment: An exact branch-and-price approach[J]. Computers Operations Research, 2009, 36: 2660-2669 [7 Pham D N, Klinkert A. Surgical case scheduling as a generalized job shop scheduling problem[J. European Journal of Operational rcscarch, 2008, 185: 1011-1025 8 LaIniri M, Xie X L, Dolgui A, et al. A stochastic Inodel for operating room planning with elective and energency demand for surgery J. European Journal of Operational Research, 2008, 185: 1026-1037 ⑨]杨亚萍,杜树新.基于合同网机制的分布式办同医疗诊断系统.系统工程理论实践,2002,22(6):8086. Yang Y P: Du s X. Distributed collaborative medical diagnosis system based on the contract net mechanismJ Systems Engineering- Theory Practice, 2002, 22 (6):80-86 10 Ozkarahan I. Allocation of surgeries to operating rooms by goal programing. Journal of Medical Systems, 2000, 24(6):339378

...展开详情
试读 9P 论文研究-多资源约束下改进NSGA-II算法的手术调度.pdf
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-多资源约束下改进NSGA-II算法的手术调度.pdf 9积分/C币 立即下载
    1/9
    论文研究-多资源约束下改进NSGA-II算法的手术调度.pdf第1页
    论文研究-多资源约束下改进NSGA-II算法的手术调度.pdf第2页
    论文研究-多资源约束下改进NSGA-II算法的手术调度.pdf第3页

    试读已结束,剩余6页未读...

    9积分/C币 立即下载 >