چطور این مقاله مهندسی کامپیوتر و IT را دانلود کنم؟
فایل انگلیسی این مقاله با شناسه 2005677 رایگان است. ترجمه چکیده این مقاله مهندسی کامپیوتر و IT در همین صفحه قابل مشاهده است. شما می توانید پس از بررسی این دو مورد نسبت به خرید و دانلود مقاله ترجمه شده اقدام نمایید
حجم فایل انگلیسی :
283 Kb
حجم فایل فارسی :
131 کیلو بایت
نوع فایل های ضمیمه :
Pdf+Word
کلمه عبور همه فایلها :
www.daneshgahi.com
عنوان فارسي
حل مسئلهی فروشندهی دورهگرد به وسیلهی الگوریتم ژنتیک و با استفاده از عملگر M-Crossover (عملگر تقاطع چندگانه)
عنوان انگليسي
Unraveling Travelling Salesman Problem by genetic algorithm using m-crossover operator
نویسنده/ناشر/نام مجله
International Conference on Signal Processing, Image Processing and Pattern Recognition
این مقاله چند صفحه است؟
این مقاله ترجمه شده مهندسی کامپیوتر و IT شامل 5 صفحه انگلیسی به صورت پی دی اف و 9 صفحه متن فارسی به صورت ورد تایپ شده است
چکیده
مسئلهی فروشندهی دورهگرد (TSP) را می‌توان یک مسئلهی ان پی سخت و یکی از مسائل بسیار مطالعه شده‌ی مربوط به حوزه‌های پژوهشی دانست. هدف اصلی این مسئله، جستجوی کوتاه‌ترین (یا ارزان‌ترین) مسیر برای یک فروشنده برای پیمایش تمام شهر می‌باشد به طوری که تنها از هر شهر فقط یک‌بار عبور کرده و در نهایت به محل اول خود باز گردد. بسیاری از مسائلی که در زندگی واقعی با آن روبرو هستیم، نمونه‌ای از این مسئله می‌باشند و در صورتی که بتوان مسئلهی فروشندهی دورهگرد را به شکلی کارآمد حل کرد این مسائل را نیز می‌توان حل نمود. از کاربردهای مسئلهی فروشند ی دورهگرد می‌توان به مسیریابی خودرویی، توالی کار، سیم‌کشی کامپیوتر و غیره اشاره کرد. با توجه به اینکه روش‌های نیروی ضربتی را می‌توان روشی غیرممکن دانست، می‌توان از روش‌های هیروستیک برای حل این مسائل استفاده کرد، چرا که این روش‌ها نیاز به انرژی محاسباتی کمتری دارند. اگرچه راهکارهایی که از روش هیروستیک ارائه شده است ممکن است بهترین راهکار نباشد ولی به قطع می‌تواند راهکار بهتری را فراهم سازد. الگوریتم ژنتیک یکی از تکنیک‌های جستجوی هیروستیک بوده که بر مبنای انتخاب طبیعی و ژنتیکی می‌باشد. الگوریتم ژنتیک می‌تواند این کار را با انجام سه عملکرد انتخاب، تقاطع و جهش انجام دهد. در این مقاله، مؤلفین اقدام به ارائه‌ی یک مدل عملکرد تقاطع (کراس آورد) جدیدی نموده‌اند که می‌تواند مسئلهی فروشندهی دورهگرد را حل نماید. مدل پیشنهادی قادر به ایجاد 18 کروموزوم فرزند مختلف از هر دو کروموزوم والد و انتخاب دو کروموزوم فرزند بهتر از این 18 کروموزوم ایجاد شده می‌باشد. ما اقدام به مقایسه‌ی بهره‌وری این عملگر با عملگرهای موجود نموده‌ایم. در آزمایش‌هایی که به وسیلهی این روش جدید تقاطع انجام داده‌ایم، نتایج نشان می‌تواند که جستجوی راهکارهای بهتر در این روش در مقایسه با عملگرهای تقاطع به شکلی سریع‌تر صورت می‌گیرد. علاوه بر این مسئله، چالش‌ها و محدودیت‌های فعالیت پژوهشی پیش رو نیز مطرح شده است.
1-مقدمه
مسئلهی فروشندهی دورهگرد را می‌توان یک مسئلهی ان پی سخت دانست که در آن، یک فروشنده باید همه‌ی شهرهای محدوده‌ی خود را یک‌بار ملاقات کرده و فقط یک‌بار مجاز به ورود به هر شهر می‌باشد و در نهایت باید به نقطه‌ی اولیه خود باز گردد. برای به دست آوردن کوتاه‌ترین مسیر، باید همه‌ی مسیرهای ممکن و فواصل آنها را به دست آورد. اگرچه با این روش، با افزایش تعداد شهرها، تعداد مسیرها نیز به صورت نمایی افزایش پیدا می‌کند. بسیاری از مسائل دنیای واقعی، مانند مسئلهی زمان‌بندی مصاحبه، مسئلهی مسیریابی اتوبوس مدرسه، زمان‌بندی خبر را می‌توان نمونه‌هایی از مسئلهی فروشندهی دورهگرد دانست...
مسئلهی فروشندهی دورهگرد الگوریتم ژنتیک تابع سزاواری عملگر کراس آور (تقاطع)
:کلمات کلیدی
Abstract
Travelling Salesman Problem (TSP) is a NP - Hard problem and one of the most studied problems related to many research areas. The main aim of this problem is to search the shortest (or cheapest) tour for a salesman to visit all cities exactly once and finally return to the starting city. Many real life problems which are a variant of TSP would be solved easily if the Travelling Salesman Problem could be solved that efficiently. Applications of Travelling Salesman Problem consists of Vehicle Routing, Job Sequencing, Computer Wiring, etc. Since brute force approach is an infeasible option, heuristics approach can be fairly relied upon to solve these kind of problems where heuristics approach utilizes much less computing power. Although solution from heuristics approach may not be the best solution, it surely provides much better solution. Genetic algorithm is one such heuristic search technique which is based upon genetic and natural selection. Genetic algorithm can perform this task by applying three operators viz. selection, crossover and mutation. In this paper, the authors propose a new crossover operator model (called m-crossover) of genetic algorithm to solve the travelling salesman problem. The proposed model is able to produce 18 different valid offspring chromosomes from any two valid parent chromosomes and select best two offspring chromosomes from the newly generated 18 chromosomes. We compared the efficiency of our crossover operator with existing crossover operators viz. Partially Mapped Crossover, Order Crossover, Cycle Crossover. Experimental results by applying our new crossover approach prove that it is faster at searching better solutions that the compared crossover operators. In addition to this, challenges and constraints of the proposed research work are also discussed.
Keywords:
genetic algorithms search problems travelling salesman problems computational complexity
سایر منابع مهندسی کامپیوتر و IT در زمینه مسئله فروشنده دوره گرد