×

zbMATH — the first resource for mathematics

A parallel multiple reference point approach for multi-objective optimization. (English) Zbl 1188.90237
Summary: This paper presents a multiple reference point approach for multi-objective optimization problems of discrete and combinatorial nature. When approximating the Pareto Frontier, multiple reference points can be used instead of traditional techniques. These multiple reference points can easily be implemented in a parallel algorithmic framework. The reference points can be uniformly distributed within a region that covers the Pareto Frontier. An evolutionary algorithm is based on an achievement scalarizing function that does not impose any restrictions with respect to the location of the reference points in the objective space. Computational experiments are performed on a bi-objective flow-shop scheduling problem. Results, quality measures as well as a statistical analysis are reported in the paper.

MSC:
90C29 Multi-objective and goal programming
68W10 Parallel algorithms in computer science
90C59 Approximation methods and heuristics in mathematical programming
90B35 Deterministic scheduling theory in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bleuler, S.; Laumanns, M.; Thiele, L.; Zitzler, E., PISA - A platform and programming language independent interface for search algorithms, (), 494-508 · Zbl 1037.68743
[2] Cahon, S.; Melab, N.; Talbi, E.-G., Paradiseo: A framework for the reusable design of parallel and distributed metaheuristics, Journal of heuristics, 10, 3, 357-380, (2004) · Zbl 1098.68644
[3] Coello Coello, C.A.; Van Veldhuizen, D.A.; Lamont, G.B., Evolutionary algorithms for solving multi-objective problems, (2002), Kluwer Academic Publishers Boston, MA, USA · Zbl 1130.90002
[4] Deb, K., Multi-objective optimization using evolutionary algorithms, (2001), John Wiley & Sons Chichester, UK · Zbl 0970.90091
[5] Deb, K., Agrawal, S., Pratab, A., Meyarivan, T., 2000. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In: Proceedings of the Sixth International Conference on Parallel Problem Solving from Nature (PPSN VI), Paris, France, pp. 849-858.
[6] Deb, K., Chaudhuri, S., Miettinen, K., 2006. Towards estimating nadir objective vector using evolutionary approaches. In: Proceedings of the Eighth Genetic and Evolutionary Computation Conference (GECCO 2006), Seattle, Washington, USA, pp. 643-650.
[7] Du, J.; Leung, J.Y.-T., Minimizing total tardiness on one machine is NP-hard, Mathematics of operations research, 15, 483-495, (1990) · Zbl 0714.90052
[8] Graham, R.L.; Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of discrete mathematics, 5, 287-326, (1979) · Zbl 0411.90044
[9] Hernández-Díaz, A.G.; Santana-Quintero, L.V.; Coello, C.A.C.; Molina, J., Pareto-adaptive epsilon-dominance, Evolutionary computation, 15, 4, 493-517, (2007)
[10] Ishibuchi, H.; Murata, T., A multi-objective genetic local search algorithm and its application to flowshop scheduling, IEEE transactions on systems, man and cybernetics, 28, 392-403, (1998)
[11] Johnson, S.M., Optimal two- and three-stage production schedules with setup times included, Naval research logistics quarterly, 1, 61-68, (1954) · Zbl 1349.90359
[12] Kim, Y.-D., Minimizing total tardiness in permutation flowshops, European journal of operational research, 33, 541-551, (1995) · Zbl 0912.90174
[13] Knowles, J., Thiele, L., Zitzler, E., 2006. A tutorial on the performance assessment of stochastic multiobjective optimizers. Tech. Rep., Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Switzerland (revised version).
[14] Landa Silva, J.D.; Burke, E.; Petrovic, S., An introduction to multiobjective metaheuristics for scheduling and timetabling, (), 91-129 · Zbl 1139.90420
[15] Lenstra, J.K.; Rinnooy Kan, A.H.G.; Brucker, P., Complexity of machine scheduling problems, Annals of discrete mathematics, 1, 343-362, (1977) · Zbl 0301.90025
[16] Liefooghe, A.; Basseur, M.; Jourdan, L.; Talbi, E.-G., Combinatorial optimization of stochastic multi-objective problems: an application to the flow-shop scheduling problem, (), 457-471
[17] Liefooghe, A., Jourdan, L., Talbi, E.-G., 2009. A unified model for evolutionary multiobjective optimization and its implementation in a general purpose software framework: ParadisEO-MOEO. Working Paper RR-6906, INRIA.
[18] Luque, M.; Miettinen, K.; Eskelinen, P.; Ruiz, F., Incorporating preference information in interactive reference point methods for multiobjective optmization, Omega-international journal of management science, 37, 2, 450-462, (2009)
[19] Melab, N.; Talbi, E.-G.; Cahon, S.; Alba, E.; Luque, G., Parallel metaheuristics: models and frameworks, (), 149-162, (Ch. 6)
[20] Miettinen, K., Nonlinear multiobjective optimization, vol. 12, (1999), Kluwer Academic Publishers Boston, MA, USA · Zbl 0949.90082
[21] Minella, G.; Ruiz, R.; Ciavotta, M., A review and evaluation of multi-objective algorithms for the flowshop scheduling problem, INFORMS journal on computing, 20, 3, 451-471, (2008) · Zbl 1243.90069
[22] Molina, J.; Santana, L.V.; Hernández-Díaz, A.G.; Coello Coello, C.A.; Caballero, R., G-dominance: reference point based dominance for multiobjective metaheuristics, European journal of operational research, 167, 2, 685-692, (2009) · Zbl 1159.90424
[23] Murata, T.; Ishibuchi, H.; Gen, M., Specification of genetic search directions in cellular multi-objective genetic algorithms, (), 82-95
[24] Nagar, A.; Haddock, J.; Heragu, S., Multiple and bicriteria scheduling: A literature survey, European journal of operational research, 81, 88-104, (1995) · Zbl 0913.90178
[25] Ruiz, F.; Luque, M.; Cabello, J.M., A classification of the weighting schemes in reference point procedures for multiobjective programming, Journal of operational research society, 60, 4, 544-553, (2009) · Zbl 1163.90739
[26] Steuer, R.E., Multiple criteria optimization: theory, computation, and application, (1986), John Wiley & Sons Chichester, UK · Zbl 0663.90085
[27] Szczepański, M.; Wierzbicki, A., Application of multiple criteria evolutionary algorithms to vector optimisation, decision support and reference point approaches, Journal of telecommunications and information technology, 3, 16-33, (2003)
[28] Taillard, E.D., Benchmarks for basic scheduling problems, European journal of operational research, 64, 278-285, (1993) · Zbl 0769.90052
[29] Thiele, L.; Miettinen, K.; Korhonen, P.J.; Molina, J., A preference-based evolutionary algorithm for multi-objective optimization, Evolutionary computation, 17, 3, 411-436, (2009)
[30] T’Kindt, V.; Billaut, J.-C., Multicriteria scheduling: theory, models and algorithms, (2002), Springer-Verlag Berlin, Germany · Zbl 1014.90046
[31] Wierzbicki, A., 1980. The use of reference objectives in multiobjective optimization. In: Fandel, G., Gal, T. (Eds.), Multiple Objective Decision Making, Theory and Application. Lecture Notes in Economics and Mathematical Systems, vol. 177. Springer-Verlag, pp. 468-486.
[32] ()
[33] Wilcoxon, F., Individual comparisons by ranking methods, Biometrics, 1, 80-83, (1945)
[34] Zhang, Q.; Li, H., MOEA/D: A multiobjective evolutionary algorithm based on decomposition, IEEE transactions on evolutionary computation, 11, 6, 712-731, (2007)
[35] Zitzler, E., Künzli, S., 2004. Indicator-based selection in multiobjective search. In: Proceedings of the Eighth International Conference on Parallel Problem Solving from Nature, Birmingham, UK (PPSN VIII). Lecture Notes in Computer Science, vol. 3242. Springer-Verlag, Berlin, Germany, pp. 832-842.
[36] Zitzler, E.; Thiele, L.; Laumanns, M.; Foneseca, C.M.; Grunert da Fonseca, V., Performance assessment of multiobjective optimizers: an analysis and review, IEEE transactions on evolutionary computation, 7, 2, 117-132, (2003)
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.