【摘要】 针对整数编码的冗余性,提出了求解图着色问题的一种新的编码方式.采用有序划分编码问题的解,编码后的个体具有与问题的潜在解一一对应的特点.与整数编码相比,新的编码避免了冗余性,将搜索空间缩小了k!倍.对5个标准图着色问题的仿真结果表明,基于有序划分编码的新算法是求解图着色问题的一种有效的算法.更多还原

【Abstract】 A novel encoding scheme was presented to solve the redundancy of the integer representation for the graph coloring problem.The ordered partition representation has the characteristic of one-to-one correspondence to the valid solution of the related problem.Compared with the integer representation,the new encoding avoided the redundancy completely and shrunk the search space k! times of that of the integer representation.The simulation results on five standard benchmark problems demonstrated the proposed algorithm was effective for the graph coloring problem.更多还原