×

On local optima in multiobjective combinatorial optimization problems. (English) Zbl 1145.90067

Summary: In this article, local optimality in multiobjective combinatorial optimization is used as a baseline for the design and analysis of two iterative improvement algorithms. Both algorithms search in a neighborhood that is defined on a collection of sets of feasible solutions and their acceptance criterion is based on outperformance relations. Proofs of the soundness and completeness of these algorithms are given.

MSC:

90C29 Multi-objective and goal programming
90C27 Combinatorial optimization

Software:

PAES
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aarts, E. H. L., & Lenstra, J. K. (Eds.). (1997). Local search in combinatorial optimization. Chichester: Wiley. · Zbl 0869.00019
[2] Angel, E., Bampis, E., & Gourvés, L. (2004a). Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem. Theoretical Computer Science, 310, 135–146. · Zbl 1067.90056 · doi:10.1016/S0304-3975(03)00376-1
[3] Angel, E., Bampis, E., & Gourvés, L. (2004b). A dynasearch neighborhood for the bicriteria traveling salesman problem. In X. Gandibleux, M. Sevaux, K. Sörensen & V. T’kindt (Eds.), Lecture notes in economics and mathematical systems : Vol. 535. Metaheuristics for multiobjective optimisation (pp. 153–176). Berlin: Springer. · Zbl 1162.90537
[4] Deb, K. (1999). Multi-objective genetic algorithms: problem difficulties and construction of test problems. Evolutionary Computation, 7(3), 205–230. · Zbl 05412758 · doi:10.1162/evco.1999.7.3.205
[5] Ehrgott, M. (2000). Lecture notes in economics and mathematical systems: Vol. 491. Multicriteria optimization. Heidelberg: Springer. · Zbl 0956.90039
[6] Ehrgott, M., & Gandibleux, X. (2004). Approximative solution methods for combinatorial multicriteria optimization. TOP, 12(1), 1–90. · Zbl 1148.90300 · doi:10.1007/BF02578918
[7] Emelichev, V., & Perepelitsa, V. (1991). Complexity of vector optimization problems on graphs. Optimization, 6, 903–918. · Zbl 0736.90065
[8] Emelichev, V., & Perepelitsa, V. (1992). On the cardinality of the set of alternatives in discrete many-criterion problems. Discrete Mathematics and Applications, 2(5), 461–471. · Zbl 0787.90085 · doi:10.1515/dma.1992.2.5.461
[9] Erlebach, T., Kellerer, H., & Pferschy, U. (2002). Approximating multiobjective knapsack problems. Management Science, 48(12), 1603–1612. · Zbl 1232.90324 · doi:10.1287/mnsc.48.12.1603.445
[10] Fonseca, C., Fleming, P., Zitzler, E., Deb, K., & Thiele, L. (Eds.). (2003). Lecture notes in computer science: Vol. 2632. Evolutionary multi-criterion optimization (EMO 2003). Berlin: Springer.
[11] Hamacher, H., & Ruhe, G. (1994). On spanning tree problems with multiple objectives. Annals of Operations Research, 5, 209–230. · Zbl 0821.90126 · doi:10.1007/BF02032304
[12] Hansen, M., & Jaszkiewicz, A. (1998). Evaluating the quality of approximations to the non-dominated set (Technical report IMM-REP-1998-7). Institute of Mathematical Modelling, Technical University of Denmark, Lyngby, Denmark.
[13] Hansen, P. (1979). Bicriterion path problems. In Lecture notes in economics and mathematical systems : Vol. 177. Multiple criteria decision making theory and application (pp. 109–127). Berlin: Springer.
[14] Hansen, P., & Mladenović, N. (2002). Variable neighborhood search. In F. Glover & G. Kochenberger (Eds.), Handbook of metaheuristics (pp. 145–184). Norwell: Kluwer Academic. · Zbl 1102.90371
[15] Hoos, H. H., & Stützle, T. (2004). Stochastic local search–foundations and applications. San Francisco: Morgan Kaufmann. · Zbl 1126.68032
[16] Jörnsten, K., Andersen, K., & Lind, M. (1996). On bicriterion minimal spanning trees: an approximation. Computers & Operations Research, 23(12), 1171–1182. · Zbl 0876.90087 · doi:10.1016/S0305-0548(96)00026-3
[17] Knowles, J., & Corne, D. (1999). The Pareto archived evolution strategy: a new base line algorithm for multiobjective optimisation. In Proceedings of the 1999 congress on evolutionary computation (CEC’99) (pp. 98–105). Washington.
[18] Knowles, J., & Corne, D. (2000). Approximating the nondominated front using the Pareto archived evolution strategy. Evolutionary Computation, 8(2), 149–172. · Zbl 05412708 · doi:10.1162/106365600568167
[19] Knowles, J., & Corne, D. (2004). Bounded Pareto archiving: theory and practice. In X. Gandibleux, M. Sevaux, K. Sörensen & V. T’kindt (Eds.), Lecture notes in economics and mathematical systems : Vol. 535. Metaheuristics for multiobjective optimisation (pp. 39–64). Berlin: Springer. · Zbl 1140.90489
[20] Kung, H., Luccio, F., & Preparata, F. (1975). On finding the maxima of a set of vectors. Journal of the Association for Computing Machinery, 22(4), 469–476. · Zbl 0316.68030
[21] Laumanns, M., Thiele, L., Zitzler, E., Welzl, E., & Deb, K. (2002). Running time analysis of multi-objective evolutionary algorithms on a simple discrete optimization problem. In J. M. Guervos et al. (Eds.), Lecture notes in computer science : Vol. 2439. Proceedings of PPSN-VII (pp. 44–53). Berlin: Springer.
[22] Moscato, P. (1999). Memetic algorithms: a short introduction. In D. Corne & M. Dorigo (Eds.), New ideas in optimization (pp. 219–234). London: McGraw-Hill.
[23] Papadimitriou, C. H., & Yannakakis, M. (2000). On the approximability of trade-offs and optimal access of web sources. In Proceedings of the 41st annual symposium on foundations of computer science (FOCS 2000) (pp. 86–92).
[24] Paquete, L., Chiarandini, M., & Stützle, T. (2002). A study of local optima in the multiobjective traveling salesman problem (Technical report AIDA-02-07). Fachgebiet Intellektik, Fachbereich Informatik, Technische Universität Darmstadt. Presented at the multiobjective metaheuristics workshop (MOMH 2002), Paris, 4–5 November 2002. · Zbl 1070.90102
[25] Paquete, L., Chiarandini, M., & Stützle, T. (2004). Pareto local optimum sets in the biobjective traveling salesman problem: an experimental study. In X. Gandibleux, M. Sevaux K. Sörensen & V. T’kindt (Eds.), Lecture notes in economics and mathematical systems : Vol. 535. Metaheuristics for multiobjective optimisation (pp. 177–200). Berlin: Springer. · Zbl 1070.90102
[26] Paquete, L., & Stützle, T. (2003). A two-phase local search for the biobjective traveling salesman problem. In C. Fonseca, P. Fleming, E. Zitzler, K. Deb & L. Thiele (Eds.), Lecture notes in computer science : Vol. 2632. Evolutionary multi-criterion optimization (EMO 2003) (pp. 479–493). New York: Springer. · Zbl 1036.90561
[27] Paquete, L., & Stützle, T. (2006). A study of stochastic local search algorithms for the biobjective QAP with correlated flow matrices. European Journal of Operational Research, 169(3), 943–959. · Zbl 1079.90113 · doi:10.1016/j.ejor.2004.08.024
[28] Ruhe, G., & Fruhwirth, B. (1990). {\(\epsilon\)}-optimality for bicriteria programs and its application to minimum cost flows. Computing, 44(1), 21–34. · Zbl 0694.90092 · doi:10.1007/BF02247962
[29] Schott, J. R. (1995). Fault tolerant design using single and multicriteria genetic algorithm optimization. Master’s thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, MA.
[30] Serafini, P. (1986). Some considerations about computational complexity for multiobjective combinatorial problems. In Lecture notes in economics and mathematical systems : Vol. 294. Recent advances and historical development of vector optimization (pp. 222–231). Berlin: Springer.
[31] Talbi, E. G. (2003). A hybrid evolutionary approach for multicriteria optimization problems: application to the flow shop. In C. Fonseca, P. Fleming, E. Zitzler K. Deb & L. Thiele (Eds.), Lecture notes in computer science : Vol. 2632. Evolutionary multi-criterion optimization (EMO 2003) (pp. 416–428). Berlin: Springer.
[32] Warburton, A. (1987). Approximation of Pareto optima in multi-objective shortest-path problems. Operations Research, 35(1), 70–79. · Zbl 0623.90084 · doi:10.1287/opre.35.1.70
[33] Zitzler, E., Deb, K., Thiele, L., Coello, C. A., & Corne, D. (Eds.). (2001). In Lecture notes in computer science: Vol. 1993. Evolutionary multi-criterion optimization (EMO 2001). Berlin: Springer.
[34] Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C. M., & Fonseca, V. G. (2003). Performance assessment of multiobjective optimizers: an analysis and review. IEEE Transactions on Evolutionary Computation, 7(2), 117–132. · Zbl 05452216 · doi:10.1109/TEVC.2003.810758
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.