Application of population evolvability in a hyper-heuristic for dynamic multi-objective optimization
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
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
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