***************«بسم الله الرحمن الرحیم» نشریه علمی «پردازش علائم و داده‌ها» با مجوز رسمی از کمیسیون نشریات وزارت علوم، تحقیقات و فناوری، صاحب امتیاز: پژوهشگاه توسعه فناوری‌های پیشرفته ***************
Signal and Data Processing Journal A scientific journal officially licensed by the Commission for Scientific Publications of the (MSRT). Publisher: Research Ceter for Developmen of Technologies
دوره 23، شماره 1 - ( 3-1405 )
جلد 23 شماره 1 صفحات 36-19 |
برگشت به فهرست نسخه ها
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Heydari A, Alipour M M, Abdolhosseinzadeh M, Emami H. A novel Near Distance Order Crossover to improve the performance of genetic algorithms for solving the TSP. JSDP 2026; 23 (1) : 2
URL: http://jsdp.rcisp.ac.ir/article-1-1476-fa.html
URL: http://jsdp.rcisp.ac.ir/article-1-1476-fa.html
حیدری علی، علیپور میرمحمد، عبدالحسین زاده محسن، امامی حجت. بهبود عملکرد الگوریتم‌های ژن‌شناسی در حل مسئلۀ فروشندۀ دوره‌گرد با معرفی عمل‌گر تقاطع ترتیب با فاصلۀ نزدیک. پردازش علائم و داده‌ها. 1405; 23 (1) :19-36
استادیار دانشکدۀ فنی‌ومهندسی، گروه مهندسی کامپیوتر، دانشگاه بناب، بناب، ایران
چکیده: (566 مشاهده)
مسئله فروشنده دوره‌گرد[1] به‌دلیل تعداد بسیار بالای حالت‌های ممکن برای مسیریابی به‌شدت پیچیده و زمان‌بر است؛ به‌طوری‌که برای حل این مسئله الگوریتم‌های دقیق و تقریبی مختلفی ازجمله الگوریتم ژن‌شناسی[2] مورد توجه قرار گرفته است. در این مقاله الگوریتم جدیدی برای حل مسئله فروشنده دوره‌گرد با استفاده از عمل‌گر تقاطع ترتیب با فاصله نزدیک[3] ارائه شده‌است که هدف از آن، بهبود کیفیت مسیریابی در کمترین زمان ممکن نسبت به روش‌های دیگر است و مهم‌ترین ویژگی این عمل‌گر تقاطع جدید، استفاده از فاصله بین شهرها ضمن حفظ تنوع جمعیت است و این عمل‌گر نسخه‌ای پیشرفته از عمل‌گر تقاطع ترتیبی[4] است. یک الگوریتم ژن‌شناسی بهینه برای استفاده از این عمل‌گر تقاطع[5] نیز ارائه می‌شود؛ این الگوریتم با به‌کارگیری عمل‌گر تقاطع ترتیب با فاصله نزدیک قادر است مسیرهای کوتاه‌تر و کارآمدتری نسبت به الگوریتم‌های ژن‌شناسی معمولی تولید کند. نتایج الگوریتم ژن‌شناسی پیشنهادی بر روی 26 نمونه مسئله استاندارد فروشنده دوره‌گرد از TSPLIB، از اندازه‌های مختلف، مورد ارزیابی قرار گرفته‌است و طبق نتایج به‌دست‌آمده عمل‌گر پیشنهادی در مواردی از عمل‌گرهای مقایسه‌شده مانند PMX، CX، OX و چندین عمل‌گر تقاطع دیگر عملکرد قابل‌قبول و بهتری داشته‌است؛ علاوه‌برآن زمان محاسباتی را نیز به‌شدت کاهش داده‌است؛ پس از آن الگوریتم پیشنهادی نیز مورد مقایسه با تعدادی از الگوریتم‌های مرسوم مانند ACO، PSO، SA و چندین مورد از الگوریتم‌های ارائه‌شده در مقالات معتبر قرار گرفت و بر اساس نتایج به‌دست‌آمده در کیفیت جواب‌ها و در زمان اجرای موردنیاز الگوریتم پیشنهادی، دستاوردهای قابل دفاعی در بین روش‌های فراابتکاری داشته و توانسته‌است عملکرد مناسبی در حفظ تعادل میان اکتشاف و بهره‌برداری نشان دهد؛ همچنین نتایج تجربی به‌دست‌آمده حاکی از قابلیت رقابت الگوریتم ارائه‌شده، برمبنای کیفیت نتایج و زمان محاسباتی، در مقایسه با تعدادی از الگوریتم‌های اکتشافی و فرااکتشافی مطرح در این زمینه است.
شماره‌ی مقاله: 2
واژه‌های کلیدی: مسئلۀ فروشندۀ دوره‌گرد، الگوریتم ژن‌شناسی، عمل‌گر تقاطع ترتیب، عمل‌گر تقاطع ترتیب با فاصلۀ نزدیک.
نوع مطالعه: پژوهشي |
موضوع مقاله:
مقالات پردازش داده‌های رقمی
دریافت: 1404/4/9 | پذیرش: 1404/11/14 | انتشار: 1405/3/31 | انتشار الکترونیک: 1405/3/31
دریافت: 1404/4/9 | پذیرش: 1404/11/14 | انتشار: 1405/3/31 | انتشار الکترونیک: 1405/3/31
فهرست منابع
1. P. Larrañaga, Kuijpers, C. M., & Poza, J, "Genetic algorithms for the travelling salesman problem: A review of representations and operators," Artificial Intelligence Review, vol. 13, pp. 97-128, 1999. [DOI:10.1023/A:1006529012972]
2. G. B. Dantzig, Fulkerson, R., & Johnson, S, "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, 1954. [DOI:10.1287/opre.2.4.393]
3. M. Gen, & Cheng, R, Genetic Algorithms and Engineering Design. New York, United States: Wiley, 1997. [DOI:10.1002/9780470172254]
4. M. M. Alipour, S. N. Razavi, M. R. F. Derakhshi, and M. A. Balafar, "A hybrid algorithm using a genetic algorithm and multiagent reinforcement learning heuristic to solve the traveling salesman problem," Neural Computing and Applications, pp. 1-17, 2018.
5. M. Dorigo, & Stützle, T, Ant Colony Optimization. Cambridge: MIT Press, 2004. [DOI:10.7551/mitpress/1290.001.0001]
6. F. Gutierrez, et al, "A Comparative Study on Metaheuristic Algorithms for Solving NP-Hard Problems," Computational Optimization and Applications, 2020.
7. علیپور میر محمد، عبدالحسین زاده محسن، «ارائۀ الگوریتمی جدید برای تشخیص اجتماع با استفاده از یادگیری تقویتی چندعاملی»، پردازش علائم و داده‌ها، ۱۹ (۱)، 100-87، ۱۴۰۱.
7. M. M. Alipour and M. Abdolhosseinzadeh, "A Multiagent Reinforcement Learning algorithm to solve the Community Detection Problem," (in eng), Signal and Data Processing, Research vol. 19, no. 1, pp. 87-100, 2022. [Online]. Available: http://jsdp.rcisp.ac.ir /article-1-1084-en.html [DOI:10.52547/jsdp.19.1.87]
8. D. E. Goldberg, & Lingle, R, "Alleles, loci, and the traveling salesman problem," in Proceedings of the 1st International Conference on Genetic Algorithms, Pittsburgh, 1985, pp. 154-159.
9. I. Oliver, Smith, D. R., & Holland, J. H, "A study of permutation crossover operators on the travelling salesman problem," in Proceedings of the 2nd International Conference on Genetic Algorithms, Pittsburgh, 1987, pp. 224-230.
10. J. K. L. E.L. Lawler, A.H.G. Rinnooy Kan, D.B. Shmoys, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, 1985.
11. T. Bektas, "The multiple traveling salesman problem: An overview of formulations and solution procedures," Omega, vol. 34, no. 3, pp. 209-219, 2006. [DOI:10.1016/j.omega.2004.10.004]
12. M. F. Demiral, "An artificial intelligence technique: experimental analysis of population-based physarum-energy optimiz ation algorithm," Discover Artificial Intelligence, vol. 5, no. 1, p. 115, 2025/06 /19 2025, doi: 10.1007/s44163-025-00367-w. [DOI:10.1007/s44163-025-00367-w]
13. Y. Wang, "The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem," Computers & Industrial Engineering, vol. 70, pp. 124-133, 2014/04/01/ 2014, doi:
https://doi.org/10.1016/j.cie.2014.01.015 [DOI:10.1016/j.cie.2014.01.015.]
14. K.-P. Wang, L. Huang, C.-G. Zhou, and W. Pang, Particle swarm optimization for traveling salesman problem. 2003, pp. 1583-1585 Vol.3.
15. M. A. H. Akhand, S. Hossain, and S. Akter, "A Comparative Study of Prominent Particle Swarm Optimization Based Methods to Solve Traveling Salesman Problem," International Journal of Swarm Intelligence and Evolutionary Computation, vol. 5, 10/28 2016, doi: 10.4172/2090-4908.1000139. [DOI:10.4172/2090-4908.1000139]
16. M. Dorigo and L. M. Gambardella, "Ant colonies for the travelling salesman problem," Biosystems, vol. 43, no. 2, pp. 73-81, 1997/07/01/ 1997, doi: https://doi.org/ 10.1016/S0303-2647(97)01708- .
https://doi.org/10.1016/S0303-2647(97)01708-5 [DOI:10.1016/S0303-2647(97)01708- .]
17. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by Simulated Annealing," Science, vol. 220, no. 4598, pp. 671-680, 1983/05/13 1983, doi: 10.1126/science.220.4598.671. [DOI:10.1126/science.220.4598.671]
18. P. Victer Paul, C. Ganeshkumar, P. Dhavachelvan, and R. Baskaran, "A novel ODV crossover operator-based genetic algorithms for traveling salesman problem," Soft Computing, vol. 24, no. 17, pp. 12855-12885, 2020/09/01 2020, doi: 10.1007/s00500-020-04712-2. [DOI:10.1007/s00500-020-04712-2]
19. J. de Vasconcelos, J. Ramirez, R. Takahashi, and R. Saldanha, "Improvements in Genetic Algorithms," Magnetics, IEEE Transactions on, vol. 37, pp. 3414-3417, 10/01 2001, doi: 10.1109/20.952626. [DOI:10.1109/20.952626]
20. J. Zhang, "An Improved Genetic Algorithm with 2-Opt Local Search for the Traveling Salesman Problem," in Application of Intelligent Systems in Multi-modal Information Analytics, Cham, V. Sugumaran, Z. Xu, and H. Zhou, Eds., 2021// 2021: Springer International Publishing, pp. 404-409. [DOI:10.1007/978-3-030-74814-2_57]
21. Y. Dong, Q. Wu, and J. Wen, "An improved shuffled frog-leaping algorithm for the minmax multiple traveling salesman problem," Neural Computing and Applications, vol. 33, pp. 1-13, 12/01 2021, doi: 10.1007/s00521-021-06298-8. [DOI:10.1007/s00521-021-06298-8]
22. Y. Fang and J. li, A Review of Tournament Selection in Genetic Programming. 2010, pp. 181-192. [DOI:10.1007/978-3-642-16493-4_19]
23. G. Reinelt, "TSPLIB - A traveling salesman problem library.," ORSA Journal on Computing, vol. 4, no. 376-384, p. 3, 1991. [DOI:10.1287/ijoc.3.4.376]
24. Ş. Dalkılıç, A. Özgür, and H. Erdem, "Comparison of Genetic Crossover Operators for Traveling Salesman Problem," Gazi University Journal of Science, vol. 38, pp. 1-1, 03/09 2025, doi: 10.35378/ gujs.1582521.
ارسال پیام به نویسنده مسئول
| بازنشر اطلاعات | |
 |
این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است. |