Optimal recombination in genetic algorithms for combinatorial optimization problems: Part II
DOI:
https://doi.org/10.2298/YJOR131030041EKeywords:
Genetic Algorithm, Optimal Recombination Problem, complexity, crossover, permutation problemsAbstract
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. In Part II, we consider the computational complexity of ORPs arising in genetic algorithms for problems on permutations: the Travelling Salesman Problem, the Shortest Hamilton Path Problem and the Makespan Minimization on Single Machine and some other related problems. The analysis indicates that the corresponding ORPs are NP-hard, but solvable by faster algorithms, compared to the problems they are derived from.References
Aggarwal, C.C., Orlin, J.B., Tai, R.P., An optimized crossover for maximum independent set, Operations Research, 45 (1997) 225-234.
Ausiello, G., Crescenzi, P., Gambosi, G. et al., Complexity and approximation: Combinatorial optimization problems and their approximability properties, Berlin, Springer-Verlag, 1999.
Avis, D., A survey of heuristics for the weighted matching problem, Networks, 13 (1983) 475-493.
Balas, E., Niehaus, W., Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems, Journal of Heuristics, 4 (2) (1998) 107-122.
Berge, C., The theory of graphs and its applications, New York, NY, John Wiley & Sons Inc., 1962.
Cook, W., Seymour, P., Tour merging via branch-decomposition, INFORMS Journal on Computing, 15 (2) (2003) 233-248.
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., Introduction to Algorithms, 2nd edition, MIT Press, 2001.
Cotta, C., Alba, E., Troya, J.M., Utilizing dynastically optimal forma recombination in hybrid genetic algorithms, Proc. of 5-th Int. Conf. on Parallel Problem Solving from Nature, LNCS, Berlin, Springer-Verlag, (1498) 1998, 305-314.
Cotta, C., Moscato, P., The parameterized complexity of multiparent recombination, Proc. of The 6-th Metaheuristics International Conference, Vienna, Universitat Wien, 2003, 237-241.
Doerr, B., Happ, E., Klein, C., Crossover can provably be useful in evolutionary computation, Theoretical Computer Science, 425 (2012) 17-33.
Dolgui, A., Eremeev, A., Guschinskaya, O., MIP-based GRASP and genetic algorithm for balancing transfer lines, Matheuristics. Hybridizing Metaheuristics and Mathematical Programming, Ed. by V. Maniezzo, T. Stutzle, S. Voss, Berlin, Springer-Verlag, 2010, 189-208.
Eppstein, D., The travelling salesman problem for cubic graphs, Journal of Graph Algorithms and Applications, 11 (1) (2007) 61-81.
Eremeev, A.V., On complexity of optimal recombination for the travelling salesman problem, Proc. of Evolutionary Computation in Combinatorial Optimization (EvoCOP 2011), LNCS, Berlin, Springer Verlag, (6622) 2011, 215-225.
Eremeev, A.V., Non-elitist genetic algorithm as a local search method, Preprint (arXiv:1307.3463v2 [cs.NE]), Cornell, Cornell University, 2013, 9 p. URL: http://arxiv.org/abs/1307.3463.
Eremeev, A.V., Kovalenko, J.V., On scheduling with technology based machines grouping, Diskretnyi analiz i issledovanie operacii, 18 (5) (2011) 54-79. (In Russian)
Eremeev, A.V., Kovalenko, J.V., On complexity of optimal recombination for one scheduling problem with setup times, Diskretnyi analiz i issledovanie operacii, 19 (3) (2012) 13-26. (In Russian)
Garey, M., Johnson, D., Computers and intractability. A guide to the theory of NP-completeness, W.H. Freeman and Company, San Francisco, CA, 1979.
Hazir, O., Gunalay, Y., Erel, E., Customer order scheduling problem: A comparative metaheuristics study, International Journal of Advanced Manufacturing Technology, 37 (2008) 589-598.
Held, M., Karp, R.M., A dynamic programming approach to sequencing problems, SIAM Journal on Applied Mathematics, 10 (1962) 196-210.
Holland, J., Adaptation in natural and artificial systems, Ann Arbor, University of Michigan Press, 1975.
Itai, A., Papadimitriou, C.H., Szwarc ter, J.L., Hamilton paths in grid graphs, SIAM Journal on Computing, 11 (4) (1982) 676-686.
Karp, R.M., Reducibility among combinatorial problems, Proc. of a Symp. on the Complexity of Computer Computations, Ed by R.E. Miller and J.W. Thatcher, The IBM Research Symposia Series, New York, NY, Plenum Press, 1972, 85-103.
Kovalenko, J.V., Complexity of some scheduling problems and evolutionary algorithms of their solution, Dissertation of Cand. of Sci., Novosibirsk, Sobolev Institute of Mathematics SB RAS, 2013. (In Russian)
Moscato, P., NP Optimization Problems, approximability and evolutionary computation: from practice to theory, Ph.D. dissertation, Campinas, University of Campinas, 2001.
Reeves, C.R., Genetic algorithms for the operations researcher, INFORMS Journal on Computing, 9 (3) (1997) 231-250.
Reingold, E.M., Nievergelt, J., Deo, N., Combinatorial algorithms: Theory and practice, Englewood Cliffs, Prentice-Hall, 1977.
Serdyukov, A.I., On travelling salesman problem with prohibitions, Upravlyaemye systemi, 17 (1978) 80-86. (In Russian)
Tanaev, V.S., Kovalyov, M.Y., Shafransky, Y.M., Scheduling Theory. Group Technologies, Minsk, Institute of Technical Cybernetics NAN of Belarus, 1998. (In Russian)
Whitley, D., Hains, D., Howe, A., A hybrid genetic algorithm for the travelling salesman problem using generalized partition crossover, Proc. of 11th Int. Conf. on Parallel Problem Solving from Nature, LNCS, Berlin, Springer, (6238) 2010, 566-575.
Yagiura, M., Ibaraki, T., The use of dynamic programming in genetic algorithms for permutation problems, European Journal of Operational Research, 92 (1996) 387-401.
Downloads
Published
Issue
Section
License
Copyright (c) 2014 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
