基于不等式方法的多目标遗传算法在排课问题中的应用分析.docx

1绪论 11.1课题的研究背景及意义 11.2课题的发展及国内外研究现状 21.3本文的主要研究内容 21.4本文的组织架构 32排课问题描述 42.1排课问题概述 42.2排课问题一般描述 52.3现有的排课问题解决方案 63基于不等式方法的多目标遗传算法概述 83.1不等式方法简介 83.2多目标遗传算法的研究现状 83.3基于不等式方法的多目标遗传算法的优势 104基于不等式方法的排课问题建模 134.1排课问题定义 134.2目标定义 134.3可采纳边界的定义 154.4辅助性能指标向量定义 164.5 Pareto 支配和 Pareto 优化方案 164.6排课问题的数学模型 175基于不等式的多目标遗传算法的排课问题解决方案 185.1排课问题编码设计 185.2遗传算子的描述 205.3目标函数的算法实现 265.4非支配分类和改进的基于排序的适应度分配方法 285.4.1非支配分类和排序方法 285.4.2改进的基于排序的适应度分配方法 355.5基于不等式的多目标遗传算法 365.6小规模测试分析 396总结与展望 446.1本文总结 446.2展望 44参考文献 45致谢 48攻读硕士学位期间发表的论文 491绪论1.1课题的研究背景及意义系统理论是系统科学下面的二级学科，源自于系统科学，是一门复杂的交叉 学科。

以系统为研究对象，以科学的方法和现代技术为手段，寻求解决复杂开放 性问题的方法系统科学在中国的奠基人钱学森明确提出了系统科学的体系结 构，把整个人类作为一个系统进行研究而排课问题作为一个综合的系统问题， 也是学校管理中的重要问题，排课问题关系到学校的整体运作本课题是在长期 的教学实践和科研关注的基础上，基于系统科学的思想，以系统为研究对象，以 多目标遗传算法为手段，着眼于当前教学的实际，从资源优化的角度出发，寻求 更加高效且切实可行的问题解决方案遗传算法源于对自然和社会动态复杂系统适应性问题的研究，是一种求解优 化问题的适应性搜索方法其理论基础主要以收敛性分析为主，即群体收敛到优 化问题的全局最优解的概率遗传算法既是一种自然进化系统的计算模型，也是 一种通用的求解优化问题的适应性搜索方法通过建立适应过程的一般描述模型 和计算机模拟试验研究，分析系统对环境变化的适应性现象，是一种具体的算法 形式遗传算法和复杂适应系统(CAS)理论都是Holland提出的遗传算法的历 史背景和发展源泉仍是Holland关于自然和社会的复杂系统的适应性理论按照 Holland的定义，所谓系统的适应性就是在环境的作用下系统结构的不断改变的 过程。

虽然CAS理论是九十年代才提出来的，但它却是系统科学的一大重要理 论，也是圣菲研究所的一大特色其理论本质同出一辙，因此，用遗传算法解决 排课问题既符合决策优化的内在要求，同时也是科学可行的在实现机制上，遗传算法是一种离散动力学系统，在给定初始群体和遗传操 作的前提下，通过迭代实现群体的进化它尤其适用于处理传统搜索方法难于解 决的复杂和非线性问题，可广泛用于组合优化、机器学习、自适应控制、规划设 计和人工生命等领域排课问题是一个时间表问题，涉及的变量比较多且复杂，不仅包括时间、地 点、教师、学生等，而且还包含了较多的动态约束条件，比如班级、教师的一些 特殊要求，这些要求不是基本约束，但却通常情况下是必须满足的另外，教师、 班级本身也具有复杂性，比如每一位教师所能教的课程是有限的，一些课程只能 其中的某些教师能上班级安排的课程是必须循序渐进的，而不是随意的这些 都增加了排课问题的复杂性，使得排课问题成为一个完完全全的复杂开放性问 题1.2课题的发展及国内外研究现状多目标优化问题一直是科学和工程研究领域的一个难题和热点问题在国 外，已经提出的算法主要有Schaffer提出的“向量评估遗传算法”气 将它作为 对单目标遗传算法的改进，是一种非Pareto方法；Hajela等人提出的“可变目标 权重聚合法”田是另一种非Pareto方法；Fonseca等人提出的基于排序选择的“多 目标遗传算法”⑶是一种典型的Pareto方法，通过采用通用的GA方法框架来有 效地解决多目标问题；Horn等人提出的基于小生境技术的“小生境Pareto遗传 算法”⑷也是一种应用较多的Pareto方法，采用Pareto优胜关系进行锦标赛选择, 并使用适应度共享机制；还有Zitzler等人提出的“强度Pareto进化算法”回等。

这些都属于隐式积木块类型算法，还有诸如由Van Veodhuizen等人基于单目标 杂乱遗传算法的的概念推广移植而来的多目标杂乱遗传算法等显式积木块类型 算法而在国内，关于多目标遗传算法不管是理论还是应用方面的研究都比较缺 乏对于多目标问题，其解决方案通常情况下都不是单一的解，而是一套非劣解 或满意解已有的这些方法在现实问题中得到了广泛的应用，但是在求解问题时 存在目标数量、问题复杂度等的约束，因此，在处理高维、多模态等问题时难以 得到满意的结果，在决策支持方面效益不是特别明显，存在一定的局限性，鲁棒 性也较差，需要进行改进随着人工智能的发展特别是智能计算的应用，遗传算法应用于多目标优化问 题，并表现出高度的鲁棒性和决策的灵活性在排课问题研究方面，遗传算法也 有很多的应用和改进，如马永通过改进遗传算法设计中的编码方案和遗传算子 的实现方法进行优化，胡义伟等人⑻在算法中加入重生操作来实现优化，韦玉等 人⑼则将结合免疫规划，应用免疫遗传算法实现优化1.3本文的主要研究内容目前对遗传算法的研究无论是理论上还是实践应用中都存在诸多问题，理论 上，由于Wolpert和Marcteady的NFL (No Free Lunch)定理使得我们在面对遗传 算法应用时，不得不针对每一个应用领域研究相应的优化遗传算法。

对于多目标 问题，通常情况下都难以找到对所有目标都最优的解，而只能找到一组对所有目 标都是非劣的解或满意解同时，对实际问题的多目标模型描述也是一个值得探 讨的问题所以，对遗传算法的研究从一般的理论到有针对性的成熟算法研究都 存在值得探讨的问题，特别是针对越来越复杂的实际应用问题，针对某一类问题 建立一套可行的建模方法，并提出一类解决方案辅助决策，是当前解决优化问题, 辅助决策的重点，正是基于这个研究背景，这里主要以排课问题作为研究对象， 通过引入不等式方法，寻求解决问题的优化方案本文的研究主要利用计算机实验的手段，通过在多目标遗传算法中加入不等 式方法，对多目标遗传算法进行改进，并通过测试和比较，讨论基于不等式方法 在解决多目标问题中的作用，寻求一种具有较好决策意义的多目标遗传算法，满 足多目标优化问题的需求1.4本文的组织架构本文的研究基于不等式的方法，同时结合多目标遗传算法的优势，对排课问 题作新的探讨，主要研究结构如下：首先，在了解问题和综合分析的基础上，对排课问题和现有的解决方案进行 介绍；第二，对不等式方法和多目标遗传算法进行简单的介绍，并指出基于不等 式的多目标遗传算法在解决问题中的优势；第三，结合不等式的方法对排课问题 进行定义和建模，并给出了相关的算法，对排课问题进行描述；第四，提出解决 排课问题的基于不等式的多目标遗传算法，并对相关算子做了深入的讨论;最后， 给出结论，并提出进一步的研究方向。

图1-1文章结构图2排课问题描述2.1排课问题概述随着我国高等教育的发展，教育设施不配套的现象越来越突出，资源的合理 利用和优化成为一个典型的问题学校资源的状况制约着学校整体的发展，排课 问题是一个组合优化问题，也是一个资源合理、有效进行分配的一个过程，是教 学管理的重要环节它一方面规范着学校资源的分配和利用，另一方面又是对资 源分配状况的检验课程表的编排是学校教务管理中的一个重要的组成部分，同 时，教务管理还必须面对很多临时性的调课问题，教师和班级的一些合理要求等 所以，排课过程是一个在满足常规约束条件的前提下，对动态约束最大程度满足 的优化过程其中常规约束是指那些对应于问题可行域的基本约束条件，只有满 足那些条件的解才是可行解；动态约束是指那些条件如果满足则能够更好体现以 人为本的理念，也使得解更加合理和优化的条件所以，排课问题的解决过程就 是在寻求可行解的基础上，寻求满意解的过程排课问题是学校教务管理中最重要，也是最复杂的问题之一课程表编排主 要分为两个部分，一是根据各专业、不同年级授课任务确定各班课程，二是根据 每周的课时数、课室进行课程表的编排班级的课表由班主任或主管老师根据教 学大纲进行编排，这个过程通过手工操作也可以完成。

教务管理部门的工作人员 通过提前收集各校区、二级学院、系的开课情况，然后统一进行处理，确定哪些 课是一定要开的，哪些课可以做机动处理，然后统一安排学校的开课计划，再按 照开课计划进行排课所以对于第二阶段的课程编排，涉及到的变量主要包括： 时间、教师、班级、课室、课程、校区、院系、课室类型、以及一些其它特殊要 求等要素在课室和教师资源极大充分的条件下，学校的课程安排可以交由各院 系进行，各院系直接统筹本院系的教师和课室资源，进行统一调度就可以完成， 这样，排课的复杂性也就相对降低了但是，大多数情况下，由于学校招生的扩 大，课室很多情况下都成为排课问题中的紧缺资源，所以，争取课室资源的最大 利用率就成为排课问题的关键这种情况下，学校统一资源的安排通常是手工难 以很好地完成，需要协调各个因素，实现资源的优化配置目前，在资源优化问 题上主要采用的方法有：贪婪算法，规划论和遗传算法2.2排课问题一般描述多目标优化问题(MOP) 一般采用如下定义回：一般MOP由n个决策变量参数、k个目标函数和m个约束条件组成，目标 函数、约束条件与决策变量之间是函数关系最优化目标如(2.1)：minimize y =『(x )尸(fx ) , f ( x ), , f ( x ))s. t. e(x)=(et(x),e2(x),...em(x)) < 0 (2.1)其中 x=(X],x2,...xn)e Xy=(yi,y2，...,yn)e 丫这里x表示决策向量，y表示目标向量，X表示决策向量x形成的决策空间， Y表示目标向量y形成的目标空间，约束条件e(x) V0确定决策向量的可行取值 范围。

通常多目标优化问题的目标函数具有线性或者非线性性质，优化函数是将决 策向量X映射到目标向量y,记作F:QtA排课问题也是一个多目标问题，在排课问题的定义中包括了目标向量、决策向量和约束条件，排课问题是在多准则决策中寻求相互冲突的多目标间的折衷与 平衡，最终获得问题的满意解结合多目标优化问题的描述，对于由n个决策变 量参数、k个目标函数和m个约束条件组成，目标函数、约束条件与决策变量之 间是函数关系的排课问题，一般情况可以用(2.2)的数学公式进行描述：y = O(x)s. t. G(x)<0 (2.2)具中Q(x) = , G(x) = 一 , xg F o(pk(x)VO ^gm(x)<0①(x)为目标函数，即排课问题必须满足的目标；G(x)为约束条件，确定排课问题决策向量的可行范围；x为决策向量；F为所有课程n的集合排课问题 是求约束条件G(x)确定的可行范围内满足目标函数中(x)的排课 方案，排课问题的描述充分体现了排课问题的多目标特性及不等式特征由于排 课问题存在目标和约束的复杂性，相对于一般多目标问题，排课问题在处理约束 函数时表现为更复杂的关联约束关系，进一步增加了排课问题的复杂度。

2.3现有的排课问题解决方案国外对排课问题的研究比较早，从1963年Gotlieb提出了一个排课问题。