[發(fā)明專利]遺傳和蟻群混合算法在組卷中的應(yīng)用方法及裝置

在審

• 申請?zhí)枺?/td>: 201710537503.6
• 申請日: 2017-07-04
• 公開（公告）號: CN107480765A
• 公開（公告）日: 2017-12-15
• 發(fā)明（設(shè)計）人: 王雪松;張中祥
• 申請（專利權(quán)）人: 北京奧鵬遠(yuǎn)程教育中心有限公司
• 主分類號: G06N3/00
• 分類號: G06N3/00;G06N3/12
• 代理公司: 北京清亦華知識產(chǎn)權(quán)代理事務(wù)所(普通合伙)11201
• 代理人: 張潤

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

本發(fā)明涉及組卷技術(shù)領(lǐng)域，特別涉及一種遺傳和蟻群混合算法在組卷中的應(yīng)用方法及裝置。

背景技術(shù)

目前，常見的組卷算法有：隨機抽取算法、基于遺傳算法的組卷和基于蟻群算法的組卷。

其中，隨機抽取組卷算法，實現(xiàn)簡單，單次組卷過程運行速度快，但是組卷重復(fù)率高；基于遺傳算法的組卷，雖然能進(jìn)行全局快速的搜索，組卷重復(fù)率低，但遺傳算法沒有反饋機制，進(jìn)行進(jìn)化時有很長時間都只在做無用的進(jìn)化和驗算，耗費時間較長；蟻群算法具有反饋機制，雖然能夠?qū)⑦M(jìn)化的信息反饋到下一輪的進(jìn)化中，但是缺點就是收斂速度慢，而且全局搜索能力較差。

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

本發(fā)明旨在至少在一定程度上解決相關(guān)技術(shù)中的技術(shù)問題之一。

為此，本發(fā)明的一個目的在于提出一種遺傳和蟻群混合算法在組卷中的應(yīng)用方法，該方法可以快速準(zhǔn)確地進(jìn)行組卷。

本發(fā)明的另一個目的在于提出一種遺傳和蟻群混合算法在組卷中的應(yīng)用裝置。

為達(dá)到上述目的，本發(fā)明一方面實施例提出了一種遺傳和蟻群混合算法在組卷中的應(yīng)用方法，包括以下步驟：利用遺傳算法進(jìn)行組卷以形成初步最優(yōu)解；將所述初步最優(yōu)解轉(zhuǎn)化為蟻群算法的初始信息素參數(shù)；利用所述蟻群算法進(jìn)行組卷；判斷是否達(dá)到預(yù)設(shè)組卷條件；如果是，則由所述蟻群算法得到最終最優(yōu)解，輸出試卷。

本發(fā)明實施例的遺傳和蟻群混合算法在組卷中的應(yīng)用方法，通過利用遺傳算法對試題庫進(jìn)行初步的全局較優(yōu)解進(jìn)行搜索，并且將得到的全局較優(yōu)解信息轉(zhuǎn)換為蟻群算法的信息素描述，最后利用蟻群算法實現(xiàn)快速精確收斂，實現(xiàn)組卷，不但充分利用了遺傳算法較強的全局搜索能力和蟻群算法較高的求解精度的優(yōu)勢，同時避免了遺傳算法局部求解能力不足、容易早熟和退化，對系統(tǒng)中反饋利用不夠的問題，也客服了蟻群算法搜索初期信息素匱乏的缺點。

另外，根據(jù)本發(fā)明上述實施例的遺傳和蟻群混合算法在組卷中的應(yīng)用方法還可以具有以下附加的技術(shù)特征：

進(jìn)一步地，在本發(fā)明的一個實施例中，所述遺傳算法的步驟包括：采用實數(shù)編碼、分段交叉、有條件生成初始種群；選擇交叉后增加適應(yīng)度檢查。

進(jìn)一步地，在本發(fā)明的一個實施例中，所述生成初始種群包括：根據(jù)總題數(shù)、題型比例、總分產(chǎn)生試卷初始種群，并且采用分組實數(shù)編碼。

進(jìn)一步地，在本發(fā)明的一個實施例中，計算適應(yīng)度的適應(yīng)度函數(shù)為：

f＝1-(1-M/N)*f1-|EP-P|*f2，

其中，f1為知識點分布的權(quán)重，f2為難度系數(shù)所占權(quán)重，EP為用戶的期望難度系數(shù)，P為試卷難度系數(shù)，N為試卷所含的題目數(shù)，M為一個個體中所有題目知識點的并集中包含個數(shù)。

進(jìn)一步地，在本發(fā)明的一個實施例中，所述蟻群算法的步驟包括：根據(jù)所述初步最優(yōu)解生成初始信息素，將m只螞蟻放置于n個節(jié)點；采用輪盤賭算法計算每只螞蟻移動到下個節(jié)點的概率，并根據(jù)選擇概率移動螞蟻到下個節(jié)點；當(dāng)所述m只螞蟻遍歷所述n個節(jié)點后，最優(yōu)圈進(jìn)行信息素增加，且所有路徑信息素更新；輸出所述最終最優(yōu)解。

為達(dá)到上述目的，本發(fā)明另一方面實施例提出了一種傳和蟻群混合算法在組卷中的應(yīng)用裝置，包括：第一組卷模塊，用于利用遺傳算法進(jìn)行組卷以形成初步最優(yōu)解；轉(zhuǎn)化模塊，用于將所述初步最優(yōu)解轉(zhuǎn)化為蟻群算法的初始信息素參數(shù)；第二組卷模塊，用于利用所述蟻群算法進(jìn)行組卷；判斷模塊，用于判斷是否達(dá)到預(yù)設(shè)組卷條件；輸出模塊，用于在達(dá)到所述預(yù)設(shè)組卷條件時，由所述蟻群算法得到最終最優(yōu)解，輸出試卷。

本發(fā)明實施例的遺傳和蟻群混合算法在組卷中的應(yīng)用裝置，通過利用遺傳算法對試題庫進(jìn)行初步的全局較優(yōu)解進(jìn)行搜索，并且將得到的全局較優(yōu)解信息轉(zhuǎn)換為蟻群算法的信息素描述，最后利用蟻群算法實現(xiàn)快速精確收斂，實現(xiàn)組卷，不但充分利用了遺傳算法較強的全局搜索能力和蟻群算法較高的求解精度的優(yōu)勢，同時避免了遺傳算法局部求解能力不足、容易早熟和退化，對系統(tǒng)中反饋利用不夠的問題，也客服了蟻群算法搜索初期信息素匱乏的缺點。

另外，根據(jù)本發(fā)明上述實施例的遺傳和蟻群混合算法在組卷中的應(yīng)用裝置還可以具有以下附加的技術(shù)特征：

進(jìn)一步地，在本發(fā)明的一個實施例中，所述遺傳算法的步驟包括：采用實數(shù)編碼、分段交叉、有條件生成初始種群；選擇交叉后增加適應(yīng)度檢查。

進(jìn)一步地，在本發(fā)明的一個實施例中，所述生成初始種群包括：根據(jù)總題數(shù)、題型比例、總分產(chǎn)生試卷初始種群，并且采用分組實數(shù)編碼。

進(jìn)一步地，在本發(fā)明的一個實施例中，計算適應(yīng)度的適應(yīng)度函數(shù)為：

f＝1-(1-M/N)*f1-|EP-P|*f2，