الگوریتم انطباقی بهینه سازی ذرات افزایشی کاهشی برای حل مسائل بهینه سازی پویا

نوع مقاله: مقاله پژوهشی فارسی

نویسندگان

1 دانشکده مهندسی برق و کامپیوتر، دانشگاه بیرجند، بیرجند، ایران.

2 استاد، دانشکده مهندسی برق و کامپیوتر، دانشگاه بیرجند، بیرجند، ایران

چکیده

با پیشرفت روز افزون علم، همواره با مسائل جدیدی در دنیای واقعی روبرو میشویم که نیاز به الگوریتم بهینه سازی با قابلیت انطباق سریع با محیط در حال تغییر با زمان و غیرقطعی را بیشتر نمایان می کند. در این گونه مسائل شرایط همواره بگونه ای پیش می رود که مکان و مقدار بهینه در طول زمان تغییر می یابد، از این رو الگوریتم بهینه سازی باید توانایی انطباق سریع با شرایط متغیر را دارا باشد. در این مقاله الگوریتم جدیدی بر مبنای الگوریتم بهینه سازی ذرات به نام الگوریتم انطباقی بهینه سازی ذرات افزایشی کاهشی، پیشنهاد شده است. این الگوریتم همواره در روند بهینه سازی به طور انطباقی با کاهش یا افزایش تعداد ذرات الگوریتم و محدوده جستجو موثر توانایی یافتن و دنبال کردن تعداد بهینه متغیر با زمان در محیط های غیرخطی و پویایی که تغییرات آن قابل آشکارسازی نیست، را دارا می باشد. علاوه بر این تعاریف جدیدی به نام ناحیه جستجو متمرکز با هدف برجسته کردن فضاهای امیدبخش برای سرعت بخشیدن به فرایند جستجوی محلی و جلوگیری از همگرایی زودرس و شاخص موفقیت به عنوان معیاری برای چگونگی رفتار ناحیه جستجو متمرکز نسبت به شرایط محیطی، تعریف شده است. نتایج حاصل از الگوریتم پیشنهادی بر روی تابع محک قله های متحرک ارزیابی شده و با نتایج چندین الگوریتم معتبر مقایسه گردیده است. نتایج نشان دهنده تاثیر مثبت مکانیزم های انطباقی بکار گرفته شده از جمله کاهش و افزایش ذرات و محدوده جستجو بر زمان یافتن و دنبال کردن چندین بهینه در مقایسه با سایر الگوریتم های بهینه سازی مبتنی بر چند جمعیتی می باشد.

کلیدواژه‌ها


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

   [2]      T. T. Nguyen, S. Yang, and J. Branke, “Evolutionary dynamic optimization: A survey of the state of the art”, Swarm and Evolutionary Computation, Vol. 6, pp. 1-24, 2012.

   [3]      M. Mavrovouniotis, S. Yang, “Adapting the pheromone evaporation rate in dynamic routing problems”, In European Conference on the Applications of Evolutionary Computation, pp. 606–615, 2013.

   [4]      A. Baykaso˘glu, F. Ozsoydan, “An improved firefly algorithm for solving dynamic multidimensional knapsack problems”, Expert Systems with Applications, Vol. 41, pp. 3712–3725, 2014.

   [5]      J. Euchi, A. Yassine, H. Chabchoub, “The dynamic vehicle routing problem: Solution with hybrid metaheuristic approach”, Swarm and Evolutionary Computation, Vol. 21, pp. 41–53, 2015.

   [6]      Y. E. Demirtas¸, E. ¨Ozdemir, U. Demirtas¸, “A particle swarm optimization for the dynamic vehicle routing problem”, In Modeling, Simulation, and Applied Optimization (ICMSAO), pp. 1–5, 2015.

   [7]      M. R. Khouadjia, B.Sarasola, E. Alba, L. Jourdan, E.-G. Talbi, “A comparative study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic requests”, Applied Soft Computing, Vol. 12, pp. 1426–1439, 2012.

   [8]      M. Okulewicz, J.Ma´ndziuk, “Application of particle swarm optimization algorithm to dynamic vehicle routing problem”, In Artificial Intelligence and Soft Computing (ICAISC), pp. 547–558, 2013.

   [9]      M. Mavrovouniotis, S. Yang, “Applying ant colony optimization to dynamic binary-encoded problem”, In Applications of Evolutionary Computation, Vol. 9028, pp. 845–856, 2015.

[10]      U. Boryczka, Ł. Stra¸k, “Diversification and entropy improvement on the DPSO algorithm for DTSP”, In Intelligent Information and Database Systems (ACIIDS), pp. 337–347, 2015.

[11]      M. Mavrovouniotis, S. Yang, “Ant colony optimization with self-adaptive evaporation rate in dynamic environments”, In IEEE Symposium on Computational Intelligence in Dynamic and Uncertain Environments (CIDUE), pp. 47–54, 2014.

[12]      M. Mavrovouniotis, S. Yang, “Memory-based immigrants for ant colony optimization in changing environments”, In Applications of Evolutionary Computation, Vol. 6624, pp. 324–333, 2011,

[13]      M. Mavrovouniotis, S. Yang, “Interactive and non-interactive hybrid immigrants schemes for ant algorithms in dynamic environments”, In IEEE Congress on Evolutionary Computation (CEC), pp. 1542– 1549, 2014.

[14]      S. Gao, Y.Wang, J. Cheng, Y. Inazumi, Z. Tang, “Ant colony optimization with clustering for solving the dynamic location routing problem”, Applied Mathematics and Computation., Vol. 285, pp. 149–173, 2016.

[15]      M. Mavrovouniotis, S. Yang, “Ant colony optimization with memorybased immigrants for the dynamic vehicle routing problem”, In 2012 IEEE Congress on Evolutionary Computation (CEC), pp. 2645– 2652, 2012.

[16]      M. Mavrovouniotis, S. Yang, “Ant colony optimization with immigrants schemes for the dynamic travelling salesman problem with traffic factors”, Applied Soft Computing, Vol. 13, pp. 4023–4037, 2013.

[17]      M. Mavrovouniotis, S. Yang, X. Yao, “Multi-colony ant algorithms for the dynamic travelling salesman problem”, In IEEE Symposium on Computational Intelligence in Dynamic and Uncertain Environments (CIDUE), pp. 9–16, 2014.

[18]      B. van Veen, M. Emmerich, Z. Yang, T. B¨ack, J. Kok, “Ant colony algorithms for the dynamic vehicle routing problem with time windows”, In 5th International Work-Conference on the Interplay Between Natural and Artificial Computation (IWINAC), pp. 1–10, 2013.

[19]      Z. Yang, M. Emmerich, T. B¨ack, “Ant based solver for dynamic vehicle routing problem with time windows and multiple priorities”, In 2015 IEEE Congress on Evolutionary Computation (CEC), pp. 2813– 2819, 2015.

[20]      L. Melo, F. Pereira, E. Costa, “Multi-caste ant colony algorithm for the dynamic traveling salesperson problem”, In Adaptive and Natural Computing Algorithms, pp. 179–188, 2013.

[21]      L. Melo, F. Pereira, E. Costa, “Extended experiments with ant colony optimization with heterogeneous ants for large dynamic traveling salesperson problems”, In 14th International Conference on Computational Science and Its Applications (ICCSA), pp. 171–175, 2014.

[22]      U. Boryczka, Ł. Stra¸k, “Heterogeneous DPSO algorithm for DTSP”, In Computational Collective Intelligence (ICCCI), pp. 119–128, 2015.

[23]      M. Okulewicz, J. Ma´ndziuk, “Two-phase multi-swarm PSO and the dynamic vehicle routing problem”, In IEEE Symposium on Computational Intelligence for Human-like Intelligence (CIHLI), pp. 1–8, 2014.

[24]      M. Mavrovouniotis, S. Yang, “A memetic ant colony optimization algorithm for the dynamic travelling salesman problem”, Soft Computing, Vol. 15, No. 7, pp. 1405–1425, 2011.

[25]      M. Mavrovouniotis, S. Yang, “Dynamic vehicle routing: A memetic ant colony optimization approach”, In Automated Scheduling and Planning, pp. 283– 301, 2013.

[26]      M. Mavrovouniotis, F. M. M¨uller and S. Yang, “Ant colony optimization with local search for the dynamic travelling salesman problems”, IEEE Transactions on Cybernetics, Vol. 99, pp. 1–14, 2016.

[27]      L. Liu and S. R. Ranjithan, “An adaptive optimization technique for dynamic environments”, Engineering Applications of Artificial Intelligence, Vol. 23, No. 5, pp. 772– 779, 2010.

[28]      D. Parrott, X. Li, “Locating and tracking multiple dynamic optima by a particle swarm model using speciation”, IEEE Transactions on Evolutionary Computation, Vol. 10, No. 4, pp. 440–458, 2006.

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

[30]      C. Li and S. Yang, “A clustering particle swarm optimizer for dynamic optimization”, In IEEE Congress on Evolutionary Computation, pp. 439–446, 2009.

[31]      J. Branke, “Memory enhanced evolutionary algorithms for changing optimization problems”, In Proceedings of the 1999 Congress on Evolutionary Computation, Vol. 3, pp. 1875–1882, 1999.

[32]      J. Yaochu and J. Branke, “Evolutionary optimization in uncertain environments-a survey”, IEEE Transactions on Evolutionary Computation, Vol. 9, pp. 303-317, 2005.

[33]      M. Khouadjia, E. Alba, L. Jourdan, E.-G. Talbi, “Multi-swarm optimization for dynamic combinatorial problems: A case study on dynamic vehicle routing problem”, In Swarm Intelligence, pp. 227– 238, 2010.

[34]      J. Branke, T. Kaußler, C. Schmidth, and H. Schmeck, “A multipopulation approach to dynamic optimization problem”, In   Proceedings of the Congress on Evolutionary Computation, pp. 299–308, 2000.

[35]      C. Li and S. Yang, “Fast multi-swarm optimization for dynamic optimization problems”, In 4th International Conference on Natural Computation, Vol. 7, pp. 624–628, 2008.

[36]      M. Kamosi, A. B. Hashemi, and M. R. Meybodi, “A hibernating multiswarm optimization algorithm for dynamic environments”, In World Congress on Nature and Biologically Inspired Computing, NaBIC2010, pp. 363–369, 2010.

[37]      T. M. Blackwell and J. Branke, “Multiswarms, exclusion, and anticonvergence in dynamic environments”, IEEE Transactions on Evolutionary Computation, Vol. 10, No. 4, pp. 459–472, 2006.

[38]      I. del Amo, D. Pelta, Gonz´aez, and J. lez, “Using heuristic rules to enhance a multiswarm pso for dynamic environments”, In IEEE Congress on Evolutionary Computation, pp. 1–8, 2010.

[39]      C. Li, S. Yang, “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.

[40]      A. Simoes and E. Costa, “Evolutionary algorithms for dynamic environments: prediction using linear regression and markov chains”, In Parallel Problem Solving from Nature, pp. 306–315, 2008.

[41]      J. Kennedy and R. C. Eberhart, “Particle swarm optimization”, In Proc. IEEE International Conference on Neural Networks, pp. 1942–1948, 1995.

[42]      Y. Shi, R. Eberhart, “A modified particle swarm optimizer”, In IEEE World Congress on Computational Intelligence, pp. 69–73, 1998.

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

[44]      S. Bird and X. Li, “Using regression to improve local convergence”, In IEEE Congress on Evolutionary Computation, pp. 592–599, 2007.

[45]      T. Blackwell, J. Branke, and X. Li, “Particle swarms for dynamic optimization problems", Swarm Intelligence, pp. 193-217, 2008.

[46]      M. Kamosi, A. Hashemi, and M. Meybodi, “A New Particle Swarm Optimization Algorithm for Dynamic Environments", In International Conference on Swarm, Evolutionary, and Memetic Computing, pp. 129-138, 2010.

[47]      I. Rezazadeh, M. Meybodi, and A. Naebi, “Adaptive particle swarm optimization algorithm for dynamic environments”, Advances in Swarm Intelligence, pp. 120-129, 2011.

[48]      D. Yazdani, B. Nasiri, A. Sepas-Moghaddam, and M. R. Meybodi, “A novel multi-swarm algorithm for optimization in dynamic environments based on particle swarm optimization”, Applied Soft Computing, Vol. 13, pp. 2144-2158, 2013.

[49]      B. Nasiri and M. Meybodi, “Speciation based firefly algorithm for optimization in dynamic environments”, International Journal of Artificial Intelligence, Vol. 8, pp. 118-132, 2012.

[50]      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, Vol. 11, pp. 170-192, 2013.

[51]      J. K. Kordestani, A. Rezvanian, and M. R. Meybodi, “CDEPSO: a bi-population hybrid approach for dynamic optimization problems”, Applied intelligence, Vol. 40, pp. 682-694, 2014.

[52]      R. Mukherjee, G. R. Patra, R. Kundu, and S. Das, “Cluster-based differential evolution with Crowding Archive for niching in dynamic environments”, Information Sciences, Vol. 267, pp. 58- 82, 2014.