Feasibility-preserving crossover for maximum k-coverage problem

ABSTRACT

The maximum k-coverage problem is a generalized version of covering problems. We introduce the problem formally and analyze its property in relation to the operators of genetic algorithm. Based on the analysis, we propose a new crossover tailored to the maximum k-coverage problem. While traditional n-point crossovers have a problem of requiring repair steps, the proposed crossover has an additional advantage of always producing feasible solutions. We give a comparative analysis of the proposed crossover through experiments.

REFERENCES

• 1: U. Aickelin. An indirect genetic algorithm for set covering problems. Journal of the Operational Research Society, 53(10):1118--1126, 2002.
• 2: Enrique Alba , Gabriel Luque , Lourdes Araujo, Natural language tagging with genetic algorithms, Information Processing Letters, v.100 n.5, p.173-182, 16 December 2006 [doi>10.1016/j.ipl.2006.07.002]
• 3: J. E. Beasley. OR--library: Distributing test problems by electronic mail. Journal of the Operational Research Society, 41:1069--1072, 1990.
• 4: J. E. Beasley and P. C. Chu. A genetic algorithm for the set covering problem. European Journal of Operational Research, 94:392--404, 1996.
• 5: O. Cordon, S. Damasb, and J. Santamaria. Feature-based image registration by means of the CHC evolutionary algorithm. Image and Vision Computing, 24(5):525--533, 2006.
• 6: L. J. Eshelman. The CHC adaptive search algorithm: how to have safe search when engaging in nontraditional genetic recombination. In Foundations of Genetic Algorithms, pages 265--283. Morgan Kaufmann, 1991.
• 7: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 8: C. Guerra-Salcedo and D. Whitley. Genetic search for feature subset selection: A comparison between CHC and GENESIS. In Proceedings of the Third Annual Conference on Genetic Programming, pages 504--509. Morgan Kaufmann, 1998.
• 9: D. S. Hochbaum and A. Pathria. Analysis of the greedy approach in problems of maximum k--coverage. Naval Research Logistics, 45(6):615--627, 1998.
• 10: H. W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistic Quarterly, 2:83--97, 1955.
• 11: Alberto Moraglio , Yong-Hyuk Kim , Yourim Yoon , Byung-Ro Moon, Geometric crossovers for multiway graph partitioning, Evolutionary Computation, v.15 n.4, p.445-474, Winter 2007 [doi>10.1162/evco.2007.15.4.445]
• 12: Antonio J. Nebro , Enrique Alba , Guillermo Molina , Francisco Chicano , Francisco Luna , Juan J. Durillo, Optimal antenna placement using a new multi-objective chc algorithm, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277128]
• 13: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 14: Shigeyoshi Tsutsui , Devid E. Goldberg, Search space boundary extension method in real-coded genetic algorithms, Information Sciences—Informatics and Computer Science: An International Journal, v.133 n.3-4, p.229-247, April 2001 [doi>10.1016/S0020-0255(01)00087-1]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms, Experimentation

Keywords:
feasibility-preserving crossover, genetic algorithms, maximum k-coverage