Share:


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

Abstract

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. https://doi.org/10.3846/tede.2019.10291
Published in Issue
Jul 12, 2019
Abstract Views
154
PDF Downloads
86
Creative Commons License

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

References

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. https://doi.org/10.1007/978-3-319-42978-6_2

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. https://doi.org/10.1007/s00500-015-1820-4

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. https://doi.org/10.1007/0-387-25383-1_4

Baykasoğlu, A., & Ozsoydan, F. B. (2017). Evolutionary and population–based methods versus constructive search strategies in dynamic combinatorial optimization. Information Sciences, 420, 159183. https://doi.org/10.1016/j.ins.2017.08.058

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. https://doi.org/10.1007/978-3-540-77345-0_25

Branke, J. (2001). Evolutionary optimization in dynamic environments. Norwell, MA, USA: Kluwer Academic Publishers. https://doi.org/10.1007/978-1-4615-0911-0_2

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. https://doi.org/10.1145/1276958.1277114

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 https://www.patatconference.org/patat2008/proceedings/BykovHC2a.pdf

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. https://doi.org/10.1007/978-1-4419-1665-5_15

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. https://doi.org/10.1007/0-387-25383-1_6

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. https://doi.org/10.1109/ICCSE.2011.6028589

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. https://doi.org/10.1007/3-540-44629-X_11

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. https://doi.org/10.1109/4235.996017

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. https://doi.org/10.1007/978-3-540-70928-2_60

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. https://doi.org/10.1016/j.ejor.2005.03.058

Dueck, G. (1993). New optimization heuristics. Journal of Computational Physics, 104(1), 86-92. https://doi.org/10.1006/jcph.1993.1010

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

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. https://doi.org/10.1016/j.asoc.2011.09.001

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. https://doi.org/10.1109/TEVC.2006.882428

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

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. https://doi.org/10.1145/1143997.1144187

Helbig, M., & Engelbrecht, A. P. (2014). Benchmarks for dynamic multi-objective optimisation algorithms. ACM Computing Surveys (CSUR), 46(3), 37. https://doi.org/10.1145/2517649

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. https://doi.org/10.1214/aoms/1177704575

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. https://doi.org/10.1109/TEVC.2005.861417

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

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. https://doi.org/10.1109/IAdCC.2013.6514331

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. https://doi.org/10.1109/CEC.2017.7969573

Li, W., Özcan, E., & John, R. (2017). Multi-objective evolutionary algorithms and hyper-heuristics for wind farm layout optimisation. Renewable Energy, 105, 473-482. https://doi.org/10.1016/j.renene.2016.12.022

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. https://doi.org/10.1007/s00158-007-0163-x

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. https://doi.org/10.1109/icece.2010.334

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. https://doi.org/10.1007/11881070_117

Maashi, M., Özcan, E., & Kendall, G. (2014). A multi-objective hyper-heuristic based on choice function. Expert Systems with Applications, 41(9), 4475-4493. https://doi.org/10.1016/j.eswa.2013.12.050

Maashi, M., Kendall, G., & Özcan, E. (2015). Choice function based hyper-heuristics for multi-objective optimization. Applied Soft Computing, 28, 312-326. https://doi.org/10.1016/j.asoc.2014.12.012

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. https://doi.org/10.1145/2001576.2001845

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. https://doi.org/10.1109/TEVC.2013.2248159

Richter, H. (2013). Dynamic fitness landscape analysis. In Evolutionary computation for dynamic optimization problems (pp. 269-297). Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-38416-5_11

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. https://doi.org/10.1016/j.ins.2018.09.005

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. https://doi.org/10.1007/978-3-540-31880-4_35

Smith, T., Husbands, P., & O’Shea, M. (2002). Fitness landscapes and evolvability. Evolutionary computation, 10(1), 1-34. https://doi.org/10.1162/106365602317301754

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. https://doi.org/10.1109/ACCESS.2017.2699426

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. https://doi.org/10.1016/j.ejor.2017.01.042

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. https://doi.org/10.1023/A:1015516501242

Topcuoglu, H. R., Ucar, A., & Altin, L. (2014). A hyper-heuristic based framework for dynamic optimization problems. Applied Soft Computing, 19, 236-251. https://doi.org/10.1016/j.asoc.2014.01.037

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

Vázquez-Rodríguez, J. A., & Petrovic, S. (2012). Calibrating continuous multi-objective heuristics using mixture experiments. Journal of Heuristics, 18(5), 699-726. https://doi.org/10.1007/s10732-012-9204-8

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. https://doi.org/10.1073/pnas.0610471104

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. https://doi.org/10.1109/CEC.2009.4983004

Wang, Y., & Li, B. (2010). Multi–strategy ensemble evolutionary algorithm for dynamic multi-objective optimization. Memetic Computing, 2(1), 3-24. https://doi.org/10.1007/s12293-009-0012-0

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. https://doi.org/10.1109/TEVC.2017.2744324

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. https://doi.org/10.1007/s00500-008-0347-3

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. https://doi.org/10.1016/j.ins.2017.03.007

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. https://doi.org/10.1109/TEVC.2007.894202

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