摘要
给出了一种求解图着色问题的新算法,即单个个体的单亲遗传算法.算法采用顶点序号的聚类编码将个体的某个子串随机分配到其他子串中的变异方法.并对该算法的时间复杂度进行了分析比较,结果表明该算法具有较好的运行效率与收敛速度.
A kind of new single-individual partheno genetic algorithm is proposed for solving graph coloring problem. This algorithm uses an encoding method of classifying the vertex by the color and a mutated method of randomly dividing a child bunch into others. The time complexity is also analyzed. Experimental results show that this method is efficient and fast.
出处
《云南民族大学学报(自然科学版)》
CAS
2008年第3期255-257,共3页
Journal of Yunnan Minzu University:Natural Sciences Edition
基金
西北第二民族学院自然科学类基金资助项目(2007Y036)
关键词
单亲遗传算法
图着色
聚类编码
变异
partheno-genetic algorithm
graph coloring
classifying code
mutation