• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Arabian Journal for Science and Engineering >Solution to Graph Coloring Using Genetic and Tabu Search Procedures
【24h】

Solution to Graph Coloring Using Genetic and Tabu Search Procedures

机译：使用遗传和禁忌搜索程序进行图形着色的解决方案

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Some of the engineering applications warrant the solution of Graph Coloring Problem, an NP-hard combinatorial optimization problem. This paper focuses on designing three new evolutionary operators using Tabu searching which are expected to offset the problems in the existing well-known methods in minimal search space and generations, besides maximizing the percentage of successful runs through effectively distributing promising genes for achieving fast stochastic convergence with smaller population size N. In the first method, Single Parent Conflict Gene Extended Crossover and Conflict Gene Mutation with Advanced Local Guided Search operators are designed and employed. These operators have been processed with Conflict Gene Removal constraints in the second method to minimize the search space and to increase the percentage of successful runs of the genetic algorithm. Multipoint Single Parent Conflict Gene Crossover and Multipoint Conflict Gene Mutation with Advanced Local Guided Search operators are employed along with a Conflict Gene Removal constraint in the third method. It has been exhibited that these operators reduce the search space by minimizing to obtain a better near optimal solution. The solution for most of the small and large benchmark graphs has been obtained through multipoint crossover and mutation with reduced whose value lies in a specific interval represented using maximum and minimum degrees of G. Our methods reduce the bound for the minimum colors obtained so far for certain families of graphs using smaller population size.
机译：一些工程应用程序需要解决Graph着色问题，这是一个NP-hard组合优化问题。本文着重设计使用禁忌搜索的三个新的进化算子，它们有望通过最小的搜索空间和代数来抵消现有知名方法中的问题，此外还可以通过有效地分配有前途的基因来实现快速随机收敛来最大化成功运行的百分比在第一种方法中，设计并采用了具有高级本地指导搜索运算符的单亲冲突基因扩展交叉和冲突基因突变。在第二种方法中，已使用“冲突基因去除”约束对这些算子进行了处理，以最大程度地减少搜索空间并增加遗传算法成功运行的百分比。在第三种方法中，采用了具有高级本地指导搜索运算符的多点单亲冲突基因交叉和多点冲突基因突变以及冲突基因去除约束。已经显示出这些算子通过最小化来减小搜索空间，以获得更好的接近最优的解决方案。对于大多数小型基准图和大型基准图，已通过多点交叉和突变获得了解决方案，其值减小了，该值位于使用G的最大和最小度表示的特定间隔中。我们的方法减小了迄今为止获得的最小颜色的界限某些图族使用较小的人口规模。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号