计算机应用考试系统的模拟退火算法研究

来源:用户上传      作者:

　　摘  要： 针对传统计算机应用考试系统在大规模应用时存在的任务并发拥堵问题，提出一种基于并行组合模拟退火算法的分布式计算机应用考试系统，以便提高分发效率和访问容量。该系统采用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]。现阶段，针对计算机应用的相关课程考试系统已经不少，但是大多数仍旧采用C/S架构，需要在所有的客户端上安装考试软件，并要适用于各种客户端设备，这对软件开发的难度和后期维护工作量都是较大的考验，导致应用成本居高不下[3]。此外，当应用于大规模考试情况时，由于学生数量较多、时间较为集中、服务器资源有限等问题，导致常常发生并发冲突、无法访问和延迟卡顿等不良现象，需要增加软硬件投入来有效改善此问题[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.
转载注明来源:https://www.xzbu.com/8/view-15245404.htm