共查询到17条相似文献,搜索用时 78 毫秒
1.
一种基于矩阵遗传算子的优化组合遗传算法 总被引:5,自引:0,他引:5
针对遗传算法中全局搜索与局部搜索之间的矛盾,应用二进制编码具有对搜索空间表示精细、容易位值计算的特点,提出矩阵遗传算子,实现群体性对样本空间探索,从而增强遗传算法的全局搜索性能,与具有良好局部搜索性能的遗传算子组合应用,构造了基于矩阵遗传算子的优化组合遗传算法,保证了算法的全局收敛性.实验结果表明,该算法具有更好的整体寻优能力,对利用基于二进制编码遗传算法求解复杂非线性优化问题具有重要借鉴意义. 相似文献
2.
遗传算法在图着色问题上已经得到广泛的应用,但对于顶点数较多的图,使用此类算法进行着色的结果就显得不够理想,运行效率也不够高。由于遗传算法具有全局收敛性,蚁群算法具有局部收敛性,因此,将遗传算法和蚁群搜索算法融合,提出一种新的解决图着色问题的蚁群遗传算法。该算法先利用蚁群算法快速地为遗传算法搜索到较好的初始解,然后利用遗传算法进一步遗传优化,同时在优化解上加强信息素强度,并反馈给蚁群搜索。实验结果表明,改进的算法在解决顶点数较大的图着色问题上有明显的优势。 相似文献
3.
针对基于行结构的整数编码遗传算法在求解图着色问题时存在的2个主要问题:编码冗余引起的性能下降和遗传算法易“早熟”陷入局部最优,本文给出一种新的适应度值计算函数,能够使遗传算法对冗余编码获得相同的适应度值,从而将冗余编码作为同一编码处理,减少对冗余编码的无效操作,并且在此基础上,设计与适应度函数相适应的遗传算子,这些算子一方面能使遗传算法在前期产生优秀个体并且维护优秀个体对种群进化的引导作用,加速遗传算法的收敛;另一方面能在遗传算法后期对优秀个体进行爬山优化,弱化优秀个体对种群进化的控制作用,使遗传算法能够收敛到全局最优解。实验结果表明,本文的算法能够准确解决图的点着色问题,并且在时间性能上要优于穷举法和基本遗传算法。
相似文献
4.
5.
6.
7.
8.
基于阀值逆序算子的优化组合遗传算法 总被引:1,自引:0,他引:1
针对遗传算法局部搜索能力差的缺点,模拟生物染色体中基因排列的有序性,对阀值逆序算子进行了研究,它与传统逆序算子相比,能较好地提高群体性能提高,减少了对种群多样性的破坏,改善了遗传算法的局部搜索性能,与具有全局搜索性能好的遗传算子组合,弥补了阀值逆序算子对全局搜索性能的影响,构造了一种基于阀值逆序算子的优化组合遗传算法。从理论上证明了该算法的收敛性,实验结果表明,该优化组合算法具有更好的寻优能力,对应用串型编码的遗传算法解决一般的优化问题时,具有很好的借鉴意义,阀值可根据求解问题特征和局部搜索强度而选定。 相似文献
9.
—个求解层次图边交叉数最小化问题的遗传算法 总被引:1,自引:0,他引:1
最小化边交叉数是层次图绘制过程中的一个关键步骤,直接影响着层次图的可读性。提出了一个基于遗传算法的层次图边交叉数最小化算法,详细地给出了编码表示方法以及遗传算子的设计。与常用的启发算法相比,该算法得到了更好的计算结果,此外算法简单且易于实现。 相似文献
10.
11.
图着色问题(GCP)是NP完全问题.近年来求解GCP的启发式局部搜索算法引起人们的关注,GSAT是最著名的局部搜索算法之一.许多局部搜索算法引入跳出局部极小的机制来提高搜索效率,权值学习是一种被广泛采用的方式之一.我们从一些权值学习局部搜索算法抽象出一个通用的权值学习算法(SWLA),进一步把SWLA和GSAT相结合提出了最小冲突权值学习算法(MCWLA),算法还应用还原策略和“权值交叉”算子来提高搜索后期的效率.算法在求解一些难解测试范例时显示出较高的效率,能求得GSAT及SWLA无法求得的最优解. 相似文献
12.
在构造了一种新型的“类发夹”式探针的基础上,给出了图的顶点着色问题的一种DNA算法。利用顶点的适当编码,该算法直接生成可满足解空间,无须在全体解空间中进行各种过滤过程,使用常规的生物操作完成可满足解空间的产生及最终解的分离。 相似文献
13.
14.
时间表问题是将有限的时间资源分配给多个对象的资源分配问题,它是一类具有多约束条件的组合优化问题。时间表问题已经被证明是一个NP完全问题。大学考试时间安排问题是时间表问题的一个应用,利用改进的图着色算法来处理大学考试的时间安排问题能够最大程度上使考试时间安排得更加人性化、合理化。实验测试表明,基于所给出的算法实现的考试时间安排系统具有良好的可行性、实用性和优越性。 相似文献
15.
求图着色问题的新算法 总被引:4,自引:0,他引:4
图着色问题是NP-难度的问题。基于两种传统的启发式算法,提出了两种新的求解策略,由此给出了求图着色问题的两个新算法。与传统算法相比,其中一个新算法在时间复杂度不变的条件下,解的质量有明显提高;另一个则在时间复杂度稍有增加的前提下,进一步较显著地提高了所得解的质量。 相似文献
16.
17.
本文通过分析遗传算法的机理和特点,介绍了遗传算法在组合优化问题中的应用。在组合优化的求解问题中,相比于其他优化算法,遗传算法具有一定的优势,但仍存在着严重的局限性。为此,本文对传统的遗传算法进行了改进,并通过TSP(旅行商)问题验证了算法的有效性。 相似文献