[發(fā)明專利]一種任務(wù)安排表制定方法、裝置和介質(zhì)

在審

• 申請?zhí)枺?/td>: 201910289976.8
• 申請日: 2019-04-11
• 公開（公告）號: CN110020805A
• 公開（公告）日: 2019-07-16
• 發(fā)明（設(shè)計）人: 吳皖莉;許洋;許方園
• 申請（專利權(quán)）人: 廣東工業(yè)大學(xué)
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06N3/12
• 代理公司: 北京集佳知識產(chǎn)權(quán)代理有限公司 11227
• 代理人: 羅滿

本發(fā)明實施例公開了一種任務(wù)安排表制定方法、裝置和計算機(jī)可讀存儲介質(zhì)，根據(jù)初始化后的任務(wù)參數(shù)，建立滿足約束條件的初始任務(wù)安排表；依據(jù)預(yù)先設(shè)定的交叉概率，對各初始任務(wù)安排表進(jìn)行自交叉操作，得到多個交叉表；按照預(yù)設(shè)規(guī)則從交叉表中篩選出優(yōu)化表；判斷各優(yōu)化表是否滿足預(yù)設(shè)條件；若是，則輸出適應(yīng)度最高的優(yōu)化表；若否，則將各優(yōu)化表作為初始任務(wù)安排表，并返回按照預(yù)先設(shè)定的交叉概率，對各初始任務(wù)安排表進(jìn)行自交叉操作，得到多個交叉表的步驟。通過自交叉操作，保證了優(yōu)化過程中任務(wù)安排表的多樣性，有效的降低了任務(wù)安排表陷入局部最優(yōu)的情況發(fā)生。并且降低了數(shù)據(jù)處理量，提升了任務(wù)安排表的尋優(yōu)效率。

技術(shù)領(lǐng)域

本發(fā)明涉及遺傳算法技術(shù)領(lǐng)域，特別是涉及一種任務(wù)安排表制定方法、裝置和計算機(jī)可讀存儲介質(zhì)。

背景技術(shù)

遺傳算法是模仿自然界生物遺傳進(jìn)化過程中“物競天擇、適者生存”的原理，而開發(fā)出的一種全局優(yōu)化隨機(jī)搜索算法。傳統(tǒng)的遺傳算法已經(jīng)在工業(yè)工程和設(shè)計、經(jīng)濟(jì)管理、交通運(yùn)輸?shù)阮I(lǐng)域得到了廣泛的應(yīng)用。

在實際應(yīng)用中，常采用遺傳算法的思想解決實際問題。例如，學(xué)校課程表的安排，公司職員排班表的安排等。但是由于計算機(jī)條件的限制，遺傳算法的種群規(guī)模是有限的，并且在算法運(yùn)行過程中通常保持群體規(guī)模不變。而遺傳操作中的選擇操作往往使優(yōu)良個體呈指數(shù)級增長，隨著種群的進(jìn)化，部分高適應(yīng)度模式的指數(shù)級增長，必然使得種群中大部分個體趨于一致，種群的多樣性逐漸減小。因此，基于遺產(chǎn)算法制定任務(wù)安排表時，在進(jìn)化初期往往會出現(xiàn)大量相同的優(yōu)良樣本，這些優(yōu)良樣本趨于一致，導(dǎo)致樣本多樣性喪失，使得算法只能收斂于局部任務(wù)安排表，引起“早熟”現(xiàn)象的發(fā)生。

可見，如何降低任務(wù)安排表陷入局部最優(yōu)，是本領(lǐng)域技術(shù)人員亟待解決的問題。

發(fā)明內(nèi)容

本發(fā)明實施例的目的是提供一種任務(wù)安排表制定方法、裝置和計算機(jī)可讀存儲介質(zhì)，可以有效的降低任務(wù)安排表陷入局部最優(yōu)，提升任務(wù)安排表的尋優(yōu)效率。

為解決上述技術(shù)問題，本發(fā)明實施例提供一種任務(wù)安排表制定方法，包括：

根據(jù)初始化后的任務(wù)參數(shù)，建立滿足約束條件的初始任務(wù)安排表；

依據(jù)預(yù)先設(shè)定的交叉概率，對各所述初始任務(wù)安排表進(jìn)行自交叉操作，得到多個交叉表；

按照預(yù)設(shè)規(guī)則從所述交叉表中篩選出優(yōu)化表；

判斷各所述優(yōu)化表是否滿足預(yù)設(shè)條件；

若是，則輸出適應(yīng)度最高的優(yōu)化表；若否，則將各所述優(yōu)化表作為初始任務(wù)安排表，并返回所述按照預(yù)先設(shè)定的交叉概率，對各所述初始任務(wù)安排表進(jìn)行自交叉操作，得到多個交叉表的步驟。

可選的，所述按照預(yù)設(shè)規(guī)則從所述交叉表中篩選出優(yōu)化表包括：

從多個所述交叉表中刪除不滿足所述約束條件的交叉表，得到優(yōu)化表；

依據(jù)各優(yōu)化表的適應(yīng)度，確定出初始優(yōu)化表；

按照輪盤賭方式從剩余的優(yōu)化表中篩選出次優(yōu)表，并將所述初始優(yōu)化表和所述次優(yōu)表作為優(yōu)化表。

可選的，所述判斷各所述優(yōu)化表是否滿足預(yù)設(shè)條件包括：

判斷優(yōu)化表的自交叉操作次數(shù)是否達(dá)到預(yù)設(shè)次數(shù)。

可選的，所述判斷各所述優(yōu)化表是否滿足預(yù)設(shè)條件包括：

判斷是否存在適應(yīng)度大于或等于預(yù)設(shè)閾值的優(yōu)化表。

可選的，所述約束條件包括課程安排等式約束條件、教師滿意度約束條件、教室承載力約束條件。

本發(fā)明實施例還提供了一種任務(wù)安排表制定裝置，包括建立單元、自交叉單元、篩選單元、判斷單元、作為單元和返回單元；