自适应遗传算子解决排课问题的研究

时间：2025-07-09

遗传算法

内蒙古大学

硕士学位论文

自适应遗传算子解决排课问题的研究

姓名：白雪松

申请学位级别：硕士

专业：计算数学

指导教师：行飞

20090520

遗传算法

内蒙古大学硕士学位论文

摘要

现代科学理论研究与实践中存在大量与组合优化、自适应等相关的

问题。使用常规方法解决这些问题，除了一些简单的情况之外，人们对于大型复杂系统的优化和自适应问题显得无能为力。遗传算法借鉴生物界自然选择和自然遗传机制，使用群体搜索技术，尤其适用于处理传统搜索方法难以解决的复杂的和非线形的问题。经过近４０年的发展，遗传算法在理论研究与实际应用中取得了巨大的成功，但相对其鲜明的生物基础，其数学基础还是相对不完善的。

摘要排课问题是典型的多重约束和组合优化问题，并且早在７０年代

已经被证明是一个ＮＰ完全问题。遗传算法是一种借鉴生物界自然选择和进化机制发展起来的自适应随机搜索算法。它具有良好的并行性、通用性、稳定性，是一种比较有效的解决ＮＰ完全问题的方法。本文将遗传算法应用于求解排课问题，主要进行了以下几个方面研究工作：首先，系统分析了排课问题的各要素及多重约束条件，提出了排课问题的求解难点和优化目标。其次，着重分析比较常用的遗传算法编码方案并研究其在排课系统中的应用，在综合各种编码方案优缺点基础上，设计了一种更适合解决排课问题的编码方案。较之传统编码方案，该编码方案更简单、更高效、更易于理解。并且，根据设计的编码方案，重新设计了与之对应的交叉算子和变异算子。

关键词：排课问题，遗传算法，编码方案，多重约束

遗传算法

ＳＥｌＦ—ＡＤＡＰＴＡＴＩＯＮＧＥＮＥＴＩＣＧＥＮＥＴＩＣＯＰＥＲＡＴＯＲＳＴＯＳＯＬＶＥ

ＣＵＲＲＩＣＵＬＵＭＳＣＨＥＤＵＬＩＮＧＰＲＯＢＬＥＭ

ＰｄＢＳＴＲＡＣＴ

Ｔｌｌｅｒｅａｒｅｓｔｉｌｌｍａｎｙｉｓｓｕｅｓｔｏｂｅｔａｃｋｌｅｄｗｉｔｈｉｎｍｏｄｅｒｎｓｃｉｅｎｔｉｆｉｃ

ｔｏｔｈｅｏ巧ｒｅｓｅａｒｃｈａｎｄｐｒａｃｔｉｃｅ，ｗｉｔｈｒｅｇａｒｄ

ｓｅｌｆ－ａｄａｐｔａｔｉｏｎｅｔｃ．Ｒｏｕｔｉｎｅ

ａｎｄｍｅｔｈｏｄｓＣｏｍｂｍａｔｉｏｎ＆Ｏｐｔｉｎ此ａｔｉｏｎｑｕｉｔｅｈｅｌｐｆｕｌｂｕｔ

ｏｎａｌｌｄａｒｅｒｅｓｏｌｖｉｎｇｈｅｌｐｌｅｓｓｓｉｍｐｌｅｆｏｒｏｐｔｉｍｉｚａｔｉｏｎｓｅｌｆ－ａｄａｐｔａｔｉｏｎｐｒｏｂｌｅｍｓｃｏｍｐｌｉｃａｔｅｄｌａ唱ｅ－ｓｅａｌｅｓｙｓｔｅｍｓ．ＧｅｎｅｔｉｃＡｌｇ。ｒｉｔｈｍｓ；ｂａｓｅｄ

ｍｅｃｈａｎｉｓｍ。ｆｎａＩｕｒａｌ

ｔｅｃｈｎｏｌｏｇｙ，ｉｓｔｈｅｂ。ｉｏｌｏｇｉｃａｌｓｅｌｅｃｔｉｏｎ＆ｈｅｒｅｄｉｔｙａｎｄｌｅｖｅｒａｇｉｎｇｃ。１。ｎｙａｐｐｌｉｃａｂｌｅｆｏｒ