改進蟻群算法在職業技能鑒定題庫管理系統中的應用

潘海云+彭英慧+彭友

摘要：該項目針對職業技能鑒定考核中不同專業、不同工種及不同等級，開發職業技能鑒定題庫綜合管理系統。利用改進蟻群算法智能組合技能鑒定試卷，解決了組題過程中多目標問題，滿足不同群體的職業技能鑒定考核需求；考試試題二次組卷，體現了考試的公平性和公正性。

關鍵詞：職業技能鑒定；自動組題；多目標優化問題

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2016）08-0007-03

Abstract： this project is aimed at the different profession， the different type of work and the different grade in the appraisal of the professional skill appraisal， and develops the comprehensive management system. Using improved ant colony algorithm intelligent combination of skills identification papers， to solve the multi-objective problem set of problems in the process， meet different groups of vocational skills appraisal and assessment requirements； test second generation， reflecting the test of fairness and justice.

Key words： occupation skill identification； automatic group problem； multi-objective optimization problem

當前，智能組卷系統在教育系統中的應用，為各類用戶減少了大量的工作量，解決了許多實際問題。而教育工作者不斷提出更高的要求，組卷速度快、試卷題型多樣，難度系數適中、涵蓋的知識面廣，注重考查學生的實踐技能和綜合素質等。在職業技能鑒定題庫管理系統中組卷時間長、速度慢仍是普遍存在的問題，還不能滿足職業技能鑒定考核中的需求。所以筆者提出一種基于改進蟻群算法自動組卷策略在職業技能鑒定題庫中應用。

1 智能組卷理論研究

任何系統都有一定的指標體系，職業技能鑒定題庫也不例外，每個指標體系都有一定的作用，每個參數都有一定的意義，每個指標參數的構建都是為試卷分析、自動組卷、題庫管理服務的，這些指標參數實現了優化，基于指標參數的系統也就有一定的優化功能。智能組卷指標參數如下：

1）試卷題型：試卷題型因不同專業、不同工種的用戶需求而變化，通常設為5種題型：判斷題、單選題、多選題、填空題、綜合應用題（或大題）；

2）章節：課程的章節與題庫中各種類型的試題間存在對應關系，便于考核和管理；

3）知識點：教學大綱要求需要考核的知識點；

4）答題時間：完成某道試題所占用的時間，指大多數學生做完并檢查該題耗費的時間，出題者根據教學經驗綜合客觀情況適當調整；

5）難度系數：難度系統計算公式Pi=1-Ri/n，其中，Ri為該題得分的平均值，pi為試題i的難度系數， n為該題的滿分值[1]。在命題時，試題的難度隨著考試所針對的對象不同而不同，組卷時，按照組卷設定的難度系數得到符合難度要求的試卷。

由于被測對象不同、工種不同等因素變化對難度系統影響較大，所以不同對象、不同工種考核時更要科學、客觀地確定難度系數。除了參考以上算式，還要結合出題人員的教學經驗、考核對象進行調整，將難度系數模糊為下表列出的三個等級。一般情況下，試卷的平均難度系數大約控制在0.5，只有這樣試卷分數的分布才基本呈正態分布，符合自然規律，考試成績才具有參考價值[1]。

[難度等級＼&簡單題＼&中等題＼&較難題＼&難度區間＼&0.0-0.3＼&0.3-0.7＼&0.7-1.0＼&模糊化＼&0.2＼&0.5＼&0.8＼&]

2 職業技能鑒定題庫管理系統功能模塊介紹

職業技能鑒定題庫管理系統中應開發的功能為：

1）人員管理模塊：主要用來對用戶信息、各種角色以及系統使用權限等進行管理。

2）試卷管理模塊：主要根據考核大綱要求，設置題型、數量、難度系數并結合相關智能組卷算法自動組卷，并對生成的試卷進行編輯等操作。

3）題庫管理模塊：對歷年來生成的試卷進行評估。分析考試情況，對題庫中的試題類型、數量、難度系數等信息進行修正，為以后的智能組卷提供依據。

4）考試模塊：主要實現考生根據考號和密碼登錄系統進行考試等功能，為了體現考試的公平性，對同一試卷在保證答題結構、順序合理的情況下進行二次組卷。

5）閱卷管理模塊：主要實現考生提交試卷的評閱功能，包括對客觀題系統自動評判和主觀題人工評判兩部分。

6）成績管理模塊：該模塊中，學生可以查詢分數，管理人員可以查看、分析、匯總、導入、導出成績等操作功能。

3 職業技能鑒定題庫自動組卷問題的數學建模

在職業技能鑒定題庫管理系統自動組卷算法中，設試卷總分為M，試題總數為N，每套試卷的考試時間為T分鐘，試卷內容由n部分組成，各部分內容試題分數比為n1n2...nn；試卷中要考核的知識點包括m類，各類知識點所包含試題的分數比是m1m2...mm；題庫中試題的難度級別共有P個，試卷中每個難度級別試題的分數比為p1p2...pp；試卷中包含q種題型，則各個題型的分數比為q1q2...qq，具體數學模型如下：

3.1 改進的蟻群算法基本思想

蟻群算法主要是模擬螞蟻群落尋找食物過程，螞蟻之間的協作是蟻群算法中最關鍵的因素。蟻群算法依據蟻群的集體尋優特征搜索食物和蟻穴之間的路徑，在尋找食物時螞蟻會在路徑上散發信息素，這些信息素會被陸陸續續經過本路徑的螞蟻獲取到，然后螞蟻根據不斷獲取到的信息素選擇最佳路徑。每只螞蟻簡單的散發信息素、自行選擇路徑，隨著信息素的不斷積累，通過蟻群之間的協作多次尋找最后可選擇一條最優路徑[2]。目前，蟻群算法解決了最優解問題，但職業技能鑒定題庫組卷問題是一個多目標尋優問題，同時還要保證試題題型多樣、涵蓋的知識面廣、重復性不能過高，因此，根據職業技能鑒定題庫管理系統的實際需求，改進和優化蟻群算法，將信息素的積累從被考試過的題目次數轉移到降低被考過試題的信息素來增加其他試題的信息素，從而增加未考過的試題被選中的概率[3]。

3.2 改進后的蟻群算法實現

在基于蟻群算法的職業技能鑒定題庫自動組卷算法中，在試題庫中，每只螞蟻從一個試題節點移動到另一個試題節點，不斷地尋找路徑，當蟻群中的所有螞蟻都能夠走到路徑的終點時，相應的就組成了一套試卷。我們可以把組卷過程構造為一個有向圖，假設試題庫中有N道題，則該問題可以看成一個有N個節點和N*（N-1）邊的完全有向圖，記作G（V，E），其中V表示試題庫中的試題節點（試題庫中試題的數量），E表示連接節點的邊[2]。

3.3 螞蟻選擇路徑的方法

隨機生成試題節點M個并放置螞蟻M只，給出路徑的信息素量以及啟發因子，每只螞蟻會根據路徑上的信息素量自主選擇合適的有向線段并移動到下一個試題節點。按上述過程不斷地重復，直到約束條件滿足為止，在t時刻，螞蟻k（k=1，2，…m）從節點i（i=1，2，…，L）經過路徑a[i，j]到節點i+1的轉移概率Pkij（t）為：

JK（i）表示位于節點i的螞蟻k當前能選擇的有向線段組合，ηij表示螞蟻選擇有向線段a[i，j]的期望程度，α和β表示螞蟻k在進行路徑選擇時，有向線段a[i，j]上的信息素量和啟發因子的重要程度[2]。

3.4 信息素的更新

表示本次循環中有向線段a[i，j]上信息素的增量，也即第k只螞蟻在a[I，j]上留下的信息素量。

3.5 二次組卷功能的實現

為了保證在線考試的公平性，本文還采用一種二次組卷分發策略，將原始試卷中的試題在保證答題結構順序合理的情況下隨機打亂進行二次重組后分發給考生。這樣使得考生考試內容雖相同但試卷試題順序不同。從而避免抄襲現象，進而體現了考試的公正和公平。

對于一份n道試題組成的試卷，將試卷按題型順序打亂，程序流程圖1所示。

對原始試卷的不同題型下的試題順序打亂并重新組卷分發在考試中的作用非常重要，既保證了同一時間參加考試的全部考生同一試卷，又保證了試卷的題型結構合理、答題順序符合做題習慣，更重要的是整個考場內相鄰考生的試題順序截然不同，充分體現了考試的公平性和公正性[4]。

4 系統實現

在Microsoft visual studio 2010環境下，采用Sql server 2005數據庫管理系統存儲數據信息，實現了職業技能鑒定題庫管理系統，對機械鉗工、機械車工、汽車維修工、汽車裝配工等多種工種的職業技能鑒定試卷的生成。其中試題庫中有判斷題、單選題、填空題、多選題和綜合題每種題型各50答題，經過具體的實驗模擬，發現該算法能夠在一定時間內找到最優解，能夠自動生成難易適中，學生考試成績比較理想的試卷。

參考文獻：

[1] 韓英慧. 改進的遺傳算法在智能組卷系統中的應用[J].長春教育學院學報，2015（4）.

[2] 劉燕茹，李麗娜. 蟻群算法在計算機自動組卷中的應用研究[J].研究與開發，2014（5）.

[3] 廖金權. 一種基于改進蟻群算法的考試系統的研究[J].軟件雜志，2014（5）.

[4] 賀榮，陳爽. 在線組卷策略的研究與設計[J].計算機工程與設計，2011（12）.