ORIGINAL ARTICLE
Handling multiple objectives using k-means clustering guided multiobjective evolutionary algorithm
Tribhuvan Singh,
Corresponding Author
Tribhuvan Singh
Department of Computer Science and Engineering, Siksha ‘O’ Anusandhan (Deemed to be University), Bhubaneswar, Odisha, India
Correspondence
Tribhuvan Singh, Department of Computer Science and Engineering, Siksha ‘O’ Anusandhan (Deemed to be University), Bhubaneswar, Odisha, India.
Email: [email protected]
Search for more papers by this authorTribhuvan Singh,
Corresponding Author
Tribhuvan Singh
Department of Computer Science and Engineering, Siksha ‘O’ Anusandhan (Deemed to be University), Bhubaneswar, Odisha, India
Correspondence
Tribhuvan Singh, Department of Computer Science and Engineering, Siksha ‘O’ Anusandhan (Deemed to be University), Bhubaneswar, Odisha, India.
Email: [email protected]
Search for more papers by this authorAbstract
Multiobjective optimization problems (MOPs) are very popular these days and have gained continuous research attention. These problems involve a minimum of two conflicting objectives that need to be optimized simultaneously. Multiobjective evolutionary algorithms (MOEAs) optimize these objectives by targeting solutions on the Pareto front. To judge the performance of different MOEAs, the convergence rate and population diversity are used. In order to create a good algorithm with a high convergence rate and diversity, the k-means clustering algorithm is combined with a real parameter version of the improved environmental adaptation method (IEAM-RP) in this paper. This is done as IEAM-RP converges very fast and the k-means clustering algorithm is used to provide diversity in decision search space. To check the performance of the proposed algorithm, it has been compared with nine state-of-the-art multiobjective algorithms (MOPSOtridist, MOEA/D-STM, MOEA/D, MOPSO, NSGA-II, MOPSOses, MOGOA, MODA, MOALO) using standard multiobjective benchmark functions. Further, the performance of the proposed algorithm is compared against IBEA and SMS-EMOA using walking fish group (WFG) test suit. The experimental results prove the effectiveness of the proposed algorithm.
Open Research
DATA AVAILABILITY STATEMENT
The data that support the findings of this study are available on request from the corresponding author. The data are not publicly available due to privacy or ethical restrictions.
REFERENCES
- Afshari, H., Hare, W., & Tesfamariam, S. (2019). Constrained multi-objective optimization algorithms: Review and comparison with application in reinforced concrete structures. Applied Soft Computing, 83, 105631.
- Amelian, S. S., Sajadi, S. M., Navabakhsh, M., & Esmaelian, M. (2019). Multi-objective optimization for stochastic failure-prone job shop scheduling problem via hybrid of nsga-ii and simulation method. Expert Systems, XX, e12455.
- Beume, N., Naujoks, B., & Emmerich, M. (2007). Sms-emoa: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research, 181(3), 1653–1669.
- Bo-Yang, Q., & Ponnuthurai, N. (2009). Suganthan. Multi-objective evolutionary programming without non-domination sorting is up to twenty times faster. In Evolutionary computation, 2009. CEC'09. IEEE congress (pp. 2934–2939). IEEE.
- Chen, G., & Li, J. (2019). A diversity ranking based evolutionary algorithm for multi-objective and many-objective optimization. Swarm and Evolutionary Computation, 48, 274–287.
- Chow, C. K., & Yuen, S. Y. (2012). A multiobjective evolutionary algorithm that diversifies population by its density. IEEE Transactions on Evolutionary Computation, 16(2), 149–172.
- Coello, C. A., Coello, D. A., Veldhuizen, V., & Lamont, G. B. (2002). Evolutionary algorithms for solving multi-objective problems (Vol. 242). Springer.
10.1007/978-1-4757-5184-0 Google Scholar
- Coello Coello, C. A., Pulido, G. T., & Lechuga, M. S. (2004). Handling multiple objectives with particle swarm optimization. IEEE Transactions on Evolutionary Computation, 8(3), 256–279.
- Črepinšek, M., Liu, S.-H., & Mernik, M. (2014). Replication and comparison of computational experiments in applied evolutionary computing: Common pitfalls and guidelines to avoid them. Applied Soft Computing, 19, 161–170.
- Deb, K. (1999). Multi-objective genetic algorithms: Problem difficulties and construction of test problems. Evolutionary Computation, 7(3), 205–230.
- Deb, K. (2001). Multi-objective optimization using evolutionary algorithms (Vol. 16). John Wiley & Sons.
- Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. A. M. T. (2002). A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE Transactions on Evolutionary Computation, 6(2), 182–197.
- Deb, K., Thiele, L., Laumanns, M., & Zitzler, E. (2002). Scalable multi-objective optimization test problems. In Evolutionary computation, 2002. CEC'02. Proceedings of the 2002 congress, volume 1 (pp. 825–830). IEEE.
10.1109/CEC.2002.1007032 Google Scholar
- El Aziz, M. A., Ewees, A. A., Hassanien, A. E., Mudhsh, M., & Xiong, S. (2018). Multi-objective whale optimization algorithm for multilevel thresholding segmentation. In Advances in soft computing and machine learning in image processing (pp. 23–39). Springer.
10.1007/978-3-319-63754-9_2 Google Scholar
- Evan James Hughes (2011). Many-objective directed evolutionary line search. In Proceedings of the 13th annual conference on genetic and evolutionary computation (pp. 761–768). ACM.
10.1145/2001576.2001680 Google Scholar
- Falcón-Cardona, J. G., & Coello Coello, C. A. (2020). Indicator-based multi-objective evolutionary algorithms: A comprehensive survey. ACM Computing Surveys (CSUR), 53(2), 1–35.
- Fonseca, C. M., & Fleming, P. J. (1998). Multiobjective optimization and multiple constraint handling with evolutionary algorithms. II. Application example. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 28(1), 38–47.
- Song Gao, Bo Xiao, Lei Zhang, Yulong Shi, Xin Tian, Yang Yang, Haoqiu Long, Xianqiang Yang, Danping Yu, Zu Yan, An orthogonal multi-objective evolutionary algorithm with lower-dimensional crossover. In Evolutionary computation, 2009. CEC'09. IEEE congress, pages 1959–1964. IEEE, 2009.
- Goh, C.-K., Ong, Y.-S., & Tan, K. C. (2008). Multi-objective memetic algorithms (Vol. 171). Springer.
- Gong, D., Han, Y., & Sun, J. (2018). A novel hybrid multi-objective artificial bee colony algorithm for blocking lot-streaming flow shop scheduling problems. Knowledge-Based Systems, 148, 115–130.
- Holm, S. (1979). A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics, 6, 65–70.
- Horn, J., Nafpliotis, N., & Goldberg, D. E. (1994). A niched pareto genetic algorithm for multiobjective optimization. In Evolutionary computation, 1994. IEEE world congress on computational intelligence., Proceedings of the first IEEE conference (pp. 82–87). IEEE.
10.1109/ICEC.1994.350037 Google Scholar
- Hu, K., Jiang, H., Ji, C.-G., & Pan, Z. (2021). A modified butterfly optimization algorithm: An adaptive algorithm for global optimization and the support vector machine. Expert Systems, 38, e12642.
- Hughes, E. J. (2007). Msops-ii: A general-purpose many-objective optimiser. In Evolutionary computation, 2007. CEC 2007. IEEE congress (pp. 3944–3951). IEEE.
10.1109/CEC.2007.4424985 Google Scholar
- Inman, R. L., & Davenpot, J. M. (1980). Approximations of the critical region of the friedman statistic. Communications in Statistics, Theory and Methods A, 9, 571–595.
- Ishibuchi, H., Masuda, H., & Nojima, Y. (2015). A study on performance evaluation ability of a modified inverted generational distance indicator. In Proceedings of the 2015 annual conference on genetic and evolutionary computation (pp. 695–702). ACM Digital Library.
10.1145/2739480.2754792 Google Scholar
- Ishibuchi, H., & Murata, T. (1996). Multi-objective genetic local search algorithm. In Proceedings of IEEE international conference on evolutionary computation (pp. 119–124). IEEE.
10.1109/ICEC.1996.542345 Google Scholar
- Ismayilov, G., & Topcuoglu, H. R. (2020). Neural network based multi-objective evolutionary algorithm for dynamic workflow scheduling in cloud computing. Future Generation Computer Systems, 102, 307–322.
- Jiang, S., Zhang, J., Ong, Y.-S., Zhang, A. N., & Tan, P. S. (2014). A simple and fast hypervolume indicator-based multiobjective evolutionary algorithm. IEEE Transactions on Cybernetics, 45(10), 2202–2213.
- Karahan, İ., & Koksalan, M. (2010). A territory defining multiobjective evolutionary algorithms and preference incorporation. IEEE Transactions on Evolutionary Computation, 14(4), 636–664.
- Knowles, J., & Corne, D. (1999). The pareto archived evolution strategy: A new baseline algorithm for pareto multiobjective optimisation. In Evolutionary computation, 1999. CEC 99. Proceedings of the 1999 congress, volume 1. IEEE.
10.1109/CEC.1999.781913 Google Scholar
- Kursawe, F. (1990). A variant of evolution strategies for vector optimization. In International conference on parallel problem solving from nature (pp. 193–197). Springer.
- Leong, W.-F., & Yen, G. G. (2008). Pso-based multiobjective optimization with dynamic population size and adaptive local archives. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 38(5), 1270–1293.
- Leung, M.-F., Ng, S.-C., Cheung, C.-C., & Lui, A. K. (2015). A new algorithm based on pso for multi-objective optimization. In Evolutionary computation (CEC), 2015 IEEE congress (pp. 3156–3162). IEEE.
10.1109/CEC.2015.7257283 Google Scholar
- Li, K., Zhang, Q., Kwong, S., Li, M., & Wang, R. (2014). Stable matching-based selection in evolutionary multiobjective optimization. IEEE Transactions on Evolutionary Computation, 18(6), 909–923.
- Liu, H.-L., Fangqing, G., & Zhang, Q. (2014). Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems. IEEE Transactions on Evolutionary Computation, 18(3), 450–455.
- Liu, Y., Yen, G. G., & Gong, D. (2018). A multimodal multiobjective evolutionary algorithm using two-archive and recombination strategies. IEEE Transactions on Evolutionary Computation, 23(4), 660–674.
- Mengqi, H., Teresa, W., & Weir, J. D. (2012). An intelligent augmentation of particle swarm optimization with multiple adaptive methods. Information Sciences, 213, 68–83.
- Mirjalili, S. (2016). Dragonfly algorithm: A new meta-heuristic optimization technique for solving single-objective, discrete, and multi-objective problems. Neural Computing and Applications, 27(4), 1053–1073.
- Mirjalili, S., Jangir, P., Mirjalili, S. Z., Saremi, S., & Trivedi, I. N. (2017). Optimization of problems with multiple objectives using the multi-verse optimization algorithm. Knowledge-Based Systems, 134, 50–71.
- Mirjalili, S., Jangir, P., & Saremi, S. (2017). Multi-objective ant lion optimizer: A multi-objective optimization algorithm for solving engineering problems. Applied Intelligence, 46(1), 79–95.
- Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey wolf optimizer. Advances in Engineering Software, 69, 46–61.
- Mirjalili, S., Saremi, S., Mirjalili, S. M., & Coelho., L. d. S. (2016). Multi-objective grey wolf optimizer: A novel algorithm for multi-criterion optimization. Expert Systems with Applications, 47, 106–119.
- Mirjalili, S. Z., Mirjalili, S., Saremi, S., Faris, H., & Aljarah, I. (2018). Grasshopper optimization algorithm for multi-objective optimization problems. Applied Intelligence, 48(4), 805–820.
- Pan, I., & Das, S. (2015). Fractional-order load-frequency control of interconnected power systems using chaotic multi-objective optimization. Applied Soft Computing, 29, 328–344.
- Qi, Y., Ma, X., Liu, F., Jiao, L., Sun, J., & Jianshe, W. (2014). Moea/d with adaptive weight adjustment. Evolutionary Computation, 22(2), 231–264.
- Qian, X., Zhanqi, X., & Ma, T. (2020). A survey of multiobjective evolutionary algorithms based on decomposition: Variants, challenges and future directions. IEEE Access, 8, 41588–41614.
- Savsani, V., & Tawhid, M. A. (2017). Non-dominated sorting moth flame optimization (ns-mfo) for multi-objective problems. Engineering Applications of Artificial Intelligence, 63, 20–32.
- Saxena, N., & Mishra, K. K. (2017). Improved multi-objective particle swarm optimization algorithm for optimizing watermark strength in color image watermarking. Applied Intelligence, 47, 362–381.
- Schaffer, J. D. (1985). Multiple objective optimization with vector evaluated genetic algorithms. In Proceedings of the 1st international conference on genetic algorithms (pp. 93–100). L. Erlbaum Associates Inc.
- Jason R Schott. Fault tolerant design using single and multicriteria genetic algorithm optimization. Technical report, DTIC Document, 1995.
- Sheskin, D. J. (2003). Handbook of parametric and nonparametric statistical procedures. Chapman and Hall/CRC.
10.1201/9781420036268 Google Scholar
- Singh, T. (2020). A chaotic sequence-guided Harris hawks optimizer for data clustering. Neural Computing and Applications, 32, 17789–17803.
- Singh, T. (2021). A novel data clustering approach based on whale optimization algorithm. Expert Systems, 38(3), e12657.
- Singh, T., Mishra, K. K., & Vijay, R. (2019). Data clustering using environmental adaptation method. In International conference on hybrid intelligent systems (pp. 156–164). Springer.
- Singh, T., & Saxena, N. (2021). Chaotic sequence and opposition learning guided approach for data clustering. Pattern Analysis and Applications, 24, 1–15.
- Singh, T., Shukla, A., & Mishra, K. K. (2018). Improved environmental adaption method with real parameter encoding for solving optimization problems. In Advances in computer and computational sciences (pp. 13–20). Springer.
10.1007/978-981-10-3773-3_2 Google Scholar
- Sun, Y., Yen, G. G., & Yi, Z. (2018). Igd indicator-based evolutionary algorithm for many-objective optimization problems. IEEE Transactions on Evolutionary Computation, 23(2), 173–187.
- Tawhid, M. A., & Savsani, V. (2019). Multi-objective sine-cosine algorithm (mo-sca) for multi-objective engineering design problems. Neural Computing and Applications, 31(2), 915–929.
- Wang, J., Yuchao, S., Lin, Q., Ma, L., Gong, D., Li, J., & Ming, Z. (2020). A survey of decomposition approaches in multiobjective evolutionary algorithms. Neurocomputing, 408, 308–330.
- Wang, J., Ren, W., Zhang, Z., Huang, H., & Zhou, Y. (2018). A hybrid multiobjective memetic algorithm for multiobjective periodic vehicle routing problem with time windows. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 99, 1–14.
- Wang, J., Yang, W., Pei, D., & Niu, T. (2018). A novel hybrid forecasting system of wind speed based on a newly developed multi-objective sine cosine algorithm. Energy Conversion and Management, 163, 134–150.
- Wang, Y., Dang, C., Li, H., Han, L., & Wei, J. (2009). A clustering multi-objective evolutionary algorithm based on orthogonal and uniform design. In Evolutionary computation, 2009. CEC'09. IEEE congress (pp. 2927–2933). IEEE.
10.1109/CEC.2009.4983311 Google Scholar
- Wang, Z., Zhang, Q., Gong, M., & Zhou, A. (2014). A replacement strategy for balancing convergence and diversity in moea/d. In 2014 IEEE congress on evolutionary computation (CEC) (pp. 2132–2139). IEEE.
10.1109/CEC.2014.6900319 Google Scholar
- Yen, G. G., & Leong, W. F. (2009). Dynamic multiple swarms in multiobjective particle swarm optimization. IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 39(4), 890–911.
10.1109/TSMCA.2009.2013915 Google Scholar
- Zapotecas-Martnez, S., López-Jaimes, A., & Garca-Nájera, A. (2019). Libea: A lebesgue indicator-based evolutionary algorithm for multi-objective optimization. Swarm and Evolutionary Computation, 44, 404–419.
- Zhan, Z.-H., Zhang, J., Li, Y., & Chung, H. S.-H. (2009). Adaptive particle swarm optimization. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 39(6), 1362–1381.
- Zhang, Q., & Li, H. (2007). MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 11(6), 712–731.
- Qingfu Zhang, Aimin Zhou, Shizheng Zhao, Ponnuthurai Nagaratnam Suganthan, Wudong Liu, and Santosh Tiwari. Multiobjective optimization test instances for the cec 2009 special session and competition. University of Essex, Colchester, UK and Nanyang technological University, Singapore, special session on performance assessment of multi-objective optimization algorithms, Technical Report, 264, 2008.
- Zhou, Y., Chen, Z., Huang, Z., & Xiang, Y. (2020). A multiobjective evolutionary algorithm based on objective-space localization selection. IEEE Transactions on Cybernetics, 1–14.
- Zitzler, E., Deb, K., & Thiele, L. (2000). Comparison of multiobjective evolutionary algorithms: Empirical results. Evolutionary Computation, 8(2), 173–195.
