logo
دوره 23، شماره 1 - ( 3-1405 )                   جلد 23 شماره 1 صفحات 36-19 | برگشت به فهرست نسخه ها

XML English Abstract Print

Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Alipour M M, Heydari A, 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
علیپور میرمحمد، حیدری علی، عبدالحسین زاده محسن، امامی حجت. بهبود عملکرد الگوریتم‌های ژنتیک در حل مسئله فروشنده دوره‌گرد با معرفی عملگر تقاطع ترتیب بافاصله نزدیک. پردازش علائم و داده‌ها. 1405; 23 (1) :19-36

URL: http://jsdp.rcisp.ac.ir/article-1-1476-fa.html

بهبود عملکرد الگوریتم‌های ژنتیک در حل مسئله فروشنده دوره‌گرد با معرفی عملگر تقاطع ترتیب بافاصله نزدیک
میرمحمد علیپور* ، علی حیدری ، محسن عبدالحسین زاده ، حجت امامی
دانشگاه بناب
چکیده:   (12 مشاهده)
مسئله فروشنده دوره‌گرد (TSP) به دلیل تعداد بسیار بالای حالت‌های ممکن برای مسیریابی به‌شدت پیچیده و زمان‌بر است، به‌طوری‌که برای حل این مسئله الگوریتم‌های دقیق و تقریبی مختلفی از جمله الگوریتم ژنتیک موردتوجه قرار گرفته است. در این مقاله الگوریتم جدیدی برای حل مسئله TSP با استفاده از عملگر تقاطع ترتیب با فاصله نزدیک (NDOX) ارائه شده است که هدف از آن بهبود کیفیت مسیریابی در کمترین زمان ممکن نسبت به روش‌های دیگر است که مهم‌ترین ویژگی این عملگر تقاطع جدید استفاده از فاصله بین شهرها ضمن حفظ تنوع جمعیت است و این عملگر نسخه‌ای پیشرفته از عملگر تقاطع ترتیبی (OX) است. یک الگوریتم ژنتیک بهینه برای استفاده از این عملگر تقاطع (GNDOX) نیز ارائه می‌شود، این الگوریتم با به‌کارگیری عملگر NDOX قادر است مسیرهای کوتاه‌تر و کارآمدتری نسبت به الگوریتم‌های ژنتیک معمولی تولید کند. نتایج الگوریتم ژنتیک پیشنهادی بر روی 26 نمونه مسئله استاندارد TSP از TSPLIB، از اندازه‌های مختلف، مورد ارزیابی قرار گرفته و طبق نتایج به‌دست‌آمده عملگر پیشنهادی در 50% موارد از عملگرهای مقایسه شده مانند PMX، CX، OX و چندین عملگر تقاطع دیگر عملکرد قابل‌قبول و بهتری داشته و علاوه‌برآن زمان محاسباتی را نیز به‌شدت کاهش داده است و پس از آن الگوریتم پیشنهادی نیز مورد مقایسه با تعدادی از الگوریتم‌های مرسوم مانند ACO، PSO، SA و چندین مورد از الگوریتم‌های ارائه شده در مقالات معتبر قرار گرفته و بر اساس نتایج به‌دست‌آمده در کیفیت جواب‌ها و در زمان اجرای موردنیاز الگوریتم پیشنهادی، دستاوردهای قابل‌دفاعی در بین روش‌های فراابتکاری داشته و توانسته عملکرد مناسبی در حفظ تعادل میان اکتشاف و بهره‌برداری نشان دهد و همچنین نتایج تجربی به‌دست‌آمده حاکی از قابلیت رقابت الگوریتم ارائه شده، بر مبنای کیفیت نتایج و زمان محاسباتی، در مقایسه با تعدادی از الگوریتم‌های اکتشافی و فرااکتشافی مطرح در این زمینه را دارند.
شماره‌ی مقاله: 2
واژه‌های کلیدی: مسئله فروشنده دوره‌گرد، الگوریتم ژنتیک، عملگر تقاطع ترتیب، عملگر تقاطع ترتیب با فاصله نزدیک
متن کامل [PDF 1272 kb]   (21 دریافت)    
نوع مطالعه: پژوهشي | موضوع مقاله: مقالات پردازش داده‌های رقمی
دریافت: 1404/4/9 | پذیرش: 1404/11/14 | انتشار: 1405/3/31 | انتشار الکترونیک: 1405/3/31
ارسال نظر درباره این مقاله : نام کاربری یا پست الکترونیک شما:
CAPTCHA
ارسال پیام به نویسنده مسئول

بازنشر اطلاعات
Creative Commons License این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است.