Signal and Data Processing

fa بهبود عملکرد الگوریتم‌های ژنتیک در حل مسئله فروشنده دوره‌گرد با معرفی عملگر تقاطع ترتیب بافاصله نزدیک A novel Near Distance Order Crossover to improve the performance of genetic algorithms for solving the TSP مقالات پردازش داده‌های رقمی Paper پژوهشي Research مسئله فروشنده دوره‌گرد (TSP) به دلیل تعداد بسیار بالای حالت‌های ممکن برای مسیریابی به‌شدت پیچیده و زمان‌بر است، به‌طوری‌که برای حل این مسئله الگوریتم‌های دقیق و تقریبی مختلفی از جمله الگوریتم ژنتیک موردتوجه قرار گرفته است. در این مقاله الگوریتم جدیدی برای حل مسئله TSP با استفاده از عملگر تقاطع ترتیب با فاصله نزدیک (NDOX) ارائه شده است که هدف از آن بهبود کیفیت مسیریابی در کمترین زمان ممکن نسبت به روش‌های دیگر است که مهم‌ترین ویژگی این عملگر تقاطع جدید استفاده از فاصله بین شهرها ضمن حفظ تنوع جمعیت است و این عملگر نسخه‌ای پیشرفته از عملگر تقاطع ترتیبی (OX) است. یک الگوریتم ژنتیک بهینه برای استفاده از این عملگر تقاطع (GNDOX) نیز ارائه می‌شود، این الگوریتم با به‌کارگیری عملگر NDOX قادر است مسیرهای کوتاه‌تر و کارآمدتری نسبت به الگوریتم‌های ژنتیک معمولی تولید کند. نتایج الگوریتم ژنتیک پیشنهادی بر روی 26 نمونه مسئله استاندارد TSP از TSPLIB، از اندازه‌های مختلف، مورد ارزیابی قرار گرفته و طبق نتایج به‌دست‌آمده عملگر پیشنهادی در 50% موارد از عملگرهای مقایسه شده مانند PMX، CX، OX و چندین عملگر تقاطع دیگر عملکرد قابل‌قبول و بهتری داشته و علاوه‌برآن زمان محاسباتی را نیز به‌شدت کاهش داده است و پس از آن الگوریتم پیشنهادی نیز مورد مقایسه با تعدادی از الگوریتم‌های مرسوم مانند ACO، PSO، SA و چندین مورد از الگوریتم‌های ارائه شده در مقالات معتبر قرار گرفته و بر اساس نتایج به‌دست‌آمده در کیفیت جواب‌ها و در زمان اجرای موردنیاز الگوریتم پیشنهادی، دستاوردهای قابل‌دفاعی در بین روش‌های فراابتکاری داشته و توانسته عملکرد مناسبی در حفظ تعادل میان اکتشاف و بهره‌برداری نشان دهد و همچنین نتایج تجربی به‌دست‌آمده حاکی از قابلیت رقابت الگوریتم ارائه شده، بر مبنای کیفیت نتایج و زمان محاسباتی، در مقایسه با تعدادی از الگوریتم‌های اکتشافی و فرااکتشافی مطرح در این زمینه را دارند. 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 Mir Mohammad Alipour میرمحمد علیپور alipour@ubonab.ac.ir 100319475328460014262 100319475328460014262 Yes University of Bonab دانشگاه بناب Ali Heydari علی حیدری a.heydari@ubonab.ac.ir 100319475328460014263 100319475328460014263 No University of Bonab دانشگاه بناب Mohsen Abdolhosseinzadeh محسن عبدالحسین زاده mohsen.ab@ubonab.ac.ir 100319475328460014264 100319475328460014264 No University of Bonab دانشگاه بناب Hojjat Emami حجت امامی emami@ubonab.ac.ir 100319475328460014265 100319475328460014265 No University of Bonab دانشگاه بناب علی 100319475328460014266 100319475328460014266 No