کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6903264 1446989 2018 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Creating hard-to-solve instances of travelling salesman problem
ترجمه فارسی عنوان
ایجاد مواردی که به سختی حل می شود مشکل فروشندگان مسافرتی است
کلمات کلیدی
ترجمه چکیده
مشکل حمل و نقل فروشنده یک مشکل بهینه سازی ترکیبی است کلاسیک. نمونه هایی از این مشکل به عنوان معیار برای تست عملکرد بسیاری از پیشنهادات الگوریتم های بهینه کننده گسسته استفاده شده اند. با این حال، سختی یا درجه سختی برای حل موارد معمولا مورد توجه نیست. در گذشته، ارزیابی سختی موارد مورد نیاز برای به دست آوردن یک راه حل با کیفیت بالا، در بهترین حالت بهینه است. با این وجود، این نوع استراتژی با ارزیابی با پردازش های بزرگ روبرو می شود. در این کار، اقدامات غیرمستقیم غیرمستقیم برای ارزیابی سختی جهت حل موارد نمونه مسیر فروش فروشنده پیشنهاد می شود. این ارزیابی ها از ویژگی های فضایی نمونه های قبلا ارزیابی شده است و بعدها با سختی نمونه ها همبستگی دارد. در نهایت، که در آن یک همبستگی معنی پیدا شده است، یک مدل خطی ساخته شده است و با یک الگوریتم ژنتیکی مرتبط است. به عنوان یک نتیجه از این کار، مکانیسم هایی برای سخت شدن نمونه هایی از مشکلات فروشندگان مسافرتی اجرا می شود.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نرم افزارهای علوم کامپیوتر
پیش نمایش مقاله
ایجاد مواردی که به سختی حل می شود مشکل فروشندگان مسافرتی است
چکیده انگلیسی
Travelling salesman problem is a classical combinatorial optimization problem. Instances of this problem have been used as benchmark for testing the performance of many proposals of discrete optimizer algorithms. However, the hardness or the difficulty degree to solve the instances has not been usually addressed. In the past the evaluation of the difficulty of the instances has required to obtain a high-quality solution, ideally the optimal one. However, this type of strategy burdens the evaluation with large processing times. In this work, diverse indirect measures for evaluating the hardness to solve instances of the travelling salesman problem are proposed. These evaluations are inferred from the spatial attributes of previously evaluated instances, and later correlated with the hardness of the instances. Finally, where a significant correlation is found, a linear model is built and linked to a genetic algorithm. As a consequence of this work, mechanisms for hardening instances of travelling salesman problem are implemented.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Soft Computing - Volume 71, October 2018, Pages 268-276
نویسندگان
,