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.
چکیده
مسئله‌ی فروشنده‌ی دوره‌گرد (TSP) را می‌توان یک مسئله‌ی ان پی سخت و یکی از مسائل بسیار مطالعه شده‌ی مربوط به حوزه‌های پژوهشی دانست. هدف اصلی این مسئله، جستجوی کوتاه‌ترین (یا ارزان‌ترین) مسیر برای یک فروشنده برای پیمایش تمام شهر می‌باشد به طوری که تنها از هر شهر فقط یک‌بار عبور کرده و در نهایت به محل اول خود باز گردد. بسیاری از مسائلی که در زندگی واقعی با آن روبرو هستیم، نمونه‌ای از این مسئله می‌باشند و در صورتی که بتوان مسئله‌ی فروشنده‌ی دوره‌گرد را به شکلی کارآمد حل کرد این مسائل را نیز می‌توان حل نمود. از کاربردهای مسئله‌ی فروشند ی دوره‌گرد می‌توان به مسیریابی خودرویی، توالی کار، سیم‌کشی کامپیوتر و غیره اشاره کرد. با توجه به اینکه روش‌های نیروی ضربتی را می‌توان روشی غیرممکن دانست، می‌توان از روش‌های هیروستیک برای حل این مسائل استفاده کرد، چرا که این روش‌ها نیاز به انرژی محاسباتی کمتری دارند. اگرچه راهکارهایی که از روش هیروستیک ارائه شده است ممکن است بهترین راهکار نباشد ولی به قطع می‌تواند راهکار بهتری را فراهم سازد. الگوریتم ژنتیک یکی از تکنیک‌های جستجوی هیروستیک بوده که بر مبنای انتخاب طبیعی و ژنتیکی می‌باشد. الگوریتم ژنتیک می‌تواند این کار را با انجام سه عملکرد انتخاب، تقاطع و جهش انجام دهد. در این مقاله، مؤلفین اقدام به ارائه‌ی یک مدل عملکرد تقاطع (کراس آورد) جدیدی نموده‌اند که می‌تواند مسئله‌ی فروشنده‌ی دوره‌گرد را حل نماید. مدل پیشنهادی قادر به ایجاد 18 کروموزوم فرزند مختلف از هر دو کروموزوم والد و انتخاب دو کروموزوم فرزند بهتر از این 18 کروموزوم ایجاد شده می‌باشد. ما اقدام به مقایسه‌ی بهره‌وری این عملگر با عملگرهای موجود نموده‌ایم. در آزمایش‌هایی که به وسیله‌ی این روش جدید تقاطع انجام داده‌ایم، نتایج نشان می‌تواند که جستجوی راهکارهای بهتر در این روش در مقایسه با عملگرهای تقاطع به شکلی سریع‌تر صورت می‌گیرد. علاوه بر این مسئله، چالش‌ها و محدودیت‌های فعالیت پژوهشی پیش رو نیز مطرح شده است.
1-مقدمه
مسئله‌ی فروشنده‌ی دوره‌گرد را می‌توان یک مسئله‌ی ان پی سخت دانست که در آن، یک فروشنده باید همه‌ی شهرهای محدوده‌ی خود را یک‌بار ملاقات کرده و فقط یک‌بار مجاز به ورود به هر شهر می‌باشد و در نهایت باید به نقطه‌ی اولیه خود باز گردد. برای به دست آوردن کوتاه‌ترین مسیر، باید همه‌ی مسیرهای ممکن و فواصل آن‌ها را به دست آورد. اگرچه با این روش، با افزایش تعداد شهرها، تعداد مسیرها نیز به صورت نمایی افزایش پیدا می‌کند. بسیاری از مسائل دنیای واقعی، مانند مسئله‌ی زمان‌بندی مصاحبه، مسئله‌ی مسیریابی اتوبوس مدرسه، زمان‌بندی خبر را می‌توان نمونه‌هایی از مسئله‌ی فروشنده‌ی دوره‌گرد دانست...