【正文】 在論文的撰寫過程中老師們給予我很大的幫助，幫助解決了不少的難點(diǎn)，使得論文能夠及時完成，這里一并表示真誠的感謝。最后，我要特別感謝我的導(dǎo)師趙達(dá)睿老師、和研究生助教熊偉麗老師。感謝老師四年來對我孜孜不倦的教誨，對我成長的關(guān)心和愛護(hù)。最后，我要感謝我的父母對我的關(guān)系和理解，如果沒有他們在我的學(xué)習(xí)生涯中的無私奉獻(xiàn)和默默支持，我將無法順利完成今天的學(xué)業(yè)。從他身上，我學(xué)到了許多能受益終生的東西。這期間凝聚了很多人的心血，在此我表示由衷的感謝。首先非常感謝學(xué)校開設(shè)這個課題，為本人日后從事計(jì)算機(jī)方面的工作提供了經(jīng)驗(yàn)，奠定了基礎(chǔ)。畢業(yè)設(shè)計(jì)（論文）使用授權(quán)聲明本人完全了解濱州學(xué)院關(guān)于收集、保存、使用畢業(yè)設(shè)計(jì)（論文）的規(guī)定。對本文的研究做出重要貢獻(xiàn)的個人和集體均已在文中以明確方式標(biāo)明。本人完全意識到本聲明的法律結(jié)果由本人承擔(dān)。電子科技大學(xué)學(xué)報(bào)。計(jì)算機(jī)自動排課的技術(shù)研究[D]。2005年01期.[10]吳志斌,陳淑珍,孫曉安。福建教育學(xué)院學(xué)報(bào)。2005年.[7]黃曉梅,王浩。吉林大學(xué)?；趯＜蚁到y(tǒng)的排課軟件的研究與設(shè)計(jì)[D]。2003年.[3]胡獻(xiàn)華。安徽大學(xué)。我非常的感謝謝文平老師，黃國華老師，孫文兵老師以及恩師戴亞濱老師等老師，在我人生一大轉(zhuǎn)折點(diǎn)的時候給予我巨大的幫助，一個人只有堅(jiān)持，再難的事終究會有一個好的結(jié)果，也許不是很理想，但是我相信，只要你堅(jiān)持了，那成功就已經(jīng)過半了。 由于水平有限，設(shè)計(jì)作品有很多不足之處，請老師和同學(xué)們多多批評、指正。在此我們先給出實(shí)驗(yàn)數(shù)據(jù)如下表所示：表51 實(shí)驗(yàn)數(shù)據(jù)表Table 51 table of experimental data描述值班級數(shù)62教師數(shù)量100理論課教室數(shù)量72語音室數(shù)量10公共機(jī)房數(shù)量12所有課程數(shù)量150所有專業(yè)實(shí)驗(yàn)課教室數(shù)量70天數(shù)5每天節(jié)數(shù)10操場數(shù)量2教學(xué)任務(wù)記錄310 為了得出最優(yōu)化結(jié)果，結(jié)合實(shí)驗(yàn)的思想，讓實(shí)驗(yàn)更具說服力，本文給出了操作數(shù)的不同參數(shù)值(文[3])：表52 參數(shù)表Table 52 table of parameters操作數(shù)參數(shù)值雜交概率突變概率進(jìn)化代數(shù)100進(jìn)化代數(shù)200種群總數(shù)50個體種群總數(shù)100個體種群總數(shù)200個體經(jīng)過在不同情況下實(shí)驗(yàn)得出進(jìn)化結(jié)果，每次所排出的課表經(jīng)檢測無任何沖突，我們?yōu)榱俗鰧Ρ?，在下面圖中予以●當(dāng)種群數(shù)是100時，種群中最優(yōu)個體隨著代數(shù)的增加而變化的曲線：圖16 最優(yōu)個體適應(yīng)度值變化Chart 16 variation of fitness of optimal individaul●當(dāng)種群數(shù)是50時，種群中最優(yōu)個體隨著代數(shù)的增加而變化的曲線：圖17 最優(yōu)個體適應(yīng)度值變化Chart 17 variation of fitness of optimal individaul●當(dāng)種群數(shù)是200時，種群中最優(yōu)個體隨著代數(shù)的增加而變化的曲線：圖18 最優(yōu)個體適應(yīng)度值變化Chart 18 variation of fitness of optimal individaul●當(dāng)進(jìn)化代數(shù)為100時，不同種群總數(shù)的三種情況的種群中每代最優(yōu)個體走勢做比較：圖19 最優(yōu)個體適應(yīng)度值變化Chart 19variation of fitness of optimal individaul實(shí)驗(yàn)分析：隨著代數(shù)的增加可以看出個體的適應(yīng)度值是逐漸增加，而到了一定代數(shù)后就不再增加。(4)“固定課”問題:有的教師因?yàn)槟承┰蛐枰才盘囟ǖ慕虒W(xué)時一段，如教室受到其他課程的影響，或者某學(xué)院部門領(lǐng)導(dǎo)，因工作性質(zhì)關(guān)系，須指定安排上課時間為“星期五的第6節(jié)”，這樣的要求在編排課程表時必須滿足，即“固定時段”問題。每門課程都有授課計(jì)劃，包括起始周和截止周以及周學(xué)時安排。每個課程都有自己的編號、名稱以及開課學(xué)院。圖12 主界面Chart 12 main interface學(xué)院管理本院的一些教師分配。在進(jìn)化過程中，沖突必須完全消除。 一門課在一周內(nèi)分散安排，提供可引導(dǎo)性學(xué)習(xí)環(huán)境。適應(yīng)度值實(shí)際上反映了排課人員對課表理想化編排的一種期望。消除冗余數(shù)據(jù)雖然能提高空間的利用率，但同時也會提高檢索的代價，因此，這三方面必須權(quán)衡，選擇一個折中方案。這會將數(shù)據(jù)庫的概念結(jié)構(gòu)轉(zhuǎn)換為邏輯結(jié)構(gòu)方法簡單，易于實(shí)現(xiàn)。對于數(shù)據(jù)庫中教學(xué)樓，教室，班級等一些數(shù)量都未知的數(shù)據(jù)進(jìn)行存儲，運(yùn)用數(shù)組顯然不能解決，會出現(xiàn)很多的冗余，浪費(fèi)內(nèi)存，并且處理繁瑣。于是，一個初始個體便產(chǎn)生了。首先把固定教學(xué)時間的教師編碼填入該行中，然后使用隨機(jī)函數(shù)產(chǎn)生一個1—25的數(shù)，將該班的其它教師編碼填入其中。其中BJS為參與課表編排的班級總數(shù)；d.“種群”——由ZQS個個體構(gòu)成。上2學(xué)時課時，該教師編碼只能出現(xiàn)1次，上4學(xué)時課時該教師編碼出現(xiàn)2次，依次類推。每一門課程都有其各自不同的特點(diǎn)，比如上機(jī)課需要在機(jī)房上課，英語口語需要在語音室上課，體育課需要在操場上課，為此我們規(guī)定：把16bits分開，前后8bits各有不同的意思； 圖5比特信息圖在此我們把課程分為專業(yè)必修課，專選科，公共課，上機(jī)實(shí)驗(yàn)課，專業(yè)實(shí)驗(yàn)課，體育課，英語語音課，前三個屬于理論課，不在此分配教室。這也反應(yīng)了排課要人性化，畢竟有些教師有特殊的要求，例如，年齡、事物等等。圖3 遺傳算法流程圖實(shí)施遺傳算法的第1步，就是把與求解目標(biāo)相關(guān)的實(shí)際參數(shù)進(jìn)行基因編碼，這是算法的關(guān)鍵與難點(diǎn)。(2)計(jì)算出每個個體的適應(yīng)度函數(shù)值，以進(jìn)行優(yōu)勝劣汰。自動排課系統(tǒng)的設(shè)計(jì)在本課題中，遺傳算法解決的問題只是求出班級+課程+教師+時間的記錄集，得到比較優(yōu)的一個解，然后再去按條件用教室去填充這個記錄集，就形成了可行可用的課表。所以，可知在三類約束條件之中，前兩者是衡量排課方案是否切實(shí)可行的基本標(biāo)準(zhǔn)，軟約束是衡量排課方案是否人性化的標(biāo)準(zhǔn)，通常判別一個排課方案的優(yōu)劣標(biāo)準(zhǔn)有多個。只有在滿足全部約束條件和避免所有沖突的基礎(chǔ)上，才能保證整個教學(xué)計(jì)劃合理正常進(jìn)行。然后，對這個（班級，教師，課程，時間）記錄做變換，讓位置表去填充它，當(dāng)然是按條件填充，就可以完成整個排課的大部分工作了，從而得到課表。另一個功能，學(xué)院在這塊可以查詢本學(xué)院的課表，還有學(xué)院內(nèi)班級的課表。當(dāng)上課的人數(shù)遠(yuǎn)遠(yuǎn)小于教室容量時，這種情況也往往不合適的。如今的大學(xué)都有很多的教學(xué)樓，校園面積也很大，宿舍與教學(xué)樓，教學(xué)樓與教學(xué)樓之間的距離可能會比較大，如果安排不佳的話，會導(dǎo)致學(xué)生上課時要跑動很遠(yuǎn)距離，浪費(fèi)不必要的時間。 (2)“一師多班”沖突問題:一位教師可能只給一個班講課，也可能同時給多個班級講課，也就是說同一教師可以在多個班出現(xiàn)，這樣可能會出現(xiàn)同一時間，同一教師在多個班級上課的沖突，在編排課程表時此類沖突必須解決。每門課程都有指定的教室類型。全校有N個教學(xué)班級，則周課表為:以25個時間片為列，形成一維的時間序列，每個班級為行組成的一個二維數(shù)據(jù)表。 這樣，每周5天涉及25個時間片。 (2)上午3, 4節(jié)課10:1011:50。開始算法設(shè)計(jì)的基礎(chǔ)是對這些數(shù)據(jù)之間的問題的透徹分析和適當(dāng)?shù)奶幚怼?(2) 盡可能滿足個別教師的特殊上課時間要求；課程門類多、班級多、教師少、教室少、教師連續(xù)上課的要求、班級連續(xù)上課的時間合理安排是排課時發(fā)生沖突和矛盾的主要因素，而班級多、教室少則是矛盾的重要方面。本文根據(jù)高校開課的具體情況，采用優(yōu)化的編碼方案，滿足排課過程中的一些硬性和軟性約束因素，利用遺傳算法對課表進(jìn)行了優(yōu)化，從而得到了最終的無沖突、更人性的排課方案。我們認(rèn)為，問題不盡在數(shù)學(xué)建模上，還與問題的處理方式有關(guān)。 前言 隨著高校招生逐年擴(kuò)張，大學(xué)課程向著廣度和深度發(fā)展，高校的教師、教室等一些資源越發(fā)顯得緊張，不管是在時間還是效率方面，用人工排課已不能夠解決現(xiàn)有的問題。 遺傳算法； 排課問題； 適應(yīng)度函數(shù)36ABSTRACTAbstract In recent years, with the University Expansion and expansion of the has bee a very difficult problem. Limited resources in the classroom context, Curriculum has bee more onerous. The courses bee the key to teaching management at the same time. It affects students in developing and improving the quality of teaching to some extent. Arranging automatically by puter, not only to academic staff from the cumbersome task of freeing Arranging, improve efficiency of educational administration, but also to improve the quality of teaching management. Rational and efficient use of limited teaching resources, making variety of teaching activities, teaching management and other related work orderly and standardized manner, keeping the normal teaching order, At the same time promoting the academic management of information technology play a very important role.
Timetabling problem is a constrained, multiobjective, intractable binatorial optimization problems, it belongs to NPComplete problems. Researchers have proposed many other Timetabling Problem, such as Simulated Annealing, List of search optimization, Constraint satisfaction and so on. But genetic algorithm is very effective algorithm for solving the optimal solution .GA carry out genetic and functional variation through Crossover, mutation and selection of three genetic operators. And adopt fitness function ensure Arranging Results tend to the best. According to the problem that running time is too long,which the researchers didn39。
遺傳算法通過交叉、變異、選擇三種遺傳算子來實(shí)現(xiàn)遺傳和變異的功能,