多目標粒子群算法在醫(yī)院床位安排中的優(yōu)化應(yīng)用①

沈良生, 鄧子龍

(安慶職業(yè)技術(shù)學院，安徽 安慶 246003)

0 引 言

醫(yī)院床位的合理安排涉及醫(yī)院床位利用率、醫(yī)院效益和患者滿意度等多個方面，是典型的多目標優(yōu)化問題。針對床位資源的合理配置，學者們展開了大量研究，文獻[1]從國家政策、醫(yī)院管理、病人結(jié)構(gòu)等方面討論了醫(yī)院床位的使用效率問題；文獻[2]從醫(yī)療市場、疾病譜、醫(yī)學模式、付費方式等幾個方面，討論了醫(yī)院床位的配置標準；文獻[3]建立了病人等待時間模型，將目標函數(shù)設(shè)置為最優(yōu)平均等待時間，將病床安排具體模型化。上述實踐多停留在定性層面或?qū)⒉〈舶才诺刃С蓡文繕艘?guī)劃問題，沒有綜合考慮醫(yī)院和病人等多方需求。針對醫(yī)院病床安排問題展開研究，將醫(yī)院病床安排轉(zhuǎn)換為多目標優(yōu)化模型，并利用多目標粒子群算法加以求解。

1 醫(yī)院床位安排問題建模

(1)床位安排的多目標優(yōu)化問題

假設(shè)醫(yī)院某科室空余床位N0張，現(xiàn)有n種病的患者排隊住院，每種病包含患者的數(shù)量矩陣為M0，要求從這n中病人中，擇優(yōu)選出N0個病人入院。由于病情嚴重情況(不考慮急癥需立即安排入院的情況)，即使患相同疾病的患者住院時間及開銷也會不同。設(shè)P0表示入住病人的已等待時間(天數(shù))矩陣，V0表病人入院后的擬住院時間(天數(shù))矩陣，C0表示病人住院期間的醫(yī)療保障支出。

衡量病床安排方案是否最優(yōu)，要從醫(yī)院和患者兩方加以考慮。醫(yī)院方面，通常以病床周轉(zhuǎn)率來衡量病床安排的合理性，周轉(zhuǎn)率最高，等效于病人的總住院時間最短；同時，醫(yī)院還需綜合考慮患者滿意度，患者滿意度主要與病人等待入院時間相關(guān)，即病人等待入院時間越長，入院安排的優(yōu)先級越高。

因此，病床合理安排可歸結(jié)為病人總住院時間最短和已等待時間最長的雙目標優(yōu)化。同時，醫(yī)療保障支出是院方與政府的經(jīng)濟支出，一次病床安排所需的醫(yī)療保障支出不宜過高，因此，可將一次病床安排所需的醫(yī)療保障支出作為限制條件。

(2)多目標背包問題模型

設(shè)計一種方案，將多種物品放入背包中進行運送，要求運送物品的總價值達到最大，總體積為最小，同時運送物品質(zhì)量在一定的限制范圍內(nèi)，這就是多目標背包問題。假設(shè)物品的種類數(shù)為N，每一個種類包含的物件數(shù)為M，從每類物品中選取一個物件放入背包。待運送物品價值矩陣為P，體積矩陣為V，質(zhì)量為C，選擇矩為X。多目標背包問題可用下式描述：

(1)

其中，P、V、X都是M×N的矩陣，Z表示對于背包的質(zhì)量限制。

(3)病床安排與背包問題的轉(zhuǎn)化

病床安排問題與背包問題有相似之處，但也存在差異，如床位數(shù)N0與病種數(shù)n之間并不匹配；安排病人時，不一定按患病種類進行挑選；每種病包含病人數(shù)不一定相同等問題，使病床安排問題不能套用背包模型求解，需進一步處理、簡化。將病床安排問題轉(zhuǎn)化為背包問題求解，可進行以下幾方面簡化：

(1)出于手術(shù)安排方便等原因，醫(yī)院病床安排中常采用“異種病優(yōu)先”原則[3]，每次安排病床時，優(yōu)先選擇患不同病的病人，如眼科空余兩張病床，白內(nèi)障、眼科外傷各有若干患者等待入院，若一張病床安排了白內(nèi)障病人，則另一張病床優(yōu)先安排眼科外傷病人；

(2)床位數(shù)N0與病種數(shù)n不相等時，可直接假設(shè)N0=n,當N0小于n時，根據(jù)得到的選擇方案，優(yōu)先安排被選擇的病人，被選擇到但因床位數(shù)未安排的病人，可以確定優(yōu)先級，優(yōu)先安排至下一階段空出病床中；而當N0大于n時，從N0張病床中選出n張病床，進行優(yōu)化方案求解，再比較N0-n與n的大小，如(N0-n)>n則繼續(xù)從剩余床位中選擇n張進行床位安排，反之，則按照床位數(shù)小于病種數(shù)的情況進行求解；

(3)每種病包含的病人數(shù)不同，這會導(dǎo)致各矩陣各列包含的元素個數(shù)不同，這種情況下，將每種病包含的病人數(shù)按已等待天數(shù)進行排序，然后，設(shè)n種病中，包含患者數(shù)量最少的為第n0種病，包含患者數(shù)為a,則從各種病中，依據(jù)等待天數(shù)排序后，各選擇a個患者，重新組成各個矩陣。

經(jīng)過以上處理，病床的合理安排問題就可描述為，現(xiàn)有n種病的病患，每種病包含M0個病患，已知所有病患的已等待時間矩陣P0，擬住院時間矩陣V0，醫(yī)保支出矩陣C0。要求從這n種病的病患中，各選擇一個病患，在保證一定醫(yī)保支出的前提下，使選擇的病人已等待時間最長、總住院時間最短。這就將病床安排問題等效為背包問題進行求解。該問題可用公式表示為：

(2)

其中，P0、V0、X0都是的M0×n矩陣，Z0表示對于一次入院安排醫(yī)保支出的限制。

2 經(jīng)典粒子群算法

在經(jīng)典粒子群算法中，所有粒子搜索時都要在限定區(qū)域內(nèi)，并滿足一定的限制條件。假設(shè)粒子在D維空間進行搜索，粒子數(shù)為m，則基本過程描述如下：

(1)初始化粒子位置、速度

隨機初始化粒子的位置和速度，假設(shè)Xi=(xi1,xi2,...,xiD)是粒子i的初始位置；Vi=(vi1,vi2,...,viD)是粒子i的初始速度；

設(shè)集合Pi=(pi1,pi2,...,piD)為單粒子最優(yōu)解，用來記錄粒子i經(jīng)歷過的最好位置；設(shè)集合Pg=(pg1,pg2,...,pgD)為全體粒子最優(yōu)解，用于記錄所有粒子經(jīng)歷過的最好位置。從定義上可以看出，Pg中元素的值對應(yīng)于Pi(i=1,2,...,m)中的最優(yōu)值。

圖1 經(jīng)典粒子群算法流程圖

(2)選擇迭代更新策略

根據(jù)上述參數(shù)，更新位置、速度的公式為：

(3)

其中，d∈[1,2,...,D]，w表示粒子當前時刻的狀態(tài)受前一時刻狀態(tài)的影響程度，即慣性權(quán)重；c1、c2為學習因子，一般取c1=c2；r1、r2為擾動系數(shù)，用來表示搜索的隨機性，從而增大各粒子的遍歷空間，其通常在[0,1]之間隨機取值。

(3)更新最優(yōu)位置

(4)設(shè)定停機準則

一般而言，尋優(yōu)算法都要設(shè)定相應(yīng)的停機準則，普遍遵從以下原則：

1)對迭代次數(shù)進行設(shè)定，使其達到規(guī)定次數(shù)；2)全局最優(yōu)位置在連續(xù)規(guī)定的次數(shù)內(nèi)沒有變化；3)在連續(xù)規(guī)定次數(shù)內(nèi)，全局最優(yōu)位置的改善量不能大于或等于規(guī)定界限。

圖1所示即為經(jīng)典粒子群算法流程圖。

3 多目標粒子群算法

多目標粒子群算法相較于經(jīng)典粒子群算法，其目標函數(shù)為多個，應(yīng)用時具有一定的局限性。為了解決在應(yīng)用粒子群算法時的局限性問題，對算法進行了如下改進：一是假設(shè)在某次迭代后，某粒子的最優(yōu)位置解不單一，存在多組非劣解，則歷史最優(yōu)解采取隨機選擇的方式從中擇一而定；二是采取某種特定準則，在眾多粒子的非劣解集中，確定某次迭代后的全體最優(yōu)解，目前而言，根據(jù)“擁擠度”選擇全局最優(yōu)解是較常見的方法，通常情況下，為了保證能夠最大程度的遍歷所有未知區(qū)域，全局最優(yōu)解要在不是特別“擁擠”的區(qū)域選擇。確定各粒子“擁擠度”時，一般采用自適應(yīng)網(wǎng)格法。

綜上所述，多目標粒子群算法流程如下所述：

(1)對種群進行初始化，將搜索過程中發(fā)現(xiàn)的全局最優(yōu)解的全體非劣解存儲在某設(shè)定的非劣解集中；

(2)通過迭代、更新產(chǎn)生下一代粒子的位置，并存儲在相對應(yīng)的非劣解集中；

(3)通過篩選比較，從每一個粒子的非劣解集中選出歷史最優(yōu)解，進而確定全局最優(yōu)解的非劣解集；

(4)不斷重復(fù)(2)-(3)，直至滿足停機準則；

(5)將最終得到的非劣解集輸出。

4 實例分析

為了驗證多目標粒子群算法的優(yōu)劣，下面將以醫(yī)院床位安排為實例，分別利用多目標粒子群算法、加權(quán)法進行求解，并對結(jié)果進行比較。

參數(shù)設(shè)置：某醫(yī)院眼科現(xiàn)有空余床位5張，現(xiàn)有白內(nèi)障(單眼)、白內(nèi)障(雙眼)、青光眼、視網(wǎng)膜疾病、眼科外傷等5類疾病的患者等待入院，每類疾病排隊等待的患者數(shù)量、已等待天數(shù)、擬住院時間以及估算的醫(yī)保支出如表1所示，要求給出一種合理的病床安排方案，限制條件是一次病床安排醫(yī)保支出不大于85000元。

表1 排隊入院患者參數(shù)表

根據(jù)以上參數(shù)，已等待時間矩陣P0，擬住院時間矩陣V0，醫(yī)保支出矩陣C0可分別表示為：

首先采取多目標粒子群算法對該問題進行求解。根據(jù)問題描述，設(shè)粒子維數(shù)為D=5，粒子數(shù)為M=50，最大迭代次數(shù)為N=200，在速度更新時，學習因子取值為c1=c2=0.8，慣性因子取值范圍為最大值ωmax=1.2，最小值ωmin=0.1，每次迭代時，慣性因子的計算公式為ω=(ωmax-ωmin)×n/N，其中n表示當前迭代次數(shù)，根據(jù)以上設(shè)置參數(shù)進行求解，結(jié)果如下：

表2 多目標粒子群算法求解的病床安排方案

注：每一方案中，P0、V0、X0的列數(shù)分別對應(yīng)五類疾病，每一類下選取1-4對應(yīng)P0、V0、X0行數(shù)。

從表2可以看出，通過多目標粒子群算法求解，共得出20種醫(yī)院床位安排方案，每種方案對應(yīng)的病人已等待天數(shù)、擬住院時間如圖2所示。

圖2 非劣解集住院時間、等待時間的空間分布情況

根據(jù)圖2可以看出，利用多目標粒子群算法能夠得到多種病床安排方案，多種病床安排方案的非劣解集內(nèi)所有點之間，一些在等待時間上占優(yōu)勢，一些在住院時間上占優(yōu)勢，決策者可以綜合考慮各種情況，根據(jù)實際需求來進行選擇。

針對同一問題，選取文獻[6]中的加權(quán)法進行求解，設(shè)置目標函數(shù)為：

圖3 加權(quán)法求取結(jié)果與多目標粒子群求取結(jié)果的比較

5 結(jié) 論

通過比較可知，利用多目標粒子群算法能夠給出所有滿足約束條件的病床安排方案的非劣解集，而運用加權(quán)法，需要不斷重新調(diào)整權(quán)值進行運算，其不同權(quán)值下的解只是多目標粒子群算法中非劣解集的一個特例。因此，通過實例分析可以得出，采取多目標粒子群算法，能夠更方便決策者綜合考慮各種情況來進行決策，該算法更加有針對性，在實際應(yīng)用中具有一定的參考價值。