一種基于改進差分算法的智能組卷方法

（云南電網公司教育培訓評價中心昆明650000）

一種基于改進差分算法的智能組卷方法

江龍曹俊豪陳祖恩張德剛

（云南電網公司教育培訓評價中心昆明650000）

智能組卷是典型的多約束組合優化問題，用戶設定針對試卷的多個限定條件，系統給出滿足約束的最優試題組合。符合實際的組卷模型與高效的算法是保證組卷質量的關鍵。結合南方電網的實際考試需求，對于差分算法收斂過早，且易收斂于局部最優等不足，提出了通過均勻搜索題庫生成初始種群，根據種群適應度的取值情況對變異率和交叉率進行動態微調。實驗表明，經過改進的差分算法在面對海量試題時仍具有較好的全局尋優能力，具有較高的組卷質量與組卷效率。

智能組卷；差分進化；智能優化

Class NumberTP391

1 引言

隨著計算機技術的發展，以組合優化算法為基礎，按照用戶要求無需人工參與自動構建一份符合考試約束的試卷已成為眾多學者研究的課題［1～2］。智能組卷大大降低了組織考試的工作量，節約了考試成本。符合實際需求的高質量試卷也為企業的人才測評工作提供了更為科學合理的工具。

目前用于計算機智能組卷的方法主要有以下兩類：一類是以隨機生成法［3］為代表，包括分段隨機抽取、集合隨機抽取、回溯試探法，此類方法實現簡單但具有較大的不確定性，難以生成高質量試卷；另一類是以進化算法為代表的組合優化算法，該類方法具有較好的魯棒性，組卷的質量相對較高，但搜索時間長、參數控制復雜。目前的研究主要是針對其不足進行改進，包括：蟻群組卷算法［4］、粒子群組卷算法［5］、遺傳算法［6］等。相較于其他算法，差分進化具有收斂速度快，穩定性好等優異性能，但標準的差分進化易于陷入局部最優和收斂過早［7］。本文針對差分進化算法的不足，結合南方電網實際的考試需求，提出了改進措施，并建立了基于該算法的智能組卷模型，實驗結果表明，經過優化的差分進化算法在性能上具有明顯的優越性。

2 智能組卷的數學描述

本文經過對南方電網考試需求的深入調研，確定試題屬性的定性指標為能力層次、素質維度、知識點、題型；定量指標為分值、難度、區分度、曝光度；試卷的評價指標為：試卷總分、試卷難度、試卷區分度、試卷曝光度［8］。其中，能力層次取值為基本能力、專業能力、管理能力；素質維度取值分別為：知識、技能、潛能。知識點、題型、分值等指標為傳統組卷指標。定量指標描述如下：試卷總分P為該試卷題目i的分值pi之和，其中n為試題總數；試卷難度為

其中，fi是試題i的區分度，W是該試卷考生考試成績的標準差。它可用于驗證區分度取值的正確性，a，b是由經驗確定的常數。試卷曝光度

其中P為試卷滿分值，di為第i道試題難度值，pi是第i道試題的分值，Yˉ是該試卷全部考生的平均得分，該值用于驗證試題難度的準確性。試卷的區分度為取值為0表示試題i在以往試卷中從未出現，gi取值為1表示試題i在以往的試卷中已出現過。基于以上約束定義，對于具有m道試題的題庫，組卷過程即是算法從迭代中選擇n道試題（m?n）。且滿足用戶設定的8個約束屬性。組卷算法的目標狀態矩陣如式（3）：

顯然，組卷問題的目標狀態并不唯一，S的每個行向量為滿足所有約束的一道試題，其列向量滿足組卷約束的整體要求，即8個指標滿足用戶指定或與用戶設定的誤差最小。

為了便于組卷算法的迭代，更好地衡量試卷指

其中，?i(i=1，2，3，4)為指標權重，且滿足標與用戶給定約束的誤差，需定義目標函數（適應度函數）F(x)。本文將定性指標作為初始選題邊界，將關鍵的定量指標作為目標函數的設計因素，這樣做在一定程度上簡化了組卷算法的復雜度。因此：分別為用戶給定的試卷分數、試卷難度、試卷區分度和試卷曝光度。

3 基于改進差分算法的組卷過程

3.1 差分進化算法改進

差分進化算法可解決具有多個約束條件的極值優化問題，是一種控制參數較少具有較高收斂速率的算法［9～10］。基于標準的DE算法，本文提出一種經過優化的的DE算法—SDE算法，首先按題型分布，在試題庫中均勻隨機產生初始種群，相較于傳統的直接隨機抽取，其初始種群覆蓋面更廣分布更均勻使得算法搜索空間更加合理，大大提高了全局尋優能力。另外，根據適應度變化，對算法參數變異率F和交叉率Cr進行反饋自適應調節，從而實現了根據上一代的搜索信息對下一代種群個體的變異方向進行微調，保證了搜索過程的效率與高精度。

3.2 組卷過程

按照改進的差分進化算法步驟，首先應產生一定規模的初始種群。題庫中共m道試題，按照題型劃分為若干區域，然后根據組卷的定性指標約束在每個區域隨機產生一個原始解構成初始種群。規則如下

其中，xi，j表示初始種群個體xi的第j個分量，N為種群個體數量，d為每個區間的長度。xi，max，xi，min分別為其取值上下界。種群矩陣如下式：

其中t取0，表示第0代即初始種群。P(0)的每一行均為組卷問題的一個可行解，可表示為xi(0)=(xi1(0)，xi2(0)，…，xin(0))T(i=1，2，…，N)，因此組卷的最終目標就是經過t代的進化，使得P(t)中產生滿足終止條件的行向量。

第二步，需進行變異操作。根據改進措施，按式（4）計算適應度，令Ft為當前變異率，fi_max，fi_avg分別是種群中最大適應度、平均適應度，則變異率F的更新計算公式為

每代種群的變異率均按上式計算，其取值范圍為F∈[0.5，1]。以更新的變異率對第t代種群P(t)中的可行解xi(0)=(xi1(0)，xi2(0)，…，xin(0))T(i=1，2，…，N)執行變異操作，所生成的新個體為

其中，i，r，s∈{1，2，…，N};i≠r≠s，xrj(t)與xsj(t)為進化種群中不同于xi(t)的兩個個體的第j個分量。

第三步，進行交叉操作。交叉率Cr的更新計算公式如下，其中fi_max，fi_avg分別為種群中最大適應度和平均適應度，Cr的取值范圍為Cr∈[0.8，1]。

對于父代個體xi(t)=(xi1(t)，xi2(t)，…，xin(t))，(i=1，2，…，N)的每個分量xij(t)產生[0，1]區間內的隨機數βi，然后根據βi與Cr的關系決定是否將變異步驟中的第j個分量代替xij(t)。具體規則如下式：

第四步，需根據適應度對種群中的個體進行選擇。先對種群中每個個體進行排序，然后采用輪盤賭法進行選擇，對于適應度較高的個體有更大的概率被選中參與進化。

第五步，達到終止條件，設定固定的進化代數或適應度滿足要求，當達到該條件時，算法終止，

4 實驗結果與分析

為驗證所提出改進差分進化算法的性能，本文以南方電網企業考試為背景，分別以不同題庫規模的《安規考試》為算例進行實驗，并與遺傳算法（GA）、標準的差分進化算法（DE）進行對比。本文算法SDE與標準差分算法初始參數為：種群規模N=100，變異率F為0.6，交叉率Cr為0.9，對DE算法來說上述參數均為定值。實驗中對兩個規模分別為2000、10000的安規考試題庫分別進行組卷。設定約束如下：能力層次為基本能力與專業能力；素質維度為知識與技能；知識點為全部知識點；題型為選擇、分析、論述；試卷總分為100分；試卷難度為0.52；試卷區分度為0.48；試卷曝光度為0.1。

在兩種不同的題庫規模下，按照上述設定進行三種算法的組卷對比試驗，每種算法各獨立運行50次，運行結果如表1所示。

表1 不同題庫規模下三種組卷算法運行結果比較

表中的成功率是指算法運行50次生成符合要求的試卷概率，最優值、最差值和標準差分別表示各個算法組卷過程中最優和最差的適應度函數值及對應的標準差。分析表1的結果可知，本文提出的SDE算法性能優異，在中等題庫規模時具有較好的尋優能力，組卷成功率高。在面對大規模題庫時，遺傳算法收斂速度慢且組卷成功率略低，標準的差分算法存在陷入局部最優，組卷成功率不夠理想等問題，相比之下，SDE在保證組卷速度的同時，提高了組卷成功率。

5 結語

本文結合南方電網的實際考試需求，建立了智能組卷數學模型，在此基礎上提出了差分進化算法的改進算法—SDE，實現了高質量高效率的智能組卷。實驗表明，該算法即便是面對大規模題庫仍具有較高的性能，這對于大型考試系統的設計具有重要的參考價值。

［1］Chen X.A Fast and Efficient Algorithm for Intelligent Test Paper Generating：Practical Applications of Intelligent Systems［M］.Berlin Heidelberg：Springer，2011：231-236.

［2］Jiang L，Zhang F.Research and Implementation of Intelligent Paper Generating System［C］//International Conference on Computer Science and Service System.Nanjing，China，2011.

［3］Li J，Wang M.Research on Intelligent Generating Test Pa-per Basedon Parallel Genetic Algorithm［C］//KESE.Shenzhen，China，2009.

［4］Hu X M，Zhang J，Chung S H，et al.An intelligent testingsystemembeddedwithanant-colony-optimization-based test composition method［J］.Systems Man& Cybernetics Part C Applications&Reviews IEEE Transactions on，2009，39（6）：659-669.

［5］Jian L V.Application of Improved PSO in Intelligent Test Paper Auto-Generation System［J］.Modern Computer，2008.

［6］Liu D，Zheng L，Wang X，et al.Research on Intelligent Test Paper Generation Based on Improved Genetic Algorithm［C］//Second Wri Global Congress on Intelligent Systems.2010：363-365.

［7］Ali M，Siarry P，Pant M.An efficient Differential Evolution based algorithm for solving multi-objective optimization problems［J］.European Journal of Operational Research，2012，217（2）：404-416.

［8］Luo J，Zhang R，Jin Y.Implementation Strategy of Several Key Issues in Intelligent Testing Paper Generation System［C］//Computational Intelligence and Software Engineering，2009.CiSE 2009.International Conference on. IEEE，2009：1-4.

［9］Shi Y，Gao H，Wu D.An improved differential evolution algorithm with novel mutation strategy［C］//Symposium on Differential Evolution，Orlando，FL，2014：20-25.

［10］Cheng S L，Hwang C.Optimal approximation of linear systems by a differential evolution algorithm［J］.Systems Man&Cybernetics Part A Systems&Humans IEEE Transactions on，2001，31（6）：698-707.

An Intelligent Test Paper Generation Method Based on Improved Differential Algorithm

JIANG LongCAO JunhaoCHEN Zu'enZHANG Degang
（The Education and Training Evaluation Center of Yunnan Power Grid Co.，Ltd，Kunming650000）

Intelligent generating test paper is a typical multi constrained combinatorial optimization problem.The user sets a number of qualified conditions for the paper.The system gives the optimal combination of test questions to meet the constraints.In line with the actual test paper model and efficient algorithm is the key to ensure the quality of the test paper.According to the actual demand of China Southern Power Grid test，for the differential algorithm premature convergence，and easy convergence to the local optimum problem，proposes a search database to generate the initial population by uniform，according to the value of the population to adapt to the dynamic fine-tuning of the mutation rate and crossover rate.Experiments show that the improved differential algorithm still has a good global optimization ability in the face of massive test questions，which has a high quality of the test paper and the efficiency.

intelligent generating test paper，differential evolution，intelligent optimization

TP391

10.3969/j.issn.1672-9722.2017.06.009

2016年12月24日，

2017年1月30日

江龍，男，博士，政工師，研究方向：電網教育培訓評價。曹俊豪，男，碩士，工程師，研究方向：電網教育培訓評價。陳祖恩，男，高級經濟師，研究方向：電網教育培訓評價。張德剛，男，博士，工程師，研究方向：電網教育培訓評價。