License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06061.6
URN: urn:nbn:de:0030-drops-5932
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/593/
Go to the corresponding Portal

Eremeev, Anton

On Complexity of Optimized Crossover for Binary Representations

pdf-format:
06061.EremeevAnton.Paper.593.pdf (0.2 MB)

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.

BibTeX - Entry

@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/opus/volltexte/2006/593},
  URN =		{urn:nbn:de:0030-drops-5932},
  doi =		{10.4230/DagSemProc.06061.6},
  annote =	{Keywords: Genetic Algorithm, Optimized Crossover, Complexity}
}

Keywords: Genetic Algorithm, Optimized Crossover, Complexity
Collection: 06061 - Theory of Evolutionary Algorithms
Issue Date: 2006
Date of publication: 07.07.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI