Article
Authors: Clément Legrand, Diego Cattaruzza, Laetitia Jourdan, and Marie-Eléonore Kessaci
Metaheuristics: 15th International Conference, MIC 2024, Lorient, France, June 4–7, 2024, Proceedings, Part I
June 2024
Pages 62 - 77
Published: 17 June 2024 Publication History
- 0citation
- 0
- Downloads
Metrics
Total Citations0Total Downloads0Last 12 Months0
Last 6 weeks0
New Citation Alert added!
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
Manage my Alerts
New Citation Alert!
Please log in to your account
- View Options
- References
- Media
- Tables
- Share
Abstract
Hybridizing learning and optimization often improves existing algorithms in single-objective optimization. Indeed, high-quality solutions often contain relevant knowledge that can be used to guide the heuristic towards promising areas. Learning from the structure of solutions is challenging in combinatorial problems. Most of the time, local optima are considered for this task since they tend to contain more relevant structural information. If local optima generally contain more interesting information than other solutions, producing them requires a time-consuming process. In this paper, we study the benefits of learning from local optima during the execution of a multi-objective algorithm. To this end, we consider a hybridized MOEA/D (a multi-objective genetic algorithm) with a knowledge discovery mechanism adapted to the problem solved and we conduct experiments on a bi-objective vehicle routing problem with time windows. The knowledge discovery mechanism extracts sequences of customers from solutions. The results show the benefit of using different strategies for the components of the knowledge discovery mechanism and the efficacy of extracting patterns from local optima for larger instances. An analysis of speed-up performance gives deeper conclusions about the use of local optima.
References
[1]
Arnold F, Santana Í, Sörensen K, and Vidal T PILS: exploring high-order neighborhoods by pattern mining and injection Pattern Recogn. 2021 116
Digital Library
[2]
Arnold F and Sörensen K Knowledge-guided local search for the vehicle routing problem Comput. Oper. Res. 2019 105 32-46
Digital Library
[3]
Barbalho H, Rosseti I, Martins SL, and Plastino A A hybrid data mining grasp with path-relinking Comput. Oper. Res. 2013 40 12 3159-3173
Digital Library
[4]
Benitez-Hidalgo A, Nebro AJ, Garcia-Nieto J, Oregi I, and Del Ser J jMetalPy: a python framework for multi-objective optimization with metaheuristics Swarm Evol. Comput. 2019 51
[5]
Blot A, Marmion M, and Jourdan L Survey and unification of local search techniques in metaheuristics for multi-objective combinatorial optimisation J. Heuristics 2018 24 6 853-877
[6]
Castro-Gutierrez, J., Landa-Silva, D., Pérez, J.M.: Nature of real-world multi-objective vehicle routing with evolutionary algorithms. In: 2011 IEEE International Conference on Systems, Man, and Cybernetics, pp.257–264. IEEE (2011)
[7]
Coello Coello CA, Dhaenens C, and Jourdan L Coello Coello CA, Dhaenens C, and Jourdan L Multi-objective combinatorial optimization: problematic and context Advances in Multi-Objective Nature Inspired Computing 2010 Heidelberg Springer 1-21
[8]
Corne D, Dhaenens C, and Jourdan L Synergies between operations research and data mining: the emerging use of multi-objective approaches Eur. J. Oper. Res. 2012 221 3 469-479
[9]
Deb K, Pratap A, Agarwal S, and Meyarivan T A fast and elitist multiobjective genetic algorithm: NSGA-II IEEE Trans. Evol. Comput. 2002 6 2 182-197
Digital Library
[10]
Khalil, E., Dai, H., Zhang, Y., Dilkina, B., Song, L.: Learning combinatorial optimization algorithms over graphs. In: Advances in Neural Information Processing Systems, vol. 30 (2017)
[11]
Knowles, J.D.: Local-search and hybrid evolutionary algorithms for Pareto optimization. Ph.D. thesis, University of Reading Reading (2002)
[12]
Kora P and Yadlapalli P Crossover operators in genetic algorithms: a review Int. J. Comput. Appl. 2017 162 10
[13]
Land, M.W.S.: Evolutionary algorithms with local search for combinatorial optimization. University of California, San Diego (1998)
[14]
Legrand, C., Cattaruzza, D., Jourdan, L., Kessaci, M.-E.: Improving neighborhood exploration into MOEA/D framework to solve a bi-objective routing problem. Int. Trans. Oper. Res. (2023)
[15]
López-Ibáñez M, Dubois-Lacoste J, Cáceres LP, Birattari M, and Stützle T The irace package: iterated racing for automatic algorithm configuration Oper. Res. Perspect. 2016 3 43-58
[16]
Ma X et al. MOEA/D with opposition-based learning for multiobjective optimization problem Neurocomputing 2014 146 48-64
Digital Library
[17]
Riquelme, N., VonLücken, C., Baran, B.: Performance metrics in multi-objective optimization. In: 2015 Latin American computing conference (CLEI), pp.1–11. IEEE (2015)
[18]
Schneider M, Schwahn F, and Vigo D Designing granular solution methods for routing problems with time windows Eur. J. Oper. Res. 2017 263 2 493-509
[19]
Solomon MM Algorithms for the vehicle routing and scheduling problems with time window constraints Oper. Res. 1987 35 2 254-265
Digital Library
[20]
Subramanian A, Uchoa E, and Ochi LS A hybrid algorithm for a class of vehicle routing problems Comput. Oper. Res. 2013 40 10 2519-2531
[21]
Talbi E-G Machine learning into metaheuristics: A survey and taxonomy ACM Comput. Surv. (CSUR) 2021 54 6 1-32
Digital Library
[22]
Toth P and Vigo D The granular tabu search and its application to the vehicle-routing problem INFORMS J. Comput. 2003 15 4 333-346
Digital Library
[23]
Toth, P., Vigo, D.: Vehicle Routing: Problems, Methods, and Applications. SIAM (2014)
[24]
Uchoa E, Pecin D, Pessoa A, Poggi M, Vidal T, and Subramanian A New benchmark instances for the capacitated vehicle routing problem Eur. J. Oper. Res. 2017 257 3 845-858
[25]
Vidal T, Crainic TG, Gendreau M, and Prins C A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows Comput. Oper. Res. 2013 40 1 475-489
Digital Library
[26]
Vidal, T., Crainic, T.G., Gendreau, M., Prins, C.: A unified solution framework for multi-attribute vehicle routing problems. Eur. J. Oper. Res. (2014)
[27]
Xu Q, Xu Z, and Ma T A survey of multiobjective evolutionary algorithms based on decomposition: variants, challenges and future directions IEEE Access 2020 8 41588-41614
[28]
Zhang Q and Li H MOEA/D: a multiobjective evolutionary algorithm based on decomposition IEEE Trans. Evol. Comput. 2007 11 6 712-731
Digital Library
[29]
Zitzler E, Thiele L, Laumanns M, Fonseca CM, and Da Fonseca VG Performance assessment of multiobjective optimizers: an analysis and review IEEE Trans. Evol. Comput. 2003 7 2 117-132
Digital Library
Recommendations
- Local search effects in bi-objective orienteering
GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference
We analyze the effects of including local search techniques into a multi-objective evolutionary algorithm for solving a bi-objective orienteering problem with a single vehicle while the two conflicting objectives are minimization of travel time and ...
Read More
- A bi-objective iterated local search heuristic with path-relinking for the p-median problem
EMO'11: Proceedings of the 6th international conference on Evolutionary multi-criterion optimization
In this paper, we examine the p-median problem from a bi-objective point of view. Since this is a NP-Hard problem, an efficient algorithm based on the Iterated Local Search heuristic (ILS) is proposed to determine nondominated solutions (an ...
Read More
- Local search algorithms for the k-cardinality tree problem
In this paper we deal with an NP-hard combinatorial optimization problem, the k-cardinality tree problem in node-weighted graphs. This problem has several applications, which justify the need for efficient methods to obtain good solutions. We review ...
Read More
Comments
Information & Contributors
Information
Published In
Metaheuristics: 15th International Conference, MIC 2024, Lorient, France, June 4–7, 2024, Proceedings, Part I
Jun 2024
403 pages
ISBN:978-3-031-62911-2
DOI:10.1007/978-3-031-62912-9
- Editors:
- Marc Sevaux
Centre de Recherche, Université Bretagne Sud, Lorient, France
, - Alexandru-Liviu Olteanu
Centre de Recherche, Université Bretagne Sud, LORIENT, France
, - Eduardo G. Pardo
https://ror.org/01v5cv687Universidad Rey Juan Carlos, Móstoles, Spain
, - Angelo Sifaleras
https://ror.org/05fg6gr82University of Macedonia, Thessaloniki, Greece
, - Salma Makboul
https://ror.org/01qhqcj41Université de Technologie de Troyes, Troyes Cedex, France
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 17 June 2024
Author Tags
- Combinatorial Optimization
- Multi-Objective Optimization
- Online Learning
- Genetic Algorithm
- Local Search
Qualifiers
- Article
Contributors
Other Metrics
View Article Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
Total Citations
Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Other Metrics
View Author Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in
Full Access
Get this Publication
Media
Figures
Other
Tables
