Multi-guide particle swarm optimisation archive management strategies for dynamic optimisation problems
Tóm tắt
This study presents archive management approaches for dynamic multi-objective optimisation problems (DMOPs) using the multi-guide particle swarm optimisation (MGPSO) algorithm by Scheepers et al. (Swarm Intell, 13(3–4):245–276, 2019,
https://doi.org/10.1007/s11721-019-00171-0
). The MGPSO is a multi-swarm approach developed for static multi-objective optimisation problems, where each subswarm optimises one of the objectives. It uses a bounded archive that is based on a crowding distance archive implementation. This paper adapts the MGPSO algorithm to solve DMOPs by proposing alternative archive update strategies to allow efficient tracking of the changing Pareto-optimal front. To evaluate the adapted MGPSO for DMOPs, a total of twenty-nine benchmark functions and six performance measures were implemented. The problem set consists of problems with only two or three objectives, and the exact time of the changes is assumed to be known beforehand. The experiments were run against five different environment types, where both the frequency of changes and the severity of changes parameters control how often and how severe the changes are during the optimisation of a DMOP. The best archive management approach was compared to the other state-of-the-art dynamic multi-objective optimisation algorithms (DMOAs). An extensive empirical analysis shows that MGPSO with a local search approach to the archive management achieves very competitive and oftentimes better performance when compared with the other DMOAs.
Tài liệu tham khảo
Branke, J., Salihoglu, E., & Uyar, S. (2005). Towards an analysis of dynamic environments. In Proceedings of the genetic and evolutionary computation conference (pp. 1433–1440). ACM. https://doi.org/10.1145/1068009.1068237
Cámara, M., Lopera, J. O., & de Toro, F. (2009). A single front genetic algorithm for parallel multi-objective optimization in dynamic environments. Neurocomputing, 72(16–18), 3570–3579. https://doi.org/10.1016/j.neucom.2008.12.041.
Cámara, M., Lopera, J. O., & de Toro, F. (2010). Approaching dynamic multi-objective optimization problems by using parallel evolutionary algorithms. In Advances in multi-objective nature inspired computing, studies in computational intelligence (Vol. 272, pp. 63–86). Springer. https://doi.org/10.1007/978-3-642-11218-8_4
Cámara, M., Ortega, J., & de Toro, F. (2007). Parallel processing for multi-objective optimization in dynamic environments. In Proceedings of the IEEE international parallel and distributed processing symposium (pp. 1–8). https://doi.org/10.1109/IPDPS.2007.370433
Deb, K., Agrawal, S., Pratap, A., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182–197. https://doi.org/10.1109/4235.996017.
Deb, K. Rao N, U. B., & Karthik, S. (2006). Dynamic multi-objective optimization and decision-making using modified NSGA-II: A case study on hydro-thermal power scheduling. In 4th international conference on proceedings of the evolutionary multi-criterion optimization, lecture notes in computer science (Vol. 4403, pp. 803–817). Springer. https://doi.org/10.1007/978-3-540-70928-2_60
Engelbrecht, A. P. (2013). Particle swarm optimization: Iteration strategies revisited. In Proceedings of the BRICS congress on computational intelligence & 11th Brazilian congress on computational intelligence (pp. 119–123). https://doi.org/10.1109/BRICS-CCI-CBIC.2013.30
Erwin, K., & Engelbrecht, A. P. (2019). Control parameter sensitivity analysis of the multi-guide particle swarm optimization algorithm. In Proceedings of the genetic and evolutionary computation conference (pp. 22–29). ACM. https://doi.org/10.1145/3321707.3321739
Farina, M., Deb, K., & Amato, P. (2004). Dynamic multiobjective optimization problems: Test cases, approximations, and applications. IEEE Transactions on Evolutionary Computation, 8(5), 425–442. https://doi.org/10.1109/TEVC.2004.831456.
Goh, C. K., & Tan, K. C. (2009). A competitive-cooperative coevolutionary paradigm for dynamic multiobjective optimization. IEEE Transactions on Evolutionary Computation, 13(1), 103–127. https://doi.org/10.1109/TEVC.2008.920671.
Greeff, M., & Engelbrecht, A. P. (2008). Solving dynamic multi-objective problems with vector evaluated particle swarm optimisation. In Proceedings of the IEEE congress on evolutionary computation (pp. 2917–2924). IEEE. https://doi.org/10.1109/CEC.2008.4631190
Harrison, K. R., Ombuki-Berman, B. M., & Engelbrecht, A. P. (2016). A radius-free quantum particle swarm optimization technique for dynamic optimization problems. In Proceedings of the IEEE congress on evolutionary computation (pp. 578–585). IEEE. https://doi.org/10.1109/CEC.2016.7743845
Helbig, M., & Engelbrecht, A. P. (2012). Analyses of guide update approaches for vector evaluated particle swarm optimisation on dynamic multi-objective optimisation problems. In Proceedings of the IEEE congress on evolutionary computation (pp. 1–8). IEEE. https://doi.org/10.1109/CEC.2012.6252882
Harrison, K. R., Engelbrecht, A. P., & Ombuki-Berman, B. M. (2018). Optimal parameter regions and the time-dependence of control parameter values for the particle swarm optimization algorithm. Swarm and Evolutionary Computation, 41, 20–35. https://doi.org/10.1016/j.swevo.2018.01.006.
Helbig, M., & Engelbrecht, A. P. (2013a). Analysing the performance of dynamic multi-objective optimisation algorithms. In Proceedings of the IEEE congress on evolutionary computation (pp. 1531–1539). IEEE. https://doi.org/10.1109/CEC.2013.6557744
Helbig, M., & Engelbrecht, A. P. (2013b). Benchmarks for dynamic multi-objective optimisation. In Proceedings of the IEEE symposium on computational intelligence in dynamic and uncertain environments (pp. 84–91). IEEE. https://doi.org/10.1109/CIDUE.2013.6595776
Helbig, M., & Engelbrecht, A. P. (2013c). Performance measures for dynamic multi-objective optimisation algorithms. Information Sciences, 250, 61–81. https://doi.org/10.1016/j.ins.2013.06.051.
Jiang, S., & Yang, S. (2017). A steady-state and generational evolutionary algorithm for dynamic multiobjective optimization. IEEE Transactions on Evolutionary Computation, 21(1), 65–82. https://doi.org/10.1109/TEVC.2016.2574621.
Jiang, S., Yang, S., Yao, X., Tan, K. C., Kaiser, M., & Krasnogor, N. (2017). Benchmark problems for CEC2018 competition on dynamic multiobjective optimisation. Tech. rep., Newcastle University, School of Computing. http://www.tech.dmu.ac.uk/%7Esyang/TF-ECiDUE/TR-CEC2018-DMOP-Competition.pdf
Joćko, P. (2021). Multi-guide particle swarm optimisation for dynamic multi-objective optimisation problems. Master’s thesis, Brock University.
Koo, W. T., Goh, C. K., & Tan, K. C. (2010). A predictive gradient strategy for multiobjective evolutionary algorithms in a fast changing environment. Memetic Computing, 2(2), 87–110. https://doi.org/10.1007/s12293-009-0026-7.
Leonard, B. J., & Engelbrecht, A. P. (2013). On the optimality of particle swarm parameters in dynamic environments. In Proceedings of the IEEE congress on evolutionary computation (pp. 1564–1569). IEEE. https://doi.org/10.1109/CEC.2013.6557748
Oldewage, E. T., Engelbrecht, A. P., & Cleghorn, C. W. (2019). Degrees of stochasticity in particle swarm optimization. Swarm Intelligence, 13(3–4), 193–215. https://doi.org/10.1007/s11721-019-00168-9.
Pamparà, G., & Engelbrecht, A. P. (2018). Self-adaptive quantum particle swarm optimization for dynamic environments. In 11th international conference on proceedings of the swarm intelligence, lecture notes in computer science (Vol. 11172, pp. 163–175). Springer. https://doi.org/10.1007/978-3-030-00533-7_13
Scheepers, C., Engelbrecht, A. P., & Cleghorn, C. W. (2019). Multi-guide particle swarm optimization for multi-objective optimization: Empirical and stability analysis. Swarm Intelligence, 13(3–4), 245–276. https://doi.org/10.1007/s11721-019-00171-0.
Schott, J. (2005). Fault tolerant design using single and multicriteria genetic algorithm optimization. Master’s thesis, Massachusetts Institute of Technology. http://hdl.handle.net/1721.1/11582
Shi, Y., & Eberhart, R. (1998). A modified particle swarm optimizer. In Proceedings of the IEEE international conference on evolutionary computation (pp. 69–73). https://doi.org/10.1109/ICEC.1998.699146
Weicker, K. (2002). Performance measures for dynamic environments. In Proceedings of the parallel problem solving from nature, lecture notes in computer science (Vol. 2439, pp. 64–76). Springer. https://doi.org/10.1007/3-540-45712-7_7
Zhang, K., Shen, C., Liu, X., & Yen, G. G. (2020). Multiobjective evolution strategy for dynamic multiobjective optimization. IEEE Transactions on Evolutionary Computation, 24(5), 974–988. https://doi.org/10.1109/TEVC.2020.2985323.
Zhou, A., Jin, Y., & Zhang, Q. (2014). A population prediction strategy for evolutionary dynamic multiobjective optimization. IEEE Transactions on Cybernetics, 44(1), 40–53. https://doi.org/10.1109/TCYB.2013.2245892.
Zhou, A., Jin, Y., Zhang, Q., Sendhoff, B., & Tsang, E. P. K. (2006). Prediction-based population re-initialization for evolutionary dynamic multi-objective optimization. In 4th international conference on proceedings of the evolutionary multi-criterion optimization, lecture notes in computer science (Vol. 4403, pp. 832–846). Springer. https://doi.org/10.1007/978-3-540-70928-2_62
Zitzler, E. (1999). Evolutionary algorithms for multiobjective optimization: Methods and applications. PhD thesis, University of Zurich, Zürich, Switzerland. http://d-nb.info/95814172X