[發明專利]基于進化算法的走班制高中排課方法

在審

• 申請號: 202110709194.2
• 申請日: 2021-06-25
• 公開（公告）號: CN113435647A
• 公開（公告）日: 2021-09-24
• 發明（設計）人: 劉靜;王超;滕祥意;郝星星
• 申請（專利權）人: 西安電子科技大學廣州研究院
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/20;G06N3/12
• 代理公司: 廣州大象飛揚知識產權代理有限公司 44745
• 代理人: 趙娜

1.一種基于進化算法的走班制高中排課方法，其特征在于，具體包括以下步驟：

S1，構建一個高中年級的課時表，作為進化算法的一條染色體X；

S101，基因編碼：設基因x表示排課任務中的課時，其具體組成包括但不限于課程信息x¹、教室編號x²、是否有課標志x³；

S102，構造染色體：構建以全年級班級為列，班級/授課時間段為行的課程表X，基因x作為元素放入課程表X中，課程表X為一條染色體；

S2，設定與課程、教師和教師相關的多種硬約束條件，以及課程連堂和課時均勻分布的軟約束條件；

S3，基于約束條件，使用進化算法排課得到最優的排課方案；

S301，初始化大小為P的父代種群；

S302，為每條染色體對應的課表安排教室并計算父代種群中每一條染色體對應的目標函數值；

S303，對父代種群實施選擇操作產生交配池種群；

S304，對交配池種群實施交叉操作產生子代種群，假設從交配池種群中不放回地選擇兩條染色體為X₁和X₂，依次將X₁和X₂的對應行進行交配，首先將染色體進行劃分；然后每天產生一個隨機數r，如果r小于交叉概率p_c，將X₁和X₂的對應行基因x¹進行交配產生子代染色體的對應行，否則，設置子代染色體對應位置基因x¹與父代相同；重復上述操作P/2次，得到的所有子代染色體組成子代種群；

S305，對子代種群中的染色體實施變異操作，包括行政班變異操作和教學班變異操作；

S306，為每條染色體對應的課表安排教室并計算子代種群中每一條染色體對應的目標函數值；

S307，將父代種群和子代種群合并，然后從中選擇目標函數值從低到高排名前P的染色體組成新的父代種群；

S308，重復步驟S303-307，父代種群中最小目標函數值對應的染色體為最優的排課方案。

2.根據權利要求1所述的基于進化算法的走班制高中排課方法，其特征在于，步驟S301初始化大小為P的父代種群具體指的是

將染色體X中基因x包含的三個元素x¹、x²、x³置為0，將染色體X分割為若干單元，依次根據班級的課時情況對x¹賦值，并對應地將x³置為1，重復上述步驟直至產生P條染色體，組成初始化的父代種群。