论文部分内容阅读
图着色问题是一个被广泛研究的组合优化问题,它也是科学计算和工程设计中一个重要和基本的问题。由于对于任意一个图着色例子而言,没有一种算法可以在多项式的时间内找到它的解,因此图着色问题是一个NP问题。实际工程中的问题例如考试时间表问题和任务分配问题等都可以被模拟成图着色问题的拓展,因此图着色问题具有较好的实际应用背景。本文主要针对图着色的算法展开研究。传统的遗传算法有许多缺点,其中最严重的是过早收敛问题。为了提高图着色算法的寻优效率,提出将模拟退火算法与遗传算法相结合。具体操作是通过遗传算法得到一代种群,接着用模拟退火算法对这一代种群进行局部优化,这时生成的种群才作为下一代的新种群使用。运用模拟退火遗传算法可以同时兼顾全局寻优性能与局部寻优性能的目的。但是对于顶点数较大的图着色问题,继续采用模拟退火遗传算法,必然需要选取较大的群体规模,增加迭代次数,才能找到正确的着色方案,这样就必然增加了计算量,降低了计算效率。这一缺陷使得模拟退火遗传算法对顶点数较大的图着色问题的寻优效率大大降低。因此,对于大规模图着色问题,需要降低图着色问题的复杂性,采用更加高效的寻优算法,才能提高寻优效率。本文根据图着色问题的特点,提出基于启发式算法的模拟退火遗传算法。启发式算法通过指导搜索向最有希望的方向前进,降低了复杂性。因此,将启发式算法引入模拟退火遗传算法中,可以指导图着色方案朝最优方向前进,降低图着色问题的复杂性,减少迭代次数。采用本文提出的模拟退火遗传算法应用于24顶点图着色问题,并与遗传算法进行了详细比较,仿真结果无论是单次迭代次数和单次计算时间还是平均迭代次数和平均计算时间,模拟退火遗传算法都明显小于传统遗传算法,证明了本文所提出的模拟退火遗传算法的有效性。将启发式模拟退火遗传算法用来解决48顶点图着色问题,仿真结果表明将启发式模拟退火遗传算法用于解决顶点数目较大的图着色问题是有效的,其收敛性较好,并且迭代次数和收敛时间都很小。