VLR: A Memory-Based Optimization Heuristic

作者: Hansang Yun , Myoung Hoon Ha , Robert Ian McKay

DOI: 10.1007/978-3-319-10762-2_15

关键词:

摘要: We suggest a novel memory-based metaheuristic optimization algorithm, VLR, which uses list of already-visited areas to more effectively search for an optimal solution. chose the Max-cut problem test its performance, comparing it with state-of-the-art methods.VLRdominates previous best-performing heuristics.We also undertake preliminary analysis algorithm’s parameter space, noting that larger memory improves performance. VLR was designed as general-purpose so performance on other problems will be investigated in future.

参考文章(15)
Ron Y. Pinter, Optimal layer assignment for interconnect Advances in VLSI and Computer Systems archive. ,vol. 1, pp. 123- 137 ,(1984) , 10.5555/2334.2335
Richard M. Karp, Reducibility Among Combinatorial Problems Journal of Symbolic Logic. ,vol. 40, pp. 219- 241 ,(2010) , 10.1007/978-3-540-68279-0_8
Fred Glover, Zhipeng Lü, Jin-Kao Hao, Diversification-driven tabu search for unconstrained binary quadratic problems A Quarterly Journal of Operations Research. ,vol. 8, pp. 239- 253 ,(2010) , 10.1007/S10288-009-0115-Y
Rafael Martí, Abraham Duarte, Manuel Laguna, Advanced Scatter Search for the Max-Cut Problem Informs Journal on Computing. ,vol. 21, pp. 26- 38 ,(2009) , 10.1287/IJOC.1080.0275
Michel X. Goemans, David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming Journal of the ACM. ,vol. 42, pp. 1115- 1145 ,(1995) , 10.1145/227683.227684
Bo Song, Victor Li, A hybridization between memetic algorithm and semidefinite relaxation for the max-cut problem genetic and evolutionary computation conference. pp. 425- 432 ,(2012) , 10.1145/2330163.2330224
P. Festa, P.M. Pardalos, M.G.C. Resende, C.C. Ribeiro, RANDOMIZED HEURISTICS FOR THE MAX-CUT PROBLEM Optimization Methods & Software. ,vol. 17, pp. 1033- 1058 ,(2002) , 10.1080/1055678021000090033
Kevin Chen, Nikolaus Rajewsky, The evolution of gene regulation by transcription factors and microRNAs Nature Reviews Genetics. ,vol. 8, pp. 93- 103 ,(2007) , 10.1038/NRG1990
C. Helmberg, F. Rendl, A Spectral Bundle Method for Semidefinite Programming Siam Journal on Optimization. ,vol. 10, pp. 673- 696 ,(1999) , 10.1137/S1052623497328987
Samuel Burer, Renato D. C. Monteiro, Yin Zhang, Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs Siam Journal on Optimization. ,vol. 12, pp. 503- 521 ,(2002) , 10.1137/S1052623400382467