СРАВНЕНИЕ КАЧЕСТВА РЕШЕНИЙ ЭВРИСТИЧЕСКИХ МЕТОДОВ НА БАЗЕ МОДИФИЦИРУЮЩИХ ОПЕРАЦИЙ В ЗАДАЧЕ ПОИСКА КРАТЧАЙШЕГО ПУТИ В ГРАФЕ - Проблемы Информационных Технологий

СРАВНЕНИЕ КАЧЕСТВА РЕШЕНИЙ ЭВРИСТИЧЕСКИХ МЕТОДОВ НА БАЗЕ МОДИФИЦИРУЮЩИХ ОПЕРАЦИЙ В ЗАДАЧЕ ПОИСКА КРАТЧАЙШЕГО ПУТИ В ГРАФЕ - Проблемы Информационных Технологий

СРАВНЕНИЕ КАЧЕСТВА РЕШЕНИЙ ЭВРИСТИЧЕСКИХ МЕТОДОВ НА БАЗЕ МОДИФИЦИРУЮЩИХ ОПЕРАЦИЙ В ЗАДАЧЕ ПОИСКА КРАТЧАЙШЕГО ПУТИ В ГРАФЕ - Проблемы Информационных Технологий

СРАВНЕНИЕ КАЧЕСТВА РЕШЕНИЙ ЭВРИСТИЧЕСКИХ МЕТОДОВ НА БАЗЕ МОДИФИЦИРУЮЩИХ ОПЕРАЦИЙ В ЗАДАЧЕ ПОИСКА КРАТЧАЙШЕГО ПУТИ В ГРАФЕ - Проблемы Информационных Технологий

СРАВНЕНИЕ КАЧЕСТВА РЕШЕНИЙ ЭВРИСТИЧЕСКИХ МЕТОДОВ НА БАЗЕ МОДИФИЦИРУЮЩИХ ОПЕРАЦИЙ В ЗАДАЧЕ ПОИСКА КРАТЧАЙШЕГО ПУТИ В ГРАФЕ - Проблемы Информационных Технологий
СРАВНЕНИЕ КАЧЕСТВА РЕШЕНИЙ ЭВРИСТИЧЕСКИХ МЕТОДОВ НА БАЗЕ МОДИФИЦИРУЮЩИХ ОПЕРАЦИЙ В ЗАДАЧЕ ПОИСКА КРАТЧАЙШЕГО ПУТИ В ГРАФЕ - Проблемы Информационных Технологий
НАЦИОНАЛЬНАЯ АКАДЕМИЯ НАУК АЗЕРБАЙДЖАНА

№1, 2020

СРАВНЕНИЕ КАЧЕСТВА РЕШЕНИЙ ЭВРИСТИЧЕСКИХ МЕТОДОВ НА БАЗЕ МОДИФИЦИРУЮЩИХ ОПЕРАЦИЙ В ЗАДАЧЕ ПОИСКА КРАТЧАЙШЕГО ПУТИ В ГРАФЕ

Ватутин Эдуард И., Панищев Владимир С., Гвоздева Светлана Н., Титов Виталий С.

Статья посвящена изучению эффективности эвристических итерационных методов на базе модификации существующих решений в задаче поиска кратчайшего пути в графе. В статье приведено краткое описание рассматриваемой группы методов. Организованный вычислительный эксперимент базируется на формировании выборок псевдослучайных графов с заданными параметрами и организации поиска решений с использованием добровольных распределенных вычислений на платформе BOINC. В статье приведено подробное описание полученных экспериментальных результатов выбранной группы методов в зависимости от размерности задачи и силы ограничений. Полученные экспериментальные результаты позволяют сделать вывод, что методы роя частиц, случайных блужданий, имитации отжига и пчелиной колонии неэффективны при решении выбранной задачи и существенно уступают по качеству решений методам муравьиной колонии и генетическим алгоритмам (стр.3-15).

Ключевые слова: эвристические методы, генетические алгоритмы, метод роя частиц, метод случайных блужданий, метод имитации отжига, метод пчелиной колонии, поиск кратчайшего пути в графе, дискретная комбинаторная оптимизация, BOINC.
DOI : 10.25045/jpit.v11.i1.01
Литература
  • 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.