基于改進(jìn)遺傳算法的智能組卷系統(tǒng)設(shè)計(jì)

王宣策　歐陽鑫玉

摘要：針對(duì)大學(xué)課程考核及題庫建設(shè)需求，設(shè)計(jì)并實(shí)現(xiàn)了一種基于改進(jìn)遺傳算法的智能組卷系統(tǒng)。系統(tǒng)采用Word文檔保存試題的內(nèi)容和答案;在組卷策略上采用了改進(jìn)遺傳算法，詳細(xì)設(shè)計(jì)了組卷問題的染色體結(jié)構(gòu)、適應(yīng)度函數(shù)和遺傳操作等，克服了傳統(tǒng)隨機(jī)組卷方法存在的局限性，科學(xué)合理地解決了智能組卷問題。通過測試后發(fā)現(xiàn)，本智能組卷系統(tǒng)可操作性強(qiáng)、組卷效率高，可以顯著提高組卷的質(zhì)量，完全能夠滿足課程考核的實(shí)際需求。

關(guān)鍵詞：智能組卷;遺傳算法;系統(tǒng)設(shè)計(jì);題庫建設(shè)

中圖分類號(hào)：TP11; TP391? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）02-0065-03

Abstract： Aiming at the needs of university course assessment and item bank construction， an intelligent test paper generating system Based on improved genetic algorithm is designed and implemented. The system uses Word document to save the contents and answers of the test questions， and adopts improved genetic algorithm to organize the test papers. The chromosome structure， fitness function and genetic operation of the test paper problem are designed in detail， which overcomes the limitations of the traditional random test paper generation method and solves the problem of intelligent test paper generation scientifically and reasonably. After testing， it is found that the intelligent test paper generating system has strong operability， high efficiency， can significantly improve the quality of test paper， and can fully meet the actual needs of curriculum assessment.

Key words： intelligent test paper generating; genetic algorithm; system design; item bank construction

1 概述

隨著信息時(shí)代的發(fā)展，計(jì)算機(jī)已成為了人們?nèi)粘Ｉ詈凸ぷ鞑豢苫蛉钡墓ぞ?，在大學(xué)教學(xué)改革過程中，也成為重要的教學(xué)輔助工具和教學(xué)管理手段。隨著高校教學(xué)改革不斷推進(jìn)，利用計(jì)算機(jī)進(jìn)行大學(xué)課程的題庫系統(tǒng)建設(shè)得到了廣泛的重視和應(yīng)用，各種類型的題庫及其應(yīng)用系統(tǒng)在日常教學(xué)管理中正發(fā)揮著越來越重要的作用。

在題庫系統(tǒng)建設(shè)過程中，如何保障生成的試卷能最好地滿足教學(xué)評(píng)價(jià)目標(biāo)要求，是整個(gè)系統(tǒng)設(shè)計(jì)的一個(gè)難點(diǎn)和重點(diǎn)問題。傳統(tǒng)的題庫系統(tǒng)一般采用人工或隨機(jī)組卷方法，在題庫規(guī)模越大越大的情況下，很難保證所形成的試卷在質(zhì)量、難度、廣度等方面達(dá)到滿意的效果;尤其是在約束性條件越多的情況下，越難組成滿意的試卷。當(dāng)前比較流行的組卷方法主要有回溯組卷算法、粒子群算法和遺傳算法等[1-4]。回溯組卷算法是基于隨機(jī)抽取算法，粒子群算法是通過模擬鳥群覓食行為而發(fā)展起來的一種基于群體協(xié)作的隨機(jī)搜索算法[5-6]，這兩種算法的缺點(diǎn)是隨機(jī)性較強(qiáng);而遺傳算法是一種自適應(yīng)全局優(yōu)化搜索算法，具有全局優(yōu)化強(qiáng)的特點(diǎn)，為多目標(biāo)的優(yōu)化問題提供了更好的解決方法[7]。

因而，本文將以《土木工程施工》課程為例，針對(duì)課程考核目標(biāo)和要求，在遺傳算法的基礎(chǔ)上，通過適當(dāng)改進(jìn)后形成優(yōu)化組卷策略，設(shè)計(jì)并實(shí)現(xiàn)一個(gè)大學(xué)課程智能組卷系統(tǒng)。

2 需求分析

本項(xiàng)目的目標(biāo)是開發(fā)一個(gè)通用、易用、高效的試題庫管理及自動(dòng)組卷系統(tǒng)，要求圍繞如何實(shí)現(xiàn)科目與題型的自定義、試題的重復(fù)檢測、智能組卷等關(guān)鍵問題進(jìn)行研究和設(shè)計(jì)。

2.1 系統(tǒng)主界面功能需求

要求主界面簡潔美觀，可以按照用戶的要求隱藏或者顯示，可以添加四個(gè)按鈕供用戶快速操作，分別是“隱藏章節(jié)目錄”“隱藏功能區(qū)”“隱藏答案”“隱藏考點(diǎn)面板”。此外，還需在主界面下方添加狀態(tài)欄，顯示當(dāng)前打開的題庫和登錄的用戶名。

2.2 組卷系統(tǒng)管理功能需求

為了滿足不同課程需要，本系統(tǒng)要求提供章節(jié)管理、考點(diǎn)管理、題型管理、試卷分類、組卷設(shè)置、試卷模板管理，使用戶能夠自定義題庫結(jié)構(gòu)。各個(gè)管理模塊界面左側(cè)采用樹形控件顯示題庫的結(jié)構(gòu)信息，并提供增加、刪除、上移、下移、導(dǎo)入、導(dǎo)出等功能按鈕。在章節(jié)管理中，提供章節(jié)導(dǎo)入導(dǎo)出功能。

2.3 試題模塊功能需求

系統(tǒng)應(yīng)提供單題錄入功能，在錄入時(shí)用戶需把試題的章節(jié)信息、難度、類型、分值、考察的知識(shí)點(diǎn)以及試題的題目、簡要答案、詳細(xì)答案進(jìn)行錄入，點(diǎn)擊保存即可把試題錄入到系統(tǒng)中。為了讓方便客戶管理試題，系統(tǒng)應(yīng)提供批量刪除、批量修改、重復(fù)檢測、轉(zhuǎn)移試題等功能。

2.4 組卷的需求

系統(tǒng)的核心是要求具有智能組卷功能。通過實(shí)際分析，本系統(tǒng)采用基于題目編號(hào)編碼的改進(jìn)遺傳算法進(jìn)行智能組卷。利用該功能，用戶確定試卷整體架構(gòu)后，系統(tǒng)會(huì)給出默認(rèn)的組卷約束條件，用戶也可以對(duì)約束條件中的試題總分、難度系數(shù)、考察的知識(shí)點(diǎn)進(jìn)行重新設(shè)置，然后點(diǎn)擊開始抽題，系統(tǒng)便可以按照設(shè)置和模板自動(dòng)組成若干套試卷。

2.5 瀏覽需求

瀏覽分為三種瀏覽方式，分別是試題瀏覽、收藏夾瀏覽和回收站瀏覽。在試題瀏覽時(shí)，必須先選中一個(gè)章節(jié)，然后可以一次瀏覽該節(jié)的所有試題。在瀏覽收藏夾和回收站時(shí)，會(huì)先判斷是否為空，如果為空則提示為空，否則則打開對(duì)應(yīng)的題目。系統(tǒng)應(yīng)提供瀏覽錄入卷和試卷庫的功能，并可以對(duì)試卷進(jìn)行屬性查看和試卷導(dǎo)出。

2.6 權(quán)限控制的需求

要求在用戶設(shè)置里面，根據(jù)用戶級(jí)別的不同賦予不同的系統(tǒng)權(quán)限，對(duì)系統(tǒng)進(jìn)行精細(xì)化的管理，同時(shí)也能保障系統(tǒng)的安全性，在用戶設(shè)置里面，可以對(duì)用戶信息進(jìn)行管理，同時(shí)可以對(duì)系統(tǒng)中的每一種權(quán)限進(jìn)行管理。

2.7 系統(tǒng)設(shè)置的需求

在系統(tǒng)設(shè)置中，系統(tǒng)需提供試題難度的五級(jí)模型，用戶可以自定義每一級(jí)的難度名稱，并能自定義系統(tǒng)的標(biāo)題，給用戶最大的自由。此外，用戶還可以自由的設(shè)置遺傳算法的初始化參數(shù)，以及開機(jī)自啟動(dòng)等功能。

3 總體設(shè)計(jì)

根據(jù)需求分析，本智能組卷系統(tǒng)的設(shè)計(jì)內(nèi)容主要包括如下16個(gè)方面：

1） 系統(tǒng)主界面的設(shè)計(jì);

2） 新建題庫;

3） 最近打開;

4） 章節(jié)管理;

5） 考點(diǎn)管理;

6） 題型管理;

7） 試卷分類;

8） 組卷設(shè)置;

9） 單題錄入;

10） 重復(fù)檢測;

11） 轉(zhuǎn)移試題;

12） 批量刪除和批量修改;

13） 智能組卷的設(shè)計(jì)與實(shí)現(xiàn);

14） 查看試卷庫和錄入卷;

15） 收藏夾和回收站的實(shí)現(xiàn);

16） 系統(tǒng)設(shè)置和用戶設(shè)置。

4 基于改進(jìn)遺傳算法的智能組卷設(shè)計(jì)

本系統(tǒng)的智能組卷采用改進(jìn)遺傳算法來實(shí)現(xiàn)，具體算法流程如圖1所示。

4.1 染色體編碼方式設(shè)計(jì)

遺傳算法首先要進(jìn)行染色體的編碼設(shè)計(jì)，其實(shí)就是構(gòu)建屬于自己的一套編碼方案。在一般情況下，使用二進(jìn)制編碼對(duì)特征值進(jìn)行抽象比較普遍，但是對(duì)于組卷系統(tǒng)的實(shí)際情況來說，這樣的設(shè)計(jì)會(huì)導(dǎo)致基因序列會(huì)非常的冗余，而且在編碼和解碼的過程中耗費(fèi)大量不必要的時(shí)間，從而導(dǎo)致系統(tǒng)的運(yùn)行效率非常的低。因此，本系統(tǒng)在設(shè)計(jì)的時(shí)候，每道題目的命名用一個(gè)實(shí)數(shù)進(jìn)行命名，并且保存到試題的屬性中，這樣就可以把試題的名字作為染色體的基因，然后許多的試題構(gòu)成一個(gè)染色體，每一個(gè)染色體就代表一套試卷，他們建立了一種對(duì)應(yīng)關(guān)系，并且把相同題型的試題編號(hào)放在染色體的相鄰位置，以便于后期進(jìn)行各種分段操作。

4.2 初始化種群設(shè)計(jì)

初始化種群的時(shí)候涉及種群的大小，這個(gè)參數(shù)應(yīng)該在系統(tǒng)中有相應(yīng)的設(shè)置，用戶可以根據(jù)自己的需要設(shè)置為自己想要的種群大小，這個(gè)參數(shù)的大小直接影響算法最終的結(jié)果，設(shè)置一個(gè)適當(dāng)?shù)闹禃?huì)讓結(jié)果更加的合理。另外，為了讓算法盡快地收斂，在初始化種群的時(shí)候，應(yīng)該讓個(gè)體滿足一些約束條件，本系統(tǒng)在初始化種群的過程中，讓每個(gè)個(gè)體滿足題型、題目的數(shù)量和試卷的總分這三個(gè)約束條件，這樣在后期的遺傳操作過程中，可以減少迭代的次數(shù)，提高系統(tǒng)的效率。

4.3 適應(yīng)度函數(shù)設(shè)計(jì)

在遺傳算法中，通常用適應(yīng)度來表示個(gè)體的好壞，一個(gè)個(gè)體的適應(yīng)度越高，表明它的進(jìn)化過程中更加的適應(yīng)環(huán)境。而適應(yīng)度的計(jì)算要根據(jù)具體的適應(yīng)度函數(shù)來決定，所以適應(yīng)度函數(shù)是設(shè)計(jì)是決定遺傳算法最終結(jié)果的關(guān)鍵。所謂的適應(yīng)度，就是判斷種群中的個(gè)體和預(yù)期想要的結(jié)果的一致性，因?yàn)樵诔跏蓟臅r(shí)候，已經(jīng)達(dá)到了一些要求，所以在后期判斷的時(shí)候主要考慮難度系數(shù)是否滿足設(shè)置的要求，還要把知識(shí)點(diǎn)的涵蓋范圍作為一個(gè)參考，總的來說，就是難度系數(shù)盡量和預(yù)期的一致，知識(shí)點(diǎn)涵蓋的范圍越廣越好。

通過分析，可以設(shè)計(jì)出組卷系統(tǒng)的適應(yīng)度函數(shù)。例如用戶希望得到的試卷考察[N]個(gè)知識(shí)點(diǎn)，但是把個(gè)體中所有題目含有的知識(shí)點(diǎn)放在一起，總數(shù)是有[M]個(gè)，則這套試卷的知識(shí)點(diǎn)分布率為[MN]。用戶希望試卷的難度系數(shù)為[P]，一個(gè)個(gè)體經(jīng)過計(jì)算后的難度系數(shù)為[p]，則適應(yīng)度函數(shù)如下：

其中，[k1]為知識(shí)點(diǎn)在評(píng)價(jià)適應(yīng)度中的比例系數(shù)，[k2]表示難度系數(shù)在評(píng)價(jià)適應(yīng)度中的比例。當(dāng)[k1=0]時(shí)表示試題難度系數(shù)占有全部的權(quán)重，不考慮知識(shí)點(diǎn)的影響，當(dāng)[k2=0]時(shí)表示適應(yīng)度只考慮知識(shí)點(diǎn)。

4.4 遺傳算子的設(shè)計(jì)

（1） 選擇算子。在遺傳算法中，肯定有的個(gè)體要被淘汰，淘汰就是通過選擇進(jìn)行的，在這個(gè)過程中被選中則留下，否則就不能進(jìn)行下一步的操作。選擇算子從當(dāng)前進(jìn)化群體中選擇適應(yīng)度高的個(gè)體，交叉算子只能從選擇算子選擇的個(gè)體中選取個(gè)體執(zhí)行交叉操作。遺傳算法中有很多的選擇策略，本系統(tǒng)采用了基本遺傳算法的選擇策略——輪盤賭方法，其具體設(shè)計(jì)為：通過適應(yīng)度函數(shù)計(jì)算出每個(gè)個(gè)體的適應(yīng)度[Fi]，種群的大小為[N]，則每個(gè)個(gè)體被保留的幾率為[Fii=0NFi]。

（2） 交叉算子。由于在設(shè)計(jì)編碼方案時(shí)每道題目的文件名稱作為一個(gè)基因，文件名稱都是一個(gè)整數(shù)，而且按照題型的不同分了幾個(gè)部分，所以在進(jìn)行交叉時(shí)可以在每一段選擇一點(diǎn)交叉，這樣從整體來看的話染色體就實(shí)現(xiàn)了在多個(gè)地方交叉。交叉的具體步驟：每兩個(gè)染色體組合為一對(duì)，然后隨機(jī)產(chǎn)生一個(gè)數(shù)[r]，交換[r]位置及之后的共兩道題目，這樣就得到了下一代，但是還要判斷總分是否還能滿足要求。交叉后可能會(huì)使新生成的子代包含題號(hào)一樣的情況，此時(shí)可以將一樣的題號(hào)中的一個(gè)換成沒有出現(xiàn)過的題號(hào)，這樣就可以滿足要求了。

（3） 變異算子。在遺傳算法中，變異概率都比較小，考慮到這種情況，本系統(tǒng)就不再在每一段上都進(jìn)行變異，而是隨意選擇一個(gè)片段中的一個(gè)基因進(jìn)行變異。變異的步驟如下：在染色體長度范圍內(nèi)產(chǎn)生一個(gè)隨機(jī)數(shù)P，這個(gè)數(shù)就是基因?qū)⒁儺惖奈恢?，然后從試題庫所有題目中找一個(gè)各個(gè)屬性值和[P]位置基因差不多的題目替換掉即可。

5 系統(tǒng)實(shí)現(xiàn)

本智能組卷系統(tǒng)以課程題庫數(shù)據(jù)為基礎(chǔ)，采用C#語言開發(fā)，開發(fā)環(huán)境是Visual Studio 2017：社區(qū)版，運(yùn)行環(huán)境是Windows XP以上。

系統(tǒng)登陸界面如圖2所示;系統(tǒng)主界面如圖3所示;組卷成功界面如圖4所示。

本系統(tǒng)實(shí)現(xiàn)了以Word形式存儲(chǔ)的智能組卷功能，能夠增加、刪除、編輯課程目錄和對(duì)應(yīng)的題目;根據(jù)組卷設(shè)置自動(dòng)生成一套試卷;方便快捷地完成目錄導(dǎo)入和導(dǎo)出，還提供了重復(fù)檢測的功能，能夠準(zhǔn)確定位重復(fù)的試題。

6 結(jié)束語

本文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)智能組卷系統(tǒng)。該系統(tǒng)提供了便捷的工具欄和信息豐富的狀態(tài)欄，使操作更人性化;開發(fā)遵循了傳統(tǒng)Windows應(yīng)用的布局方式;采用Word文檔保存試題的內(nèi)容和答案，解決了課程題目中的圖片、表格、公式等傳統(tǒng)組卷系統(tǒng)很難解決的問題。在組卷策略上采用了改進(jìn)遺傳算法，解決了科學(xué)合理的智能組卷問題。該系統(tǒng)可操作性強(qiáng)、組卷效率高，顯著提高了組卷的質(zhì)量，很好地滿足了用戶的實(shí)際需求。

參考文獻(xiàn)：

[1] 賀建英， 王光瓊， 唐青松. 一種基于遺傳算法的智能組卷策略優(yōu)化研究[J]. 計(jì)算機(jī)與數(shù)字工程，2019， 47（1）：130-135.

[2] 郭竑暉. 智能組卷試題庫系統(tǒng)的設(shè)計(jì)與開發(fā)探討[J].時(shí)代農(nóng)機(jī)， 2017， 44（10）：128.

[3] 高凌潔. 基于改進(jìn)遺傳算法的智能組卷系統(tǒng)設(shè)計(jì)[J]. 計(jì)算機(jī)與數(shù)字工程，2017， 45（10）：1910-1913.

[4] 李川，楊俊清，張少茹. 一種基于回溯試探法組卷的優(yōu)化算法[J].兵工自動(dòng)化，2019，38（2）：60-63.

[5] 崔星華，郭秀娟. 粒子群算法在智能組卷中的應(yīng)用[J]. 吉林建筑工程學(xué)院學(xué)報(bào)， 2013，30（6）：46-48.

[6] 王菲. 基于改進(jìn)粒子群算法的組卷系統(tǒng)[J]. 信息與電腦， 2017，（14）：55-61.

[7] 馬小姝，李宇龍，嚴(yán)浪. 傳統(tǒng)多目標(biāo)優(yōu)化方法和多目標(biāo)遺傳算法的比較綜述[J]. 電氣傳動(dòng)自動(dòng)化， 2010，32（3）：48-50.

【通聯(lián)編輯：梁書】