Abstract
The paper shows the importance of a multi-criteria performance analysis in evaluating the quality of non-dominated sets. The sets are generated by the use of evolutionary algorithms, more specifically through SPEA2 or NSGA-II. Problem examples from different problem domains are analyzed on four criteria of quality. These four criteria namely cardinality of the non-dominated set, spread of the solutions, hyper-volume, and set coverage do not favour any algorithm along the problem examples. In the Multiple Shortest Path Problem (MSPP) examples, the spread of solutions is the decisive factor for the 2S|1M configuration, and the cardinality and set coverage for the 3S configuration. The differences in set coverage values between SPEA2 and NSGA-II in the MSPP are small since both algorithms have almost identical non-dominated solutions. In the Decision Tree examples, the decisive factors are set coverage and hyper-volume. The computations show that the decisive criterion or criteria vary in all examples except for the set coverage criterion. This shows the importance of a binary measure in evaluating the quality of non-dominated sets, as the measure itself tests for dominance. The various criteria are confronted by means of a multi-criteria decision tool.
Chapter PDF
Similar content being viewed by others
References
Bosman, P.A., Thierens, D.: A balance between proximity and diversity in multiobjective evolutionary algorithms. IEEE Transactions on Evolutionary Computation 7(2), 174–188 (2003)
Brans, J.P., Vincke, P., Mareschal, B.: How to select and how to rank projects: the PROMETHEE method. European Journal of Operational Research 24, 228–238 (1986)
Brans, J.P., Mareschal, B.: The PROMCALC and GAIA Decision Support System for Multicriteria Decision Aid. Decision Support Systems 12, 297–310 (1994)
Cantu-Paz, E., Kamath, C.: Inducint oblique decision trees with evolutionary algorithms. IEEE Transactions on Evolutionary Computation 7(1), 54–68 (2003)
Carrizosa, E., Plastria, F.: On minquantile and maxcovering optimization. Mathematical Programming 71, 101–112 (1995)
Coello, C.: An updated survey of GA-based multiobjective optimization techniques. ACM Computing Surveys 32(2), 109–143 (2000)
Deb, K.: MultiObjective Optimization Using Evolutionary Algorithms. Wiley, Chichester (2001)
Deb, K., Agrawal, S., Pratap, A., Meyarivan, T.: A fast elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6(2), 182–197 (2002)
Ehrgott, M.: Multicriteria Optimization, 2nd edn. Springer, Berlin (2005)
Ehrgott, M., Gandibleux, X.: A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spectrum 22(4), 425–460 (2000)
Eiselt, H.A., Laporte, G., Thisse, J.-F.: Competitive location models: a framework and bibliography. Transportation Science 27, 44–54 (1993)
Murty, S.K., Kasif, S., Salzberg, S.: A system for induction of oblique decision trees. Journal of Artificial Intelligence Research 2(1), 1–32 (1994)
Schott, J.: Fault tolerant design using single and multicriteria genetic algorithm optimization. Master thesis. Massachusetts Institute of Technology, Cambridge (1995)
Van Veldhuizen, D.A.: Multiobjective Evolutionary Algorithms: Classifications, Analyses and New Innovations. Ph.D. thesis, Graduate School of Engineering of the Air Force Institute of Technology, Dayton, Ohio (1999)
Visual Decision: Decision Lab and Decision Lab 2000. Visual Decision Inc., Montreal (2003)
Zitzler, E.: Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. Ph.D. thesis, Shaker Verlag, Aachen (1999)
Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation 3(4), 257–271 (1999)
Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization. In: Giannakoglou, K., Tsahalis, D., Periaux, J., Papailou, K., Fogarty, T. (eds.) Evolutionary Methods for Design, Optimization and Control, pp. 19–26. CIMNE, Barcelona (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 IFIP
About this paper
Cite this paper
Janssens, G.K., Pangilinan, J.M. (2010). Multiple Criteria Performance Analysis of Non-dominated Sets Obtained by Multi-objective Evolutionary Algorithms for Optimisation. In: Papadopoulos, H., Andreou, A.S., Bramer, M. (eds) Artificial Intelligence Applications and Innovations. AIAI 2010. IFIP Advances in Information and Communication Technology, vol 339. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-16239-8_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-16239-8_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-16238-1
Online ISBN: 978-3-642-16239-8
eBook Packages: Computer ScienceComputer Science (R0)