• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    遺傳算法在高校排課調(diào)課中的應(yīng)用

    2019-01-06 02:19:13葛曉春彭俊文
    電腦知識與技術(shù) 2019年32期
    關(guān)鍵詞:遺傳算法

    葛曉春 彭俊文

    摘要:高校排課中待解決的主要問題就是合理的安排教師、教室、時間、班級等教學(xué)資源。大多數(shù)遺傳算法對排課的應(yīng)用考慮的是節(jié)次優(yōu)先等問題,而對排課中的教學(xué)資源沖突采用消除的辦法解決。針對排課中的沖突,該文以班級、時間、教室為三維坐標(biāo)空間,以排課中存在的沖突數(shù)為適應(yīng)度函數(shù),采用平面交叉的方式,通過精英保留策略構(gòu)造遺傳種群進(jìn)行選擇進(jìn)化。

    關(guān)鍵詞:遺傳算法;三維編碼;沖突函數(shù);平面交叉;精英保留

    中圖分類號:TP301.6 文獻(xiàn)標(biāo)識碼:A

    文章編號:1009-3044(2019)32-0080-02

    1概述

    隨著高校的不斷擴(kuò)招,對高校教學(xué)資源的合理分配顯得越來越重要,其直接影響到高校的正常教學(xué)工作的開展。尤其是新學(xué)期開學(xué)時對高校內(nèi)的課程安排問題最為突出。排課問題中,涉及了任課教師、教室、教學(xué)班、任課時間等多種因素,而我們首要解決的便是在存在大量教師、教室、教學(xué)班、認(rèn)可時間等情況下找到一種合理的排課方案,例如:同一時間同一老師不能出任兩門課程等。

    排課問題是一個復(fù)雜的、多約束的組合問題。國外從20世紀(jì)50年代末開始對排課問題進(jìn)行研究,并在S.Even和Cooper的論文中被證明這是一個NP完全問題。在意識到無法求出排課問題的精確解的情況下,科學(xué)家們致力于研究新的排課算法并應(yīng)用于實(shí)際當(dāng)中,例如Ferland等提出的將整數(shù)規(guī)劃用于排課算法,然而由于該算法計(jì)算量大,只能運(yùn)用于小型課表的編排。

    2基于遺傳算法的排課理論

    遺傳算法(Genetic Algorithm,簡稱GA)是一種模擬生物自然進(jìn)化過程的優(yōu)化算法,它由美國Michigan大學(xué)的Holland教授于1975年首先提出,并吸引了大批學(xué)者進(jìn)行研究與推廣。

    高校排課的實(shí)質(zhì)就是利用本校有限的資源,合理的安排教師和學(xué)生的授課任務(wù)。通常,在高校中都是以班為單位參與到教學(xué)計(jì)劃的制定當(dāng)中,因此排課當(dāng)中涉及的因素有教室、教師、班級、時間、課程等因素。其次,在實(shí)際當(dāng)中,教師與課程是對應(yīng)的,即對一門固定的課程,其任課老師會提前確定下來。再有,對每一個班級,其所上課程是確定的。而不同班級之間又相互關(guān)聯(lián),即可能存在同一教師擔(dān)任不同班級的某一門課程的授課任務(wù)或者不同班級可能存在占用同一間教室的情況。排課所對應(yīng)的任務(wù)便是為不同班級合理的安排授課時間以及地點(diǎn),以使其不產(chǎn)生沖突。一個合理的排課方案必須滿足以下要求:

    同一時間同一教師不能出任一門以上的課程;

    同一時間同一教室不能安排一門以上的課程;

    同一時間同一班級不能安排一門以上的課程。

    2.1遺傳算法的基本思想

    遺傳算法是從代表問題的可能潛在的解集的一個種群開始的,而一個種群是由經(jīng)過基因編碼的一定數(shù)目的個體組成。初始種群產(chǎn)生后,根據(jù)適者生存和優(yōu)勝劣汰的原則,逐代演化產(chǎn)生越來越好的個體。而逐代演化的過程則是根據(jù)當(dāng)代種群中個體適應(yīng)度的優(yōu)良挑選出父代,并根據(jù)遺傳學(xué)中的遺傳算子進(jìn)行交叉與變異等產(chǎn)生子代,子代又組成新的種群。如此,使得每一代的個體越來越優(yōu)秀,即所求問題的解越趨近真實(shí)解。

    2.2排課問題的遺傳算法模型

    2.2.1編碼

    使用遺傳算法首要考慮的便是如何編碼,即怎樣將問題與遺傳算法對應(yīng)起來。例如,求一個一元函數(shù)的極大值問題,可將自變量用二進(jìn)制的方式編碼,這樣既利于計(jì)算機(jī)的計(jì)算又方便執(zhí)行遺傳算法中的交叉、變異等操作。排課問題中,課程與教師的關(guān)系為多對一、班級與課程的關(guān)系為一對多,而教室與班級、課程并無實(shí)際聯(lián)系。由此,可采用三維網(wǎng)格的形式將一張課表完整的表示。

    建立三維坐標(biāo)系,以x軸表示班級,y軸表示時間段,z軸表示教室,如圖1所示。

    此時,若通過x軸上某一點(diǎn),得到平行于yoz平面的切面,該平面上又有許多網(wǎng)格節(jié)點(diǎn),如圖2。

    將x軸上對應(yīng)班級下的課程按照一個網(wǎng)格節(jié)點(diǎn)至多填充一門課程一教師對的原則全部填人上述平面的網(wǎng)格節(jié)點(diǎn)中,即該班級的課程安排完成。對于剩下的班級以此類推,由此一個課表的編碼完成。

    2.2.2個體適應(yīng)度函數(shù)

    自然選擇過程中,適者生存、優(yōu)勝劣汰的法則普遍存在。而評判個體是否較其他個體優(yōu)秀則是根據(jù)其對環(huán)境的適應(yīng)來確定。在排課問題中,個體代表一張課表,其適應(yīng)度越高則表示越趨近合理。因此,排課問題的適應(yīng)度可由課表中存在的沖突數(shù)來反映,沖突越多則表明是適應(yīng)度越低。故本問題的適應(yīng)度函數(shù)可由如下公式計(jì)算:

    其中,fllness為個體適應(yīng)度,clashes為個體存在的沖突數(shù)量。當(dāng)適應(yīng)度為1時,說明該個體所表示的課表合理。

    2.2.3選擇

    生物的進(jìn)化時通過自然選擇來完成的,在遺傳算法理論中,搜索解通過選擇操作來達(dá)成。常見的選擇操作有賭輪盤選擇以及錦標(biāo)賽選擇,而錦標(biāo)賽選擇更具通用性,且性能更優(yōu)。錦標(biāo)賽選擇策略每次從種群中隨機(jī)取出一定數(shù)量的個體(放回抽樣),然后選擇其中最好的一個個體進(jìn)入子代種群。通常采用二元錦標(biāo)賽選擇,即每次隨機(jī)取出2個個體。

    2.2.4交叉

    交叉操作在遺傳算法起到核心作用,通過交叉使得遺傳算法的搜索能力大大增加,同時使子代更容易出現(xiàn)優(yōu)良的基因模式。排課問題中,不能在不同班級之間進(jìn)行交叉操作,否則會破壞課表結(jié)構(gòu)。遺傳算法中,常見的交叉方式主要有單點(diǎn)交叉、兩點(diǎn)交叉以及多點(diǎn)交叉等。其中,兩點(diǎn)交叉的原理為隨機(jī)選擇染色體上的2個位置,將兩者中間的基因片段互換。本文根據(jù)編碼結(jié)構(gòu),結(jié)合兩點(diǎn)交叉原理,設(shè)計(jì)了排課問題的面交叉方式。操作如下:

    1)隨機(jī)選擇編碼結(jié)構(gòu)中的某一個班級;

    2)將父代中該班級對應(yīng)的平行于教室一時間平面的切面相互交換;

    3)檢測交換后生成的子代適應(yīng)度;若適應(yīng)度更低則返回1),否則交叉結(jié)束。

    2.2.5變異

    遺傳算法中,變異操作保持了種群的多樣性,同時防止遺傳算法的過早收斂。在基于二進(jìn)制編碼的遺傳算法中,變異操作一般是對0-1二進(jìn)制串中的某一位進(jìn)行求反操作。例如,將0變?yōu)?或?qū)?變?yōu)?。在排課問題中,一個班級下的課程不能改變的原則不變,因此變異操作可用如下方法進(jìn)行:

    1)隨機(jī)選擇編碼結(jié)構(gòu)中的某一個班級;

    2)隨機(jī)選擇該班級下某兩個時間段;

    3)交換步驟2)中選擇的兩個時間段中的教師一課程對,變異結(jié)束。

    2.2.6精英保留策略

    對遺傳算法來講,能否收斂到全局最優(yōu)解是其首要解決的問題,而Rudoph已經(jīng)采用有限馬爾可夫鏈理論證明了僅采用交叉、變異和選擇(比例選擇法)三個標(biāo)準(zhǔn)遺傳算子的遺傳算法不能收斂到全局最優(yōu)解?!熬⒈A簟辈呗允荄e Jong針對遺傳算法提出的,該策略保證了遺傳算法的全局收斂性。在排課問題中,采用群體“精英保留”策略,即:將父代種群和子代種群合并后,選擇其中最優(yōu)的N個(種群大?。﹤€體構(gòu)成下一代種群。

    2.2.7算法結(jié)束條件

    算法本身不能無限制的執(zhí)行下去,因此必須設(shè)置排課算法的結(jié)束條件。對于排課問題,算法結(jié)束標(biāo)志著找到一個最優(yōu)解或者沒有找到,因此根據(jù)適應(yīng)度值為1可判斷算法結(jié)束,此時找到最優(yōu)解;其次,設(shè)置算法的最大迭代次數(shù),若算法執(zhí)行完了最大迭代次數(shù)還沒有找到最優(yōu)解則強(qiáng)制結(jié)束。

    在算法結(jié)束后,輸出的原始結(jié)果為一條經(jīng)過編碼的染色體,即課表。通過解碼的方式可找到任意班級、教室、教師的課表。

    3結(jié)束語

    本文通過分析高校排課問題中存在的主要問題,結(jié)合遺傳算法理論,構(gòu)造三維編碼模式,極大地降低了排課問題中的沖突量。同時,在編碼方案的基礎(chǔ)上通過平面交叉的方式,結(jié)合“群體精英保留”策略實(shí)現(xiàn)排課算法理論??紤]的遺傳算法的并行性,該算法在計(jì)算機(jī)上能快速穩(wěn)定的進(jìn)行排課求解。

    猜你喜歡
    遺傳算法
    基于遺傳算法的模糊控制在過熱汽溫控制系統(tǒng)優(yōu)化中的應(yīng)用
    電子制作(2019年16期)2019-09-27 09:34:44
    遺傳算法對CMAC與PID并行勵磁控制的優(yōu)化
    基于自適應(yīng)遺傳算法的CSAMT一維反演
    基于遺傳算法的建筑物沉降回歸分析
    一種基于遺傳算法的聚類分析方法在DNA序列比較中的應(yīng)用
    基于遺傳算法和LS-SVM的財(cái)務(wù)危機(jī)預(yù)測
    遺傳算法識別模型在水污染源辨識中的應(yīng)用
    協(xié)同進(jìn)化在遺傳算法中的應(yīng)用研究
    軟件發(fā)布規(guī)劃的遺傳算法實(shí)現(xiàn)與解釋
    基于改進(jìn)的遺傳算法的模糊聚類算法
    固原市| 武城县| 长武县| 静海县| 雷州市| 南宫市| 赣州市| 泰和县| 武汉市| 孝感市| 东安县| 新兴县| 镇巴县| 荃湾区| 遵化市| 五峰| 富平县| 巫山县| 三亚市| 卫辉市| 怀宁县| 五台县| 台南市| 大姚县| 惠来县| 磐安县| 平定县| SHOW| 德江县| 龙岩市| 祁连县| 郴州市| 定兴县| 沙坪坝区| 淮南市| 彭阳县| 襄垣县| 繁峙县| 平湖市| 长沙县| 渝北区|