計算機應用考試系統的模擬退火算法研究

厲丹 康曉鳳 張麗娜

摘 ?要： 針對傳統計算機應用考試系統在大規模應用時存在的任務并發擁堵問題，提出一種基于并行組合模擬退火算法的分布式計算機應用考試系統，以便提高分發效率和訪問容量。該系統采用B/S結構，解決了傳統C/S結構適用性較差的問題。設計中將考試的分發服務進行拆分，并使用模擬退火算法對分配方案進行優化，優化過程考慮到了服務器數量、考生數量和位置信息等約束條件。此外，結合遺傳算法和模擬退火算法進行組合改進，提高了并行性和收斂速度。算法仿真測試結果表明，提出的改進算法具有更好的快速收斂性能。實際應用結果驗證了提出的設計在大規?？荚噾弥械目尚行院瓦\行效率。

關鍵詞： 模擬退火算法; 計算機應用考試; 分配方案優化; B/S結構; 仿真測試; 并行性驗證

中圖分類號： TN911.1?34; TP302.1 ? ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2020）07?0107?04

Research on simulated annealing algorithm for computer application examination system

LI Dan， KANG Xiaofeng， ZHANG Lina

（Xuzhou University of Technology， Xuzhou 221000， China）

Abstract： Since the concurrent congestion occurs in the large?scale application process of the traditional computer application examination systems， a distributed computer application examination system based on parallel recombination simulated annealing algorithm （PRSAA） is proposed to improve the distribution efficiency and increase the access capacity. The B/S structure is adopted in the system to deal with the poor applicability of the traditional C/S structure. In the design， the distribution service in the examination is split and the distribution scheme is optimized with the simulated annealing algorithm. In the optimization process， constraints such as the number of servers， the number of candidates and the location information are taken into account. In addition， the composition improvement is carried out in combination with the genetic algorithm and the simulated annealing algorithm to improve the concurrency and the convergence rate. The results of simulation test for the algorithm shows that the proposed improved algorithm has high rapid convergence performance. The feasibility and operational efficiency of the proposed design were verified in the practical applications of large?scale examinations.

Keywords： simulated annealing algorithm; computer application examination; distribution scheme optimization; B/S structure; simulation testing; concurrency verification

0 ?引 ?言

隨著計算機應用和網絡技術的迅猛發展，世界范圍內的廣大高校均不斷退出各種在線考試系統，無紙化、互聯網化的考試系統正成為當前教育領域研究的熱點之一[1?2]?，F階段，針對計算機應用的相關課程考試系統已經不少，但是大多數仍舊采用C/S架構，需要在所有的客戶端上安裝考試軟件，并要適用于各種客戶端設備，這對軟件開發的難度和后期維護工作量都是較大的考驗，導致應用成本居高不下[3]。此外，當應用于大規?？荚嚽闆r時，由于學生數量較多、時間較為集中、服務器資源有限等問題，導致常常發生并發沖突、無法訪問和延遲卡頓等不良現象，需要增加軟硬件投入來有效改善此問題[4]。近期，文獻[5]提出了面向中小學的基于UML的網絡分布式考試系統軟件，可視化效果突出。文獻[6]提出的在線考試系統采用了基于ASP，Access數據庫及B/S結構的技術，簡化了傳統考試系統，提高了工作效率。文獻[7]提出一種基于遺傳算法的高校在線考試系統，但是僅僅限于試題的多樣性組卷。這些設計均無法有效解決大規模應用的并發和效率問題。因此，采用B/S結構設計了分布式考試系統設計框架，給出了系統主要功能模塊以及任務流程，并設計基于組合模擬退火算法的計算機應用考試任務分發實現方法，提高了系統的并行性和運行效率，緩解了大規模應用的并發擁堵問題。

1 ?系統設計

1.1 ?分布式系統設計框架

根據計算機應用考試的功能性需求，分布式考試系統應該具有基本的試題庫和在線考試功能。試題庫應該包括Word，Windows，Excel，PowerPoint，Email和Web網頁等主題內容。本文設計的分布式在線考試系統采用B/S結構，解決了傳統C/S結構適用性較差的問題，其網絡運行結構示意圖如圖1所示。

1.2 ?系統主要功能模塊以及任務流程

分布式計算機應用考試系統的配置基礎是學生的客戶機，數量為[n]，[n∈{1，2，…，N}]。所有的客戶機均通過互聯網連接到系統Web服務器，也就是分布式計算機應用考試系統端。分布式計算機應用考試系統的所有試題文件均保存在數據庫服務器中，供Web服務器直接搜索和讀取。分布式計算機應用考試系統的功能模塊設計如圖2所示，包括用戶注冊、登錄、成績查詢、在線考試、系統設置等。其中，系統設置可以對分布式考試的時間、學生信息等數據進行管理。

本文采用Spring技術[8]搭建分布式計算機應用考試系統的工作流程，任務工作流程如圖3所示。學生在登錄后首先選擇試卷，執行下載和生成試卷文件夾操作。學生答題后進行交卷，系統開始執行評分和保存操作。試卷的分發和收交流程是大規模應用時發生擁堵問題的節點，因此，設計了基于組合模擬退火算法的計算機應用考試任務分發實現方法，以提高系統的并行性和運行效率，減少大規模應用的擁堵現象。

2 ?基于組合模擬退火算法的計算機應用考試任務分發

2.1 ?模擬退火算法的原理

作為一種啟發式隨機搜索過程，模擬退火算法來源于固體退火原理[9?11]。研究人員通常采用固體退火模擬組合優化問題，在常溫時達到基態，算法終止時的當前解即為所得近似最優解。模擬退火算法的計算流程為：

1） 設定初始溫度[T]，產生初始值[i]，限定解狀態[S];

2） 在[k=1，2，…，L]迭代中，重復執行步驟3）～步驟6）;

3） 產生新解[i′];

4） 根據如下公式評估能量函數[ΔE]：

[ΔE=C（i′）-C（i）] （1）

式中[C（i）]表示評估函數。

5） 如果[ΔE<0]，那么設定[i′]替換當前解，否則，按照概率設定[i′]替換當前解;

6） 判斷終止條件是否滿足，是則迭代終止，輸出當前解，否則，進行降溫，[T]逐漸減少，且[T→0]，然后執行步驟2）。

2.2 ?組合模擬退火算法

通過上述模擬退火算法流程分析，可以看出其局部優化能力和并行性較強，但是全局搜索能力較差，導致收斂性不好。而經典的遺傳算法把握總體的能力較強，因此，提出將模擬退火算法和遺傳算法相結合，在模擬退火算法的迭代操作之前，首先執行遺傳算法的選擇、交叉和變異過程，也就是在遺傳算法的交叉操作后面增加模擬退火的降溫操作。組合模擬退火算法的改進流程如圖4所示。

2.3 ?目標函數

考試分發服務中的分配方案不是一個單目標的優化問題，而應該是一個多目標優化求解問題。因此，本文將其進行拆分并使用組合模擬退火算法進行優化。本文結合權重系數法，考慮到了服務器數量、考生數量和位置信息等約束條件，設計基于組合模擬退火算法的考試任務分發的總目標函數如下：

[f（P）=1-ω1?V1+ω2?V2+ω3?V3] ?（2）

式中：[ω1]為服務器數量[V1]約束條件的權值因子;[ω2]為考生數量[V2]約束條件的權值因子;[ω3]為位置信息[V3]約束條件的權值因子。其中，服務器數量、考生數量和位置信息等約束條件的計算方式和文獻[7]一致。

3 ?實驗結果與分析

3.1 ?實驗參數

為了驗證提出的組合模擬退火算法的有效性，在Matlab仿真環境下進行了模擬實驗。本文所有實驗的運行環境均為 Windows 7系統下的Matlab 2015b，處理器為Intel[?] CoreTM i5?3210M CPU @ 2.50 GHz，內存為8 GB。在本文實驗過程中，設置最大迭代次數為2 000，交叉概率為0.3，變異概率為0.02，退火初始溫度為50 ℃，退火因子[k=]0.95。

3.2 ?仿真結果分析

將單一模擬退火算法和本文組合模擬退火算法在Matlab仿真環境下，使用簡單的二維測試函數進行了對比實驗。測試函數為[12]：

[f（x，y）=sin x+cos y] （3）

從圖5可以看出，本文組合模擬退火算法已成功找出了最優解。從圖6可以看出，相比于單一模擬退火算法，本文方法能夠較快地找到全局最優解，反映出改進的模擬退火算法的快速收斂性能。

3.3 ?分布式性能驗證

為了進一步驗證基于組合模擬退火算法的考試任務分發系統的運行效率，在集群環境下對系統的執行效率進行了對比。將無并行分發的考試系統和基于組合模擬退火算法的考試系統的運行時間進行比較。統計結果如表1所示，可以看出，隨著節點數量的不斷增大，獲得的加速效果越來越顯著。

從表1可以看出，隨著樣本文件的增大，兩者的運行時間均緩慢上升，但從上升速度方面來看，本文算法優于無并行分發的考試系統。在同等大小樣本集下，本文算法相比無并行分發的考試系統，在大規模分布式任務上表現更好。

3.4 ?系統具體實現

本文對提出基于組合模擬退火算法的計算機應用考試系統進行了具體實現，在某大型植物園林場景中進行了具體測試。選擇“進入在線考試系統”，即可進入在線考試系統的登錄界面，選擇考試題目開始測試，如圖7所示。

4 ?結 ?語

本文提出將考試的分發服務進行拆分，并使用模擬退火算法對分配方案進行了優化，針對模擬退火算法存在的缺點，結合遺傳算法進行了改進，有利于提高尋優精度和運行速度。此外，結合權重系數法，引入服務器數量、考生數量和位置信息等約束條件，設計了考試分發任務的總目標函數。仿真環境下的函數測試和系統具體實現結果驗證了本文提出系統設計的可行性和有效性。但是，在實際應用的過程中，每次考試應用均需要對初始參數進行設置，這在一定程度上限制了其推廣效果，后續將針對此問題進行進一步改進。

參考文獻

[1] LUAN H L， WANG H B， QIN H Y， et al. Design and implementation of stud?farm daily management system based on C/S structure [J]. Journal of Northeast Agricultural University （English edition）， 2014， 21（3）： 50?59.

[2] 韓麗紅，祝榮欣，李海越，等.基于B/S+C/S的高校科技協同管理綜合系統的研究與實現[J].煤礦機械，2014，35（3）：221?224.

[3] GIL D， FERR?NDEZ A， MORAMORA H， et al. Internet of Things： a review of surveys based on context aware intelligent services [J]. Sensors， 2016， 16（7）： 1069.

[4] 劉彩利.C/S和B/S混合體系結構的開發與應用[J].電子設計工程，2015，23（14）：26?28.

[5] 李莉.基于UML的網絡分布式考試系統軟件建模[J].電子技術與軟件工程，2018（14）：55?56.

[6] 石亞妮.基于B/S構架的遠程教育學生在線考試系統設計[J]. 自動化技術與應用，2018，37（7）：52?55.

[7] 王莉.基于遺傳算法的高校在線考試系統研究[J].電子設計工程，2015（24）：29?31.

[8] ZHANG Rui， WU Cheng. A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective [J]. Computers & operations research， 2011， 38（5）： 854?867.

[9] CRUZ?CH?VEZ M A， MART?NEZ?RANGEL M G， CRUZ?ROSALES M H. Accelerated simulated annealing algorithm applied to the flexible job shop scheduling problem [J]. International transactions in operational research， 2017， 24（5）： 1119?1137.

[10] KANAGARAJ G， JAWAHAR N. A simulated annealing algorithm for optimal supplier selection using the reliability?based total cost of ownership model [J]. International journal of procurement management， 2017， 2（3）： 244?266.

[11] CHEN Haihong， WU Changchun， ZUO Lili， et al. Optimization of detailed schedule for a multiproduct pipeline using a simulated annealing algorithm and heuristic rules [J]. Industrial & engineering chemistry research， 2017， 56（17）： 5092?5106.

[12] ZOU D X， WANG G G， SANGAIAH A K， et al. A memory?based simulated annealing algorithm and a new auxiliary function for the fixed?outline floorplanning with soft blocks [J]. Journal of ambient intelligence & humanized computing， 2017（6）： 1?12.