基于Pareto多目標遺傳算法的排課算法

摘 要：中小學課表編排要考慮時間、空間和人員安排問題等多個目標的同時優化問題。傳統方法是將多目標優化問題的多個目標函數通過適當方法（如加權法等）轉化為單目標優化問題進行處理。該方法的缺點需要對優化問題掌握一定的先驗知識，否則難以確定加權系數。針對傳統多目標算法需要對目標掌握先驗知識的缺點，本文提出一種基于Pareto多目標遺傳算法的排課算法，并實驗證明該方法的有效性。

關鍵詞：遺傳算法 Pareto 多目標 排課

中圖分類號：TP311.13文獻標識碼：A 文章編號：1672-3791（2015）01（a）-0000-00

Curriculum Scheduling Algorithm based on Pareto Multi Object Genetic Algorithm

HE Yi-xuan

Class 12 Grade Three， Haizhou Senior High School of Jiangsu Province， Lianyungang 222023， China

Abstract： Curriculum scheduling for primary school and high school should not only to resolve the arrangement of time， room and personnel， but should also to optimize some other factors， and these factors need optimized simultaneously. For the weak point that traditional multi objective optimization algorithm should have priori knowledge before optimization， we propose a curriculum scheduling algorithm based on Pareto multi object genetic algorithm. Finally， an experiment is given to verify our algorithm.

KeyWord： genetic algorithm； multi object； Pareto； curriculum scheduling

課表編排系統的設計是整個教務管理信息系統的設計難點。除了要解決時間、空間、人員的安排問題，排課需要考慮的因素和指標還比較多，如課程安排的均勻程度、重要課程盡量安排在上午等。這些指標往往需要同時優化，即多目標優化問題[1-2]。由于往往多個目標不能同時最優，對各個目標的偏好不同，得到的優化解也不同。傳統方法是將多目標優化問題的多個目標函數通過適當方法（如加權法等）轉化為單目標優化問題進行處理。該方法的缺點需要對優化問題掌握一定的先驗知識，否則難以確定加權系數。

針對上述問題，本文采用Pareto多目標遺傳算法來進行優化計算。該方法無需對優化的各個目標掌握先驗知識，并具有極強的魯棒性、全局尋優能力和隱含的并行性等特點，使得該方法成為多目標優化方法中的一個研究熱點。

1 排課系統設計

課表的安排除了要考慮教學計劃、教師資源以及教室使用情況，同時還要以其他教學要求來評判課程安排的優劣，如：

（1）課程分布均勻，避免課程都集中在某一兩天的情況；

（2）重要課程盡量安排在上午；

（3）對于一周多節的課程要盡量保證同一門課程兩節之間時間間隔較長。

本文設定一個班級一天排6節課，上午排4節課，下午排2節課，即一周有30節課，因此每一節上課時間的變量在整數區間（1-30）上取值。量化排課優劣程度的方法如下描述：

（1）為了使重要課程盡量安排在上午，首先將每一節課的值進行修正：一周有n節課時，按先后順序記課的值分別為1，2，…，n。其中，式中，若該節無課，則當前值設為0。假設排課結果為x1，x2，…，xn，評價函數f1（X）如式（1）所示：

（1）

由式（1）可以看出，當f1（X）的值越小時，課程就越集中在上午。

（2）對于使課程安排均勻，我們統計一周每天安排的課程數目，并求這5天課程數目的方差f2（X）。那么，方差f2（X）越小則排課越均勻。

（3）對于每周要安排多節的課程，要使同一門課程兩節之間間隔的時間盡可能長，我們計算同一門課（每周需要安排多節的課程）兩次值的相差絕對值。那么，一周內所有課的相差絕對值之和f3（X）越大，則課程安排越合理。

2 多目標遺傳算法優化

傳統多目標優化方法是將多目標優化問題轉化為單目標優化問題。如線性加權法，將上述三個目標函數f1（X），f2（X），f3（X）按其重要程度給出一組權系數w1，w2，w3，則評價函數的最優解如式（2）所示：

（2）

但該方法要求對優化問題掌握先驗知識時。而本文采用Pareto多目標遺傳算法來進行優化計算。無需掌握先驗知識，

Pareto占優定義如下：假設x1，x2∈某一可行域Ω，x1被x2占優是指對部分i，有fi（X）≥fj（X），而對其他的j≠i，fi（X）> fj（X）。Pareto最優解x0是指在Ω中不存在任何x占優于x0。

從定義中可知，Pareto最優解不是唯一的，而是由許多“非劣解”（非劣解，是指在不降低其它性能指標的前提下，再也不能提高該性能指標）組成的解集，因此群體搜索策略（如遺傳算法）是非常合適的求解方法。

遺傳算法是通過對一代群體按照尋優目標進行一系列的選種、交叉、變異而使下一代群體從整體上更接近最優解[3]。本文將選擇算子中引入Pareto占優概念，即Pareto遺傳算法。

本文Pareto遺傳算法操作流程如下：

輸入：函數h（X）；權系數w1，w2，w3；初始群體

Step 1：設小生境距離；

Step 2：在每類部分群體中選Pareto占優個體；

Step 3：交叉；

Step 4：變異；

Step 5：生成下一代群體；

Step 6：檢查評價優化結果是否收斂。如沒有，

返回步驟（2）；如已收斂，執行-結束。

輸出：優化結果（即最后一代群體）

相比較以往傳統遺傳算法，本文算法改進措施如下：

（1）根據種群中占優的個數多少來賦予個體相應適應度。

（2）在每代中采用部分種群來決定占優的情況。而且，當兩個個體之間彼此互不占優的時候，其結果通過適應度共享來決定。由于本文沒有在整個種群中使用Pareto意義選種，而是在每代中只采用部分種群，因此其能快速并產生較好的Pareto意義占優解。

（3）相比較傳統遺傳算法，本文算法還引入小生境技術[4-5]。該技術可以防止基因漂移，使群體均勻分布在Pareto最優解集中。由于一周有5天課程，本文將個體劃分為5類，即從這5個類當中選出適應度較大的個體作為該類的代表組群。

3 實驗結果及分析

假設需為某班排課，共6門課程，英語、語文、數學等。其中英語、語文、數學每周需要安排6節，其他課程每周安排2節。

我們首先通過隨機方法生成30次排課解作為初始群體，以上述f1（X），f2（X），f3（X）的極值作為優化目標。根據遺傳算法進行優化計算，設突變率為1%，經過100代進化，結果如表1所示：

表1 Pareto多目標遺傳算法優化結果

初始群體100代群體

均值標準差均值標準差

f1（X）10.131.297.620.22

f2（X）1.340.031.110.01

f3（X）132.2415.21168.121.25

由表1可以看出，盡管實驗沒有提供對優化目標的先驗知識，但通過Pareto遺傳算法優化后，3個優化目標f1（X），f2（X），f3（X）都得到同時優化，并且優化結果比較理想。

4 結束語

該文針對傳統多目標優化排課算法需要先驗知識的缺點，將Pareto多目標遺傳算法應用到排課系統中，并實驗證明該方法的有效性。

參 考 文 獻

[1]Tan K C， Lee T H， Khoo D， and et al. A multi-objective evolutionary algorithm toolbox for computer-aided multi-objective optimization[J]， IEEE Transactions on Systems， Man and Cybernetics： Part B （Cybernetics）， 2001， 31（4）：537-556.

[2]Vieira D A G， Adriano R， Vasconcelos J A， and et al. Treating constraints as objectives in multiobjective optimization problems using niched Pareto genetic algorithm[J]， IEEE Transactions on Magnetics， 2004， 40（2）： 1188-1191.

[3]陸金桂等. 遺傳算法原理及其工程應用[M]， 江蘇徐州：中國礦業大學出版社， 1997：40-52.

[4]喬佩利，鄭林，馬麗麗. 一種小生境遺傳算法研究[J]， 哈爾濱理工大學學報， 2011， 16（1）：90-93.

[5]Liao G C. Integrated Isolation Niche and Immune Genetic Algorithm for solving Bid-Based Dynamic Economic Dispatch Original Research Article[J]， International Journal of Electrical Power Energy Systems， 2012， 42（1）：264-275.