基于不等式方法的多目标遗传算法在排课问题中的应用研究

摘要

排课问题是一个多目标的复杂开放性问题,并且已经被证明是NP完全问题。基于排课在学校教学管理中的重要性,对排课问题的研究具有重要的现实意义。
　　多目标遗传算法是基于遗传算法的基本原理,结合多目标优化的理论和思想,解决多目标、多约束问题的算法。本文应用多目标遗传算法解决排课问题,主要从以下几个方面进行研究:
　　第一、从多目标、多约束简化出发,将排课问题分阶段进行,先分课室类型,把特殊要求的课程先编排,然后再排没有类型限制的课程。同时,采用实数编码,基于时间片的染色体编码,减少变量数量。
　　第二、应用不等式方法把多目标不等式问题转化为多目标优化问题,引入边界向量和辅助性能指标向量,应用非支配分类和改进的基于排序的适应度分配方法进行问题的求解和优化。
　　第三、在遗传算子的操作过程中,基于不可行解避免的原则,采用部分映射交叉的方法和修复策略,强化了算法的针对性。
　　本文讨论了基于不等式的多目标遗传算法的排课问题建模与排课算法,并通过比较和验证,证明了该排课算法是可行的,而且是比较优的多目标协同优化算法。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 课题的研究背景及意义

1.2 课题的发展及国内外研究现状

1.3 本文的主要研究内容

1.4 本文的组织架构

2 排课问题描述

2.1 排课问题概述

2.2 排课问题一般描述

2.3 现有的排课问题解决方案

3 基于不等式方法的多目标遗传算法概述

3.1 不等式方法简介

3.2 多目标遗传算法的研究现状

3.3 基于不等式方法的多目标遗传算法的优势

4 基于不等式方法的排课问题建模

4.1 排课问题定义

4.2 目标定义

4.3 可采纳边界的定义

4.4 辅助性能指标向量定义

4.5 Pareto支配和Pareto优化方案

4.6 排课问题的数学模型

5 基于不等式的多目标遗传算法的排课问题解决方案

5.1 排课问题编码设计

5.2 遗传算子的描述

5.3 目标函数的算法实现

5.4 非支配分类和改进的基于排序的适应度分配方法

5.5 基于不等式的多目标遗传算法

5.6 小规模测试分析

6 总结与展望

6.1 本文总结

6.2 展望

参考文献

致谢

攻读硕士学位期间发表的论文