Популяционный алгоритм решения задачи коммивояжера
Аннотация
В данной статье рассматривается популяционный гибридный алгоритм решения задачи коммивояжера, построенный с применением двух алгоритмов – генетического и алгоритма роя частиц, объединенных по принципу высокоуровневой гибридизации вложением – предполагает слабую связность рассматриваемых алгоритмов. В статье приводится постановка задачи коммивояжера и подробный разбор данной проблемы, относящейся к классу задач комбинаторной оптимизации. Приводятся аргументы в пользу выбора эвристического популяционного алгоритма решения данной проблемы: задача коммивояжера является NP-трудной и для неё не доказано существование алгоритма, который мог бы решить её за полиномиальное время, даже более того – неизвестно, существует ли эвристический подход, который будет давать гарантированную точность решения (данный вопрос до сих пор является открытым). Кроме того, задачу коммивояжера относят к классу трансвычислительных задач – при количестве городов больше 66 для нахождения точного решения методом полного перебора необходимо обработать более чем 1093 бит информации. Следовательно, эффективные приближенные методы решения являются очень важными для данной задачи. Далее формулируется популяционный гибридный метод решения задачи коммивояжера в виде пошаговой структуры с подробным описанием каждого из шагов алгоритма. Затем приводится блок-схема полученного алгоритма. Далее рассмотрен результат работы программы: построенный граф, найденный маршрут коммивояжёра, его длина и последовательность городов. Также в статье приводятся разработанный пользовательский интерфейс с возможностью регулировки различных параметров алгоритма, позволяющий оптимизировать работу алгоритма. В последней части статьи приведены сравнительный анализ эффективности работы полученного алгоритма, а также сравнение точности разработанного популяционного гибридного алгоритма решения задачи коммивояжера с алгоритмом ближайшего соседа и муравьиным алгоритмом.
Литература
2. Karpenko A.P. Sovremennye algoritmy poiskovoj optimizacii. Algoritmy, vdohnovlennye prirodoj [Modern search optimization algorithms. Nature-inspired algorithms]. BMSTU, Moscow; 2014. 448 p. (In Russ.)
3. Gladkov L.A., Kureychik V.V., Kureychik V.M. Geneticheskie algoritmy [Genetic Algorithms]. PhysMathLit, Moscow; 2010. 317 p. (In Russ.)
4. Mudrov V.I. Zadacha o kommivojazhere [The traveling salesman problem]. Znanie, Moscow; 1969. 62 p. (In Russ.)
5. Antukh A.E., Karpenko A.P. Global optimization based on methods of particle swarm, mind evolution and clonal selection. Science and Education of Bauman MSTU. 2012; (8):379-416. (In Russ., abstract in Eng.) DOI: https://doi.org/10.7463/0812.0431723
6. del Valle Y., Venayagamoorthy G.K., Mohagheghi S., Hernandez J. -C., Harley R.G. Particle Swarm Optimization: Basic Concepts, Variants and Applications in Power Systems. IEEE Transactions on Evolutionary Computation. 2008; 12(2):171-195. (In Eng.) DOI: https://doi.org/10.1109/TEVC.2007.896686
7. Domínguez J.S.H., Pulido G.T. A comparison on the search of particle swarm optimization and differential evolution on multi-objective optimization. 2011 IEEE Congress of Evolutionary Computation (CEC). IEEE Pres, New Orleans, LA, USA; 2011. p. 1978-1985. (In Eng.) DOI: https://doi.org/10.1109/CEC.2011.5949858
8. Niknam T., Amiri B. An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis. Applied Soft Computing. 2010; 10(1):183-197. (In Eng.) DOI: https://doi.org/10.1016/j.asoc.2009.07.001
9. Ritscher T., Helwig S., Wanka R. Design and experimental evaluation of multiple adaptation layers in self-optimizing particle swarm optimization. IEEE Congress on Evolutionary Computation. IEEE Press, Barcelona, Spain; 2010. p. 1-8. (In Eng.) DOI: https://doi.org/10.1109/CEC.2010.5586255
10. Shi Y., Eberhart R. A modified particle swarm optimizer. 1998 IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence (Cat. No.98TH8360). IEEE Press, Anchorage, AK, USA; 1998. p. 69-73. (In Eng.) DOI: https://doi.org/10.1109/ICEC.1998.699146
11. Simon D. Evolutionary Optimization Algorithms. John Wiley & Sons, Inc.; 2013. 784 p. (In Eng.)
12. Kureychik V.V., Bova V.V., Kureychik V.V. Bioinspired algorithm for design and optimization problems. In: Ed. by E. L. Gloriozov. Proceedings of the International Conference on Information technologies in science, education and management. Gurzuf; 2015. p. 427-432. Available at: https://www.elibrary.ru/item.asp?id=23519161 (accessed 13.04.2021). (In Russ., abstract in Eng.)
13. Kureychik V.V., Kureychik L.V. Summary of some hybrid approach to solving combinatorically logical tasks on graphs. Proceedings of the International Scientific and Technical Congress on Intelligent Systems and Information Technologies ‒ 2020 (IS&IT-2020). Publ. house of Stupin S.A., Divnomorskoye; 2020. p. 102-108. Available at: https://www.elibrary.ru/item.asp?id=45435484 (accessed 11.04.2021). (In Russ., abstract in Eng.)
14. Kureychik V.V., Kursitys I.O., Kuliev E.V., Gerasimenko E.M. Application of bioinspired algorithms for solving transcomputational tasks. Journal of Physics: Conference Series. 2020; 1703:012021. (In Eng.) DOI: https://doi.org/10.1088/1742-6596/1703/1/012021
15. Kureychik V., Zaruba D., Kureychik V. Hybrid Approach for Graph Partitioning. In: Ed. by R. Silhavy et al. Artificial Intelligence Trends in Intelligent Systems. CSOC 2017. Advances in Intelligent Systems and Computing. 2017; 573:64-73. Springer, Cham. (In Eng.) DOI: https://doi.org/10.1007/978-3-319-57261-1_7
16. Su F., Kong L., Wang H., Wen Z. Modeling and application for rolling scheduling problem based on TSP. Applied Mathematics and Computation. 2021; 407:126333. (In Eng.) DOI: https://doi.org/10.1016/j.amc.2021.126333
17. Zhang J., Hong L., Liu Q. An Improved Whale Optimization Algorithm for the Traveling Salesman Problem. Symmetry. 2021; 13(1):48. (In Eng.) DOI: https://doi.org/10.3390/sym13010048
18. Krishna M.M., Panda N., Majhi S.K. Solving traveling salesman problem using hybridization of rider optimization and spotted hyena optimization algorithm. Expert Systems with Applications. 2021; 183:115353. (In Eng.) DOI: https://doi.org/10.1016/j.eswa.2021.115353
19. Garn W. Balanced dynamic multiple travelling salesmen: Algorithms and continuous approximations. Computers & Operations Research. 2021; 136:105509. (In Eng.) DOI: https://doi.org/10.1016/j.cor.2021.105509
20. Oliveira S.M., Hussin M.S., Stuetzle T., Roli A., Dorigo M. A detailed analysis of the population-based ant colony optimization algorithm for the TSP and the QAP. Proceedings of the 13th annual conference companion on Genetic and evolutionary computation (GECCO'11). Association for Computing Machinery, New York, NY, USA; 2011. p. 13-14. (In Eng.) DOI: https://doi.org/10.1145/2001858.2001866
21. Nagata Y. High-Order Entropy-Based Population Diversity Measures in the Traveling Salesman Problem. Evolutionary Computation. 2020; 28(4):595-619. (In Eng.) DOI: https://doi.org/10.1162/evco_a_00268
22. Pop P., Matei O., Pintea C. A two-level diploid genetic based algorithm for solving the family traveling salesman problem. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'18). Association for Computing Machinery, New York, NY, USA; 2018. p. 340-346. (In Eng.) DOI: https://doi.org/10.1145/3205455.3205545
23. Bernardino R., Paias A. Solving the family traveling salesman problem. European Journal of Operational Research. 2018; 267(2):453-466. (In Eng.) DOI: https://doi.org/10.1016/j.ejor.2017.11.063
24. Cacchiani V., Muritiba A.E.F., Negreiros M., Toth P. A multistart heuristic for the equality generalized traveling salesman problem. Networks. 2011; 57(3):231-239. (In Eng.) DOI: https://doi.org/10.1002/net.20421
25. Morán-Mirabal L.F., González-Velarde J.L., Resende M.G.C. Randomized heuristics for the family traveling salesperson problem. International Transactions in Operational Research. 2014; 21(1):41-57. (In Eng.) DOI: https://doi.org/10.1111/itor.12026
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
