All
 
|
 
 


Probabilistic Prediction of the Complexity of Traveling Salesman Problems Based on Approximating the Complexity Distribution from Experimental Data
 
PIIS000523100000273-4-1
DOI10.31857/S000523100000273-4
Publication type Article
Status Published
Authors
Michael Fomichev 
Affiliation: National Research University Higher School of Economics
Address: Russian Federation
Vasily Goloveshkin
Affiliation:
Moscow Technological University
Institute of Applied Mechanics
Michael Ulyanov
Affiliation:
Institute of Control Sciences, Russian Academy of Sciences
Lomonosov State University
Address: Russian Federation
Galina Zhukova
Affiliation: National Research University Higher School of Economics
Address: Russian Federation
Journal nameAvtomatika i Telemekhanika
EditionIssue 7
Pages149-167
Abstract

We show the results of a statistical study of the complexity of the asymmetric traveling salesman problem (ATSP) obtained by processing a specially generated pool of matrices. We show that the normal distribution can serve as an approximation to the distribution of the logarithm of complexity for a fixed problem dimension. We construct a family of probability distributions that represent satisfactory approximations of the complexity distribution with a dimension of the cost matrix from 20 to 49. Our main objective is to make probabilistic predictions of the complexity of individual problems for larger values of the dimension of the cost matrix. We propose a representation of the complexity distribution that makes it possible to predict the complexity. We formulate the unification hypothesis and show directions for further study, in particular proposals on the task of clustering “complex” and “simple” ATSP problems and proposals on the task of directly predicting the complexity of a specific problem instance based on the initial cost matrix.

 
KeywordsTraveling salesman problem, complexity of an individual traveling salesman problem, approximations of probability distributions, quantile skewness, quantile kurtosis, probabilistic prediction
Received29.09.2018
Publication date29.09.2018
Number of characters993
Cite   Download pdf To download PDF you should sign in
Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной

views: 1589

Readers community rating: votes 0 

1. Ul'yanov M.V. Resursno-ehffektivnye komp'yuternye algoritmy. Razrabotka i analiz M.: FIZMATLIT, 2008.
2. Oliver I.M., Smith D.J., Holland J.R.C. A Study of Permutation Crossover Operators on the Traveling Salesman Problem // Proc. 2nd Int. Conf. on Genetic Algorithms. Hillsdale, N.J.: Lawrence Erlbaum Associates, 1987. P. 224–230.
3. Cotta C., Aldana J.F., Nebro A.J., Troya J.M. Hybridizing Genetic Algorithms with Branch and Bound Techniques for the Resolution of the TSP / Artificial Neural Nets and Genetic Algorithm. Pearson D., Steele N., Albrecht R. (Eds.), Wien, N.Y.: Springer-Verlag, 1995. P. 277–280.
4. Goldberg D.E., Lingle R. Alleles, Loci, and the Travelling Salesman Problem // Proc. 1st Int. Conf. on Genetic Algorithms (ICGA’85). Hillsdale, N.J.: Lawrence Erlbaum Associates, 1985. P. 154–159.
5. Sergeev S. Nonlinear Resolving Functions for the Travelling Salesman Problem // Autom. Remote Control. 2013. V. 74. No. 6. P. 978–994.
6. Sergeev S. The Symmetric Travelling Salesman Problem. II // Autom. Remote Control. 2010. V. 71. No. 4. P. 681–696.
7. Chang-Chien Chou. On the Shortest Path Touring n Circles // Int. J. Advancement Comput. Technol. 2012. V. 4. No. 10. P. 356–364.
8. Toriello A. Optimal Toll Design: A Lower Bound Framework for the Asymmetric Traveling Salesman Problem // Math. Programm. 2014. V. 144. No. 1/2. P. 247–264.
9. Khachaj M.Yu., Neznakhina E.D. Priblizhennye skhemy dlya obobschennoj zadachi kommivoyazhera // Tr. IMM UrO RAN. 2016. No. 22:3. S. 283–292.
10. Khachaj M.Yu., Dubinin R.D. Approksimiruemost' zadachi ob optimal'noj marshrutizatsii transporta v konechnomernykh evklidovykh prostranstvakh // Tr. IMM UrO RAN. 2016. № 22:2. S. 292–303.
11. Knuth D.E. Estimating the Efficiency of Backtracking Programs // Math. Comput. 1975. V. 29. P. 121–136.
12. Cornu´ejols G., Karamanov M., Li Y. Early Estimates of the Size of Branch-andBound Trees // INFORMS J. Comput. 2006. V. 18. No. 1. P. 86–96.
13. Lobjois L., Lemaitre M. Branch-and-Bound Algorithm Selection by Performance Prediction // Amer. Associat. Artific. Intelligence, Menlo Park, CA, 1998.
14. Purdom P.W. Tree Size by Partial Backtracking // SIAM J. Comput. 1978. V. 7. No. 4. P. 481–491.
15. Little J.D.C., Murty K.G., Sweeney D.W., Karel C. An Algorithm for the Traveling Salesman Problem // Oper. Res. 1963. No. 11. P. 972–989.
16. Ulyanov M.V., Fomichev M.I. Resource Characteristics of Ways to Organize a Decision Tree in the Branch-and-Bound Method for the Traveling Salesmen Problem // Biznes–informatika. 2015. № 4(34). C. 38–46.
17. Goloveshkin V.A., Zhukova G.N., Ul'yanov M.V., Fomichev M.I. Sravnenie resursnykh kharakteristik traditsionnogo i modifitsirovannogo metoda vetvej i granits dlya TSP // Sovremen. inform. tekhnologii i IT-obrazovanie. 2015. T. 2. № 11. C. 151–159.
18. Kramer G. Matematicheskie metody statistiki. M.: Mir, 1975.
19. Pearson K. Contributions to the Mathematical Theory of Evolution. III // Phil. Trans. Royal Soc. London. 1896. V. 187. P. 253–318.
20. Goloveshkin V.A., Zhukova G.N., Ul'yanov M.V., Fomichev M.I. Raspredelenie logarifma slozhnosti individual'nykh zadach kommivoyazhera pri fiksirovannoj dline vkhoda // Sovremen. inform. tekhnologii i IT-obrazovanie. 2016. T. 12. № 3. Ch. 2. C. 131–137.
21. Goloveshkin V.A. , Zhukova G.N., Ul'yanov M.V., Fomichev M.I. Ispol'zovanie kvantil'nykh koehffitsientov asimmetrii i ehkstsessa dlya otsenki slozhnosti resheniya zadachi kommivoyazhera // Int. J. Open Inform. Technol. 2016. T. 4. № 12. C. 7–12.
22. Zhukova G.N. Identifikatsiya veroyatnostnogo raspredeleniya po koehffitsientam asimmetrii i ehkstsessa // Avtomatizatsiya. Sovremennye tekhnologii. 2016. № 5. C. 26–33.
23. Moors J.J.A. A Quantile Alternative for Kurtosis // The Statist. 1988. V. 37. P. 25-32.
24. Moors J.J.A., Coenen V.M.J., Heuts R.M.J. Limiting Distributions of Moment- and Quantile-based Measures for Skewness and Kurtosis // School Econom. Management, Tilburg Univer., Res. Mem. FEW 620, 1993.
25. Moors J.J.A., Wagemakers R.Th.A., Coenen V.M.J., et al. Characterizing Systems of Distributions by Quantile Measures // Statist. Neerlandica, 1996. V. 50. No. 3. P. 417–430.

Система Orphus

Loading...
Up