×

A reinforcement learning approach for dynamic multi-objective optimization. (English) Zbl 1475.90099

Summary: Dynamic Multi-objective Optimization Problem (DMOP) is emerging in recent years as a major real-world optimization problem receiving considerable attention. Tracking the movement of Pareto front efficiently and effectively over time has been a central issue in solving DMOPs. In this paper, a reinforcement learning-based dynamic multi-objective evolutionary algorithm, called RL-DMOEA, which seamlessly integrates reinforcement learning framework and three change response mechanisms, is proposed for solving DMOPs. The proposed algorithm relocates the individuals based on the severity degree of environmental changes, which is estimated through the corresponding changes in the objective space of their decision variables. When identifying different severity degree of environmental changes, the proposed RL-DMOEA approach can learn better evolutionary behaviors from environment information, based on which apply the appropriate response mechanisms. Specifically, these change response mechanisms including the knee-based prediction, center-based prediction and indicator-based local search, are devised to promote both convergence and diversity of the algorithm under different severity of environmental changes. To verify this idea, the proposed RL-DMOEA is evaluated on CEC 2015 test problems involving various problem characteristics. Empirical studies on chosen state-of-the-art designs validate that the proposed RL-DMOEA is effective in addressing the DMOPs.

MSC:

90C29 Multi-objective and goal programming
68T05 Learning and adaptive systems in artificial intelligence

Software:

MOEA/D
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] V.S. Aragón, S.C. Esquivel, C. Coello Coello. Evolutionary multiobjetive optimization in non-stationary environments, Journal of Computer Science & Technology 5 (2005). · Zbl 1202.74128
[2] Azzouz, R.; Bechikh, S.; Said, L. B., A dynamic multi-objective evolutionary algorithm using a change severity-based adaptive population management strategy, Soft Computing, 21, 4, 885-906 (2017)
[3] Branke, J.; Deb, K.; Dierolf, H.; Osswald, M., Finding knees in multi-objective optimization, (International Conference on Parallel Problem Solving from Nature (2004), Springer), 722-731
[4] Bravo, Y.; Luque, G.; Alba, E., Global memory schemes for dynamic optimization, Natural Computing, 15, 2, 319-333 (2016) · Zbl 1415.68186
[5] Cámara, M.; Ortega, J.; de Toro, F., A single front genetic algorithm for parallel multi-objective optimization in dynamic environments, Neurocomputing, 72, 16-18, 3570-3579 (2009)
[6] Chen, R.; Li, K.; Yao, X., Dynamic multiobjectives optimization with a changing number of objectives, IEEE Transactions on Evolutionary Computation, 22, 1, 157-171 (2017)
[7] Chiu, W.-Y.; Yen, G. G.; Juan, T.-K., Minimum manhattan distance approach to multiple criteria decision making in multiobjective optimization problems, IEEE Transactions on Evolutionary Computation, 20, 6, 972-985 (2016)
[8] Coello, C. A.C.; Pulido, G. T.; Lechuga, M. S., Handling multiple objectives with particle swarm optimization, IEEE Transactions on Evolutionary Computation, 8, 3, 256-279 (2004)
[9] Cruz, C.; González, J. R.; Pelta, D. A., Optimization in dynamic environments: A survey on problems, methods and measures, Soft Computing, 15, 7, 1427-1448 (2011)
[10] K. Deb, S. Karthik, et al. Dynamic multi-objective optimization and decision-making using modified nsga-II: A case study on hydro-thermal power scheduling. In International conference on evolutionary multi-criterion optimization, Springer, 2007, pp 803-817.
[11] Farina, M.; Deb, K.; Amato, P., Dynamic multiobjective optimization problems: test cases, approximations, and applications, IEEE Transactions on Evolutionary Computation, 8, 5, 425-442 (2004)
[12] Goh, C.-K.; Tan, K. C., A coevolutionary paradigm for dynamic multi-objective optimization, (Evolutionary Multi-objective Optimization in Uncertain Environments (2009), Springer), 153-185
[13] M. Helbig, A. Engelbrecht, Benchmark functions for cec 2015 special session and competition on dynamic multi-objective optimization. Tech. Rep., 2015.
[14] Jiang, M.; Huang, Z.; Qiu, L.; Huang, W.; Yen, G. G., Transfer learning-based dynamic multiobjective optimization algorithms, IEEE Transactions on Evolutionary Computation, 22, 4, 501-514 (2018)
[15] Jiang, S.; Yang, S., A steady-state and generational evolutionary algorithm for dynamic multiobjective optimization, IEEE Transactions on Evolutionary Computation, 21, 1, 65-82 (2016)
[16] Koo, W. T.; Goh, C. K.; Tan, K. C., A predictive gradient strategy for multiobjective evolutionary algorithms in a fast changing environment, Memetic Computing, 2, 2, 87-110 (2010)
[17] Li, H.; Zhang, Q., Multiobjective optimization problems with complicated pareto sets, MOEA/D and NSGA-II, IEEE Transactions on Evolutionary Computation, 13, 2, 284-302 (2009)
[18] Li, K.; Kwong, S.; Cao, J.; Li, M.; Zheng, J.; Shen, R., Achieving balance between proximity and diversity in multi-objective evolutionary algorithm, Information Sciences, 182, 1, 220-242 (2012)
[19] H. Liao, Q. Wu, L. Jiang, Multi-objective optimization by reinforcement learning for power system dispatch and voltage stability, in: 2010 IEEE PES Innovative Smart Grid Technologies Conference Europe (ISGT Europe), IEEE, 2010, pp. 1-8.
[20] M. Liu, J. Zheng, J. Wang, Y. Liu, L. Jiang, An adaptive diversity introduction method for dynamic evolutionary multiobjective optimization, in: 2014 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2014, pp. 3160-3167.
[21] Liu, R.; Li, J.; Mu, C.; Jiao, L., A coevolutionary technique based on multi-swarm particle swarm optimization for dynamic multi-objective optimization, European Journal of Operational Research, 261, 3, 1028-1051 (2017) · Zbl 1403.90611
[22] Liu, R.; Zhang, W.; Jiao, L.; Liu, F.; Ma, J., A sphere-dominance based preference immune-inspired algorithm for dynamic multi-objective optimization, (Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (2010), ACM), 423-430
[23] Muruganantham, A.; Tan, K. C.; Vadakkepat, P., Evolutionary dynamic multiobjective optimization via kalman filter prediction, IEEE Transactions on Cybernetics, 46, 12, 2862-2873 (2015)
[24] Z. Peng, J. Zheng, J. Zou, A population diversity maintaining strategy based on dynamic environment evolutionary model for dynamic multiobjective optimization, in: 2014 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2014, pp. 274-281.
[25] Ruan, G.; Yu, G.; Zheng, J.; Zou, J.; Yang, S., The effect of diversity maintenance on prediction in dynamic multi-objective optimization, Applied Soft Computing, 58, 631-647 (2017)
[26] Ruiz-Montiel, M.; Mandow, L.; Perez-de-la Cruz, J.-L., A temporal difference method for multi-objective reinforcement learning, Neurocomputing, 263, 15-25 (2017)
[27] Samma, H.; Lim, C. P.; Saleh, J. M., A new reinforcement learning-based memetic particle swarm optimizer, Applied Soft Computing, 43, 276-297 (2016)
[28] J.R. Schott, Fault tolerant design using single and multicriteria genetic algorithm optimization. Technical report, Air Force Inst of Tech Wright-Patterson AFB OH, 1995.
[29] Schwartz, A., A reinforcement learning method for maximizing undiscounted rewards, Proceedings of the Tenth International Conference on Machine Learning, 298, 298-305 (1993)
[30] Shang, R.; Jiao, L.; Ren, Y.; Li, L.; Wang, L., Quantum immune clonal coevolutionary algorithm for dynamic multiobjective optimization, Soft Computing, 18, 4, 743-756 (2014) · Zbl 1331.68212
[31] Shen, X.-N.; Minku, L. L.; Marturi, N.; Guo, Y.-N.; Han, Y., A Q-learning-based memetic algorithm for multi-objective dynamic software project scheduling, Information Sciences, 428, 1-29 (2018)
[32] K. Sindhya, Hybrid evolutionary multi-objective optimization with enhanced convergence and diversity. Jyväskylä Studies in Computing 131 (2011). · Zbl 1251.90358
[33] Singh, S.; Jaakkola, T.; Littman, M. L.; Szepesvári, C., Convergence results for single-step on-policy reinforcement-learning algorithms, Machine Learning, 38, 3, 287-308 (2000) · Zbl 0954.68127
[34] Sutton, R. S., Learning to predict by the methods of temporal differences, Machine Learning, 3, 1, 9-44 (1988)
[35] Sutton, R. S.; Barto, A. G., Reinforcement Learning: An Introduction (2018), MIT press · Zbl 1407.68009
[36] G. Tesauro, Practical issues in temporal difference learning, in: Advances in Neural Information Processing Systems, 1992, pp. 259-266. · Zbl 0772.68075
[37] Y. Wang, B. Li, Investigation of memory-based multi-objective optimization evolutionary algorithm in dynamic environment, in: 2009 IEEE Congress on Evolutionary Computation, IEEE, 2009, pp. 630-637.
[38] Watkins, C. J.; Dayan, P., Q-learning. Machine Learning, 8, 3-4, 279-292 (1992) · Zbl 0773.68062
[39] Woldesenbet, Y. G.; Yen, G. G., Dynamic evolutionary algorithm with variable relocation, IEEE Transactions on Evolutionary Computation, 13, 3, 500-513 (2009)
[40] Wu, Y.; Jin, Y.; Liu, X., A directed search strategy for evolutionary dynamic multiobjective optimization, Soft Computing, 19, 11, 3221-3235 (2015)
[41] Zhang, J.; Zhan, Z.-H.; Lin, Y.; Chen, N.; Gong, Y.-J.; Zhong, J.-H.; Chung, H. S.; Li, Y.; Shi, Y.-H., Evolutionary computation meets machine learning: A survey, IEEE Computational Intelligence Magazine, 6, 4, 68-75 (2011)
[42] Zhang, X.; Tian, Y.; Jin, Y., A knee point-driven evolutionary algorithm for many-objective optimization, IEEE Transactions on Evolutionary Computation, 19, 6, 761-776 (2014)
[43] Zhang, Z., Multiobjective optimization immune algorithm in dynamic environments and its application to greenhouse control, Applied Soft Computing, 8, 2, 959-971 (2008)
[44] Zhou, A.; Jin, Y.; Zhang, Q., A population prediction strategy for evolutionary dynamic multiobjective optimization, IEEE Transactions on Cybernetics, 44, 1, 40-53 (2014)
[45] A. Zhou, Y. Jin, Q. Zhang, B. Sendhoff, E. Tsang, Prediction-based population re-initialization for evolutionary dynamic multi-objective optimization, in: International Conference on Evolutionary Multi-Criterion Optimization, Springer, 2007, pp. 832-846.
[46] E. Zitzler, S. Künzli, Indicator-based selection in multiobjective search, in: International Conference on Parallel Problem Solving from Nature, Springer, 2004, pp. 832-842.
[47] Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, C. M.; Da Fonseca, V. G., Performance assessment of multiobjective optimizers: An analysis and review, IEEE Transactions on Evolutionary Computation, 7, 2, 117-132 (2003)
[48] Zou, F.; Yen, G. G.; Tang, L., A knee-guided prediction approach for dynamic multi-objective optimization, Information Sciences, 509, 193-209 (2020)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.