مسئله فروشنده دوره‌گرد TSP با الگوریتم‌های فراابتکاری

مسئله فروشنده دوره‌گرد (Traveling Salesman Problem – TSP) و حل آن با الگوریتم‌های فراابتکاری

مسئله فروشنده دوره‌گرد (TSP) یکی از مسائل کلاسیک بهینه‌سازی ترکیبیاتی (Combinatorial Optimization) است که در آن هدف یافتن کوتاه‌ترین مسیر (Shortest Path) برای بازدید از مجموعه‌ای از شهرها (Cities) و بازگشت به شهر اولیه است، به گونه‌ای که هر شهر فقط یک بار بازدید شود. این مسئله از نوع مسائل NP-hard است، یعنی حل دقیق آن با افزایش تعداد شهرها به‌طور نمایی دشوارتر می‌شود. یکی از بهترین روش های استفاده از الگوریتم‌های فراابتکاری (Metaheuristic Algorithms) است.

تعریف مسئله TSP

در مسئله TSP، فروشنده‌ای باید مجموعه‌ای از شهرها (Cities) را بازدید کند به طوری که:

1. هر شهر فقط یک بار بازدید (Single Visit) شود.
2. فروشنده در پایان به شهر اولیه خود بازگردد (Return to Starting Point).
3. هزینه کل سفر (Total Travel Cost)، که معمولاً بر اساس فاصله یا زمان سفر محاسبه می‌شود، حداقل شود.

ویژگی‌ها و دشواری‌های TSP

• NP-Hard بودن: با افزایش تعداد شهرها، تعداد مسیرهای ممکن برای بررسی به طور نمایی افزایش می‌یابد. این باعث می‌شود که حل دقیق (Exact Solution) برای تعداد زیاد شهرها در زمان معقول غیرممکن باشد.
• کاربردهای متنوع: علاوه بر مسائل مسیریابی، TSP در طراحی مدارهای الکترونیکی (PCB Layouts)، توالی‌دهی وظایف (Task Scheduling)، و حتی در ژنومیک (Genomics) نیز کاربرد دارد.

روش‌های حل TSP

روش‌های حل TSP به دو دسته کلی تقسیم می‌شوند:

1. روش‌های دقیق (Exact Methods): مانند الگوریتم شاخه و حد (Branch and Bound)، برنامه‌ریزی پویا (Dynamic Programming) و برنامه‌ریزی خطی صحیح (Integer Linear Programming – ILP). این روش‌ها جواب بهینه را پیدا می‌کنند اما برای تعداد زیادی شهر زمان‌بر هستند.
2. روش‌های تقریبی (Approximation Methods): مانند الگوریتم‌های فراابتکاری که به دنبال جواب‌های نزدیک به بهینه (Near-Optimal Solutions) هستند و برای مسائل با ابعاد بزرگ کاربرد دارند.

---

حل TSP با الگوریتم‌های فراابتکاری

الگوریتم‌های فراابتکاری به دلیل توانایی بالا در جستجوی فضای بزرگ مسائل و تعادل بین جستجوی محلی (Exploitation) و جستجوی سراسری (Exploration)، ابزار قدرتمندی برای حل TSP هستند. برخی از الگوریتم‌های معروف برای حل TSP شامل موارد زیر می‌شوند:

الگوریتم‌های فراابتکاری به دلیل توانایی در یافتن جواب‌های نزدیک به بهینه (Near-Optimal Solutions) در زمانی کوتاه و توانایی بالا در جستجوی فضای بزرگ مسائل و تعادل بین جستجوی محلی (Exploitation) و جستجوی سراسری (Exploration)، ابزار قدرتمندی برای حل TSP هستند.. این الگوریتم‌ها، از رفتارهای طبیعت، سیستم‌های اجتماعی یا فرایندهای فیزیکی الهام گرفته شده‌اند. در ادامه لیستی از بهترین الگوریتم های فراابتکاری برای حل مسئله TSP‌ بررسی نموده‌ایم.

---

نویسنده: حسن سعادتمند

• بیش از 250 دوره آموزشی در MATLAB و پایتون.
• بیش از 15 سال تجربه در زمینه یادگیری ماشین، الگوریتم های فراابتکاری، یادگیری عمیق، مهندسی کنترل.
• چاپ چندین مقاله Q1 در بهترین ژرنال های دنیا Google Scholar.
• مدرس فرادرس

اطلاعات تماس:

• تلگرام: t.me/matlabanyone
• ایمیل: h.saadatmand22@yahoo.com
• یوتیوب: matlablearning
• تلفن: 09155137038

---

لیست الگوریتم‌های مهم فراابتکاری از ابتدا تا سال 2025:

1. الگوریتم ژنتیک (Genetic Algorithm – GA) – 1975
2. الگوریتم تبرید شبیه‌سازی (Simulated Annealing – SA) – 1983
3. جستجوی تابو (Tabu Search – TS) – 1986
4. الگوریتم فرهنگی (Cultural Algorithm – CA) – 1991
5. بهینه‌سازی کلونی مورچه‌ها (Ant Colony Optimization – ACO) – 1992
6. بهینه‌سازی ازدحام ذرات (Particle Swarm Optimization – PSO) – 1995
7. تکامل تفاضلی (Differential Evolution – DE) – 1997
8. جستجوی هارمونی (Harmony Search – HS) – 2001
9. الگوریتم ازدحام ماهی (Fish Swarm – FS) – 2002
10. الگوریتم زنبورها (Bees Algorithms – BA) – 2005
11. کلونی زنبور عسل مصنوعی (Artificial Bee Colony – ABC) – 2005
12. الگوریتم قورباغه (Shuffled Frog Leaping Algorithm – SFLA) – 2006
13. الگوریتم رقابت استعماری (Imperialist Competitive Algorithm – ICA) – 2007
14. الگوریتم کرم شب‌تاب (Firefly Algorithm – FA) – 2008
15. الگوریتم جغرافیای زیستی (Biogeography-based Optimization – BBO) – 2009
16. الگوریتم جستجوی گرانشی (Gravitational Search Algorithm – GSA) – 2009
17. جستجوی فاخته (Cuckoo Search – CS) – 2009
18. الگوریتم خفاش (Bat Algorithm – BA) – 2010
19. الگوریتم علف هرز (Invasive Weed Optimization – IWO) – 2011
20. الگوریتم بهینه‌سازی ایده پردازی (Brain Storm Optimization – BSO) – 2011
21. الگوریتم بهینه‌سازی فاخته (Cuckoo Optimization Algorithm – COA) – 2011
22. الگوریتم آموزش و یادگیری (Teaching–Learning-Based Optimization – TLBO) – 2011
23. الگوریتم سیاه‌چاله (Black Hole – BA) – 2013
24. بهینه‌سازی گرگ خاکستری (Grey Wolf Optimizer – GWO) – 2014
25. الگوریتم گرده‌افشانی گل (Flower Pollination Algorithm – FPA) – 2014
26. الگوریتم جستجوی فراکتال تصادفی (Stochastic Fractal Search – SFS) – 2015
27. الگوریتم شیر مورچه (Ant Lion Optimizer – ALO) – 2015
28. الگوریتم سنجاقک (Dragonfly Algorithm – DA) – 2015
29. الگوریتم شمع پروانه (Moth-Flame Optimization – MFO) – 2015
30. الگوریتم بهینه‌سازی پروانه سلطنتی (Monarch Butterfly Optimization – MBO) – 2015
31. الگوریتم ازدحام پرندگان (Bird Swarm Optimization Algorithm – BSOA) – 2015
32. الگوریتم کلاغ (Crow Search Algorithm – CSA) – 2016
33. الگوریتم سینوس کسینوس (Sine Cosine Algorithm – SCA) – 2016
34. الگوریتم جستجوی پروانه (Moth Search Algorithm – MSA) – 2016
35. الگوریتم جایا (Jaya Algorithm – JA) – 2016
36. الگوریتم بهینه‌سازی کرم (Glowworm Swarm Optimization – GSO) – 2016
37. الگوریتم بهینه‌ساز چند-نظمی (Multi-Verse Optimizer – MVO) – 2016
38. الگوریتم پشه (Mosquito Flying Optimization – MFO) – 2016
39. الگوریتم وال (نهنگ) (Whale Optimization Algorithm – WOA) – 2016
40. الگوریتم سالپ (Slap Swarm Algorithm – SSA) – 2017
41. الگوریتم بهینه‌ساز کفتار خالدار (Spotted Hyena Optimizer – SHO) – 2017
42. الگوریتم بهینه‌سازی پروانه و زنبور (Butterfly Optimization Algorithm with Bee – BOAB) – 2017
43. الگوریتم ملخ (Grasshopper Optimization Algorithm – GOA) – 2017
44. الگوریتم رشد درخت (Tree Growth Algorithm – TGA) – 2018
45. الگوریتم پنگوئن امپراتور (Emperor penguin optimizer – EPO) – 2018
46. الگوریتم شاهین هریس (Harris Hawks Optimization – HHO) – 2019
47. الگوریتم گوزن قرمز (Red Deer Algorithm – RDA) – 2019
48. الگوریتم بهینه‌سازی فقیر و غنی (Poor and Rich Optimization – PRO) – 2019
49. الگوریتم مسیریاب (Pathfinder Algorithm – PFA) – 2019
50. الگوریتم بهینه‌سازی اتم (Atom Search Optimization – ASO) – 2019
51. الگوریتم ازدحام دلفین‌ها (Dolphin Swarm Algorithm – DSA) – 2019
52. الگوریتم بهینه‌سازی ارشمیدس (Archimedes Optimization Algorithm – AOA) – 2020
53. الگوریتم کپک لجن (Slime Mould Algorithm – SMA) – 2020
54. الگوریتم اسب وحشی (Wild Horse Optimizer Algorithm – WHOA) – 2020
55. الگوریتم سفره ماهی (Manta Ray Foraging Optimization – MRFO) – 2020
56. الگوریتم عقاب طلایی (Golden Eagle Optimizer – GEO) – 2020
57. الگوریتم کانگورو (Kangaroo Optimization – KO) – 2020
58. الگوریتم بهینه‌سازی اکوسیستم مصنوعی (Artificial Ecosystem-Based Optimization – AEO) – 2020
59. الگوریتم عنکبوت اجتماعی (Social Spider Optimization – SSO) – 2020
60. الگوریتم شکارچیان دریایی (Marine Predators Algorithm – MPA) – 2020
61. بهینه‌ساز نقاشی تصادفی (Stochastic Paint Optimizer – SPO) – 2020
62. الگوریتم بهینه‌سازی مبتنی بر روان‌شناسی دانش‌آموزان (Student Psychology Based Optimization Algorithm) – 2020
63. الگوریتم مبتنی بر اشتراک و کسب دانش (Gaining-Sharing Knowledge Based Algorithm) – 2020
64. الگوریتم فیل (Elephant Herding Optimization – EHO) – 2021
65. الگوریتم گله اسب (Horse herd Optimization Algorithm – HOA) – 2021
66. الگوریتم جستجوی اجتماعی (Social Network Search – SNS) – 2021
67. الگوریتم عقاب (Bald Eagle Search Optimization – BES) – 2021
68. الگوریتم بهینه‌سازی خروس‌ها (Roosters Algorithm – RA) – 2021
69. الگوریتم بهینه‌سازی کرکس‌های آفریقایی (African Vultures Optimization Algorithm – AVOA) – 2021
70. بهینه‌سازی بازی آشوب (Chaos Game Optimization – CGO) – 2021
71. الگوریتم حسابی (The Arithmetic Optimization Algorithm – AOA) – 2021
72. الگوریتم بهینه‌سازی گرادیان (Gradient Based Optimization – GBO) – 2021
73. الگوریتم مار (Snake Optimizer – SO) – 2022
74. الگوریتم غزال (Gazelle Optimization Algorithm – GOA) – 2022
75. الگوریتم بهینه‌سازی خرگوش‌ها (Artificial Rabbits Optimization – ARO) – 2022
76. الگوریتم بهینه‌سازی ازدحام گربه شنی (Sand Cat Swarm Optimization – SCSO) – 2022
77. الگوریتم بهینه‌سازی سوسک (Cockroach Swarm Optimization – CSO) – 2022
78. الگوریتم بهینه‌سازی زنبور عسل مصنوعی بهبود یافته (Improved Artificial Bee Colony Algorithm – IABC) – 2022
79. الگوریتم علی بابا و چهل دزد (Alibaba and the Forty Thieves – AFT) – 2022
80. الگوریتم بهینه‌سازی سارها (Starling Murmuration Optimizer – SMO) – 2022
81. الگوریتم بهینه‌سازی غزال کوهستان (Mountain Gazelle Optimizer – MGO) – 2022
82. الگوریتم جستجوی بهینه‌سازی ابولا (Ebola Optimization Search – EOS) – 2022
83. الگوریتم جستجوی طلایی (Golden Search Optimization Algorithm – GSA) – 2022
84. الگوریتم بهینه‌سازی درخت (Tree Optimization Algorithm – TOA) – 2022
85. الگوریتم گورکن عسل (Honey Badger Algorithm – HBA) – 2022
86. الگوریتم جستجوی خزنده (Reptile Search Algorithm – RSA) – 2022
87. الگوریتم بهینه‌سازی موش‌خرمای کوتوله (Dwarf Mongoose Optimization Algorithm) – 2022
88. بهینه‌ساز فندق‌شکن (Nutcracker Optimizer) – 2023
89. الگوریتم قانون فیک (Fick’s Law Algorithm) – 2023
90. الگوریتم نهنگ بهبود یافته (Improved Whale Optimization Algorithm – IWOA) – 2023
91. الگوریتم بهینه‌سازی حافظه انسان (Human Memory Optimization Algorithm – HMOA) – 2023
92. الگوریتم بهینه‌سازی تیرانوسور (Tyrannosaurus Optimization Algorithm – TOA) – 2023
93. الگوریتم Coati Optimization Algorithm (COA) – 2023
94. الگوریتم Crayfish Optimization Algorithm (COA) – 2023
95. الگوریتم خواب عمیق (The Deep Sleep Optimizer – DSO) – 2023
96. الگوریتم بهینه‌سازی شکار گوزن‌ها (Deer Hunting Optimization Algorithm – DHOA) – 2024
97. الگوریتم بهینه‌سازی اسب آبی (Hippopotamus Optimization Algorithm – HOA) – 2024
98. بهینه‌سازی گروه جوجه‌ها (Chickens Swarm Optimization – CSO) – 2024
99. الگوریتم کروکدیل (Crocodile Optimization Algorithm – COA) – 2024
100. الگوریتم یوزپلنگ (Puma Optimizer – PO) – 2024
101. الگوریتم هایکینگ (Hiking Optimization Algorithm – HOA) – 2024
102. الگوریتم بهینه‌سازی درونیابی درجه دوم (Quadratic Interpolation Optimization – QIO) – 2023
103. الگوریتم پروتوزوای مصنوعی (Artificial Protozoa Optimizer – APO) – 2024
104. الگوریتم مارماهی و هامور (Eel and Grouper Optimizer – EGO) – 2024
105. الگوریتم خرگوش نیشکر بزرگ (Greater Cane Rat Algorithm – GCRA) – 2024
106. الگوریتم کوید (COVIDOA) – 2024
107. الگوریتم جستوجوی پنگوئن ها (Penguins Search Optimization Algorithm -PeSOA) – 2024
108. الگوریتم نهنگ قاتل (Killer Whale Algorithm – KWA) – 2024
109. الگوریتم ستاره دریایی (Starfish Optimization Algorithm – SFOA) – 2025
110. الگوریتم روباه قطبی (Arctic Fox Optimization – AFO) – 2025

---

کپی با ذکر نام سایت (www.matlablearning.com) مجاز است.