高等教育系统资源配置混合优化策略

摘 要：高等教育系统资源配置优化,不仅能提高教育资源的效益,而且还可以改善教育的质量,对提高高等教育的竞争力和可持续发展具有非常重要的意义.该系统资源配置优化问题是一个含有连续变量和离散变量的资源组合优化问题,属于最优潮流问题的一个研究领域.为提高解的质量与计算效率,给出了混合使用贪婪算法与遗传算法的解决方案：利用贪婪算法优势,获得该结构的初始资源分配解空间,由于算法的特性,空间规模被最小化.然后,利用遗传算法将初始解空间进行全局择优,提升其使用效益.

关 键 词：高等教育系统资源配置贪婪算法遗传算法

中图分类号：TP301.6文献标识码：A

一、引言

高等教育系统主要包括管理子系统、科类子系统、层次子系统、区域子系统等.各子系统内又分诸多要素,如管理子系统分专任教师结构、教学设备总量、教育经费投入额等要素.各要素又可按层级进行多维向量分解,如专业教师结构要素,可按职称系列划分为：高级教师、中级教师、初级教师；区域子系统中的经济环境要素,可按经济发展状态划分为：发达地区、中等发展地区、不发达地区等.每个要素还具备若干属性,包括能力属性（如：高级教师普遍具备较强的教学科研能力,中级教师次之,初级教师较弱）、生命周期属性（如：高级教师平均年龄偏大,作为资源的可利用时间最短,中级教师次之,初级教师较长）、离散度属性（在资源的生命周期内,同一资源重复使用的时间间隔越均衡,其利用效能越大）.

把各种子系统中的基本要素当作办学资源,组成资源结构模型.那么,我们要解决的问题是：在各种资源的生命周期内,如何对所有相关资源进行最优组合分配,以资源的执行时间最短为前提,克服资源争用冲突,尽可能提高其综合利用效率.

该资源结构模型中的参数分为连续变量和离散变量二类.资源中的向量为连续变量（如高级教师、中级教师、初级教师）,资源向量的属性为离散变量（如量能比、离散度、生命周期）.连续变量与离散变量共存的混合结构优化问题,属于最优潮流问题的一个研究领域,是目前组合优化研究领域的重点,具有实际应用价值,但也是非常困难的领域.对于这类多目标组合优化的难解问题,从20世纪70年始至今,各种算法研究一直非常活跃.近年来,随着计算机的发展,产生了一类新兴的算法技术——智能优化技术.

二、混合优化策略

优化高等教育系统配置的内容,可转化为对资源的合理分配与提升资源的使用效率二个方面进行综合考量.具体表现为,资源量化总值越高,则该结构优化度越高.

从求解难度分析,由于该组合结构具有多目标、强耦合、参数时变、非线性等特点,对其进行优化的时间复杂性函数可以表示为：

time等于f(ga1,ga2,等,gan,TS)(1)

其中：ga1,ga2,等,gan分别代表结构模型中的各种资源,TS表示资源使用时所处的位置,对应各子系统资源利用时间片数目,time表示对系统资源配置优化模型通过编程实现后,在计算机中进行求解所用的时间.函数f是一个指数函数,即当自变量增大时,其函数值time呈指数量级递增.可见,该难解问题的求解算法是否可行,不但取决于能否达成优化目标,还应尽可能减小其运算量,使time足够小.

贪婪算法有局部择优特性,能有效减少运算量,快速产生一个初步匹配的解,但未考虑全局择优.遗传算法具有全局择优特性,却存在初始种群很难产生的缺陷.

综合贪婪算法和遗传算法各自具有的优缺点,可采取“扬长避短”的混合算法求解策略：

①贪婪算法初步匹配

检测设高等教育系统资源配置各子系统的资源总数为S,以排列方式确定各资源优化次序,每个序列当作一个局部意义下的优化准则,共可得到.

根据贪婪算法,以每一个资源优化序列为优化规则,依次取该序列下的一个资源,以该资源在当前位置下效能最大化为目标,对其资源要素的向量进行最优匹配.当序列中全部资源要素向量的结构匹配完成后,就可获得基于该优化规则下的一个最佳综合资源向量结构体.据此,可获得S!个不同规则系列条件下的最佳资源向量结构体.

这些结构体构成高等教育系统资源配置模型的初步匹配解空间.

②遗传算法全局择优

用①所获得的初步匹配解集合作为初始种群,该种群数为S!.

通过对染色体实施选择、交叉、变异等遗传进化操作,使其适应度值不断升高,汰弱留强.最终使个体进化（染色体适应度值逐步递增收敛于近似最大值）到近似最优状态.

算法结束后,适应度值最大的染色体结构可作为高等教育系统资源配置模型的近似最优解.

1.贪婪优化初步匹配

（1）贪婪算法初始资源搜索匹配

匹配流程：

①初始化,取一个优化序列.

②按资源编号顺序取序列中的一个资源,以该资源所需完成的目标任务为依据,在资源队列中搜索能完成该目标任务的其它资源,生成当前资源的后备资源库,转③.

③以当前资源利用效能最大化为目标,搜索该资源的向量结构,若搜索成功,转④,否则转⑤.

④将满足条件的当前资源向量结构存入匹配结果队列中,资源编号加1；判断是否满足当前搜索序列的结束条件,若条件满足时,产生该优化序列对应的资源向量结构体,资源编号初始化,序列编号加1,转⑥；若不满足该搜索序列的结束条件,转②.

⑤从该资源的后备资源库中任选一个资源替换当前资源,转③.

⑥判断是否满足算法的结束条件,若满足,转⑦,否则转①.

⑦获得资源初步匹配解空间,算法结束.

（2）消除冲突算子

资源结构向量中包含了资源的生命周期属性.将资源的生命周期划分为时间片单位（资源的利用时间分布）.对资源冲突作如下定义：在资源匹配向量结构体中,若同一时间片单位中重复出现了相同的资源,则认为该资源存在争用冲突.

依次提取解空间中的每一个解(资源向量结构体),执行如下资源冲突消除算法：

①选一个解,按当前资源编号顺序取出当前资源的向量结构.

②向后搜索以该资源同名且时间片相同的资源,若找到转③,否则资源编号序加1,判断算法结束条件,若满足转④,不满足转①.

③从该资源的后备资源库中任选一个资源替换当前资源,时间片不变,转②.

④该资源结构体的冲突消除.

2.遗传优化全局策略

初始种群通过贪婪算法产生以后,对种群实施遗传进化操作.以下对本遗传算法的关键部分进行简要阐述.

（1）染色体的编码结构

S个资源的向量所构成的组合结构为染色体,以资源计划的开始执行时间为变量,染色体中每一段基因都表示成一种资源向量的相对开始时间：TS＇等于TS-ES.TS＇≥0,TS为资源利用终止时间,ES为使用周期.以自然数编码,将每种资源按顺序排列.染色体的长度就是资源的总数S.将每种资源引入TS后构成染色体编码.

（2）适应度函数

在遗传算法中,种群进化以适应度函数为依据,这是问题求解品质的测量函数,代表个体的生存能力,需要根据求解对象进行构造,该函数构造的好坏,影响算法的收敛速度和搜索结果.

（3）选择算子

选择算子：为保持染色体的优良品性,适应度值大的染色体被选概率也较大.通常,用赌方法进行实现.

（4）交叉算子

交叉算子：杂交操作发生在选配个体中的相应染色体之间,检测设染色体交叉概率与染色体的适应度值成正比,以被选染色体作为父代,按资源结构链进行交叉配对.生成两个新的个体,交叉位置是随机选择的.采用父代与新生代同时竞争的策略,取高适配值的两条染色体保存到下一代中.

（5）变异算子

变异算子：变异操作发生在同一染色体中的二个基因位之间.即对所选的变异个体中随机产生一个行,在该行中任选二个资源结构的时间片值进行互换.

（6）算法终止条件

算法终止条件通常根据适应度值持续进化若干代无变化情况,进行测试设定.

三、混合优化流程

混合算法流程如下：

①将资源结构的相关参数进行编码.

②贪婪算法初始化种群X(t)等于(X1,X2,等,XS!),t等于0,S!为种群规模.

③对当前种群X(t)中每个染色体Xi计算其适应度值f(Xi),适应度值的大小表示了该染色体性能的优劣.

④应用选择算子产生中间代Xr(t).

⑤对Xr(t)应行交叉、变异算子,产生新一代种群X(t+1),这些算子的目的在于扩展染色体的覆盖面,实现全局择优的思想.

⑥迭代进化,代计数器t加1,转步骤⑦,如果未满足终止条件,转步骤③.

⑦输出近似最优解.

结论：优化高等教育系统资源配置主要包括对资源的合理分配和提高资源使用效率二方面内容.本文通过运用贪婪算法使资源快速分配,这些分配方案在所构造的最优度量标准（在某确定的资源优化次序）下是局部最优的.然后利用遗传算法所具有的全局择优的特性,对初始分配组合的资源结构进行全局优化配置,整体提升其结构的优化度.

[4]费春国,韩正之.一种改进的混沌优化算法[J].控制理论与应用,2006,23(3):471-474