畢業(yè)設(shè)計(jì)學(xué)分制模式下基于遺傳算法-預(yù)覽頁(yè)

　

【正文】 System。利用計(jì)算機(jī)輔助排課，是教學(xué)管理實(shí)現(xiàn)科學(xué)化，現(xiàn)代化的重要課題之一。排課問(wèn)題不僅是教學(xué)管理工作中必需面對(duì)的問(wèn)題，而且也是運(yùn)籌學(xué)中研究的一個(gè)問(wèn)題——時(shí)間表問(wèn)題 (TimeTable Problems，簡(jiǎn)記TTPS)。我國(guó)對(duì)排課問(wèn)題的研究始于20世紀(jì)80年代初期，所用方法從模擬手工排課到運(yùn)用人工智能構(gòu)建專家系統(tǒng)或決策支持系統(tǒng)。但由于實(shí)際排課問(wèn)題存在各種各樣的限制條件與特殊要求，至今沒(méi)有一個(gè)有效地普遍適用的排課算法。在對(duì)固體物質(zhì)進(jìn)行退火處理時(shí)，常先將它加溫使其粒子可自由運(yùn)動(dòng)，以后隨著溫度的逐漸下降，粒子逐漸形成低能態(tài)晶格。禁忌搜索的思想最早由Glover于1986年提出，它是對(duì)局部領(lǐng)域搜索的一種擴(kuò)展，是一種全局逐步尋優(yōu)算法，是對(duì)人類智力過(guò)程的一種模擬。文獻(xiàn)[10]提出了基于二部圖的排課模型，并揉合蟻群算法AS、ACS、MMAS三個(gè)不同模型的優(yōu)點(diǎn)，提出一種面向排課問(wèn)題的改進(jìn)型蟻群算法，但是問(wèn)題求解復(fù)雜，操作繁瑣。2 遺傳算法遺傳算法(Genetic Algorithm, GA)是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過(guò)程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。遺傳算法是一種借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展起來(lái)的高度并行、隨機(jī)、自適應(yīng)的搜索算法。遺傳算法是多學(xué)科結(jié)合與滲透的產(chǎn)物，從產(chǎn)生至今已廣泛地運(yùn)用于包括工程設(shè)計(jì)、制造業(yè)、人工智能、計(jì)算機(jī)科學(xué)、生物工程、石油勘探、自動(dòng)控制、社會(huì)科學(xué)、商業(yè)和金融等各個(gè)領(lǐng)域。簡(jiǎn)單二進(jìn)制編碼的采用得到了Holland早期理論結(jié)果（Schema定理、最小字母表原理）的支持，但仍有很多不足之處。這些編碼方法的提出是啟發(fā)式的，缺乏一個(gè)理論基礎(chǔ)來(lái)判斷各種編碼方法的好壞并指導(dǎo)它們的設(shè)計(jì)。遺傳算法正是根據(jù)適應(yīng)值對(duì)個(gè)體進(jìn)行選擇的。選擇體現(xiàn)“適者生存”的原理，通過(guò)適應(yīng)值選擇優(yōu)質(zhì)個(gè)體而拋棄劣質(zhì)個(gè)體。由于其對(duì)遺傳搜索過(guò)程具有較大的影響，很多人早就意識(shí)到它在遺傳算法中的重要性。Muhlenbein和SchlierkampVossen討論了選擇強(qiáng)度在收斂分析中的應(yīng)用。Potts概括了17種交叉方法。本文根據(jù)這些相關(guān)算子設(shè)計(jì)原則，設(shè)計(jì)了有利于排課操作的遺傳算子。 遺傳算法的基本術(shù)語(yǔ)既然遺傳算法效法于自然選擇的生物進(jìn)化，是一種模仿生物進(jìn)化過(guò)程的隨機(jī)算法，那么我們先分析幾個(gè)生物學(xué)的基本概念與術(shù)語(yǔ)，這對(duì)理解和運(yùn)用遺傳算法是非常重要的[13]。生物的基因數(shù)量根據(jù)物種的不同多少不一，小的病毒只含有幾個(gè)基因，而高等動(dòng)植物的基因卻數(shù)以萬(wàn)計(jì)。有時(shí)個(gè)體的集合也稱為個(gè)體群。對(duì)生存環(huán)境適應(yīng)度高的物種將獲得更多的繁殖機(jī)會(huì)，而對(duì)生存環(huán)境適應(yīng)程度較低的物種，其繁殖的機(jī)會(huì)就會(huì)相對(duì)較少，甚至逐漸滅絕。(7) 復(fù)制(reproduction)細(xì)胞在分裂時(shí)，遺傳物質(zhì)DNA通過(guò)復(fù)制而轉(zhuǎn)移到新產(chǎn)生的細(xì)胞中，新的細(xì)胞就繼承了舊細(xì)胞的基因。(10) 編碼(coding)DNA中遺傳信息在一個(gè)長(zhǎng)鏈上按一定的模式排列，即進(jìn)行了遺傳編碼。遺傳算法是從代表問(wèn)題可能潛在解集的一個(gè)種群(population)開(kāi)始的，而一個(gè)種群則由經(jīng)過(guò)基因(Gene)編碼(coding)的一定數(shù)目的個(gè)體(individual)（或染色體）組成。在每一代中，根據(jù)問(wèn)題域中個(gè)體的適應(yīng)度(fitness)大小挑選(selection)個(gè)體，并借助于自然遺傳學(xué)的遺傳算子(geneticoperators)進(jìn)行組合交叉(crossover)和變異(mutation)，產(chǎn)生出代表新的解集的種群。如果不滿足優(yōu)化準(zhǔn)則，開(kāi)始產(chǎn)生新一代的計(jì)算。遺傳算法的過(guò)程如圖21所示。① 選擇是用來(lái)確定重組或交叉?zhèn)€體，以及被選個(gè)體將產(chǎn)生多少子代個(gè)體?；蛑亟M是結(jié)合來(lái)自父代交配種群中的信息產(chǎn)生新的個(gè)體。由于各學(xué)校自身情況、采用的教學(xué)模式(學(xué)分制或?qū)W年制)的不同，導(dǎo)致各學(xué)校排課流程存在差異，本文以江西財(cái)經(jīng)大學(xué)為分析對(duì)象，設(shè)計(jì)出適合學(xué)分制模式下的高校排課算法[14,15]。教務(wù)處工作流程如圖32 所示。學(xué)院工作流程如圖33 所示。如因特殊情況調(diào)整，須按學(xué)校有關(guān)規(guī)定辦理手續(xù)，并由教務(wù)處下達(dá)調(diào)課通知。并注明了所列出的每門課程的學(xué)分，及每個(gè)學(xué)生畢業(yè)時(shí)所要修完的總學(xué)分。教務(wù)處可以根據(jù)具體情況調(diào)整課程表，并下達(dá)調(diào)課通知。一般我們按照周課表來(lái)上課，從開(kāi)學(xué)第一周到第N周，江西財(cái)經(jīng)大學(xué)每上學(xué)上課16周。(2) 課程因素課程有課程編號(hào)、課程名稱、課程的周學(xué)時(shí)、課程學(xué)分、課程對(duì)教室類型的要求、所屬學(xué)院等。每個(gè)教室都有教室類型，教室類型包括普通教室、多媒體教室、語(yǔ)音教室、實(shí)驗(yàn)室、機(jī)房、體育館等。(5) 班級(jí)因素本文所涉及的班級(jí)均指的是教學(xué)班（選課班或行政班）。(6) 校區(qū)因素每個(gè)校區(qū)都有編號(hào)和名稱。 排課的約束條件排課問(wèn)題中，主要任務(wù)是將班級(jí)、教師、課程安排在一周內(nèi)某一不發(fā)生沖突的時(shí)間和教室，保證課表在時(shí)間的分配上符合一切共性(時(shí)間上不存在沖突)和個(gè)性(不與老師的特殊時(shí)間要求沖突)的要求，在此基礎(chǔ)上，使其安排在各個(gè)目標(biāo)上盡量達(dá)到最優(yōu)。對(duì)教師、班級(jí)、課程、時(shí)間、教室等幾部分資源進(jìn)行最優(yōu)化配置，才能保證排課的順利完成以及充分發(fā)揮各個(gè)資源的優(yōu)勢(shì)以達(dá)到提高管理水平和教學(xué)質(zhì)量的目的。軟約束則是指排課過(guò)程中若滿足則更佳，不能滿足也不影響教學(xué)的開(kāi)展的約束條件。(2) 軟性約束條件① 每個(gè)時(shí)間段安排的課程數(shù)盡量均勻；② 一周的課表中每個(gè)上課時(shí)間都有一定的優(yōu)度，盡量將課程安排在優(yōu)度高的時(shí)間段；③ 一門課程的多次上課的時(shí)間盡量間隔并分布均勻；④ 教室容量適中，以充分利用教室；⑤ 兩個(gè)課時(shí)的課程盡量不要安排在下午或晚上，以免造成一個(gè)課時(shí)的浪費(fèi)。(1) 教室利用度教室利用度，是衡量所開(kāi)設(shè)的課次的教室利用程度的好壞標(biāo)志。節(jié)次優(yōu)度含有一定的主觀因素，每個(gè)人對(duì)同一時(shí)間片的偏好不同，不同的季節(jié)同一個(gè)時(shí)間片的上課效果也會(huì)有差別。本系統(tǒng)采用的節(jié)次優(yōu)度值如表31所示。我們對(duì)所有的課程的日組合優(yōu)度進(jìn)行優(yōu)度判定。我們可以利用全校的所有周上課次數(shù)大于1的課程的日組合優(yōu)度的平均值來(lái)衡量課程表中日組合優(yōu)度的優(yōu)劣。 ()式中 ——所有課程的時(shí)間片利用度的平均值 ——課程i的第j個(gè)時(shí)間片的利用度 ——課程i的所分配的時(shí)間片的個(gè)數(shù) ——所開(kāi)設(shè)的課程的總數(shù)的值越大，說(shuō)明課表的所有課程的時(shí)間片利用度越高。的值越大，我們認(rèn)為課程表中每個(gè)時(shí)間段安排的課程的數(shù)目越均勻。public class CourseUnite { internal int CourseUniteNo。 //班級(jí)編號(hào) internal char CampusNo。 //課程周學(xué)時(shí) }(2) 基因基本信息類排課的任務(wù)就是為每個(gè)教學(xué)任務(wù) (課元)安排一個(gè)合適時(shí)間和教室。 //課元編號(hào) internal int roomno。同時(shí)，為方便檢測(cè)同一老師同一時(shí)間只能上一個(gè)班課的約束，創(chuàng)建了一個(gè)記錄教師上課時(shí)間安排的數(shù)組。internal sbyte[] arrangetime=new sbyte[20]。在排課系統(tǒng)初始化數(shù)據(jù)時(shí)，我們視老師不能上課的時(shí)間段為在該時(shí)間段老師已經(jīng)安排了課程，這樣該時(shí)間段就不能再安排課程了。public class FitnessValue //染色體適應(yīng)度類 { internal int chromosomeno。在排課時(shí)，為每個(gè)校區(qū)建立相應(yīng)的教師信息表。 //教室類型 } 教室調(diào)度算法根據(jù)江西財(cái)經(jīng)大學(xué)的校區(qū)分布情況，在系統(tǒng)中建立了三個(gè)教室信息表，分別為蛟橋園教室信息表、楓林園教室信息表、麥廬園教室信息表。在為課元分配教室時(shí)，從教室信息表的第一條記錄開(kāi)始檢索，從小到大依次匹配，匹配成功則返回該教室編號(hào)。同時(shí)，一個(gè)教室可用，但是這個(gè)教室在20個(gè)時(shí)間段中已經(jīng)安排了15或更多個(gè)時(shí)間段，則說(shuō)明該教室已經(jīng)負(fù)荷很重，若再給這個(gè)教室安排課程，很容易出現(xiàn)教室利用的沖突。具體算法描述如下：(1) 產(chǎn)生一個(gè)隨機(jī)數(shù)，其值在0到19之間，作為一個(gè)時(shí)間片；(2) 根據(jù)該時(shí)間片，利用教室調(diào)度算法調(diào)用一個(gè)空閑的教室類型容量都符合要求的教室；(3) 判斷該課元的周學(xué)時(shí)；(4) 初始化countfalse=0(記錄失敗次數(shù))；(5) 根據(jù)周學(xué)時(shí)的大小，產(chǎn)生隨機(jī)數(shù)(019)。在分配合理的教室和時(shí)間段后，將該教室的相應(yīng)時(shí)間段設(shè)置為占用，實(shí)現(xiàn)了同一時(shí)間同一教室只能上一門課，同一時(shí)間同一班級(jí)只能上一門課的約束。但是在進(jìn)行交叉操作室，我們交換交叉點(diǎn)處兩個(gè)課元的上課時(shí)間，其他不變。 排課問(wèn)題中遺傳算法的設(shè)計(jì) 遺傳算法的編碼在遺傳算法中如何描述問(wèn)題的可行解，即把一個(gè)問(wèn)題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法就稱為編碼。一個(gè)好的編碼方法使交叉操作、變異操作可以簡(jiǎn)單的實(shí)現(xiàn)和執(zhí)行。我們把課程、班別、教師作為一個(gè)元組考慮，稱之為課元信息。然后，根據(jù)排好序的課元信息來(lái)初始化每個(gè)課表的課元編號(hào)，這樣就保證了在任一課表中，每個(gè)課元的位置是相對(duì)固定的，在進(jìn)行交叉操作時(shí)就可以直接交換相同位置的教室和時(shí)間片信息。填充染色體的函數(shù)是FillCourseTable(Genetic[] coursetable)，coursetable為一個(gè)基因?qū)ο髷?shù)組，每一個(gè)基因?qū)?yīng)一個(gè)課元的排課信息。 遺傳操作的設(shè)計(jì)(1) 選擇操作的設(shè)計(jì)在排課問(wèn)題中，我們采用輪盤(pán)賭的方法進(jìn)行選擇操作。相反適應(yīng)度小的個(gè)體被淘汰的可能性就很大。將每條染色體的編號(hào)、適應(yīng)度值記錄在fitnessvalue中。最后利用輪盤(pán)賭的方法，隨機(jī)選擇一條染色體，并將其作為父?jìng)€(gè)體插入下一代種群中。它的好處在于破壞染色體形狀的可能性小，但產(chǎn)生新個(gè)體的可能性也小，因此對(duì)于復(fù)雜的問(wèn)題，這種交叉算子收斂速度很慢。由于每個(gè)課程表中課元的位置是相對(duì)固定的，采用這種交叉方式并沒(méi)有打亂課元元素，避免了班級(jí)和課程不對(duì)應(yīng)的沖突，同時(shí)由于在生成初始種群時(shí)的個(gè)體(排課方案)都是可行的排課方案，教室容量和類型都滿足上課要求，這樣也避免了教室容量與班級(jí)上課人數(shù)不匹配的沖突。若需要變異，則隨機(jī)產(chǎn)生一個(gè)變異點(diǎn)，并讀取該點(diǎn)處課元任課老師不能上課的時(shí)間(canottime)，然后將不能上課的時(shí)間轉(zhuǎn)換為老師已經(jīng)排課的時(shí)間。染色體是復(fù)制到下一代還是被淘汰，都是依據(jù)適應(yīng)度的大小。在計(jì)算染色體適應(yīng)度之前，首先要檢查染色體是否存在沖突，若存在沖突，則將其適應(yīng)度置為0，說(shuō)明這是一個(gè)不可行的排課方案，將其淘汰。它不僅能用于WEB服務(wù)程序的開(kāi)發(fā)，還能開(kāi)發(fā)強(qiáng)大的系統(tǒng)級(jí)程序。 參數(shù)設(shè)置對(duì)排課效率的影響測(cè)試系統(tǒng)的實(shí)例是以江西財(cái)經(jīng)大學(xué)20062007學(xué)年第一學(xué)期的部分?jǐn)?shù)據(jù)為基礎(chǔ)的排課實(shí)例。各參數(shù)的取值對(duì)各目標(biāo)收斂造成的影響，可以根據(jù)遺傳理論定性確定及通過(guò)實(shí)驗(yàn)分析取得。本文取2002遺傳代數(shù)取值過(guò)小，目標(biāo)并沒(méi)有收斂，各目標(biāo)沒(méi)有得到充分優(yōu)化，取值過(guò)大，各目標(biāo)早已收斂，只是在重復(fù)遺傳，且運(yùn)行時(shí)間長(zhǎng)。每次實(shí)驗(yàn)我們進(jìn)行5次測(cè)試，最終取平均值作為此次實(shí)驗(yàn)的遺傳效率值。經(jīng)過(guò)多次測(cè)試，本文取種群規(guī)模為200。一般選擇較大的交叉概率，以盡量產(chǎn)生優(yōu)秀的個(gè)體。表53 交叉概率對(duì)排課效率的影響(單位：秒)編號(hào)實(shí)驗(yàn)一()實(shí)驗(yàn)二()實(shí)驗(yàn)三()12345平均值從表53可以看出，交叉概率越大，遺傳效率越高。但是當(dāng)變異概率設(shè)置過(guò)小，卻會(huì)導(dǎo)致全局搜索難于進(jìn)行，因?yàn)槿鄙僮儺?，種群往往在局部搜索，很難跳出來(lái)。(4) 遺傳代數(shù)對(duì)排課結(jié)果的影響遺傳代數(shù)決定遺傳操作的次數(shù)，遺傳代數(shù)越大，遺傳操作所用的時(shí)間相應(yīng)增加。表55 遺傳代數(shù)對(duì)排課結(jié)果的影響編號(hào)實(shí)驗(yàn)一(1000)實(shí)驗(yàn)二(1200)實(shí)驗(yàn)三(1300)實(shí)驗(yàn)四(1500)12345平均值從表55可以看出，遺傳代數(shù)并不是越大越好。與傳統(tǒng)的人工排課方式的比較如下：(1) 相似方面① 無(wú)沖突性指課程表必須滿足所有硬性約束。教師在進(jìn)行每一節(jié)課的教學(xué)之前需要深入領(lǐng)會(huì)教學(xué)大綱的精神、仔細(xì)研究教材內(nèi)容、恰當(dāng)安排教學(xué)過(guò)程和認(rèn)真編寫(xiě)教案。另一方面，連續(xù)的課程安排之后是相對(duì)的空閑，這使學(xué)生對(duì)新學(xué)習(xí)的知識(shí)缺乏鞏固。例如，在本文中，我們考慮了如果某時(shí)間段某老師不能上課，則該時(shí)間不給其安排課程。② 時(shí)間安排對(duì)稱方面的差異人工排課時(shí)，對(duì)周上課次數(shù)大于1的課程的多次安排往往采用時(shí)間對(duì)稱的方式。因此，人工排課中雖然會(huì)考慮課程的節(jié)次優(yōu)度，但最終排課時(shí)很難真正實(shí)施。本文實(shí)現(xiàn)了基于遺傳算法的排課問(wèn)題解決方案。③ 根據(jù)排課問(wèn)題的約束條件，設(shè)計(jì)了基因初始算法、教師調(diào)度算法、沖突檢測(cè)算法，并建立了合理的適應(yīng)度函數(shù)。但是課表中蘊(yùn)含著紛繁復(fù)雜的約束條件，想設(shè)計(jì)出一個(gè)滿足實(shí)際應(yīng)用的通用的排課算法，還需要做更多的分析和研究。④ 應(yīng)用多種群的并行遺傳算法求解排課問(wèn)題也是進(jìn)一步改進(jìn)排課效果的一個(gè)方向。是狼就要練好牙，是羊就要練好腿。拼一個(gè)春夏秋冬！贏一個(gè)無(wú)悔人生！早安！—————獻(xiàn)給所有努力的人.