[课题研究的基本操作]基于蚁群算法的排课问题的研究.doc

[课题研究的基本操作]基于蚁群算法的排课问题的研究 71 篇一 : 基于蚁群算法的排课问题的研究 71 分类号 ＵＤＣ密级１０１５１单位代码 基于蚁群算法的排课问题的研究 赵惠怡 指导教师傅英亮职称副教授 学位授予单位大连海事大学 中请学位级别硕士学科与专业计算机软件与理论论文完成日期２００７—１论文答辩日期２００７．３答辩委员会主席 中文摘要 摘要 为了保证教学质量，学校必须制定一套规范的教学计划，而课表编排是教学计划得以顺利执行的重要一环。随着高校学生数量猛埔，数据规模大、各种约束复杂，在教学资源一定的情况下排课越来越繁难。人丁排课已经雉以完成课表编排的工作要求。因此，利用计算机解决排课问题成为当务之急。 蚁群算法是近十几年才提出来的种新型模拟进化算法，通过候选解组成的群体的进化过程来寻求最优解。该过程包括适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构；在协作阶段，候选解之间通过信息交流以期产生性能更好的解。蚁群算法通过正反馈和负反馈相结合的机制使算法朝着最优解方向发展，又保持有哪些信誉好的足球投注网站范围避免过早停滞。从而得到一定程度上的满意解。 本文对基本蚁群算法的思想及原理进行了分析，结合排课问题的自身特点提出一种适于排课问题的改进的蚁群算法。在此，对排课问题进行了抽象，将解决排课问题转化为寻求二部图的昂人匹配问题，由于排课问题可以描述为图结构，这给蚁群算法介入排课问题提供了一个契机。而如何满足排课问题中的多种约束条件是排课问题的关键问题，在此算法中引入个体启发信息等笫略。考虑把这些约束具体抽象成一些合适的数宁，适当时候用这些数字来修ｉＦ二部图中边上的权 本文不仅存理论＿Ｅ＝论述了蚁群算法解决排课问题的方法。而日存此基础上使关键词：排课问题；二部图；蚁群算法值，达到间接修改蚁群算法的期望启发因子，配合蚁群寻求课表最优解。用ＶＢ实现了一个基于蚁群算法解决排课问题的实验测试程序。测试结果表明蚁群算法能够很好地解决排课问题，排出商质量的课表。文中还通过采集实验数据对文中所述案例的参数选择提出了建议。本文旨在拓宽排谦算法解决方案，同时推广蚁群算法的应用面。 英文摘要 ＲｅｓｅａｒｃｈｏｆＣｏｕｒｓｅｓＡｒｒａｎｇｅｍｅｎｔＢａｓｅｄ ＡｌｇｏｒｉｔｈｍｏｎＡｎｔＣｏｌｏｎｙ Ａｂｓｔｒａｃｔ Ｉｎｏｒｄｅｒｔｏｅｎｓｕｒｅｔｈｅｑｕａｌｉｔｙｏｆｔｕｉｔｉｏｎ，ａｕｎｉｖｅｒｓｉｔｙｍｕｓｔｅｓｔａｂｌｉｓｈ ｃｏｕｒｓｅｓａｓｅｔｏｆｎｏｒｍａｌｔｅａｃｈｉｎｇｐｌａｎｓ，ｗｈｉｌｅａｒｒａｎｇｉｎｇｉｓａｎｉｍｐｏｒｔａｎｔｓｔｅｐｏｆｃａｒｒｙｉｎｇｏｕｔｔｈｅｔｅａｃｈｉｎｇ ａｒｅｐｌａｎｓｕｃｃｅｓｓｆｕｌｌｙ．Ｗｉｔｈｔｈｅｉｎｃｒｅａｓｉｎｇｑｕａｎｔｉｔｙｏｆｃｏｌｌｅｇｅｓｔｕｄｅｎｔｓ，ｔｈｅｓｃａｌｅｏｆｄａｔａ ｈｕｇｅ，ａｎｄａｌｌｋｉｎｄｓｏｆｃｏｎｓｔｒａｉｎｔｓａｒｅｃｏｍｐｌｅｘ，ｃｏｕｒｓｅｓａｒｒａｎｇｅｍｅｎｔｂｅｃｏｍｅｓｍｏｒｅ ｂｙａｎｄｉｓｍｏｒｅｄｉｆｆｉｃｕｌｔｉｎｔｈｅｌｉｍｉｔｅｄｔｅａｃｈｉｎｇｒｅｓｏｕｒｃｅｓ．Ａｒｒａｎｇｉｎｇｃｏｕｒｓｅｓ ｓｏｌｖｅｔｈｅｃｏｕｒｓｅｓｈａｎｄｉｍｐｏｓｓｉｂｌｅｔｏｆｉｎｉｓｈｔｈｅｗｏｒｋ．Ｔｈｅｒｅｆｏｒｅ，ｉｔＳｕｒｇｅｎｔｔｏａｒｒａｎｇｅｍｅｎｔ ｗｉｔｈｃｏｍｐｍｅｒ． Ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｉｓａｎｅｗｋｉｎｄｏｆｓｉｍｕｌａｔｅｄｅｖｏｌｕｔｉｏｎａｌｇｏｒｉｔｈｍｗｈｉｃｈｉｓｐｕｔｆｏｒｗａｒｄｉｎｎｅａｒｄｅｃａｄｅｙｅａｒｓ．Ｉｔｓｅｅｋｓｔｈｅｏｐｔｉｍａｌａｎｓｗｅｒｆｒｏｍｔｈｅｃｏｌｏｎｙｅｖｏｌｕｔｉｏｎｐｒｏｃｅｓｓｗｈｉｃｈｉｎｃｌｕｄｅｓａｌｌｐｏｓｓｉｂｌｅ ｃｏｌｌａｂｏｒａｔｉｏｎａｎｓｗｅｒｓ．Ｔｈｅｐｒｏｃｅｓｓｉｎｃｌｕｄｅｓａｄａｐｔａｔｉｏｎｐｅｒｉｏｄａｎｄｐｅｒｉｏｄ．Ｉｎａｄａｐｔａｔｉｏｎｐｅｒｉｏｄ，ａｌｌａｎｓｗｅｒｓａｄｊｕｓｔｔｈｅｓｔｒｕｃｔｕｒｅｉｔｓｅｌｆａｃｃｏｒｄｉｎｇｔｏｔｈｅａｃｃｕｍｕｌａｔｅｄｉｎｆｏｒｍａｔｉｏｎ；ｉｎｃｏｌｌａｂｏｒａｔｉｏｎｐｅｒｉｏｄ，ａｌｌ ｔｈｅａｎｓｗｅｒｓｅｘｃｈａｎｇｅｔｏｉｎｆｏｒｍａｔｉｏｎｔｏｇｅｔｔｈｅｂｅｔｔｅｒｏｎｅｓ．Ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｄｉｒｅｃｔｓｔｈｅａｌｇｏｒｉｔｈｍｔｈｅｍｏｓｔｏｐｔｉｍａｌｄｉｒｅｃｔｉｏｎｗｉｔｈｃｏｍｂｉｎａｔ