蟻群遺傳算法在高校智能排課系統中的應用

摘 要:大學課程表問題(UTP)是阻礙各個學校的教學資源多目標組合優化問題。它的解決不僅有助于對運籌學中多目標優化類問題的研究，而且對解決我國現階段教育中教學資源相對稀少、而學生又相對較多的現狀尤其具有現實意義。采用蟻群算法和遺傳算法混合建立高校智能排課系統，可以有效地減少搜索空間，使種群在遺傳過程按規則分區，在區間中噴灑信息素，染色適應度與種群區間交互，形成正反饋系統，驅動整個算法得到排課較優解。

關鍵詞:智能排課系統; 排課;遺傳算法;蟻群算法

中圖分類號:TN911.2; TP311.51 文獻標識碼:A

文章編號:1004-373X(2010)14-0121-03

Application of Ant-colony Genetic Algorithm in Smart Course Schedule Systems of Colleges

LI Yu-ji1， LU Cai-wu2， LIU Guan3

(1.Department of Information and Control Engineering， Xi’an University of Architecture and Technology， Xi’an 710055， China;

2. Department of Management， Xi’an University of Architecture and Technology， Xi’an 710055， China;

3. Graduate School， Xi’an University of Architecture and Technology， Xi’an 710055， China)

Abstract: Almost all the universities have been plagued with their timetable problems- teaching resources multi-objective combinatorial optimization problems for a long time. The solution of the problems will not only help the universities to study the multi-objective optimization in operations research， but also have the practical significance for solving the lack of teaching resource at the present stage and dealing with the current situation of students over the school. The smart course schedule system with the hybrid application of the ant colony algorithm and genetic algorithm can effectively reduce the search volume， so that the rule-based partition of the populations， the pheromone spray in the range of section， dyeing fitness and population interact are executed in the genetic process to form a positive feedback system， and then drive the whole algorithm to obtain the better schedule result.

Keywords: smart course schedule system; course schedule; genetic algorithm; ant-colony algorithm

當前我國高校的排課軟件系統很少，涉及到自動排課算法的系統更少，這些系統只能在排課過程中輔助工作人員進行排課，并沒有一套完善有效的自動排課策略(算法)，它決定了這些系統要么沒有真正的排課功能，要么排完課后，會出現有的課程無法安排，仍然需要工作人員進行大量的調整工作。而且大部分僅局限于輔助人工排課，并沒有任何“智能”的成分。另一方面，僅有的幾套自動排課系統卻由于產生了太多的“甩課”(因無法安排時間或者教室而不能排入課表的課程)，系統的實際使用非常困難，往往由于“甩課”太多，使后期人工調整的工作量具大。

在算法選擇過程中，如果僅采用簡單的循環遍歷各個元素以避免沖突的方法，排課效率低下;簡單的隨機散列方法，又難以有效控制找到合理方案。……