Signal and Data Processing

fa بهبود عملکرد الگوریتم‌های ژن‌شناسی در حل مسئلۀ فروشندۀ دوره‌گرد با معرفی عمل‌گر تقاطع ترتیب با فاصلۀ نزدیک A novel Near Distance Order Crossover to improve the performance of genetic algorithms for solving the TSP مقالات پردازش داده‌های رقمی Paper پژوهشي Research <div style="text-align: justify;">مسئله فروشنده دوره‌گرد<a href="#_ftn1" name="_ftnref1" title="">[1]</a> به‌دلیل تعداد بسیار بالای حالت‌های ممکن برای مسیریابی به‌شدت پیچیده و زمان‌بر است؛ به‌طوری‌که برای حل این مسئله الگوریتم‌های دقیق و تقریبی مختلفی ازجمله الگوریتم ژن‌شناسی<a href="#_ftn2" name="_ftnref2" title="">[2]</a> مورد توجه قرار گرفته است. در این مقاله الگوریتم جدیدی برای حل مسئله فروشنده دوره‌گرد با استفاده از عمل‌گر تقاطع ترتیب با فاصله نزدیک<a href="#_ftn3" name="_ftnref3" title="">[3]</a> ارائه شده‌است که هدف از آن، بهبود کیفیت مسیریابی در کمترین زمان ممکن نسبت به روش‌های دیگر است و مهم‌ترین ویژگی این عمل‌گر تقاطع جدید، استفاده از فاصله بین شهرها ضمن حفظ تنوع جمعیت است و این عمل‌گر نسخه‌ای پیشرفته از عمل‌گر تقاطع ترتیبی<a href="#_ftn4" name="_ftnref4" title="">[4]</a> است. یک الگوریتم ژن‌شناسی بهینه برای استفاده از این عمل‌گر تقاطع<a href="#_ftn5" name="_ftnref5" title="">[5]</a> نیز ارائه می‌شود؛ این الگوریتم با به‌کارگیری عمل‌گر تقاطع ترتیب با فاصله نزدیک قادر است مسیرهای کوتاه‌تر و کارآمدتری نسبت به الگوریتم‌های ژن‌شناسی معمولی تولید کند. نتایج الگوریتم ژن‌شناسی پیشنهادی بر روی 26 نمونه مسئله استاندارد فروشنده دوره‌گرد از TSPLIB، از اندازه‌های مختلف، مورد ارزیابی قرار گرفته‌است و طبق نتایج به‌دست‌آمده عمل‌گر پیشنهادی در مواردی از عمل‌گرهای مقایسه‌شده مانند PMX، CX، OX و چندین عمل‌گر تقاطع دیگر عملکرد قابل‌قبول و بهتری داشته‌است؛ علاوه‌برآن زمان محاسباتی را نیز به‌شدت کاهش داده‌است؛ پس از آن الگوریتم پیشنهادی نیز مورد مقایسه با تعدادی از الگوریتم‌های مرسوم مانند ACO، PSO، SA و چندین مورد از الگوریتم‌های ارائه‌شده در مقالات معتبر قرار گرفت و بر اساس نتایج به‌دست‌آمده در کیفیت جواب‌ها و در زمان اجرای موردنیاز الگوریتم پیشنهادی، دستاوردهای قابل‌ دفاعی در بین روش‌های فراابتکاری داشته و توانسته‌است عملکرد مناسبی در حفظ تعادل میان اکتشاف و بهره‌برداری نشان دهد؛ همچنین نتایج تجربی به‌دست‌آمده حاکی از قابلیت رقابت الگوریتم ارائه‌شده، برمبنای کیفیت نتایج و زمان محاسباتی، در مقایسه با تعدادی از الگوریتم‌های اکتشافی و فرااکتشافی مطرح در این زمینه است.</div> <div>  <hr align="left" size="1" width="33%" > <div dir="ltr" id="ftn1"><a href="#_ftnref1" name="_ftn1" title="">[1]</a> Traveling Salesman Problem (TSP)</div> <div dir="ltr" id="ftn2"><a href="#_ftnref2" name="_ftn2" title="">[2]</a> Genetic Algorithm (GA)</div> <div dir="ltr" id="ftn3"><a href="#_ftnref3" name="_ftn3" title="">[3]</a> NDOX</div> <div dir="ltr" id="ftn4"><a href="#_ftnref4" name="_ftn4" title="">[4]</a> OX</div> <div dir="ltr" id="ftn5"><a href="#_ftnref5" name="_ftn5" title="">[5]</a> GNDOX</div> </div> The traveling salesman problem is one of the well-known and oldest combinatorial optimization problems in computer science, operations research, and artificial intelligence. It is widely used as a standard benchmark for measuring the performance of optimization algorithms and has special importance in the literature due to its conceptual and computational challenges. In the general definition of this problem, a salesman must travel through a set of cities such that each city is visited only once, and finally return to his starting point, while minimizing the total distance traveled or cost. According to its NP-Hard nature, this problem quickly becomes more complex as the number of cities increases, and finding its optimal solution with exact methods on large scales is practically impossible or very time-consuming. The practical applications of this problem go far beyond its title and are used in fields such as transportation planning, vehicle routing optimization, distribution network design, routing in computer networks, industrial operation scheduling, robotics, and even genomics. Due to the limitations of exact methods such as dynamic programming, branch and bound, and linear methods, researchers have turned to using meta-heuristic methods such as genetic algorithms, differential evolution algorithms, particle swarm algorithms, simulated annealing and ant algorithms. And among them, genetic algorithms have become very popular due to their conceptual simplicity, high adaptability, and ability to search the solution space extensively. Inspired by the principles of Darwinian natural selection, these algorithms evolve a population of solutions over time using operators such as selection, crossover, and mutation to reach optimal or near-optimal responses. One of the essential components in the efficiency of genetic algorithms is the implementation and selection of operators, especially the crossover operator, which is responsible for combining the characteristics of two parents, playing a vital role in producing high-quality offspring. In this study, a new crossover operator called Near Distance Order Crossover (NDOX) was introduced and investigated. Based on this crossover operator, a genetic algorithm called GNDOX is proposed, which applies NDOX to generate high-quality tours efficiently. It is designed based on the order crossover. The difference is that it optimizes the selection process of the remaining genes by considering distance information between cities. In classical crossovers, the remaining genes are usually introduced into the offspring randomly or in apparent order, but in NDOX, an attempt has been made to perform the chromosome completion process in a more intelligent manner by utilizing the knowledge of the problem, i.e., the distance between nodes. This results in routes that are likely to be more geometrically optimal, with cities closer together. The proposed algorithm works by first transferring a section of the first parent's chromosome directly to the child, then using the distance between the last transferred gene and the remaining genes to complete the remainder of the path, instead of randomly inserting genes from the second parent and thus, each stage of chromosome completion is based on step-by-step distance minimization, ultimately leading to more coherent structures and shorter paths. To evaluate the performance of the proposed operator, a series of experiments have been conducted on several standard TSP datasets, and the results of these experiments show that GNDOX was able to provide competitive performance among common meta-heuristic algorithms, achieving better or comparable results in terms of average tour length, standard deviation, and convergence speed compared to other common algorithms such as PSO, ACO and SA. In many datasets, the proposed algorithm has been able to quickly reach high-quality solutions. In conclusion, it can be said that the design and implementation of the NDOX not only improved the performance of the genetic algorithm in solving the TSP, but showed that combining meta-heuristic methods with structural information of the problem can lead to more efficient and reliable algorithms and this finding can provide a platform for future research to use this approach in other complex problems, and achieve more effective optimization. Also, the proposed operator can be used as a model for developing other genetic operators in similar problems. مسئلۀ فروشندۀ دوره‌گرد, الگوریتم ژن‌شناسی, عمل‌گر تقاطع ترتیب, عمل‌گر تقاطع ترتیب با فاصلۀ نزدیک. Traveling salesman problem Genetic algorithm, Order crossover operator, Distance order crossover 19 36 http://jsdp.rcisp.ac.ir/browse.php?a_code=A-10-1961-2&slc_lang=fa&sid=1 Ali Heydari علی حیدری a.heydari@ubonab.ac.ir No MA Student, Department of Computer Engineering, Faculty of Engineering, University of Bonab, Bonab, Iran دانشجوی کارشناسی‌ارشد، مهندسی کامپیوتر، دانشگاه بناب، بناب، ایران Mir Mohammad Alipour میرمحمد علیپور alipour@ubonab.ac.ir Yes Assistant professor, Department of Computer Engineering, Faculty of Engineering, University of Bonab, Bonab, Iran استادیار دانشکدۀ فنی‌ومهندسی، گروه مهندسی کامپیوتر، دانشگاه بناب، بناب، ایران Mohsen Abdolhosseinzadeh محسن عبدالحسین زاده mohsen.ab@ubonab.ac.ir No Assistant professor, Department of Mathematics and computer science, Basic Science Faculty, University of Bonab, Bonab, Iran استادیار دانشکدۀ علوم پایه، گروه ریاضی و علوم کامپیوتر، دانشگاه بناب، بناب، ایران Hojjat Emami حجت امامی emami@ubonab.ac.ir No Associate professor, Department of Computer Engineering, Faculty of Engineering, University of Bonab, Bonab, Iran دانشیار دانشکدۀ فنی‌ومهندسی، گروه مهندسی کامپیوتر، دانشگاه بناب، بناب، ایران