1. Home
  2. Vol 7, No 4 (2023)
  3. Pietropolli

A Genetic Programming Based Heuristic to Simplify Rugged Landscapes Exploration

Gloria Pietropolli, Giuliamaria Menara, Mauro Castelli

Abstract


Some optimization problems are difficult to solve due to a considerable number of local optima, which may result in premature convergence of the optimization process. To address this problem, we propose a novel heuristic method for constructing a smooth surrogate model of the original function. The surrogate function is easier to optimize but maintains a fundamental property of the original rugged fitness landscape: the location of the global optimum. To create such a surrogate model, we consider a linear genetic programming approach coupled with a self-tuning fitness function. More specifically, to evaluate the fitness of the produced surrogate functions, we employ Fuzzy Self-Tuning Particle Swarm Optimization, a setting-free version of particle swarm optimization. To assess the performance of the proposed method, we considered a set of benchmark functions characterized by high noise and ruggedness. Moreover, the method is evaluated over different problems’ dimensionalities. The proposed approach reveals its suitability for performing the proposed task. In particular, experimental results confirm its capability to find the global argminimum for all the considered benchmark problems and all the domain dimensions taken into account, thus providing an innovative and promising strategy for dealing with challenging optimization problems.

 

Doi: 10.28991/ESJ-2023-07-04-01

Full Text: PDF


Keywords


Genetic Programming; Particle Swarm Optimization; Surrogate Models; Fitness Landscapes.

References


Peres, F., & Castelli, M. (2021). Combinatorial optimization problems and metaheuristics: Review, challenges, design, and development. Applied Sciences (Switzerland), 11(14), 6449. doi:10.3390/app11146449.

Stadler, P.F. (2002). Fitness landscapes. Biological Evolution and Statistical Physics. Lecture Notes in Physics, 585, Springer, Berlin, Germany. doi:10.1007/3-540-45692-9_10.

Merz, P. (2004). Advanced fitness landscape analysis and the performance of memetic algorithms. Evolutionary Computation, 12(3), 303–325. doi:10.1162/1063656041774956.

Richter, H. (2013). Dynamic Fitness Landscape Analysis. Evolutionary Computation for Dynamic Optimization Problems. Studies in Computational Intelligence, 490. Springer, Berlin, Germany. doi:10.1007/978-3-642-38416-5_11.

Tan, Z., Li, K., & Wang, Y. (2021). Differential evolution with adaptive mutation strategy based on fitness landscape analysis. Information Sciences, 549, 142–163. doi:10.1016/j.ins.2020.11.023.

Vanneschi, L., Castelli, M., & Manzoni, L. (2011). The K landscapes. Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation. doi:10.1145/2001576.2001773.

Horn, J., & Goldberg, D. E. (1995). Genetic Algorithm Difficulty and the Modality of Fitness Landscapes. Foundations of genetic algorithms, Elsevier, Amsterdam, Netherlands. doi:10.1016/b978-1-55860-356-1.50016-9.

Zou, F., Chen, D., Liu, H., Cao, S., Ji, X., & Zhang, Y. (2022). A survey of fitness landscape analysis for optimization. Neurocomputing, 503, 129–139. doi:10.1016/j.neucom.2022.06.084.

Li, W., Li, S., Chen, Z., Zhong, L., & Ouyang, C. (2019). Self-feedback differential evolution adapting to fitness landscape characteristics. Soft Computing, 23(4), 1151–1163. doi:10.1007/s00500-017-2833-y.

Jin, Y. (2011). Surrogate-assisted evolutionary computation: Recent advances and future challenges. Swarm and Evolutionary Computation, 1(2), 61–70. doi:10.1016/j.swevo.2011.05.001.

Eason, J., & Cremaschi, S. (2014). Adaptive sequential sampling for surrogate model generation with artificial neural networks. Computers and Chemical Engineering, 68, 220–232. doi:10.1016/j.compchemeng.2014.05.021.

Lew, T. L., Spencer, A. B., Scarpa, F., Worden, K., Rutherford, A., & Hemez, F. (2006). Identification of response surface models using genetic programming. Mechanical Systems and Signal Processing, 20(8), 1819–1831. doi:10.1016/j.ymssp.2005.12.003.

Zhou, Z., Ong, Y. S., Nair, P. B., Keane, A. J., & Lum, K. Y. (2007). Combining global and local surrogate models to accelerate evolutionary optimization. IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews, 37(1), 66–76. doi:10.1109/TSMCC.2005.855506.

Manzoni, L., Papetti, D. M., Cazzaniga, P., Spolaor, S., Mauri, G., Besozzi, D., & Nobile, M. S. (2020). Surfing on fitness landscapes: A boost on optimization by Fourier surrogate modeling. Entropy, 22(3), 285. doi:10.3390/e22030285.

Koza, J. R. (1994). Genetic programming as a means for programming computers by natural selection. Statistics and Computing, 4(2), 87–112. doi:10.1007/BF00175355.

Talbi, E. G. (2009). Metaheuristics: From Design to Implementation. Metaheuristics: From Design to Implementation. John Wiley & Sons, Hoboken, United States. doi:10.1002/9780470496916.

Nobile, M. S., Cazzaniga, P., Besozzi, D., Colombo, R., Mauri, G., & Pasi, G. (2018). Fuzzy Self-Tuning PSO: A settings-free algorithm for global optimization. Swarm and Evolutionary Computation, 39, 70–85. doi:10.1016/j.swevo.2017.09.001.

Vanneschi, L., Castelli, M., & Silva, S. (2014). A survey of semantic methods in genetic programming. Genetic Programming and Evolvable Machines, 15(2), 195–214. doi:10.1007/s10710-013-9210-0.

Pan, J. S., Hu, P., Snášel, V., & Chu, S. C. (2022). A survey on binary metaheuristic algorithms and their engineering applications. Artificial Intelligence Review, 1–67. doi:10.1007/s10462-022-10328-9.

Lagaros, N. D., Kournoutos, M., Kallioras, N. A., & Nordas, A. N. (2023). Constraint handling techniques for metaheuristics: a state-of-the-art review and new variants. Optimization and Engineering, 1–48. doi:10.1007/s11081-022-09782-9.

Lin, M. H., Tsai, J. F., & Yu, C. S. (2012). A review of deterministic optimization methods in engineering and management. Mathematical Problems in Engineering, 2012. doi:10.1155/2012/756023.

Sörensen, K., Sevaux, M., & Glover, F. (2018). A History of Metaheuristics. Handbook of Heuristics. Springer, Cham, Switzerland. doi:10.1007/978-3-319-07124-4_4.

Papila, N., Shyy, W., Griffin, L., & Dorney, D. J. (2002). Shape optimization of supersonic turbines using global approximation methods. Journal of Propulsion and Power, 18(3), 509–518. doi:10.2514/2.5991.

Feng, X. T., Chen, B. R., Yang, C., Zhou, H., & Ding, X. (2006). Identification of visco-elastic models for rocks using genetic programming coupled with the modified particle swarm optimization algorithm. International Journal of Rock Mechanics and Mining Sciences, 43(5), 789–801. doi:10.1016/j.ijrmms.2005.12.010.

Poli, R., Langdon, W.B., Holland, O. (2005). Extending Particle Swarm Optimisation via Genetic Programming. Genetic Programming. EuroGP 2005, Lecture Notes in Computer Science, 3447, Springer, Berlin, Germany. doi:10.1007/978-3-540-31989-4_26.

Kanemasa, M., & Aiyoshi, E. (2014). Algorithm tuners for PSO methods and genetic programming techniques for learning tuning rules. IEEJ Transactions on Electrical and Electronic Engineering, 9(4), 407–414. doi:10.1002/tee.21986.

Cavazzuti, M. (2017). Deterministic Optimization. In Stochastic Process Optimization using Aspen Plus®. CRC Press, Boca Raton, United States. doi:10.1201/9781315155739-2.

Bhosekar, A., & Ierapetritou, M. (2018). Advances in surrogate based modeling, feasibility analysis, and optimization: A review. Computers and Chemical Engineering, 108, 250–267. doi:10.1016/j.compchemeng.2017.09.017.

Emmerich, M., Giotis, A., Özdemir, M., Bäck, T., Giannakoglou, K. (2002). Metamodel—Assisted Evolution Strategies. Parallel Problem Solving from Nature — PPSN VII, PPSN 2002, Lecture Notes in Computer Science, 2439. Springer, Berlin, Germany. doi:10.1007/3-540-45712-7_35.

Ulmer, H., Streichert, F., & Zell, A. (n.d.). Evolution strategies assisted by Gaussian processes with improved preselection criterion. The 2003 Congress on Evolutionary Computation, 2003. CEC’03. doi:10.1109/cec.2003.1299643.

Booker, A.J., Dennis, J.E., Frank, P.D., Serafini, D.B., & Torczon, V. (1998). Optimization Using Surrogate Objectives on a Helicopter Test Example. Computational Methods for Optimal Design and Control. Progress in Systems and Control Theory, 24. Birkhäuser, Boston, United States. doi:10.1007/978-1-4612-1780-0_3.

Knill, D. L., Giunta, A. A., Baker, C. A., Grossman, B., Mason, W. H., Haftka, R. T., & Watson, L. T. (1999). Response surface models combining linear and euler aerodynamics for supersonic transport design. Journal of Aircraft, 36(1), 75–86. doi:10.2514/2.2415.

Rai, M., Madavan, N., & Huber, F. (2000). Improving the unsteady aerodynamic performance of transonic turbines using neural networks. 38th Aerospace Sciences Meeting and Exhibit. doi:10.2514/6.2000-169.

Madsen, J. I., Shyy, W., & Haftka, R. T. (2000). Response surface techniques for diffuser shape optimization. AIAA Journal, 38, 1512–1518. doi:10.2514/3.14576.

Donoho, D. L. (2000). High-dimensional data analysis: The curses and blessings of dimensionality. AMS math challenges lecture, 1(2000), 32.

Giannakoglou, K. C. (2002). Design of optimal aerodynamic shapes using stochastic optimization methods and computational intelligence. Progress in Aerospace Sciences, 38(1), 43–76. doi:10.1016/S0376-0421(01)00019-7.

Ong, Y. S., Nair, P. B., & Keane, A. J. (2003). Evolutionary optimization of computationally expensive problems via surrogate modeling. AIAA Journal, 41(4), 687–696. doi:10.2514/2.1999.

Tong, H., Huang, C., Minku, L. L., & Yao, X. (2021). Surrogate models in evolutionary single-objective optimization: A new taxonomy and experimental study. Information Sciences, 562, 414–437. doi:10.1016/j.ins.2021.03.002.

Zhou, Z., Ong, Y. S., Lim, M. H., & Lee, B. S. (2007). Memetic algorithm using multi-surrogates for computationally expensive optimization problems. Soft Computing, 11(10), 957–971. doi:10.1007/s00500-006-0145-8.

Lian, Y., Liou, M. S., & Oyama, A. (2004). An enhanced evolutionary algorithm with a surrogate model. Proceedings of genetic and evolutionary computation conference, 26-30 June, 2004, Seattle, United States.

Kattan, A., & Galvan, E. (2012). Evolving radial basis function networks via GP for estimating fitness values using surrogate models. 2012 IEEE Congress on Evolutionary Computation. doi:10.1109/cec.2012.6256108.

Liu, Q., Wu, X., Lin, Q., Ji, J., & Wong, K. C. (2021). A novel surrogate-assisted evolutionary algorithm with an uncertainty grouping based infill criterion. Swarm and Evolutionary Computation, 60, 100787. doi:10.1016/j.swevo.2020.100787.

Wu, M., Wang, L., Xu, J., Hu, P., & Xu, P. (2022). Adaptive surrogate-assisted multi-objective evolutionary algorithm using an efficient infill technique. Swarm and Evolutionary Computation, 75, 101170. doi:10.1016/j.swevo.2022.101170.

Tang, J., Wang, H., & Xiong, L. (2023). Surrogate-assisted multi-objective optimization via knee-oriented Pareto front estimation. Swarm and Evolutionary Computation, 77, 101252. doi:10.1016/j.swevo.2023.101252.

Holland, J. H. (1992). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT Press, Cambridge, United States. doi:10.7551/mitpress/1090.001.0001.

Kennedy, J., & Eberhart, R. (n.d.). Particle swarm optimization. Proceedings of ICNN’95 - International Conference on Neural Networks. doi:10.1109/icnn.1995.488968.

Zadeh, L. A., Klir, G. J., & Yuan, B. (1996). Fuzzy Sets, Fuzzy Logic, and Fuzzy Systems. Advances in Fuzzy Systems — Applications and Theory, World Scientific Publishing, Singapore. doi:10.1142/2895.

Takagi, T., & Sugeno, M. (1985). Fuzzy Identification of Systems and Its Applications to Modeling and Control. IEEE Transactions on Systems, Man and Cybernetics, SMC-15(1), 116–132. doi:10.1109/TSMC.1985.6313399.

Jamil, M., & Yang, X. S. (2013). A literature survey of benchmark functions for global optimisation problems. International Journal of Mathematical Modelling and Numerical Optimisation, 4(2), 150–194. doi:10.1504/IJMMNO.2013.055204.

Liu, J., & Bailey, J. (2019). AI 2019: Advances in Artificial Intelligence. Lecture Notes in Computer Science, 2-5 December, 2015, Adelaide, Australia. doi:10.1007/978-3-030-35288-2.

Plevris, V., & Solorzano, G. (2022). A Collection of 30 Multidimensional Functions for Global Optimization Benchmarking. Data, 7(4), 46. doi:10.3390/data7040046.

Perkis, T. (1994). Stack-based genetic programming. Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence. doi:10.1109/icec.1994.350025.


Full Text: PDF

DOI: 10.28991/ESJ-2023-07-04-01

Refbacks

  • There are currently no refbacks.


Copyright (c) 2023 Gloria Pietropolli, Giuliamaria Menara, Mauro Castelli