◆徐 述

（湖南城市学院信息科学与工程学院 湖南 413000）

基于粒子群算法高校考试优化安排的模型建立与算法设计

◆徐 述

（湖南城市学院信息科学与工程学院 湖南 413000）

本文根据高校考试安排问题的约束条件，对高校考试优化安排进行了研究，用任务表示某门课程针对某个班级的监考，高校考试优化安排问题被描述为针对教师、教室、时间、课程与班级的五个子服务，带约束的服务组合问题，以最小化任务滞后时间与任务制造期为优化目标。并结合问题特性，建立了考试优化安排的多目标优化运筹模型，然后设计了求解该问题的粒子群算法。

考试优化；多目标优化；运筹模型；粒子群算法

0 引言

高校考试安排是一项各类教学资源冲突的调度工作，利用教学资源，安排考试任务，对维持教学秩序，提高教务管理水平有着积极意义。目前，国内外学者对考试优化调度问题的相关研究甚少。本文以高校考试优化安排为研究对象，构造基于粒子群算法的优化模型与算法。

1 问题描述

考试安排问题是时空与人力资源互为制约的优化决策问题。涉及班级、课程、教室等教学资源基本因素。这种调度必须满足一定的约束条件，例如，考试班级学生人数与教室容量要相匹配，同一课程相关班级的考试时间应该相同等等。

本文的目标是集中时间利用教室组考，提高高校考试管理效率。

1.1 考试安排问题参数描述

设F代表监考教师，i为教师总数。教师记为Fz，将其依次编号为F1…Fi，某教师Fz∈[F1..Fi]。

设C代表课程，j为课程总数。课程记为Cx，依次编号为C1…Cj，某课程Cx∈[C1..Cj]。

设N代表班级，k为班级总数。班级记为Ny，依次编号为N1…Nk，某班级Ny∈[N1..Nk]。

班级号为k的班Ny开设了Cx课程，对应一个任务S（即具体一堂考试），n为任务总数。将任务依次编号为S1…Sn。某任务Sw∈[S1..Sn]。

设R代表教室，e为教室总数。教室记为Rv，将其依次编号为R1…Re。某教室Rv∈[R1..Re]。

设Time代表时间。对于考试，分为上午、下午、晚上三个时间段，依次编号为0-1，1-2，2-3。tw表示任务Sw开始的时刻，tw∈[0，1，2]。

Tw表示任务Sw滞后期，若某考试任务安排在2-3时间段，则该任务定义为滞后，该任务所耗时间为滞后时间。Tw∈[0，1]。 Fw表示任务Sw实际完成时间。表示教室Rv最后一项任务完成时间。∈[1，2，3]；Fmax表示制造期，即最后一堂考试离开的时间；Pw为监考任务持续的时间。

1.2 考试安排问题约束条件

条件1，同一个时间段，某位监考教师只能在一个教室监考。

条件2，同一个时间段，某个班级只能在一个教室里完成考试。

条件3，选修同一门课程的所有班级，在同一时间段完成考试。

条件4，为不影响学生的学习效率与休息，课程考试尽量不安排在晚上。

1.3 考试安排问题描述

考试安排调度问题可用三元组α/β/γ来描述，表述如下：

（1）考试资源环境（α域）

教室容量为e。考试针对行政班级，所以每个教室都有能力完成任务。

（2）任务特征与约束（β域）

设监考任务Sw的预期完成时间fw（期望值）。理想状态是所有任务都能在白天完成，故fw=2。

监考任务Sw作业时间实际为90～120分钟，即每个时间段只能完成一次监考任务，将其视为单位时间Pw=1。

（3）调度目标（γ域）

0-1（上午）时间段监考第一堂考试，依此类推。若2-3（晚上）时间段有监考，则定义该监考任务为滞后，Tw= max（Fw-fw，0）= max（Fw-2，0），Tw∈{1，0}。

制造期Cmax是最后一项任务离开系统的时间。用下列公式表示：最小化制造期Cmax可以让学生有整块的空余时间支配。

2 粒子群算法

2.1 粒子群算法

粒子群优化算法[1]（Particle Swarm Optimizer，PSO）由Kennedy和Eberhart提出。其基本思想源于对人工生命和鸟群捕食行为的研究，是一种种群全局搜索策略，它通过粒子搜寻自身的个体最优解和粒子群体的全局最优解来完成更新优化。

2.2 多目标粒子群算法

现实中经常遇到使多个目标在给定区域上同时尽可能最佳的优化问题，也就是多目标优化问题（Multiobjective Optimization Problem，MOP）。粒子群算法在很多情况下，比遗传算法更有效率，所以研究PSO在多目标优化问题中的应用很有意义。已有一些基于PSO算法求解多目标优化问题的算法被提出，如Hu等应用了动态邻近的PSO算法[2]，Parsopoulos等应用了权重聚合的方法来求解多目标优化问题[3]。

一般情况下，MOP的各个子任务是相互冲突的。MOP的解并非唯一，而是存在一组最优解集合，集合中的各个元素称为Pareto最优解或非劣最优解。PSO算法在处理多MOP时，主要是解决群体和自身最佳位置对于群体最佳位置的选择。PSO算法在处理约束时，多采用惩罚函数法。Parsopoulos等人提出利用惩罚函数作为粒子适值[4]，使得PSO能够解决多目标约束优化问题。

3 考试安排优化调度模型设计

本文的考试安排调度问题可以表述为最小化滞后时间和制造期为目标[5]，具有加工时间约束的并行同速机。构建模型如下：

式（1）为目标函数，调度目标最小化Fmax和滞后时间和 wT∑。式（2）为约束条件，表示教师Tz在时间tw只能在某间教室Rv监考；。某班Ny某课程考试Cx在时间tw只能在某教室由某教师监考完成。式（3）保证所有监考任务都有机会开始。式（4）设某课程Cx有ax个班开设了课程，该课程的ax个班考试在同一时间完成tw。式（5）所有的课程Cx对应的考试门数ax之和等于监考任务n。式（6）给出任务Sw的滞后时间与制造期。式（7）给出决策变量d的取值范围。

4 算法设计

4.1 编码设计

根据本文建立的考试优化安排模型，将目标函数问题的可分解空间假想为N维搜索空间。用以下二维数组表示位置向量L和速度向量V。

在位置向量L中，对应每门课程Cx对应ax个班级考试，课程Cx有j门，所以将位置向量与速度向量分成j个区域进行优化。速度向量V中，其中。此取值范围只适用于初始速度。

4.2 粒子位置和速度迭代

4.3 多目标粒子群考试安排优化调度算法

基于考试安排优化调度，多目标粒子群算法表述如下：

①初始化粒子群，种群大小为N，构造位置和速度向量（编码），分派规则产生初始种群。

②计算每个粒子的评价函数值。

③找到每个粒子所对应的局部最优解以及全局最优解。④根据式（8）（9）更新粒子速度和位置。

⑤未达到迭代次数转步骤2，达到迭代次数结束。

5 结束语

本文对高校考试优化安排进行了研究，建立起考试优化安排的多目标优化运筹模型，设计出求解该问题的粒子群算法，为下一步算法实现与算法分析打下基础。

[1]J．Kennedy，R．Eberhart，Particle swarm optimization [C]．Proc．IEEE Int．Conf．on Neural Networks，Perth，Australia，19 95．

[2]X Hu，R C Eberhart．Multiobjective optimization using dynamic neighborhood particle swarm optimization．IEEE Con gress on Evolutionary Computation（CEC 2002），Honolulu，Hawaii，USA，2002．

[3]K E Parsopoulos，M N Vrahatis，Particle swarm opti mization method in multiobjective problems[J]．In Proc of the ACM Symp on Applied Computing 2002（SAC 2002）．Ne w York ACM Press，2002．

[4]薛洪波，伦淑娴．粒子群算法在多目标优化中的应用综述[J]．渤海大学学报（自然科学版），2009．

[5]曹策俊，杨琴，李从东．求解高校教室调度问题的混合粒子群算法[J]．计算机应用研究，2012．

[6]杨维，李岐强．粒子群优化算法综述[J]．中国工程科学，2004．