Improving the anytime behavior of two-phase local search. (English) Zbl 1234.68362

Summary: Algorithms based on the two-phase local search (TPLS) framework are a powerful method to efficiently tackle multi-objective combinatorial optimization problems. TPLS algorithms solve a sequence of scalarizations, that is, weighted sum aggregations, of the multi-objective problem. Each successive scalarization uses a different weight from a predefined sequence of weights. TPLS requires defining the stopping criterion (the number of weights) a priori, and it does not produce satisfactory results if stopped before completion. Therefore, TPLS has poor “anytime” behavior. This article examines variants of TPLS that improve its “anytime” behavior by adaptively generating the sequence of weights while solving the problem. The aim is to fill the “largest gap” in the current approximation to the Pareto front. The results presented here show that the best adaptive TPLS variants are superior to the “classical” TPLS strategies in terms of anytime behavior, matching, and often surpassing, them in terms of final quality, even if the latter run until completion.


68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)


Full Text: DOI Link


[1] Aneja, Y.P., Nair, K.P.K.: Bicriteria transportation problem. Manag. Sci. 25(1), 73–78 (1979) · Zbl 0442.90056
[2] Beume, N., Naujoks, B., Emmerich M.: SMS-EMOA: multiobjective selection based on dominated hypervolume. Eur. J. Oper. Res. 181(3), 1653–1669 (2007) · Zbl 1123.90064
[3] Conover, W.J.: Practical Nonparametric Statistics, 3rd edn. John Wiley & Sons, New York (1999)
[4] Du, J., Leung, J.Y.T.: Minimizing total tardiness on one machine is NP-hard. Math. Oper. Res. 15(3), 483–495 (1990) · Zbl 0714.90052
[5] Dubois-Lacoste, J., López-Ibáñez, M., Stützle, T.: Effective hybrid stochastic local search algorithms for biobjective permutation flowshop scheduling. In: Blesa, M.J., Blum C., Di Gaspero, L., Roli, A., Sampels, M., Schaerf, A. (eds.) Hybrid Metaheuristics, Lecture Notes in Computer Science, vol. 5818, pp 100–114. Springer, Heidelberg (2009)
[6] Dubois-Lacoste, J., López-Ibáñez, M., Stützle, T.: Adaptive ”anytime” two-phase local search. In: Blum, C., Battiti, R. (eds.) Learning and Intelligent Optimization, 4th International Conference, LION 4, Lecture Notes in Computer Science, vol. 6073, pp. 52–67. Springer, Heidelberg (2010)
[7] Dubois-Lacoste, J., López-Ibáñez, M., Stützle, T.: Supplementary Material: Improving the Anytime Behavior of Two-Phase Local Search. http://iridia.ulb.ac.be/supp/IridiaSupp2010-012 (2010) · Zbl 1234.68362
[8] Dubois-Lacoste, J., López-Ibáñez, M., Stützle, T.: A hybrid TP+PLS algorithm for bi-objective flow-shop scheduling problems. Comput. Oper. Res. 38(8), 1219–1236 (2011) · Zbl 1208.90059
[9] Ehrgott, M., Gandibleux, X.: Approximative solution methods for combinatorial multicriteria optimization. TOP 12(1), 1–88 (2004) · Zbl 1148.90300
[10] Fonseca, C.M., Paquete, L., López-Ibáñez, M.: An improved dimension-sweep algorithm for the hypervolume indicator. In: Proceedings of the 2006 Congress on Evolutionary Computation (CEC 2006), pp. 1157–1163. IEEE Press, Piscataway (2006)
[11] Garey, M.R., Johnson, D.S., Sethi, R.: The complexity of flowshop and jobshop scheduling. Math. Oper. Res. 1, 117–129 (1976) · Zbl 0396.90041
[12] Grunert da Fonseca, V., Fonseca, C.M., Hall, A.O.: Inferential performance assessment of stochastic optimisers and the attainment function. In: Zitzler, E., Deb, K., Thiele, L., Coello, C.A., Corne, D. (eds.) Evolutionary Multi-criterion Optimization (EMO 2001). Lecture Notes in Computer Science, vol. 1993, pp. 213–225. Springer, Heidelberg (2001)
[13] Hoos, H.H., Stützle, T.: Stochastic Local Search–Foundations and Applications. Morgan Kaufmann Publishers, San Francisco (2005) · Zbl 1126.68032
[14] Johnson, D.S.: Optimal two- and three-stage production scheduling with setup times included. Nav. Res. Logist. Q. 1, 61–68 (1954) · Zbl 1349.90359
[15] Knowles, J.D., Corne, D.: Properties of an adaptive archiving algorithm for storing nondominated vectors. IEEE Trans. Evol. Comput. 7(2), 100–116 (2003) · Zbl 05452073
[16] López-Ibáñez, M., Paquete, L., Stützle, T.: Exploratory analysis of stochastic local search algorithms in biobjective optimization. In: Bartz-Beielstein, T., Chiarandini, M., Paquete, L., Preuss, M. (eds.) Experimental Methods for the Analysis of Optimization Algorithms, pp. 209–222. Springer, Berlin (2010) · Zbl 1208.90154
[17] Lust, T., Teghem, J.: Two-phase Pareto local search for the biobjective traveling salesman problem. Journal of Heuristics 16(3), 475–510 (2010) · Zbl 1189.90145
[18] Minella, G., Ruiz, R., Ciavotta, M.: A review and evaluation of multiobjective algorithms for the flowshop scheduling problem. INFORMS J. Comput. 20(3), 451–471 (2008) · Zbl 1243.90069
[19] Paquete, L., Stützle, T.: A two-phase local search for the biobjective traveling salesman problem. In: Fonseca. C.M., et al. (eds.) Evolutionary Multi-criterion Optimization (EMO 2003). Lecture Notes in Computer Science, vol. 2632, pp. 479–493. Springer, Heidelberg (2003) · Zbl 1036.90561
[20] Paquete, L., Stützle, T.: Stochastic local search algorithms for multiobjective combinatorial optimization: a review. In: Gonzalez, T.F. (ed.) Handbook of Approximation Algorithms and Metaheuristics, pp. 29–1–29–15. Chapman & Hall/CRC, Boca Raton (2007)
[21] Paquete, L., Stützle, T.: Design and analysis of stochastic local search for the multiobjective traveling salesman problem. Comput. Oper. Res. 36(9), 2619–2631 (2009) · Zbl 1179.90302
[22] Paquete, L., Chiarandini, M., Stützle, T.: Pareto local optimum sets in the biobjective traveling salesman problem: an experimental study. In: Gandibleux, X., et al. (eds.) Metaheuristics for Multiobjective Optimisation. Lecture Notes in Economics and Mathematical Systems, vol. 535, pp. 177–200. Springer(2004) · Zbl 1070.90102
[23] Ruiz, R., Stützle, T.: A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur. J. Oper. Res. 177(3), 2033–2049 (2007) · Zbl 1110.90042
[24] Zilberstein, S.: Using anytime algorithms in intelligent systems. AI Mag. 17(3), 73–83 (1996)
[25] Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto evolutionary algorithm. IEEE Trans. Evol. Comput. 3(4), 257–271 (1999) · Zbl 05452215
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.