遺傳算法在排課系統(tǒng)中的應(yīng)用探討

郝劍媛

摘要：在計算機(jī)技術(shù)高速發(fā)展的今天，充分利用計算機(jī)技術(shù)提升學(xué)校排課系統(tǒng)效率。本文說明人工智能的遺傳算法的全局尋優(yōu)與收斂速度快的優(yōu)點，遵循課表編排的一般原則與教師學(xué)生需求，設(shè)計一種科學(xué)的課程編排算法，有效提升課程編排效率與合理性。

關(guān)鍵詞：課程編排;遺傳算法;基本原則;效率

現(xiàn)在的高等學(xué)校教學(xué)課表安排工作極為困難，主要由于學(xué)生數(shù)目龐大、教師每年的情況各有不同，因此每年的課表安排都需要做一定的改變，工作量極大?，F(xiàn)代排課中，主要運(yùn)用計算機(jī)算法對課程進(jìn)行安排，需要滿足大量的制約條件，并且解決教師與學(xué)生的時間沖突問題，因此如何設(shè)計一個滿足需求的課表安排算法對于高校教務(wù)管理工作的效率提升具有重要作用，此外通過科學(xué)的課程安排，可以提升學(xué)生的學(xué)習(xí)效率，方便學(xué)生安排自身的課余生活。

一、遺傳算法概述

遺傳算法是能夠并行處理的一種優(yōu)化算法，可以有效解決一些極為復(fù)雜的計算問題。其運(yùn)行機(jī)制如下：首先是對求解問題進(jìn)行編碼，再就可行區(qū)域隨機(jī)選擇一組為進(jìn)化起點，計算起點的每一個目標(biāo)函數(shù)值，即編碼適應(yīng)度。在模仿遺傳學(xué)原理，在編碼組中隨機(jī)選擇繁殖代碼，并且淘汰一部分適應(yīng)度較小的編碼組，而進(jìn)一步的繁殖中還需要運(yùn)用交叉與變異算子進(jìn)行樣本交換，在不斷重復(fù)上述選擇與繁殖的過程中，得到最滿足篩選條件的最優(yōu)解，而這就是繁殖的最后一代結(jié)果。

二、課表編排的設(shè)計思想和基本原則

（一）課表編排的基本原則

課表的安排需要遵循一定的原則，也就是代碼進(jìn)化的選擇條件。主要分為兩種：剛性約束條件與彈性約束條件，利用一定的算法，將約束條件寫入算法語句中。此外，在必要的情況下，需要進(jìn)行人工干預(yù)，以確保算法的最終運(yùn)行結(jié)果滿足排課需求，生成科學(xué)合理的課程表。在進(jìn)行課表編排時，需要注意的因素主要是：學(xué)生、教師、課程、班級、教室以及時間。

下面對課表編排的主要約束進(jìn)行介紹：第一，鋼性約束條件，這是在課表安排中都要遵守的條件，主要是以下幾點：教師在同一時間只能安排一門課程，每一個班級或者學(xué)生個體在同一個時間也只能有一門課程安排，課程的上課人數(shù)與上課教室的容量要一致，按照學(xué)分需求安排課程，不重復(fù)安排也不能遺漏。第二，彈性安排，這是為了給學(xué)生較好的學(xué)習(xí)體驗，主要有以下幾點：早上的課程不安排自習(xí)課，相鄰課程的教室盡量安排在附近，主干課程安排在上午，保證學(xué)生精力，預(yù)留選修課與班會課時間等等。

（二）課表編排的設(shè)計思想

在進(jìn)行課表編排時需要注意以下兩點：第一，便利性思想，課表安排是為了更好幫助學(xué)生進(jìn)行課程學(xué)習(xí)，因此在課程安排是要保證學(xué)生能夠及時趕到教室，可以充分利用課間時間與教師交流，而不是浪費(fèi)在相鄰課程的教室轉(zhuǎn)換中。第二，以人為本的思想，課程安排的主體因素，教師與學(xué)生都是人，因此在進(jìn)行課程安排時要充分考慮人的感受，例如，將復(fù)雜、重要、難度大的課程安排在學(xué)生與教師精神狀態(tài)都普遍較好的上午，避免在晚上等時間安排主干課程，給學(xué)生自主時間豐富大學(xué)生活。

三、遺傳算法課表編排數(shù)學(xué)原理

（一）班級課表的染色體編碼

本文的課表編排數(shù)學(xué)模型以班級為排課單位，因此需要首先明確班級課表的染色體編碼，明確班級信息表與本學(xué)期課程信息表的對應(yīng)關(guān)系，再以此為基礎(chǔ)進(jìn)行課程安排處理，例如，一周按照五天進(jìn)行基礎(chǔ)課程安排，該班級每周可以安排60個課時，一節(jié)課兩個課時，而每天有三個時段可以安排，需要將15節(jié)課程安排到這五天中去，將課程單元變量定義為Tn，則每周的課程安排T應(yīng)當(dāng)小于30個，也就是小于等于30節(jié)課，選中時間為1，未選中賦值為0，進(jìn)行初步的時段安排。為了進(jìn)一步簡化算法，可以將班級與教室作為同一個變量進(jìn)行考慮，而課程與教師也具有一一對應(yīng)的性質(zhì)，可以作為同一個變量。將五變量數(shù)學(xué)模型變?yōu)槿兞?，對這一關(guān)系進(jìn)行編碼，課時為T、教室（班級）為W、教師與課程為K，進(jìn)行進(jìn)化起點編碼編輯。要注意同一個課程教師可以在一周內(nèi)重復(fù)出現(xiàn)，但是在橫向?qū)Ρ葧r不能出現(xiàn)同時出現(xiàn)。

（二）最優(yōu)解的選擇

遺傳算法的最終結(jié)果是一個最優(yōu)解而不是唯一解，因此，如何進(jìn)行優(yōu)劣判斷是課程安排算法的一個重要難點，即適應(yīng)值函數(shù)的選取，通過適應(yīng)值來反應(yīng)課表排列的優(yōu)劣程度，作為篩選標(biāo)準(zhǔn)。類比于遺傳學(xué)中的環(huán)境適應(yīng)性，個體的適應(yīng)值越高，就更加符合課表安排的需求。對于任何一個階段的算法求解，都會出現(xiàn)滿足剛性約束條件的可行解，但是最終評價最優(yōu)解則需要在可行解中選出滿足最多彈性需求的課表，如教師不會長時間連續(xù)上課，兩節(jié)相鄰課程的教師安排相距不遠(yuǎn)，這一過程可以另設(shè)篩選函數(shù)進(jìn)行選擇，也可以直接在可行解中進(jìn)行人為干預(yù)。

結(jié)語：

本文對于課表安排主要是以班級為單位，同時也可以以教師為單位進(jìn)行課程安排，而適應(yīng)值函數(shù)的選擇則可以簡化為班級教師間距和教師連續(xù)上課時長，通過遺傳算法可以高效進(jìn)行課表安排，得到一個較為適宜的課表安排方案，希望對于教務(wù)人員工作效率提升有一定的參考價值。

參考文獻(xiàn)：

[1]馬小姝，李海蕓.遺傳算法在高校排課系統(tǒng)中的應(yīng)用研究[J].信息與電腦（理論版），2018（8）.

[2]宋岐.基于遺傳算法的排課系統(tǒng)開發(fā)探究[J].電子測試，2016（z1）：55-56.