Abstract
Given the availability of high-performing local search (LS) for single-objective (SO) optimisation problems, a successful approach to tackle their multi-objective (MO) counterparts is scalarisation-based local search (SBLS). SBLS strategies solve multiple scalarisations, aggregations of the multiple objectives into a single scalar value, with varying weights. They have been shown to work specially well as the initialisation phase of other types of MO local search, e.g., Pareto local search (PLS). A drawback of existing SBLS strategies is that the underlying SO-LS method is unaware of the MO nature of the problem and returns only a single solution, discarding any intermediate solutions that may be of interest. We propose here two new SBLS initialisation strategies (ChangeRestart and ChangeDirection) that overcome this drawback by augmenting the underlying SO-LS method with an archive of nondominated solutions used to dynamically update the scalarisations. The new strategies produce better results on the bi-objective permutation flowshop problem than other five SBLS strategies from the literature, not only on their own but also when used as the initialisation phase of PLS.
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
Blot, A., Jourdan, L., Kessaci-Marmion, M.E.: Automatic design of multi-objective local search algorithms: case study on a bi-objective permutation flowshop scheduling problem. In: GECCO 2017, pp. 227–234. ACM Press (2017)
Drugan, M.M., Thierens, D.: Path-guided mutation for stochastic Pareto local search algorithms. In: Schaefer, R., Cotta, C., Kołodziej, J., Rudolph, G. (eds.) PPSN 2010. LNCS, vol. 6238, pp. 485–495. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15844-5_49
Dubois-Lacoste, J., López-Ibáñez, M., Stützle, T.: A hybrid TP\(+\)PLS algorithm for bi-objective flow-shop scheduling problems. COR 38(8), 1219–1236 (2011)
Dubois-Lacoste, J., López-Ibáñez, M., Stützle, T.: Improving the anytime behavior of two-phase local search. AMAI 61(2), 125–154 (2011)
Dubois-Lacoste, J., López-Ibáñez, M., Stützle, T.: Combining two search paradigms for multi-objective optimization: two-phase and Pareto local search. In: Talbi, E.G. (ed.) Hybrid Metaheuristics, vol. 434, pp. 97–117. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-30671-6_3
Dubois-Lacoste, J., López-Ibáñez, M., Stützle, T.: Anytime Pareto local search. EJOR 243(2), 369–385 (2015)
Liefooghe, A., Humeau, J., Mesmoudi, S., Jourdan, L., Talbi, E.G.: On dominance-based multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problems. JOH 18(2), 317–352 (2011)
Lust, T., Teghem, J.: The multiobjective multidimensional knapsack problem: a survey and a new approach. ITOR 19(4), 495–520 (2012)
Paquete, L., Chiarandini, M., Stützle, T.: Pareto local optimum sets in the biobjective traveling salesman problem: an experimental study. In: Gandibleux, X., Sevaux, M., Sörensen, K., T’kindt, V. (eds.) Metaheuristics for Multiobjective Optimisation. LNMES, vol. 535, pp. 177–200. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-642-17144-4_7
Paquete, L., Stützle, T.: A two-phase local search for the biobjective traveling salesman problem. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Thiele, L., Deb, K. (eds.) EMO 2003. LNCS, vol. 2632, pp. 479–493. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36970-8_34
Paquete, L., Stützle, T.: Stochastic local search algorithms for multiobjective combinatorial optimization: a review. In: Handbook of Approximation Algorithms and Metaheuristics, pp. 29-1–29-15. Chapman & Hall/CRC (2007)
Ruiz, R., Stützle, T.: A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. EJOR 177(3), 2033–2049 (2007)
Taillard, É.D.: Benchmarks for basic scheduling problems. EJOR 64(2), 278–285 (1993)
Zhang, Q., Li, H.: MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE TEC 11(6), 712–731 (2007)
Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M., Grunert da Fonseca, V.: Performance assessment of multiobjective optimizers: an analysis and review. IEEE TEC 7(2), 117–132 (2003)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Blot, A., López-Ibáñez, M., Kessaci, MÉ., Jourdan, L. (2018). New Initialisation Techniques for Multi-objective Local Search. In: Auger, A., Fonseca, C., Lourenço, N., Machado, P., Paquete, L., Whitley, D. (eds) Parallel Problem Solving from Nature – PPSN XV. PPSN 2018. Lecture Notes in Computer Science(), vol 11101. Springer, Cham. https://doi.org/10.1007/978-3-319-99253-2_26
Download citation
DOI: https://doi.org/10.1007/978-3-319-99253-2_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-99252-5
Online ISBN: 978-3-319-99253-2
eBook Packages: Computer ScienceComputer Science (R0)