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

在審

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

1.基于遺傳算法排課系統的設計方法，其特征在于：在排課系統中，約束條件分分為兩種，一種是必須要滿足的條件，稱為硬約束條件；另一種是盡量要滿足的條件，軟約束條件；

(1)硬約束條件：硬約束條件是排課問題求解過程中必須要滿足的條件，它同時具有客觀的邏輯的特點；從班級、教室、教師和時間四個方面設計出硬性約束條件，如下表示方式；

①一個班級不可以同一時間上兩種或兩種以上的教學課程，相對應的表達式如下：

其中：l_i,l_j表示第i個和第j個課程，t_k表示第k個時間段，T表示時間段集，L表示課程集，c(l_X，t_k)表示在t_k時間段上l_X課程的班級；

②一個的教室不可以同一時間上兩種或兩種以上的教學課程，相對應的表達式如下：

其中：l_i,l_j表示第i個和第j個課程，t_k表示第k個時間段，T表示時間段集，L表示課程集，r(l_X，t_k)表示在t_k時間段上l_X課程占用的教室；

③一個老師不可以同時上兩種或兩種以上的所授課程，相對應的表達式如下：

其中：l_i,l_j表示第i個和第j個課程，t_k表示第k個時間段，T表示時間段集，L表示課程集，m(l_X，t_k)表示在t_k時間段上l_X課程的老師；

④上課的學生的數量要小于安排上課的教室空間可承載的人數，相對應的表達式如下：

其中：r_i表示第i個教室，c_j表示第j個班級，t_k表示第k個時間段，R表示班級集，T表示時間段集，Capatity(r_i)表示r_i教室容量，P(c_j)表示c_j班級人數；

(2)軟約束條件：硬約束條件是排課問題求解過程中盡量要滿足的條件，

①學生課程表中的課程盡量分布均勻，同種課程分不同的時段安排,相對應的表達式如下：

其中：p_i表示第i個學生，l_j表示第j個課程，t_k表示第k個時間段且共n個，P表示學生集，L表示課程集，P(t_X)表示學生上課的時間；

②老師所授課程也盡可能的有一定的時間間隔，方便老師的作息和課下準備,相對應的表達式如下：

其中：m_i表示第i個老師，t_k表示第k個時間段且共n個，M表示老師集，L表示課程集，M(t_X)表示老師授課時間；

③兩個相鄰課程安排的教室盡可能的近，讓學生轉換教室的路程盡可能縮短,相對應的表達式如下：

其中：p_i表示第i個學生，l_j表示第j個課程，R(d_X)表示學生上課教室的地點位置；

④上課人數少的課程盡可能不要安排到空間大的教室，避免造成教室資源的浪費,相對應的表達式如下：

其中：r_i表示第i個教室且教室共α個，c_j表示第j個班級且班級共β個，Capatity(r_i)表示r_i教室容量，P(c_j)表示c_j班級人數；

基于改進的遺傳算法的編碼方式；

在生物界里，染色體決定了物種的遺傳，物種之間的差異受染色體的影響；不同物種特有的基因信息被儲存在染色體里，基因信息有序的排列組合，稱為基因編碼；用染色體表示課程安排方案，并對課程的安排特征進行基因編碼；通過課程安排獲得的課程表被視為一個染色體，課程表中的信息被視為染色體上的不同基因；利用對染色體的選擇、交叉、變異處理，選定適應度高的染色體；排課問題可以理解為合理分配一個包含教學課堂信息數據段的教學單元是必要的；教學單元可理解為信息的存儲空間；改進后的遺傳算法采用十進制的編碼方式，對每個課程的信息：教學班級、上課時間、課程名稱、授課教師、教室類型作為染色體進行編碼共30位，

表3-1課表基因編碼

班級編碼包含入學年份、所屬院系、所屬專業、班級編號，分別以2位、2位、2位、1位十進制表示；

表3-2班級編碼

課時編碼即上課時間編碼，包含所在周次、所在星期、所在節次，分別以2位、1位、2位十進制表示；

表3-3課時編碼

課程編碼包含課程類型、授課班數、每周課次、課程編號，分別以1位、1位、1位、4位十進制表示；

表3-4課程編碼

教師編碼包含所屬院系、教師職稱、教師編號，分別以2位、1位、3位十進制表示；

表3-5教師編碼

教室編碼包含所屬樓棟、所屬樓層、門牌編號，分別以1位、2位、2位十進制表示；

表3-6教室編碼

基于改進遺傳算法的自適應交叉率和變異率

自適應變化的交叉率p'_c和變異率p'_m對應的數學公式如下：

式中f_max為種群中的最大適應度值，f_avg為群體中平均適應度值，f為要交叉操作的兩個個體中較大的適應度值，f'為要變異操作的個體的適應度值，P_c、P_m為大于0小于1的常數。