Pengaruh mekanisme Multi-Parent pada Nearest Neighbor Crossover dalam Algoritma Genetika untuk penyelesaian traveling salesmen problem

INDONESIA:

Traveling Salesman Problem (TSP) merupakan permasalahan optimasi kombinatorial yang tergolong NP-hard, di mana tujuannya adalah menemukan lintasan terpendek yang mengunjungi setiap kota tepat satu kali dan kembali ke kota asal. Salah satu pendekatan yang digunakan untuk menyelesaikan TSP adalah algoritma genetika (AG), yang efektivitasnya sangat dipengaruhi oleh operator crossover. Penelitian ini mengembangkan operator Nearest Neighbor Crossover (NNX) dengan menerapkan mekanisme multi-parent sehingga menghasilkan Multi-Parent Nearest Neighbor Crossover (MPNNX) yang melibatkan tiga induk dalam proses crossover. Pengujian dilakukan menggunakan dataset pr1002 dari TSPLIB yang memiliki 1.002 titik kota, dengan 35 kali percobaan untuk masing-masing metode menggunakan bahasa pemrograman Python di Google Colaboratory. Hasil penelitian menunjukkan bahwa MPNNX menghasilkan nilai rata-rata total jarak sebesar 1.955.529,184 dan nilai minimum sebesar 1.480.099,216, keduanya lebih kecil dibandingkan NNX yang menghasilkan rata-rata 2.392.412,232 dan minimum 1.611.346,468. Perbedaan performa kedua metode terbukti signifikan secara statistik berdasarkan uji Mann-Whitney U dengan p-value sebesar 0,0000046281. Secara keseluruhan, MPNNX lebih unggul dalam menghasilkan rute yang lebih pendek, sedangkan NNX menunjukkan konsistensi hasil yang lebih baik antarpercobaan.

INGGRIS:

The Traveling Salesman Problem (TSP) is an NP-hard combinatorial optimization problem that aims to find the shortest route visiting each city exactly once before returning to the origin. One approach used to solve TSP is the Genetic Algorithm (GA), whose effectiveness is greatly influenced by the crossover operator applied. This study develops the Nearest Neighbor Crossover (NNX) operator by incorporating a multi-parent mechanism, producing Multi-Parent Nearest Neighbor Crossover (MPNNX) which involves three parent chromosomes in the crossover process. Testing was conducted using the pr1002 dataset from TSPLIB consisting of 1,002 city nodes, with 35 runs for each method implemented in Python via Google Colaboratory. The results show that MPNNX produces a mean total distance of 1,955,529.184 and a minimum of 1,480,099.216, both lower than NNX which yields a mean of 2,392,412.232 and a minimum of 1,611,346.468. The performance difference between both methods is statistically significant based on the Mann-Whitney U test with a p-value of 0.0000046281. Overall, MPNNX is superior in generating shorter routes, while NNX demonstrates greater consistency across runs.

ARAB:

مشكلة البائع المتجول (TSP) هي مشكلة تحسين تركيبية تُصنف ضمن فئة NP-hard ، حيث يتمثل الهدف منها في إيجاد أقصر مسار يزور كل مدينة مرة واحدة فقط ثم يعود إلى المدينة الأصلية. ومن بين الأساليب المستخدمة لحل مشكلة البائع المتجول (TSP) الخوارزمية الجينية (AG) ، التي تتأثر فعاليتها بشكل كبير بمشغل التهجين. تطور هذه الدراسة عامل التهجين Nearest Neighbor Crossover (NNX) من خلال تطبيق آلية متعددة الأبوين، مما ينتج عنه Multi-Parent Nearest Neighbor Crossover (MPNNX) الذي يشمل ثلاثة آباء في عملية التهجين. تم إجراء الاختبار باستخدام مجموعة البيانات pr١٠٠٢ من TSPLIB التي تحتوي على ١٬٠٠٢ نقطة مدينة، مع ٣٥ تجربة لكل طريقة باستخدام لغة البرمجة Python في Google Colaboratory. أظهرت نتائج البحث أن MPNNX أنتجت متوسطًا إجماليًا للمسافة يبلغ ١٬٩٥٥٬٥٢٩٫١٨٤ وقيمة دنيا تبلغ ١٬٤٨٠٬٠٩٩٫٢١٦، وكلاهما أقل مقارنةً بـ NNX التي أنتجت متوسطًا يبلغ ٢٬٣٩٢٬٤١٢٫٢٣٢ وقيمة دنيا تبلغ ١٬٦١١٬٣٤٦٫٤٦٨. وقد ثبت أن الفرق في أداء الطريقتين ذو دلالة إحصائية بناءً على اختبار Mann-Whitney U بقيمة p تبلغ ٠,٠٠٠٠٠٤٦٢٨١. وبشكل عام، يتفوق MPNNX في إنتاج مسارات أقصر، بينما يُظهر NNX اتساقًا أفضل في النتائج بين التجارب.