Article

Article title ANALYSIS OF THE RESULTS OF APPLYING THE ANT COLONY OPTIMIZATION ALGORITHM TO THE SHORTEST PATH PROBLEM IN THE GRAPHS WITH CONSTRAINTS
Authors E.I. Vatutin, V.S. Titov
Section SECTION II. MATHEMATICAL AND SOFTWARE OF SUPERCOMPUTERS
Month, Year 12, 2014 @en
Index UDC 681.3
DOI
Abstract The article describes an ant colony optimization algorithm applied to the solution of combinatorial optimization problems by the example of the problem of finding the shortest path in the graph. A number of modifications compared to the classical mathematical model M. Dorigo, which reduce the computational cost in finding solutions and improve its quality during parametric optimization (metaoptimization), are described. Proposed a method for comparing the quality of decisions based on the calculation of a number of indicators (average quality of decisions mark, deviation from optimal decision quality, probability of find decision, probability of find optimal decision) using in the process of comparison of different known heuristic methods. The results of comparing the quality of solutions with known methods for graphs with different numbers of nodes (different size of a problem) and different densities are given.

Download PDF

Keywords Discrete combinatorial optimization; ant colony optimization; graph theory; shortest path problem; heuristic methods.
References 1. Available at: https://ru.wikipedia.org/wiki/ Равенство_классов_P_и_NP.
2. Valyaev V.V., Vatutin E.I. Metod opredeleniya izomorfizma grafov obshchego vida za polinomial'noe vremya [The method of determining the isomorphism of graphs of the General form in polynomial time], Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta. Seriya: Upravlenie, vychislitel'naya tekhnika, informatika. Meditsinskoe priborostroenie [News of the South-Western state University. Series: Management, computer engineering, computer science. Medical instrumentation], 2012, No. 2, Part 1, pp. 200-206.
3. Vatutin E.I. Proektirovanie logicheskikh mul'tikontrollerov. Sintez razbieniy parallel'nykh graf-skhem algoritmov [Designing logical Multicontroller. Synthesis of separations of parallel graph-schemes of algorithms]. Saarbrucken: Lambert Academic Publishing, 2011, 292 p.
4. Vatutin E.I., Zotov I.V. Metod formirovaniya suboptimal'nykh razbieniy parallel'nykh upravlyayushchikh algoritmov [A method of forming a suboptimal splits parallel logic control algorithms], Parallel'nye vychisleniya i zadachi upravleniya PACO’04 [Parallel computing and control problems PACO’04]. Moscow: IPU RAN, 2004, pp. 884-917.
5. Dorigo M. Optimization, Learning and Natural Algorithms, PhD thesis. Politecnico di Milano, Italie, 1992.
6. Dijkstra E.W. A note on two problems in connexion with graphs, Numerische Mathematik, 1959, Vol. 1, pp. 269-271.
7. Zykov A.A. Osnovy teorii grafov [Fundamentals of graph theory]. Moscow: Nauka, 1986, 384 p.
8. Vatutin E.I., Dremov E.N., Martynov I.A., Titov V.S. Metod vzveshennogo sluchaynogo perebora dlya resheniya zadach diskretnoy kombinatornoy optimizatsii [The method of weighted random search for solving problems of discrete combinatorial optimization], Izvestiya Volgogradskogo gosudarstvennogo tekhnicheskogo universiteta. Seriya: Elektronika, izmeritel'naya tekhnika, radiotekhnika i svyaz' [News of Volgograd state technical University. Series: electronics and instrumentation engineering, radio engineering and communication], 2014, No. 10 (137), Issue 9, pp. 59-64.
9. Vatutin E.I., Martynov I.A., Titov V.S. Sposob obkhoda tupikov pri reshenii zadach diskretnoy optimizatsii s ogranicheniyami [The method of avoiding deadlocks when solving discrete optimization with constraints], Perspektivnye informatsionnye tekhnologii (PIT-2014) [Advanced information technology (PIT 2014)]. Samara: Izd-vo Samarskogo nauchnogo tsentra RAN, 2014, pp. 313-317.
10. Vatutin E.I., Kolyasnikov D.V., Martynov I.A., Titov V.S. Metod sluchaynogo perebora v zadache postroeniya razbieniy graf-skhem parallel'nykh algoritmov [The method of random search in the task of building a splits graph-schemes of parallel algorithms], Mnogoyadernye protsessory, parallel'noe programmirovanie, PLIS, sistemy obrabotki signalov [Multi-core processors, parallel
programming, FPGA, signal-processing system]. Barnaul, 2014, pp. 115-125.
11. Vatutin E.I., Valyaev S.Yu., Dremov E.N., Martynov I.A., Titov V.S. Raschetnyy modul' dlya testirovaniya kombinatornykh optimizatsionnykh algoritmov v zadache poiska kratchayshego
puti v grafe s ispol'zovaniem dobrovol'nykh raspredelennykh vychisleniy [Calculating unit for testing combinatorial optimization algorithms in the task of finding the shortest path in a graph using voluntary distributed computing], Svidetel'stvo o gosudarstvennoy registratsii
programmy dlya EVM № 2014619797 ot 22.09.14.

Comments are closed.