計(jì)算機(jī)應(yīng)用考試系統(tǒng)的模擬退火算法研究

厲丹 康曉鳳 張麗娜

摘 ?要： 針對傳統(tǒng)計(jì)算機(jī)應(yīng)用考試系統(tǒng)在大規(guī)模應(yīng)用時(shí)存在的任務(wù)并發(fā)擁堵問題，提出一種基于并行組合模擬退火算法的分布式計(jì)算機(jī)應(yīng)用考試系統(tǒng)，以便提高分發(fā)效率和訪問容量。該系統(tǒng)采用B/S結(jié)構(gòu)，解決了傳統(tǒng)C/S結(jié)構(gòu)適用性較差的問題。設(shè)計(jì)中將考試的分發(fā)服務(wù)進(jìn)行拆分，并使用模擬退火算法對分配方案進(jìn)行優(yōu)化，優(yōu)化過程考慮到了服務(wù)器數(shù)量、考生數(shù)量和位置信息等約束條件。此外，結(jié)合遺傳算法和模擬退火算法進(jìn)行組合改進(jìn)，提高了并行性和收斂速度。算法仿真測試結(jié)果表明，提出的改進(jìn)算法具有更好的快速收斂性能。實(shí)際應(yīng)用結(jié)果驗(yàn)證了提出的設(shè)計(jì)在大規(guī)模考試應(yīng)用中的可行性和運(yùn)行效率。

關(guān)鍵詞： 模擬退火算法; 計(jì)算機(jī)應(yīng)用考試; 分配方案優(yōu)化; B/S結(jié)構(gòu); 仿真測試; 并行性驗(yàn)證

中圖分類號(hào)： TN911.1?34; TP302.1 ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? 文章編號(hào)： 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 ?引 ?言

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

1 ?系統(tǒng)設(shè)計(jì)

1.1 ?分布式系統(tǒng)設(shè)計(jì)框架

根據(jù)計(jì)算機(jī)應(yīng)用考試的功能性需求，分布式考試系統(tǒng)應(yīng)該具有基本的試題庫和在線考試功能。試題庫應(yīng)該包括Word，Windows，Excel，PowerPoint，Email和Web網(wǎng)頁等主題內(nèi)容。本文設(shè)計(jì)的分布式在線考試系統(tǒng)采用B/S結(jié)構(gòu)，解決了傳統(tǒng)C/S結(jié)構(gòu)適用性較差的問題，其網(wǎng)絡(luò)運(yùn)行結(jié)構(gòu)示意圖如圖1所示。

1.2 ?系統(tǒng)主要功能模塊以及任務(wù)流程

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

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

2 ?基于組合模擬退火算法的計(jì)算機(jī)應(yīng)用考試任務(wù)分發(fā)

2.1 ?模擬退火算法的原理

作為一種啟發(fā)式隨機(jī)搜索過程，模擬退火算法來源于固體退火原理[9?11]。研究人員通常采用固體退火模擬組合優(yōu)化問題，在常溫時(shí)達(dá)到基態(tài)，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解。模擬退火算法的計(jì)算流程為：

1） 設(shè)定初始溫度[T]，產(chǎn)生初始值[i]，限定解狀態(tài)[S];

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

3） 產(chǎn)生新解[i′];

4） 根據(jù)如下公式評估能量函數(shù)[ΔE]：

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

式中[C（i）]表示評估函數(shù)。

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

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

2.2 ?組合模擬退火算法

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

2.3 ?目標(biāo)函數(shù)

考試分發(fā)服務(wù)中的分配方案不是一個(gè)單目標(biāo)的優(yōu)化問題，而應(yīng)該是一個(gè)多目標(biāo)優(yōu)化求解問題。因此，本文將其進(jìn)行拆分并使用組合模擬退火算法進(jìn)行優(yōu)化。本文結(jié)合權(quán)重系數(shù)法，考慮到了服務(wù)器數(shù)量、考生數(shù)量和位置信息等約束條件，設(shè)計(jì)基于組合模擬退火算法的考試任務(wù)分發(fā)的總目標(biāo)函數(shù)如下：

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

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

3 ?實(shí)驗(yàn)結(jié)果與分析

3.1 ?實(shí)驗(yàn)參數(shù)

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

3.2 ?仿真結(jié)果分析

將單一模擬退火算法和本文組合模擬退火算法在Matlab仿真環(huán)境下，使用簡單的二維測試函數(shù)進(jìn)行了對比實(shí)驗(yàn)。測試函數(shù)為[12]：

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

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

3.3 ?分布式性能驗(yàn)證

為了進(jìn)一步驗(yàn)證基于組合模擬退火算法的考試任務(wù)分發(fā)系統(tǒng)的運(yùn)行效率，在集群環(huán)境下對系統(tǒng)的執(zhí)行效率進(jìn)行了對比。將無并行分發(fā)的考試系統(tǒng)和基于組合模擬退火算法的考試系統(tǒng)的運(yùn)行時(shí)間進(jìn)行比較。統(tǒng)計(jì)結(jié)果如表1所示，可以看出，隨著節(jié)點(diǎn)數(shù)量的不斷增大，獲得的加速效果越來越顯著。

從表1可以看出，隨著樣本文件的增大，兩者的運(yùn)行時(shí)間均緩慢上升，但從上升速度方面來看，本文算法優(yōu)于無并行分發(fā)的考試系統(tǒng)。在同等大小樣本集下，本文算法相比無并行分發(fā)的考試系統(tǒng)，在大規(guī)模分布式任務(wù)上表現(xiàn)更好。

3.4 ?系統(tǒng)具體實(shí)現(xiàn)

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

4 ?結(jié) ?語

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

參考文獻(xiàn)

[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的高?？萍紖f(xié)同管理綜合系統(tǒng)的研究與實(shí)現(xiàn)[J].煤礦機(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混合體系結(jié)構(gòu)的開發(fā)與應(yīng)用[J].電子設(shè)計(jì)工程，2015，23（14）：26?28.

[5] 李莉.基于UML的網(wǎng)絡(luò)分布式考試系統(tǒng)軟件建模[J].電子技術(shù)與軟件工程，2018（14）：55?56.

[6] 石亞妮.基于B/S構(gòu)架的遠(yuǎn)程教育學(xué)生在線考試系統(tǒng)設(shè)計(jì)[J]. 自動(dòng)化技術(shù)與應(yīng)用，2018，37（7）：52?55.

[7] 王莉.基于遺傳算法的高校在線考試系統(tǒng)研究[J].電子設(shè)計(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.