Том 18, номер 1, 2011 г., Стр. 27-40

УДК 519.854
Еремеев А. В.
О сложности оптимальной рекомбинации для задачи коммивояжёра

Аннотация:
Рассматривается вычислительная сложность оптимальной рекомбинации для задачи коммивояжёра в симметрическом и общем случаях. Доказана NP-трудность этих задач в сильном смысле, и рассмотрены подходы к их решению.
Ил. 3, библиогр. 15.

Ключевые слова: задача коммивояжёра, генетический алгоритм, оптимальная рекомбинация, вычислительная сложность, сводимость задач.

Еремеев Антон Валентинович ¹
1. Омский филиал Института математики им. С. Л. Соболева СО РАН,
ул. Певцова, 13, 644099 Омск, Россия
е-mail: eremeev@ofim.oscsbras.ru

Статья поступила 2 августа 2010 г.
Исправленный вариант — 18 октября 2010 г.

Литература

[1] Борисовский П. А., Еремеев А. В. Генетический алгоритм для задачи о вершинном покрытии графа // Математика и информатика: наука и образование. Вып. 7. — Омск: ОмГПУ, 2008. — C. 49–54.

[2] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982. — 416 c.

[3] Agarwal C. C., Orlin J. B., Tai R. P. Optimized crossover for the independent set problem // Working paper # 3787-95. — Cambridge, MA: Mas?sachusetts Institute of Technology, 1995. — 17 p.

[4] Balas E., Niehaus W. Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems // J. Heuristics. — 1998. — Vol. 4, N 2 — P. 107–122.

[5] Borisovsky P., Dolgui A., Eremeev A. Genetic algorithms for a supply management problem: MIP-recombination vs greedy decoder // Europ. J. Oper. Res. — 2009. — Vol. 195, N 3. — P. 770–779.

[6] Cook W., Seymour P. Tour merging via branch-decomposition // INFORMS J. Computing. — 2003. — Vol. 15, N 2. — P. 233–248.

[7] Cotta C., Alba E., Troya J. M. Utilizing dynastically optimal forma recombination in hybrid genetic algorithms // Proc. 5th Int. Conf. on Parallel Problem Solving from Nature. — Berlin: Springer-Verl., 1998. — P. 305–314. (Lect. Notes Comput. Sci.; Vol. 1498.)

[8] Dolgui A., Eremeev A., Guschinskaya O. MIP-based GRASP and genetic algorithm for balancing transfer lines // Matheuristics. Hybridizing metaheuristics and mathematical programming. — Berlin: Springer-Verl.,
2010. — P. 189–208.

[9] Eppstein D. The traveling salesman problem for cubic graphs // J. Graph Algorithms Appl. — 2007. — Vol. 11, N 1. — P. 61–81.

[10] Eremeev A. V. On complexity of optimal recombination for binary representations of solutions // Evolutionary Computation. — 2008. — Vol. 16, N 1. — P. 127–147.

[11] Held M., Karp R. M. A dynamic programming approach to sequencing problems // J. Soc. Ind. Appl. Math. — 1962. — Vol. 10. — P. 196–210.

[12] Itai A., Papadimitriou C. H., Szwarcfiter J. L. Hamilton paths in grid graphs // SIAM J. Computing. — 1982. — Vol. 11, N 4. — P. 676–686.

[13] Reeves C. R. Genetic algorithms for the operations researcher // INFORMS J. Comput. — 1997. — Vol. 9, N 3. — P. 231–250.

[14] Whitley D., Hains D., Howe A. A hybrid genetic algorithm for the traveling salesman problem using generalized partition crossover // Proc. 11th Int. Conf. on Parallel Problem Solving from Nature. — Berlin: Springer-Verl., 2010. — P. 566–575. (Lect. Notes Comput. Sci.; Vol. 6238.)

[15] Yagiura M., Ibaraki T. The use of dynamic programming in genetic algorithms for permutation problems // Europ. J. Oper. Res. — 1996. — Vol. 92. — P. 387–401.