Clustering of situations in solving applied optimization problems (on the examples of traveling salesman problem and distance matrix recovery)

Boris Melnikov, Anastasia Nichiporchuk, Marina Trenina, Mikhail Abramyan

Abstract


In discrete optimization problems, we apply algorithms based on extensions of the branch and bound method. These extensions consist in the joint work of several auxiliary heuristic algorithms, they can be referred to different, independent from each other, areas of artificial intelligence. Therefore, the relevance of the problems under consideration is provided by both subject areas and algorithms. In this paper, we investigate the possibility of using one of these auxiliary algorithms, so-called clustering of situations. As the subject areas, we consider two different discrete optimization problems: the traveling salesman problem in its classical formulation (we prefer to study its special cases obtained for the pseudogeometric version) and the problem of DNA distance matrix reconstruction. As a result of computational experiments, we obtained some regularities that allow us to create improved versions of the branch and bound algorithm – by connecting heuristics to it for clustering situations. The results obtained in computational experiments provide a rationale for the application of clustering situations in the development of algorithms using the branch and bound method. For example, for the traveling salesman problem, this application gives easily observable improvements in the algorithm, primarily for the pseudogeometric version.

Full Text:

PDF (Russian)

References


Makarkin S. B, Melnikov B. F., Trenina М. А. The approach to solving the pseudo-geometric version of the traveling salesman problem // Proceedings of Higher Educational Institutions. Volga Region. Physical and Mathematical Science. – 2015.– № 2 (34). – С. 135–147. (in Russian)

Melnikov B. F., Melnikov E. A. Some heuristic algorithms in the vertex minimization problem of nondeterministic finite automata // Stochastic optimization in computer science.– 2013. –Т. 9, No 2. – С. 73–87. (in Russian)

Melnikov B. F., Melnikov E. A. Approach to programming nondeterministic GAMES (Part I: Description of general heuristics) // Proceedings of higher educational institutions. Volga Region. Physics and mathematics. – 2013/ – № 4 (28). – С. 29–38. (in Russian)

Melnikov B. F, Davydova E. V., Nichiporchuk A. V., Trenina M. A. Clustering of situations in algorithms for solving the traveling salesman problem and its application in some applications. Part II. List metric and some related optimization problems // Proceedings of Higher Educational Institutions. Volga Region. Physical and Mathematical Science. – 2018.– № 4. https://izvuz_fmn.pnzgu.ru/fmn418. (in Russian)

Gutin G., Punnen A. P. Combinatorial Optimization. The Traveling Salesman Problem and Its Variations. – Berlin: Springer, 2007. – 830 p.

Makarkin S. B, Melnikov B. F. Geometric methods for solving the pseudo-geometric version of the traveling salesman problem // Stochastic optimization in computer science. – 2013. – Т. 9, № 2.– С. 54–72. (in Russian)

Melnikov B. Multiheuristic approach to discrete optimization problems // Cybernetics and Systems Analysis. – 2006. – Vol. 42, No. 3. – P. 335–341.

Melnikov B. F., Trenina М. А. On a problem of the reconstruction of distance matrices between DNA sequences // International Journal of Open Information Technologies. – 2018. – Vol. 6, No. 6.– C. 1–13. (in Russian)

Melnikov B. F., Trenina М. А. The application of the branch and bound method in the problem of reconstructing the matrix of distances between DNA strings // International Journal of Open Information Technologies. – 2018. – Vol. 6, No. 8. – C. 1–13. (in Russian)

Ganesh A., Lin Z., Wright J., Wu L., Chen M. Fast algorithms for recovering a corrupted low-rank matrix // Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP). 2009. – 3rd IEEE International Workshop on 2009. – pp. 213–216.

Goodman, S. Introduction to the Design and Analysis of Algorithms / S. Goodman, S. Hedetniemi – NY: McGraw-Hill; 1977. – 344 p.

Hromkovic J. Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. – Basel: Springer, 2004. – 536 p.

Melnikov B. F., Trenina М. А., Kochergin А. S. An approach to improving algorithms for calculating distances between DNA strings (using the example of the Needlman-Wunsch algorithm)// Proceedings of higher educational institutions. Volga Region. Physics and mathematics. – 2018. – № 1 (45). – С. 46–59. (in Russian)

Home – Nucleotide – NCBI [Электрон. ресурс]. – Режим доступа: https://www.ncbi.nlm.nih.gov/nuccore, свободный

Ayala, F. J., Kiger, J.F. (1980), Modern Genetics, 2nd ed., Menlo Park: University of California at Danis. – 724 p.

Applegate D. L., Bixby R. E., Chvatal V., Cook W. J. The Traveling Salesman Problem: A Computational Study. – NJ: Princeton University Press, 2007.– 593 p.

Melnikov B. F., Trenina М. А., Makarkin S. B. Using Problem Oriented Metrics for Solving Pseudo-Euclidian Travelling Salesman Problem with Euclidian Algorithms //Stochastic optimization in computer science. – 2014. – Т.10, № 1. – С. 63–71. (in Russian)

Melnikov B. F., Davydova E. V. Mathematical modeling of increasing the level of safety in case of failures of space technology // International Journal of Open Information Technologies. – 2018. – Vol. 6, No. 5. – P. 1-–6. (in Russian)

Gimadi E.H., Khachay M. Yu. Extremal problems on sets of permutations. – Yekaterinburg: publishing house of the UMTS UPI, 2016. – 220 p. (in Russian)


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162