×

zbMATH — the first resource for mathematics

Performance measures for dynamic multi-objective optimisation algorithms. (English) Zbl 1321.90119
Summary: When algorithms solve dynamic multi-objective optimisation problems (DMOOPs), performance measures are required to quantify the performance of the algorithm and to compare one algorithm’s performance against that of other algorithms. However, for dynamic multi-objective optimisation (DMOO) there are no standard performance measures. This article provides an overview of the performance measures that have been used so far. In addition, issues with performance measures that are currently being used in the DMOO literature are highlighted.

MSC:
90C29 Multi-objective and goal programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Avdagić, Z.; Konjicija, S.; Omanović, S., Evolutionary approach to solving non-stationary dynamic multi-objective problems, (Abraham, A.; Hassanien, A-E.; Siarry, P.; Engelbrecht, A., Foundations of Computational Intelligence, Studies in Computational Intelligence, vol. 203, (2009), Springer Berlin/Heidelberg), 267-289, (vol. 3)
[2] Ayvaz, D.; Gurgen, F., Performance evaluation of evolutionary heuristics in dynamic environments, Applied Intelligence, 37, 1, 130-144, (2012)
[3] C.R.B. Azevedo, A.F.R. Araujo, Generalized immigration schemes for dynamic evolutionary multiobjective optimization, in: Proceedings of Congress on Evolutionary Computation, June 2011, pp. 2033-2040.
[4] Besada-Portas, E.; de la Torre, L.; Moreno, A.; Risco-Martín, J. L., On the performance comparison of multi-objective evolutionary UAV path planners, Information Sciences, 238, 0, 111-125, (2013)
[5] Beume, N.; Rudolph, G., Faster s-metric calculation by considering dominated hypervolume as klee’s measure problem, (Proceedings of Computational Intelligence, (2007), IASTED/ACTA Press), 233-238
[6] Cámara, M.; Ortega, J.; de Toro, F., The parallel single front genetic algorithm (PSFGA) in dynamic multi-objective optimization, (Sandoval, F.; Prieto, A.; Cabestany, J.; Graña, M., Computational and Ambient Intelligence, Lecture Notes in Computer Science, vol. 4507, (2007), Springer Berlin/Heidelberg), 300-307
[7] Cámara, M.; Ortega, J.; de Toro, F., A single front genetic algorithm for parallel multi-objective optimization in dynamic environments, Neurocomputing, 72, 16-18, 3570-3579, (2009), Financial Engineering; Computational and Ambient Intelligence (IWANN 2007)
[8] Cámara, M.; Ortega, J.; de Toro, F., Approaching dynamic multi-objective optimization problems by using parallel evolutionary algorithms, (Coello Coello, C.; Dhaenens, C.; Jourdan, L., Advances in Multi-Objective Nature Inspired Computing, Studies in Computational Intelligence, vol. 272, (2010), Springer Berlin/Heidelberg), 63-86 · Zbl 1187.90248
[9] M. Cámara, J. Ortega, F.J. de Toro, Parallel processing for multi-objective optimization in dynamic environments, in: International Parallel and Distributed Processing Symposium, vol. 0, 2007, pp. 243-250.
[10] H. Chen, M. Li, X. Chen, Using diversity as an additional-objective in dynamic multi-objective optimization algorithms, Electronic Commerce and Security, in: International Symposium vol. 1, 2009, pp. 484-487.
[11] Cheng, S.; Shi, Y.; Qin, Q., On the performance metrics of multiobjective optimization, (Tan, Ying; Shi, Yuhui; Ji, Zhen, Advances in Swarm Intelligence, Lecture Notes in Computer Science, vol. 7331, (2012), Springer Berlin Heidelberg), 504-512
[12] Civicioglu, Pinar, Artificial cooperative search algorithm for numerical optimization problems, Information Sciences, 229, 0, 58-76, (2013) · Zbl 1288.65092
[13] Deb, K., Multi-objective optimization using evolutionary algorithms, (2004), John Wiley & Sons, Ltd.
[14] K. Deb, Single and multi-objective dynamic optimization: two tales from an evolutionary perspective, Tech. Report 2011004, Kalyanmoy Deb Kanpur Genetic Algorithms Laboratory, KanGAL, February 2011.
[15] K. Deb, S. Agarwal, A. Pratap, T. Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-II, Tech. Report 200001, Kanpur, India, 2000.
[16] Deb, K.; Anand, A.; Joshi, D., A computationally efficient evolutionary algorithm for real-parameter optimization, Evolutionary Computation, 10, 4, 371-395, (2002)
[17] K. Deb, N. Rao, S. Karthik, Dynamic multi-objective optimization and decision-making using modied NSGA-II: a case study on hydro-thermal power scheduling, in: Proceedings of International Conference on Evolutionary Multi-criterion optimization, Matsushima, Japan, 2007, pp. 803-817.
[18] Engelbrecht, A. P., Fundamentals of computational swarm intelligence, (2005), John Wiley and Sons, Ltd.
[19] A.P. Engelbrecht, Particle swarm optimization: velocity initialization, in: Proceedings of the World Congress on Computational Intelligence: Congress on Evolutionary Computation, Brisbane, June 2012, pp. 1-8.
[20] Farina, M.; Deb, K.; Amato, P., Dynamic multiobjective optimization problems: test cases, approximations, and applications, IEEE Transactions on Evolutionary Computation, 8, 5, 425-442, (2004)
[21] L.J. Fogel, On the Organization of Intellect, Ph.D. thesis, University of California, 1964.
[22] C.M. Fonseca, L. Paquete, M. Lopez-Ibanez, An improved dimension-sweep algorithm for the hypervolume indicator, in: Proceedings of Congress on Evolutionary Computation, July 2006, pp. 1157-1163.
[23] F.v.d. Bergh, An analysis of particle swarm optimizers, Ph.D. thesis, Department of Computer Science University of Pretoria, 2002.
[24] Goh, C-K.; Tan, K., A coevolutionary paradigm for dynamic multi-objective optimization, (Evolutionary Multi-objective Optimization in Uncertain Environments, Studies in Computational Intelligence, vol. 186, (2009), Springer Berlin/Heidelberg), 153-185
[25] Goh, C-K.; Tan, K. C., A competitive-cooperative coevolutionary paradigm for dynamic multiobjective optimization, IEEE Transactions on Evolutionary Computation, 13, 1, 103-127, (2009)
[26] Greeff, M.; Engelbrecht, A., Dynamic multi-objective optimisation using PSO, (Nedjah, Nadia; Coelho, Leandro dos Santos; Mourelle, Luiza de Macedo, Multi-Objective Swarm Intelligent Systems, Studies in Computational Intelligence, vol. 261, (2010), Springer Berlin/Heidelberg), 105-123
[27] M. Greeff, A.P. Engelbrecht, Solving dynamic multi-objective problems with vector evaluated particle swarm optimisation, in: Proceedings of World Congress on Computational Intelligence (WCCI): Congress on Evoluationary Computation, Hong Kong, June 2008, pp. 2917-2924.
[28] Guan, S-U.; Chen, Q.; Mo, W., Evolving dynamic multi-objective optimization problems with objective replacement, Artificial Intelligence Review, 23, 267-293, (2005)
[29] M.P. Hansen, A. Jaszkiewicz, Evaluating the quality of approximations to the non-dominated set, Tech. Report IMM-REP-1998-7, Technical University of Denmark, 22 March 1998.
[30] Hatzakis, I.; Wallace, D., Dynamic multi-objective optimization with evolutionary algorithms: a forward-looking approach, (Proceedings of the Conference on Genetic and Evolutionary Computation, (2006), ACM New York, NY, USA), 1201-1208
[31] M. Helbig, A.P. Engelbrecht, Archive management for dynamic multi-objective optimisation problems using vector evaluated particle swarm optimisation, in: Proceedings of Congress on Evolutionary Computation, New Orleans, USA, June 2011, pp. 2047-2054.
[32] M. Helbig, A.P. Engelbrecht, Dynamic multi-objective optimisation problems, Tech. report, University of Pretoria, Pretoria, South Africa, 2013. · Zbl 1321.90119
[33] M. Helbig, A.P. Engelbrecht, Issues with performance measures for dynamic multi-objective optimisation, Proceedings of IEEE Symposium Series on Computational Intelligence, Singapore, April 2013, pp. 17-24. · Zbl 1321.90119
[34] M. Helbig, A.P. Engelbrecht, Metaheuristics for dynamic optimization, Studies in Computational Intelligence, ch. Dynamic multi-objective optimization using PSO, Springer Verlag Berlin/Heidelberg, 2013, pp. 147-188. <http://link.springer.com/chapter/10.1007/978-3-642-30665-5_8> (last accessed 05.12.12).
[35] Holland, J. H., Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence., (1975), University of Michigan Press Oxford, UK · Zbl 0317.68006
[36] A. Isaacs, V. Puttige, T. Ray, W. Smith, S. Anavatti, Development of a memetic algorithm for dynamic multi-objective optimization and its applications for online neural network modeling of uavs, in: Proceedings of World Congress on Computational Intelligence: International Joint Conference on Neural Networks, June 2008, pp. 548-554.
[37] A. Isaacs, T. Ray, W. Smith, Memetic algorithm for dynamic bi-objective optimization problems, in: Proceedings of Congress on Evolutionary Computation, Trondheim, Norway, May 2009, pp. 1707-1713.
[38] J. Kennedy, R.C. Eberhart, Particle swarm optimization, in: Proceedings of International Conference on Neural Networks, vol. IV, 1995, pp. 1942-1948.
[39] A.K.M. Khaled, A. Talukder, M. Kirley, A Pareto following variation operator for fast-converging multiobjective evolutionary algorithms, in: Proceedings of World Congress on Computational Intelligence: Congress on Evolutionary Computation, June 2008, pp. 2270-2277.
[40] K. Kim, R.I. McKay, B-R. Moon, Multiobjective evolutionary algorithms for dynamic social network clustering, in: Proceedings of the Conference on Genetic and Evolutionary Computation, 2010.
[41] J.D. Knowles, Local-search and hybrid evolutionary algorithms for Pareto optimisation, Ph.D. thesis, Department of Computer Science The University of Reading, 2002.
[42] Koo, W.; Goh, C.; Tan, K., A predictive gradient strategy for multiobjective evolutionary algorithms in a fast changing environment, Memetic Computing, 2, 2, 87-110, (2010)
[43] M.S. Lechuga, Multi-objective optimisation using sharing in swarm optimisation algorithms, Ph.D. thesis, University of Birmingham, July 2009.
[44] Leung, Y-W.; Wang, Y., U-measure: a quality measure for multiobjective programming, IEEE Transactions on Systems, Man, and Cybernetics, 33, 3, 337-343, (2003)
[45] Li, K.; Kwong, S.; Cao, J.; Li, M.; Zheng, J.; Shen, R., Achieving balance between proximity and diversity in multi-objective evolutionary algorithm, Information Sciences, 182, 1, 220-242, (2012), Nature-Inspired Collective Intelligence in Theory and Practice
[46] X. Li, J. Branke, M. Kirley, On performance metrics and particle swarm methods for dynamic multiobjective optimization problems, in: Proceedings of Congress on Evolutionary Computation, September 2007, pp. 576-583.
[47] Liu, C-A., New dynamic multiobjective evolutionary algorithm with core estimation of distribution, International Conference on Electrical and Control Engineering, 0, 1345-1348, (2010)
[48] G. Lizárraga Lizárraga, On the evaluation of the quality of non-dominated sets, Ph.D. thesis, Centro de Investigación en Matemáticas, A.C. (CIMAT), April 2009.
[49] J. Mehnen, G. Rudolph, T. Wagner, Evolutionary optimization of dynamic multiobjective functions, Tech. Report CI-204/06, Universität Dortmund, Universität Dortmund, Fachbereich Informatik/XI, 44221, Dortmund, Germany, May 2006.
[50] Nakib, A.; Siarry, P., Performance analysis of dynamic optimization algorithms, (Alba, Enrique; Nakib, Amir; Siarry, Patrick, Metaheuristics for Dynamic Optimization, Studies in Computational Intelligence, vol. 433, (2013), Springer Berlin Heidelberg), 1-16
[51] Ray, T.; Isaacs, A.; Smith, W., A memetic algorithm for dynamic multiobjective optimization, (Goh, C-K.; Ong, Y-S.; Tan, K., Multi-Objective memetic algorithms, Studies in Computational Intelligence, vol. 171, (2009), Springer Berlin/Heidelberg), 353-367 · Zbl 1160.90684
[52] Rosenthal, R. E., Principles of multiobjective optimization, Decision Sciences, 16, 132-152, (1985)
[53] Sarasola, B.; Alba, E., Quantitative performance measures for dynamic optimization problems, (Alba, Enrique; Nakib, Amir; Siarry, Patrick, Metaheuristics for Dynamic Optimization, Studies in Computational Intelligence, vol. 433, (2013), Springer Berlin Heidelberg), 17-33
[54] J.R. Schott, Fault tolerance design using single and multi-criteria genetic algorithms, Master’s thesis, Department of Aeronautics and Astronautics Massachusetts Institute of Technology, 1995.
[55] Schuhmacher, D.; Vo, B-T.; Vo, B-N., A consistent metric for performance evaluation of multi-object filters, IEEE Transactions on Signal Processing, 56, 8, 3447-3457, (2008) · Zbl 1390.94399
[56] Sierra, M.; Coello Coello, C., Improving PSO-based multi-objective optimization using crowding, mutation and -dominance, (Coello, Carlos Coello; Aguirre, Arturo Hernndez; Zitzler, Eckart, Evolutionary multi-criterion optimization, Lecture Notes in Computer Science, vol. 3410, (2005), Springer Berlin Heidelberg), 505-519 · Zbl 1109.68631
[57] M. Cámara Sola, Parallel processing for dynamic multi-objective optimization, Ph.D. thesis, Universidad de Granada, Dept. of Computer Architecture and Computer Technology, Universidad de Granada, Spain, April 2010.
[58] Storn, R.; Price, K., Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces, Journal of Global Optimization, 11, 4, 341-359, (1997) · Zbl 0888.90135
[59] A.K.M. Talukder, A. Khaled, Towards high speed multiobjective evolutionary optimizers, in: Proceedings of the Genetic and Evolutionary Computation Conference, New York, NY, USA, ACM, 2008, pp. 1791-1794.
[60] Tan, K.; Goh, C., Handling uncertainties in evolutionary multi-objective optimization, (Zurada, Jacek; Yen, Gary; Wang, Jun, Computational Intelligence: Research Frontiers, Lecture Notes in Computer Science, vol. 5050, (2008), Springer Berlin/Heidelberg), 262-292
[61] E. Tantar, A-A. Tantar, P. Bouvry, On dynamic multi-objective optimization, classification and performance measures, in: Proceedings of Congress on Evolutionary Computation, June 2011, pp. 2759-2766.
[62] D.A. van Veldhuizen, Multiobjective evolutionary algorithms: classification, analyses, and new innovations, Ph.D. thesis, Graduate School of Engineering Air University, 1999.
[63] Wang, Y.; Dang, C., An evolutionary algorithm for dynamic multi-objective optimization, Applied Mathematics and Computation, 25, 6-18, (2008) · Zbl 1157.65393
[64] Y. Wang, B. Li, Investigation of memory-based multi-objective optimization evolutionary algorithm in dynamic environment, in: Proceedings of Congress on Evolutionary Computation, Trondheim, Norway, May 2009, pp. 630-637.
[65] Wang, Y.; Li, B., Multi-strategy ensemble evolutionary algorithm for dynamic multi-objective optimization, Memetic Computing, 2, 1, 3-24, (2010)
[66] Weicker, K., Performance measures for dynamic environments, (Guervós, J.; Adamidis, P.; Beyer, H-G.; Schwefel, H-P.; Fernández-Villacañas, J-L., Parallel Problem Solving from Nature, Lecture Notes in Computer Science, vol. 2439, (2002), Springer Berlin/Heidelberg), 64-73
[67] S-Y. Zeng, G. Chen, L. Zheng, H. Shi, H. de Garis, L. Ding, L. Kang, A dynamic multi-objective evolutionary algorithm based on an orthogonal design, in: Proceedings of Congress on Evolutionary Computation, Vancouver, Canada, 16-21 July 2006, pp. 573-580.
[68] Zhang, Z.; Qian, S., Artificial immune system in dynamic environments solving time-varying non-linear constrained multi-objective problems, Soft Computing - A Fusion of Foundations, Methodologies and Applications, 15, 1333-1349, (2011)
[69] B. Zheng, A new dynamic multi-objective optimization evolutionary algorithm, in: Proceedings of Third International Conference on Natural Computation, vol. 5, August 2007, pp. 565-570.
[70] Zhou, A.; Jin, Y.; Zhang, Q.; Sendhoff, B., Prediction-based population re-initialization for evolutionary dynamic multi-objective optimization, (Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science, vol. 4403, (2007), Springer Berlin/Heidelberg), 832-846
[71] E. Zitzler, Evolutionary Algorithms for multiobjective optimization: methods and applications, Ph.D. thesis, Swiss Federal Institute of Technology (ETH) Zurich Switzerland, 1999.
[72] Zitzler, E.; Brockhoff, D.; Thiele, L., The hypervolume indicator revisited: on the design of Pareto-compliant indicators via weighted integration, (Obayashi, S.; Deb, K.; Poloni, C.; Hiroyasu, T.; Murata, T., Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science, vol. 4403, (2007), Springer Berlin/Heidelberg), 862-876
[73] Zitzler, E.; Deb, K.; Thiele, L., Comparison of multiobjective evolutionary algorithms: empirical results, Evolutionary Computation, 8, 2, 173-195, (2000)
[74] E. Zitzler, L. Thiele, Multiobjective optimization using evolutionary algorithms a comparative case study 1498 (1998) 292-301.
[75] Zitzler, E.; Thiele, L., Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach, IEEE Transactions on Evolutionary Computation, 3, 4, 257-271, (1999)
[76] Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, 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.