遺傳算法在大學(xué)排課問題中的應(yīng)用

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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