基于自適應果蠅優化算法的平行試卷自動生成

王鳳蕊，王文宏，董金新

（1.聊城大學 傳媒技術學院，山東 聊城252059；2.聊城大學 計算機學院，山東 聊城252059）

0 引 言

隨著計算機輔助考試在教育領域應用的逐步深入，平行試卷自動生成成為教育考試管理部門命題時一種新的實踐需求［1－3］。平行試卷自動生成不但可以節省人力物力，而且可有效提高試卷生成效率、質量和安全性。計算復雜性理論表明，平行試卷自動生成問題具有多約束性、非線性、大規模性、多目標性等特征，屬于復雜的NP－hard組合優化問題［3－5］。因此，高效優質的平行試卷生成算法是求解平行試卷自動生成問題的關鍵。

目前，國內外有關組卷算法的研究主要集中在生成單套試卷的算法方面，有關的算法主要有兩類：一類是隨機組卷算法，另一類是智能組卷算法，如遺傳算法［6］、模擬退火算法［7］、粒子群算法［8］等。關于平行試卷自動生成的研究還不多見，主要有文獻 ［3］給出了有效的高等教育自學考試平行試卷平行性控制策略，文獻 ［2，4，5］給出了解決平行試卷自動生成的智能優化算法，但算法由于缺少有效的局部搜索策略或采用比較簡單的0－1編碼方案，組卷效率和組卷質量尚需進一步改進。

近來，受果蠅覓食行為的啟發，文獻 ［9］提出一種全局優 化 算 法－－果 蠅 優 化 算 法 （fruit fly optimization algorithm，FOA）。該算法具有控制參數少、流程簡單，容易理解和實現等優點，目前已被成功用于求解Web服務滿意度分析、連續函數優化和自動化倉庫揀選作業調度等問題［10－12］。當前國內對果蠅優化算法的研究才剛剛開始，相關研究主要針對連續空間的函數優化問題展開，而對離散空間的組合優化問題研究還較少。

本研究將果蠅優化算法用于求解平行試卷自動生成問題。針對基本果蠅優化算法求解該問題時極易陷入局部最優的特點，設計了具有自適應變異嗅覺搜索算子的改進果蠅優化算法。基于不同規模題庫的仿真結果表明，自適應的變異嗅覺操作有效地平衡了算法的全局和局部搜索能力，且與基本微粒群算法相比，自適應的果蠅優化算法能更有效地解決平行試卷自動生成問題。

1 平行試卷自動生成問題模型

假設題庫TB＝ ｛Q1，Q2，…，QN｝有N 道試題，所有試題與M 個知識點C＝｛C1，C2，…，CN｝相關。平行試卷自動生成即計算機根據用戶的平行組卷需求 （如平行試卷份數、試卷結構、試卷總分、考試時間、難度等），利用組卷算法從題庫TB 中挑選一系列試題并生成K 套平行試卷，且K 套平行試卷之間均無重題［2］。

1.1 試題屬性和組卷需求變量定義

itemID，試題的編號；

discrii，1≤i≤N，試題Qi的區分度；

difi，1≤i≤N，試題Qi的難度；

timei，1≤i≤N，試題Qi的預期作答時間；

relaij，1≤i≤N，1≤j≤M，試題Qi與知識點Cj的關聯度；

K，用戶要求的平行試卷套數；

Dif，用戶要求的平行試卷難度；

hj，1≤j≤M，用戶要求的每套平行試卷中所有試題與知識點Cj的關聯度權重下限；

timeupper，用戶要求的平行試卷的預期考試時間上限；

t

imelower，用戶要求的平行試卷的預期考試時間下限；

S，用戶要求的每套平行試卷中的試題總數。

1.2 問題模型

目標函數

目標函數應同時滿足如下約束條件

從上述問題模型可以看出，平行試卷自動生成問題目標是從題庫中挑出一系列試題并組成K 套滿足多個約束條件的平行試卷集，且所有平行試卷之間的區分度差異及平行試卷與用戶期望的試卷難度差異均最小。本研究采用目標加權的方法將多目標優化問題轉化成一個單目標優化問題，其中，權系數α和β均為0.5。如果試題Qi在第k套平行試卷中，則決策變量xik＝1，否則xik＝0。式（4）表示每套平行試卷中所有試題與每一個概念的關聯度權重不低于用戶的組卷需求。式（5）和式（6）表示平行試卷的考試時間應在用戶要求的考試時間范圍內。式 （7）表示所有平行試卷之間無重題。式（8）要求每套平行試卷均包含S道試題。

2 基于自適應果蠅優化的平行組卷算法

2.1 基本果蠅優化算法

果蠅是一種具有非常豐富的嗅覺和視覺器官的生物，在覓食過程中，首先利用嗅覺器官飛近食物源，然后利用視覺器官發現食物和果蠅群聚集位置，并飛向食物和果蠅群［9］。受果蠅覓食行為的啟發，基本果蠅優化算法的優化流程如下：

步驟1 初始化算法參數，如果蠅種群規模，最大進化代數等。

步驟2 在問題搜索空間隨機初始化果蠅群位置。

步驟3 基于嗅覺搜索在果蠅群位置周圍隨機產生果蠅群。

步驟4 評價每一個果蠅的味道濃度，找出味道濃度最佳的果蠅，并記錄其位置坐標以更新當前果蠅群位置。

在介入PPP項目前，應對項目的合法、合規性進行充分的識別，關注政策動態變化，規避合規風險。現階段至少應保證以下方面的合規性：

步驟5 果蠅群利用視覺搜索飛向味道濃度最佳的果蠅個體。

步驟6 算法迭代尋優，并判定是否滿足結束條件。如果滿足結束條件，算法結束；否則，繼續步驟3。

從上述流程可以看出，基本果蠅優化算法在整個迭代尋優過程中僅向當前最優個體學習，即一旦發現當前最優果蠅個體，果蠅群將會快速聚集到最優個體位置區域。若該個體并非是全局最優，算法極易陷入局部最優，引發早熟收斂問題。

2.2 自適應果蠅優化組卷算法設計

為克服基本果蠅優化算法易陷入局部最優的缺陷，本研究結合平行試卷自動生成問題模型，研究并提出一種具有自適應變異機制的果蠅優化智能平行組卷算法。

2.2.1 編碼和解碼

果蠅群中的每個果蠅個體代表平行試卷自動生成問題的一個候選解。假設果蠅種群的規模為NP，且NP 在整個算法的執行過程中保持不變。在算法進化過程中，第G 代果蠅群的第i （i＝1，2，…，NP）個果蠅個體用兩個D 維向量＝，…，）和＝，…）表示。其中，每一對元素和（j＝1，2，…，D）對應一個決策變量，其取值范圍為 （－∞，∞）的實數。

解碼操作用于將果蠅個體映射為問題的解。對于平行試卷自動生成問題，果蠅個體的每一維決策變量代表題庫中的一個題號，果蠅個體到問題解的解碼設計如下：

根據編碼解碼設計，在將果蠅個體味道濃度判定向量映射為問題解時，要求∈［0，1）。如果［0，1），將執行2.2.5設計的修復操作使其滿足。

式中：函數floor（）實現浮點數到整數的轉換，item－Num——題庫中試題的總數。

解向量tn是由K 段長度為s 的題號組成，其中每一段表示一套試卷。

2.2.2 果蠅群位置初始化

果蠅群初始位置xPosition0和yPosition0在搜索空間內隨機初始化，方法如下

其中，j＝1，2，…，D，函數rand（）產生區間 （－∞，∞）上均勻分布的隨機數。

2.2.3 具有自適應變異機制的嗅覺搜索

基本果蠅優化算法是為求解連續優化問題而設計，其嗅覺搜索算子適用于連續決策變量。基本果蠅優化算法在求解平行試卷自動生成問題時，由于局部尋優能力有限，在進化中后期容易出現早熟收斂。因此，為更好地平衡算法的全局搜索與局部搜索能力，本文對基本果蠅優化算法的嗅覺搜索算子進行了改進，增加了如式 （14）～式 （16）所示的自適應變異機制

其中，i＝1，2，…，NP，j＝1，2，…，D，α 為用戶要求的最小變異概率常數，函數［0，1］和rand2j［0，1］用于產生區間 ［0，1］上均勻分布的隨機數，和p為變異控制參數的最大值和最小值 （本研究中＝1，＝0），mT 為算法總的運行時間，rT 為算法的運行時間，pm為變異控制參數，其初始值等于。

自適應變異參數pm使得果蠅優化算法在進化初期，以較大的變異概率對果蠅個體進行擾動，以增強算法的全局搜索能力，在后期，當算法接近可行解區域時，逐步降低變異率，以實現在保留個體優良信息的同時，進行更為精細的局部搜索。

2.2.4 視覺搜索

根據目標函數評價每個果蠅的味道濃度，并找出味道濃度最佳的個體，并通過式 （17）和式 （18）更新果蠅種群位置

其中，bestIndex 為最優果蠅個體在果蠅種群中的位置下標。

2.2.5 修復操作

其中，函數randj［0，1］產生 ［0，1］上均勻分布的隨機數。

2.3 自適應果蠅優化組卷算法流程

步驟1 算法初始化。按照式 （12）和式 （13）初始化果蠅初始種群，并初始化算法參數種群規模NP、果蠅個體維度D、變異控制參數pm、算法總的運行時間mT 及用戶要求的最小變異概率常數α。

步驟2 自適應變異機制的嗅覺搜索產生果蠅群，即根據式 （14）～式 （16）生成每個果蠅個體。

步驟3 根據式 （19）和式 （20）對種群個體進行修復操作。

步驟4 視覺搜索。根據平行試卷自動生成問題目標函數 （式 （1））評價每個果蠅個體的味道濃度，找到味道濃度最佳的果蠅個體，并根據最佳果蠅個體更新果蠅群位置，并使果蠅群飛向該位置。

步驟5 算法迭代尋優，并判斷算法是否滿足結束條件，如果滿足，則輸出結果；否則，返回步驟2。

3 實驗與評價

為驗證本文所提出算法的優化性能，根據平行試卷自動生成問題模型，分別隨機生成了5個不同規模的仿真題庫，所有仿真題庫均具有相同的題庫結構，且每個題庫均與20個知識點相關。實驗所用算法均采用C 語言編程實現，運行環境為配備2.7GHz CPU、2GRAM 和Windows 2008server（32bite）操作系統的PC機。

3.1 與基本微粒群算法的組卷性能比較

平行組卷需求：生成3套平行試卷，每套試卷包含60道題，平行試卷難度為0.5，考試時間限制為80～100分鐘。

基 本 微 粒 群 算 法 （particle swarm optimization algorithm，PSO）參 數 為w ＝0.5，c1＝2.05，c2＝2.05，MAXV＝1.5，NP＝20，D＝180。自適應果蠅優化算法（adaptive fruit fly optimization algorithm，AFOA）參 數為：NP＝30，D＝180，mT＝600s，用戶要求的最小變異概率常數α＝0.001。

兩種算法分別在不同規模題庫上各獨立運行20次。算法結束條件為：算法找到可行解的目標函數值小于1或達到設定的最大運行時間10分鐘。

兩種算法在不同規模題庫上運行20次的組卷成功率見表1。根據算法結束條件，如果算法在運行結束時目標函數值小于1即認為組卷成功。在表1中，“組卷成功率”為算法運行20次找到可行解的比率。從表1可以看出，當題庫規模大于5000時，PSO 和AFOA 在算法結束時均能100%組卷成功。但在小規模題庫上，AFOA 組卷成功率明顯優于PSO，尤其在題庫1000上更為明顯。

表1 兩種算法在不同題庫上的組卷成功率

表2比較了兩種算法在題庫5000，10000，20000上組卷成功率為100%的組卷效率，其中 “Max”、 “Avg”和“Std”分別為算法成功運行20次所用時間的最大值、平均值和標準差。根據平行試卷自動生成模型，算法找到可行解的時間越短，組卷效率越高。

表2 兩種算法在不同題庫上的組卷時間／s

從表2可以看出，AFOA 在3種不同規模題庫的組卷效率顯著優于PSO，且AFOA 運行20 次找到可行解的平均時間均小于4s，而PSO 所需的平均時間均大于85s。此外，表2中所有測試算例的組卷時間標準差表明，AFOA對算法初始值具有較強的魯棒性。

表3展示了兩種算法在題庫10000上分別生成2套和3套平行試卷的組卷效率比較，其中， “NOPTS”表示生成平行試卷的套數，“Max”、“Avg”和 “Std”分別為算法運行20次找到可行解所用時間的最大值、平均值和標準差。

表3 生成不同套數平行試卷的組卷時間／s

表3的統計結果表明無論生成2 套或3 套平行試卷，AFOA 的組卷性能均顯著優于PSO。此外，隨著生成平行試卷套數的增加，兩種算法的平均組卷時間均有增加的趨勢，但PSO 的增加幅度較大。造成平均組卷時間增加的因素主要有兩個：一是受算法編碼的影響，種群個體中的決策變量隨著生成平行試卷套數的增加而劇增，即平行試卷生成問題變成了維度更高的組合優化問題；二是問題模型要求所有平行試卷無重題，平行試卷套數增加使得算法在解空間內搜索可行解的難度增大。

3.2 變異參數對AFOA性能的影響分析

以3種不同規模的題庫為例，分析了變異參數pm對算法組卷效率和組卷質量的影響。當pm＝0.12，pm＝0.1，pm＝0.08及pm取自適應值時分別讓算法成功運行20次，不同pm取值的果蠅優化算法在3種不同規模題庫上組卷效率和組卷質量比較分別如圖1和圖2所示。根據平行試卷自動生成問題模型，算法找到可行解的時間越短，組卷效率越高，算法找到可行解的目標函數值越接近0，組卷質量越高。pm對算法組卷效率影響實驗的算法結束條件為算法找到可行解的目標函數值小于1或算法運行時間小于3分鐘。pm對算法組卷質量影響實驗的算法結束條件為算法運行1分鐘。

圖1 pm 對果蠅優化算法組卷質量的影響

圖2 pm 對果蠅優化算法組卷效率的影響

從圖1和圖2可以得知，本文提出的自適應果蠅優化算法的組卷質量和組卷效率均優于其它3種固定變異參數取值的果蠅優化算法。具有自適應變異機制的果蠅優化算法在優化早期，使用較大的變異率對果蠅個體進行擾動以提高算法的全局搜索能力，且隨著算法的不斷優化，自適應的降低變異率，從而較好地保留了個體的優良信息，并在可行解周圍進行了更為精細的局部搜索，即自適應的變異機制較好地平衡了算法全局搜索和局部搜索能力。

4 結束語

針對基本果蠅優化算法在求解平行試卷自動生成問題時容易出現早熟收斂的缺陷，本研究結合平行試卷自動生成問題模型，提出一種具有自適應變異嗅覺搜索機制的改進果蠅優化算法。基于不同規模題庫的實驗結果表明，與PSO 算法相比，本文所提算法具有較好的組卷成功率和組卷效率，且算法能根據其迭代進化過程信息自適應地調節果蠅種群個體的變異概率，從而較好地平衡算法全局尋優和局部尋優能力。此外，算法具有原理簡單、易于實現、魯棒性好等優點。

［1］SUN Heng.The design of parallel paper in large－scale of educational examination ［J］.Education Science，2011，27 （6）：13－16 （in Chinese）.［孫恒.大規模教育考試平行試卷的設計［J］.教育科學，2011，27 （6）：13－16.］

［2］Hwang Gwo－jen，Chu Hui－chun，Yin Peng－yeng，et al.An innovative parallel test sheet composition approach to meet multiple assessment criteria for national tests ［J］.Computers ＆Education，2008，51 （3）：1058－1072.

［3］Yang Juan，Han Xibin，Zhou Qian.The design and development of a semi－auto computer generated testing paper system－a case study in the school of continuing education at China university of geosciences［J］.The Turkish Online Journal of Educational Technology，2011，10 （2）：209－217.

［4］Ho Tsu－feng，Yin Peng－yeng，Hwang Gwo－jen，et al.Multiobjective parallel test－sheet composition using enhanced particle swarm optimization ［J］.Educational Technology ＆ Society，2009，12 （4）：193－206.

［5］Chang Ting－yi，Shiu You－fu.Simultaneously construct IRTbased parallel tests based on an adapted clonal algorithm ［J］.Applied Intelligence，2012，36 （4）：979－994.

［6］XIAO Liqing，XU Xiaoju.Research of intelligent test paper generation based on improved genetic algorithm ［J］.Computer Engineering and Design，2012，33 （10）：3970－3974 （in Chinese）.［肖理慶，徐曉菊.改進遺傳算法智能組卷研究 ［J］.計算機工程與設計，2012，33 （10）：3970－3974.］

［7］ZHOU Yancong，LIU Yanliu.Research on auto－generating test paper based on genetic simulated annealing algorithm ［J］.Computer Engineering and Design，2011，32 （3）：1066－1069（in Chinese）.［周艷聰，劉艷柳.遺傳模擬退火智能組卷策略研究 ［J］.計算機工程與設計，2011，32 （3）：1066－1069.］

［8］LI Xinran，FAN Yongsheng.Study on intelligent test paper generation strategy through improved quantum－behaved particle swarm optimization［J］.Computer Science，2013，40 （4）：236－239 （in Chinese）.［李欣然，樊永生.改進量子行為粒子群算法智能組卷策略研究［J］.計算機科學，2013，40 （4）：236－239.］

［9］Pan WT.A new fruit fly optimization algorithm：Taking the financial distress model［J］.Knowledge－Based System，2012，26：69－74.

［10］Pan Quan－ke，Sang Hong－yan，Duan Jun－hua，et al.An improved fruit fly optimization algorithm for continuous function optimization problems［J］.Knowledge－Based System，2014，62：69－83.

［11］HAN Junying，LIU Chengzhong，WANG Lianguo.Dynamic double subgroups cooperative fruit fly optimization algorithm ［J］.PR ＆AI，2013，26 （11）：1057－1067（in Chinese）.［韓俊英，劉成忠，王聯國.動態雙子群協同進化果蠅優化算法 ［J］.模式識別與人工智能，2013，26 （11）：1057－1067.］

［12］LIU Zhixiong，WANG Yafen，ZHANG Yu.Multiple population fruit fly optimization algorithm for automatic warehouse order picking operation scheduling problem ［J］.Journal of Wuhan University of Technology，2014，36 （3）：71－77 （in Chinese）.［劉志雄，王雅芬，張煜.多種群果蠅優化算法求解自動化倉庫揀選作業調度問題 ［J］.武漢理工大學學報，2014，36 （3）：71－77.］