الگوریتم ژنتیک آشوب گونه مبتنی بر حافظه و خوشه بندی برای حل مسائل بهینه سازی پویا

نویسندگان

1 دانشگاه آزاد اسلامی واحد یاسوج

2 دانشگاه آزاد اسلامی واحد ممسنی

چکیده

چکیده: اکثر مسائل موجود در دنیای واقعی یک مسئله بهینه­سازی با ماهیتی پویا هستند، به‌طوری‌که مقدار بهینه سراسری آن­ها در طول زمان ممکن است تغییر کند، بنابراین برای حل این مسائل الگوریتم­هایی نیاز داریم که بتوانند خود را با شرایط این مسائل به­خوبی سازگار نموده و بهینه جدید را برای این مسائل ردیابی نمایند. در این مقاله، یک الگوریتم ژنتیک آشوب­گونه مبتنی بر خوشه­بندی و حافظه برای حل مسائل پویا ارائه شده است. یک سیستم آشوب­گـونه پیش­بینی دقیق­تـری از آینده نسبت بـه یک سیستم تصادفی دارد و میزان همگرایی را در الگوریتم افزایش می­دهد. به‌طور معمول استفاده از اطلاعات گذشته اجازه می­دهد الگوریتم به­­سرعت بعد از تغییر محیط به سازگاری در شرایط محیطی جدید برسد، بنابراین ایده موردنظر در این زمینه، استفاده از یک حافظه است که با استراتژی مناسبی اطلاعات مفید گذشته را ذخیره نموده و برای استفاده مجدد آن­ها را بازیابی می­نماید. خوشه­بندی در حافظه و جمعیت اصلی، تنوع را در حین اجرای الگوریتم با تبادل اطلاعات میان خوشه­های متناظر (خوشه­ها با برچسب شبیه به­هم) در حافظه و جمعیت اصلی حفظ می­نماید. به‌طورکلی در این روش پیشنهادی دو جنبه نوآوری اساسی پیشنهاد شده است. یکی روش خوشه­بندی استفاده‌شده که هم جمعیت اصلی و هم جمعیت حافظه را خوشه­بندی (خوشه­بندی مبتنی بر میانگین) می­کند و دیگری راهکار مناسبی است که برای به­روزرسانی حافظه استفاده شده است. برای آزمایش کارایی روش پیشنهادی از مسئله محک قله­های متحرک استفاده شده که رفتاری شبیه به مسائل پویا در دنیای واقعی را شبیه­سازی می­کند. نتایج آزمایش­ها کارایی مناسب روش پیشنهادی را در حل مسائل بهینه­سازی پویا در مقایسه با دیگر روش­ها نشان می­دهد.

کلیدواژه‌ها

عنوان مقاله [English]

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

چکیده [English]

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.

کلیدواژه‌ها [English]

  • Keywords: Dynamic optimization
  • genetic algorithm
  • explicit memory
  • chaos
  • Clustering

مراجع

[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.

فایل ها

هم رسانی

ارجاع به این مقاله

آمار