分组遗传算法用于图的着色

图的着色算法是一种典型的NP 完全问题 在系统地讨论了图的正常顶点着色、边着色以及全着色的有关理论的基础上 ,提出了基于分组遗传算法和启发式搜索的图的正常 k 点着色 ,正常k 边着色以及正常k 全着色的新型混合算法 ,提出了评价算法性能的标准 实验仿真结果表明 ,新型混合算法可以获得问题高质量的解 ,即对图进行着色所使用的颜色数接近图的色数     

New Hybrid Genetic Algorithm for Vertex Cover Problems

This paper presents a new hybrid genetic algorithm for the vertex cover problems in which scan-repair and local improvement techniques are used for local optimization. With the hybrid approach, genetic algorithms are used to perform global exploration in a population, while neighborhood search methods are used to perform local exploitation around the chromosomes. The experimental results indicate that hybrid genetic algorithms can obtain solutions of excellent quality to the problem instances with different sizes. The pure genetic algorithms are outperformed by the neighborhood search heuristics procedures combined with genetic algorithms.     

解Job-Scheduling调度问题的一种遗传算法

带有截止期的作业调度问题是企业管理、操作系统中重要而又基本的问题之一。利用遗传算法解决了操作系统中单机、无资源约束 ,且每个作业可在等量时间内完成的作业调度问题。在系统地讨论了带有截止期的作业调度有关理论的基础上 ,设计并实现了该问题的一种新型算法———基因型算法。最后给出了算法的一些运行结果。实验仿真结果表明 ,该算法具有很强的鲁棒性。     

遗传算子作用机理分析及其改进

文中分析了遗传算子的作用机理 ,指出了随机性的标准遗传算法的不足之处 从遗传算法角度来看 ,虽然随机交叉方式增强了开辟新的、可能是有用的搜索空间的能力 ,但由于缺乏对可能的交叉效果 (子代质量 )方面的考虑 ,也会带来交叉的有效性以及优化效率不太理想等方面的问题 为此引入了基于交叉机制的小生境技术 对于提高交叉后子代的质量和拓广交叉后子代具有多样性有一定的意义 提出了共享函数和共享度的概念 所提出的共享函数的概念限制了群体内某一特殊“物种”的无控制的增长 ,对于预防过早收敛具有一定作用     

典型并行算法的实现性能分析

讨论和分析了几种典型的并行算法及其各种处理方法在基于Windows XP环境、消息传递接口MPI并行编程环境支持和C 语言描述的编程实现问题，给出了相应并行程序详尽的计算结果，对比分析了它们的计算性能，以及它们对计算精度产生的影响。分析结论以相应并行算法的实际编程实现和试验计算数据为基础，可信度高。设计实例表明，分析方法是有效的。     

分组遗传算法用图的着色

图的着色算法是一种典型的ＮＰ－完全问题。在系统地讨论了图的正常顶点着色,边着色以及全着色的有关理论的基础上,提出了基于分组遗传算法和启发式搜索的图的正常ｋ－点着色,正常ｋ－边着色以及正常ｋ－全着色的新型混合算法,提出了评价算法性能的标准。实验仿真结果表明,新型混合算法可以获得问题高质量的解,即对图进行着色所使用的颜色数接近图的色数。