基于粒子群算法高?？荚噧?yōu)化安排的模型建立與算法設(shè)計(jì)

◆徐 述

（湖南城市學(xué)院信息科學(xué)與工程學(xué)院 湖南 413000）

基于粒子群算法高?？荚噧?yōu)化安排的模型建立與算法設(shè)計(jì)

◆徐 述

（湖南城市學(xué)院信息科學(xué)與工程學(xué)院 湖南 413000）

本文根據(jù)高?？荚嚢才艈?wèn)題的約束條件，對(duì)高?？荚噧?yōu)化安排進(jìn)行了研究，用任務(wù)表示某門(mén)課程針對(duì)某個(gè)班級(jí)的監(jiān)考，高?？荚噧?yōu)化安排問(wèn)題被描述為針對(duì)教師、教室、時(shí)間、課程與班級(jí)的五個(gè)子服務(wù)，帶約束的服務(wù)組合問(wèn)題，以最小化任務(wù)滯后時(shí)間與任務(wù)制造期為優(yōu)化目標(biāo)。并結(jié)合問(wèn)題特性，建立了考試優(yōu)化安排的多目標(biāo)優(yōu)化運(yùn)籌模型，然后設(shè)計(jì)了求解該問(wèn)題的粒子群算法。

考試優(yōu)化；多目標(biāo)優(yōu)化；運(yùn)籌模型；粒子群算法

0 引言

高?？荚嚢才攀且豁?xiàng)各類(lèi)教學(xué)資源沖突的調(diào)度工作，利用教學(xué)資源，安排考試任務(wù)，對(duì)維持教學(xué)秩序，提高教務(wù)管理水平有著積極意義。目前，國(guó)內(nèi)外學(xué)者對(duì)考試優(yōu)化調(diào)度問(wèn)題的相關(guān)研究甚少。本文以高?？荚噧?yōu)化安排為研究對(duì)象，構(gòu)造基于粒子群算法的優(yōu)化模型與算法。

1 問(wèn)題描述

考試安排問(wèn)題是時(shí)空與人力資源互為制約的優(yōu)化決策問(wèn)題。涉及班級(jí)、課程、教室等教學(xué)資源基本因素。這種調(diào)度必須滿(mǎn)足一定的約束條件，例如，考試班級(jí)學(xué)生人數(shù)與教室容量要相匹配，同一課程相關(guān)班級(jí)的考試時(shí)間應(yīng)該相同等等。

本文的目標(biāo)是集中時(shí)間利用教室組考，提高高?？荚嚬芾硇省?/p>

1.1 考試安排問(wèn)題參數(shù)描述

設(shè)F代表監(jiān)考教師，i為教師總數(shù)。教師記為Fz，將其依次編號(hào)為F1…Fi，某教師Fz∈[F1..Fi]。

設(shè)C代表課程，j為課程總數(shù)。課程記為Cx，依次編號(hào)為C1…Cj，某課程Cx∈[C1..Cj]。

設(shè)N代表班級(jí)，k為班級(jí)總數(shù)。班級(jí)記為Ny，依次編號(hào)為N1…Nk，某班級(jí)Ny∈[N1..Nk]。

班級(jí)號(hào)為k的班Ny開(kāi)設(shè)了Cx課程，對(duì)應(yīng)一個(gè)任務(wù)S（即具體一堂考試），n為任務(wù)總數(shù)。將任務(wù)依次編號(hào)為S1…Sn。某任務(wù)Sw∈[S1..Sn]。

設(shè)R代表教室，e為教室總數(shù)。教室記為Rv，將其依次編號(hào)為R1…Re。某教室Rv∈[R1..Re]。

設(shè)Time代表時(shí)間。對(duì)于考試，分為上午、下午、晚上三個(gè)時(shí)間段，依次編號(hào)為0-1，1-2，2-3。tw表示任務(wù)Sw開(kāi)始的時(shí)刻，tw∈[0，1，2]。

Tw表示任務(wù)Sw滯后期，若某考試任務(wù)安排在2-3時(shí)間段，則該任務(wù)定義為滯后，該任務(wù)所耗時(shí)間為滯后時(shí)間。Tw∈[0，1]。 Fw表示任務(wù)Sw實(shí)際完成時(shí)間。表示教室Rv最后一項(xiàng)任務(wù)完成時(shí)間。∈[1，2，3]；Fmax表示制造期，即最后一堂考試離開(kāi)的時(shí)間；Pw為監(jiān)考任務(wù)持續(xù)的時(shí)間。

1.2 考試安排問(wèn)題約束條件

條件1，同一個(gè)時(shí)間段，某位監(jiān)考教師只能在一個(gè)教室監(jiān)考。

條件2，同一個(gè)時(shí)間段，某個(gè)班級(jí)只能在一個(gè)教室里完成考試。

條件3，選修同一門(mén)課程的所有班級(jí)，在同一時(shí)間段完成考試。

條件4，為不影響學(xué)生的學(xué)習(xí)效率與休息，課程考試盡量不安排在晚上。

1.3 考試安排問(wèn)題描述

考試安排調(diào)度問(wèn)題可用三元組α/β/γ來(lái)描述，表述如下：

（1）考試資源環(huán)境（α域）

教室容量為e?？荚囜槍?duì)行政班級(jí)，所以每個(gè)教室都有能力完成任務(wù)。

（2）任務(wù)特征與約束（β域）

設(shè)監(jiān)考任務(wù)Sw的預(yù)期完成時(shí)間fw（期望值）。理想狀態(tài)是所有任務(wù)都能在白天完成，故fw=2。

監(jiān)考任務(wù)Sw作業(yè)時(shí)間實(shí)際為90～120分鐘，即每個(gè)時(shí)間段只能完成一次監(jiān)考任務(wù)，將其視為單位時(shí)間Pw=1。

（3）調(diào)度目標(biāo)（γ域）

0-1（上午）時(shí)間段監(jiān)考第一堂考試，依此類(lèi)推。若2-3（晚上）時(shí)間段有監(jiān)考，則定義該監(jiān)考任務(wù)為滯后，Tw= max（Fw-fw，0）= max（Fw-2，0），Tw∈{1，0}。

制造期Cmax是最后一項(xiàng)任務(wù)離開(kāi)系統(tǒng)的時(shí)間。用下列公式表示：最小化制造期Cmax可以讓學(xué)生有整塊的空余時(shí)間支配。

2 粒子群算法

2.1 粒子群算法

粒子群優(yōu)化算法[1]（Particle Swarm Optimizer，PSO）由Kennedy和Eberhart提出。其基本思想源于對(duì)人工生命和鳥(niǎo)群捕食行為的研究，是一種種群全局搜索策略，它通過(guò)粒子搜尋自身的個(gè)體最優(yōu)解和粒子群體的全局最優(yōu)解來(lái)完成更新優(yōu)化。

2.2 多目標(biāo)粒子群算法

現(xiàn)實(shí)中經(jīng)常遇到使多個(gè)目標(biāo)在給定區(qū)域上同時(shí)盡可能最佳的優(yōu)化問(wèn)題，也就是多目標(biāo)優(yōu)化問(wèn)題（Multiobjective Optimization Problem，MOP）。粒子群算法在很多情況下，比遺傳算法更有效率，所以研究PSO在多目標(biāo)優(yōu)化問(wèn)題中的應(yīng)用很有意義。已有一些基于PSO算法求解多目標(biāo)優(yōu)化問(wèn)題的算法被提出，如Hu等應(yīng)用了動(dòng)態(tài)鄰近的PSO算法[2]，Parsopoulos等應(yīng)用了權(quán)重聚合的方法來(lái)求解多目標(biāo)優(yōu)化問(wèn)題[3]。

一般情況下，MOP的各個(gè)子任務(wù)是相互沖突的。MOP的解并非唯一，而是存在一組最優(yōu)解集合，集合中的各個(gè)元素稱(chēng)為Pareto最優(yōu)解或非劣最優(yōu)解。PSO算法在處理多MOP時(shí)，主要是解決群體和自身最佳位置對(duì)于群體最佳位置的選擇。PSO算法在處理約束時(shí)，多采用懲罰函數(shù)法。Parsopoulos等人提出利用懲罰函數(shù)作為粒子適值[4]，使得PSO能夠解決多目標(biāo)約束優(yōu)化問(wèn)題。

3 考試安排優(yōu)化調(diào)度模型設(shè)計(jì)

本文的考試安排調(diào)度問(wèn)題可以表述為最小化滯后時(shí)間和制造期為目標(biāo)[5]，具有加工時(shí)間約束的并行同速機(jī)。構(gòu)建模型如下：

式（1）為目標(biāo)函數(shù)，調(diào)度目標(biāo)最小化Fmax和滯后時(shí)間和 wT∑。式（2）為約束條件，表示教師Tz在時(shí)間tw只能在某間教室Rv監(jiān)考；。某班Ny某課程考試Cx在時(shí)間tw只能在某教室由某教師監(jiān)考完成。式（3）保證所有監(jiān)考任務(wù)都有機(jī)會(huì)開(kāi)始。式（4）設(shè)某課程Cx有ax個(gè)班開(kāi)設(shè)了課程，該課程的ax個(gè)班考試在同一時(shí)間完成tw。式（5）所有的課程Cx對(duì)應(yīng)的考試門(mén)數(shù)ax之和等于監(jiān)考任務(wù)n。式（6）給出任務(wù)Sw的滯后時(shí)間與制造期。式（7）給出決策變量d的取值范圍。

4 算法設(shè)計(jì)

4.1 編碼設(shè)計(jì)

根據(jù)本文建立的考試優(yōu)化安排模型，將目標(biāo)函數(shù)問(wèn)題的可分解空間假想為N維搜索空間。用以下二維數(shù)組表示位置向量L和速度向量V。

在位置向量L中，對(duì)應(yīng)每門(mén)課程Cx對(duì)應(yīng)ax個(gè)班級(jí)考試，課程Cx有j門(mén)，所以將位置向量與速度向量分成j個(gè)區(qū)域進(jìn)行優(yōu)化。速度向量V中，其中。此取值范圍只適用于初始速度。

4.2 粒子位置和速度迭代

4.3 多目標(biāo)粒子群考試安排優(yōu)化調(diào)度算法

基于考試安排優(yōu)化調(diào)度，多目標(biāo)粒子群算法表述如下：

①初始化粒子群，種群大小為N，構(gòu)造位置和速度向量（編碼），分派規(guī)則產(chǎn)生初始種群。

②計(jì)算每個(gè)粒子的評(píng)價(jià)函數(shù)值。

③找到每個(gè)粒子所對(duì)應(yīng)的局部最優(yōu)解以及全局最優(yōu)解。④根據(jù)式（8）（9）更新粒子速度和位置。

⑤未達(dá)到迭代次數(shù)轉(zhuǎn)步驟2，達(dá)到迭代次數(shù)結(jié)束。

5 結(jié)束語(yǔ)

本文對(duì)高校考試優(yōu)化安排進(jìn)行了研究，建立起考試優(yōu)化安排的多目標(biāo)優(yōu)化運(yùn)籌模型，設(shè)計(jì)出求解該問(wèn)題的粒子群算法，為下一步算法實(shí)現(xiàn)與算法分析打下基礎(chǔ)。

[1]J．Kennedy，R．Eberhart，Particle swarm optimization [C]．Proc．IEEE Int．Conf．on Neural Networks，Perth，Australia，19 95．

[2]X Hu，R C Eberhart．Multiobjective optimization using dynamic neighborhood particle swarm optimization．IEEE Con gress on Evolutionary Computation（CEC 2002），Honolulu，Hawaii，USA，2002．

[3]K E Parsopoulos，M N Vrahatis，Particle swarm opti mization method in multiobjective problems[J]．In Proc of the ACM Symp on Applied Computing 2002（SAC 2002）．Ne w York ACM Press，2002．

[4]薛洪波，倫淑嫻．粒子群算法在多目標(biāo)優(yōu)化中的應(yīng)用綜述[J]．渤海大學(xué)學(xué)報(bào)（自然科學(xué)版），2009．

[5]曹策俊，楊琴，李從東．求解高校教室調(diào)度問(wèn)題的混合粒子群算法[J]．計(jì)算機(jī)應(yīng)用研究，2012．

[6]楊維，李岐強(qiáng)．粒子群優(yōu)化算法綜述[J]．中國(guó)工程科學(xué)，2004．