基于粒子群算法的中職學校排課問題研究

摘 要：中職學校的教學過程中，“排課”占有非常重要的地位，關(guān)系到整個教學安排合理化的實施。目前中職學校在排課時常以“粒子群算法”為基礎(chǔ)，建立數(shù)據(jù)體系模型，采用電腦自動排課的方式進行。本文嘗試以基于粒子群算法的中職學校排課問題來進行研究，全面、深入的挖掘與分析粒子群算法在排課系統(tǒng)中的科學、有效運用，以便在以后的排課系統(tǒng)設(shè)計中能夠為其他學校提供借鑒經(jīng)驗。

關(guān)鍵詞：粒子群算法；中職學校；排課；適應(yīng)性函數(shù)

在我國中等職業(yè)學校的教學中，排課是專業(yè)課程教學管理體系中的一項十分重要的教學管理工作，其具體的形式與內(nèi)容都是非常復(fù)雜的，一個科學、有效的排課設(shè)計系統(tǒng)往往會極大的促進學校教育事業(yè)的發(fā)展與教學水平的提升。我們從中職學校的排課問題中能夠看出一個帶有約束性質(zhì)的優(yōu)化問題，而其中所說的約束條件就是指，所排出的課程安排不存在教師、教室、時間上的沖突，這是粒子群算法對其進行優(yōu)化的前提條件，以便最大限度的使教師、教室、時間等資源消耗最小化，從而幫助職業(yè)學校取得最大合理化的排課效果。

1 “排課問題”與“粒子群算法”

1.1 排課問題

所謂“排課”，就是指教學課程的安排，具體意思就是說，學校為了能夠正常的進行教學工作，然后對各年級、各教室、各教師以及教學課程等一系列的教學資源進行科學、合理的安排與優(yōu)化，從而制定出學校教學使用的課程表。

排課問題是指科學、有效解決在教學時間、教學空間上資源矛盾的多因素優(yōu)化決策的一個問題，主要的元素包括教室、教師、課程、班級等，有效的排課就是讓這些基本因素之間在一定時間、地點內(nèi)不發(fā)生任何的沖突、矛盾。（表1）

1.2 粒子群算法

粒子群算法——Particle Swarm Optimization ，也被稱作為粒子群優(yōu)化算法，簡稱——PSO。粒子群優(yōu)化算法是一種與遺傳算法非常相似的科學算法，但是從它的計算內(nèi)容及形式上來看，PSO這種算法則突顯的更為簡單、實效。

2 中職學校排課問題的粒子群優(yōu)化算法

2.1 粒子的編碼

在粒子群優(yōu)化算法中，我們應(yīng)該對于每一個需要優(yōu)化的問題進行全面的挖掘、分析，通過想象把一些潛在的問題解決方案通過D維搜索空間，將其看做成一個空間“點”，也就是我們所說的“粒子”。在某中職學校的排課中，對于每一個粒子元素，我們都可以將其設(shè)定為一個元素集，T代表時間、M代表教師、C代表課程、R代表班級、I代表地點，這也是在中職、高等學校排課中比較常用的五元組優(yōu)化算法體系。

下面我們通過一個模型來表現(xiàn)“粒子編碼”的操作概念：

圖1 粒子編碼模型圖

2.2 適應(yīng)性函數(shù)

Fit=

該公式中，m1、m2、m3、w1、w2、w3分別代表權(quán)值，也就是說權(quán)值的大小代表著各種約束條件的重要程度，圖1中所表示的粒子元素，在函數(shù)中表示的則是一種可能的排課結(jié)果，具體的排課結(jié)果的優(yōu)劣好壞是由適應(yīng)性函數(shù)來決定的。

2.3 種群的初始化

在對中職學校進行排課結(jié)果研究計算過程中，粒子群優(yōu)化算法中的種群初始化，也就是指初始化的粒子群，通俗點講就是指元素集，就像在第一部分所提到的元素集一樣，T代表時間、M代表教師、C代表課程、R代表班級、I代表地點。在粒子群初始化的狀態(tài)下，所有粒子元素都是隨機進行排列的，目的就是為了后面所進行的進化操作提供初始粒子群。

2.4 基于粒子群的排課算法設(shè)計

通過粒子編碼與適應(yīng)性函數(shù)在中職學校排課問題中的應(yīng)用，制定出PSO基本算法的流程示意圖，詳見圖2。

下面就以某中職學校的計算機信息工程專業(yè)的課程任務(wù)分配工作問題來進行排課，通過運用粒子群優(yōu)化算法，并將粒子群優(yōu)化算法與傳統(tǒng)的遺傳算法來進行對比，通過排課結(jié)果來體現(xiàn)出粒子群優(yōu)化算法的科學性、準確性、實效性。

通過表3所計算出來的結(jié)果顯示，基于粒子群優(yōu)化算法下的中職學校排課結(jié)果的性能要優(yōu)于傳統(tǒng)的遺傳算法的性能，非常有效的實現(xiàn)了學校在排課過程中避免了各種時間、空間上教育資源的沖突與浪費。

3 總結(jié)

本文主要介紹了利用粒子群優(yōu)化算法來求解中職學校排課問題的具體方案，經(jīng)過對算法結(jié)果的分析與驗證，已經(jīng)證明了PSO這種算法在實際應(yīng)用中是非常有效果的。應(yīng)用粒子群的編碼方案以及適應(yīng)性函數(shù)，能夠很好地解決中職學校排課問題，并有效的保證了中職學校排課結(jié)果的正確性、實效性、科學性，對學校排課的合理化和整體教學管理水平的提高有極大的幫助，有效地促進了教學質(zhì)量的提高。

參考文獻：

[1]陳華.基于粒子群算法的高校排課系統(tǒng)設(shè)計與實現(xiàn)[D].揚州大學，2009.

[2]王超.基于離散粒子群算法的機房排課問題研究[J].計算機光盤軟件與應(yīng)用，2012（3）：206-207.

[3]張立巖，張世民，秦敏，等.基于改進粒子群算法排課問題研究[J].河北科技大學學報，2011，32（3）：265-268.

作者簡介：

李偉明，1982年生，本科畢業(yè)（在職研究生在讀），研究方向是計算機系統(tǒng)理論，現(xiàn)供職于廣州市紡織服裝職業(yè)學校，從事信息技術(shù)助理講師的工作。