Chaotic genetic algorithm based on clustering and memory for solving dynamic optimization problems

Abstract

Abstract: Most of the problems in the real world are of dyanamic optimization ones. It means that their optima may change over time, thus algorithms to solve these problems must be well adapt to their conditions in such a way that they should be able to track the optima during evolution. This article proposes a chaotic genetic algorithm based on clustering and memory for solving dynamic optimization problems. A chaotic system has more precise prediction of the future in comparison with random system and increases the speed of convergounce in the algorithm. The utilization of some information from the past allows quickly adapting right after a change. Thus the underlining idea of the paper is the use of memory in this field, which is a good strategy to store the useful information and retrieves them for reuse in the future. The clustering method maintains diversity in the memory and the population during running of the algorithm by exchanging information between corresponding clusters (clusters with similar tag) of the memory and the population. This algorithm uses a k-means clustering method to maintain diversity and improve local search.  In this paper used tow the main innovation: clustering method and memory update. To test the effectiveness of the proposed method we choose the Moving Peaks Benchmark that has similar behaviors to real world dynamic proplems. The experimental results show the efficiency of the proposed algorithm for solving optimization problems in comparison with other methods.

Keywords

References

[1] S. Yang and C. Li,  “A Clustering Particle  Swarm Optimizer  for Locating  and  Tracking  Multiple  Optima  in  Dynamic Environments,” IEEE  Transactions  on Evolutionary Computation, vol. 14, no. 6, pp. 959-974, 2010.
[2] L. Liu, S. Yang and D. Wang, “Particle Swarm Optimization With Composite Particles in Dynamic Environments,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 40, no. 6, pp. 1634-1648, 2010.
[3] S. Yang, “Explicit memory schemes for evolutionary algorithms in dynamic environments,” Studies in Computational Intelligence, vol. 51, pp. 3-28, 2007.
[4] S. Yang, “Genetic algorithms with elitism-based immigrants for changing optimization problems,” Lecture Notes in Computer Science 4448, pp. 627-636, 2007.
[5] S. Yang and C. Li,“A clustering particle swarm optimizer for locating and tracking multiple optima in dynamic environments,” IEEE Transactions on Evolutionary Computation, vol. 14, no. 6, pp. 959-974,2010.
[6] J. Branke, T. Kaußler, C. Schmidt and H. Schmeck, “A multi population approach to dynamic optimization problems,”in Adaptive Computing in Design and Manufacturing, pp. 299-308, 2000.
[7] T. Blackwell and J. Branke, “Multi-Swarms, Exclusion, and Anti-Convergence in Dynamic Environments,” IEEE Transactions on Evolutionary Computation, vol. 10, no. 4, pp. 459-472, 2006.
[8] T. Blackwell, J. Branke and X. Li, “Particle swarms for dynamic optimization problems,” Swarm Intelligence, pp. 193-217, 2008.
[9] J. Branke, Evolutionary Optimization in Dynamic Environment, Kluwer Academic Publishers Norwell, 2002.
[10] J. J. Grefenstette and C. L. Ramsey, "An approach to anytime learning," in International Conference on Machine Learning, pp. 189-195, 1992.
[11] S. Yang and C. Li, “A clustering particle swarm optimizer for dynamic optimization,” in IEEE Congress on Evolutionary Computation, pp. 439-446, 2009.
[12] S. Yang, “Memory-based immigrants for genetic algorithms in dynamic environments,” in Seventh International Genetic and Evolutionary Computation Conference (GECCO), vol. 2, pp. 1115-1122. 2005.
[13] S. Yang and C. Li, “Fast Multi-Swarm Optimization for Dynamic Optimization Problems,” in Fourth International Conference on Natural Computation, pp. 624-628, 2008.
[14] رحمت­اله هوشمند، حسین محکمی، امین خدابخشیان، «روشی جدید در جایابی بهینه خاز­ن­ها و ژنراتورهای توزیع‌شده در شبکه­های توزیع با استفاده از الگوریتم جستجوی اکتریای جهت داده‌شده با pso»، مجله مهندسی برق دانشگاه تبریز. جلد 39. شماره 2. 1389.
[15] الهام شکرانی­پور، مسعود افتخاری­مقدم، «یک الگـوریتم جـدید بهینه­سازی گروه ذرات تعاونی با قابلیت به‌روزرسانی تطبیقی پارامترها»، مجله مهندسی برق دانشگاه تبریز. جلد 40. شماره 2. زمستان 1389.
[16] R. Morrison and K. DeJong. “A test problem generator   for non-stationary environments,” In Congress on Evolutionary Computation, pp. 2047-2053, 1999.
[17] J. Branke, “Memory enhanced evolutionary algorithms for changing optimization problems,” In Congress on Evolutionary Computation, pp. 1875-1882, 1999.
[18] J. Holland, “Adaptation in Natural and Artificial Systems,” University of Michigan Press, Ann Arbor, MI, 1975.
[19] N.  Krasnogor and j. Smith “A Tutorial for Competent Memetic Algorithms: Model, Taxonomy, and Design Issues,” IEEE Transactions on Evolutionary Computation, vol. 9, no. 5, pp. 474-488, 2005.
[20] C. Ryan, “Diploidy without dominance,” In Nordic Workshop on Genetic Algorithms, pp. 45-52, 1997.
[21] S. Yang, “Genetic algorithms with elitism-based immigrants for changing optimization problems,” In Applications of Evolutionary Computing, Lecture Notes in Computer Science 4448, pp. 627-636, 2007.
[22] C. Ramsey and J. Grefenstette, “Case-based initialization of genetic algorithms,”in Proceedings of the Fifth International Conference on Genetic Algorithms, pp. 84-91, 1993.
[23] K. Trojanowski and Z. Michalewicz, “Searching for optima in non-stationary environments,” in Proceedings of the IEEE Congress on Evolutionary Computation (CEC 1999), pp. 1843-1850, 1999.
[24] A. Simoes andE. Costa, “Improving memory’s usage in evolutionary algorithms for changing environments,” in IEEE congress on evolutionary computation, pp. 276-283, 2007.
[25] D. Parrott and X. Li, “Locating and Tracking Multiple Dynamic Optima by A Particle Swarm Model Using  peciation,” IEEE Transaction on Evolutionary Computation, vol. 10, no. 4, pp. 440-458, 2006.
[26] B. Hashemi and M. R.  Meybodi, “Cellular PSO: A PSO for Dynamic Environments”, in Advances in Computation and ntelligence, Lecture Notes in Computer Science, vol. 5821, pp. 422-433, 2009.
[27] R. I. Lung and D. Dumitrescu, “Evolutionary swarm cooperative optimization in dynamic environments,” Natural Computing, vol. 9, no. 1, pp. 83-94, 2010.
[28] R. I. Lung and D. Dumitrescu,“A collaborative model for tracking optima in dynamic environments,” in IEEE Congress on Evolutionary Computation, pp. 564-567, 2007.
[29] G. J. Barlow, Improving memory for optimization and learning in dynamic environments, Ph.D. Thesis, Carnegie Mellon University, pp. 65-82, 2011.
TABRIZ JOURNAL OF ELECTRICAL ENGINEERING
Volume 46, Issue 3 - Serial Number 77
November 2016
Pages 299-318

Files

Share

How to cite

Statistics