Application of population evolvability in a hyper-heuristic for dynamic multi-objective optimization

    Teodoro Macias-Escobar   Affiliation
    ; Laura Cruz-Reyes   Affiliation
    ; Bernabé Dorronsoro   Affiliation
    ; Héctor Fraire-Huacuja   Affiliation
    ; Nelson Rangel-Valdez   Affiliation
    ; Claudia Gómez-Santillán   Affiliation


It is important to know the properties of an optimization problem and the difficulty an algorithm faces to solve it. Population evolvability obtains information related to both elements by analysing the probability of an algorithm to improve current solutions and the degree of those improvements. DPEM_HH is a dynamic multi-objective hyper-heuristic that uses low-level heuristic (LLH) selection methods that apply population evolvability. DPEM_HH uses dynamic multiobjective evolutionary algorithms (DMOEAs) as LLHs to solve dynamic multi-objective optimization problems (DMOPs). Population evolvability is incorporated in DPEM_HH by calculating it on each candidate DMOEA for a set of sampled generations after a change is detected, using those values to select which LLH will be applied. DPEM_HH is tested on multiple DMOPs with dynamic properties that provide several challenges. Experimental results show that DPEM_HH with a greedy LLH selection method that uses average population evolvability values can produce solutions closer to the Pareto optimal front with equal to or better diversity than previously proposed heuristics. This shows the effectiveness and feasibility of the application of population evolvability on hyperheuristics to solve dynamic optimization problems.

First published online 12 July 2019

Keyword : population evolvability, hyper-heuristic, dynamic multi-objective optimization, dynamic multi-objective evolutionary algorithm, fitness landscape analysis, DNSGA-II

How to Cite
Macias-Escobar, T., Cruz-Reyes, L., Dorronsoro, B., Fraire-Huacuja, H., Rangel-Valdez, N., & Gómez-Santillán, C. (2019). Application of population evolvability in a hyper-heuristic for dynamic multi-objective optimization. Technological and Economic Development of Economy, 25(5), 951-978.
Published in Issue
Jul 12, 2019
Abstract Views
PDF Downloads
Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.


Agrawal, R. B., & Deb, K. (1994). Simulated binary crossover for continuous search space. Complex Systems, 9(3), 1–15.

Altenberg, L. (1994). The evolution of evolvability in genetic programming. Advances in genetic programming, 3, 47–74.

Azzouz, R., Bechikh, S., & Said, L. B. (2017a). Dynamic multi-objective optimization using evolutionary algorithms: a survey. In Recent Advances in Evolutionary Multi-objective Optimization (pp. 31-70). Cham: Springer.

Azzouz, R., Bechikh, S., & Said, L. B. (2017b). A dynamic multi-objective evolutionary algorithm using a change severity-based adaptive population management strategy. Soft Computing, 21(4), 885-906.

Ayob, M., & Kendall, G. (2003). A monte carlo hyper-heuristic to optimise component placement sequencing for multi head placement machine. In Proceedings of the international conference on intelligent technologies (Vol. 3, pp. 132-141). InTech.

Bai, R., & Kendall, G. (2005). An investigation of automated planograms using a simulated annealing based hyper-heuristic. In Metaheuristics: Progress as real problem solvers (pp. 87-108). Boston, MA: Springer.

Baykasoğlu, A., & Ozsoydan, F. B. (2017). Evolutionary and population–based methods versus constructive search strategies in dynamic combinatorial optimization. Information Sciences, 420, 159183.

Bilgin, B., Özcan, E., & Korkmaz, E. E. (2006, August). An experimental study on hyper-heuristics and exam timetabling. In International Conference on the Practice and Theory of Automated Timetabling (pp. 394-412). Berlin, Heidelberg: Springer.

Branke, J. (2001). Evolutionary optimization in dynamic environments. Norwell, MA, USA: Kluwer Academic Publishers.

Brockhoff, D., Friedrich, T., Hebbinghaus, N., Klein, C., Neumann, F., & Zitzler, E. (2007, July). Do additional objectives make a problem harder?. In Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation (pp. 765-772). ACM.

Burke, E. K., & Bykov, Y. (2008, August). A late acceptance strategy in hill-climbing for exam timetabling problems. In Practice and Theory of Automated Timetabling (PATAT 2008). Conference, Montreal, Canada. Retrieved from

Burke, E. K., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., & Woodward, J. R. (2010). A classification of hyper-heuristic approaches. In Handbook of metaheuristics (pp. 449-468). Springer US.

Burke, E. K., Silva, J. D. L., & Soubeiga, E. (2005). Multi-objective hyper-heuristic approaches for space allocation and timetabling. In Metaheuristics: Progress as Real Problem Solvers (pp. 129-158). Boston, MA: Springer.

Chen, R., & Zeng, W. (2011, August). Multi-objective optimization in dynamic environment: A review. In Computer Science & Education (ICCSE), 2011 6th International Conference on (pp. 78-82). IEEE.

Cowling, P., Kendall, G., & Soubeiga, E. (2000, August). A hyperheuristic approach to scheduling a sales summit. In International Conference on the Practice and Theory of Automated Timetabling (pp. 176-190). Berlin, Heidelberg: Springer.

Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. A. M. T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA–II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.

Deb, K., Rao, N. U. B., & Karthik, S. (2007). 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 (pp. 803-817). Berlin, Heidelberg: Springer.

Deb, K., Thiele, L., Laumanns, M., & Zitzler, E. (2002, May). Scalable multi-objective optimization test problems. In Evolutionary Computation, 2002. CEC’02. Proceedings of the 2002 Congress on (Vol. 1, pp. 825-830). IEEE.

Dowsland, K. A., Soubeiga, E., & Burke, E. (2007). A simulated annealing based hyperheuristic for determining shipper sizes for storage and transportation. European Journal of Operational Research, 179(3), 759-774.

Dueck, G. (1993). New optimization heuristics. Journal of Computational Physics, 104(1), 86-92.

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.

Furtuna, R., Curteanu, S., & Leon, F. (2012). Multi-objective optimization of a stacked neural network using an evolutionary hyper-heuristic. Applied Soft Computing, 12(1), 133-144.

García, R. (2010). Hiper–heurístico para Resolver el Problema de Cartera de Proyectos Sociales (MSc Thesis). Instituto Tecnológico de Ciudad Madero, Ciudad Madero, Mexico.

Goh, C. K., & Tan, K. C. (2007). An investigation on noisy environments in evolutionary multiobjective optimization. IEEE Transactions on Evolutionary Computation, 11(3), 354-381.

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.

Hatzakis, I., & Wallace, D. (2006, July). Dynamic multi-objective optimization with evolutionary algorithms: a forward-looking approach. In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation (pp. 1201-1208). ACM.

Helbig, M., & Engelbrecht, A. P. (2014). Benchmarks for dynamic multi-objective optimisation algorithms. ACM Computing Surveys (CSUR), 46(3), 37.

Hodges Jr, J. L., & Lehmann, E. L. (1962). Rank methods for combination of independent experiments in analysis of variance. The Annals of Mathematical Statistics, 33(2), 482-497.

Holm, S. (1979). A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics, 6(2), 65-70.

Huband, S., Hingston, P., Barone, L., & While, L. (2006). A review of multiobjective test problems and a scalable test problem toolkit. IEEE Transactions on Evolutionary Computation, 10(5), 477-506.

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.

Kumari, A. C., Srinivas, K., & Gupta, M. P. (2013, February). Software module clustering using a hyperheuristic based multi-objective genetic algorithm. In Advance Computing Conference (IACC), 2013 IEEE 3rd International (pp. 813-818). IEEE.

Li, H., & Deb, K. (2017, June). Challenges for evolutionary multiobjective optimization algorithms in solving variable–length problems. In Evolutionary Computation (CEC), 2017 IEEE Congress on (pp. 2217–2224). IEEE.

Li, W., Özcan, E., & John, R. (2017). Multi-objective evolutionary algorithms and hyper-heuristics for wind farm layout optimisation. Renewable Energy, 105, 473-482.

Liao, X., Li, Q., Yang, X., Zhang, W., & Li, W. (2008). Multiobjective optimization for crash safety design of vehicles using stepwise regression model. Structural and multidisciplinary optimization, 35(6), 561-569.

Liu, C. A. (2010, June). New dynamic multiobjective evolutionary algorithm with core estimation of distribution. In 2010 International Conference on Electrical and Control Engineering (pp. 1345-1348). IEEE.

Liu, C. A., & Wang, Y. (2006, September). New evolutionary algorithm for dynamic multiobjective optimization problems. In International Conference on Natural Computation (pp. 889-892). Berlin, Heidelberg: Springer.

Maashi, M., Özcan, E., & Kendall, G. (2014). A multi-objective hyper-heuristic based on choice function. Expert Systems with Applications, 41(9), 4475-4493.

Maashi, M., Kendall, G., & Özcan, E. (2015). Choice function based hyper-heuristics for multi-objective optimization. Applied Soft Computing, 28, 312-326.

McClymont, K., & Keedwell, E. C. (2011, July). Markov chain hyper-heuristic (MCHH): an online selective hyper-heuristic for multi-objective continuous problems. In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation (pp. 2003-2010). ACM.

Nguyen, S., Zhang, M., Johnston, M., & Tan, K. C. (2014). Automatic design of scheduling policies for dynamic multi-objective job shop scheduling via cooperative coevolution genetic programming. IEEE Transactions on Evolutionary Computation, 18(2), 193–208.

Richter, H. (2013). Dynamic fitness landscape analysis. In Evolutionary computation for dynamic optimization problems (pp. 269-297). Berlin, Heidelberg: Springer.

Roy, S., & Chakraborty, U. (2013). Introduction to soft computing: neuro-fuzzy and genetic algorithms. Dorling Kindersley.

Santiago, A., Dorronsoro, B., Nebro, A. J., Durillo, J. J., Castillo, O., & Fraire, H. J. (2019). A novel multiobjective evolutionary algorithm with fuzzy logic based adaptive selection of operators: FAME. Information Sciences, 471, 233-251.

Sierra, M. R., & Coello, C. A. C. (2005, March). Improving PSO–based multi-objective optimization using crowding, mutation and∈– dominance. In International Conference on Evolutionary Multi– Criterion Optimization (pp. 505–519). Berlin, Heidelberg: Springer.

Smith, T., Husbands, P., & O’Shea, M. (2002). Fitness landscapes and evolvability. Evolutionary computation, 10(1), 1-34.

Soria-Alcaraz, J. A., Espinal, A., & Sotelo-Figueroa, M. A. (2017). Evolvability metric estimation by a parallel perceptron for on-line selection hyper-heuristics. IEEE Access, 5, 7055-7063.

Soria-Alcaraz, J. A., Ochoa, G., Sotelo-Figeroa, M. A., & Burke, E. K. (2017). A methodology for determining an effective subset of heuristics in selection hyper-heuristics. European Journal of Operational Research, 260(3), 972-983.

Tan, K. C., Lee, T. H., & Khor, E. F. (2002). Evolutionary algorithms for multi-objective optimization: Performance assessments and comparisons. Artificial Intelligence Review, 17(4), 251-290.

Topcuoglu, H. R., Ucar, A., & Altin, L. (2014). A hyper-heuristic based framework for dynamic optimization problems. Applied Soft Computing, 19, 236-251.

Van Veldhuizen, D. A. (1999). Multiobjective evolutionary algorithms: classifications, analyses, and new innovations (PhD thesis). Air Force Institute of Technology, Alabama, USA.

Vázquez-Rodríguez, J. A., & Petrovic, S. (2012). Calibrating continuous multi-objective heuristics using mixture experiments. Journal of Heuristics, 18(5), 699-726.

Vrugt, J. A., & Robinson, B. A. (2007). Improved evolutionary optimization from genetically adaptive multimethod search. Proceedings of the National Academy of Sciences, 104(3), 708-711.

Wang, Y., & Li, B. (2009, May). Investigation of memory-based multi-objective optimization evolutionary algorithm in dynamic environment. In Evolutionary Computation, 2009. CEC’09. IEEE Congress on (pp. 630-637). IEEE.

Wang, Y., & Li, B. (2010). Multi–strategy ensemble evolutionary algorithm for dynamic multi-objective optimization. Memetic Computing, 2(1), 3-24.

Wang, M., Li, B., Zhang, G., & Yao, X. (2017). Population Evolvability: Dynamic Fitness Landscape Analysis for Population–based Metaheuristic Algorithms. IEEE Transactions on Evolutionary Computation.

Wang, H., Wang, D., & Yang, S. (2009). A memetic algorithm with adaptive hill climbing strategy for dynamic optimization problems. Soft Computing, 13(8-9), 763-780.

Zamli, K. Z., Din, F., Kendall, G., & Ahmed, B. S. (2017). An experimental study of hyper-heuristic selection and acceptance mechanism for combinatorial t–way test suite generation. Information Sciences, 399, 121-153.

Zhang, Q., Zhou, A., & Jin, Y. (2008). RM-MEDA: A regularity model-based multiobjective estimation of distribution algorithm. IEEE Transactions on Evolutionary Computation, 12(1), 41-63.

Zhou, A., Jin, Y., & Zhang, Q. (2014). A population prediction strategy for evolutionary dynamic multiobjective optimization. IEEE transactions on cybernetics, 44(1), 40-53.