Name
Title | ||
|---|---|---|
Single- and multi-objective genetic programming: new bounds for weighted order and majority |
Abstract | ||
|---|---|---|
We consolidate the existing computational complexity analysis of genetic programming (GP) by bringing together sound theoretical proofs and empirical analysis. In particular, we address computational complexity issues arising when coupling algorithms using variable length representation, such as GP itself, with different bloat-control techniques. In order to accomplish this, we first introduce several novel upper bounds for two single- and multi-objective GP algorithms on the generalised Weighted ORDER and MAJORITY problems. To obtain these, we employ well-established computational complexity analysis techniques such as fitness-based partitions, and for the first time, additive and multiplicative drift. The bounds we identify depend on two measures, the maximum tree size and the maximum population size, that arise during the optimization run and that have a key relevance in determining the runtime of the studied GP algorithms. In order to understand the impact of these measures on a typical run, we study their magnitude experimentally, and we discuss the obtained findings. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2460239.2460254 | FOGA |
Keywords | Field | DocType |
computational complexity issue,optimization run,maximum population size,new bound,maximum tree size,weighted order,empirical analysis,existing computational complexity analysis,computational complexity analysis technique,multi-objective gp algorithm,multi-objective genetic programming,gp algorithm,typical run,theory,multi objective optimization,genetic programming | Coupling,Multiplicative function,Computer science,Genetic programming,Multi-objective optimization,Population size,Artificial intelligence,Key relevance,Mathematical optimization,Algorithm,Mathematical proof,Machine learning,Computational complexity theory | Conference |
Citations | PageRank | References |
5 | 0.42 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anh Nguyen | 1 | 5 | 0.42 |
| Tommaso Urli | 2 | 79 | 8.66 |
| Markus Wagner | 3 | 358 | 43.21 |