检索结果-内蒙古大学图书馆

计算机工程与设计 2008年第2期29卷 398-400页

作者：袁占亭张秋余刁雪峰张安杰兰州理工大学计算机与通信学院甘肃兰州730050 西安理工大学计算机科学与工程学院陕西西安710048

课程表问题是经典的组合优化问题,属于NP-hard问题。长期以来人们一直都在寻求快速高效的近似算法,以便在合理的计算时间内准确解决大规模课程安排问题,并提出许多有效且实用的启发式和元启发式算法。在此基础上提出了一种基于多个图染... 详细信息

课程表问题是经典的组合优化问题,属于NP-hard问题。长期以来人们一直都在寻求快速高效的近似算法,以便在合理的计算时间内准确解决大规模课程安排问题,并提出许多有效且实用的启发式和元启发式算法。在此基础上提出了一种基于多个图染色启发式规则的模拟退火超启发式算法。在超启发式算法的框架中,用模拟退火算法作为高层搜索算法,多个图染色启发式规则为底层的构造算法。与现有的方法相比,该算法具有很好的通用性,可以很容易推广到考试时间表、会议安排、旅行商问题、背包问题等应用领域。实验表明,该算法是可行有效的,且无一例时间、空间冲突。

关键词：课程表问题启发式超启发式算法模拟退火算法图染色

来源：评论

学校读者我要写书评

暂无评论

基于遗传算法的课程表问题研究

基于遗传算法的课程表问题研究

引用

作者：熊焱东北大学

学位级别：硕士

课程表编排问题是时间表问题之一,也是一个解决时间和空间资源矛盾的多因素优化决策问题,即对各类课程、教师、学生进行时空安排问题,这种安排问题需要满足一定的约束条件集,如关于教室的位置与容量、时间间隔、特定课程承接关系等方面... 详细信息

课程表编排问题是时间表问题之一,也是一个解决时间和空间资源矛盾的多因素优化决策问题,即对各类课程、教师、学生进行时空安排问题,这种安排问题需要满足一定的约束条件集,如关于教室的位置与容量、时间间隔、特定课程承接关系等方面的约束条件.目前各类学校都存在着学生数量、课程设置增多,而相应的配套资源没有太大变化的情况.这就要求能充分利用已有的资源,选择最合理的编排方案.近40年来,人们尝试着用各种方法求解此类问题,如:整数规划、图着色、各种推理搜索方法、进化算法等等.遗传算法是一种拟自然的、具有随机性的全局优化方法.近些年来,遗传算法在求解复杂问题中发挥了重要的作用.同样,遗传算法也能有效的求解课程表问题.该文分析了课程表问题的发展状况;综述了遗传算法在数学基础、遗传操作以及各领域的应用发展现状;根据大学授课形式的特点建立了大学课程表问题的数学模型;给出了基于不同目标的遗传算法求解方法;提出教师和教室的两种编码形式,为了提高解的质量和加快收敛速度又设计最佳时段-查找法,并将其嵌入遗传算法中;对于利用教室编码的遗传算法提出了一种新的交叉算子;通过实验验证了该文所提出的算法适合于所建模型的求解,是可行性和有效性.最后给出了课程表问题进一步研究的方向.

关键词：时间表问题课程表问题遗传算法编码遗传操作早熟收敛进化计算数学模型

来源：评论

学校读者我要写书评

暂无评论

求解课程表问题的分支定界算法

求解课程表问题的分支定界算法

引用

作者：吴金荣中国科学院数学与系统科学研究院

学位级别：硕士

在该论文中我们讨论了几类排课程表问题,建立和分析了求解这些问题的数学模型和解决方案.在此基础上我们主要研究了带约束有教案的中学排课程表问题.首先我们得到了有关该问题的中学课程表必须满足的几个条件,并证明了该排课程表问题是... 详细信息

在该论文中我们讨论了几类排课程表问题,建立和分析了求解这些问题的数学模型和解决方案.在此基础上我们主要研究了带约束有教案的中学排课程表问题.首先我们得到了有关该问题的中学课程表必须满足的几个条件,并证明了该排课程表问题是一个NP-难解的问题,因此该问题没有多项式时间算法.通过分析得出,已有的求解时间表问题的方法对我们所要解决的时间表问题是不适用的.而后我们提出了一个求解该问题的分支定界算法.数值试验表明这是解决一般编排中学课程表问题的一个有效的算法.最后我们讨论了所提出的分支定界算法对小学、专科类、大学、研究生等学校的排课程表问题的适用情况.

关键词：课程表问题 NP-难解问题分支定界算法

来源：评论

学校读者我要写书评

暂无评论

案例注入式遗传算法及其在大学课程表问题中的应用

案例注入式遗传算法及其在大学课程表问题中的应用

引用

作者：屠雄刚国防科学技术大学

学位级别：硕士

大学课程表问题(University Timetable Problem-UTP)是一个长久以来一直困扰着各个学校的教学资源多目标组合优化问题。它的解决不仅有助于我们对运筹学中多目标优化类问题的研究,而且对解决我国现阶段教育中教学资源相对稀少、而学生... 详细信息

大学课程表问题(University Timetable Problem-UTP)是一个长久以来一直困扰着各个学校的教学资源多目标组合优化问题。它的解决不仅有助于我们对运筹学中多目标优化类问题的研究,而且对解决我国现阶段教育中教学资源相对稀少、而学生又相对较多的现状尤其具有现实意义。大学课程表问题已经被***证明是一个NP完全问题,而目前能够较好解决该问题的就是遗传算法,但是在研究过程中我们也发现,为了要保留优秀个体以防止出现局部最优解的情况,大多数的遗传算法总是采用随机方式来初始化种群,这就造成了运算量变大和复杂度增加等情况,从而影响了算法的性能。而基于案例的推理具有良好的学习能力,能够通过对先前解决问题方法的学习来获得当前问题的解决方案,以此来提高解决问题的速度。因此本文提出了一种解决大学课程表问题的算法——案例注入式遗传算法,该算法利用基于案例的推理对遗传算法进行初始化,并在进化自然选择阶段对适应度较差的个体进行替换,以此来加快遗传算法的收敛速度,以便更快更好的完成排课任务。为了检验该算法的实际应用效果,本文针对大学课程表问题建立了数学模型,并利用数学化语言对排课问题的影响因素、主要约束条件和求解目标等进行了描述和分析;同时完成了遗传算法操作算子的设计,以及案例注入式初始化、合班拆解避让、冲突避让等算法的编码。最后使用VC++6.0作为开发工具,Access作为后台数据库,设计出了一个应用案例注入式遗传算法的自动排课系统,并将它与采用随机遗传算法的自动排课系统进行了对比测试。从最终排课时间及排课质量的分析结果来看,该算法较随机遗传算法有较大的性能改进,取得了良好的排课效果。

关键词：遗传算法基于案例的推理课程表问题多目标优化

来源：评论

学校读者我要写书评

暂无评论

用遗传算法求解课程表问题

用遗传算法求解课程表问题

引用

作者：李庆民山东科技大学

学位级别：硕士

实现计算机自动排课,是学校教学管理工作迈入科学化、规范化和现代化管理的关键步骤,其意义十分重大。然而,排课问题己被证明为NP完全的组合优化问题,至今在多项式时间内没有完善、成熟的解决方案。遗传算法是一种借鉴生物界自然选择和... 详细信息

实现计算机自动排课,是学校教学管理工作迈入科学化、规范化和现代化管理的关键步骤,其意义十分重大。然而,排课问题己被证明为NP完全的组合优化问题,至今在多项式时间内没有完善、成熟的解决方案。遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、自适应的随机搜索算法,是一种非常有效的解决NP完全组合问题的方法。本文在详细分析遗传算法的应用特点和关键要素的基础上,结合课程表问题的求解难点和目标,综合考虑排课问题涉及到的各种因素和约束条件,确定了求解排课问题方案的总体思路,设计了遗传算法的具体实现方案,以济宁市实验中学2008-2009学年度第一学期课程表为实例,使用C#和.net作为开发工具设计完成了计算机自动排课系统。本文的主要的研究内容有: 1.系统完整地讨论了排课问题中的影响因素、主要约束条件、求解目标和难点,用数学模型完整地描述了排课问题,并提出了使用遗传算法求解课程表问题的方法和优势。 2.针对排课问题研究了染色体编码方式以及遗传操作算子的设计,提出了一种针对课程表问题解的特点的染色体混合矩阵二进制编码,并引入多目标决策协调模型优化课程表问题,并改进了遗传算法一般结构,形成了一套多目标协同优化的排课算法。 3.以C#}和.net为基本开发工具,MS SQL SERVER2000为后台数据库,设计和实现了基于GA算法的B/S和C/S混合架构的自动排课系统。我们通过对济宁市实验中学的共306个教师和90个班级的1230个开课计划的实例,在由时间片优先度、班级日分布均匀度、教师时间期望、教师课时日分布平均度和每个工作日密集课程度五个因素组成的目标空间上进行求解,所得结果基本令人满意,在求解过程中算法稳健并且收敛与Pareto最优解。

关键词：课程表问题遗传算法组合优化

来源：评论

学校读者我要写书评

暂无评论

大学课程表问题中的算法研究与应用

大学课程表问题中的算法研究与应用

引用

作者：黄锟中南大学

学位级别：硕士

课程表问题(UTP)是一个应用广泛的、典型的组合优化和不确定性调度问题,并且已经被证明是NP完全问题。随着高校规模的不断扩大,和教学管理信息化的不断深入,传统的手工排课和计算机辅助排课已经越来越难以适应现实的需求,而自动化排课系... 详细信息

课程表问题(UTP)是一个应用广泛的、典型的组合优化和不确定性调度问题,并且已经被证明是NP完全问题。随着高校规模的不断扩大,和教学管理信息化的不断深入,传统的手工排课和计算机辅助排课已经越来越难以适应现实的需求,而自动化排课系统,因其固有的高难度和复杂性,它的研究与实现成为完善中南大学网络教学管理系统十分重要的一环。本文从实际应用出发,基于动态规划的思想,提出了一种解决大学课程表问题的混合算法,并基于此算法设计并实现了自动化排课系统。本文首先介绍了UTP问题的研究现状、涉及的因素、各种约束条件,及其数学模型,然后详细阐述了将课程表问题划分为时间片安排和场地安排两个阶段,分别采用智能算法和最佳适应算法逐段求解,并最终求得全局较优解的混合算法。然后,对混合算法与经典遗传算法进行了对比实验分析,结果表明这种分阶段决策的算法在保证课表质量的同时,能够有效的减小遗传算法在求解UTP问题中的复杂度,提高程序的运行速度,也有利于工程应用中对多目标优化的进一步扩展。随后,本文基于混合算法,根据项目的实际需求,并考虑到和网络教学管理系统中其它子系统的集成,设计了排课系统的数据库表和各个功能模块,结合图表和文字说明,给出了详细的系统实现过程,并对系统实现过程中的关键技术进行了说明。最后,总结了本文所做的工作,分析了当前工作的不足及需进一步研究的工作。

关键词：课程表问题动态规划遗传算法排课

来源：评论

学校读者我要写书评

暂无评论

关于课程表问题的研究

关于课程表问题的研究

引用

作者：吴金荣中国科学院数学与系统科学研究院

学位级别：硕士

在该论文中我们讨论了几类排课程表问题,分别建立中学课程表和大学课程表问题的数学模型.我们证明了这两个问题都是NP-难解的优化问题.通过分析我们得出,已有的求解时间表问题的方法对我们所要解决的排课程表问题都是不适用的.在此基础... 详细信息

在该论文中我们讨论了几类排课程表问题,分别建立中学课程表和大学课程表问题的数学模型.我们证明了这两个问题都是NP-难解的优化问题.通过分析我们得出,已有的求解时间表问题的方法对我们所要解决的排课程表问题都是不适用的.在此基础上,我们首先提出求解了带约束有教案的中学排课程表问题的分支定界算法.数值试验表明这是解决一般编排中学课程表问题的一个有效的算法.而后我们给出了求解大学课程表问题一个基于图的顶点着色的启发式算法.同时,我们还讨论了我们所提出的针对中学和大学排课程表问题的解决方案对解决小学、专科类学校排课程表问题以及其它相关问题的适用情况.

关键词：课程表问题 NP-难解问题分支定界算法启发式算法

来源：评论

学校读者我要写书评

暂无评论

求解课程表问题的分支定界算法