Abstract
Iterated Local Search (ILS) is a simple yet powerful optimisation method that iteratively invokes a local search procedure with renewed starting points by perturbation. Due to the complexity of search landscape, different ILS strategies may better suit different problem instances or different search stages. To address this issue, this work proposes a new ILS framework which selects the most suited components of ILS based on evolutionary meta-learning. It has three additional components other than ILS: meta-feature extraction, meta-learning and classification. The meta-feature and meta-learning steps are to generate a multi-class classifier by training on a set of existing problem instances. The generated classifier then selects the most suitable ILS setting when performing on new instances. The classifier is generated by Genetic Programming. The effectiveness of the proposed ILS framework is demonstrated on the Google Machine Reassignment Problem. Experimental results show that the proposed framework is highly competitive compared to 10 state-of-the-art methods reported in the literature.
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
Similar content being viewed by others
References
Roadef/euro challenge 2012: Machine reassignment. http://challenge.roadef.org/2012/en/
Afsar, H.M., Artigues, C., Bourreau, E., Kedad-Sidhoum, S.: Machine reassignment problem: the ROADEF/EURO challenge 2012. Ann. Oper. Res. 242(1), 1–17 (2016)
Armbrust, M., Fox, A., Griffith, R., Joseph, A.D., Katz, R., Konwinski, A., Lee, G., Patterson, D., Rabkin, A., Stoica, I., et al.: A view of cloud computing. Commun. ACM 53(4), 50–58 (2010)
Brandt, F., Speck, J., Völker, M.: Constraint-based large neighborhood search for machine reassignment. Ann. Oper. Res. 242(1), 63–91 (2016)
Calheiros, R.N., Ranjan, R., Beloglazov, A., De Rose, C.A., Buyya, R.: Cloudsim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms. Softw.: Practice Experience 41(1), 23–50 (2011)
de Carvalho, A.C.P.L.F., Freitas, A.A.: A tutorial on multi-label classification techniques. In: Abraham, A., Hassanien, AE., Snáŝel, V. (eds.) Foundations of Computational Intelligence, Studies in Computational Intelligence, vol. 5, pp. 177–195. Springer, Heidelberg (2009). doi:10.1007/978-3-642-01536-6_8
García, S., Fernández, A., Luengo, J., Herrera, F.: Advanced nonparametric tests for multiple comparisons in the design of experiments in computational intelligence and data mining: experimental analysis of power. Inf. Sci. 180(10), 2044–2064 (2010)
Gavranović, H., Buljubašić, M., Demirović, E.: Variable neighborhood search for Google machine reassignment problem. Electron. Notes Discrete Math. 39, 209–216 (2012)
Lopes, R., Morais, V.W.C., Noronha, T.F., Souza, V.A.A.: Heuristics and matheuristics for a real-life machine reassignment problem. Int. Trans. Oper. Res. 22(1), 77–95 (2015)
Lourenço, H.R., Martin, O., Stützle, T.: A beginners introduction to iterated local search. In: Proceedings of MIC, pp. 1–6 (2001)
Lourenço, H.R., Martin, O.C., Stützle, T.: Iterated local search. In: Glover, F., Kochenberger, G.A. (eds.) Handbook of Metaheuristics. International Series in Operations Research and Management Science, vol. 57, pp. 320–353. Springer, Heidelberg (2003). doi:10.1007/0-306-48056-5_11
Lourenço, H.R., Martin, O.C., Stützle, T.: Iterated local search: framework and applications. In: Gendreau, M., Potvin, J.Y. (eds.) Handbook of Metaheuristics. International Series in Operations Research and Management Science, vol. 146, pp. 363–397. Springer, Heidelberg (2010). doi:10.1007/978-1-4419-1665-5_12
Malitsky, Y., Mehta, D., O’Sullivan, B., Simonis, H.: Tuning parameters of large neighborhood search for the machine reassignment problem. In: Gomes, C., Sellmann, M. (eds.) CPAIOR 2013. LNCS, vol. 7874, pp. 176–192. Springer, Heidelberg (2013). doi:10.1007/978-3-642-38171-3_12
Masson, R., Vidal, T., Michallet, J., Penna, P.H.V., Petrucci, V., Subramanian, A., Dubedout, H.: An iterated local search heuristic for multi-capacity bin packing and machine reassignment problems. Expert Syst. Appl. 40(13), 5266–5275 (2013)
Mehta, D., O’Sullivan, B., Simonis, H.: Comparing solution methods for the machine reassignment problem. In: Milano, M. (ed.) CP 2012. LNCS, pp. 782–797. Springer, Heidelberg (2012). doi:10.1007/978-3-642-33558-7_56
Portal, G.M., Ritt, M., Borba, L.M., Buriol, L.S.: Simulated annealing for the machine reassignment problem. Ann. Oper. Res. 242(1), 93–114 (2016)
Ritt, M.R.P.: An algorithmic study of the machine reassignment problem. Ph.D. thesis, Universidade Federal do Rio Grande do Sul (2012)
Sabar, N.R., Song, A.: Grammatical evolution enhancing simulated annealing for the load balancing problem in cloud computing. In: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference, pp. 997–1003. ACM (2016)
Sabar, N.R., Song, A., Zhang, M.: A variable local search based memetic algorithm for the load balancing problem in cloud computing. In: Squillero, G., Burelli, P. (eds.) EvoApplications 2016. LNCS, vol. 9597, pp. 267–282. Springer, Cham (2016). doi:10.1007/978-3-319-31204-0_18
Turky, A., Moser, I., Aleti, A.: An iterated local search with guided perturbation for the heterogeneous fleet vehicle routing problem with time windows and three-dimensional loading constraints. In: Wagner, M., Li, X., Hendtlass, T. (eds.) ACALCI 2017. LNCS, vol. 10142, pp. 279–290. Springer, Cham (2017). doi:10.1007/978-3-319-51691-2_24
Turky, A., Sabar, N.R., Sattar, A., Song, A.: Parallel late acceptance Hill-Climbing algorithm for the Google machine reassignment problem. In: Kang, B.H., Bai, Q. (eds.) AI 2016. LNCS, vol. 9992, pp. 163–174. Springer, Cham (2016). doi:10.1007/978-3-319-50127-7_13
Turky, A., Sabar, N.R., Song, A.: An evolutionary simulating annealing algorithm for Google machine reassignment problem. In: Leu, G., Singh, H.K., Elsayed, S. (eds.) Intelligent and Evolutionary Systems. PALO, vol. 8, pp. 431–442. Springer, Cham (2017). doi:10.1007/978-3-319-49049-6_31
Turky, A., Sabar, N.R., Song, A.: Cooperative evolutionary heterogeneous simulated annealing algorithm for Google machine reassignment problem. In: Genetic Programming and Evolvable Machines, pp. 1–28 (2017). doi:10.1007/s10710-017-9305-0
Turky, A., Sabar, N.R., Song, A.: Neighbourhood analysis: a case study on Google machine reassignment problem. In: Wagner, M., Li, X., Hendtlass, T. (eds.) ACALCI 2017. LNCS, vol. 10142, pp. 228–237. Springer, Cham (2017). doi:10.1007/978-3-319-51691-2_20
Wang, Z., Lü, Z., Ye, T.: Multi-neighborhood local search optimization for machine reassignment problem. Comput. Oper. Res. 68, 16–29 (2016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Turky, A., Sabar, N.R., Sattar, A., Song, A. (2017). Evolutionary Learning Based Iterated Local Search for Google Machine Reassignment Problems. In: Shi, Y., et al. Simulated Evolution and Learning. SEAL 2017. Lecture Notes in Computer Science(), vol 10593. Springer, Cham. https://doi.org/10.1007/978-3-319-68759-9_34
Download citation
DOI: https://doi.org/10.1007/978-3-319-68759-9_34
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-68758-2
Online ISBN: 978-3-319-68759-9
eBook Packages: Computer ScienceComputer Science (R0)