共查询到19条相似文献,搜索用时 62 毫秒
1.
考试时间表问题是一类典型的组合优化问题,也是NP难问题.分析了大学考试时间表编排的特点,给出了一种解决考试时间冲突的自动生成考试时间表的可行时段-查找算法.为进一步解决时间间隔问题,将可行时段-查找算法嵌入到遗传算法中形成混合遗传算法.实验结果表明,本文提出的混合遗传算法能快速、有效的解决大学考试时间表问题. 相似文献
2.
基于改进的Memetic算法求解大学考试时间表问题 总被引:4,自引:0,他引:4
分析了大学考试时间表问题,给出了一种使用启发式重度变异算子的Memetic演化算法,讨论了该算法中的编码方案、约束条件以及各演化算子的实现等问题,实验结果表明:启发式重度变异算子的使用能有效提高算法性能,减少演化代数。 相似文献
3.
4.
求解0-1背包问题的混合遗传算法 总被引:7,自引:0,他引:7
对于0-1背包问题设计一种价值密度,并在此基础上提出求解0-1背包问题的混合遗传算法.经大量数值实验比较该方法与传统方法及简单遗传算法,结果表明算法能有效求解0-1背包问题. 相似文献
5.
0-1背包问题是一类典型的组合优化问题,并且是NP完全问题,具有重要的研究意义.介绍了贪婪算法和基本遗传算法求解背包问题的设计思想,提出了基于贪婪算法的混合遗传算法求解0-1背包问题.实验结果表明改进的遗传算法有更好的近似解. 相似文献
6.
将遗传算法应用于背包问题,利用遗传算法的求解思想,对传统的背包问题进行了详细的分析,按照遗传算法的基本结构设计了编码,并通过实例验证了遗传算法用于解决背包问题的可行性和有效性. 相似文献
7.
时间表问题是一类特殊的调度问题,排课问题是它的一个实例。排课问题是一个多因素的优化决策问题,遗传算法被广泛应用于解决多目标优化问题。本文根据排课问题的特点,给出了排课问题的数学模型,提出了一种基于遗传算法的解决方法。 相似文献
8.
用自适应的遗传算法求解大学课表安排问题 总被引:17,自引:1,他引:16
课程表问题又称时间表问题 (timetable problem) ,是一个多因素的优化决策问题 ,也是组合规划中的典型问题 .本文研究的是大学课表安排问题 ,根据大学课表安排的特点并以优化时间和空间两种资源为目标 ,将课程分为 P、Q两类 .采用鲁棒性比较好的遗传算法 ,并对两类课分别给出其染色体编码和适应度函数 ,并采用了自适应的杂交和变异概率 ,最后通过实验验证该方法可产生适合需求的课表 相似文献
9.
时间表问题属于NP完全问题,一般来说,只能找出用于实际工作的“亚优解”(sub-optimal solution),对遗传算法和禁忌搜索算法用于求解时间表问题进行了对比研究,结果表明,禁忌搜索算法能找出比遗传算法更好的时间表,而且禁忌搜索算法所花费的搜索时间也比遗传算法少。但是,遗传算法能同时产生几个不同的逼近最优解的解。 相似文献
10.
针对基本遗传算法在求解大规模问题时,收敛速度缓慢、容易早熟的现象,借鉴生物区域性进化的原理,设计了一种基于星型迁移策略的并行混合遗传算法(Parallel Hybrid Genetic Algorithm,简称PHGA).该算法采用高效的超贪心算子进行解码,使遗传进化过程从多个平均适应度较高的文明群体开始进化,并采用定期将各群体的最优个体输出给其他群体,使得最优个体共享,促进所有群体共同进化的共产主义迁移策略.在PVM环境下,对背包问题进行求解的实验,已取得超线性的加速比,并改进了解质量. 相似文献
11.
课程表问题(Tinletabling problem.简称TTP)是时间表问题之一,也是NP难问题。根据大学授课形式的特点建立了大学课程表问题的数学模型.并给出了求解该问题的遗传算法。为了提高解的质量和加快收敛速度,当相同时问段内班级重复出现时,给出了寻找可能的新位置的方法,并将其嵌入遗传算法,实验结果表明该方法是可行和有效的。 相似文献
12.
遗传算法在解决大学课程表问题过程中往往采用随机方式来初始化种群,这就造成了运算量变大和复杂度增加等情况,从而影响了算法的性能.提出了一种改进的遗传算法——案例注入式遗传算法,该算法利用基于案例的推理对遗传算法进行初始化,以此加快算法的收敛速度. 相似文献
13.
背包问题的遗传算法求解 总被引:5,自引:2,他引:5
探讨利用遗传算法解决背包问题并设计新型的遗传算法,给出了背包问题的数学模型,建立了有效的约束条件。在引入一种新的具有自适应性的杂交概率和变异概率的基础上,提出了面向背包问题的遗传算法和一种构造染色体的新方法,提供了遗传算法的结构并讨论了遗传算法,给出了一个例子说明算法的收敛性和收敛效率,仿真说明了算法的有效性。 相似文献
14.
求解装配线平衡问题的混合遗传算法 总被引:6,自引:0,他引:6
装配线平衡问题一直是设施规划问题中的重要组成部分,是在建立生产线时就被考虑、解决并确定的。在面向市场的情况下,生产线必须是柔性的生产线,能快速响应新产品的需求,装配线平衡问题更应该是一个动态的生产调度问题。文章提出了混合遗传算法求解装配线平衡问题,给出了合适的编码方法,设计了新的交叉和变异算子,并通过实例验证了该算法的有效性和可行性。 相似文献
15.
16.
17.
求解车辆路径问题的改进遗传算法 总被引:1,自引:0,他引:1
陈久梅 《重庆工商大学学报(自然科学版)》2005,22(5):464-468
在建立车辆路径问题数学模型的基础上,设计了求解该问题的改进遗传算法,即采用自然数编码,构造一定长度的遗传个体表,动态记录适应度以及引入新交叉算子。实验结果表明,该算法用于求解车辆路径问题,不但可以解决传统遗传算法在求解该问题所遇到的“早熟收敛”,而且大大提高算法的运行效率。 相似文献
18.
提出一种新的求解旅行商问题的混合遗传算法。该混合遗传算法充分利用2-opt和3-opt局部搜索能力,有效地弥补了具有较强全局搜索能力的遗传算法在局部搜索方面表现出来的缺陷。实验结果表明,该混合算法性能显著优于遗传算法。 相似文献
19.
Hybrid ant colony algorithm for traveling salesman problem 总被引:8,自引:0,他引:8
A hybrid approach based on ant colony algorithm for the traveling salesman problem is proposed, which is an improved algorithm characterized by adding a local search mechanism, a cross-removing strategy and candidate lists. Experimental results show that it is competitive in terms of solution quality and computation time. 相似文献