Page 267 - 《软件学报》2025年第8期

3690 软件学报 2025 年第 36 卷第 8 期

Theoretical Nanoscience, 2014, 11(12): 2476–2480. [doi: 10.1166/jctn.2014.3664]
[11] Zhang ZQ, Li ZW, Qiao XB, Wang WJ. An efficient memetic algorithm for the minimum load coloring problem. Mathematics, 2019,
7(5): 475. [doi: 10.3390/math7050475]
[12] Herrán A, Colmenar JM, Mladenović N, Duarte A. A general variable neighborhood search approach for the minimum load coloring
problem. Optimization Letters, 2023, 17(9): 2065–2086. [doi: 10.1007/s11590-022-01861-1]
[13] Cai SW. Balance between complexity and quality: Local search for minimum vertex cover in massive graphs. In: Proc. of the 24th Int’l
Joint Conf. on Artificial Intelligence. Buenos Aires: AAAI, 2015. 747–753.
[14] Wang YY, Cai SW, Chen JJ, Yin MH. A fast local search algorithm for minimum weight dominating set problem on massive graphs. In:
Proc. of the 27th Int’l Joint Conf. on Artificial Intelligence. Stockholm: AAAI, 2018. 1514–1522.
[15] Wang YY, Cai SW, Pan SW, Li XM, Yin MH. Reduction and local search for weighted graph coloring problem. In: Proc. of the 34th
AAAI Conf. on Artificial Intelligence. New York: AAAI, 2020. 2433–2441. [doi: 10.1609/aaai.v34i03.5624]
[16] Chu Y, Liu BX, Cai SW, Luo C, You HH. An efficient local search algorithm for solving maximum edge weight clique problem in large
graphs. Journal of Combinatorial Optimization, 2020, 39(4): 933–954. [doi: 10.1007/s10878-020-00529-9]
[17] Zhou YM, Hao JK, Duval B. Reinforcement learning based local search for grouping problems: A case study on graph coloring. Expert
Systems with Applications, 2016, 64: 412–422. [doi: 10.1016/j.eswa.2016.07.047]
[18] Wu QH, Wang Y, Glover F. Advanced tabu search algorithms for bipartite Boolean quadratic programs guided by strategic oscillation
and path relinking. INFORMS Journal on Computing, 2019, 32(1): 74–89. [doi: 10.1287/ijoc.2018.0871]
[19] Liu H, Zhang JY, Zhang XD, Kurniawan A, Juhana T, Ai B. Tabu-search-based pilot assignment for cell-free massive MIMO systems.
IEEE Trans. on Vehicular Technology, 2020, 69(2): 2286–2290. [doi: 10.1109/TVT.2019.2956217]
[20] Wu QH, Hao JK. Memetic search for the max-bisection problem. Computers & Operations Research, 2013, 40(1): 166–179. [doi: 10.
1016/j.cor.2012.06.001]
[21] Zhou YM, Duval B, Hao JK. Improving probability learning based local search for graph coloring. Applied Soft Computing, 2018, 65:
542–553. [doi: 10.1016/j.asoc.2018.01.027]
[22] Wang YY, Pan SW, Li CX, Yin MH. A local search algorithm with reinforcement learning based repair procedure for minimum weight
independent dominating set. Information Sciences, 2020, 512: 533–548. [doi: 10.1016/j.ins.2019.09.059]
[23] Qin T, Peng B, Benlic U, Cheng TCE, Wang Y, Lü ZP. Iterated local search based on multi-type perturbation for single-machine
earliness/tardiness scheduling. Computers & Operations Research, 2015, 61: 81–88. [doi: 10.1016/j.cor.2015.03.005]
[24] Cai SW, Su KL, Luo C, Sattar A. NuMVC: An efficient local search algorithm for minimum vertex cover. Journal of Artificial
Intelligence Research, 2013, 46(1): 687–716. [doi: 10.1613/jair.3907]
[25] Lin JK, Cai SW, Luo C, Su KL. A reduction based method for coloring very large graphs. In: Proc. of the 26th Int’l Joint Conf. on
Artificial Intelligence. Melbourne: ijcai.org, 2017. 517–523. [doi: 10.24963/ijcai.2017/73]
[26] Wu QH, Wang Y, Lü ZP. A tabu search based hybrid evolutionary algorithm for the max-cut problem. Applied Soft Computing, 2015,
34: 827–837. [doi: 10.1016/j.asoc.2015.04.033]
[27] Ma FD, Hao JK, Wang Y. An effective iterated tabu search for the maximum bisection problem. Computers & Operations Research,
2017, 81: 78–89. [doi: 10.1016/j.cor.2016.12.012]
[28] Tian XL, Ouyang DT, Sun R, Zhou HS, Zhang LM. Two efficient local search algorithms for the vertex bisection minimization problem.
Information Sciences, 2022, 609: 153–171. [doi: 10.1016/j.ins.2022.07.106]

附录 A

表 A1 IRLTS 算法与 3 个对比算法的具体实验结果

GVNS MS-GVNS RLTS IRLTS
Graph |V|
best avg time (s) best avg time (s) best avg time (s) best avg time (s)
ia-email-univ 1 133 2 348 2 310.2 855.123 2 360 2 351.9 1 099.54 2 374 2 341.7 939.629 2 371 2 337.6 508.084
ia-fb-messages 1 266 2 426 2 408.5 892.697 2 432 2 418.8 1 218.91 2 447 2 445.7 1 023.95 2 447 2 445.6 879.883
web-google 1 299 1 368 1 362.5 720.411 1 369 1 364 792.187 1 374 1 370.7 1 071.02 1 374 1 369.7 983.929
bio-yeast 1 458 906 901.3 979.732 909 901.5 1 024.58 926 923.4 988.297 927 924.9 1 321.1
scc_rt_voteonedirection 1 833 2 2 0.110 235 2 2 0.178 833 2 2 6.408 63 2 2 8.054 6
ca-CSphd 1 882 855 851.1 982.513 856 850.8 878.149 864 861.8 925.614 864 863.1 1 077.01
scc_fb-messages 1 899 156 922 156 551 959.498 156 892 156 717 1 214.68 156 317 156 116 1 298.93 156 435 156 159 1 114.43