基于B/S 模式下的優(yōu)化遺傳算法的自動組卷系統(tǒng)設(shè)計與實(shí)現(xiàn)

王旭，吳志雄，周子勛

（長江大學(xué) 計算機(jī)科學(xué)學(xué)院, 湖北荊州，434023）

0 引言

隨著信息化時代的發(fā)展，以及全國疫情的爆發(fā)，各種云會議、網(wǎng)絡(luò)授課等網(wǎng)絡(luò)技術(shù)的出現(xiàn)，同時教育行業(yè)的自動組卷模式也成為熱點(diǎn)。

本文采用具有較高的安全性、擴(kuò)展性和兼容性等特點(diǎn)的B/S 模式架構(gòu)[1]，在普通遺傳算法的基礎(chǔ)之上對選擇算法的選擇策略進(jìn)行優(yōu)化將更好的篩選試題及交叉概率和變異概率的調(diào)整，將更好的防止“未熟就收斂，局部最優(yōu)，生成的試題質(zhì)量偏低”等問題，B/S 和優(yōu)化的遺傳算法的相互融合很好的應(yīng)用到自動組卷系統(tǒng)中[2]。

1 技術(shù)概述

1.1 B/S 模式

Browser/Server 模式，是指瀏覽器/服務(wù)器模式下的交互。B/S 相比于C/S 模式不需要安裝相應(yīng)的軟件、占用內(nèi)存小、與服務(wù)器交互時響應(yīng)速度快的特點(diǎn)，而且可跨平臺操作、業(yè)務(wù)邏輯簡單方便、易于維護(hù)和較靈活結(jié)構(gòu)等顯著優(yōu)勢，使得自動組卷系統(tǒng)交互下展現(xiàn)其特性。

1.2 JMV 體系

JMV 體系是指Java+MySQL+Vue 技術(shù)的組合實(shí)現(xiàn)。采用具有多線程、安全性等特性的Java 的Spring Boot 架構(gòu)編寫前后端服務(wù)器功能達(dá)到接收前端發(fā)送的增刪、修改、組卷操作請求命令和做出響應(yīng)返還數(shù)據(jù)；數(shù)據(jù)庫服務(wù)器開發(fā)將使用MySQL 數(shù)據(jù)庫按照難度、知識點(diǎn)、區(qū)分度、時間等約束條件建立相應(yīng)的表用以存儲試題庫；前端界面將采用具有視圖、數(shù)據(jù)、結(jié)構(gòu)分離操作簡單化、組件化、速度快等特性的Vue 框架技術(shù)，用于用戶點(diǎn)擊界面的某一操作實(shí)現(xiàn)交互功能，JMV 體系將很好適用于自動組卷系統(tǒng)中。

2 系統(tǒng)設(shè)計

2.1 總體設(shè)計

自動組卷系統(tǒng)采用三層架構(gòu)的思想，即表示層（Demonstrate）、服務(wù)層（Service）、數(shù)據(jù)層（Database）[3]。

基本設(shè)計流程：表示層是用戶登錄/注冊功能和用戶點(diǎn)擊增加或刪除、修改、查看試題等操作時將采用Ajax 異步請求服務(wù)，向服務(wù)器發(fā)送用戶的增刪改查試題等操作命令；服務(wù)層是對界面發(fā)送的增刪改查試題等操作命令進(jìn)行邏輯處理，并且根據(jù)用戶選擇的難度系數(shù)、知識點(diǎn)、時間等約束條件通過優(yōu)化的遺傳算法向試題庫進(jìn)行抽選，然后返回數(shù)據(jù)到前端；數(shù)據(jù)層是每種試題按照難度系數(shù)、知識點(diǎn)、區(qū)分度、時間等約束條件進(jìn)行存儲，接收服務(wù)器的查詢命令，返回數(shù)據(jù)[4]。如圖1 所示。

圖1 三層架構(gòu)圖

2.2 系統(tǒng)功能設(shè)計模塊

本系統(tǒng)功能結(jié)構(gòu)分為三大部分：用戶管理模塊；數(shù)據(jù)庫模塊；考試管理模塊。

(1)用戶管理模塊

用戶管理由管理員、教師、學(xué)生組成，登錄后的界面各不相同，其中管理員權(quán)限高于教師權(quán)限和學(xué)生權(quán)限。

①管理員：擁有創(chuàng)建或刪除用戶，修改密碼，用戶角色管理，系統(tǒng)菜單管理，考試管理以及試題庫的管理，維護(hù)系統(tǒng)數(shù)據(jù)等。

②教師：擁有密碼修改、試題管理、科目管理權(quán)限，例如增刪試題，自動組卷等。

③學(xué)生：擁有密碼修改、試題管理和試卷管理和自動組卷功能等。

(2)數(shù)據(jù)庫模塊

MySQL 數(shù)據(jù)庫是整個系統(tǒng)軟件的根基，是存儲數(shù)據(jù)和管理數(shù)據(jù)的庫[5]。

數(shù)據(jù)庫表的設(shè)計，數(shù)據(jù)以二維表格呈現(xiàn)的方式，用來記錄存儲數(shù)據(jù)對象的關(guān)系。本系統(tǒng)包括用戶表（user）、菜單表（menu）、角色表（role）、課程表（course）、試卷表（test）、試題表（paper）、成績表（score）等表，其中在試題表中字段列舉了每個題的難度（difficult）、區(qū)分度（distinction）、知識點(diǎn)（knowledge）、時間（time）等參數(shù)，有利于提高組卷系統(tǒng)的高效性。如表1 所示。

表1 數(shù)據(jù)表

(3)考試管理模塊

該模塊主要有試題管理、科目管理、試卷管理。用戶可對試題進(jìn)行增加、刪除、修改,還可按照難度系數(shù)、知識點(diǎn)、區(qū)分度、答題時間進(jìn)行自動組卷操作。

3 組卷策略設(shè)計

通過遺傳算法模擬自然界生物進(jìn)化的思想，“物競天擇，適者生存”的生存法則[6]，以種群為研究對象，對每個個體進(jìn)行編碼，依據(jù)預(yù)先設(shè)定的目標(biāo)函數(shù)對個體進(jìn)行評估給出相應(yīng)的適度值，通過逐代的選擇、交叉、變異，逐漸形成新的、適應(yīng)度高的種群，最后進(jìn)行解碼操作得到最大的適應(yīng)度的個體并輸出。其執(zhí)行流程如圖2 所示。

圖2 遺傳算法執(zhí)行流程圖

本文將采用優(yōu)化的遺傳算法在選擇策略上采用輪盤賭選擇法，保留當(dāng)前種群中30%最優(yōu)個體并記為oldmax，其不參與交叉變異，剩下的個體由輪盤賭法選擇出來。本文將傳統(tǒng)的只使用輪盤賭選擇算法改進(jìn)為結(jié)合最優(yōu)個體保存策略，改進(jìn)后既可以保證遺傳算法能夠收斂，又能避免提前收斂陷入局部最優(yōu)。

算法整體執(zhí)行流程如下：

(1)種群初始化

系統(tǒng)將依據(jù)試題難度系數(shù)（difficult）、區(qū)分度（discrimination）、知識點(diǎn)（knowledge）、答題時間（time）4 個參數(shù)作為約束條件，假設(shè)有n 個試題則組成一個n×4的矩陣，如(1)式所示：

D 是目標(biāo)矩陣的解，某一題 1iD=[1ia,2ia,3ia,4ia],其中0 ≤i ≤n,1ia代表難度系數(shù)，2ia代表區(qū)分度，3iD代表知識點(diǎn)，4iD代表答題時間，由上述約束條件生成試卷，構(gòu)成“染色體”編碼。

根據(jù)用戶選定的考試類型和題量、難度系數(shù)、區(qū)分度、知識點(diǎn)、答題時間等條件，隨機(jī)從試題庫中抽取符合條件的題目，生成初代的n 套卷。

(2)適應(yīng)度函數(shù)的建立

在遺傳算法中，適應(yīng)度的大小是區(qū)分種群優(yōu)劣的主要指標(biāo)，將直接影響著算法的性能[7]，本系統(tǒng)將采用4 個約束條件對適應(yīng)度進(jìn)行設(shè)計，模型如(2)式所示：

(3)遺傳操作算子

①選擇算子

選擇是指在種群中選擇好的個體，淘汰劣的個體，是生物進(jìn)化學(xué)的“優(yōu)勝劣汰”的應(yīng)用，建立在適應(yīng)度的基礎(chǔ)之上，適應(yīng)度越高，被選擇的概率就越大。通過輪盤賭和最優(yōu)適應(yīng)度保存策略對其進(jìn)行選擇操作。

假設(shè)種群由n 個個體組成，個體in的適應(yīng)度用iF表示，則in個體被選擇的概率如(3)式所示：

式中，iF指第i 個個體的適應(yīng)度值。

經(jīng)過輪盤賭選擇后，保存30% 的最優(yōu)個體記為oldmax，并且不參與個體的交叉變異操作，最后再替換掉適應(yīng)度低于oldmax 的個體，較好的解決了“收斂快和局部收斂”的問題。

②交叉算子

交叉是指模擬生物進(jìn)化的過程，從中獲取優(yōu)良個體，產(chǎn)生新的下一代個體，交叉過程是按照一定的交叉概率在相應(yīng)庫中兩兩隨機(jī)交叉，本系統(tǒng)采用兩點(diǎn)交叉方式，則交叉過程如圖3 所示。

圖3 交叉過程圖

隨機(jī)交叉方式，容易導(dǎo)致交叉后會出現(xiàn)重復(fù)的題目，使得算法早熟早收斂。為了防止重復(fù)事件的發(fā)生，通過控制交叉概率cP，一般選擇0.4-0.99，本系統(tǒng)使用0.5 的交叉概率，用以保證題目的不重復(fù)性。

③變異算子

變異是指生物模擬生物個體突變的過程，通過變異概率mP隨機(jī)的反轉(zhuǎn)某位二進(jìn)制數(shù)值，則交叉過程如圖4 所示。

圖4 變異過程圖

變異過程是一種局部搜索，為了防止因選擇和交叉導(dǎo)致的信息丟失，保持種群的多樣性[8]，變異概率一般選擇0.0001～0.1，本系統(tǒng)使用0.01 的變異概率，防止出現(xiàn)未熟就收斂的現(xiàn)象。

改進(jìn)后的遺傳算法很大程度的保證了染色體中的優(yōu)良個體，很大程度的防止早熟，局部最優(yōu)等問題，最終通過不斷的選擇、交叉、變異達(dá)到預(yù)定的適應(yīng)度或者迭代次數(shù)，滿足最高的適應(yīng)度值的個體即為最優(yōu)解。

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

4.1 用戶管理實(shí)現(xiàn)

系統(tǒng)初始登錄界面，新用戶可選擇教師或?qū)W生來注冊系統(tǒng)，然后可登錄系統(tǒng)，已注冊用戶可直接登錄，成功后進(jìn)入主界面，如圖5 所示。管理員擁有最高權(quán)限，可點(diǎn)擊用戶管理實(shí)現(xiàn)對教師和學(xué)生信息的查找和修改，另外還可以實(shí)現(xiàn)角色菜單管理功能。教師或?qū)W生點(diǎn)擊系統(tǒng)管理的密碼修改按鈕，可在輸入框中輸入舊密碼，再輸入新密碼，確認(rèn)密碼，則可實(shí)現(xiàn)密碼修改。如圖6 所示。

圖5 登錄/注冊界面

圖6 教師界面

4.2 考試管理實(shí)現(xiàn)

考試管理包括了3 大部分，即試題管理、科目管理、試卷管理，教師和學(xué)生可在試題界面操作向服務(wù)器發(fā)送試題增刪修改操作命令，服務(wù)器響應(yīng)并傳輸相應(yīng)數(shù)據(jù)[9]，本系統(tǒng)通過使用優(yōu)化的遺傳算法進(jìn)行組卷，教師或?qū)W生在試卷管理界面輸入難度系數(shù)（0-1，數(shù)字越大，難度越高），區(qū)分度（0-1，數(shù)字越大，難度越高），選擇知識點(diǎn)，再輸入答題時間，如圖7所示，即可組出一套試卷，并且可打印試卷，如圖8所示。

圖7 自動組卷界面圖

圖8 試卷生成界面圖

■4.3 試題庫管理實(shí)現(xiàn)

考試系統(tǒng)需要不斷的填充題目以完善題庫，保證測試的有效性，對試題進(jìn)行必不可少的增添和修改功能。實(shí)現(xiàn)了試題按照題目、答案、難度、知識點(diǎn)、區(qū)分度、時間等參數(shù)添加相應(yīng)試題，存儲到MySQL 數(shù)據(jù)庫中并且定期檢查和維護(hù)試題。

5 結(jié)束語

本文的自動組卷系統(tǒng)設(shè)計對傳統(tǒng)遺傳算法的選擇、交叉和變異策略進(jìn)行改進(jìn)，很大程度上防止“未熟就收斂，局部最優(yōu)，生成的試題質(zhì)量偏低”等問題，較好的根據(jù)用戶需求做到相應(yīng)要求的試卷，實(shí)現(xiàn)組卷速度快且成卷質(zhì)量高的優(yōu)點(diǎn)，但還無法做到根據(jù)用戶動態(tài)的調(diào)整難度系數(shù)，還需一定改進(jìn)，總體上大大減少了教師在出卷時消耗的時間和精力，為教師和學(xué)生提供了方便。