一个求解层次图边交叉数最小化问题的遗传算法

最小化边交叉数是层次图绘制过程中的一个关键步骤,直接影响着层次图的可读性。提出了一个基于 遗传算法的层次图边交叉数最小化算法,详细地给出了编码表示方法以及遗传算子的设计。与常用的启发算法 相比,该算法得到了更好的计算结果,此外算法简单且易于实现。     

基于遗传算法的概念格布局优化

针对概念格布局过程中产生的边交叉数过多问题,分析了求解概念格图形中边交叉数问题的方法,并结合遗传算法,提出了减少边交叉数的优化策略,通过目标函数计算出概念格层次图的边交叉数最少时格节点的布局序列,从而达到在二维概念格图形布局过程中尽量减少边交叉数的目的。     

一种求解旅行商问题的贪婪边重组交叉算子

提出了一种新的求解旅行商问题的贪婪边重组交叉算子。该交叉算子吸取了边重组交叉算子的优点,使得父代在进化过程中获得的优良的边能顺利地遗传给子代。同时,在边重组的过程中,该交叉算子引入所求旅行商问题的具体信息以指导新边的生成,从而该交叉算子具有贪婪特征。实验结果表明:对于简单的旅行商问题,贪婪边重组交叉算子能显著提高算法效率;对于大规模的旅行商问题,该交叉算子的效果也较理想。     

求解TSP的启发式顺序交叉算子

旅行商问题是经典的NP难组合优化问题之一.在用遗传算法求解旅行商问题时,顺序交叉算子是一种较为常用的遗传交叉算子.使用顺序交叉算子时的交叉点位置是随机指定的,不能反映关键遗传信息,导致算法执行效率较低.在顺序交叉算子的基础上,提出了一种启发式顺序交叉算子.该算子结合顺序交叉算子和启发式算法以得到双亲中交叉点位置,保留了双亲中关键的城市顺序信息.该算子改善了使用顺序交叉算子执行效率低的问题.实验结果表明了该算子的有效性.     

求图着色问题的新算法

图着色问题是NP-难度的问题。基于两种传统的启发式算法，提出了两种新的求解策略，由此给出了求图着色问题的两个新算法。与传统算法相比，其中一个新算法在时间复杂度不变的条件下，解的质量有明显提高；另一个则在时间复杂度稍有增加的前提下，进一步较显著地提高了所得解的质量。     

遗传算法及其异位交叉问题的研究

针对目前遗传算法的搜索速度比较慢的问题，提出加快收敛速度的界伏交叉算子以提高算法的收效速度。仿真结果超明，这种交叉算子比一般的对等位交叉更能有效提高收敛速度，不易陷入局部最优解。     

一种求解图着色问题的优化组合遗传算法①

图着色算法是一种典型的NP-完全问题。在逆序算子、对偶算子和矩阵遗传算子的性能研究基础上,采用自然数与二进制相互转换的编码方案,应用图着色问题的约束条件建立适应度评价函数,将具有良好局部搜索性能的矩阵遗传算子与具有良好局部搜索性能的逆序与对偶组合算子优化组合应用,构造了一种用于求解图着色问题的优化组合遗传算法,保证了算法的全局收敛性。与基本遗传算法相比较,实验结果表明,该算法对图着色问题有较好的求解性能。     

求解TSP问题的遗传算法新方法研究

遗传算法是一种基于自然选择与遗传变异等生物进化机制的全局优化搜索算法。由于它在搜索空间中同时考虑许多点．这样就减少了收敛于局部极小的可能,也增加了处理的并行性。因此可以利用遗传算法研究典型的组合优化实例-TSP问题的求解问题。本文借助于遗传算法,采用新的交叉算子,给出了旅行销售员问题较优解的求解方法。     

应用改进的遗传算法求解TSP问题

旅行商问题,也称货郎担问题,属于完全NP问题,而遗传算法在解决组合排列问题方面占有很重要的地位.针对TSP问题,提出了一种改进的遗传算法.利用交换启发交叉算子和可变交叉概率实现局部搜索,加快算法的收敛速度,利用变换变异算子和可变变异概率维持群体的多样性防止算法早熟收敛.Java仿真实验结果表明,改进后的算法明显优于传统的遗传算法,说明该算法具有良好的有效性和可行性.     

不超过9个顶点的所有图的交叉数

利用本文作者研制的计算图的交叉数的算法CCN(Calculate Crossing Number)，本文对n≤9的所有图的交叉数进行了研究．由于图的交叉数等于其所有二连通分支的交叉数的和，本文计算了n≤9的所有单二连通分支图的交叉数．并得出相关的规律：1)n个顶点q条边的单二连通分支图的平均交叉数Ave(n，q)可近似地表示为q的二次多项式，2)在给定顶点数n与边数q的单二连通分支图中围长较大的图的平均交叉数大于围长较小的图的平均交叉数，3)在给定顶点数n与边数q的单二连通分支图中当n为奇数或r≤n／2时，r正则图的平均交叉数大于非r正则图的平均交叉数．     

求解有约束优化问题的实数遗传算法改进研究

提出一种求解有约束优化问题的改进实数遗传算法.首先,提出一种排序分组选择法,该方法具有种群多样性好、易于实现的优点.其次,给出一种基于方向的启发式交叉算子(DBHX),DBHX能够产生无数个交叉方向,且有可能产生一个引导参与交叉的染色体向最优解移动的方向vecD,即使交叉方向与vecD不一致,也有很大的可能性非常接近方向vecD,可以保证有很大的机会产生更好的子代染色体.最后,针对单一的变异算子无法兼顾局部搜索能力和全局搜索能力的缺点,提出一种组合变异方法,使得变异操作既能保证算法的局部搜索能力,又能兼顾全局搜索能力.10个实例的计算结果表明,所提出的改进实数遗传算法具有较快的收敛速度,从而验证了所提出算法的可行性和有效性.     

旅行商问题(TSP)的一种改进遗传算法

传统的序号编码遗传算法(GA)使用PMX、CX和OX等特殊的交叉算子，这些算子实施起来很麻烦。针对TSP问题的求解，提出了一种新的改进遗传算法：单亲进化遗传算法(PEGA)，PEGA是利用父体所提供的有效边的信息，使用保留最小边的方法进行个体的进化。与传统的遗传算法相比，PEGA算法弥补了它们的不足之处，简化了遗传算法。给出了PEGA算法的数值算例，仿真实验表明了该算法对于对称的TSP和非对称的TSP问题，都具有收敛速度快的特点，证明了该算法的有效性。     

一种求解图着色问题的蚁群遗传算法

遗传算法在图着色问题上已经得到广泛的应用,但对于顶点数较多的图,使用此类算法进行着色的结果就显得不够理想,运行效率也不够高。由于遗传算法具有全局收敛性,蚁群算法具有局部收敛性,因此,将遗传算法和蚁群搜索算法融合,提出一种新的解决图着色问题的蚁群遗传算法。该算法先利用蚁群算法快速地为遗传算法搜索到较好的初始解,然后利用遗传算法进一步遗传优化,同时在优化解上加强信息素强度,并反馈给蚁群搜索。实验结果表明,改进的算法在解决顶点数较大的图着色问题上有明显的优势。     

遗传算法求解图的染色问题

探讨了用遗传算法求解图的染色问题,对问题进行转换后给 出了基于“近邻归类法”的两种遗传编码,并给出了用遗传算法求解的具体实施过程。     

求解旅行商问题的一个改进的遗传算法

利用遗传算法求解TSP问题,通常需要使用PCX,CX和OX等特殊的交叉算子以提高算法的运行效率。针对自然数编码的方式,提出一种改进的遗传算法,即改进传统的顺序交叉算子,进行不相同子排列顺序交叉,使子代继承父代中优秀的子排列,加快算法的收敛速度。另外,采用没有重复的稳态繁殖避免早熟。实验结果表明,此改进算法对于TSP和DHC问题均具有较好的性能。     

基于遗传算法的文件满TRIE结构最小化问题研究

提出了遗传算法寻求一个检索顺序来构造文件较小或最小的满TRIE结构的方法。     

求解TSP问题的改进模拟退火遗传算法

巡回旅行商问题（TSP）是最典型的NP的难题,遗传算法（GA）是解决这类问题的有效方法之一。由于该问题的解是一种特殊的序列,一般的交叉算子在该问题的求解效果方面并不理想,提出了贪心的3PM交叉算子,同时又引入退火选择方法,形成一种新的模拟退火遗传算法GCBSAGA（Greed Cross-3PM Based on Simulated Annealing Genetic Algorithms）。该算法还将模拟退火算法与遗传算法相结合,使得遗传算法在前期发挥着全局搜索的强大功能,很容易收敛到全局较优解;后期用模拟退火算法来处理遗传算法前期的全局较优解,充分利用模拟退火算法后期局部搜索的强大功能,最终收敛到全局最优解。经过国际公认的TSPLIB提供的实验数据的验证,GCBSAGA在实例eil76、eil101、pr144、st70均找到了比TSPLIB提供的最优路径更优的解。     

基于免疫遗传算法的装箱问题求解

装箱是一类典型的ＮＰ完全问题．本文用一种免疫遗传算法来研究装箱问题的求解．免疫遗传算法在传统遗传算法的全局随机搜索基础上,借鉴生物免疫机制中抗体的多样性保持策略,大大提高了算法的群体多样性,实验表明,免疫遗传算法具有很好的全局收敛性,能有效解决装箱问题．     

求解VRP问题的一种基于交叉算子的改进型遗传算法

采用基于自然数编码染色体、改进型交叉算子并增加内外扰动策略,构造出一种改进型遗传算法。详细介绍了此算法的基本原理,并进行了代表性算例实验与结果分析。实验表明,该算法收敛速度快,有效地遏制了早熟收敛,防止了进化过程中最优解的退化,改善了遗传算法的性能,提高了算法优化效率,是求解车辆路径问题的一种有效算法。     

基于灾变遗传算法的二叉判定图最小化算法

二叉判定图广泛应用于形式验证,但相关算法存在节点规模过大的问题。提出了一种基于灾变遗传算法的二叉判定图最小化算法,它能在不扩大种群规模的情况下增加个体多样性,改善遗传算法局部收敛的问题。试验结果表明该算法的全局特性显著优于传统遗传算法,能够进一步减小节点规模,改善程度最高可达25%。而且,由于使用何种进化策略并不影响灾变的发生,因此,算法可扩展性好,极易与其他改进策略结合起来,在原有特性的基础上引入全局优势,以进一步减小节点规模。