Analysis of an Iterated Local Search Algorithm for Vertex Coloring
Analysis of an Iterated Local Search Algorithm for Vertex Coloring
复制标题
顶点着色的迭代局部搜索算法分析
DOI：
10.1007/978-3-642-17517-6_31
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
C. Zarges
中科院分区：
文献类型：
--
作者：
Dirk Sudholt;C. Zarges
进化算法和局部搜索的混合算法是顶点着色的最佳算法之一。然而，对这些算法的理论知识非常有限，人们普遍认为需要坚实的理论基础。我们考虑一种迭代局部搜索算法，该算法迭代地试图通过在局部搜索之后应用变异来改进着色。我们使用期望迭代次数的界限来研究这种方法的能力和局限性，直到找到最优或接近最优的着色。这是针对两个不同的变异算子和不同的图类：二部图、稀疏随机图和平面图完成的。
Hybridizations of evolutionary algorithms and local search are among the best-performing algorithms for vertex coloring. However, the theoretical knowledge about these algorithms is very limited and it is agreed that a solid theoretical foundation is needed. We consider an iterated local search algorithm that iteratively tries to improve a coloring by applying mutation followed by local search. We investigate the capabilities and the limitations of this approach using bounds on the expected number of iterations until an optimal or near-optimal coloring is found. This is done for two different mutation operators and for different graph classes: bipartite graphs, sparse random graphs, and planar graphs.
DOI：
10.1007/b96500
发表时间：
2004
期刊：
--
影响因子：
--
作者：
G. Raidl;S. Cagnoni;J. Branke;D. Corne;R. Drechsler;Yaochu Jin;Colin G. Johnson;Penousal Machado;E. Marchiori;Franz Rothlauf;George D. Smith;Giovanni Squillero
通讯作者：
G. Raidl;S. Cagnoni;J. Branke;D. Corne;R. Drechsler;Yaochu Jin;Colin G. Johnson;Penousal Machado;E. Marchiori;Franz Rothlauf;George D. Smith;Giovanni Squillero