Computer Science – Neural and Evolutionary Computing
Scientific paper
2007-05-25
Computer Science
Neural and Evolutionary Computing
Dagstuhl Seminar 06061 "Theory of Evolutionary Algorithms", 2006
Scientific paper
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.
No associations
LandOfFree
On complexity of optimized crossover for binary representations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On complexity of optimized crossover for binary representations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On complexity of optimized crossover for binary representations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-680142