共查询到18条相似文献,搜索用时 62 毫秒
1.
课程表问题是NP完全类问题.近些年来人们尝试着用进化算法求此问题.本文根据大学编排课表的特点设计了一种全新的编码和适应值函数,并应用遗传算法求解.试验说明了该方法的可行性和有效性. 相似文献
2.
遗传算法在排课问题中的运用 总被引:5,自引:0,他引:5
遗传算法借鉴生物界自然选择和遗传机制,使用群体搜索技术,处理传统搜索方法难以解决的复杂的非线性问题.排课问题是一个多因素的优化决策问题,是组合规划中的典型问题,属于NP完全类问题.根据大学课表的特点,采用遗传算法,给出染色体编码和适应度函数,并采用了自适应的调整概率进行排课,数值试验证明了方法的有效性和可行性. 相似文献
3.
求解车辆路径问题的改进遗传算法 总被引:1,自引:0,他引:1
陈久梅 《重庆工商大学学报(自然科学版)》2005,22(5):464-468
在建立车辆路径问题数学模型的基础上,设计了求解该问题的改进遗传算法,即采用自然数编码,构造一定长度的遗传个体表,动态记录适应度以及引入新交叉算子。实验结果表明,该算法用于求解车辆路径问题,不但可以解决传统遗传算法在求解该问题所遇到的“早熟收敛”,而且大大提高算法的运行效率。 相似文献
4.
5.
根据SAT问题的特点,通过分析传统蚁群算法和遗传算法在求解SAT问题上的不足,提出一种基于混合蚁群遗传算法的SAT问题求解方法。给出一种新的初始解的生成方式;在迭代过程中,根据较优解的累积信息提出进化算子;利用当前得到的最优解,通过改变不满足子句中文字的取值,增加变异算子。最后选取标准测试集中的20个实例对算法进行测试,实验结果表明:改进后的算法通常仅通过较少次数的迭代就能找到解,能够有效避免蚁群算法和遗传算法过早收敛的缺点,具有较强的寻优能力。 相似文献
6.
介绍了一种求解旅行商问题的混合蚂蚁算法,该算法结合了遗传算法中的改进的交叉算子和变异算子,对产生的局部最优解进行适当地交叉和变异,提高算法的搜索空间,可以提高蚁群算法的寻优能力,实验表明该算法很有效. 相似文献
7.
遗传算法通过编码技术,运用繁殖、杂交和突变等遗传算子,对染色体组成的初始种群,进行适应度分析,构成优胜劣汰、适者生存的自然环境,产生出新的更加优良的种群.经过若干代的进化,最终求得适合问题的最优解. 相似文献
8.
课程表问题(Tinletabling problem.简称TTP)是时间表问题之一,也是NP难问题。根据大学授课形式的特点建立了大学课程表问题的数学模型.并给出了求解该问题的遗传算法。为了提高解的质量和加快收敛速度,当相同时问段内班级重复出现时,给出了寻找可能的新位置的方法,并将其嵌入遗传算法,实验结果表明该方法是可行和有效的。 相似文献
9.
王勇 《哈尔滨商业大学学报(自然科学版)》2005,21(4):517-519
阐述遗传算法针对一类NP完全的组合优化问题——旅行商问题,提出采用高级算子操作对遗传算法进行改进,仅利用城市间的距离信息求解中国旅行商问题,用很短的时间得到了16719km这一最优结果。 相似文献
10.
11.
用自适应的遗传算法求解大学课表安排问题 总被引:17,自引:1,他引:16
课程表问题又称时间表问题 (timetable problem) ,是一个多因素的优化决策问题 ,也是组合规划中的典型问题 .本文研究的是大学课表安排问题 ,根据大学课表安排的特点并以优化时间和空间两种资源为目标 ,将课程分为 P、Q两类 .采用鲁棒性比较好的遗传算法 ,并对两类课分别给出其染色体编码和适应度函数 ,并采用了自适应的杂交和变异概率 ,最后通过实验验证该方法可产生适合需求的课表 相似文献
12.
课表问题是一个多因素的优化决策问题,在分析大学课表问题的基础上,设计了一种全新的、基于三维数组的二进制编码方式及几个优化目标评价函数,用遗传算法求解,并通过实验证明这种方法大大提高了遗传算法的效率。 相似文献
13.
课程表问题又称时间表问题(timetable problem),是一个多指标的优化决策问题,也是组合规划中的典型问题.对已有的时间表问题进行探讨,并研究其数学模型及解决方法. 相似文献
14.
遗传算法(简称GA)是基于生物进化原理的普适性全局优化算法,是解决NP难问题的一种行之有效的方法.但是,序号编码的遗传算法不能在任意两条染色体的任意位置进行交叉,必须使用PMX,CX和OX等特殊的交叉算子,这些算子实施起来都很麻烦且效率不高.针对这一问题,采用单亲遗传算法,取消交叉操作,强化变异作用.这样既简化了遗传操作,又克服了早熟现象.较成功的解决了影片递送问题,文中的算例表明,该算法是实际有效的. 相似文献
15.
一种改进的遗传算法求解旅行商问题 总被引:1,自引:0,他引:1
针对在解决旅行商问题时标准遗传算法效率不高,很容易陷入局部最优解的问题,提出了一种改进的遗传算法. 根据种群个体的多样性和分布情况,提出了判定遗传算法截止代数的方法. 研究结果表明,通过加入了初始化信息,改进交差算子,可提高遗传算法的精确性和收敛性. 相似文献
16.
用改进的遗传算法求解中国旅行商问题 总被引:7,自引:1,他引:7
遗传算法是基于生物进化原理的普适性全局优化算法,针对一类NP完全的组合优化问题-旅行商问题,提出用交换算子操作和模拟退火思想对遗传算法进行改进,显著提高了算法的优化效率,到目前为止,中国旅行商问题的最优解是15426km,使用改进的遗传算法,仅利用城市间的距离信息求解中国诱行商问题,得到了15409km的更优结果。 相似文献
17.
张晓玲 《大理学院学报:综合版》2009,8(4)
提出一种基于顶点的候选表进行交配的遗传算法(Candidate Crossover Genetic Algorithm,CCGA)求解旅行商问题(TSP).遗传算法(GAs)是一种广泛使用的全局优化算法,并且已经成功地用于求解TSP.但是传统的遗传算法的交配算子缺乏指导性和启发性,交配算子随机的选择父体基因进行交配,导致GAs求解速度慢、解的精度不高等不足.通过分析TSP问题本身的特征,给出了一个使用已有的邻接边的信息和路径信息生成顶点的候选表,然后基于顶点的候选表进行交配的交配算子,使用该交配算子的遗传算法在求解TSP问题时性能上得到了很大的提高,通过TSP Lib上的测试样例将该CCGA和传统的遗传算法进行比较.比较结果表明CCGA具有更大的优势,它能使算法求解到近似最优解和最优解只存在很小的偏差. 相似文献
18.
求解0-1背包问题的混合遗传算法 总被引:7,自引:0,他引:7
对于0-1背包问题设计一种价值密度,并在此基础上提出求解0-1背包问题的混合遗传算法.经大量数值实验比较该方法与传统方法及简单遗传算法,结果表明算法能有效求解0-1背包问题. 相似文献