Çok Amaçlı Dağınık Arama Algoritmasının Zdt-Dtlz Test Problemleri Üzerinde Uygulanması

Year 2024, , 1150 - 1164, 01.10.2024

Zeynep Haber , Harun Uğuz

https://doi.org/10.35414/akufemubid.1411831

Abstract

Dağınık arama algoritması, tek amaçlı optimizasyon problemlerinin çözümünde sıkça kullanılan bir yöntemdir. Ancak, çok amaçlı problemlerle başa çıkmak oldukça zorlu bir süreçtir. Bu makale, çok amaçlı optimizasyon problemleriyle başa çıkabilmek için "Dağınık Arama Algoritması" (DA) olarak adlandırılan yöntemin genişletilmesine yönelik bir öneri sunmaktadır. Önerilen yaklaşım, DA algoritmasına çok amaçlı optimizasyon algoritması olan Baskın Olmayan Sıralama Genetik Algoritması II (NSGA-II) yöntemindeki Yoğunluk Mesafesi (CD) ve Hızlı Bastırılmamış Sıralama kavramlarını ekleyerek hibrit çok amaçlı optimizasyon algoritması önermektedir. Bu önerilen algoritma, ZDT ve DTLZ test problemleri kullanılarak değerlendirilmiştir. Yapılan deneysel sonuçlar, önerilen Çok Amaçlı Dağınık Arama(ÇADA) algoritmasının 19 farklı çok amaçlı optimizasyon yöntemi ile karşılaştırıldığında, ZDT problemi için 2.40 IGD ortalama ile birinci sırada, DTLZ probleminde ise 0.0035 IGD ortalama değeri ile altıncı sırada yer aldığını göstermektedir. Bu sonuçlar, önerilen algoritmanın karşılaştırılabilir düzeyde başarılı bir performansa sahip olduğunu ortaya koymaktadır.

Keywords

Çok Amaçlı Optimizasyon Algoritması, Dağınık Arama Algoritması, NSGA-II algoritması, ZDT-DTLZ problemleri

Applıcatıon Of Multı-Objective Scatter Search Algorıthm On Zdt-Dtlz Test Problems

Abstract

The Scatter Search algorithm is a frequently used method in solving single-objective optimization problems. However, dealing with multi-objective problems is a highly challenging process. This article proposes an extension of the method referred to as "Scatter Search Algorithm" (SSA) to tackle multi-objective optimization problems. The suggested approach aims to augment the SSA algorithm by incorporating concepts from the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) method, specifically Density Distance (CD), and Fast Non-Dominated Sorting. This proposed algorithm has been evaluated using ZDT and DTLZ test problems. Experimental results show that the proposed Multi-Objective Scatter Search (ÇADA) algorithm ranks first with an average IGD of 2.40 for the ZDT problem and sixth with an average IGD value of 0.0035 for the DTLZ problem when compared to 19 different multi-objective optimization methods. These results demonstrate that the proposed algorithm exhibits a comparable level of successful performance.

Keywords

Multi-Objective Optimization Algorithm, Scattered Search Algorithm, NSGA-II algorithm, ZDT-DTLZ problems

References

• Abed-Alguni, B. H. ve Paul, D. J., 2020, Hybridizing the cuckoo search algorithm with different mutation operators for numerical optimization problems, Journal of Intelligent Systems, 29 (1), 1043-1062. https://doi.org/10.1515/jisys-2018-0331
• Azizi, S., SoltanAghaei, M., Ghaffarian, H. ve Javadpour, A., 2023, Improving Hierarchical Traffic Engineering and Reducing the Congestion with PSO in SDN and DataCenter Networks, Research Square, Preprint, Version1, https://doi.org/10.21203/rs.3.rs-1887790/v1
• Bilici, Z. ve Özdemir, D., 2023, Meteorolojik parametreler ile doğal gaz talep tahmini için metasezgisel optimizasyon algoritmalarının karşılaştırmalı analizi, Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 38 (2), 1153-1168. https://doi.org/10.17341/gazimmfd.1014788
• Chen, H., Feng, Z., Liu, Y., Chen, B., Deng, T., Qin, Y. ve Xu, W., 2023, Multiobjective Optimization of a 3D Laser Scanning Scheme for Engineering Structures Based on RF-NSGA-II, Journal of Construction Engineering and Management, 149 (2), 04022169. https://doi.org/10.1061/(ASCE)CO.1943-7862.0002411
• Cheng, R., Jin, Y., Olhofer, M. ve Sendhoff, B., 2016, A reference vector guided evolutionary algorithm for many-objective optimization, IEEE transactions on evolutionary computation, 20 (5), 773-791. https://doi.org/10.1109/TEVC.2016.2519378
• Cheraghi, R. ve Jahangir, M. H., 2023, Multi-objective optimization of a hybrid renewable energy system supplying a residential building using NSGA-II and MOPSO algorithms, Energy Conversion and Management, 294, 117515. https://doi.org/10.1016/j.enconman.2023.117515
• Coello, C. C. ve Lechuga, M. S., 2002, MOPSO: A proposal for multiple objective particle swarm optimization, Proceedings of the 2002 Congress on Evolutionary Computation. CEC'02 (Cat. No. 02TH8600), 1051-1056. Corne, D. W., Jerram, N. R., Knowles, J. D. ve Oates, M. J., 2001, PESA-II: Region-based selection in evolutionary multiobjective optimization, Proceedings of the 3rd annual conference on genetic and evolutionary computation, 283-290.
• Deb, K. ve Goyal, M., 1996, A combined genetic adaptive search (GeneAS) for engineering design, Computer Science and informatics, 26, 30-45.
• Deb, K., Agrawal, S., Pratap, A. ve Meyarivan, T., 2000, A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II, International conference on parallel problem solving from nature, 849-858.
• Deb, K., Pratap, A., Agarwal, S. ve Meyarivan, T., 2002, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE transactions on evolutionary computation, 6 (2), 182-197. https://doi.org/10.1109/4235.996017
• Deb, K., Thiele, L., Laumanns, M. ve Zitzler, E., 2005, Scalable test problems for evolutionary multiobjective optimization, In: Evolutionary multiobjective optimization, Eds: Springer, p. 105-145. Deb, K. ve Tiwari, S., 2008, Omni-optimizer: A generic evolutionary algorithm for single and multi-objective optimization, European Journal of Operational Research, 185 (3), 1062-1087. https://doi.org/10.1016/j.ejor.2006.06.042
• Deb, K. ve Jain, H., 2013, An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints, IEEE transactions on evolutionary computation, 18 (4), 577-601. https://doi.org/10.1109/TEVC.2013.2281535
• Dörterler, S., Dumlu, H., Özdemir, D. ve Temurtaş, H., 2022, Melezlenmiş K-means ve Diferansiyel Gelişim Algoritmaları ile Kalp Hastalığının Teşhisi, International Conference on Engineering and Applied Natural Sciences içinde (ss. 1840-1844). Konya.
• Emel, G. G. ve Taşkın, Ç., 2002, Genetik algoritmalar ve uygulama alanlari, Uludağ Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 21 (1), 129-152.
• Ewees, A. A., Abd Elaziz, M. ve Oliva, D., 2021, A new multi-objective optimization algorithm combined with opposition-based learning, Expert Systems with Applications, 165, 113844. https://doi.org/10.1016/j.eswa.2020.113844
• Glover, F., 1977, Heuristics for integer programming using surrogate constraints, Decision sciences, 8 (1), 156-166. https://doi.org/10.1111/j.1540-5915.1977.tb01074.x
• Hakli, H. ve Ortacay, Z., 2019, An improved scatter search algorithm for the uncapacitated facility location problem, Computers & Industrial Engineering, 135, 855-867. https://doi.org/10.1016/j.cie.2019.06.060
• Hassan, B. A., 2021, CSCF: a chaotic sine cosine firefly algorithm for practical application problems, Neural Computing and Applications, 33 (12), 7011-7030. https://doi.org/10.1007/s00521-020-05474-6
• Heidari, A., Imani, D. M., Khalilzadeh, M. ve Sarbazvatan, M., 2023, Green two-echelon closed and open location-routing problem: application of NSGA-II and MOGWO metaheuristic approaches, Environment, Development and Sustainability, 25 (9), 9163-9199 https://doi.org/10.1007/s10668-022-02429-w
• Huang, Y.-F. ve Chen, S.-H., 2020, Solving multi-objective optimization problems using self-adaptive harmony search algorithms, Soft Computing, 24 (6), 4081-4107. https://doi.org/10.1007/s00500-019-04175-0
• Hughes, E. J., 2003, Multiple single objective Pareto sampling, The 2003 Congress on Evolutionary Computation, 2003. CEC'03., 2678-2684.
• Kamjoo, A., Maheri, A., Dizqah, A. M. ve Putrus, G. A., 2016, Multi-objective design under uncertainties of hybrid renewable energy system using NSGA-II and chance constrained programming, International Journal of Electrical Power & Energy Systems, 74, 187-194. https://doi.org/10.1016/j.ijepes.2015.07.007
• Knowles, J. D. ve Corne, D. W., 2000, Approximating the nondominated front using the Pareto archived evolution strategy, Evolutionary computation, 8 (2), 149-172. https://doi.org/10.1162/106365600568167
• Li, K., Zhang, Q., Kwong, S., Li, M. ve Wang, R., 2013, Stable matching-based selection in evolutionary multiobjective optimization, IEEE transactions on evolutionary computation, 18 (6), 909-923. https://doi.org/10.1109/TEVC.2013.2293776
• Li, X. ve Li, S., 2021, An adaptive surrogate-assisted particle swarm optimization for expensive problems, Soft Computing, 25 (24), 15051-15065. https://doi.org/10.1007/s00500-021-06348-2
• Liu, Q., Jin, Y., Heiderich, M., Rodemann, T. ve Yu, G., 2022, An adaptive reference vector-guided evolutionary algorithm using growing neural gas for many-objective optimization of irregular problems, IEEE Transactions on Cybernetics, 52, 5, 2698-2711. https://doi.org/10.1109/TCYB.2020.3020630
• Ma, H., Wei, H., Tian, Y., Cheng, R. ve Zhang, X., 2021, A multi-stage evolutionary algorithm for multi-objective optimization with complex constraints, Information Sciences, 560, 68-91. https://doi.org/10.1016/j.ins.2021.01.029
• Mirjalili, S., Saremi, S., Mirjalili, S. M. ve Coelho, L. d. S., 2016, Multi-objective grey wolf optimizer: a novel algorithm for multi-criterion optimization, Expert Systems with Applications, 47, 106-119. https://doi.org/10.1016/j.eswa.2015.10.039
• Mirjalili, S., Jangir, P. ve Saremi, S., 2017, Multi-objective ant lion optimizer: a multi-objective optimization algorithm for solving engineering problems, Applied Intelligence, 46 (1), 79-95. https://doi.org/10.1007/s10489-016-0825-8
• Mirjalili, S. Z., Mirjalili, S., Saremi, S., Faris, H. ve Aljarah, I., 2018, Grasshopper optimization algorithm for multi-objective optimization problems, Applied Intelligence, 48 (4), 805-820. https://doi.org/10.1007/s10489-017-1019-8
• Murata, T. ve Ishibuchi, H., 1995, MOGA: multi-objective genetic algorithms, IEEE international conference on evolutionary computation, 289-294.
• Nebro, A. J., Durillo, J. J., Garcia-Nieto, J., Coello, C. C., Luna, F. ve Alba, E., 2009, SMPSO: A new PSO-based metaheuristic for multi-objective optimization, 2009 IEEE Symposium on computational intelligence in multi-criteria decision-making (MCDM), 66-73.
• Özdemir, D. ve Dörterler, S., 2022, An adaptive search equation-based artificial bee colony algorithm for transportation energy demand forecasting, Turkish Journal of Electrical Engineering and Computer Sciences, 30 (4), 1251-1268. https://doi.org/10.55730/1300-0632.3847
• Panagant, N., Bureerat, S. ve Tai, K., 2019, A novel self-adaptive hybrid multi-objective meta-heuristic for reliability design of trusses with simultaneous topology, shape and sizing optimisation design variables, Structural and Multidisciplinary Optimization, 60 (5), 1937-1955. https://doi.org/10.1007/s00158-019-02302-x
• Patil, R. N., Rawandale, S., Rawandale, N., Rawandale, U. ve Patil, S., 2023, An efficient stacking based NSGA-II approach for predicting type 2 diabetes, International Journal of Electrical and Computer Engineering (IJECE), 13 (1), 1015-1023. https://doi.org/10.11591/ijece.v13i1.pp1015-1023
• Peng, S., Liu, Q. ve Hu, J., 2023, Green Distribution Route Optimization of Medical Relief Supplies Based on Improved NSGA-II Algorithm under Dual-Uncertainty, Sustainability, 15 (15), 11939. https://doi.org/10.3390/su151511939
• rey Horn, J., Nafpliotis, N. ve Goldberg, D. E., 1994, A niched Pareto genetic algorithm for multiobjective optimization, Proceedings of the first IEEE conference on evolutionary computation, IEEE world congress on computational intelligence, 82-87.
• Schaffer, J. D., 1985, Multiple objective optimization with vector evaluated genetic algorithms, Proceedings of the first international conference on genetic algorithms and their applications, 1985. Sekkal, M., Benzina, A. ve badir Benkrelifa, L., 2024, Multi-Objective Evolutionary Algorithm based on NSGA-II for Neural Network Optimization Application to the Prediction of Severe Diseases, Informatica, 47 (10), 27-40. https://doi.org/10.31449/inf.v47i10.5126
• Tian, J., Tan, Y., Sun, C., Zeng, J. ve Jin, Y., 2016, A self-adaptive similarity-based fitness approximation for evolutionary optimization, 2016 IEEE symposium series on computational intelligence (SSCI), 1-8. Wang, R., Purshouse, R. C. ve Fleming, P. J., 2012, Preference-inspired coevolutionary algorithms for many-objective optimization, IEEE transactions on evolutionary computation, 17 (4), 474-494. https://doi.org/10.1109/TEVC.2012.2204264
• Yang, S., Li, M., Liu, X. ve Zheng, J., 2013, A grid-based evolutionary algorithm for many-objective optimization, IEEE transactions on evolutionary computation, 17 (5), 721-736. https://doi.org/10.1109/TEVC.2012.2227145
• Zeng, S., Yao, S., Kang, L. ve Liu, Y., 2005, An efficient multi-objective evolutionary algorithm: OMOEA-II, International Conference on Evolutionary Multi-Criterion Optimization, 108-119. Zhang, Q. ve Li, H., 2007, MOEA/D: A multiobjective evolutionary algorithm based on decomposition, IEEE transactions on evolutionary computation, 11 (6), 712-731 https://doi.org/10.1109/TEVC.2007.892759
• Zhang, X., Tian, Y. ve Jin, Y., 2014, A knee point-driven evolutionary algorithm for many-objective optimization, IEEE transactions on evolutionary computation, 19 (6), 761-776. https://doi.org/10.1109/TEVC.2014.2378512
• Zitzler, E., Deb, K. ve Thiele, L., 2000, Comparison of multiobjective evolutionary algorithms: Empirical results, Evolutionary computation, 8 (2), 173-195. Zitzler, E., Laumanns, M. ve Thiele, L., 2001, SPEA2: Improving the strength Pareto evolutionary algorithm, TIK-report, 103. https://doi.org/10.3929/ethz-a-004284029
• Zou, W., Zhu, Y., Chen, H. ve Zhang, B., 2011, Solving multiobjective optimization problems using artificial bee colony algorithm, Discrete dynamics in nature and society, 2011, 569784.