QRAFDA ƏN QISA YOLUN AXTARIŞI MƏSƏLƏSİNDƏ DƏYİŞƏN ƏMƏLİYYATLAR ƏSASINDA EVRİSTİK METODLARIN HƏLLİ KEYFİYYƏTİNİN MÜQAYİSƏSİ - İnformasiya Texnologiyaları Problemləri

QRAFDA ƏN QISA YOLUN AXTARIŞI MƏSƏLƏSİNDƏ DƏYİŞƏN ƏMƏLİYYATLAR ƏSASINDA EVRİSTİK METODLARIN HƏLLİ KEYFİYYƏTİNİN MÜQAYİSƏSİ - İnformasiya Texnologiyaları Problemləri

QRAFDA ƏN QISA YOLUN AXTARIŞI MƏSƏLƏSİNDƏ DƏYİŞƏN ƏMƏLİYYATLAR ƏSASINDA EVRİSTİK METODLARIN HƏLLİ KEYFİYYƏTİNİN MÜQAYİSƏSİ - İnformasiya Texnologiyaları Problemləri

QRAFDA ƏN QISA YOLUN AXTARIŞI MƏSƏLƏSİNDƏ DƏYİŞƏN ƏMƏLİYYATLAR ƏSASINDA EVRİSTİK METODLARIN HƏLLİ KEYFİYYƏTİNİN MÜQAYİSƏSİ - İnformasiya Texnologiyaları Problemləri

QRAFDA ƏN QISA YOLUN AXTARIŞI MƏSƏLƏSİNDƏ DƏYİŞƏN ƏMƏLİYYATLAR ƏSASINDA EVRİSTİK METODLARIN HƏLLİ KEYFİYYƏTİNİN MÜQAYİSƏSİ - İnformasiya Texnologiyaları Problemləri
QRAFDA ƏN QISA YOLUN AXTARIŞI MƏSƏLƏSİNDƏ DƏYİŞƏN ƏMƏLİYYATLAR ƏSASINDA EVRİSTİK METODLARIN HƏLLİ KEYFİYYƏTİNİN MÜQAYİSƏSİ - İnformasiya Texnologiyaları Problemləri
AZƏRBAYCAN MİLLİ ELMLƏR AKADEMİYASI

№1, 2020

QRAFDA ƏN QISA YOLUN AXTARIŞI MƏSƏLƏSİNDƏ DƏYİŞƏN ƏMƏLİYYATLAR ƏSASINDA EVRİSTİK METODLARIN HƏLLİ KEYFİYYƏTİNİN MÜQAYİSƏSİ

Vatutin Eduard İ., Panişev Vladimir S., Qvozdeva Svetlana N., Titov Vitaliy S.

Məqalə qrafda ən qısa yolun axtarışı məsələsində mövcud həllərin modifikasiyası əsasında evristik iterasiya metodlarının effektivliyinin öyrənilməsinə həsr edilmişdir. Məqalədə baxılan metod qrupunun qısa təsviri verilmişdir. Təşkil olunmuş hesablama sınağı verilmiş parametrlərlə psevdotəsadüfi qrafların seçiminin formalaşdırılmasına və BOINC platformasında könüllü paylanmış hesablamalardan istifadə etməklə həllərin axtarışının təşkilinə əsaslanmışdır. Məqalədə məsələnin ölçüsündən və məhdudiyyət gücündən asılı olaraq seçilmiş metod qrupundan alınmış eksperimental nəticələrin ətraflı təsviri verilmişdir. Alınmış eksperimental nəticələr belə bir nəticəyə gəlməyə imkan verir ki, hissəcik sürüsü metodları, təsadüfi dolaşma, yanma təqlidi və arı sürüsü metodları seçilmiş məsələnin həllində səmərəli deyil və həllərin keyfiyyəti üzrə qarışqa sürüsü və genetik alqoritm metodlarından əhəmiyyətli dərəcədə geridə qalır (səh.3-15).

Açar sözlər: evristik metodlar, genetik alqoritmlər, hissəcik sürüsü metodu, təsadüfi dolaşma metodu, yanma təqlidi metodu, arı sürüsü metodu, qrafda ən qısa yolun axtarışı, diskret kombinator optimallaşdırma, BOINC.
DOI : 10.25045/jpit.v11.i1.01
Ədəbiyyat
  • Rosen K.H. et al. Handbook of discrete and combinatorial mathematics. CRC Press, New York, 2000, 768 p.
  • Vatutin E.I., Titov V.S., Emelyanov S.G. Basics of discrete combinatorial optimization (in Russian). M.: Argamac-Media, Moscow, 2016, 270 p.
  • Karpenko A.P. Modern algorithms of search optimization. Algorithms inspired by nature (in Russian). M.: Bauman Moscow State Technical University, 2014, 446 p.
  • Prim R.C. Shortest connection networks and some generalizations // Bell System Technical Journal, 1957, vol. 36, no 6, pp. 1389–1401. DOI: 10.1002/j.1538-7305.1957.tb01515.x
  • Kruskal J.B. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 1956, vol. 7, pp. 48–50. 
    DOI: 10.1090/S0002-9939-1956-0078686-7
  • Kuhn H.W. Variants of the Hungarian method for assignment problems. Naval Research Logistics Quarterly. 1956. pp. 253–258. DOI: 10.1002/nav.3800030404
  • Munkres J. Algorithms for the Assignment and Transportation Problems // Journal of the Society for Industrial and Applied Mathematics, 1957, vol. 1, no. 5, pp. 32–38. DOI: 10.1137/0105003
  • Land A.H., Doig A.G. An Automatic Method of Solving Discrete Programming Problems. Econometrica, 1960, vol. 28, pp. 497–520. DOI: 10.2307/1910129
  • Colbourn C.J., Dinitz J.H. Handbook of Combinatorial Designs, 2nd ed. (Discrete Mathematics and Its Applications). New York: Chapman & Hall/CRC, 2006, 1026 p.
  • Zaikin O.S., Kochemazov S.E., Semenov A.A. SAT-based search for systems of diagonal Latin squares in volunteer computing project SAT@home / 39th international convention on information and communication technology, electronics and microelectronics (MIPRO 2016). 2016, pp. 277–281. DOI: 10.1109/MIPRO.2016.7522152
  • Vatutin E.I., Dremov E.N., Martynov I.A., Titov V.S. Weighted random search method for discrete combinatorial problems solving (in Russian) // Proceedings of Volgograd State Technical University. Series: Electronics, Measuring Equipment, Radiotechnics and Communication, 2014, № 10 (137). 9, pp. 59–64.
  • Dorigo M. Optimization, Learning and Natural Algorithms. PhD thesis. Milan: Politecnico di Milano, 1992.
  • Vatutin E.I., Titov V.S. Analysis of results of ant colony optimization method in the problem of getting shortest path in graph with constraints (in Russian) // Proceedings of South State University. Technical sciences. 2014, № 12 (161), pp. 111–120.
  • Glover F., Kochenberger G.A. Handbook of Metaheuristics. New York: Kluwer Academic Publishers, 2003, 756 p.
  • Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by Simulated Annealing. Science, 1983, vol. 220, no. 4598, pp. 671–680. DOI: 10.1126/science.220.4598.671
  • Karaboga D.D. An Idea Based On Honey Bee Swarm for Numerical Optimization. Technical Report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.
  • Pham D.T., Ghanbarzadeh A., Koc E., Otri S., Rahim S., Zaidi M. The Bees Algorithm. Technical Note, Manufacturing Engineering Centre, Cardiff University, 2005.
  • Kennedy J., Eberhart R. Particle Swarm Optimization / Proceedings of IEEE International Conference on Neural Networks. 1995, pp. 1942–1948. DOI: 10.1109/ICNN.1995.488968
  • Vatutin E.I., Titov V.S. Investigation of Features of Particle Swarm Optimization Method in Graph Shortest Path Problem with Constraints (in Russian) // Herald of computer and information technologies, 2018, no. 5 (167), pp. 26–34. DOI: 0.14489/vkit.2018.05.pp.026–034
  • Vatutin E.I. Comparison of Decisions Quality of Heuristic Methods with Sequential Formation of the Decision in the Graph Shortest Path Problem / CEUR Workshop Proceedings. Proceedings of the Third International Conference BOINC-based High Performance Computing: Fundamental Research and Development (BOINC: FAST 2017). Technical University of Aachen, Germany, 2017, pp. 67–76.
  • Vatutin E.I. Comparison of Decisions Quality of Heuristic Methods with Limited Depth-First Search Techniques in the Graph Shortest Path Problem // Open Engineering, 2017, vol. 7, no 1, pp. 428–434. DOI: 10.1515/eng-2017-0041
  • Dijkstra E.W. A note on two problems in connexion with graphs. Numerische Mathematik, 1959, vol. 1., pp. 269–271.
  • Vatutin E.I., Valyaev S.Yu., Titov V.S. Comparison of Sequential Methods for Getting Separations of Parallel Logic Control Algorithms Using Volunteer Computing / CEUR Workshop Proceedings. Proceedings of the Second International Conference BOINC-based High Performance Computing: Fundamental Research and Development (BOINC: FAST 2015). 2015, vol. 1502, pp. 37–51. urn:nbn:de:0074-1502-3
  • Vatutin E.I., Titov V.S. Analisys of the areas of qualitative superiority of the sequential heuristic methods for getting separation during logic multicontrollers design (in Russian). Proceedings of the Higher Educational Institutions. Instrument Making, 2015, vol. 58, no 2, pp. 115–122. DOI: 10.17586/0021-3454-2015-58-2-115-122
  • Anderson D.P. BOINC: a system for public-resource computing and storage / Fifth IEEE/ACM International Workshop on Grid Computing, 2004. DOI: 10.1109/GRID.2004.14
  • Vatutin E.I., Titov V.S. Parametric optimization of simulated annealing algorithm at the shortest path problem (in Russian) // Proceedings of Cherepovets State University, 2015, no 6 (67), pp.13–16.
  • Vatutin E.I., Titov V.S. The features of use genetic algorithm in the problem of finding the shortest path in the graph with graph density constraint (in Russian) // Multicore processors, parallel programming, FPGA, signal processing systems. Barnaul: Altay State University, 2016. pp.152–159.
  • Vatutin E.I., Titov V.S. Features of meta-optimization of the bee colony method in the shortest path problem with constraints on the graph density (in Russian) // Proceedings of Southwest State University. Series: Control, Computer Science, Informatics. Medical Devices, 2016, no 2 (19), pp. 52–65.
  • Hamming R.W. Error detecting and error correcting codes // Bell System Technical Journal. 1950, vol. 29, pp. 147–160. DOI: 10.1002/j.1538-7305.1950.tb00463.x.
  • Levenstein V.I. Binary codes with correction of fallouts, inserts and substitutions of symbols (in Russian) // Proceedings of Academies of Sciences of the USSR, 1965, vol. 163, no 4. pp. 845–848.
  • Kurochkin I.I. Determination of Replication Parameters in the Project of the Voluntary Distributed Computing Netmax@Home // Science. Business. Society, 2016, vol. 2, pp.10–12.
  • Nikitina N.N., Ivashko E.E. The Price of Anarchy in a Game for Drug Discovery. Networking Games and Management Extended abstracts. 2016, pp. 24–25.
  • Vatutin E.I., Martynov I.A., Titov V.S. Method of Workaround deadlocks for solving discrete combinatorial optimization problems with constraints (in Russian) // Perspective information technologies. Samara, Samara scientific center of RAS, 2014, pp. 313–317.