求解GCP问题的ILSBR算法

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (33): 43-45.

求解GCP问题的ILSBR算法

田瑞兴,江贺

大连理工大学软件学院,辽宁大连 116621

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-11-21 发布日期:2007-11-21
通讯作者: 田瑞兴

ILSBR algorithm for graph coloring problem

TIAN Rui-xing,JIANG He

School of Software,Dalian University of Technology,Dalian,Liaoning 116621,China

Received:1900-01-01 Revised:1900-01-01 Online:2007-11-21 Published:2007-11-21
Contact: TIAN Rui-xing

摘要/Abstract

摘要： 图着色问题（GCP,Graph Coloring Problem）是经典的NP-Hard组合优化问题之一。长期以来,人们一直在寻求快速、高效的启发式算法,以便在合理的计算时间内解决大规模问题。由于对规模较大的问题,目前的启发式算法尚不能在较短的时间内给出高质量的解,因此提出了一种基于全局最优解和局部最优解关系的ILS算法（ILSBR）。该算法的基本原理是通过对GCP问题的局部最优解和全局最优解之间关系的分析,发现对局部最优解的简单的相交操作能以很高的概率得到全局最优解的部分解。利用这些部分解构造一种新的扰动策略（RLG重着色）,并将其应用到传统的ILS算法中。在DIMACS标准集中,典型实例上的实验结果表明,采用RBILS算法在求解质量不变的情况下,求解速度上与目前的已知算法相比有较大的改进。

关键词: 图着色问题, NP-难解, 部分解, 扰动

Abstract: Graph Coloring Problem（GCP） is one of the typical NP-hard problems in combinatorial optimization problem.The fast and effective approximate algorithms are needed to solve the large scale problem in reasonable computing time.The known approximate algorithm can not give a good enough solution for larger instance in reasonable time.So ILS based Relation of local optimal and global coloring（ILSBR） is proposed.The algorithm is based on the analysis of the relation of local optimal and global optimal coloring of the GCP finding that the partial solution of the global optimal solution is obtained by a very high probability through intersecting the local optimal solutions.Using the partial solution could construct a kind of perturbation strategy（RLG Re-coloring） which then is applied to Iterated Local Search.The experimental results on DIMACS benchmark show that the ILS outperforms the known best ones in the running time without decreasing in the quality of solutions.

Key words: GCP, NP-hard, partial solution, perturbation

田瑞兴,江贺. 求解GCP问题的ILSBR算法[J]. 计算机工程与应用, 2007, 43(33): 43-45.

TIAN Rui-xing,JIANG He. ILSBR algorithm for graph coloring problem[J]. Computer Engineering and Applications, 2007, 43(33): 43-45.

[1]	王海瑞，鲜于建川. 改进麻雀搜索算法在分布式电源配置中的应用[J]. 计算机工程与应用, 2021, 57(20): 245-252.
[2]	舒乐，戴佳筑. 基于通用对抗扰动的图像验证码保护方法[J]. 计算机工程与应用, 2021, 57(18): 135-141.
[3]	章铁飞，徐斌. 利用内存行激活信息的DRAM行扰动问题研究[J]. 计算机工程与应用, 2021, 57(17): 269-274.
[4]	廖玮霖，程杉，尚冬冬，魏昭彬. 多策略融合的粒子群优化算法[J]. 计算机工程与应用, 2021, 57(1): 69-76.
[5]	钟鸣，刘建东，刘博，陈飞，张世博. 三维动态整数帐篷映射设计与分析[J]. 计算机工程与应用, 2020, 56(9): 56-64.
[6]	辛梓芸，张达敏，陈忠云，张绘娟，闫威. 多段扰动的共享型乌鸦算法[J]. 计算机工程与应用, 2020, 56(2): 55-61.
[7]	蔡子伟，徐正全，王晓艳. 基于时间扰动的智能电表隐私保护方法[J]. 计算机工程与应用, 2020, 56(1): 106-114.
[8]	黄宇达1，王迤冉2，牛四杰3. 基于混沌和自适应搜索策略的GSO算法分析与优化[J]. 计算机工程与应用, 2019, 55(3): 147-153.
[9]	邢伯阳，潘峰，冯肖雪. 智能决策改进的四足机器人ZMP爬行步态算法[J]. 计算机工程与应用, 2019, 55(22): 206-211.
[10]	侯利民，顾海旺，蒋尚昆，刘宇. 容错逆变器驱动的PMSM双环预测控制的研究[J]. 计算机工程与应用, 2019, 55(18): 212-217.
[11]	马巧梅，刘忠宝. 参数修正与收敛策略融合的果蝇优化算法[J]. 计算机工程与应用, 2018, 54(7): 164-169.
[12]	王彦博，殷红，彭珍瑞，蒋兆远. 混合引力搜索与高斯扰动的精英布谷鸟算法[J]. 计算机工程与应用, 2018, 54(21): 48-55.
[13]	丁晓迪，崔宝同. 带扰动模型失配史密斯预估器的自适应控制[J]. 计算机工程与应用, 2017, 53(6): 223-226.
[14]	孔淑霞，刘艳芹. Jumarie’s修正的R-L分数阶系统的新解法[J]. 计算机工程与应用, 2017, 53(5): 28-30.
[15]	张锦华1，宋来锁2，张元华3，李富昌4. 加权变异策略动态差分进化算法[J]. 计算机工程与应用, 2017, 53(4): 156-162.