基于離散粒子群算法的機房排課問題研究

1、基于離散粒子群算法的機房排課問題研究摘要：粒子群優(yōu)化算法以其實現(xiàn)容易、精度高、收斂快等優(yōu)點引起了學(xué)術(shù)界的重視，并且在解決實際問題中展示了其優(yōu)越性。本文通過改造離散粒子群算法使之適合機房排課問題的求解。從而達到為機房排課問題的解決提供一種新的思路。關(guān)鍵詞：粒子群優(yōu)化算法；離散粒子群算法；機房排課lab course problems study based on discrete particle swarmwang chao(chongqing business vocational college, chongqing 400036,china)abstract: the particle

2、swarm optimization algorithm for its easy implementation, high accuracy, fast convergence advantages attracted the attention of academia, and demonstrated its superiority in solving practical problems. in this paper, the transformation of discrete particle swarm optimization to solving for lab cours

3、e. so as to achieve the solution to the problem for the lab course provides a new way of thinking.keywords: particle swarm optimization algorithm; discrete particle swarm optimization; lab course一、緒論機房排課問題是典型的涉及多種因素的多目標(biāo)組合優(yōu)化問題，需要考慮學(xué)生學(xué)習(xí)效果、照顧教師合理的工作安排、充分利用機房資源等因素，傳統(tǒng)的人工排課方式在資源緊張、約束條件復(fù)雜度增大的情況下，會遇到越來越多的沖突

4、。如果排課的數(shù)據(jù)規(guī)模足夠大，則很可能出現(xiàn)沖突難以解決的狀況。而用計算機排課代替?zhèn)鹘y(tǒng)的手工排課將可以最大限度地利用各種排課資源，解決沖突。計算機排課問題是一個多目標(biāo)組合優(yōu)化問題。國外從20世紀(jì)50年代末開始就對排課問題開展了研究。到目前為止，已知的解決排課問題的方法有：模擬手工排課法，圖論方法，拉格朗日松弛法，二次分配法等多種方法。然而，隨著排課問題的約束條件越來越復(fù)雜，對排課算法的要求也越來越高。粒子群優(yōu)化算法在函數(shù)優(yōu)化、約束優(yōu)化、極大極小問題、多目標(biāo)優(yōu)化等問題中均得到了成功的應(yīng)用。在研究粒子群算法原理的基礎(chǔ)上，本文通過改造離散粒子群算法1,2用于機房排課問題的求解取得了良好的效果。二、機房排

5、課問題的分析（一）機房排課問題中的要素。機房排課問題涉及的要素主要有任課教師、課程、班級、時間、機房五個要素，其中教師、課程和班級三者之間的關(guān)系一般是在排課前就已經(jīng)確定，機房排課問題的解空間實際上就是這五個要素之間的笛卡爾集。1.任課教師要素。每位任課教師在同一時刻只能上一門課程。每位任課教師每天最多安排4節(jié)課。2.課程要素。每門課程會預(yù)先確定開課班級、任課教師，在排課算法中會確定機房和時間。3.班級要素。由于上機課不存在合班上大課的情況，因此每個班級的學(xué)生人數(shù)是固定的。在同一時刻一個班級只能上一門課。4.機房要素。每個機房有固定的容量，機房中計算機的性能的高低及相關(guān)設(shè)備的配備情況決定機房適合

6、上某種類型的課程。分為1，2，3，4類機房，分別適合上計算機應(yīng)用基礎(chǔ)、多媒體課程、設(shè)計類課程、網(wǎng)絡(luò)課程。5.時間要素。時間要素主要考慮一周中的教學(xué)工作日、每天可以安排的教學(xué)時間以及課次之間的時間間隔等。（二）機房排課問題的數(shù)學(xué)描述。機房排課問題實際上就是將任課教師、課程、班級、機房四個要素合理地安排在一周五天工作日的相應(yīng)時間里，目標(biāo)是沒有沖突。因此，在機房排課問題中共有五個相關(guān)要素。下面分別用五個集合來表示如下：任課教師集合：t=t1，t2，tnt；（nt表示任課教師總數(shù)）課程集合：c=c1，c2，cnc；（nc表示課程總數(shù)）班級集合：l=l1，l2，lnl；（nl表示班級總數(shù)）機房集合：ar

7、=ar1，ar2，arna；（na表示機房）上課時間集合：lt=lt1，lt2，ltnl；（nl表示上課時間總數(shù)）由任課教師、課程、班級、機房、上課時間五個要素構(gòu)成的笛卡爾積t×c×l×ar×lt就是機房排課問題的解空間，機房排課問題的求解就是在解空間中找到那些滿足約束條件的解。課程的數(shù)量越多，教學(xué)規(guī)模越大，解空間的規(guī)模也就越大。在上述五個要素中，課程、班級和任課教師的對應(yīng)關(guān)系是在排課前已經(jīng)確定好的。而機房和上課時間是ar×lt完全映射。通過分析機房排課問題的相關(guān)約束條件，可建立適應(yīng)度函數(shù)如公式2.1所示：xx（2.1）式（2.1）中x為問題的

8、一個可行解，x為所有可行解組成的集合；1、2、3分別表示適應(yīng)度函數(shù)f1、 f2 、f3的權(quán)值（其中1+2+3=1）。f1是所排課程分散度的適應(yīng)度函數(shù)；f2是所排課程時間安排合理性的適應(yīng)度函數(shù)；f3是機房安排合理性的適應(yīng)度函數(shù)。（三）機房排課問題的多目標(biāo)分析。機房排課的目的是將任課教師、學(xué)生、相應(yīng)的課程在時間和機房選擇上根據(jù)不同的約束條件進行合理的安排。使所有課程安排都達到比較合理的狀態(tài)。得到較為合理的課表，即找到排課問題的最優(yōu)解。1.機房排課問題的約束條件。機房排課問題的約束條件分為必須滿足的硬約束條件和應(yīng)盡量滿足的軟約束條件。也就是說，滿足硬約束條件的就是機房排課問題的可行解，而既滿足硬約束

9、條件又滿足軟約束條件的就是機房排課問題的最優(yōu)解。硬約束：（1）同一個老師在同一時間只能上一門課；（2）同一個班級在同一時間只能參加一門課的學(xué)習(xí)；（3）一個機房在同一時間只能安排一門課程的上機教學(xué)；（4）機房的容量必須滿足上課學(xué)生人數(shù)；（5）機房數(shù)量要大于同一時間安排的上機課程總數(shù)；（6）部分課程必須安排在能滿足該課程上機用軟件所需計算機性能的計算機所在的機房。軟約束（1）同一門課程的上機課時間應(yīng)盡量安排在該課程理論課上課時間之后（本周內(nèi)）；（2）上機課應(yīng)盡量安排在下午或上午3，4節(jié)；（3）盡可能滿足個別教師的特殊上課時間要求；（4）同一個班級的同一門上機課在一周之內(nèi)應(yīng)間隔排列；（5）課程盡量安

10、排在與之對應(yīng)類型的機房上課，如果機房資源不夠，在機房能基本滿足教學(xué)實訓(xùn)的前提下，可退而求其次，選擇其它類型的機房。滿足上述中的硬約束條件的映射就是機房排課問題的解。而在此基礎(chǔ)上盡量滿足軟約束條件就是獲得一個科學(xué)、合理的排課結(jié)果必須考慮的問題。2.機房排課問題的優(yōu)化。機房排課問題的優(yōu)化目標(biāo)就是怎樣在滿足基本的硬約束條件，獲得可行解的前提下，通過滿足盡量多的軟約束，以獲得較優(yōu)解?，F(xiàn)將機房排課問題涉及到的軟約束指標(biāo)歸納如下：（1）時間安排合理性。課程安排時間為3，4/5，6、7，8、1，2、9，10節(jié)的，對應(yīng)時間安排合理性1取值為6，4，2，1；與理論課時間相隔的天數(shù)為1/無理論課時、2、3/0、&

11、gt;=4/<=-4、-3、-2、-1的，對應(yīng)時間安排合理性取值2分別為10、8、6、5、3、2、1。其中，1，2分別表示時間安排合理性指標(biāo)1，2的權(quán)值，兩者的和應(yīng)該等于1； 分別表示課表上每門課程的時間安排合理性指標(biāo)1，2的值；n表示所有的課程數(shù)量；kmax表示時間安排合理性指標(biāo)1，2的最大值。（2.2）（2）機房安排的合理性。機房多余的座位數(shù)分別為5座以內(nèi)、5-10座、10座以上的，對應(yīng)機房利用率1取值分別為5、3、1；機房使用頻率為30節(jié)次以上/周、20-30節(jié)次/周、20節(jié)次以下/周的，對應(yīng)機房利用率2取值分別為5、3、1；課程所排機房情況為適合、基本適合的，則課程與所安排機房的

12、適合度為5、3。（2.3）在公式（2.3）其中，1，2，3分別表示機房的利用率1，2，課程與所安排機房的適合度的權(quán)值，三者的和應(yīng)該等于1； 分別表示課表上每門課程的機房的利用率1，2，課程與所安排機房的適合度的值；n表示所有的課程數(shù)量； 表示時間安排合理性指標(biāo)1，2的最大值。三、求解機房排課問題的粒子群算法設(shè)計（一）粒子群優(yōu)化算法求解機房排課問題的編碼設(shè)計根據(jù)排課問題的特征，排課算法的調(diào)度方案的編碼方式有矩陣表示法1、三維編碼、布爾矩陣編碼三種。求解機房非課問題需要根據(jù)所選擇的算法及軟件開發(fā)技術(shù)來選擇合適的編碼方式。由于矩陣表示法的特點適合用數(shù)據(jù)庫來表示，因此，本文在矩陣表示法的基礎(chǔ)上根據(jù)所研

13、究問題的特點確定了所用的編碼方式：設(shè)有二維矩陣xk，l，其中k表示在課表編排過程中可以用來作為機房上課的時間的數(shù)量，l表示可以用于上機課使用的機房數(shù)量。矩陣中的每個元素都由課程、任課教師、上課班級三部分組成。在機房排課問題的實現(xiàn)算法中，這個二維矩陣將與關(guān)系數(shù)據(jù)庫中的一張數(shù)據(jù)表對應(yīng)（行表示可供排課使用的機房，列表示可以排課的時間）。同時，每一張數(shù)據(jù)表表示粒子中群中的一個個體。對粒子的初始化就是對數(shù)據(jù)表的初始化。（二）求解機房排課問題的算法設(shè)計1.初始化種群。粒子群作為機房排課問題的解空間，一個可行解就與群中一個粒子相對應(yīng)，因此種群的初始化就是構(gòu)造機房排課問題的初始解空間。因為種群初始化在機房排課

14、問題中就是形成一定數(shù)量的問題可行解，所以在初始化過程中，應(yīng)盡量做到在隨機排課時，不存在任何沖突的前提下，如果一門課程每周上課次數(shù)超過兩次，則兩次課上課時間的間隔一天是最好選擇，其次是兩天、三天。同時也應(yīng)盡量滿足多次上同一門課程要安排在同一個機房。從而完成一個粒子的初始化。然后重復(fù)以上過程以構(gòu)造出指定數(shù)量的粒子，從而完成種群的初始化過程。2.適應(yīng)度函數(shù)。適應(yīng)度函數(shù)的建立是在充分考慮機房排課問題是多目標(biāo)組合優(yōu)化問題的基礎(chǔ)上，根據(jù)4.2.1中提到的要求確定下來的，如下式：xx（3.1）式（3.1）中x為問題的一個可行解，x為所有可行解組成的集合；1、2、3分別表示適應(yīng)度函數(shù)f1、 f2 、f3的權(quán)值

15、（其中1+2+3=1）。f1是所排課程分散度的適應(yīng)度函數(shù)；f2是所排課程時間安排合理性的適應(yīng)度函數(shù)；f3是機房安排合理性的適應(yīng)度函數(shù)。3.粒子位置更新操作。本文對為解決機房排課問題所采用的粒子群算法中粒子位置更新公式進行修改以適應(yīng)本文所研究的問題。如公式（3.2）、（3.3）所示：（3.2）(3.3）在上述公式中，利用遺傳算法的交叉操作改造了粒子位置的更新公式，在滿足條件的前提下將待更新粒子的當(dāng)前位置與該粒子的歷史最好位置、粒子群全局最好位置進行交叉操作，再引入遺傳算法的變異思想對該粒子按公式（3.3）進行局部交換，從而完成了粒子位置的更新。在更新時，本文選擇將待更新粒子與其歷史最優(yōu)位置及全局

16、最優(yōu)位置的粒子對應(yīng)的二維表的列進行交叉操作，即在操持機房不變的情況下，改變上課的時間。在上述操作過程中，若遇到的沖突，將按算法的規(guī)則進行調(diào)整，使之符合可行解的要求。即如果遇到的沖突能通過調(diào)整解決，則交換，否則放棄交換操作。4.算法流程。根據(jù)上文的分析，總結(jié)求解機房排課問題的離散粒子群算法如下所示：對粒子數(shù)量m進行初始化，概率c1，和c2，給計數(shù)器n賦初值0；采用隨機方式產(chǎn)生各初始粒子的位置，并計算各初始粒子的適應(yīng)度值；令各粒子群中各粒子的當(dāng)前最好位置 等于各粒子的當(dāng)前位置 ，令粒子群當(dāng)前全局最優(yōu)粒子的位置為gn；判斷算法的收斂條件是否滿足，如滿足，則由gn得到最優(yōu)解，即最終課表，算法結(jié)束；否則跳轉(zhuǎn)到步驟對粒子群中所有粒子進行如下操作：1)按公式（3.2）和公式（3.3）更新粒子位置；2)計算新生成的粒子的適應(yīng)度值；3)如果粒子適應(yīng)度值優(yōu)于 ，令 = ；4)如果粒子適應(yīng)度值優(yōu)于gn，令gn= ；n=n+1，轉(zhuǎn)向。四、結(jié)束語本文對機房排課問題進行了比較深入的探討，在此基礎(chǔ)上給出了一個基于粒子群思想的機房排課