2017 [ to top ]

• 
  Doerr, Benjamin; Kötzing, Timo; Lagodzinski, J. A. Gregor; Lengler, Johannes Bounding Bloat in Genetic Programming. Genetic and Evolutionary Computation Conference (GECCO) 2017
  [ Abstract ] [ BibTeX ] [ Download ]
   
  While many optimization problems work with a fixed number of decision variables and thus a fixed-length representation of possible solutions, genetic programming (GP) works on variable-length representations. A naturally occurring problem is that of bloat (unnecessary growth of solutions) slowing down optimization. Theoretical analyses could so far not bound bloat and required explicit assumptions on the magnitude of bloat. In this paper we analyze bloat in mutation-based genetic programming for the two test functions ORDER and MAJORITY. We overcome previous assumptions on the magnitude of bloat and give matching or close-to-matching upper and lower bounds for the expected optimization time. In particular, we show that the \((1+1)\) GP takes (i) \(\Theta(T_init + n log n)\) iterations with bloat control on ORDER as well as MAJORITY; and (ii) \(O(T_init log T_init + n(log n)^3)\) and \(\Omega(T_init + n log n)\) (and \(\Omega(T_init log T_init)\) for \(n = 1\)) iterations without bloat control on MAJORITY.
  @inproceedings{doerr2017bounding, abstract = {While many optimization problems work with a fixed number of decision variables and thus a fixed-length representation of possible solutions, genetic programming (GP) works on variable-length representations. A naturally occurring problem is that of bloat (unnecessary growth of solutions) slowing down optimization. Theoretical analyses could so far not bound bloat and required explicit assumptions on the magnitude of bloat. In this paper we analyze bloat in mutation-based genetic programming for the two test functions ORDER and MAJORITY. We overcome previous assumptions on the magnitude of bloat and give matching or close-to-matching upper and lower bounds for the expected optimization time. In particular, we show that the \((1+1)\) GP takes (i) \(\Theta(T_init + n log n)\) iterations with bloat control on ORDER as well as MAJORITY; and (ii) \(O(T_init log T_init + n(log n)^3)\) and \(\Omega(T_init + n log n)\) (and \(\Omega(T_init log T_init)\) for \(n = 1\)) iterations without bloat control on MAJORITY.}, author = {Doerr, Benjamin and Kötzing, Timo and Lagodzinski, J. A. Gregor and Lengler, Johannes}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, title = {Bounding Bloat in Genetic Programming}, year = 2017 }
• 
  Friedrich, Tobias; Kötzing, Timo; Lagodzinski, J. A. Gregor; Neumann, Frank; Schirneck, Martin Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints. Foundations of Genetic Algorithms (FOGA) 2017: 45-54
  [ Abstract ] [ BibTeX ] [DOI] [ Download ]
   
  Linear functions have gained a lot of attention in the area of run time analysis of evolutionary computation methods and the corresponding analyses have provided many effective tools for analyzing more complex problems. In this paper, we consider the behavior of the classical (1+1) Evolutionary Algorithm for linear functions under linear constraint. We show tight bounds in the case where both the objective function and the constraint is given by the OneMax function and present upper bounds as well as lower bounds for the general case. Furthermore, we also consider the LeadingOnes fitness function.
  @inproceedings{DBLP:conf/foga/0001KLNS17, abstract = {Linear functions have gained a lot of attention in the area of run time analysis of evolutionary computation methods and the corresponding analyses have provided many effective tools for analyzing more complex problems. In this paper, we consider the behavior of the classical (1+1) Evolutionary Algorithm for linear functions under linear constraint. We show tight bounds in the case where both the objective function and the constraint is given by the OneMax function and present upper bounds as well as lower bounds for the general case. Furthermore, we also consider the LeadingOnes fitness function.}, author = {Friedrich, Tobias and Kötzing, Timo and Lagodzinski, J. A. Gregor and Neumann, Frank and Schirneck, Martin}, booktitle = {Foundations of Genetic Algorithms (FOGA)}, pages = {45-54}, publisher = {ACM Press}, title = {Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints}, year = 2017 }