Multi-objective methods for tree size control

被引:49
作者
Edwin D. de Jong
Jordan B. Pollack
机构
[1] Department of Computer Science, Brandeis University, Waltham
[2] Utrecht University, Inst. of Info./Coumputing Sciences, Decision Support Systems Group
关键词
Bloat; Code growth; Genetic programming; Interpretability; Multi-objective optimization; Pareto optimality; Variable size representations;
D O I
10.1023/A:1025122906870
中图分类号
学科分类号
摘要
Variable length methods for evolutionary computation can lead to a progressive and mainly unnecessary growth of individuals, known as bloat. First, we propose to measure performance in genetic programming as a function of the number of nodes, rather than trees, that have been evaluated. Evolutionary Multi-Objective Optimization (EMOO) constitutes a principled way to optimize both size and fitness and may provide parameterless size control. Reportedly, its use can also lead to minimization of size at the expense of fitness. We replicate this problem, and an empirical analysis suggests that multi-objective size control particularly requires diversity maintenance. Experiments support this explanation. The multi-objective approach is compared to genetic programming without size control on the 11-multiplexer, 6-parity, and a symbolic regression problem. On all three test problems, the method greatly reduces bloat and significantly improves fitness as a function of computational expense. Using the FOCUS algorithm, multi-objective size control is combined with active pursuit of diversity, and hypothesized minimum-size solutions to 3-, 4- and 5-parity are found. The solutions thus found are furthermore easily interpretable. When combined with diversity maintenance, EMOO can provide an adequate and parameterless approach to size control in variable length evolution.
引用
收藏
页码:211 / 233
页数:22
相关论文
共 46 条
[1]  
Angeline P.J., Genetic programming and emergent intelligence, Advances in Genetic Programming, pp. 75-98, (1994)
[2]  
Angeline P.J., Pollack J.B., The evolutionary induction of subroutines, Proceedings of the Fourteenth Annual Conference of the Cognitive Science Society, pp. 236-241, (1992)
[3]  
Banzhaf W., Banscherus D., Dittrich P., Hierarchical genetic programming using local modules, Interjounrnal Complex Systems, 228, (1998)
[4]  
Banzhaf W., Langdon W.B., Some considerations on the reason for bloat, Genetic Programming and Evolvable Machines, 3, 1, pp. 81-91, (2002)
[5]  
Banzhaf W., Nordin P., Keller R.E., Francone F.D., Genetic Programming - An Introduction: On the Automatic Evolution of Computer Programs and Its Applications, (1998)
[6]  
Blickle T., Thiele L., Genetic programming and redundancy, Genetic Algorithms Within the Framework of Evolutionary Computation, pp. 33-38, (1994)
[7]  
Brindle A., Genetic algorithms for function optimization, Computer Science Department, Technical Report, TR81-2
[8]  
Coello C.A.C., An updated survey of GA-based multiobjective optimization techniques, ACM Computing Surveys, 32, 2, pp. 109-143, (2000)
[9]  
Conover W., Practical Nonparametric Statistics, (1980)
[10]  
Come D.W., Jerram N.R., Knowles J.D., Oates M.J., PESA-II: Region-based selection in evolutionary multiobjective optimization, Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2001, pp. 283-290, (2001)