基于Pareto多目標(biāo)遺傳算法的排課算法

摘 要：中小學(xué)課表編排要考慮時(shí)間、空間和人員安排問題等多個(gè)目標(biāo)的同時(shí)優(yōu)化問題。傳統(tǒng)方法是將多目標(biāo)優(yōu)化問題的多個(gè)目標(biāo)函數(shù)通過適當(dāng)方法（如加權(quán)法等）轉(zhuǎn)化為單目標(biāo)優(yōu)化問題進(jìn)行處理。該方法的缺點(diǎn)需要對(duì)優(yōu)化問題掌握一定的先驗(yàn)知識(shí)，否則難以確定加權(quán)系數(shù)。針對(duì)傳統(tǒng)多目標(biāo)算法需要對(duì)目標(biāo)掌握先驗(yàn)知識(shí)的缺點(diǎn)，本文提出一種基于Pareto多目標(biāo)遺傳算法的排課算法，并實(shí)驗(yàn)證明該方法的有效性。

關(guān)鍵詞：遺傳算法 Pareto 多目標(biāo) 排課

中圖分類號(hào)：TP311.13文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

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

針對(duì)上述問題，本文采用Pareto多目標(biāo)遺傳算法來進(jìn)行優(yōu)化計(jì)算。該方法無需對(duì)優(yōu)化的各個(gè)目標(biāo)掌握先驗(yàn)知識(shí)，并具有極強(qiáng)的魯棒性、全局尋優(yōu)能力和隱含的并行性等特點(diǎn)，使得該方法成為多目標(biāo)優(yōu)化方法中的一個(gè)研究熱點(diǎn)。

1 排課系統(tǒng)設(shè)計(jì)

課表的安排除了要考慮教學(xué)計(jì)劃、教師資源以及教室使用情況，同時(shí)還要以其他教學(xué)要求來評(píng)判課程安排的優(yōu)劣，如：

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

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

（3）對(duì)于一周多節(jié)的課程要盡量保證同一門課程兩節(jié)之間時(shí)間間隔較長(zhǎng)。

本文設(shè)定一個(gè)班級(jí)一天排6節(jié)課，上午排4節(jié)課，下午排2節(jié)課，即一周有30節(jié)課，因此每一節(jié)上課時(shí)間的變量在整數(shù)區(qū)間（1-30）上取值。量化排課優(yōu)劣程度的方法如下描述：

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

（1）

由式（1）可以看出，當(dāng)f1（X）的值越小時(shí)，課程就越集中在上午。

（2）對(duì)于使課程安排均勻，我們統(tǒng)計(jì)一周每天安排的課程數(shù)目，并求這5天課程數(shù)目的方差f2（X）。那么，方差f2（X）越小則排課越均勻。

（3）對(duì)于每周要安排多節(jié)的課程，要使同一門課程兩節(jié)之間間隔的時(shí)間盡可能長(zhǎng)，我們計(jì)算同一門課（每周需要安排多節(jié)的課程）兩次值的相差絕對(duì)值。那么，一周內(nèi)所有課的相差絕對(duì)值之和f3（X）越大，則課程安排越合理。

2 多目標(biāo)遺傳算法優(yōu)化

傳統(tǒng)多目標(biāo)優(yōu)化方法是將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題。如線性加權(quán)法，將上述三個(gè)目標(biāo)函數(shù)f1（X），f2（X），f3（X）按其重要程度給出一組權(quán)系數(shù)w1，w2，w3，則評(píng)價(jià)函數(shù)的最優(yōu)解如式（2）所示：

（2）

但該方法要求對(duì)優(yōu)化問題掌握先驗(yàn)知識(shí)時(shí)。而本文采用Pareto多目標(biāo)遺傳算法來進(jìn)行優(yōu)化計(jì)算。無需掌握先驗(yàn)知識(shí)，

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

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

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

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

輸入：函數(shù)h（X）；權(quán)系數(shù)w1，w2，w3；初始群體

Step 1：設(shè)小生境距離；

Step 2：在每類部分群體中選Pareto占優(yōu)個(gè)體；

Step 3：交叉；

Step 4：變異；

Step 5：生成下一代群體；

Step 6：檢查評(píng)價(jià)優(yōu)化結(jié)果是否收斂。如沒有，

返回步驟（2）；如已收斂，執(zhí)行-結(jié)束。

輸出：優(yōu)化結(jié)果（即最后一代群體）

相比較以往傳統(tǒng)遺傳算法，本文算法改進(jìn)措施如下：

（1）根據(jù)種群中占優(yōu)的個(gè)數(shù)多少來賦予個(gè)體相應(yīng)適應(yīng)度。

（2）在每代中采用部分種群來決定占優(yōu)的情況。而且，當(dāng)兩個(gè)個(gè)體之間彼此互不占優(yōu)的時(shí)候，其結(jié)果通過適應(yīng)度共享來決定。由于本文沒有在整個(gè)種群中使用Pareto意義選種，而是在每代中只采用部分種群，因此其能快速并產(chǎn)生較好的Pareto意義占優(yōu)解。

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

3 實(shí)驗(yàn)結(jié)果及分析

假設(shè)需為某班排課，共6門課程，英語、語文、數(shù)學(xué)等。其中英語、語文、數(shù)學(xué)每周需要安排6節(jié)，其他課程每周安排2節(jié)。

我們首先通過隨機(jī)方法生成30次排課解作為初始群體，以上述f1（X），f2（X），f3（X）的極值作為優(yōu)化目標(biāo)。根據(jù)遺傳算法進(jìn)行優(yōu)化計(jì)算，設(shè)突變率為1%，經(jīng)過100代進(jìn)化，結(jié)果如表1所示：

表1 Pareto多目標(biāo)遺傳算法優(yōu)化結(jié)果

初始群體100代群體

均值標(biāo)準(zhǔn)差均值標(biāo)準(zhǔn)差

f1（X）10.131.297.620.22

f2（X）1.340.031.110.01

f3（X）132.2415.21168.121.25

由表1可以看出，盡管實(shí)驗(yàn)沒有提供對(duì)優(yōu)化目標(biāo)的先驗(yàn)知識(shí)，但通過Pareto遺傳算法優(yōu)化后，3個(gè)優(yōu)化目標(biāo)f1（X），f2（X），f3（X）都得到同時(shí)優(yōu)化，并且優(yōu)化結(jié)果比較理想。

4 結(jié)束語

該文針對(duì)傳統(tǒng)多目標(biāo)優(yōu)化排課算法需要先驗(yàn)知識(shí)的缺點(diǎn)，將Pareto多目標(biāo)遺傳算法應(yīng)用到排課系統(tǒng)中，并實(shí)驗(yàn)證明該方法的有效性。

參 考 文 獻(xiàn)

[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]陸金桂等. 遺傳算法原理及其工程應(yīng)用[M]， 江蘇徐州：中國(guó)礦業(yè)大學(xué)出版社， 1997：40-52.

[4]喬佩利，鄭林，馬麗麗. 一種小生境遺傳算法研究[J]， 哈爾濱理工大學(xué)學(xué)報(bào)， 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.