Abstract
The multi-level paradigm is a simple and useful approach to tackle a number of combinatorial optimization problems. In this paper, we investigate a multi-objective multi-level algorithm to solve the bi-criteria maximum diversity problem. The computational results indicate that the proposed algorithm is very competitive in comparison with the original multi-objective optimization algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
More information about the benchmark instances of max-cut problem can be found on this website: http://www.stanford.edu/~yyye/yyye/Gset/.
- 2.
More information about the benchmark instances of unconstrained binary quadratic programming problem can be found on this website: http://www.soften.ktu.lt/-gintaras/ubqop\_its.html.
- 3.
More information about the performance assessment package can be found on this website: http://www.tik.ee.ethz.ch/pisa/assessment.html.
References
Alidaee, B., Kochenberger, G.A., Ahmadian, A.: 0-1 quadratic programming approach for the optimal solution of two scheduling problems. Int. J. Syst. Sci. 25, 401–408 (1994)
Aringhieri, R., Cordone, R.: Comparing local search metaheuristics for the maximum diversity problem. J. Oper. Res. Soc. 62(2), 266–280 (2011)
Basseur, M., Liefooghe, A., Le, K., Burke, E.: The efficiency of indicator-based local search for multi-objective combinatorial optimisation problems. J. Heuristics 18(2), 263–296 (2012)
Basseur, M., Zeng, R.-Q., Hao, J.-K.: Hypervolume-based multi-objective local search. Neural Comput. Appl. 21(8), 1917–1929 (2012)
Benlic, U., Hao, J.-K.: An effective multilevel tabu search approach for balanced graph partitioning. Comput. Oper. Res. 38, 1066–1075 (2011)
Benlic, U., Hao, J.-K.: A multilevel memetic approach for improving graph k-partitions. IEEE Trans. Evol. Comput. 15(2), 624–642 (2011)
Benlic, U., Hao, J.-K.: Breakout local search for the max-cut problem. Eng. Appl. Artif. Intell. 26, 1162–1173 (2013)
Brimberg, J., Mladenovic, N., Urosevic, D., Ngai, E.: Variable neighborhood search for the heaviest k-subgraph. Comput. Oper. Res. 36(11), 2885–2891 (2009)
Coello, C.A., Lamont, G.B., Van Veldhuizen, D.A.: Evolutionary Algorithms for Solving Multi-Objective Problems. Genetic and Evolutionary Computation. Springer, New York (2007). https://doi.org/10.1007/978-0-387-36797-2
Freitas, A., Guimaraes, F., Silva, R.C.P.: Memetic self-adaptive evolution strategies applied to the maximum diversity problem. Optim. Lett. 8(2), 705–714 (2014)
Gallego, M., Duarte, A., Laguna, M., Marti, R.: Hybrid heuristics for the maximum diversity problem. Comput. Optim. Appl. 200(1), 36–44 (2009)
Gallo, G., Hammer, P., Simeone, B.: Quadratic knapsack problems. Math. Program. 12, 132–149 (1980)
Liefooghe, A., Verel, S., Paquete, L., Hao, J.-K.: Experiments on local search for bi-objective unconstrained binary quadratic programming. In: Proceedings of the 8th International Conference on Evolutionary Multi-criterion Optimization (EMO 2015), Guimarães, Portugal, pp. 171–186 (2015)
Lü, Z., Glover, F., Hao, J.-K.: A hybrid metaheuristic approach to solving the UBQP problem. Eur. J. Oper. Res. 207, 1254–1262 (2010)
Palubeckis, G.: Iterated tabu search for the maximum diversity problem. Optim. Lett. 189(1), 371–383 (2007)
Wang, Y., Hao, J., Glover, F., Lü, Z.: A tabu search based memetic algorithm for the maximum diversity problem. Eng. Appl. Artif. Intell. 27, 103–114 (2014)
Wu, Q., Wang, Y., Lü, Z.: A tabu search based hybrid evolutionary algorithm for the max-cut problem. Appl. Soft Comput. 34, 827–837 (2015)
Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. Evol. Comput. 3, 257–271 (1999)
Acknowledgments
The work in this paper was supported by the Fundamental Research Funds for the Central Universities (Grant No. A0920502051722-53) and supported by the West Light Foundation of Chinese Academy of Science (Grant No: Y4C0011001).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Xue, LY., Zeng, RQ., Xu, HY., Wen, Y. (2018). Solving Bi-criteria Maximum Diversity Problem with Multi-objective Multi-level Algorithm. In: Huang, DS., Gromiha, M., Han, K., Hussain, A. (eds) Intelligent Computing Methodologies. ICIC 2018. Lecture Notes in Computer Science(), vol 10956. Springer, Cham. https://doi.org/10.1007/978-3-319-95957-3_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-95957-3_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-95956-6
Online ISBN: 978-3-319-95957-3
eBook Packages: Computer ScienceComputer Science (R0)