2018 [ to top ]

• 
  Kötzing, Timo; Lagodzinski, J. A. Gregor; Lengler, Johannes; Melnichenko, Anna Destructiveness of Lexicographic Parsimony Pressure and Alleviation by a Concatenation Crossover in Genetic Programming. Parallel Problem Solving From Nature (PPSN) 2018
  [ BibTeX ] [ Download ]
   
  @inproceedings{kotzing2018destructiveness, author = {Kötzing, Timo and Lagodzinski, J. A. Gregor and Lengler, Johannes and Melnichenko, Anna}, booktitle = {Parallel Problem Solving From Nature (PPSN)}, title = {Destructiveness of Lexicographic Parsimony Pressure and Alleviation by a Concatenation Crossover in Genetic Programming}, year = 2018 }
• 
  Kötzing, Timo; Lagodzinski, J. A. Gregor; Lengler, Johannes; Melnichenko, Anna Destructiveness of Lexicographic Parsimony Pressure and Alleviation by a Concatenation Crossover in Genetic Programming. arxiv 2018
  [ Abstract ] [ BibTeX ] [ URL ] [ Download ]
   
  For theoretical analyses there are two specifics distinguishing GP from many other areas of evolutionary computation. First, the variable size representations, in particular yielding a possible bloat (i.e. the growth of individuals with redundant parts). Second, the role and realization of crossover, which is particularly central in GP due to the tree-based representation. Whereas some theoretical work on GP has studied the effects of bloat, crossover had a surprisingly little share in this work. We analyze a simple crossover operator in combination with local search, where a preference for small solutions minimizes bloat (\emph{lexicographic parsimony pressure}); the resulting algorithm is denoted \emph{Concatenation Crossover GP. For this purpose three variants of the well-studied MAJORITY test function with large plateaus are considered. We show that the Concatenation Crossover GP can efficiently optimize these test functions, while local search cannot be efficient for all three variants independent of employing bloat control.
  @preprint{kotzing2018destructiveness, abstract = {For theoretical analyses there are two specifics distinguishing GP from many other areas of evolutionary computation. First, the variable size representations, in particular yielding a possible bloat (i.e. the growth of individuals with redundant parts). Second, the role and realization of crossover, which is particularly central in GP due to the tree-based representation. Whereas some theoretical work on GP has studied the effects of bloat, crossover had a surprisingly little share in this work. We analyze a simple crossover operator in combination with local search, where a preference for small solutions minimizes bloat (\emph{lexicographic parsimony pressure}); the resulting algorithm is denoted \emph{Concatenation Crossover GP}. For this purpose three variants of the well-studied MAJORITY test function with large plateaus are considered. We show that the Concatenation Crossover GP can efficiently optimize these test functions, while local search cannot be efficient for all three variants independent of employing bloat control.}, author = {Kötzing, Timo and Lagodzinski, J. A. Gregor and Lengler, Johannes and Melnichenko, Anna}, journal = {arxiv}, number = {arXiv:1805.10169}, title = {Destructiveness of Lexicographic Parsimony Pressure and Alleviation by a Concatenation Crossover in Genetic Programming}, year = 2018 }

2017 [ to top ]

• 
  Friedrich, Tobias; Kötzing, Timo; Melnichenko, Anna Analyzing Search Heuristics with Differential Equations. Genetic and Evolutionary Computation Conference (GECCO) 2017: 313-314
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Drift Theory is currently the most common technique for the analysis of randomized search heuristics because of its broad applicability and the resulting tight first hitting time bounds. The biggest problem when applying a drift theorem is to find a suitable potential function which maps a complex space into a single number, capturing the essence of the state of the search in just one value. We discuss another method for the analysis of randomized search heuristics based on the Theory of Differential Equations. This method considers the deterministic counterpart of the randomized process by replacing probabilistic outcomes by their expectation, and then bounding the error with good probability. We illustrate this by analyzing an Ant Colony Optimization algorithm (ACO) for the Minimum Spanning Tree problem (MST).
  @inproceedings{friedrich2017analyzing, abstract = {Drift Theory is currently the most common technique for the analysis of randomized search heuristics because of its broad applicability and the resulting tight first hitting time bounds. The biggest problem when applying a drift theorem is to find a suitable potential function which maps a complex space into a single number, capturing the essence of the state of the search in just one value. We discuss another method for the analysis of randomized search heuristics based on the Theory of Differential Equations. This method considers the deterministic counterpart of the randomized process by replacing probabilistic outcomes by their expectation, and then bounding the error with good probability. We illustrate this by analyzing an Ant Colony Optimization algorithm (ACO) for the Minimum Spanning Tree problem (MST).}, author = {Friedrich, Tobias and Kötzing, Timo and Melnichenko, Anna}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, pages = {313-314}, title = {Analyzing Search Heuristics with Differential Equations}, year = 2017 }
• 
  Chauhan, Ankit; Lenzner, Pascal; Melnichenko, Anna; Molitor, Louise Selfish Network Creation with Non-Uniform Edge Cost. Symposium on Algorithmic Game Theory (SAGT) 2017: 160-172
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Network creation games investigate complex networks from a game-theoretic point of view. Based on the original model by Fabrikant et al. [PODC’03] many variants have been introduced. However, almost all versions have the drawback that edges are treated uniformly, i.e. every edge has the same cost and that this common parameter heavily influences the outcomes and the analysis of these games. We propose and analyze simple and natural parameter-free network creation games with non-uniform edge cost. Our models are inspired by social networks where the cost of forming a link is proportional to the popularity of the targeted node. Besides results on the complexity of computing a best response and on various properties of the sequential versions, we show that the most general version of our model has con- stant Price of Anarchy. To the best of our knowledge, this is the first proof of a constant Price of Anarchy for any network creation game.
  @inproceedings{chauhan2017selfish, abstract = {Network creation games investigate complex networks from a game-theoretic point of view. Based on the original model by Fabrikant et al. [PODC’03] many variants have been introduced. However, almost all versions have the drawback that edges are treated uniformly, i.e. every edge has the same cost and that this common parameter heavily influences the outcomes and the analysis of these games. We propose and analyze simple and natural parameter-free network creation games with non-uniform edge cost. Our models are inspired by social networks where the cost of forming a link is proportional to the popularity of the targeted node. Besides results on the complexity of computing a best response and on various properties of the sequential versions, we show that the most general version of our model has con- stant Price of Anarchy. To the best of our knowledge, this is the first proof of a constant Price of Anarchy for any network creation game.}, author = {Chauhan, Ankit and Lenzner, Pascal and Melnichenko, Anna and Molitor, Louise}, booktitle = {Symposium on Algorithmic Game Theory (SAGT)}, pages = {160-172}, title = {Selfish Network Creation with Non-Uniform Edge Cost}, year = 2017 }

2016 [ to top ]

• 
  Chauhan, Ankit; Lenzner, Pascal; Melnichenko, Anna; Münn, Martin On Selfish Creation of Robust Networks. Symposium on Algorithmic Game Theory (SAGT) 2016: 141-152
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Robustness is one of the key properties of nowadays networks. However, robustness cannot be simply enforced by design or regulation since many important networks, most prominently the Internet, are not created and controlled by a central authority. Instead, Internet-like networks emerge from strategic decisions of many selfish agents. Interestingly, although lacking a coordinating authority, such naturally grown networks are surprisingly robust while at the same time having desirable properties like a small diameter. To investigate this phenomenon we present the first simple model for selfish network creation which explicitly incorporates agents striving for a central position in the network while at the same time protecting themselves against random edge-failure. We show that networks in our model are diverse and we prove the versatility of our model by adapting various properties and techniques from the non-robust versions which we then use for establishing bounds on the Price of Anarchy. Moreover, we analyze the computational hardness of finding best possible strategies and investigate the game dynamics of our model.
  @inproceedings{Chauhan2016, abstract = {Robustness is one of the key properties of nowadays networks. However, robustness cannot be simply enforced by design or regulation since many important networks, most prominently the Internet, are not created and controlled by a central authority. Instead, Internet-like networks emerge from strategic decisions of many selfish agents. Interestingly, although lacking a coordinating authority, such naturally grown networks are surprisingly robust while at the same time having desirable properties like a small diameter. To investigate this phenomenon we present the first simple model for selfish network creation which explicitly incorporates agents striving for a central position in the network while at the same time protecting themselves against random edge-failure. We show that networks in our model are diverse and we prove the versatility of our model by adapting various properties and techniques from the non-robust versions which we then use for establishing bounds on the Price of Anarchy. Moreover, we analyze the computational hardness of finding best possible strategies and investigate the game dynamics of our model.}, address = {Berlin, Heidelberg}, author = {Chauhan, Ankit and Lenzner, Pascal and Melnichenko, Anna and Münn, Martin}, booktitle = {Symposium on Algorithmic Game Theory (SAGT)}, editor = {Gairing, Martin and Savani, Rahul}, pages = {141-152}, publisher = {Springer Berlin Heidelberg}, title = {On Selfish Creation of Robust Networks}, year = 2016 }