Published December 27, 2021
| Version v1
Publication
Open
Novel Metaheuristic Based on Iterated Constructive Stochastic Heuristic: Dhouib-Matrix-3 (DM3)
Description
This paper presents a new metaheuristic named Dhouib-Matrix-3 (DM3) inspired by our recently developed constructive stochastic heuristic Dhouib-Matrix-TSP2 (DM-TSP2) and characterized by only one parameter: the number of iterations. The proposed metaheuristic DM3 is an iterative algorithm in which every iteration is based on two relay hybridization techniques. At first, the constructive stochastic heuristic DM-TSP2 starts by generating a different initial basic feasible solution and then each solution is intensified by the novel procedure Far-to-Near which exchanges far cities by closer ones using three perturbation techniques: insertion, exchange, and 2-opt. Experimental results carried out on the classical travelling salesman problem using the well-known TSP-LIB benchmark instances demonstrate that our approach DM3 outclasses the simulated annealing algorithm, the genetic algorithm, and the cellular genetic algorithm. Furthermore, the proposed DM3 is statistically concurrent to the hybrid simulated annealing cellular genetic algorithm. Nevertheless, DM3 is easier to implement and needs only one parameter to identify (the maximum number of iterations).
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
تقدم هذه الورقة دراسة استكشافية جديدة تسمى Dhouib - Matrix -3 (dm3) مستوحاة من الاستدلال العشوائي البناء الذي طورناه مؤخرًا Dhouib - Matrix - TSP2 (DM - TSP2) وتتميز بمعلمة واحدة فقط: عدد التكرارات. تعد خوارزمية DM3 الميتاهورية المقترحة خوارزمية تكرارية يعتمد فيها كل تكرار على تقنيتي تهجين مرحلتين. في البداية، يبدأ الاستدلال العشوائي البناء DM - TSP2 من خلال توليد حل أولي أساسي مختلف، ثم يتم تكثيف كل حل من خلال الإجراء الجديد من بعيد إلى قريب الذي يتبادل المدن البعيدة عن طريق المدن الأقرب باستخدام ثلاث تقنيات للاضطراب: الإدراج والتبادل و 2 - opt. تُظهر النتائج التجريبية التي تم إجراؤها على مشكلة مندوب المبيعات المتجول الكلاسيكي باستخدام الحالات المعيارية المعروفة لـ TSP - LIB أن نهجنا dm3 يتفوق على خوارزمية التلدين المحاكاة والخوارزمية الوراثية والخوارزمية الوراثية الخلوية. علاوة على ذلك، فإن dm3 المقترح متزامن إحصائيًا مع الخوارزمية الوراثية الخلوية المحاكاة الهجينة. ومع ذلك، فإن dm3 أسهل في التنفيذ ويحتاج إلى معلمة واحدة فقط لتحديدها (الحد الأقصى لعدد التكرارات).Translated Description (French)
Cet article présente une nouvelle métaheuristique nommée Dhouib-Matrix-3 (DM3) inspirée de notre heuristique stochastique constructive récemment développée Dhouib-Matrix-TSP2 (DM-TSP2) et caractérisée par un seul paramètre : le nombre d'itérations. Le DM3 métaheuristique proposé est un algorithme itératif dans lequel chaque itération est basée sur deux techniques d'hybridation de relais. Dans un premier temps, l'heuristique stochastique constructive DM-TSP2 commence par générer une solution de base réalisable initiale différente, puis chaque solution est intensifiée par la nouvelle procédure Far-to-Near qui échange des villes lointaines par des villes plus proches en utilisant trois techniques de perturbation : insertion, échange et 2-opt. Les résultats expérimentaux réalisés sur le problème des vendeurs itinérants classiques en utilisant les instances de référence TSP-LIB bien connues démontrent que notre approche DM3 surpasse l'algorithme de recuit simulé, l'algorithme génétique et l'algorithme génétique cellulaire. En outre, la DM3 proposée est statistiquement concurrente à l'algorithme génétique cellulaire de recuit simulé hybride. Néanmoins, DM3 est plus facile à mettre en œuvre et n'a besoin que d'un seul paramètre à identifier (le nombre maximum d'itérations).Translated Description (Spanish)
Este documento presenta una nueva metaheurística llamada Dhouib-Matrix-3 (DM3) inspirada en nuestra heurística estocástica constructiva recientemente desarrollada Dhouib-Matrix-TSP2 (DM-TSP2) y caracterizada por un solo parámetro: el número de iteraciones. El DM3 metaheurístico propuesto es un algoritmo iterativo en el que cada iteración se basa en dos técnicas de hibridación de relé. Al principio, la heurística estocástica constructiva DM-TSP2 comienza generando una solución factible básica inicial diferente y luego cada solución se intensifica mediante el novedoso procedimiento Far-to-Near que intercambia ciudades lejanas por ciudades más cercanas utilizando tres técnicas de perturbación: inserción, intercambio y 2-opt. Los resultados experimentales llevados a cabo sobre el problema clásico del vendedor ambulante utilizando las conocidas instancias de referencia TSP-LIB demuestran que nuestro enfoque DM3 supera el algoritmo de hibridación simulada, el algoritmo genético y el algoritmo genético celular. Además, el DM3 propuesto es estadísticamente concurrente con el algoritmo genético celular de hibridación simulada híbrido. Sin embargo, DM3 es más fácil de implementar y solo necesita un parámetro para identificarlo (el número máximo de iteraciones).Files
7761993.pdf.pdf
Files
(4.5 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:2de58f71ece45b6ed8e40583b2cf9b36
|
4.5 kB | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- ميتاهوريستيك الرواية على أساس الاستدلال العشوائي البناء المتكرر: Dhouib - Matrix -3 (DM3)
- Translated title (French)
- Nouvelle métaheuristique basée sur l'heuristique stochastique constructive itérée : Dhouib-Matrix-3 (DM3)
- Translated title (Spanish)
- Novedosa metaheurística basada en heurística estocástica constructiva iterada: Dhouib-Matrix-3 (DM3)
Identifiers
- Other
- https://openalex.org/W4200360130
- DOI
- 10.1155/2021/7761993
References
- https://openalex.org/W1982600514
- https://openalex.org/W1993885071
- https://openalex.org/W1995719137
- https://openalex.org/W2061438946
- https://openalex.org/W2086029661
- https://openalex.org/W2126050191
- https://openalex.org/W2134816084
- https://openalex.org/W2290883490
- https://openalex.org/W2403763572
- https://openalex.org/W2803306286
- https://openalex.org/W2884377042
- https://openalex.org/W2906784067
- https://openalex.org/W2944431795
- https://openalex.org/W3035573586
- https://openalex.org/W3041516214
- https://openalex.org/W3063913079
- https://openalex.org/W3083710364
- https://openalex.org/W3123148777
- https://openalex.org/W3126899030
- https://openalex.org/W3127096806
- https://openalex.org/W3131586835
- https://openalex.org/W3135860989
- https://openalex.org/W3163903840
- https://openalex.org/W3168274391
- https://openalex.org/W3173175448
- https://openalex.org/W3210084734
- https://openalex.org/W3210307938
- https://openalex.org/W4250503569
- https://openalex.org/W4256261968