No Access

EXPLICITLY SIMPLIFYING EVOLVED GENETIC PROGRAMS DURING EVOLUTION

School of Mathematics, Statistics and Computer Science, Victoria University of Wellington, PO Box 600, Wellington, New Zealand

Search for more papers by this author

and

PHILLIP WONG

School of Mathematics, Statistics and Computer Science, Victoria University of Wellington, PO Box 600, Wellington, New Zealand

Search for more papers by this author

https://doi.org/10.1142/S1469026808002247Cited by:3 (Source: Crossref)

Abstract

The genetic programming (GP) evolutionary process typically introduces a large amount of redundancy and unnecessary complexity into evolved programs. Quick growth of redundant and functionally useless sections of programs can quickly overcome a GP system, exhausting system resources and causing premature termination of the system before an acceptable solution can be found. Rather than implicitly controlling the redundancy and code growth/bloat as in most of the existing approaches, this paper investigates an algebraic simplification algorithm for explicitly removing the redundancy from the genetic programs and simplifying these programs online during the evolutionary process. The new GP system with the simplification is examined and compared with a standard GP system on two regression and three classification problems of varying difficulties. The results show that the GP system employing a simplification component can achieve superior efficiency with comparable or slightly superior effectiveness to the standard GP system on these problems. The programs evolved by the new GP approach with the explicit simplification contain ``hidden patterns'' for a particular problem and are relatively simple and easy to interpret.

Keywords:

References

J. R. Koza , Genetic Programming: On the Programming of Computers by Means of Natural Selection ( MIT Press , Cambridge, MA, USA , 1992 ) . Google Scholar
G. Olaguea, S. Cagnoni and E. Lutton, Pattern Recogn. Lett. 27(11), 1161 (2006). Crossref, Google Scholar
M. Zhang and V. Ciesielski, Genetic programming for multiple class object detection, 12th Australian Joint Conf. Artificial Intelligence, Lecture Notes in Artificial Intelligence 1747, ed. N. Foo (Springer-Verlag, 1999) pp. 180–192. Google Scholar
J. Buschet al., Automatic generation of control programs for walking robots using genetic programming, EuroGP '02: Proc. 5th Eur. Conf. Genetic Programming (2002) pp. 258–267. Google Scholar
J. R. Koza et al. , Genetic Programming IV: Routine Human–Competitive Machine Intelligence ( Kluwer Academic Publishers , 2003 ) . Google Scholar
T. Soule, J. A. Foster and J. Dickinson, Code growth in genetic programming, Genetic Programming 1996: Proc. First Ann. Conf., eds. J. R. Kozaet al. (MIT Press, 1996) pp. 215–223. Google Scholar
T. Blickle and L. Thiele, Genetic programming and redundancy, in Genetic Algorithms Within the Framework of Evolutionary Computation, ed. J. Hopf, Workshop at KI-94, Saarbrücken, Im Stadtwald, Building 44, D-66123 Saarbrücken, Germany, Max-Planck-Institut für Informatik, MPI-I-94-241 (1994), pp. 33–38 . Google Scholar
P. Nordin and W. Banzhaf, Complexity compression and evolution, Genetic Algorithms: Proc. Sixth Int. Conf. (ICGA95), ed. L. Eshelman (Morgan Kaufmann, Pittsburgh, PA, USA) pp. 310–317. Google Scholar
D. Parrott, X. Li and V. Ciesielski, Multi-objective techniques in genetic programming for evolving classifiers, Proc. 2005 IEEE Cong. Evolutionary Computation2, eds. D. Corneet al. (IEEE Press) pp. 1141–1148. Google Scholar
B.-T. Zhang and H. Mühlenbein, Evol. Comput. 3(1), 17 (1995), DOI: 10.1162/evco.1995.3.1.17. Crossref, Google Scholar
M. Zhang and U. Bhowan, Program size and pixel statistics in genetic programming for object detection, Applications of Evolutionary Computing, EvoWorkshops2004: EvoBIO, EvoCOMNET, EvoHOT, EvoIASP, EvoMUSART, EvoSTOC, Lecture Notes in Computer Science 3005, eds. G. R. Raidlet al. (Springer-Verlag, 2004) pp. 379–388. Google Scholar
S. Luke and L. Panait, Lexicographic parsimony pressure, GECCO 2002: Proc. Genet. Evol. Comput. Conf., eds. W. B. Langdonet al. (Morgan Kaufmann Publishers, New York) pp. 829–836. Google Scholar
S. Luke, Code growth is not caused by introns, Late Breaking Papers, Proc. Genet. Evol. Comput. Conf. 2000 (2000) pp. 228–235. Google Scholar
W. B. Langdon, Quadratic bloat in genetic programming, Proc. Genet. Evol. Comput. Conf. (GECCO-2000), eds. D. Whitleyet al. (Morgan Kaufmann) pp. 451–458. Google Scholar
M. J. Streeter, The root causes of code growth in genetic programming, Genetic Programming, Proc. EuroGP'2003, Lecture Notes in Computer Science 2610, eds. C. Ryanet al. (Springer-Verlag) pp. 443–454. Google Scholar
S. Gustafsonet al., Genet. Program. Evol. Mach. 5(3), 271 (2004), DOI: 10.1023/B:GENP.0000030194.98244.e3. Crossref, Google Scholar
D. Jackson, Fitness evaluation avoidance in boolean GP problems, Proc. 2005 IEEE Congress on Evolutionary Computation3, eds. D. Corneet al. (IEEE Press) pp. 2530–2536. Google Scholar
T. Soule, Code growth in genetic programming, Ph.D. thesis, University of Idaho, Moscow, Idaho, USA (15, May 1998) . Google Scholar
T. Soule and J. A. Foster, Evol. Comput. 6(4), 293 (1998), DOI: 10.1162/evco.1998.6.4.293. Crossref, Google Scholar
A. Piszcz and T. Soule, Dynamics of evolutionary robustness, GECCO 2006: Proc. 8th Ann. Conf. Genetic and Evolutionary Computation1, eds. M. Keijzeret al. (ACM Press) pp. 871–878. Google Scholar
W. Ashlock and D. Ashlock, Single parent genetic programming, Proc. 2005 IEEE Congr. Evolutionary Computation2, eds. D. Corneet al. (IEEE Press) pp. 1172–1179. Google Scholar
W. B. Langdon and R. Poli, Fitness causes bloat: Mutation, Proc. First Eur. Workshop on Genetic Programming, Lecture Notes in Computer Science 1391, eds. W. Banzhafet al. (Springer-Verlag, 1998) pp. 37–48. Google Scholar
W. B. Langdon and R. Poli, Soft Computing in Engineering Design and Manufacturing, eds. P. K. Chawdhry, R. Roy and R. K. Pant (Springer-Verlag, London, 1997) pp. 13–22. Google Scholar
P. Nordin, F. Francone and W. Banzhaf, Explicitly defined introns and destructive crossover in genetic programming, Proc. Workshop on Genetic Programming: From Theory to Real-World Applications, ed. J. P. Rosca pp. 6–22. Google Scholar
X. Zhong and T. Soule, Growth of self-canceling code in evolutionary systems, GECCO 2006: Proc. 8th Ann. Conf. Genetic and Evolutionary Computation1, eds. M. Keijzeret al. (ACM Press) pp. 223–228. Google Scholar
S. Silva and E. Costa, Comparing tree depth limits and resource-limited GP, Proc. 2005 IEEE Congress on Evolutionary Computation1, eds. D. Corneet al. (IEEE Press) pp. 920–927. Google Scholar
C. Skinner, P. J. Riddle and C. Triggs, Mathematics prevents bloat, Proc. 2005 IEEE Congress on Evolutionary Computation1, eds. D. Corneet al. (IEEE Press) pp. 390–395. Google Scholar
N. F. McPhee and J. D. Miller, Accurate replication in genetic programming, Genetic Algorithms: Proc. Sixth Int. Conf. (ICGA95), ed. L. Eshelman (Morgan Kaufmann) pp. 303–309. Google Scholar
H. Stringer and A. S. Wu, Winnowing wheat from chaff: The chunking ga, Genetic and Evolutionary Computation — GECCO-2004, Lecture Notes in Computer Science 3013, eds. K. Debet al. (Springer-Verlag, 2004) pp. 198–209. Google Scholar
D. Hooper and N. S. Flann, Improving the accuracy and robustness of genetic programming through expression simplification, Genetic Programming 1996: Proc. First Ann. Conf., eds. J. R. Kozaet al. (MIT Press) p. 428. Google Scholar
A. Ekart, Shorter fitness preserving genetic programs, Artificial Evolution 4th European Conference, AE'99, Selected Papers, Lecture Notes in Computer Science 1829, eds. C. Fonluptet al. pp. 73–83. Google Scholar
J. F. Smith III, Genetic program based data mining for fuzzy decision trees, Intelligent Data Engineering and Automated Learning — IDEAL 2004, Proc. 5th Int. Conf., Lecture Notes in Computer Science 3177, eds. Z. R. Yang, R. M. Everson and H. Yin (Springer, 2004) pp. 464–470. Google Scholar
J. F. Smith III, Evolving fuzzy decision tree structure that adapts in real-time, GECCO 2005: Proc. 2005 Conf. Genetic and Evolutionary Computation2, eds. H.-G. Beyeret al. (ACM Press) pp. 1737–1744. Google Scholar
M. Zhang, Y. Zhang and W. D. Smart, Program simplification in genetic programming for object classification, Knowledge-based Intelligent Information and Engineering Systems, Proc. 9th Int. Conf., KES 2005, Lecture Notes in Computer Science 3683, eds. R. Khosla, R. J. Howlett and L. C. Jain (Springer, 2005) pp. 988–996. Google Scholar
W. B. Langdon and R. Poli , Foundations of Genetic Programming ( Springer-Verlag , 2002 ) . Crossref, Google Scholar
W. B. Langdon, Fitness causes bloat: Simulated annealing, hill climbing and populations, Technical Report CSRP-97-22, University of Birmingham, School of Computer Science (2, September 1997) . Google Scholar
W. Banzhaf et al. , Genetic Programming: An Introduction on the Automatic Evolution of Computer Programs and Its Applications, San Francisco, CA ( Morgan Kaufmann Publishers , Dpunkt-Verlag, Heidelburg , 1998 ) . Crossref, Google Scholar
R. Fikes and N. Nilsson, Artil. Intell. 2, 189 (1971), DOI: 10.1016/0004-3702(71)90010-5. Crossref, Google Scholar
W. A. Martin, J. ACM 18(4), 549 (1971), DOI: 10.1145/321662.321668. Crossref, Google Scholar
G. H. Gonnet, Determining equivalence of expressions in random polynomial time, STOC '84: Proc. Sixteenth Ann. ACM Symp. Theory of Computing (ACM Press, New York, NY, USA, 1984) pp. 334–341. Google Scholar
R. Lidl and H. Niederreiter , Introduction to Finite Fields and Their Applications ( Cambridge University Press , New York, NY, USA , 1986 ) . Google Scholar
W. Trappe and L. C. Washington , Introduction to Cryptography with Coding Theory , 2nd edn. ( Prentice-Hall , 2006 ) . Google Scholar
B. Cherowitzo, Lecture Notes (2006), http://www-math.cudenver.edu/~wcherowi/courses/m5410/exeucalg.html, available online 7, January 2006 . Google Scholar
R. Solomonoff, Advances in Cognitive Science, AAAS Selected Symposia Series, AAAS, eds. M. Kochen and H. M. Hastings (Washington, DC, 1986) pp. 210–227. Google Scholar
R. Solomonoff, A system for incremental learning based on algorithmic probability, Proc. Sixth Israeli Conf. Artificial Intelligence, Computer Vision and Pattern Recognition pp. 515–527. Google Scholar
M. Anthony and N. Biggs, The Handbook of Brain Theory and Neural Networks (1995) pp. 694–697. Google Scholar
A. S. Georghiades, P. N. Belhumeur and D. J. Kriegman, IEEE Trans. Pattern Anal. Mach. Intell. 23(6), 643 (2001), DOI: 10.1109/34.927464. Crossref, Google Scholar
O. L. Mangasarian and W. H. Wolberg, Cancer diagnosis via linear programming (September 1990) . Google Scholar
M. Zhang and W. Smart, Multiclass object classification using genetic programming, Applications of Evolutionary Computing, EvoWorkshops2004, Lecture Notes in Computer Science 3003, eds. G. R. Raidlet al. (Springer-Verlag) pp. 369–378. Google Scholar
T. Loveard and V. Ciesielski, Representing classification problems in genetic programming, Proc. Congress on Evolutionary Computation2 (IEEE Press) pp. 1070–1077. Google Scholar
M. L. Berenson and D. M. Levine , Applied Statistics: A First Course ( Prentice-Hall, Inc. , Upper Saddle River, NJ, USA , 1988 ) . Google Scholar
J. R. Quinlan , C4.5: Programs for Machine Learning ( Morgan Kaufmann Publishers Inc. , San Francisco, CA , 1993 ) . Google Scholar