Optimal recombination in genetic algorithms for combinatorial optimization problems: Part I
DOI:
https://doi.org/10.2298/YJOR130731040EKeywords:
Genetic Algorithm, Optimal Recombination Problem, complexity, crossover, Boolean Linear ProgrammingAbstract
This paper surveys results on complexity of the optimal recombination problem (ORP), which consists in finding the best possible offspring as a result of a recombination operator in a genetic algorithm, given two parent solutions. We consider efficient reductions of the ORPs, allowing to establish polynomial solvability or NP-hardness of the ORPs, as well as direct proofs of hardness results. Part I presents the basic principles of optimal recombination with a survey of results on Boolean Linear Programming Problems. Part II (to appear in a subsequent issue) is devoted to the ORPs for problems which are naturally formulated in terms of search for an optimal permutation.References
Agarwal, C.C., Orlin, J.B. and Tai, R.P., Optimized crossover for the independent set problem, Massachusetts Institute of Technology, 1995.
Alekseeva, E., Kochetov, Yu. and Plyasunov, A., “Complexity of local search for the p-median problem”, European Journal of Operational Research, 191 (2008) 736-752.
Ausiello, G., Crescenzi, P., Gambosi, G. et al., Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag, Berlin, 1999.
Balas, E. and Niehaus, W., A Max-Flow Based Procedure for Finding Heavy Cliques in Vertex-Weighted Graphs, MSRR no. 612, Carnegie-Mellon University, 1995.
Balas, E. and Niehaus, W., “Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems”, Journal of Heuristics, 4 (2) (1998) 107-122.
Beresnev, V.L., Gimady, Ed.Kh. and Dementev, V. T., Extremal Problems of Standardization, Novosibirsk, Nauka, 1978 (in Russian).
Beyer, H.-G., Schwefel, H.-P. and Wegener, I., “How to analyse evolutionary algorithms”, Theoretical Computer Science, 287 (2002) 101-130.
Borisovsky, P., Dolgui, A. and Eremeev, A., “Genetic algorithms for a supply management problem: MIP-recombination vs greedy decoder”, European Journal of Operational Research, 195 (3) (2009) 770-779.
Cook, W. and Seymour, P., “Tour merging via branch-decomposition”, INFORMS Journal on Computing, 15 (2) (2003) 233-248.
Cotta, C., “A study on allelic recombination”, Proc. of 2003 Congress on Evolutionary Computation, Canberra, IEEE Press, 2003, 1406-1413.
Cotta, C. and Troya, J.M., “Embedding branch and bound within evolutionary algorithms”, Applied Intelligence, 18 (2003) 137-153.
Dolgui, A. and Eremeev, A., “On complexity of optimal recombination for one-dimensional bin packing problem”, Proc. of VIII Intern. Conf. “Dynamics of Systems, Mechanisms and Machines”, Vol. 3, Omsk, Omsk Polytechnical University, 2012, 25-27. (In Russian)
Dolgui, A., Eremeev, A. and Guschinskaya, O., “MIP-based GRASP and genetic algorithm for balancing transfer lines”, Matheuristics. Hybridizing Metaheuristics and Mathematical Programming, (ed.) by V. Maniezzo, T. Stutzle, and S. Voss, Berlin, Springer-Verlag, 2010, 189-208.
Eremeev, A.V., “A Genetic algorithm with a non-binary representation for the set covering problem”, Proc. of Operations Research (OR’98), Springer-Verlag, Berlin, 1999, 175-181.
Eremeev, A.V., “On complexity of optimal recombination for binary representations of solutions”, Evolutionary Computation, 16 (1) (2008) 127-147.
Eremeev, A.V. and Kovalenko, J.V., “On scheduling with technology based machines grouping”, Diskretnyi analiz i issledovanie operacii, 18 (5) (2011) 54-79. (In Russian)
Garey, M. and Johnson, D., Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman and Company, San Francisco, CA, 1979.
Glover, F., Laguna, M. and Marti, R., “Fundamentals of scatter search and path relinking”, Control and Cybernetics, 29 (3) (2000) 653-684.
Hochbaum, D.S., “Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems”, Approximation Algorithms for NP-Hard Problems, (ed.) by D. Hochbaum, PWS Publishing Company, Boston, 1997, 94-143.
Holland, J., Adaptation in natural and artificial systems, Ann Arbor, University of Michigan Press, 1975.
Jansen, T. and Wegener, I., “On the analysis of evolutionary algorithms– a proof that crossover really can help”, Algorithmica, 34 (1) (2002) 47-66.
Mukhacheva, E.A. and Mukhacheva, A.S., “L.V. Kantorovich and cutting-packing problems: New approaches to combinatorial problems of linear cutting and rectangular packing”, Journal of Mathematical Sciences, 133 (4) (2006) 1504-1512.
Korte, B. and Vygen, J., Combinatorial Optimization. Theory and Algorithms, 3rd edition, Springer-Verlag, Berlin, 2005.
Krarup, J. and Pruzan, P., “The simple plant location problem: survey and synthesis”, European Journal of Operational Research, 12 (1983) 36-81.
Lourenço, H., Paixão, J. and Portugal, R., “Multiobjective metaheuristics for the bus driver scheduling problem”, Transportation Science, 35 (2001) 331-343.
Papadimitriou, C.H. and Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Upper Saddle River, NJ, 1982.
Radcliffe, N.J., “The algebra of genetic algorithms”, Annals of Mathematics and Artificial Intelligence, 10 (4) (1994) 339-384.
Reeves, C.R., “Genetic algorithms for the operations researcher”, INFORMS Journal on Computing, 9 (3) (1997) 231-250.
Reeves, C.R. and Rowe, J.E., Genetic algorithms: principles and perspectives, Norwell, MA, Kluwer Acad. Pbs., 2002.
Schuurman, P. and Woeginger, G., Approximation schemes– a tutorial, Eindhoven University of Technology, 2006.
Yagiura, M., Ibaraki, T., “The use of dynamic programming in genetic algorithms for permutation problems”, European Journal of Operational Research, 92 (1996) 387-401.
Yankovskaya, A.E., “Test pattern recognition with the use of genetic algorithms”, Pattern Recognition and Image Analysis, 9 (1) (1999) 121-123.
Downloads
Published
Issue
Section
License
Copyright (c) 2014 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
