[en] A large number of problems can be formalized as finding the best symbolic expression to maximize a given numerical objective. Most approaches to approximately solve such problems rely on random exploration of the search space. This paper focuses on how this random exploration should be performed to take into account expressions redundancy and invalid expressions. We propose a learning algorithm that, given the set of available constants, variables and operators and given the target finite number of trials, computes a probability distribution to maximize the expected number of semantically different, valid, generated expressions. We illustrate the use of our approach on both medium-scale and large-scale expression spaces, and empirically show that such optimized distributions significantly outperform the uniform distribution in terms of the diversity of generated expressions. We further test the method in combination with the recently proposed nested Monte-Carlo algorithm on a set of benchmark symbolic regression problems and demonstrate its interest in terms of reduction of the number of required calls to the objective function.
Disciplines :
Computer science
Author, co-author :
St-Pierre, David Lupien
Maes, Francis
Ernst, Damien ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Smart grids
Louveaux, Quentin ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète
Language :
English
Title :
A learning procedure for sampling semantically different valid expressions
Cazenave, T. 2009. Nested monte-carlo search, Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI'09), Pasadena (CA) USA, pp. 456-461.
Cazenave, T. 2010. Nested Monte-Carlo Expression Discovery, Proceedings of the 19th European Conference on Artificial Intelligence (ECAI'2010), IOS Press, pp. 1057-1058.
Deb, K., Pratap, A., Agarwal, S. and Meyarivan, T. 2002. A fast and elitist multiobjective genetic algorithm: Nsga-ii, IEEE Transactions on Evolutionary Computation 6(2): 182-197.
Holland, J. 1992. Genetic algorithms, Scientific American 267(1): 66-72.
Hu, Y. and Yang, S. 2004. A knowledge based genetic algorithm for path planning of a mobile robot, Proceedings of the IEEE International Conference on Robotics and Automation(ICRA'04), Vol. 5, New Orleans (LA), USA, pp. 4350-4355.
Jones, G., Willett, P., Glen, R., Leach, A. and Taylor, R. 1997. Development and validation of a genetic algorithm for flexible docking, Journal of Molecular Biology 267(3): 727-748.
Kargupta, H. and Buescher, K. 1996. The gene expression messy genetic algorithm for financial applications, Proceedings of the IEEE International Conference on Evolutionary Computation, Nagoya, JPN, pp. 814-819.
Kikuchi, S., Tominaga, D., Arita, M., Takahashi, K. and Tomita, M. 2003. Dynamic modeling of genetic networks using genetic algorithm and s-system, Bioinformatics 19(5): 643-650.
Koza, J. and Poli, R. 2005. Genetic programming, Search Methodologies pp. 127-164.
Maulik, U. and Bandyopadhyay, S. 2000. Genetic algorithm-based clustering technique, Pattern Recognition 33(9): 1455-1465.
Omranpour, H., Ebadzadeh, M., Shiry, S. and Barzegar, S. 2012. Dynamic particle swarm optimization for multimodal function, International Journal of Artificial Intelligence (IJAI) 1(1): 1-10.
O'Neill, M. and Ryan, C. 2001. Grammatical evolution, Evolutionary Computation, IEEE Transactions on 5(4): 349-358.
Uy, N., Hoai, N., ONeill, M., McKay, R. and Galv Ánlópez, E. 2011. Semantically-based crossover in genetic programming: application to real-valued symbolic regression, Genetic Programming and Evolvable Machines 12(2): 91-119.
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.