|
DOI: 10.14489/vkit.2018.05.pp.026-034
Ватутин Э. И., Титов В. С.
ИССЛЕДОВАНИЕ ОСОБЕННОСТЕЙ ПРИМЕНЕНИЯ МЕТОДА РОЯ ЧАСТИЦ В ЗАДАЧЕ ПОИСКА КРАТЧАЙШЕГО ПУТИ В ГРАФЕ ПРИ НАЛИЧИИ ОГРАНИЧЕНИЙ
(c. 26-34)
Аннотация. Приведено описание особенностей реализации метода роя частиц при решении задач дискретной комбинаторной оптимизации. Показано, что основные подходы базируются на движении частиц роя в непрерывном пространстве с последующим отображением их координат в дискретные элементы решения, либо на применении модифицирующих операций, специфических для решаемой задачи. Эффективность разработанных авторами программных реализаций метода роя частиц проанализирована в тестовой задаче поиска кратчайшего пути в графе, в результате чего выявлено, что метод эффективен только при решении задач малой размерности, с ростом их размерности качество получаемых решений и скорость сходимости существенно уступают методу муравьиной колонии.
Ключевые слова: дискретная комбинаторная оптимизация; эвристические методы; метод роя частиц; поиск пути в графе; метаоптимизация.
Vatutin E. I., Titov V. S.
INVESTIGATION OF FEATURES OF PARTICLE SWARM OPTIMIZATION METHOD IN GRAPH SHORTEST PATH PROBLEM WITH CONSTRAINTS
(pp. 26-34)
Abstract. The article describes the features of the implementation of the particle swarm optimization method for solving discrete combinatorial optimization problems. It is shown that the well known approaches are based on the motion of the swarm particles in a continuous space with the subsequent mapping of their coordinates into discrete elements of the solution of the problem or on the set of modifying operations that are specific for discrete problem being solved. Three versions of the software implementation of the particle swarm method was developed by authors. First of them based on moving of the agents (particles) within the continuous space with real coordinates, speeds and velocities and mapping coordinated to vertices of path being formed using truncation. Second of them very similar to fuzzy logic group of approaches and based on the changing probabilities of use vertiex i in path position j (probabilities and “speeds” of their changing are also real values and mapping procedure appears during final decision constructing from the set of probabilities). Third of them don’t use movement in continuous space. Instead it based on forming starting decisions using random search method with combinatorial returns and modifying it using set of modifying operations (adding vertex to path, deleting vertex from path, etc.) aimed to decrease some metrics (very similar to the well known Hamming or Levenstein distances) in the direction to decision with better quality (in most cases to local or global record). The effectiveness of the software implementations of the particle swarm optimization method was analyzed in the graph shortest path problem. Within computing experiment formation of the sample with pseudorandom graphs with selected parameters N (number of vertices) and d (graph density) was organized. For each graph in sample with using all of developed software implementations the process of getting best decision was performed. After that comparison process based on averaged values of decisions quality (paths length) was organized. It is revealed that the method is effective only for solving problems of small size. With the increase of the problem size the quality of the solutions obtained and the convergence rate of method are significantly inferior to the ant colony optimization method.
Keywords: Discrete combinatorial optimization; Heuristic methods; Particle swarm optimization; Graph shortest path problem; Meta-optimization.
Э. И. Ватутин, В. С. Титов (Юго-Западный государственный университет, Курск, Россия) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
E. I. Vatutin, V. S. Titov (Southwest State University, Kursk, Russia) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
1. Ватутин Э. И., Титов В. С., Емельянов С. Г. Основы дискретной комбинаторной оптимизации. М.: Аргамак-Медиа, 2016. 270 с.
2. Glover F., Kochenberger G. A. Handbook of Metaheuristics. New York: Kluwer Academic Publishers, 2003. 560 p.
3. Kennedy J., Eberhart R. Particle Swarm Optimization // Proc. of IEEE Intern. Conf. on Neural Networks IV. 1995. Р. 1942 – 1948. doi: 10.1109/ICNN. 1995.488968.
4. Карпенко А. П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. М.: Изд-во МГТУ им. Н. Э. Баумана, 2014. 446 с.
5. Кошур В. Д. Глобальная оптимизация на основе гибридного метода усреднения координат и метода роя частиц // Вычислительные технологии. 2013. Т. 18, № 4. С. 36 – 47.
6. Карпенко А. П., Матвеева К. О., Буланов В. А. 6. Решение задачи молекулярного докинга модифицированным методом роя частиц [Электронный ресурс] // Наука и образование: Научное издание МГТУ им. Н. Э. Баумана: электр. науч.-техн. журнал. 2014. № 4. С. 339 – 353. URL: http: // technomagelpub. elpub.ru/jour/article/view/582/584. doi: 10.7463/0414. 0707258 (дата обращения: 15.09.2017.
7. Частикова В. А., Власов К. А., Картамышев Д. А. Обнаружение DDOS-атак на основе нейронных сетей с применением метода роя частиц в качестве алгоритма обучения // Фундаментальные исследования. 2014. № 8. Ч. 4. С. 829 – 832.
8. Kennedy J., Eberhart R. C. A Discrete Binary Version of the Particle Swarm Algorithm // Proc. of the Conference on Systems, Man, and Cybernetics (SMC97). 1997. V. 5. Р. 4104 – 4109. doi: 10.1109/ICSMC.1997. 637339.
9. Goldbarg E. F. G., Souza G. R. de, Goldbarg M. C. Particle Swarm Optimization Algorithm for the Traveling Salesman Problem [Электронный ресурс] // Traveling Salesman Problem. 2008. URL.: http://www.intechopen.com/books/traveling_salesman_problem/particle_swarm_optimization_algorithm_for_the_traveling_salesman_problem (дата обращения: 21.09. 2017).
10. Particle Swarm Optimization Based Algorithms for TSP and Generalized TSP / X. H. Shi et al. // Information Processing Letters. 2007. V. 103, No. 5. P. 169 – 176.
11. Hu X., Eberhart R.C., Shi Y. Swarm Intelligence for Permutation Optimization: A Case Study of n-Queens Problem // Proc. IEEE Swarm Intelligence Symposium. Indianapolis, Indiana, USA, 2003. P. 243 – 246.
12. Халил Селим Т. М., Горпинич А. В. Выбор оптимальных сечений проводников и мест установки и мощности батарей конденсаторов в радиальных распределительных сетях с помощью селективного метода роя частиц // Научные записки Донецкого национального технического университета. Серия: Электротехника и энергетика. 2011. № 11 (186). С. 406 – 413.
13. Лебедев В. Б., Лебедев Б. К. Построение кратчайших связывающих соединений методом кристаллизации россыпи альтернатив [Электронный ресурс] // Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС). М., 2014. № 1. С. 177 – 182. URL: http://www.mes-conference.ru/data/ year2014/pdf/D174.pdf (дата обращения: 02.10.2017).
14. Ватутин Э. И., Мартынов И. А., Титов В. С. Способ обхода тупиков при решении задач дискретной оптимизации с ограничениями // Перспективные информационные технологии (ПИТ-2014) / Самарский научный центр РАН. Самара, 2014. С. 313 – 317.
15. Ватутин Э. И., Титов В. С. Анализ скорости сходимости качества решений эвристических методов в задаче поиска кратчайшего пути в графе [Электронный ресурс] // Информационно-измерительные диагностирующие и управляющие системы (Диагностика – 2016). Курск, 2016. С. 19 – 25. URL: http://evatutin. narod.ru/evatutin_grth_pathfind_convrate.pdf (дата обращения: 02.10.2017).
1. Vatutin E. I., Titov V. S., Emel'yanov S. G. (2016). Basics of discrete combinatorial optimization. Moscow: Argamak-Media. [in Russian language]
2. Glover F., Kochenberger G. A. (2003). Handbook of metaheuristics. New York: Kluwer Academic Publishers.
3. Kennedy J., Eberhart R. (1995). Particle swarm optimization. Proceedings of IEEE International Conference on Neural Networks IV, pp. 1942-1948. doi: 10.1109/ICNN.1995.488968
4. Karpenko A. P. (2014). Modern algorithms of search optimization. Algorithms inspired by nature: textbook. Moscow: MGTU im. N. E. Baumana. [in Russian language]
5. Koshur V. D. (2013). Global optimization based on the hybrid method of averaging coordinates and the method of swarm particles. Vychislitel'nye tekhnologii, 18(4), pp. 36 – 47. [in Russian language]
6. Karpenko A. P., Matveeva K. O., Bulanov V. A. (2014). Solution of the molecular docking problem by a modified swarm particle method. Nauka i obrazovanie, (4), pp. 339-353. [in Russian language]
7. Chastikova V. A., Vlasov K. A., Kartamyshev D. A. (2014). Detection of DDOS-attacks based on neural networks using the particle swarm method as a learning algorithm. Fundamental'nye issledovaniya, (8–4), pp. 829-832. [in Russian language]
8. Kennedy J., Eberhart R. C. (1997). A discrete binary version of the particle swarm algorithm. Proc. of the Conference on Systems, Man, and Cybernetics (SMC97), pp. 4104-4109.
9. Goldbarg E. F. G., Goldbarg M. C., Souza G. R. (2008). Particle swarm optimization algorithm for the traveling salesman problem. Travelling Salesman Problem (book edt. by Federico Greco). (pp. 202-225). Vienna, Austria: I-Tech.
10. Shi X. H.; Liang Y. C.; Lee H. P.; Lu C., Wang Q. X. (2007). Particle swarm optimization based algorithms for TSP and generalized TSP. Information Processing Letters, 103, pp. 169-176.
11. Hu X., Eberhart R. C., Shi Y. (2003). Swarm intelligence for permutation optimization: a case study of n-queens problem. Proceedings of the 2003 IEEE Swarm Intelligence Symposium, pp. 243-246.
12. Halil T. M., Gorpinich A. V. (2011). Selection of optimal conductor cross-sections, installation site and capacitor bank power in radial distribution networks using the selective particle swarm method. Nauchnye zapiski Doneckogo nacional'nogo tekhnicheskogo universiteta. Seriya: Elektrotekhnika i energetika, 186(11), pp. 406-413. [in Russian language]
13. Lebedev V. B., Lebedev B. K. (2014). Construction of the shortest binding compounds by the method of crystallization of alternatives placers. Problemy razrabotki perspektivnyh mikro- i nanoelektronnyh sistem (MES), (1), pp. 177-182. [in Russian language]
14. Vatutin E. I., Martynov I. A., Titov V. S. (2014). Method for traversing dead ends in solving discrete optimization problems with constraints. Perspective information technology (PIT-2014). (pp. 313-317). Samara: Izdatel'stvo Samarskogo nauchnogo centra RAN. [in Russian language]
15. Vatutin E. I., Titov V. S. (2016). Analysis of the rate of convergence of the solutions quality using heuristic methods in the problem of finding the shortest path in the graph. Information-measuring diagnostic and control systems (Diagnostics – 2016). (pp. 19-25). Kursk: Izdatel'stvo YUZGU. [in Russian language]
Статью можно приобрести в электронном виде (PDF формат).
Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.
После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.
Для заказа скопируйте doi статьи:
10.14489/vkit.2018.05.pp.026-034
и заполните форму
Отправляя форму вы даете согласие на обработку персональных данных.
.
This article is available in electronic format (PDF).
The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.
After depositing your payment on our bank account we send you file of the article by e-mail.
To order articles please copy the article doi:
10.14489/vkit.2018.05.pp.026-034
and fill out the form
.
|
Архив номеров
Разработка концепции и создание сайта - ООО «Издательский дом «СПЕКТР»