遺傳算法在大學排課問題中的應用

1、遺傳算法在大學排課問題中的應用口王維陳滿林胡冠字(長春工業(yè)大學軟件職業(yè)技術學院 吉林長春130012摘要:針對排課問題,基于遺傳算法的特點分析了解決排課問題的可能性,介紹了排課原則,以及遺傳算法在 排課問題上的應用性研究,利用遺傳算法進行編碼,交叉、變異,以及進行沖突檢測,用遺傳算法解決這一復雜的 NP問題。關鍵詞:排課遺傳算法最優(yōu)解沖突檢測中圖分類號:024文獻標識碼:A 文章編號:1007-3973(20100916702當今時代,伴隨著計算機技術的快速發(fā)展,許多繁瑣的人 工操作已經(jīng)被計算機系統(tǒng)所取代。排課系統(tǒng)作為高校教務管 理系統(tǒng)中最重要也最復雜的部分之一,已經(jīng)成為國內(nèi)外眾多 高校以及軟

2、件公司的研究課題,在這方面也取得了許多的理 論成果和實現(xiàn)方法。因此,研究開發(fā)一個實用的排課系統(tǒng)具 有十分重要的現(xiàn)實意義。1研究背景隨著我國教育體制改革的不斷深入和發(fā)展,高校的辦學 規(guī)模逐年擴大,因此,編排一張適用的、科學的課表已經(jīng)成為 每一所高校在新學期開始之前必須進行的一項極其重要工作。 簡而言之,它具體的工作內(nèi)容就是將課程、教師、教室和學生 四者之間進行合理的調(diào)度分配,從而達到四者之間的完美結(jié) 合,從而使整個教學活動能夠正常、有序地順利進行。大學課表的編排不但數(shù)量多、規(guī)模大、涉及的因素多、限 制條件多,而且結(jié)構復雜,要想編排出合理、科學的課表必然 要消耗大量的時間與精力,它復雜性的原因在于

3、排課中資源 約束條件與特殊要求對有限時空目標的限制。由于近幾年各 個高校連年擴招,使得課程安排的工作量逐年增大,學校自身 問題的逐步暴露,這也給課程安排增加了許多的難度,這些問 題主要包括:教室資源的不足、師資力量的不足、多媒體教學 設備的不足等,這些問題的出現(xiàn)對排課工作提出更高的要求。 伴隨著科學技術的不斷發(fā)展和提高,計算機具有的強大功 能已經(jīng)被人們所深刻地認識,計算機應用技術也已經(jīng)逐漸進入 人類社會的各個領域,同時在各個領域都發(fā)揮著非常重要的 作用。作為計算機應用技術的一部分,通過計算機進行排課, 具有手工排課無法比擬的優(yōu)點,包括:排課速度快、省時省力、一I一.一一一一一.I.一一一.t.

4、一一一I一.t一.t一一一一一一.t.一一.I一一40使學生對所講授的樹種特征產(chǎn)生直觀的感受,這樣不僅調(diào)動了 他們的興趣,同時也大大提高了教學效果;其次,園林樹木學教 師本身應利用一切機會到各地考察、研究,在專業(yè)知識方面進 一步完善自己,在課堂講授中就會做到繪聲繪色。作為學生, 則必須對實驗和教學實習格外重視。在教學時數(shù)不斷縮短的 情況下,理論課教學必須是突出重點,不可能面面俱到。學生 只有在實驗和實習過程中,依靠自己親手的觀察和解剖,才能 對一些結(jié)構、概念和術語理解透徹,?使課內(nèi)知識進一步深化, 做到永生不忘。園林樹木學這門學科實踐性很強,必須經(jīng)過從 課本到實際觀察,再到課本幾個來回的重復,

5、才能夠?qū)浞N的 形態(tài)特征了如指掌。如:學生到山上實習,讓他們投入到大自 然的懷抱,在老師對現(xiàn)場樹種的講解下,學生邊認樹木邊采集 標本,通過大量的實物,使學生很輕松、自如掌握了知識要點, 很順利的就記住了每種園林樹木的特征、特性,同時還培養(yǎng)學 生觀察、思維、動手、綜合解決生產(chǎn)實際問題和創(chuàng)新等能力,與 學生呆在枯燥的實驗室里,面對變形的干標本相比,學習效果 明顯要強得多。寓教于樂,在游玩中認識了不少樹種,是最有 效的授課方法。4重視學生學法指導,培養(yǎng)學生自學能力哈佛大學教學理念:學習是為了有能力繼續(xù)學習。一個優(yōu) 秀的學生不是老師教出來的,而是在老師的指導下學出來的。 方法是運用知識的橋梁。在教學過

6、程中,教師只有依據(jù)學生的 特點,結(jié)合相應的教學內(nèi)容,有意識地滲透有科學性、有針對性 的學法指導,融教法與學法為一體,才能使學生養(yǎng)成良好的學 習習慣,掌握科學的學習方法,最終實現(xiàn)教師“授人以漁”,培養(yǎng) 學生終身的學習能力。例如,我與學生交流時發(fā)現(xiàn),學生普遍 感覺記憶園林樹木種類特征、科屬特征、拉丁文學名是一件很 枯燥的事情,有些學生時間花費不少,就是記不住。我告訴他 們理解是記憶的前提,記憶是理解的過程,如果不理解而硬背, 只能成為知識的“容器”。并總結(jié)了在理論結(jié)合實際的基礎上, 運用主要樹種法、常見法、本地法、要點法、比較歸納法、總論指 導法、各論主體法、識別基礎法等多種方法,實踐效果良好。如

7、:園林樹木的科、屬、種雖然很多,但相似的科與科、屬與屬、種與 種之間的形態(tài)特征等卻有一定的規(guī)律,采用比較法找到這一規(guī) 律,即找出它們的相同特征和不同特征,記憶將會成為一件比 較輕松的事情。通過比較,不僅掌握的它們的規(guī)律所在,強化 了記憶效果,更掌握了園林樹木學的重要學習方法。由理解到 記憶抓知識的實質(zhì):由分散到集中抓知識的積累;由累加到串 聯(lián)抓知識的結(jié)構:由應試到應用抓知識的運用。這樣,學生在 學習中通過主動思考,積極思維,就能實現(xiàn)學習目標。學會學 習是時代發(fā)展的需要,更是學生終身學習與發(fā)展的需要。 綜上所述,教師在教學中要靈活運用各種有效的教學方 法,努力探索,從而達到最佳教學效果。參考文獻

8、:【l】邱國金,孫賢琦,劉國華.高職園林樹木學課程的教改 研究與實踐【J】.中國農(nóng)業(yè)教育,2003.02.【2】沈大剛.園林樹木學課程的教改研究與實踐【J】.安徽農(nóng) 業(yè)科學,2009.02.【3】陳建.園林樹木學教改初探【J】.安徽農(nóng)業(yè)科學,2007.08.斛協(xié)論壇2010年第9期(下 斛鮑查找方便、檢索迅速、可靠性較高、保密性較好、存儲量較大、 人工成本較低、使用壽命較長等。這些優(yōu)點可以極大地提高 排課管理工作的效率。排課系統(tǒng)是對一個教育單位而言是不 可缺少的重要組成部分,排課效果的好壞直接影響到教學工作 能否有序地、正常地開展,對于學校的領導來說也是一項至關 重要的工作,因此排課系統(tǒng)必須為

9、用戶提供充足的信息以及快 捷的查詢手段。利用計算機進行排課操作,任何具有使用者 都能夠清晰的看到教學中的各種信息,可以高效、快速的工作, 這不但減輕了教務人員手Tf#課的工作,而且極大提高了管 理工作的效率,可以合理高效地分配、利用教學資源,間接地 提高了教學質(zhì)量,推進了教學活動的良性循環(huán)。因此,研究并 改進一個排課系統(tǒng)具有十分重要的實際意義。2排課原則排課問題實質(zhì)上一種資源競爭問題。在排課過程中要全 面考慮教師、課程、教室、時間、學生人數(shù)等多方面因素,做到 統(tǒng)籌兼顧,才能排出即符合教學規(guī)律,又滿足各方面要求的課 程表。一個好的課表應該既能符合學校的管理要求,又能滿 足所有參與者的基本要求,盡

10、量使絕大多數(shù)課程的安排能夠 令學校師生滿意。為了達到這樣的目的,在排課中必須遵守 以下六個基本原則:(1在同一時間段內(nèi),一位教師只能安排一門課程。(2在同一時間段內(nèi),一個班級只能安排一門課程。(3在同一時間段內(nèi),一問教室只能安排一門課程。(4根據(jù)能提供的教室總數(shù)安排同一時間段內(nèi)安排的課程 總數(shù),二者要相適應。(5每門課程的學生人數(shù)不應大于所安排教室的座位數(shù), 二者也要相適應。(6多媒體教室應合理安排,因為有的科目用多媒體設備 教學的效果比較好,但是有的科目并不需要多媒體教室,如果 安排了多媒體,就造成了教學資源的浪費。同時,為了使排出的課表更具人性化、更合理、更科學,排 課還需要考慮以下五個因

11、素:(1盡可能保證同一個班級連續(xù)的兩門課之間更換教室的 機率最小,或就近安排。(2每門課程在一周內(nèi)的上課時間盡可能合理分布。(3同一門課程的不同上課時間應盡可能安排在同一間教 室,同時要隔一天以上再安排,以給任課教師留出充足的備課 和批改作業(yè)的時間,使學生也有足夠的時間復習和消化所學 的內(nèi)容,并有時間預習下次課的內(nèi)容。(4學生每天必修課的安排盡可能趨于合理、平衡,應盡量 避免出現(xiàn)全天有課,而第二天一天沒課的情況。(5滿足個別教師(如外聘教師的特殊上課時間要求。 3遺傳算法在排課問題中的應用遺傳算法應用類似基因演化的循環(huán)過程,它的演算過程 如下:(1根據(jù)排課的因素產(chǎn)生相關基因編碼和染色體,并隨機

12、產(chǎn) 生一定數(shù)目的初始種群,即一定數(shù)目的班級課程表。(2對個體,即班級課程表適應度進行評估,如果個體的適 應度與優(yōu)化準則相符,則輸出最佳個體和它所代表的最優(yōu)解, 并結(jié)束計算,否則進入第(3步。(3依據(jù)適應度情況選擇再生個體。(4按照一定的交叉概率及交叉方法生成新個體。(5按照一定的變異概率及變異方法生成新個體。(6由交叉和變異產(chǎn)生新一代種群,之后返回第(2步,最 后進行沖突檢測與消除。通?？衫镁幋a技術對變量進行編碼,將變量轉(zhuǎn)化成適 合群體進化的表達形式。對目標函數(shù)進行處理操作,使其能 夠蘊含遺傳算法的適應度函數(shù)。這樣,在群體進化的過程之 中,適應度就能夠反映模型的目標函數(shù)。當群體進化結(jié)束的 時

13、候,適應度值最大的那個個體對應的目標函數(shù)值最小,這個 個體即為最優(yōu)解。最佳個體的產(chǎn)生過程是這樣的:首先產(chǎn)生 一個初始化種群,然后對初始化種群中的每一個個體進行適 應度的計算,得出個體對環(huán)境的適應程度。計算后的這個個 體能否滿足準則判定,如果能夠滿足,那么算法就找到了這個 個體并停止汁算,如果不滿足準則判定,那么算法將會對這個 種群進行選擇、交叉、變異等相關操作。遺傳操作的目的是從 初始化種群中篩選出較優(yōu)的個體,之后進行演變,對演變后的 子代群體,再重新進行優(yōu)化準則的判定,如此循環(huán)下去,直到 找到一個最優(yōu)的個體,或者不滿足其它循環(huán)條件為止。約束條件和優(yōu)化的目標有輕重緩急的分別,約束條件必須 滿足

14、,優(yōu)先級別必須最高,同時,各種優(yōu)化目標之間也有優(yōu)先級 的分別,應盡量滿足級別較高的優(yōu)化目標。將它們都轉(zhuǎn)化成罰 值,而其罰值權則是不同的,高一級的罰值權比所有低級的罰 值的和值還要大。由此可以得出,采用靜態(tài)定標罰值權的方法 是不可取的,因此我們采用動態(tài)罰值權的定標方法。遺傳進化 在進行選擇的操作過程中,我們著眼于目標函數(shù)或者適應度函 數(shù)的相對值而并不關心它的絕對值,確定這個個體目標函數(shù)的 真正目的在于確定該個體在群體中的優(yōu)劣,因此我們可以根據(jù) 整個群體情況進行罰值權的統(tǒng)一定標,把各級的罰值用向量進 行表示,此時,目標函數(shù)就是各級罰值的帶權和。如果想終止可以采用以下方法;(1給定一個迭代步數(shù); .

15、(2當設定與估計的最優(yōu)解的距離小于某個范圍時,就終 止搜索:(3當與最優(yōu)解的距離連續(xù)若干步保持不變時,就終止搜索。 排課問題同樣是一個N.P問題,無論應用哪種方法沖突 問題的出現(xiàn)都不可能避免。但是,解決沖突問題的方法有很 多種,這里采用一種利用二進制0、1矩陣檢測沖突的方法。在 沖突檢測過程中其基本的約束條件為:(1任何教師在同一時間最多只能安排一門課。(2任何班級在同一時問最多只能安排一門課。(3任何教室在同一時間最多只能有-I"1課程被安排。 為了避免沖突的出現(xiàn),在本系統(tǒng)的設計、實現(xiàn)過程中引進 了沖突檢測函數(shù),保證當排完一位教師的所有相關課程后,系 統(tǒng)就會通過該沖突檢測函數(shù)對這位

16、教師課程安排的沖突情況 進行檢測并做出相應的修正。參考文獻:【1】畢曉君.信息智能處理技術【M】.北京:電子工業(yè)出版社,2010【2】陳強.通用高校排課算法研究【J】.科技廣場,2006年第07期 【3】張文修。梁怡.遺傳算法的數(shù)學基礎(第2版【M1.西安:西 安交通大學出版社,2003.【4】潘以鋒.高校智能排課系統(tǒng)的算法【J】.上海師范大學學報(自 然科學版,2006,(10.斛協(xié)論1ij2010年第9期(下 遺傳算法在大學排課問題中的應用作者:王維 , 陳滿林 , 胡冠宇作者單位:長春工業(yè)大學軟件職業(yè)技術學院,吉林·長春,130012刊名:科協(xié)論壇(下半月英文刊名:SCIENC

17、E & TECHNOLOGY ASSOCIATION FORUM年,卷(期:2010,""(9被引用次數(shù):0次參考文獻(4條1. 畢曉君.信息智能處理技術M.北京:電子工業(yè)出版社,2010.2. 陳強.通用高校排課算法研究J.科技廣場,2006年第07期.3. 張文修,梁怡.遺傳算法的數(shù)學基礎(第2版M.西安:西安交通大學出版社,2003.4. 潘以鋒.高校智能排課系統(tǒng)的算法J.上海師范大學學報(自然科學版,2006,(10.相似文獻(10條1.期刊論文 張燕 . 宋錦斌 基于遺傳算法的排課系統(tǒng) -電腦知識與技術 2010,6(11排課問題是一直是業(yè)界NP完全問題,

18、牽涉到多約束,多條件,多目標等問題,遺傳算法一直是當今解決排課問題的優(yōu)先選擇算法.把班級,課程,教師,教 室等因素進行染色體編碼,利用遺傳算法的選擇、交叉,變異等特性進行對排課因子進行選擇篩選,得到的最優(yōu)解,基本能滿足當代大學排課的基本需求,在 實際運行中有一定的實用價值.2.學位論文 肖鵬 遺傳算法在排課系統(tǒng)中的應用研究 2008現(xiàn)代科學理論在研究與實踐中存在大量與組合優(yōu)化、自適應等相關的問題。使用常規(guī)方法解決這類問題,除一些簡單情況之外,人們對于大型復雜 系統(tǒng)的優(yōu)化和自適應問題的處理顯得無能為力。排課問題正是一個有約束的、多目標的組合優(yōu)化時間表問題,并且已經(jīng)被證明為一個NP完全問題。 遺傳

19、算法借鑒生物界自然選擇和自然遺傳機制,使用群體搜索技術,尤其適用于處理傳統(tǒng)搜索方法難以解決的復雜的非線形問題。經(jīng)過近50年的發(fā) 展,遺傳算法在理論研究與實際應用中取得了巨大的成功,是一種非常有效的解決NP完全組合問題的方法。本文結(jié)合湖北工業(yè)大學工程技術學院教務管理的實際情況,采用遺傳算法求解排課問題,并從遺傳算法的基本理論入手,首先,分析了遺傳算法的 特點、數(shù)學基礎以及遺傳操作和算法結(jié)構;其次,討論了排課問題中的排課因素、主要約束條件與求解目標,分析了排課問題的組合爆炸性和不確定性 ,并用數(shù)學模型完整地描述了排課問題。在實際的排課系統(tǒng)算法設計中采用運籌學中分層規(guī)劃的思想,對具體問題應用遺傳算法

20、進行分步求解,設計了 遺傳算法的基因、適應度函數(shù)及成本函數(shù),改進了單點交叉以及變異操作,確定了種群規(guī)模及遺傳代數(shù),設計并編程實現(xiàn)了一個基于遺傳算法與調(diào)整算 法相結(jié)合的排課系統(tǒng)。系統(tǒng)經(jīng)時間性能和排課性能測試,表明降低了排課復雜度,提高了排課效率。該排課算法的實現(xiàn)很好地滿足了工程技術學院復雜的排課管理需求 ,同時對其他高校排課系統(tǒng)的開發(fā)也具有參考價值。3.期刊論文 蘭兆青 . 白艷萍 . Lan Zhaoqing. Bai Yanping遺傳算法在排課問題中的應用 -太原師范學院學報(自然 科學版 2008,7(1在分析造成排課困難的各種因素的基礎上,將遺傳算法運用到解決排課問題中.并給出了該算法

21、的詳細設計(文中采用了二進制編碼和矩陣編碼相結(jié)合 的編碼方法;給出了帶有權值的適應度函數(shù);對染色體中的時間碼采用映射同/異或交叉;采用兩點變異的變異方法和排課模型;很好地解決了多約束條件 下的排課問題.4.學位論文 熊婷 基于遺傳算法的高校排課系統(tǒng)研究 2006排課是學校教學管理中十分重要、又相當復雜的教學管理工作之一,尤其是隨著高校擴招帶來的在校學生人數(shù)劇增與學校教學資源緊缺之間的矛盾 已經(jīng)日趨嚴重,普通的手工排課已經(jīng)越來越不能滿足需求。隨著計算機技術的日益廣泛使用,計算機輔助排課系統(tǒng)(CACSS已經(jīng)成為高校教學管理中的一 個重要的研究領域。排課問題實際上是時間表優(yōu)化的問題,由于其超大的求解

22、規(guī)模和眾多的約束條件,是運籌學領域和計算機領域一直致力尋求解決但 沒有得到解決的NP難解問題,即如何根據(jù)班級的課程設置、課程的周內(nèi)次數(shù)以及利用現(xiàn)有的教室、教師資源進行科學的合理安排。因此,國內(nèi)外對排課 算法的研究越來越活躍,紛紛走向探求排課算法的各類經(jīng)驗方法的求解道路。本文首先闡述手工排課系統(tǒng)已遠遠不能勝任當今高校排課需要,然后具體闡述了自動排課系統(tǒng)在國內(nèi)外的發(fā)展現(xiàn)狀與趨勢,通過細致分析近年來國 內(nèi)外各種有關排課算法與結(jié)合我國高等學校現(xiàn)有狀況的基礎上,提出了基于遺傳算法的高校排課系統(tǒng),并詳細闡述了遺傳算法設計中的編碼方案以及遺 傳算子的實現(xiàn)方法。根據(jù)高校排課系統(tǒng)的需求,給出了高校排課系統(tǒng)的設計

23、與實現(xiàn),從高校排課系統(tǒng)的實施結(jié)果看出,本文提出的基于遺傳算法的高校 排課系統(tǒng)不但能夠減少排課人員的工作量,而且能夠提高排課的準確性,從而具有良好的市場前景。在系統(tǒng)實施過程中,成功地將排課系統(tǒng)與高校信息 管理系統(tǒng)對接,從而使得排課系統(tǒng)能夠更好的為高校管理系統(tǒng)服務。5.期刊論文 方江祎 . 段富 基于遺傳算法的排課問題分層研究 -電腦開發(fā)與應用 2010,23(5分析了目前高校排課存在的問題,研究如何利用遺傳算法解決排課問題以及沖突,并設計應該考慮的各種約束條件.把傳統(tǒng)的排課問題分為時間排課和 教室排課兩個方面來研究,在時間排課方面又分為單目標排課和多目標排課兩個步驟來考慮.通過計算機化管理的排課

24、問題,能夠有效地提高工作效率. 6.學位論文 李建麗 基于遺傳算法的排課系統(tǒng)研究 2009排課問題是典型的多重約束和組合優(yōu)化問題,并且已經(jīng)被證明是一個NP完全問題。影響排課問題的因素不僅眾多,而且各因素之間相互制約,加上 不同的學校因各自情況不一,很難形成一個相對固定的排課模式。借助計算機軟件,實現(xiàn)排課的自動化和人性化,已經(jīng)成為各高校教學管理人員的一個 共識,也是解決排課問題的理想途徑。遺傳算法是一種借鑒生物界自然選擇和進化機制發(fā)展起來的高度并行、自適應的隨機搜索算法。由于其思想簡單 、易于實現(xiàn)以及表現(xiàn)出來的健壯性,是一種非常有效的解決NP完全問題的方法。用遺傳算法解決排課問題是一種較明智的選

25、擇。 本論文將遺傳算法應用于排課問題的求解。首先,分析了遺傳算法的特點、數(shù)學基礎以及遺傳操作和算法結(jié)構,討論了排課問題中的排課因素、主要約 束條件與求解目標,分析了排課問題的組合爆炸性和不確定性,提出了排課問題求解方法的總體框架和技術路線。其次,采用魯棒性較好的遺傳算法 ,針對遺傳算法搜索效率較低的問題,深入研究了優(yōu)化解法,構造了混合式的教師基因編碼,較之傳統(tǒng)編碼方案,該編碼方案更簡單、更高效、更易于 理解,并且極大地降低了排課遺傳算法的復雜度。在算法實現(xiàn)過程中,添加了沖突的檢測和消除算子,設計了關鍵的優(yōu)化遺傳算子,完成了自動課程表 編排系統(tǒng)。 7.期刊論文 張帥 . ZHANG Shuai遺

26、傳算法在排課系統(tǒng)中的應用 -電腦編程技巧與維護 2009,""(8隨著高校招生規(guī)模的擴大,教務管理系統(tǒng)中的排課方式也顯得越來越重要.本文討論了排課問題中的影響因素、各類約束條件、求解目標以及求解難 點,運用遺傳算法的基本理論,研究了如何解決高校的排課問題.實踐證明,利用遺傳算法求解排課問題,其搜索過程帶有智能性和并行性,并且操作簡單,可 以更少地依賴于實際問題的情況,從而能夠有效地解決排課問題.8.學位論文 王仲華 遺傳算法求解排課問題的研究 2006排課問題是一個有約束的、多目標的組合優(yōu)化問題,并且已經(jīng)被證明為一個NP完全問題。運用計算機進行自動排課既是高校教務管理的迫切

27、需要 ,同時也有重要的理論意義。但由于排課問題復雜多變,幾十年來一直沒有很好解決。本文的目的就是要找到一種解決這種復雜問題的方法。遺傳算法是一種借鑒于生物界自然選擇和進化機制發(fā)展起來的高度并行、自適應的隨機搜索算法,是一種非常有效的解決NP完全的組合問題的方法 。本文將遺傳算法應用于排課問題的求解,進行了以下幾個方面研究工作:1.系統(tǒng)完整地討論了排課問題中的影響因素、主要約束條件、求解目標和難點,用數(shù)學模型完整地描述了排課問題,并提出了排課問題求解方法的 總體框架和技術路線。2.給出了排課問題的ERD和類圖,設計了排課系統(tǒng)的數(shù)據(jù)結(jié)構,并以此對課表安排過程的各個子算法進行了研究。3.針對排課問題研究了染色體編碼方式以及遺傳操作算子的設計,并引入多目標決策協(xié)調(diào)模型,提出了一種基于多目標決策協(xié)調(diào)模型的適應度計算 方法,并改進了遺傳算法一般結(jié)構,形成了一套多目標協(xié)同優(yōu)化的排課算法。4.以VC+為基本開發(fā)工具,MSSQLSERVER2000為后臺數(shù)據(jù)庫,設計和實現(xiàn)基于GA算法的排課測試系統(tǒng)。通過一個實例分析了遺傳算法的各個參數(shù)的設 置對排