DROPS

Document

On Complexity of Optimized Crossover for Binary Representations

Authors: Anton Eremeev

Published in: Dagstuhl Seminar Proceedings, Volume 6061, Theory of Evolutionary Algorithms (2006)

Abstract

We consider the computational complexity of producing the best possible offspring in a crossover, given two solutions of the parents. The crossover operators are studied on the class of Boolean linear programming problems, where the Boolean vector of variables is used as the solution representation. By means of efficient reductions of the optimized gene transmitting crossover problems (OGTC) we show the polynomial solvability of the OGTC for the maximum weight set packing problem, the minimum weight set partition problem and for one of the versions of the simple plant location problem. We study a connection between the OGTC for linear Boolean programming problem and the maximum weight independent set problem on 2-colorable hypergraph and prove the NP-hardness of several special cases of the OGTC problem in Boolean linear programming.

Cite as

Anton Eremeev. On Complexity of Optimized Crossover for Binary Representations. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 6061, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{eremeev:DagSemProc.06061.6,
  author =	{Eremeev, Anton},
  title =	{{On Complexity of Optimized Crossover for Binary Representations}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6061},
  editor =	{Dirk V. Arnold and Thomas Jansen and Michael D. Vose and Jonathan E. Rowe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06061.6},
  URN =		{urn:nbn:de:0030-drops-5932},
  doi =		{10.4230/DagSemProc.06061.6},
  annote =	{Keywords: Genetic Algorithm, Optimized Crossover, Complexity}
}

Search Results

Documents authored by Eremeev, Anton

On Complexity of Optimized Crossover for Binary Representations

Abstract

Cite as

Thanks for your feedback!

Could not send message