یافتن کوتاهترین دور هامیلتونی با استفاده از رویکرد ترکیبی هوش جمعی بر پایه شبکه‌های پیچیده

نوع مقاله : علمی - پژوهشی

نویسندگان

1 دانشجوی دکتری گروه مهندسی کامپیوتر، واحد میبد، دانشگاه آزاد اسلامی، میبد، ایران.

2 . عضو هیات علمی گروه مهندسی کامپیوتر، واحد میبد، دانشگاه آزاد اسلامی، میبد، ایران

3 عضو هیات علمی گروه مهندسی کامپیوتر، واحد میبد، دانشگاه آزاد اسلامی، میبد، ایران.

چکیده

 در این مقاله از دور هامیلتونی در  یک مسئله استاندارد و نظری بنام مسئله فروشنده دوره گرد و یک مسئله کاربردی بنام یافتن کوتاهترین مسیر هامیلتونی برای پیمودن تمام استان‌های ایران استفاده‌شده‌است. برای حل این گونه مسائل می‌توان از الگوریتم‌های هوش جمعی استفاده‌کرد که از عوامل طبیعی، زیست محیطی و اجتماعی  نشأت‌گرفته‌اند. الگوریتم بهینه‌سازی ازدحام ذرات یکی از الگوریتم‌های هوش جمعی است. در روش پیشنهادی، به منظور بهبود نتایج هر ذره از جستجوی محلی در روند جستجو و برای افزایش تبادل اطلاعات بهتر میان ذرات و انتخاب موقعیت بعدی مناسب‌تر هر ذره، از شبکه پیچیده، استفاده‌می‌شود. در این شبکه گره‌ای که راه‌حلی بهتری در آن نگهداری‌می شود همواره درجه آن گره بزرگ تر می شود. در شبکه پیچیده  از دو سنجه درجه و درجه همسایگی برای یافتن راه حل بهتر استفاده‌شده‌است. برای مقایسه نتایج از مسائل استاندارد TSPLib استفاده‌‌شده که نتایج حاکی از هزینه بهتر روش بهینه‌سازی ازدحام ذرات با جستجوی محلی شبکه‌ای پیچیده نسبت به بهینه‌سازی ازدحام ذرات با جستجوی محلی و ازدحام ذرات استاندارد است، همچنین، درصد خطا نسبت به بهترین جواب موجود در TSPLib به ترتیب در الگوریتم‌های بهینه‌سازی ازدحام ذرات با جستجوی محلی شبکه‌ای پیچیده و بهینه‌سازی ازدحام ذرات با جستجوی محلی نسبت به روش ازدحام ذرات استاندارد، کاهش‌داشته‌است. به طور نمونه، برای حل  مسئلهST70 در الگوریتم های بهینه سازی ازدحام ذرات شبکه ای و پایه میانگین هزینه حل مسئله به ترتیب 705 و 797 می‌باشد.

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

Finding the Shortest Hamiltonian Cycle Using the Combined Approach of Swarm Intelligence based on Complex Networks

نویسندگان [English]

  • hadi mohammadi 1
  • Kamal Mirzaie 2
  • Mohammad Reza Mollakhalili Meybodi 3
1 Department of Computer Engineering, Maybod Branch, Islamic Azad University, Maybod, Iran
2 Department of Computer Engineering, Maybod Branch, Islamic Azad University, Maybod, Iran
3 Department of Computer Engineering, Maybod Branch, Islamic Azad University, Maybod, Iran
چکیده [English]

In this paper, Hamiltonian cycle was used in a standard and theoretical problem called TSP as well as a practical problem called finding the shortest Hamiltonian cycle to cover all provinces of Iran. These kinds of problems can be solved using swarm intelligence algorithms derived from natural, environmental and social factors. Accordingly, the PSO Algorithm, which is one of the algorithms of swarm intelligence, was used . Search was also used to improve the results of each particle. Besides, a complex network was used in order to enhance the better exchange of information between particles and to select the next most appropriate position for each particle. In this network of nodes in which a better solution is maintained, the degree of that node is always greater. In the complex network, two criteria, degree and neighborhood degree, are used to find the best solution. The TSPLib standard problems were used to compare the results.  The findings showed that the particle swarm optimization technique with a complex network local search was more cost-effective than the optimization of the particle swarm with local search and standard particle swarm in a way that the percentage of error to the best solution in TSPLib was reduced in the particle swarm optimization algorithms with complex network local search and the particle swarm optimization in the local search compared to the standard particle swarm method, respectively. To solve the ST70 in network and basic algorithms, the average cost of solving the problem is 705 and 797, respectively.

کلیدواژه‌ها [English]

  • Shortest Hamiltonian Cycle
  • Travelling Salesman Problem
  • Particle Swarm Algorithm
  • Complex Network
حیدرآبادی زاده، نسرین، غنی زاده، علیرضا، (1399) "ارزیابی توابع جریمه مختلف در بهینه‌سازی خط پروژه راه با استفاده از الگوریتم‌های بهینه‌سازی ازدحام ذرات شتابدار (APSO) و برخورد اجسام(CBO)"، فصلنامه مهندسی حمل و نقل، دوره 11، شماره 3، صفحه 697-717.
 
صالحیان، فرهاد، توکلی مقدم، رضا، و نوروزی، نرگس (1398) "حل مساله مسیریابی وسایط نقلیه با در نظر گرفتن رضایت‌مندی مشتریان و کاهش انرژی مصرفی با الگوریتم زنبور عسل"، فصلنامه مهندسی حمل و نقل، دوره 11، شماره 2، صفحه 299-311.
یقینی، مسعود، مومنی، محسن، سرمدی، محمدرضا، (1389) "یافتن کوتاهترین مسیر همیلتونی برای شهرهای ایران با استفاده از الگوریتمهای جستجوی ممنوعه و ممتیک"، فصلنامه مهندسی حمل و نقل، دوره 2، شماره 2، صفحه 181-196.
 
Adamo T., Ghiani G. and Guerriero E. (2020) “An enhanced lower bound for the time-dependent travelling salesman problem”, Computers and Operations Research, Vol.113, No.104795, pp. 1-9.
 
Akhand M.A.H., Ayon S.I., Shahriyar S.A. and Siddique N. (2020) “Discrete Spider Monkey Optimization for Traveling Salesman Problem”, Applied Soft Computing Journal, Vol.86, No. 105887.
 
Amouei S., Mirzaie K. (2019) “Vector quantization using a modified firefly algorithm for image compression”, Tabriz Journal of Electrical Engineering, Vol.49, No.2, pp. 693-707.
 
Auh S. and Menguc (2005) “Balancing exploration and exploitation: the moderating role of competitive intensity”, Journal of Business Research, Vol.58, No.12, pp. 1652-1661.
 
Baraba´si A.L. and Albert R. (1999) “Emergence of scaling in random networks”, SCIENCE, Vol.286, No.1, pp.509-512.
 
Brown C.T., Liebovitch L.S. and Glendon R. (2007) “Lévy flights in dobe ju/’hoansi foraging patterns”, Human Ecology, Vol.35, No.1, pp. 129-138.
 
Cheng M.Y. and Prayogo D. (2014) "Symbiotic organisms search: a new metaheuristic optimization algorithm", Computers & Structures, Vol.139, No.1, pp. 98-112.
Corman F., Andrea D., Dario P. and Marco P. (2010) "A tabu search algorithm for rerouting trains during rail operations", Transportation Research Part B: Methodological, Vol.44, No.1, pp. 175-192.
 
 
Eremeev A.V. and Kovalenko Y.V. (2020) “Amemetic algorithm with optimal recombination for the asymmetric travelling salesman problem”, Memetic Computing, Vol.12, No. 1, pp. 23-36.
 
Ezugwu A.E.S and Adewumi A.O. (2017) “Discrete symbiotic organisms search algorithm for travelling salesman problem”, Expert Systems with Applications, Vol.87, No.1, pp. 70-78.
 
Jaradat G.M. (2018) “Hybrid elitist-ant system for a symmetric traveling salesman problem: case of jordan”, Neural Computing and Application, Vol.29, No.2, pp. 565-578.
 
Kennedy J. and Eberhart R. (1995) “Particle swarm optimization”, Proceedings of the IEEE International Conference on Neural Networks, pp. 1942-1948.
 
Letchford A. and Nasiri S.D. (2015) “The steiner travelling salesman problem with correlated costs”, European Journal of Operational Research, Vol.245, No.1, pp. 62-69.
 
Liu B., Wang L., Jin Y.H., Tang F. and Huang D.-X. (2005) “Improved particle swarm optimization combined with chaos”, Chaos, Solitons & Fractals, Vol.25, No.5, pp. 1261-1271.
Mafarja M.M. and Mirjalili S.A. (2017) "Hybrid Whale Optimization Algorithm with Simulated Annealing for Feature Selection", Neuro computing, Vol.260, No.1, pp. 302-312, 2017.
 
Mitchell M. (2006) “Complex systems: network thinking”, Artificial Intelligence, Vol.170, No.2006, pp. 1194-1212.
 
Ouaarab A., Ahiod B. and Yang X.S. (2014) “Random-key cuckoo search for the travelling salesman problem”, Soft Computing, Vol.19, No.4, pp. 1099-1106.
 
Saji Y. and Riffi M.E. (2016) “A novel discrete bat algorithm for solving the travelling salesman problem”, Neural Computing and Applications, Vol.27, No.7, pp. 1853-1866.
 
Strasser S., Sheppard J. and Butcher S. (2016) “A new discrete particle swarm optimization algorithm,” GECCO '16Proceedings of the Genetic and Evolutionary Computation Conference 2016, pp. 53-60.
 
Taillard E.D. and Helsgaun K. (2019) “POPMUSIC for the travelling salesman problem”, European Journal of Operational Research, Vol.272, No.2, pp. 420-429.
 
UmapathyVenkataseshaiah C.and  Arumugam M.S. (2010) “Particle swarm optimization with various inertia weight variants for optimal power flow solution”, Discrete Dynamics in Nature and Society, Vol.2010, No.1, pp. 1-15.
 
Watts D.J. and Strogatz S.H. (1998) “Collective dynamics of ‘small-world’ networks”, Nature, Vol.393, No.1, pp.440-442.
 
Wu D., Jiang N., Du W., Tang K., and Cao X. (2017) “Particle swarm optimization with moving particles on scale-free networks”, Journal Of Latex Class Files, Vol.14, No.8, pp. 1-10.
Yang X.S. (2010) “A new metaheuristic bat-inspired algorithm”, Springer.