摘要
随着互联网技术的迅猛发展,网络已经融入到人们的学习和生活之中,高校校园网做为一个成功应用的实例,给高校的教学管理带来新的方式,也为高校教育活动提供一个发展平台,因此校园网是现代教学与管理中重要的部分。校园网的发展带着高等教育走进一个IT的时代。同时,意味着IT技术的应用在教育领域迎来一个崭新的阶段,为高等教学资源的整合、教学资源的共享、提高教学质量具有重要现实意义。
智能校园网利用网络技术进行教学与管理,实现网络化管理教学资源以及实现网络化教学、学生档案管理、学生网上考试、考试安排、成绩查询等一些日常教学活动。本文主要针对智能校园网中组卷问题及教学资源优化问题进行研究。组卷及教学资源优化是智能校园网应用中的重要组成部分,在日常的教学与教学管理中发挥着重要的作用。国内外的许多科研机构、学校都在对其进行研究。组卷问题是从试题库中选取符合用户要求的各种试题,而教学资源优化问题即排课问题是根据教学计划的要求设置每个学期的课程,将教师、学生、教室、多媒体教室等各种教学资源充分利用起来,安排合理、高效的教学时间表。因此它们都是典型的多约束问题的求解过程,这类问题利用智能算法一般可以求得满意的解。
粒子群算法是一类通用的优化算法,但对于特定问题的局部搜索能力较弱,易陷入局部极值。因此,本文在粒子群算法的基础上引入模拟退火算法来解决组卷问题与教学资源优化问题,同时加入了遗传算法中的交叉操作与变异操作,以提高算法的整体质量和效率。具体而言,粒子群算法进化为模拟退火算法搜索提供一组具有较好的质量和分散度的初始解,采用模拟退火算法机制进行局部领域搜索,不仅是对粒子群算法搜索的补充,有利于优化解,使算法具有概率突跳的能力,实验结果表明可以得到较满意的结果。
本文的主要工作是：对粒子群算法、改进的粒子群算法、模拟退火算法以及遗传算法进行分析；掌握这些算法的基本原理及适用范围；确定组卷问题及教学资源优化问题的目标函数；提出离散的粒子群算法与模拟退火算法相结合；并采用遗传算法中的交叉操作与变异操作的思想来解决组卷问题与教学资源优化问题。在相同的实验数据下,以离散粒子群算法及改进的离散粒子群算法分别对组卷及教学资源优化问题试验,对得出的数据进行对比,实验结果证明改进的离散粒子群算法在解决组合优化问题上是具有一定的优势的。
With the rapid development of Internet technology, the network has been integrated into learning and life of people, Network of campus is one example of successful application. At the same time, network of campus has brought new ways of teaching management about universities, it provides development platform for college education, therefore, it is an important part in modern education and management. The development of the network of campus has entered into a higher education IT era. The application of IT technology in the field of education had entered a new phase and had important actual significance for the integration of teaching resources, the share of teaching resources and the improvement of teaching quality.
Intelligent campus network use network technology for teaching and management, the network manage resources of school; The network manage teaching, student records management, optimize the management of teaching resources, student online examinations, examination arrangements, result inquiry and some other daily teaching activities. In this paper, test paper and the teaching resource optimization issues in the intelligent campus network mainly research objects. It is an important part of the intelligent of campus that test paper and teaching resource optimization Management, In daily teaching and teaching management, the intelligent campus network plays an important role. Many domestic and foreign research institutions, schools all study the network of campus.As test paper is various of questions that user require to select from question library.Teaching resources optimization problem take full advantage of teachers, students, classrooms, multimedia classrooms and other teaching resources according to the requirements of teaching to set the courses of each term, arrange a reasonable and efficient time schedule of teaching. Therefore, they are typical and more constrained problem with solving process, such problems can generally be obtained by using smart algorithms satisfactory solution.
PSO is a class of general optimization algorithm, the local search for the specific problem is weak, its ability avoid poor local minimum. Therefore, this paper introduced simulated anneal algorithms based on PSO solving test paper problem and teaching resources optimization problem, adopted crossover variation operation improving the whole quality and efficiency. In particular, PSO evolutionary provides the initial solutions with a set of good quality and dispersion for the SA, SA mechanisms are used to search local areas for these solutions, which is the complement for PSO search and help to optimize solutions, and give the algorithm a probabilistic jumping ability, experimental results show that satisfactory results can be obtained.
The main contents of this paper:analyzed particle swarm algorithm;the improved particle swarm algorithm;simulated annealing algorithm and genetic algorithm; mastered the basic principle and suitable scope; determined test paper and the target function of teaching resources optimization problem; proposed discrete particle swarm algorithm combining with simulated annealing algorithm; adopted the ideas of the crossover operation and variation operation in genetic algorithm sloving test paper problem and teaching resources optimization problem. In the same experiment data, the article analyses the genetic algorithm, discrete particle swarm optimization, and improvement of the hybrid algorithm algorithm to solve Test-Paper problem and teaching resources optimization problem and compare the obtained data. The experiments proved that the improved discrete particle swarm algorithm had certain advantages in solving combinatorial optimization problem.
引文
[1]刘波,王凌.微粒群优化与调度算法[M].清华大学出版社,2008.
[2]权金娟,温显斌,张桦,张颖.软计算及其应用[M],科学出版社,2009.
[3]Eberhart R C, Kennedy J. A discrete binary version of the particle swarm alg-orithm[Z]. Proc.of the World Multiconference on Systemics, Cybernetics and Inf-ormatics.1997:4104-4109.
[4]张长胜.求解规划、聚类和调度问题的混合粒子群算法研究[D].长春：吉林大学,2009.
[5]M.Clerc:Discrete Particle Swarm Optimization, A Fuzzy Combinatorial Black Bo x[OL]. http://clerc.maurice.free.fr/pso-/Fuzzy_Discrete_PSO/Fuzzy_DPSO.html.
[6]M.Clerc:Discrete Particle Swarm optimization, illustrated by the Traveling Sales man Problem[C].New Optimization Techniques in Engineering.Heidelberg, Germa ny,2004,219-239.
[7]Kennedy J, Eberhart R C.A discrete binary version of the particle swarm algor ithm.IEEE Press,1997:4104-4108.
[8]胡艳军,许耀华,张媛媛.基于离散粒子群算法的CDMA多用户检测方法[J].通信学报,2005,26(7)：109-122.
[9]de Jong K A.An analysis of the behavior of a class of genetic adaptive system. Doctoraldissertation[D].University of Michigan,1975.
[10]高洪元,庞伟正,杨红孺等.基于离散粒子群优化算法的多用户检测器,哈尔滨工业大学学报[J],2005,37(9)：1303-1306.
[11]Jiao L, Wang M, Yang S. A quantum particle swarm optimization.Proceeding of the 2004 IEEE Congress on Evolutionary Computation,2004:320-324.
[12]Chen A L, Wu Z M, Yang G K.Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem[J], 浙江大学学报,2006,7(4): 607-614.
[13]Angeline PJ.Using selection to improve particle swam optimization[C].IEEE Int ernational Conference on Evolutionary Computation, Anchorage,1998:84-89.
[14]Krink T, Lovjerg M, Rasmussen T K. Hybrid particle swarm optimizer with breeding and subpopulation. Proceedings of the Third Genetic and Evolutionary Computation Conference[C],2001:607-614.
[15]高鹰,谢胜利.基于模拟退火的粒子群优化算法[J].计算机工程与应用,2004,1：47-50.
[16]纪震,廖惠连等.粒子群算法及其应用[M].科技出版社,2009.
[17]刘怀亮.模拟退火算法及其改进[J].广州大学学报,2005.
[18]王知人.一种改进的模拟退火算法[J].高等学校计算数学学报,2006.
[19]Gelan C D, Kirkpatrick S, Jr Vecchi M P.Optinization by simulated annealing [Z].Science,1983:671-680.
[20]Aragon C R, Johnson D S, Mcgeoch L A et al.Optimization by Simulated A nnealing[Z].an Experimental Evaluation,1987.
[21]Aarts E, Korst J.Simulated Annealing and Boltzmann Machines[Z].John Wiley& Sons,1989.
[22]谢云.模拟退火算法综述[J].微型计算机,1998.
[23]梁艳春,周春光.计算智能[M].吉林大学出版社,2009.
[24]李战怀,朱剑冰,赵娜.基于混合遗传算法的自动组卷问题的研究[J].计算机仿真,2009.
[25]林焰,孙晓雅.一种新的离散粒子群算法在指派问题的应用[J],计算机研究,2009.
[26]杜焱,刘英,王琰,张嘉易.基于自适应算子的遗传算法多目标智能组卷[J],计算机应用,2008.
[27]洪毅,王联国,余冬梅,赵付青.一种模拟退火和粒子群混合优化算法[J],计算机仿真,2008.
[28]刘光远,温万惠,王文峰.求解TSP问题的混合离散粒子群算法[J].西南大学学报,2007,29(1)：85-88.
[29]黄锟.大学课程表问题中的算法研究与应用[D].中南大学,2008.
[30]陈章辉,黄小晖,康烈,任文艺.基于双倍体遗传算法求解大学排课问题[J].计算机应用,2008.
[31]郑月锋.遗传算法在求解时间表问题中的应用研究[D].浙江：浙江工业大学,2005.
[32]邓辉文,滕姿,杨久俊.基于遗传算法的排课系统的设计与实现[J].计算机应用,2007.