Evolutionary Algorithms for Dynamic Environments: Prediction using Linear Regression and Markov Chains

Authors

Abstract

In this work we investigate the use of prediction mechanisms in Evolutionary Algorithms for dynamic environments. These mechanisms, linear regression and Markov chains, are used to estimate the generation when a change in the environment will occur, and also to predict to which state (or states) the environment may change, respectively.
Different types of environmental changes were studied. A memory-based evolutionary algorithm empowered by these two techniques was successfully applied to several instances of the dynamic bit matching problem.

Keywords

Evolutioary Computation, Dynamic environments, prediction, linear regression, Markov chains

Subject

Evolutionary Optimization

Conference

PPSN X, September 2008

Cited by

Year 2015 : 4 citations

Li, C., Nguyen, T. T., Yang, M., Yang, S., & Zeng, S. (2015). Multi-population methods in unconstrained continuous dynamic environments: The challenges. Information Sciences, 296, 95-118.

Filipiak, P., & Lipinski, P. (2015). Making IDEA-ARIMA efficient in dynamic constrained optimization problems. In Applications of Evolutionary Computation (pp. 882-893). Springer International Publishing.

Bravo, Y., Luque, G., & Alba, E. (2015). Global memory schemes for dynamic optimization. Natural Computing, 1-15.

Chen, X., Zhang, D., & Zeng, X. (2015, November). A Stable Matching-Based Selection and Memory Enhanced MOEA/D for Evolutionary Dynamic Multiobjective Optimization. In Tools with Artificial Intelligence (ICTAI), 2015 IEEE 27th International Conference on (pp. 478-485). IEEE.

Year 2014 : 5 citations

Li, C., Yang, S., & Yang, M. (2014). An adaptive multi-swarm optimizer for dynamic optimization problems.

Li, C., Nguyen, T. T., Yang, M., Yang, S., & Zeng, S. (2014). Multi-population methods in unconstrained continuous dynamic environments: the challenges.Information Sciences.

Richter, H. (2014). Fitness Landscapes That Depend on Time. In Recent Advances in the Theory and Application of Fitness Landscapes (pp. 265-299). Springer Berlin Heidelberg.

Filipiak, P., & Lipinski, P. (2014). Infeasibility Driven Evolutionary Algorithm with Feed-Forward Prediction Strategy for Dynamic Constrained Optimization Problems. In Applications of Evolutionary Computation (pp. 817-828). Springer Berlin Heidelberg.

Mukherjee, R., Patra, G. R., Kundu, R., & Das, S. (2014). Cluster-based differential evolution with Crowding Archive for niching in dynamic environments. Information Sciences, 267, 58-82.

Year 2013 : 9 citations

Shengxiang Yang, Yong Jiang, and Trung Thanh Nguyen (2013). Metaheuristics for dynamic combinatorial optimization problems. IMA Journal of Management Mathematics, 2013.

Hajer Ben-Romdhane, Enrique Alba, and Saoussen Krichen (2013). Best practices in measuring algorithm performance for dynamic optimization problems. Soft Computing, pp. 1-13, Springer, 2013.

Hendrik Richter and Shengxiang Yang (2013). Dynamic Optimization Using Analytic and Evolutionary Approaches: A Comparative Review. Zelinka et al. (Eds.): Handbook of Optimization, ISRL 38, pp. 1–28, Springer, 2013.

Danial Yazdani, Babak Nasiri, Alireza Sepas-Moghaddam, and Mohammad Reza Meybodi (2013). A novel multi-swarm algorithm for optimization in dynamic environments based on particle swarm optimization. Applied Soft Computing, Elsevier, 2013.

Trung Thanh Nguyen, Shengxiang Yang, Juergen Branke, Xin Yao (2013). Evolutionary Dynamic Optimization: Methodologies. Evolutionary Computation for Dynamic Optimization Problems, Studies in Computational Intelligence Volume 490, pp 39-64, Springer 2013

S Yang, TT Nguyen, C Li (2013). Evolutionary Dynamic Optimization: Test and Evaluation Environments. Studies in Computational Intelligence, Volume 490, pp. 3-37, Springer 2013.

Enrique Alba, H. Ben-Romdhane, S. Krichen, B. Sarasola (2013). BIPOP: A New Algorithm with Explicit Exploration/Exploitation Control for Dynamic Optimization Problems" Evolutionary Computation for Dynamic Optimization Problems, pp. 171-191, Springer Berlin Heidelberg, 2013.

Wang, H., & Yang, S. (2013). Memetic Algorithms for Dynamic Optimization Problems. In Evolutionary Computation for Dynamic Optimization Problems (pp. 137-170). Springer Berlin Heidelberg.

Uluda?, G., Kiraz, B., Etaner-Uyar, A. ?., & Özcan, E. (2013). A hybrid multi-population framework for dynamic environments combining online and offline learning. Soft Computing, 17(12), 2327-2348.

Year 2012 : 5 citations

Hendrik Richter and Shengxiang Yang (2012). Dynamic Optimization Using Analytic and Evolutionary Approaches: A Comparative Review. Zelinka et al. (Eds.): Handbook of Optimization, ISRL 38, pp. 1–28, Springer 2012.

C. Li, S. Yang, M. Yang (2012). Maintaining diversity by clustering in dynamic environments. 2012 IEEE Congress on Evolutionary Computation (CEC), pp. 1-8, IEEE 2012.

T. T. Nguyen, S. Yang, and J. Branke (2012). “Evolutionary dynamic optimization: A survey of the state of the art”. Swarm and Evolutionary Computation, Elsevier, 2012.

Changhe Li, Shengxiang Yang. A general framework of multipopulation methods with clustering in undetectable dynamic environments. IEEE Transactions on Evolutionary Computation, 16(4), pp. 556-577, IEEE, 2012.

Shengxiang Yang, Yong Jiang, and Trung Thanh Nguyen (2012). "Metaheuristics for dynamic combinatorial optimization problems." IMA Journal of Management Mathematics, 2012.

Year 2011 : 5 citations

Hendrik Richter, Franz Dietel (2011), “Solving Dynamic Constrained Optimization Problems with Asynchronous Change Pattern”. In C. Di Chio et al. (Eds.): EvoApplications 2011, Part I, LNCS 6624, pp. 334-343, Springer-Verlag Berlin Heidelberg 2011, Torino, Italy, 27-29 April 2011.

J. Lepagnot, A. Nakib, H. Oulhadj, P. Siarry (2011). “Brain cine MRI segmentation based on a multiagent algorithm for dynamic continuous optimization”. 2011 IEEE Congress on Evolutionary Computation, pp. 1695-1702, IEEE, 2011.

C. Li and S. Yang (2011). A general framework of multi-population methods with clustering in undetectable dynamic environments. IEEE Transactions on Evolutionary Computation, September 2011. IEEE Press.

Li Chen, Lixin Ding, Xin Du (2011). Genetic algorithm with Particle Filter for dynamic optimization problems. 3rd International Conference on Computer Research and Development (ICCRD), 2011, pp. 452- 457, IEEE 2011.

Chen Li (2011). Dynamic Optimization Algorithms. Journal of Wuhan University: Natural Science, 2011.

Year 2010 : 2 citations

H. Richter (2010). "Evolutionary Optimization and Dynamic Fitness Landscapes?. Evolutionary Algorithms and Chaotic Systems, Studies in Computational Intelligence, Vol. 267/2010, pp. 409-446, Springer, 2010.

H. Richter (2010). Memory Design for Constrained Dynamic Optimization Problems. C. Di Chio et al. (Eds.): EvoApplications 2010, Part I, LNCS 6024, pp. 552"561, Springer-Verlag Berlin Heidelberg, 2010.