Обговорення:Локальний пошук (оптимізація)

Матеріал з Вікіпедії — вільної енциклопедії.
Найсвіжіший коментар: Dzyadyk у темі «David S. Johnson» 8 років тому
Перейти до навігації Перейти до пошуку

David S. Johnson[ред. код]

Найсвіжіший коментар: 8 років тому1 коментар1 особа в обговоренні

David S. Johnson[en]. Local optimization and the Traveling Salesman Problem. Date: 27 June 2005 // Volume 443 of the series en:Lecture Notes in Computer Science pp. 446-461.

Preview
Abstract

The Traveling Salesman Problem (TSP) is often cited as the prototypical “hard” combinatorial optimization problem. As such, it would seem to be an ideal candidate for nonstandard algorithmic approaches, such as simulated annealing, and, more recently, genetic algorithms. Both of these approaches can be viewed as variants on the traditional technique called local optimization. This paper surveys the state of the art with respect to the TSP, with emphasis on the performance of traditional local optimization algorithms and their new competitors, and on what insights complexity theory does, or does not, provide.

References
  1. J. L. Bentley, “Experiments on traveling salesman heuristics,” in Proc. 1st Ann. ACM-SIAM Symp. on Discrete Algorithms, SIAM, Philadelphia, PA, 1990, 91–99.
  2. J. L. Bentley, “Fast algorithms for geometric traveling salesman problems,” in preparation.
  3. J. L. Bentley, D. S. Johnson, L. A. McGeoch, and E. E. Rothberg, “Near-optimal solutions to very large traveling salesman problems,” in preparation.
  4. R. G. Bland and D. F. Shallcross, “Large traveling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation,” Operations Res. Lett.8 (1989), 125–128.
  5. R. M. Brady, “Optimization strategies gleaned from biological evolution,” Nature317 (October 31, 1985), 804–806.
  6. N. E. Collins, R. W. Eglese, and B. L. Golden, “Simulated Annealing: An Annotated Bibliography,” Amer. J. Math. & Mgmt. Sci.8 (1988), 205–307.
  7. V. Cerny, “A Thermodynamical Approach to the Travelling Salesman Problem: An Efficient Simulation Algorithm,” J. Optimization Theory and Appl.45 (1985), 41–51.
  8. N. Christofides, “Worst-case analysis of a new heuristic for the travelling salesman problem,” Report No. 388, GSIA, Carnegie-Mellon University, Pittsburgh, PA, 1976.
  9. G. Dueck, “Threshold Accepting: A general purpose optimization algorithm appearing superior to simulated annealing,” TR88.10.011, Heidelberg Scientific Center, IBM Germany, 1988.
  10. R. Durbin and D. Willshaw, “An analogue approach to the travelling salesman problem using an elastic net method,” Nature326 (April 16, 1987), 689–691.
  11. M. R. Garey, and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, San Francisco, 1979.
  12. F. Glover, “Tabu search — Part I,” ORSA J. Comput.1 (1989), 190–206.
  13. M. Grötschel and O. Holland, “Solution of large-scale symmetric travelling salesman problems,” Report No. 73, Institut für Mathematik, Universität Augsburg, 1988.
  14. M. Held and R. M. Karp, “The traveling-salesman problem and minimum spanning trees,” Operations Res.18 (1970), 1138–1162.
  15. M. Held and R. M. Karp, “The traveling-salesman problem and minimum spanning trees: Part II,” Math. Programming1 (1971), 6–25.
  16. J. J. Hopfield and D. W. Tank, “'Neural’ computation of decisions in optimization problems,” Biol. Cybern52 (1985), 141–152.
  17. D. S. Johnson, “More approaches to the travelling salesman guide,” Nature330 (December 10, 1987), 525.
  18. D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon, “Optimization by Simulated Annealing: An Experimental Evaluation, Part I (Graph Partitioning),” Operations Res.37 (1989), 865–892.
  19. D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon, “Optimization by Simulated Annealing: An Experimental Evaluation, Part III (The Traveling Salesman Problem),” in preparation.
  20. D. S. Johnson, L. A. McGeoch, and G. Ostheimer, “Data structures for traveling salesmen,” in preparation.
  21. D. S. Johnson, C. H. Papadimitriou, and M. Yannakakis, “How easy is local search?,” J. Comput. System Sci.37 (1988), 79–100.
  22. D. S. Johnson and E. E. Rothberg, “Asymptotic experimental analysis of the Held-Karp lower bound for the traveling salesman problem,” in preparation.
  23. R. M. Karp, “Probabilistic analysis of partitioning algorithms for the traveling-salesman in the plane,” Math. Oper. Res.2 (1977), 209–224.
  24. W. Kern, “A probabilistic analysis of the switching algorithm for the Euclidean TSP,” Math. Programming44 (1989), 213–219.
  25. S. Kirkpatrick, “Optimization by simulated annealing: Quantitative studies,” J. Stat. Physics34 (1984), 976–986.
  26. S. Kirkpatrick, C. D. Gelatt, Jr, and M. P. Vecchi, “Optimization by Simulated Annealing,” Science220 (13 May 1983), 671–680.
  27. S. Kirkpatrick and G. Toulouse, “Configuration space and the travelling salesman problem,” J. Physique46 (1985), 1277–1292.
  28. B. Korte, “Applications of combinatorial optimization,” talk at the 13th International Mathematical Programming Symposium, Tokyo, 1988.
  29. W. Krauth and M. Mézard, “The cavity method and the travelling-salesman problem,” Europhys. Lett.8 (1989), 213–218.
  30. J. Lam and J.-M. Delosme, “An efficient simulated annealing schedule: implementation and evaluation,” manuscript (1988).
  31. E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, The Traveling Salesman Problem, John Wiley & Sons, Chichester, 1985.
  32. S. Lin, “Computer solutions of the traveling salesman problem,” Bell Syst. Tech. J.44 (1965), 2245–2269.
  33. S. Lin and B. W. Kernighan, “An Effective Heuristic Algorithm for the Traveling-Salesman Problem,” Operations Res.21 (1973), 498–516.
  34. J. D. Litke, “An improved solution to the traveling salesman problem with thousands of nodes,” Comm. ACM27 (1984), 1227–1236.
  35. G. Lueker, manuscript, Princeton University, 1976.
  36. O. Martin, S. W. Otto, and E. W. Felten, “Large-step Markov chains for the traveling salesman problem,” manuscript (1989).
  37. D. Mitra, F. Romeo, and A. Sangiovanni-Vincentelli, “Convergence and finite-time behavior of simulated annealing,” J. Advan. Appl. Prob.18 (1986), 747–771.
  38. H. Mühlenbein, “The dynamics of evolution and learning — Towards genetic neural networks,” manuscript (1989).
  39. H. Mühlenbein, M. Gorges-Schleuter, and O. Krämer, “Evolution algorithms in combinatorial optimization,” Parallel Comput.7 (1988), 65–85.
  40. M. Padberg and G. Rinaldi, “Optimization of a 532-city symmetric traveling salesman problem by branch and cut,” Operations Res. Lett.6 (1987), 1–7.
  41. M. Padberg and G. Rinaldi, “A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems,” Report R. 247, Istituto di Analisi dei Sistimi ed Informatica del CNR, Rome, 1988.
  42. C. H. Papadimitriou, “The complexity of the Lin-Kernighan heuristic for the traveling salesman problem,” manuscript (1990).
  43. C. H. Papadimitriou and K. Steiglitz, “On the complexity of local search for the traveling salesman problem,” SIAM J. Comput.6 (1977), 76–83.
  44. C. H. Papadimitriou and K. Steiglitz, “Some examples of difficult traveling salesman problems,” Operations Res.26 (1978), 434–443.
  45. L. K. Platzman and J. J. Bartholdi, III, “Spacefilling curves and the planar travelling salesman problem,” J. Assoc. Comput. Mach.36 (1989), 719–737.
  46. D. J. Rosenkrantz, R. E. Stearns, and P. M. Lewis, II, “An analysis of several heuristics for the traveling salesman problem,” SIAM J. Comput.6 (1977), 563–581.
  47. S. Sahni and T. Gonzalez, “P-complete approximation problems,” J. Assoc. Comput. Mach.23 (1976), 555–565.
  48. G. H. Sasaki and B. Hajek, “The time complexity of maximum matching by simulated annealing,” J. Assoc. Comput. Mach.35 (1988), 387–403.
  49. H. S. Stone, private communication (1989).

— Юрій Дзядик (о•в) 13:20, 15 січня 2016 (UTC).Відповісти

Отримано з https://uk.wikipedia.org/w/index.php?title=Обговорення:Локальний_пошук_(оптимізація)&oldid=17469095