基于線性遞減系數粒子群優化算法的組卷實現

白雁

摘 ?要： 為了避免目前常用的組卷算法組卷時間長、程序結構復雜、收斂速度慢等缺陷，提出基于線性遞減系數粒子群優化算法的組卷策略。通過調整慣性系數，使得步長較小，慣性權系數的變化幅度小，這種減小趨勢較為緩慢的方法能夠避免陷入局部最優。并對數學模型以及線性遞減慣性權系數進行了理論設計，同時通過編程實現了該算法。測試結果表明加入線性遞減系數后運算迭代次數明顯減少，證明加入線性遞減系數后的組卷策略收斂性好，能夠高效準確地按照一定的預期條件進行組卷，符合預期要求。

關鍵詞： 組卷; 粒子群優化算法; 線性遞減慣性權系數; 適應度函數

中圖分類號： TN911?34 ? ? ? ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2014）24?0041?04

Implementation of test paper generation based on particle swarm optimization algorithm with linear decreasing inertia weight

BAI Yan

（The Distance Education School， Xian Jiaotong University， Xian 710048， China）

Abstract：In order to avoid defects in the commonly used test paper generation algorithm， such as too much time taking， complicated program structure and low velocity of convergence， a test paper generation strategy of ?particle swarm optimization algorithm based on linear decreasing inertia weight is proposed. The step size becomes smaller and the inertia weight changes less by adjusting the inertia coefficient. The relatively slow decreasing trend method can avoid falling into local optimum. The theoretical design for mathematical model， linear decreasing inertia weight was carried out. The algorithm was realized by programming. Test results show that the addition of linear decreasing coefficient can greatly reduce the iteration times， can make the convergence characteristic better， and can efficiently and accurately generate test paper according to the expected conditions.

Keywords： test paper generation; particle swarm optimization algorithm; linear decreasing inertia weight; fitness function

0 ?引 ?言

教育信息化促進了教育領域的全面變革，其中傳統的考試方式也慢慢開始逐步被在線考試這一形式所取代。如何快捷、有效、科學地組卷是在線考試系統的技術核心。合理的組卷策略不僅僅是完成一份考題，而是要像人工考試那樣能夠按照總分，題型，章節，難度等信息篩選相應的試題組成具有一定難度和區分度的試卷，這樣能夠更加客觀，公平，真實地反映出學生對知識點掌握的情況。

組卷算法實際上是多目標約束優化問題，合理選擇組卷算法是解決問題的關鍵。目前常用的組卷算法有隨機組卷法、回溯法、遺傳算法、魚群算法、粒子群優化算法等。但這些算法存在著組卷時間長，程序結構復雜，收斂速度慢，計算復雜等缺陷[1]。針對這些問題，本文提出的基于線性遞減系數粒子群優化算法的組卷策略，其具有粒子群優化算法的原理簡單、參數少、收斂性好、容易實現等特點，同時又加入了線性遞減的慣性權重系數，在避免陷入局部最優的同時使得搜索后期加速收斂，克服了粒子群優化算法的缺點，較好地解決了組卷的優化問題。

1 ?組卷策略的理論設計

1.1 ?粒子群優化算法概述

粒子群優化算法是基于鳥群覓食行為的一種迭代優化算法，由Eberhart博士和Kennedy博士提出的。他們發現鳥群在覓食的過程中，在不清楚食物具體位置的情況下能夠不斷調整速度和飛行的位置以接近食物，最終聚到一起找到食物[2]。

經過模擬社會模型將其概括成以下公式：

[vidt+1=w*vidt+c1rand*pidt-xidt+ ? ? ? ? ? ? ? ? ? ? c2rand*Pgdt-xidt] （1）

[xidt+1=xidt+vidt+1] （2）

式中：[c1，c2]為正的常數，一般均取值為2;rand（）和rand（）為[0，1]之間的隨機數，可以用隨機數生成函數生成;w為慣性權重。

式（1）表示鳥群速度矢量的更新由以下三部分決定：首先是當前的狀態，這個是其慣性的表現。其次是自身經驗，在以往過程中距食物最近的位置往往起著導向作用。最后一部分通過與其他鳥兒進行信息交流，了解整個鳥群的社會經驗，即整個迭代過程中其他鳥兒距離食物最近的位置，來獲得的最佳位置。同時每次迭代都要使用位置矢量根據預設的適應度函數計算出適應度值來判斷位置的遠近[3]。

1.2 ?數學模型

試題數據庫中的題目具有以下幾個屬性：

（1） 總分。一份試卷中所有試題的分數總和，一般為100分，120分，150分。

（2） 題型。題庫中的題目可分為主觀題，客觀題兩種類型，主觀題是人工改卷的題型，主要有問答題，論述題等。客觀題是計算機自動改卷的題型，主要有單選題，多選題，判斷題，填空題，復合題（閱讀理解，完形填空）等。將每種題型進行編號，比如單選題為1，多選題為2，判斷題為3，填空題為4，閱讀理解為5，完形填空為6，問答題為7，論述題為8。按照要求設定各個題型的比例，比如{b1，b2，…，b8}為每種題型所占分數的比例。

（3） 章節比例。每道題目都有其所屬的章節屬性，科學的組卷是在考試中每章的知識點按照權重出題，重要的章節要多出并且兼顧每章的知識點都要有所涉及，以本院《計算機科學與技術》題庫為例，一共有8章內容，分別用數字1～8表示，所占分數比例{c1，c2，…，c8}。

（4） 難易程度。試題難度分為1，2，3等級，1表示簡單題，2表示中等難度，3表示難題。

據上述分析可知，一份由n道試題組成的試卷實際上可以轉化為一個具有多重約束的尋優問題，這份試卷就是一個目標矩陣：

[Z=a11a12a13a14a15a21a22a23a24a25??…??an1an2an3an4an5]

式中每一行是一道題目，包含5個屬性向量;其中ai1表示題目編號（1≤i≤n），ai2表示題型編號，ai3表示所屬章節，ai4表示難度編號，ai5表示分數值[4?6]。其應該滿足的約束條件如下：

（1） bm為每個題型所占分數，則有[bm=i=1nc1ai2]，當ai2為m時，c1為1，其余為0。其中1≤m≤8。

（2） Cj為每個章節所占分數，則有[cj=i=1nc2ai3]，當ai3為j時，c2為1，其余為0。其中1≤j≤8。

（3） dz每道題目的難易程度和，則有[dz=i=1nc3ai4]，當ai4為z時，c3為1，其余為0。其中1≤z≤3。

（4） Ts為試卷總分值，ai5為每道題目的分數，則有[Ts=i=1nai5] 。

適應度函數由這四個基本條件以及其他的復雜條件，比如題型分布條件、難度方差約束，區分度約束條件等組成，本系統進行了簡化使用這四個條件作為適應度函數。

1.3 ?線性遞減慣性權系數

在粒子群優化算法中，慣性權系數是最重要的參數。根據上面的公式可以知道，w大，速度V大， 這樣粒子可以搜索更大的范圍空間。而w小， 則速度V就小，有利于提高局部搜索能力在當前的空間里搜索最優解，但是容易陷入局部最優。因此對于參數的選擇，實際就是要在全局搜索和局部搜索取得最佳的比例關系[7?8]。

本文在Yuhui Shi研究的基礎上調整了慣性系數的策略，選用了[9?10]：

[wk=wini-wini-wend2kmax·k] （3）

式中：k是目前的進化次數;kmax 為最大進化次數;wini 為初始慣性權重值;wend為進化至最大次數時的慣性權重值，wini=0.9，wend=0.4。分母乘以2，使得步長較小，w的變化幅度小，這種減小趨勢較為緩慢的方法能夠避免陷入局部最優。在本程序中可以簡化為以下形式：w（k）=0.9-0.25[kkmax]，其中k為程序循環迭代的次數，kmax為最大迭代次數。

2 ?算法流程

首先確定試卷的組卷參數，比如總分，每個題型的分數比例，每章所占分數比例，題目難易程度分布等，并且確定適應度函數的幾個參數。設定條件后題目的數目也是固定的，用隨機數生成器隨機生成固定數目的若干題號，組成一份試卷，每份試卷就是一個初始群體，一共產生5個初始群體，代入適應度函數公式計算出個體適應度，作為初始pbest和gbest。根據循環的次數計算出w的值，并且計算出速度適量和位置矢量，粒子的速度和位置決定了粒子移動的方向，組卷模型中和其他模型不同的地方在于：題目的編號相當于位置矢量，而題目的遞增不會出現小數類型，故速度矢量和位置均為整型。之后進行下一步迭代，計算個體適應度，并且與初始pbest，gbest進行比較，并同時更新這兩個值。直到滿足適應度函數的取值，找出其速度矢量和位置矢量。如果收斂則取得的結果就是最終成卷結果，如果不收斂則重新抽題。

3 ?數據庫結構設計

系統前臺為ASP，后臺為VB.Net+SQL Server 2005數據庫，學生端考試是B/S架構，方便快捷。教師改卷以及管理員端是C/S架構，安全性高。

試題庫數據表儲存每道題目的詳細信息，試題是按照不同的題庫錄入的。其關鍵字段如1所示。

表1 試題庫數據表的關鍵字段

考試試卷數據庫表用于存放考試試卷，其關鍵字段如表2所示。

對于選定題庫并根據組卷算法生成的試卷的所有題目將會存放在一個數據表中，每次顯示某個試卷的試題就是根據試卷編號從這個數據庫和試題數據庫提取，其中表3中的題目編號也就是試題庫中的題目編號，根據這個外鍵聯合查詢可以取得試題的具體信息在前臺網站上顯示。其關鍵字段如表3所示。

表2 考試試卷信息數據表的關鍵字段

表3 試卷包含試題編號表的關鍵字段

4 ?組卷測試結果及數據分析

為了驗證算法及其函數取值的可行性和有效性，利用上述網上考試的組卷系統，以《計算機科學與技術》課程為例進行組卷實驗。

系統題庫共有4種題型、8個章節、3個難度系數的326道題目。組卷時設置滿分為 100分，將粒子群規模設為5，最大迭代次數為 500次，并且根據下面的約束條件設置題目：

（1） 試卷總分為100分。

（2） 題型分數比例為：{30，30，20，20，0，0，0，0}.單選題30分，多選題30分，判斷題20分，填空題20分，其他題型沒有選擇到，均為0。

（3） 章節分數比例為：{10，10，20，10，10，10，20，10}。

（4） 試題難易程度均為2。

加入線性遞減系數的運行結果為由以下題號的題目組成一份試卷：13， 16，23，27，28，31，35，47，68，72，74 ，76，80，91，95，103，111，136，138，149，169，179，183，185，191，210，258，279，287，289，293，302，323，325。

上述題號13試題在程序運行中的數據為：[13，1，1，2，3]，往數據庫中增加題目的同時自動運行存儲過程將每道題目信息轉化成矩陣形式，依次類推?；诰€性遞減系數粒子群優化算法就是基于這些元數據進行反復迭代運算。上例中單選題 10道 ，多選題10 道 ，判斷題 10道 ，填空題 4 道，單選題一道3分，多選題一道3分，判斷題一道2分，填空題一道5分。

表5 運行結果比較

分別使用粒子群優化算法和加入線性遞減系數的粒子群優化算法進行組卷實驗，總共運行10次，可以看出總體上基于線性遞減粒子群優化算法效率高，全部成功，而粒子群優化算法速度較慢，成功率較低。

5 ?結 ?語

本文設計了基于線性遞減系數粒子群優化算法的組卷策略和算法流程，并且用題庫中的數據進行測試，結果表明加入線性遞減系數后的組卷策略更能高效準確的組卷，成卷效果良好，但是本系統還需要進一步的完善以滿足實際需要。

參考文獻

[1] 潘莉.遺傳算法在自動組卷中的應用方法研究[D].長春：東北師范大學，2010.

[2] KENNEDY J， EBERHART R C.Particle swarm optimization [J]. Institute of Electrical and Electronics Engineers， 1995 （11）： 1942?1946.

[3] 劉波.粒子群優化算法及其工業應用[M].北京：電子工業出版社，2010.

[4] 駱睿，周寧，趙舵.帶慣性權重的粒子群優化算法性能仿真[J].信息技術，2008（8）：94?99.

[5] 胡建秀，曾建潮.微粒群算法中慣性權重的調整策略[J].計算機工程，2007（11）：199?201.

[6] 馬躍亮.基于改進粒子群算法的組卷策略研究[D].保定：河北農業大學，2011.

[7] SHI Y， EBERHART R C. Parameter selection in particle swarm optimization [C]// Proceedings of the IEEE International Conference on Evolutionary Computation. Piscataway， NJ： IEEE Press， 1998： 69?75.

[8] 閻峰，安曉東.基于粒子群優化算法的智能抽題策略研究[J].中北大學學報：自然科學版，2008（4）：46?50.

[9] 田民格.改進的粒子群優化算法實現多目標智能組卷[J].三明學院學報，2009（4）：49?52.

[10] 丁瑾.基于粒子群優化算法組卷的研究[J].軟件導刊，2010（11）：81?83.

表2 考試試卷信息數據表的關鍵字段

表3 試卷包含試題編號表的關鍵字段

4 ?組卷測試結果及數據分析

為了驗證算法及其函數取值的可行性和有效性，利用上述網上考試的組卷系統，以《計算機科學與技術》課程為例進行組卷實驗。

系統題庫共有4種題型、8個章節、3個難度系數的326道題目。組卷時設置滿分為 100分，將粒子群規模設為5，最大迭代次數為 500次，并且根據下面的約束條件設置題目：

（1） 試卷總分為100分。

（2） 題型分數比例為：{30，30，20，20，0，0，0，0}.單選題30分，多選題30分，判斷題20分，填空題20分，其他題型沒有選擇到，均為0。

（3） 章節分數比例為：{10，10，20，10，10，10，20，10}。

（4） 試題難易程度均為2。

加入線性遞減系數的運行結果為由以下題號的題目組成一份試卷：13， 16，23，27，28，31，35，47，68，72，74 ，76，80，91，95，103，111，136，138，149，169，179，183，185，191，210，258，279，287，289，293，302，323，325。

上述題號13試題在程序運行中的數據為：[13，1，1，2，3]，往數據庫中增加題目的同時自動運行存儲過程將每道題目信息轉化成矩陣形式，依次類推。基于線性遞減系數粒子群優化算法就是基于這些元數據進行反復迭代運算。上例中單選題 10道 ，多選題10 道 ，判斷題 10道 ，填空題 4 道，單選題一道3分，多選題一道3分，判斷題一道2分，填空題一道5分。

表5 運行結果比較

分別使用粒子群優化算法和加入線性遞減系數的粒子群優化算法進行組卷實驗，總共運行10次，可以看出總體上基于線性遞減粒子群優化算法效率高，全部成功，而粒子群優化算法速度較慢，成功率較低。

5 ?結 ?語

本文設計了基于線性遞減系數粒子群優化算法的組卷策略和算法流程，并且用題庫中的數據進行測試，結果表明加入線性遞減系數后的組卷策略更能高效準確的組卷，成卷效果良好，但是本系統還需要進一步的完善以滿足實際需要。

參考文獻

[1] 潘莉.遺傳算法在自動組卷中的應用方法研究[D].長春：東北師范大學，2010.

[2] KENNEDY J， EBERHART R C.Particle swarm optimization [J]. Institute of Electrical and Electronics Engineers， 1995 （11）： 1942?1946.

[3] 劉波.粒子群優化算法及其工業應用[M].北京：電子工業出版社，2010.

[4] 駱睿，周寧，趙舵.帶慣性權重的粒子群優化算法性能仿真[J].信息技術，2008（8）：94?99.

[5] 胡建秀，曾建潮.微粒群算法中慣性權重的調整策略[J].計算機工程，2007（11）：199?201.

[6] 馬躍亮.基于改進粒子群算法的組卷策略研究[D].保定：河北農業大學，2011.

[7] SHI Y， EBERHART R C. Parameter selection in particle swarm optimization [C]// Proceedings of the IEEE International Conference on Evolutionary Computation. Piscataway， NJ： IEEE Press， 1998： 69?75.

[8] 閻峰，安曉東.基于粒子群優化算法的智能抽題策略研究[J].中北大學學報：自然科學版，2008（4）：46?50.

[9] 田民格.改進的粒子群優化算法實現多目標智能組卷[J].三明學院學報，2009（4）：49?52.

[10] 丁瑾.基于粒子群優化算法組卷的研究[J].軟件導刊，2010（11）：81?83.

表2 考試試卷信息數據表的關鍵字段

表3 試卷包含試題編號表的關鍵字段

4 ?組卷測試結果及數據分析

為了驗證算法及其函數取值的可行性和有效性，利用上述網上考試的組卷系統，以《計算機科學與技術》課程為例進行組卷實驗。

系統題庫共有4種題型、8個章節、3個難度系數的326道題目。組卷時設置滿分為 100分，將粒子群規模設為5，最大迭代次數為 500次，并且根據下面的約束條件設置題目：

（1） 試卷總分為100分。

（2） 題型分數比例為：{30，30，20，20，0，0，0，0}.單選題30分，多選題30分，判斷題20分，填空題20分，其他題型沒有選擇到，均為0。

（3） 章節分數比例為：{10，10，20，10，10，10，20，10}。

（4） 試題難易程度均為2。

加入線性遞減系數的運行結果為由以下題號的題目組成一份試卷：13， 16，23，27，28，31，35，47，68，72，74 ，76，80，91，95，103，111，136，138，149，169，179，183，185，191，210，258，279，287，289，293，302，323，325。

上述題號13試題在程序運行中的數據為：[13，1，1，2，3]，往數據庫中增加題目的同時自動運行存儲過程將每道題目信息轉化成矩陣形式，依次類推?；诰€性遞減系數粒子群優化算法就是基于這些元數據進行反復迭代運算。上例中單選題 10道 ，多選題10 道 ，判斷題 10道 ，填空題 4 道，單選題一道3分，多選題一道3分，判斷題一道2分，填空題一道5分。

表5 運行結果比較

分別使用粒子群優化算法和加入線性遞減系數的粒子群優化算法進行組卷實驗，總共運行10次，可以看出總體上基于線性遞減粒子群優化算法效率高，全部成功，而粒子群優化算法速度較慢，成功率較低。

5 ?結 ?語

本文設計了基于線性遞減系數粒子群優化算法的組卷策略和算法流程，并且用題庫中的數據進行測試，結果表明加入線性遞減系數后的組卷策略更能高效準確的組卷，成卷效果良好，但是本系統還需要進一步的完善以滿足實際需要。

參考文獻

[1] 潘莉.遺傳算法在自動組卷中的應用方法研究[D].長春：東北師范大學，2010.

[2] KENNEDY J， EBERHART R C.Particle swarm optimization [J]. Institute of Electrical and Electronics Engineers， 1995 （11）： 1942?1946.

[3] 劉波.粒子群優化算法及其工業應用[M].北京：電子工業出版社，2010.

[4] 駱睿，周寧，趙舵.帶慣性權重的粒子群優化算法性能仿真[J].信息技術，2008（8）：94?99.

[5] 胡建秀，曾建潮.微粒群算法中慣性權重的調整策略[J].計算機工程，2007（11）：199?201.

[6] 馬躍亮.基于改進粒子群算法的組卷策略研究[D].保定：河北農業大學，2011.

[7] SHI Y， EBERHART R C. Parameter selection in particle swarm optimization [C]// Proceedings of the IEEE International Conference on Evolutionary Computation. Piscataway， NJ： IEEE Press， 1998： 69?75.

[8] 閻峰，安曉東.基于粒子群優化算法的智能抽題策略研究[J].中北大學學報：自然科學版，2008（4）：46?50.

[9] 田民格.改進的粒子群優化算法實現多目標智能組卷[J].三明學院學報，2009（4）：49?52.

[10] 丁瑾.基于粒子群優化算法組卷的研究[J].軟件導刊，2010（11）：81?83.