[發明專利]基于遺傳算法排課系統的設計方法

在審

• 申請號: 202010544724.8
• 申請日: 2020-06-15
• 公開（公告）號: CN111784127A
• 公開（公告）日: 2020-10-16
• 發明（設計）人: 孫光民;李亞輝
• 申請（專利權）人: 北京工業大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q10/10;G06Q50/20;G06N3/12
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 劉萍

基于遺傳算法排課系統的設計方法屬于算法理論中算法分析與設計領域，針對現有技術中遺傳算法的編碼方式不準確、交叉變異率的固定不變，適應度函數的不合理，本發明對傳統遺傳算法的編碼方式進行改進，由傳統的二進制編碼改進為含有特定意義的十進制編碼方式，編碼方式更加的規范和準確。本發明中的遺傳算法的交叉率和變異率會隨適應度自動變化，改進遺傳算法的自適應交叉率和變異率能夠可以使算法較快收斂到全局最優解。并在教學時間段分配的均勻度、學生課程安排均勻度、課程時間段安排優度等方面對適應度函數進行改進，并對傳統的遺傳算法和改進后的遺傳算法進行實驗數據對比，結果改進后的遺傳算法在排課中的性能和效率更令人滿意。

技術領域

本發明中設計基于遺傳算法排課系統的研究與設計。通過對傳統遺傳算法的編碼方式 的改進，即由傳統的二進制編碼改進設計為十進制編碼方式，使得編碼方式更加的規范和 準確。同時改進了交叉率和變異率，使其能夠自適應的變化，可以快速收斂到最優解。在 種群個體沖突次數、教學時段分配均勻度、班級課程安排均勻度、課程時間段安排優度、教室資源利用率等方面對適應度函數進行了改進。通過算法的平均適應度值和運行消耗的時間對比，改進的遺傳算法排課明顯優于傳統的遺傳算法。

背景技術

隨著高校的增加和每年人才的擴招以及專業的增加，對于高校的排課任務愈來愈復雜 繁重。傳統的人工排課使用手工操作存在許多弊端，如重復勞動嚴重、效率低下、且不能 達到資源的最優化配置等，將產生大量的文件和數據，這對于查找、更新和維護都帶來了 不少的困難。傳統的人工排課使用手工操作存在許多弊端，如重復勞動嚴重、效率低下、且不能達到資源的最優化配置等，將產生大量的文件和數據，這對于查找、更新和維護都帶來了不少的困難。傳統的人工排課使用手工操作存在許多弊端，如重復勞動嚴重、效率低下、且不能達到資源的最優化配置等，將產生大量的文件和數據，這對于查找、更新和 維護都帶來了不少的困難。

在教學計劃的不斷完善和各高校校園網建立的大背景下，設計滿足高校教務要求的排 課系統顯得十分必要。在教學計劃的不斷完善和各高校校園網建立的大背景下，設計滿足 高校教務要求的排課系統顯得十分必要。且排課系統有安全性要求高、交互性強、處理數 據量大等人工難以實現的特點。因此設計一個基于校園網絡的人工智能化且操作簡便的排 課系統是高校教務管理信息系統實現的首要條件，同時也是一大難點，因為排課管理要求 綜合考慮教師、課程、班級、教室、時間等諸方面的因素，統籌兼顧，使課表既符合教學 規律，又能夠充分利用現有資源使其最大限度地發揮作用。

目前我國高校排課已經由傳統早期的手工排課轉向了計算機自動排課，但是許多的突 出問題亟待解決。比如：(1)課表安排沖突。學生的課表在同一時間安排了兩節以上的課，導致學生在該時間只能選擇一門重要的課聽講，放棄了同一時間的其他課程。這造成了學生無法修學沖突課程。(2)教室安排不合理。教室安排過小，導致學生提前占座搶 位置的行為，甚至很多學生站在教室后面和走道聽課，教室空間的擁擠嚴重影響了學生的 聽課專注程度。

發明內容

本發明是基于改進遺傳算法排課的研究與設計，對傳統的遺傳算法的編碼方式進行有 效的改進，即將課表染色體編碼為30位有特定含義的十進制編碼。對傳統遺傳算法的交 叉率和變異率進行了自適應變化的改進，使算法能快速收斂到全局最優解。并根據多個約 束條件設計出更合理更準確的適應度函數，使得算法在種群個體的平均適應度和運行速度 性能上有更優越的效果。

本發明采用了如下的技術方案及實現步驟：

1.對排課問題的有關集合進行定義

排課問題的數學模型可簡化為一個資源分配模型，即在滿足一定的約束條件的情況下， 對于某些定量的資源分配給不懂的需求個體。我們的任務是將班級、教師、課程、教室根 據教學計劃安排在一周內某個不發生沖突的時間段。因此，我們給出以下有關集合的定義: