Adaptive Increasing/Decreasing PSO for Solving Dynamic Optimization Problems

Document Type : Persian Original Article

Author

Electrical and Computer Faculty, University of Birjand, Birjand, Iran

Abstract

Science progress has introduced new issues into the world requiring optimization algorithm with fast adaptation with uncertain environment changing with time. In these issues, location and optimized value change over time, so optimization algorithm should be capable of fast adaptation with variable conditions. This study has proposed a new algorithm based on particle optimization algorithm called Adaptive Increasing/Decreasing PSO. This algorithm, adaptively with an increase and decrease in the number of algorithm particles and effective search limit, is capable of searching and finding optimized number changed with time in non-linear and dynamic environments with undetectable changes. Also, a new definition, focused search zone, is provided for signalizing hopeful areas in order to accelerate local search process and prevent premature convergence, and success index as an indicator of the behavior of centralized search area in relation to environmental conditions. Results of the proposed algorithm on the moving peaks benchmark were assessed and compared with the results of some other studies. Results show positive effects of adaptive mechanisms such as a decrease and an increase in the particles and search limit on the duration of searching and finding optimization in comparison with other multi-population based optimization algorithms.

Keywords

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.
   [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.
Journal of Soft Computing and Information Technology
Volume 7, Issue 2 - Serial Number 2
Fall & Winter
January 2019
Pages 58-70

Files

Share

How to cite

Statistics