Volume 22, Issue 2 (9-2025)                   JSDP 2025, 22(2): 3-30 | Back to browse issues page


XML Persian Abstract Print


Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Sadeghi Moghadam M, nejatian S, Parvin H, Bagheri Fard K, Yagoubian S H. Solving dynamic optimization problems with an Improved Imperialis Competition Algorithm. JSDP 2025; 22 (2) : 1
URL: http://jsdp.rcisp.ac.ir/article-1-1394-en.html
Associate Professor, Department of Electrical Engineering, Yasouj Branch, Islamic Azad University, Yasouj, Iran
Abstract:   (224 Views)
Optimization issues are often defined statically, assuming constant environmental conditions. However, in many real-world scenarios, problem environments are dynamic and continuously changing. Thus we need optimization algorithms that could solves those issues in dynamic environments as well. Dynamic optimization problems are change(s) that may occur through the time. Such environments are characterized by uncertainty, temporal changes, and structural complexities, which makes the optimization process a significant challenge. In addressing these challenges, evolutionary algorithms have emerged as one of the most effective approaches for solving dynamic optimization problems (DOPs). Among these algorithms, the Imperialist Competitive Algorithm (ICA), designed based on swarm intelligence and competition among imperialist countries, has garnered considerable attention due to its capability in solving static optimization issues. In this research, Imperialist Competitive Algorithms, inspired by the historical and political processes of colonization and assimilation, have been known as one of the efficient evolutionary algorithms. These algorithms face numerous challenges when dealing with dynamic problems , including reduced population diversity, performance degradation in conditions of rapid environmental changes, and limitations in optimal convergence. These cases indicate the need to develop improved and more adaptable versions of these algorithms. Using concepts such as memory, population clustering, and repulsion mechanisms, this algorithm has been able to maintain population diversity at all stages while increasing the speed of convergence in the face of environmental changes. The key feature of the proposed algorithm is the use of memory to store previous optimal solutions, a clustering mechanism to manage population diversity, and repulsion to prevent unnecessary accumulation of solutions in specific regions. Nevertheless, ICA exhibits poor performance in dynamic environments because it lacks mechanisms to maintain diversity, quick adaptation to environmental changes, and new optima track. This study presents an improved version of ICA aimed at overcoming these limitations. The proposed algorithm incorporates a combination of a memory mechanism and a clustering strategy to enhance its adaptability to environmental changes and preserve diversity within the population. The memory mechanism stores information about previous optima and utilizes it under appropriate conditions to accelerate the optimization process.for clustering method is used for clustering. Clustering in the proposed method ensures that diversity is maintained for the population during the execution of the algorithm. In this study, our goal is to solve problems that change the environment in a global way. That means, the fitness of all points in the environment changes. By testing just one point in the environment and comparing the fitness obtained with its previously stored value, we can detect a change in the environment. On the other hand, the clustering strategy, particularly the k-means technique, to maintain maintain population diversity and prevents the convergence of solutions to specific regions. Together, these two components create a balance between exploration and exploitation, thereby improving the algorithm's performance in dynamic environments. To evaluate the performance of the proposed algorithm, the Moving Peaks Benchmark (MPB) was used as a standard metric. Due to its capability to simulate complex and diverse changes in dynamic environments—particularly in Branke's second scenario—MPB is one of the most recognized tools for assessing the performance of dynamic optimization algorithms. The proposed algorithm was evaluated alongside advanced algorithms such as FTmPSO (TMO), RAmQSO-s4, RmNAFSA-s4, TFTmPSO, RFTmPSO, mQSO10 (5+5q), FMSO, CellularPSO, Multi-SwarmPSO, mCPSO, AmQSO*, FTMPSO, almPSO, and CDEPSA. Experimental results demonstrated that the proposed algorithm outperformed other methods in areas such as convergence speed, adaptability to environmental changes, and population diversity preservation. A key feature of the proposed algorithm is its ability to retain identified optima even after environmental changes. Additionally, the use of the k-means clustering technique has ensured that the algorithm effectively avoids excessive focus on specific regions and maintains population diversity while facing complex environmental changes. Another advantage of this algorithm is its scalability in handling dynamic optimization issues with high dimensions and complexities. These findings indicate that the proposed algorithm is not only effective in laboratory settings but also suitable for real-world applications with fast and dynamic changes.
Article number: 1
Full-Text [PDF 4399 kb]   (119 Downloads)    
Type of Study: Research | Subject: Paper
Received: 2023/09/1 | Accepted: 2025/07/21 | Published: 2025/09/13 | ePublished: 2025/09/13

References
1. M. Mavrovouniotis, Ch. Li and S. Yang, "A survey of swarm intelligence for dynamic optimization: Algorithm and application", Swarm and Evolutionary Computation, Vol. 33, pp. 1-17, 2017. [DOI:10.1016/j.swevo.2016.12.005]
2. J. Branke. Evolutionary Optimization in Dynamic Environments. Springer US, 2002. [DOI:10.1007/978-1-4615-0911-0]
3. T. T. Nguyen, Z. Yang, and S. Bonsall. Dynamic time-linkage problems - the challenges. In Computing and Communication Technologies, Research, Innovation, and Vision for the Future (RIVF), pages 1-6. IEEE, 2012b. doi: 10.1109/rivf.2012.6169823. [DOI:10.1109/rivf.2012.6169823]
4. M. N. Omidvar, B. Kazimipour, X. Li, and X. Yao. CBCC3 - a contribution-based cooperative co-evolutionary algorithm with improved exploration/exploitation balance. In Evolutionary Computation (CEC), 2016 IEEE Congress on, pages 3541-3548. IEEE, 2016. [DOI:10.1109/CEC.2016.7744238]
5. G. E. P. Box, G. M. Jenkins, G. C. Reinsel, and G. M. Ljung. Time series analysis: forecasting and control. Wiley, 2015.
6. E. Atashpaz-Gargari and C. Lucas, "Imperialist competitive algorithm: An algorithm for optimization inspired by imperialistic competition," 2007 IEEE Congress on Evolutionary Computation, 2007, pp. 4661-4667, doi: 10.1109/CEC.2007.4425083. [DOI:10.1109/CEC.2007.4425083]
7. H. Nakano, M. Kojima, and A. Miyauchi, "An artificial bee colony algorithm with a memory scheme for dynamic optimization problems," in Proceedings of the IEEE Congress on Evolutionary Computation (CEC '15), pp. 2657-2663, IEEE, May 2015. [DOI:10.1109/CEC.2015.7257217]
8. T. Blackwell and J. Branke, "MultiswarmT Exclusion, and Anti-Convergence in Dynamic Environment", 2006. [DOI:10.1109/TEVC.2005.857074]
9. Y. Jin and J. Branke. Evolutionary optimization in uncertain environments-a survey. IEEE Transactions on Evolutionary Computation, 9(3):303-317, 2005. [DOI:10.1109/TEVC.2005.846356]
10. S. Yang, "Memory-based immigrants for genetic algorithms in dynamic environments," in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '05), pp. 1115-1122, ACM, June 2005. [DOI:10.1145/1068009.1068196] [PMID]
11. R. Vafashoar and M. R. Meybodi, "A multi-population differential evolution algorithm based on cellular learning automata and evolutionary context information for optimization in dynamic environments," Appl. Soft Comput., p. 106009, 2019. [DOI:10.1016/j.asoc.2019.106009]
12. M. Yasrebi, A. Eskandar-Baghban, H. Parvin, M. Mohammadpour, "Optimisation inspiring from behaviour of raining in nature: droplet optimisation algorithm," International Journal of Bio-Inspired Computation, vol. 12, no. 3, pp. 152-163, 2018. [DOI:10.1504/IJBIC.2018.094616]
13. D. Yazdani, T. T. Nguyen, J. Branke, and J. Wang. A new multi swarm particle swarm optimization for robust optimization over time. In G. Squillero and K. Sim, editors, Applications of Evolutionary Computation, volume 10200, pages 99{109. Springer Lecture Notes in Computer Science, 2017. [DOI:10.1007/978-3-319-55792-2_7]
14. D. Yazdani, T. T. Nguyen, J. Branke, and J. Wang. A new multi swarm particle swarm optimization for robust optimization over time. In G. Squillero and K. Sim, editors, Applications of Evolutionary Computation, volume 10200, pages 99-109. Springer Lecture Notes in Computer Science, 2017. [DOI:10.1007/978-3-319-55792-2_7]
15. D. Yazdani, T. T. Nguyen, and J. Branke. Robust optimization over time by learning problem space characteristics. IEEE Transactions on Evolutionary Computation, 2018a. [DOI:10.1109/TEVC.2018.2843566]
16. J. Branke, "Memory enhanced evolutionary algorithms for changing optimization problems," in Proc. Congr. Evol. Comput., vol. 3. 1999, pp. 1875-1882. [DOI:10.1109/CEC.1999.785502]
17. S. Yang, "Associative memory scheme for genetic algorithms in dynamic environments," in Proc. EvoWorkshops: Appl. Evol. Comput., LNCS 3907. 2006, pp. 788-799. [DOI:10.1007/11732242_76]
18. S. Yang, "Genetic algorithms with memory and elitism-based immigrants in dynamic environment," Evol. Comput., vol. 16, no. 3, pp. 385-416, 2008. [DOI:10.1162/evco.2008.16.3.385] [PMID]
19. J. Branke, "Memory enhanced evolutionary algorithms for changing optimization problems", In IEEE Congress on Evolutionary Computation, pages 1875-1882. IEEE, 1999. doi: 10.1109/CEC.1999.785502. [DOI:10.1109/CEC.1999.785502]
20. H., Parvin, S., Nejatian M., Mohammadpour, "Explicit memory based ABC with a clustering strategy for updating and retrieval of memory in dynamic environments", Applied Intelligence, Volume 48 , V, 11., pages, 4317-4337, doi: https://doi.org/10.1007/s10489-018-1197-z [DOI:10.1007/s10489-018-1197-z, 2018.]
21. M. Mohammadpour, H. Parvin, M. Sina "Chaotic Genetic Algorithm based on Explicit Memory with a New Strategy for Updating and Retrieval of Memory in Dynamic Environments," In Journal of AI and Data Mining. (Vol 6, No 1), Pages, 191-205, 2018.
22. X. Chen, D. Zhang and X. Zeng, "Matching-Based Selection and Memory Enhanced MOEDA/D for Evolutionary Dynamic Multiobjective Optimization," Tools with Artificial intelligence (ICTAI), 2015 IEEE 27th International Conference on, pages 478 485. [DOI:10.1109/ICTAI.2015.77]
23. Yang S (2008) Genetic algorithms with memory- and elitism-based immigrants in dynamic environments. Evol Comput 16(3):385 416. [DOI:10.1162/evco.2008.16.3.385] [PMID]
24. D. Yazdani., R. Cheng., D. Yazdani, J. Branke, Y. Jin., & X. Yao. A Survey of Evolutionary Continuous Dynamic Optimization Over Two Decades-Part A. In IEEE Transactions on Evolutionary Computation (Vol. 25, Issue 4, pp. 609-629). Institute of Electrical and Electronics Engineers (IEEE), 2021. https://doi.org/10.1109/TEVC.2021.3060014 [DOI:10.1109/tevc.2021.3060014.]
25. B. Niu, Q. Liu, and J. Wang, "Bacterial foraging optimization with memory and clone schemes for dynamic environments," in Advances in Swarm Intelligence, Y. Tan et al., Ed. Springer International Publishing, 2019, pp. 352-360. [DOI:10.1007/978-3-030-26369-0_33]
26. Y. Bravo, G. Luque, and E. Alba, "Global memory schemes for dynamic optimization," Natural Computing, vol. 15, no. 2, pp. 319-333, 2015. [DOI:10.1007/s11047-015-9497-2]
27. M. Moradi, S. Nejatian, H. Parvin and V. Rezaie, "CMCABC: Clustering and Memory-Based Chaotic Artificial Bee Colony Dynamic Optimization Algorithm", International Journal of Information Technology & Decision MakingVol. 17, No. 04, pp. 1007-1046, 2018. [DOI:10.1142/S0219622018500153]
28. Yang, S., and Li, C., "A General Framework of Multipopulation Methods with Clustering in Undetectable Dynamic Environments". IEEE Transactions on Evolutionary Computation, vol. 16, no. 4, pp. 556-577, 2012. [DOI:10.1109/TEVC.2011.2169966]
29. B. Niu, Q. Liu, and J. Wang, "Bacterial foraging optimization with memory and clone schemes for dynamic environments," in Advances in Swarm Intelligence, Y. Tan et al., Ed. Springer International Publishing, 2019, pp. 352-360. [DOI:10.1007/978-3-030-26369-0_33]
30. Y. Bravo, G. Luque, and E. Alba, "Global memory schemes for dynamic optimization," Natural Computing, vol. 15, no. 2, pp. 319-333, 2015. [DOI:10.1007/s11047-015-9497-2]
31. S. A. van der Stockt and A. P. Engelbrecht, "Analysis of selection hyper-heuristics for population-based meta-heuristics in real-valued dynamic optimization," Swarm Evol. Comput., vol. 43, pp. 127-146, 2018. [DOI:10.1016/j.swevo.2018.03.012]
32. W. Zhang, M. Zhang, W. Zhang, Y. Meng, and H. Wu, "Innate-adaptive response and memory based artificial immune system for dynamic optimization," International Journal of Performability Engineering, vol. 14, no. 9, p. 2048, 2018. [DOI:10.23940/ijpe.18.09.p13.20482055]
33. W. Luo, J. Sun, C. Bu, and H. Liang, "Species-based particle swarm optimizer enhanced by memory for dynamic optimization," Appl. Soft Comput., vol. 47, pp. 130 - 140, 2016. [DOI:10.1016/j.asoc.2016.05.032]
34. T. Zhu, W. Luo, and L. Yue, "Combining multipopulation evolutionary algorithms with memory for dynamic optimization problems," in IEEE Congr. Evol. Comput. IEEE, 2014, pp. 2047-2054. [DOI:10.1109/CEC.2014.6900492]
35. J. K. Kordestani, A. E. Ranginkaman, M. R. Meybodi, and P. Novoa-Hernandez, "A novel framework for improving multi-population algorithms for dynamic optimization problems: A scheduling approach," Swarm Evol. Comput., vol. 44, pp. 788 - 805, 2019. [DOI:10.1016/j.swevo.2018.09.002]
36. Zhu, T., Luo, W., & Yue, L. (2014). Dynamic optimization facilitated by the memory tree. In Soft Computing (Vol. 19, Issue 3, pp. 547-566). Springer Science and Business Media LLC. https://doi.org/10.1007/s00500-014-1273-1 [DOI:10.1007/s00500-014-1273-1.]
37. Yang S (2008) Genetic algorithms with memory- and elitism-based immigrants in dynamic environments. Evol Comput 16(3):385 416. [DOI:10.1162/evco.2008.16.3.385] [PMID]
38. Yang S, Yao X (2008) Population-based incremental learning with associative memory for dynamic environments. IEEE Trans Evol Comput 12(5):542-561.Simöes A, Costa E (2007b) Variable-size memory evolutionary algorithm to deal with dynamic environments. In: Applications of evolutionary computing, vol. 4448. Springer, Berlin, pp 617-626. [DOI:10.1109/TEVC.2007.913070]
39. Tinós R, Yang S (2007) A self-organizing random immigrants genetic algorithm for dynamic optimization problems. Gen Progr Evolv Mach 8(3):255-286. [DOI:10.1007/s10710-007-9024-z]
40. Urbanowicz RJ, Moore JH (2009) Learning classifier systems: a complete introduction, review, and roadmap. J Artif Evol Appl 2009. [DOI:10.1155/2009/736398]
41. S. Sadeghi, H. Parvin and F. Rad, "Particle Swarm Optimization for Dynamic Environments," in Springer International Publishing, 14th Mexican International Conference on Artificial intelligence, MICAI, 2015.
42. D. Yazdani, B. Nasiri, A. Sepas-Moghaddam and M. Meybodi, "a novel multi-swarm algorithm for optimization in dynamic environments based on particle swarm optimization," Applied Soft Computing, 2013. [DOI:10.1016/j.asoc.2012.12.020]
43. S. Kundu, D. Basu, and S. S. Chaudhuri, "Multipopulation-based differential evolution with speciation-based response to dynamic environments," in Swarm, Evolutionary, and Memetic Computing, B. K. Panigrahi et al., Ed. Springer International Publishing, 2013, pp. 222-235. [DOI:10.1007/978-3-319-03753-0_21]
44. Barlow GJ, Improving memory for optimization and learning in dynamic environments. Doctoral dissertation, Carnegie Mellon University, Pittsburgh, 2011.
45. J. K. Kordestani, A. Rezvanian, and M. R. Meybodi, "Cdepso: a bi-population hybrid approach for dynamic optimization problems," Applied Intelligence, vol. 40, no. 4, pp. 682-694, 2014. [DOI:10.1007/s10489-013-0483-z]
46. U. Halder, D. Maity, P. Dasgupta, and S. Das, "Self-adaptive cluster-based differential evolution with an external archive for dynamic optimization problems," in Swarm, Evolutionary, and Memetic Computing, B. K. Panigrahi et al., Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 19-26. [DOI:10.1007/978-3-642-27172-4_3]
47. H. Wang, S. Yang, W. Ip, and D. Wang, "A memetic particle swarm optimisation algorithm for dynamic multi-modal optimisation problems," International Journal of Systems Science, vol. 43, no. 7, pp. 1268-1283, 2012. [DOI:10.1080/00207721.2011.605966]
48. R. Mukherjee, G. R. Patra, R. Kundu, and S. Das, "Cluster-based differential evolution with crowding archive for niching in dynamic environments," Inf. Sci., vol. 267, pp. 58 - 82, 2014. [DOI:10.1016/j.ins.2013.11.025]
49. W. Wu, D. Xie, and L. Liu, "Heterogeneous differential evolution with memory enhanced brownian and quantum individuals for dynamic optimization problems," International Journal of Pattern Recognition and Artificial Intelligence, vol. 32, no. 02, p. 1859003, 2018. [DOI:10.1142/S0218001418590036]
50. R. Vafashoar and M. R. Meybodi, "A multi-population differential evolution algorithm based on cellular learning automata and evolutionary context information for optimization in dynamic environments," Appl. Soft Comput., p. 106009, 2019. [DOI:10.1016/j.asoc.2019.106009]
51. D. Yazdani, T. T. Nguyen, J. Branke, and J. Wang. A multi-objective time-linkage approach for dynamic optimization problems with previous-solution displacement restriction. In European Conference on the Applications of Evolutionary Computation. Lecture Notes in Computer Science, 2018b. [DOI:10.1007/978-3-319-77538-8_57]
52. D. Yazdani, B. Nasiri, R. Azizi, A. Sepas-Moghaddam, and M. R. Meybodi. Optimization in dynamic environments utilizing a novel method based on particle swarm optimization. International Journal of Artificial Intelligence, 11:170-192, 2013a.
53. D. Yazdani. "Particle swarm optimization for dynamically changing environments with particular focus on scalability and switching cost", Doctoral thesis, Liverpool John Moores University, (2018).

Add your comments about this article : Your username or Email:
CAPTCHA

Send email to the article author


Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

© 2015 All Rights Reserved | Signal and Data Processing