Treffer: An Enhanced Swap Sequence-Based Particle Swarm Optimization Algorithm to Solve TSP

Le problème du voyageur de commerce (TSP) est un problème d'optimisation combinatoire qui est utile dans un certain nombre d'applications. Comme il n'existe pas d'algorithme polynomial en temps connu pour résoudre les TSP à grande échelle, des algorithmes métaheuristiques tels que Ant Colony Optimization (ACO), Bee Colony Optimization (BCO) et Particle Swarm Optimization (PSO) ont été largement utilisés pour résoudre les problèmes de TSP grâce À leurs solutions de haute qualité. Plusieurs variantes de PSO ont été proposées pour résoudre des problèmes d'optimisation discrets comme TSP. Parmi eux, l'algorithme de base est le PSO basé sur la séquence d'échange, cependant, il ne fonctionne pas bien pour fournir des solutions de haute qualité. Pour améliorer les performances du PSO basé sur la séquence de swap, cet article présente un algorithme PSO basé sur la séquence de swap améliorée en intégrant les stratégies du PSO étendu (XPSO) dans le PSO basé sur la séquence de swap. En effet, bien que XPSO ne soit adapté qu'à la résolution de problèmes d'optimisation continue, il présente une performance élevée parmi les variantes de PSO. Dans notre travail, le problème TSP est utilisé pour modéliser un système de livraison de colis dans la région de Kuala Lumpur. L'ensemble de problèmes se compose de 50 emplacements à Kuala Lumpur. Notre objectif est de trouver l'itinéraire le plus court dans le système de livraison en utilisant le PSO basé sur la séquence d'échange améliorée. Nous évaluons l'algorithme en termes d'efficacité et d'efficience tout en résolvant le TSP. Pour évaluer l'algorithme proposé, les solutions au problème TSP obtenues à partir de l'algorithme proposé et du PSO basé sur la séquence d'échange sont comparées en termes de meilleure solution, de solution moyenne et de temps nécessaire pour converger vers la solution optimale. L'algorithme proposé s'avère fournir de meilleures solutions avec des chemins plus courts lorsqu'il est appliqué à TSP par rapport à un PSO basé sur une séquence de swap. Cependant, le PSO basé sur la séquence de swap converge plus rapidement que l'algorithme proposé lorsqu'il est appliqué à TSP.
El Traveling Salesman Problem (TSP) es un problema de optimización combinatoria que es útil en una serie de aplicaciones. Dado que no existe un algoritmo de tiempo polinómico conocido para resolver TSP a gran escala, los algoritmos metaheurísticos como Ant Colony Optimization (ACO), Bee Colony Optimization (BCO) y Particle Swarm Optimization (PSO) se han utilizado ampliamente para resolver problemas DE TSP a través de sus soluciones de alta calidad. Se han propuesto varias variantes de PSO para resolver problemas de optimización discreta como TSP. Entre ellos, el algoritmo básico es el PSO basado en Swap Sequence, sin embargo, no funciona bien para proporcionar soluciones de alta calidad. Para mejorar el rendimiento de la PSO basada en la secuencia de intercambio, este documento introduce un algoritmo de PSO basado en la secuencia de intercambio mejorada mediante la integración de las estrategias de la PSO expandida (XPSO) en la PSO basada en la secuencia de intercambio. Esto se debe a que, aunque XPSO solo es adecuado para resolver problemas de optimización continua, tiene un alto rendimiento entre las variantes de PSO. En nuestro trabajo, el problema TSP se utiliza para modelar un sistema de entrega de paquetes en el área de Kuala Lumpur. El conjunto de problemas consta de 50 ubicaciones en Kuala Lumpur. Nuestro objetivo es encontrar la ruta más corta en el sistema de entrega mediante el uso de la PSO basada en la secuencia de intercambio mejorada. Evaluamos el algoritmo en términos de efectividad y eficiencia mientras resolvemos el TSP. Para evaluar el algoritmo propuesto, las soluciones al problema TSP obtenidas del algoritmo propuesto y la PSO basada en la secuencia de intercambio se comparan en términos de la mejor solución, la solución media y el tiempo necesario para converger a la solución óptima. Se encuentra que el algoritmo propuesto proporciona mejores soluciones con rutas más cortas cuando se aplica a TSP en comparación con PSO basado en secuencias de intercambio. Sin embargo, se encuentra que la PSO basada en la secuencia de intercambio converge más rápido que el algoritmo propuesto cuando se aplica a TSP.
The Traveling Salesman Problem (TSP) is a combinatorial optimization problem that is useful in a number of applications. Since there is no known polynomial-time algorithm for solving large scale TSP, metaheuristic algorithms such as Ant Colony Optimization (ACO), Bee Colony Optimization (BCO), and Particle Swarm Optimization (PSO) have been widely used to solve TSP problems through their high quality solutions. Several variants of PSO have been proposed for solving discrete optimization problems like TSP. Among them, the basic algorithm is the Swap Sequence based PSO, however, it does not perform well in providing high quality solutions. To improve the performance of the swap sequence based PSO, this paper introduces an Enhanced Swap Sequence based PSO algorithm by integrating the strategies of the Expanded PSO (XPSO) in the swap sequence based PSO. This is because although XPSO is only suitable for solving continuous optimization problems, it has a high performance among the variants of PSO. In our work, the TSP problem is used to model a package delivery system in the Kuala Lumpur area. The problem set consists of 50 locations in Kuala Lumpur. Our aim is to find the shortest route in the delivery system by using the enhanced swap sequence based PSO. We evaluate the algorithm in terms of effectiveness and efficiency while solving TSP. To evaluate the proposed algorithm, the solutions to the TSP problem obtained from the proposed algorithm and swap sequence based PSO are compared in terms of the best solution, mean solution, and time taken to converge to the optimal solution. The proposed algorithm is found to provide better solutions with shorter paths when applied to TSP as compared to swap sequence based PSO. However, the swap sequence based PSO is found to converge faster than the proposed algorithm when applied to TSP.
مشكلة البائع المتنقل (TSP) هي مشكلة تحسين اندماجي مفيدة في عدد من التطبيقات. نظرًا لعدم وجود خوارزمية زمنية متعددة الحدود معروفة لحل TSP على نطاق واسع، فقد تم استخدام خوارزميات metaheuristic مثل Ant Colony Optimization (ACO) و Bee Colony Optimization (BCO) و Particle Swarm Optimization (PSO) على نطاق واسع لحل مشكلات TSP من خلال حلولها عالية الجودة. تم اقتراح العديد من متغيرات PSO لحل مشاكل التحسين المنفصلة مثل TSP. من بينها، الخوارزمية الأساسية هي PSO القائمة على Swap Sequence، ومع ذلك، فهي لا تؤدي أداءً جيدًا في توفير حلول عالية الجودة. لتحسين أداء PSO القائم على تسلسل المبادلة، تقدم هذه الورقة خوارزمية PSO القائمة على تسلسل المبادلة المحسن من خلال دمج استراتيجيات PSO الموسع (XPSO) في PSO القائم على تسلسل المبادلة. وذلك لأنه على الرغم من أن XPSO مناسبة فقط لحل مشاكل التحسين المستمر، إلا أنها تتمتع بأداء عالٍ بين متغيرات PSO. في عملنا، يتم استخدام مشكلة TSP لنمذجة نظام تسليم الطرود في منطقة كوالالمبور. تتكون مجموعة المشكلات من 50 موقعًا في كوالالمبور. هدفنا هو العثور على أقصر طريق في نظام التوصيل باستخدام PSO المحسّن القائم على تسلسل SWAP. نقوم بتقييم الخوارزمية من حيث الفعالية والكفاءة أثناء حل TSP. لتقييم الخوارزمية المقترحة، تتم مقارنة حلول مشكلة TSP التي تم الحصول عليها من خوارزمية PSO المقترحة وتسلسل SWAP من حيث أفضل حل، ومتوسط الحل، والوقت المستغرق للتقارب إلى الحل الأمثل. تم العثور على الخوارزمية المقترحة لتوفير حلول أفضل مع مسارات أقصر عند تطبيقها على TSP مقارنة بـ PSO القائم على تسلسل SWAP. ومع ذلك، تم العثور على أن PSO القائم على تسلسل المبادلة يتقارب بشكل أسرع من الخوارزمية المقترحة عند تطبيقه على TSP.