Travelling Salesman Problem over Chained-Cubic Tree Using Genetic Algorithm and Ant Colony
| العنوان بلغة أخرى: |
مشكلة البائع المتجول على شجرة المكعب-بالسلاسل باستخدام الخوارزمية الجينية ومستعمرة النمل |
|---|---|
| المؤلف الرئيسي: | الكوفحي، خالد أحمد عبدالعزيز (مؤلف) |
| مؤلفين آخرين: | محافظة، باسل علي (مشرف), الشرايعة، أحمد عبدالعزيز (مشرف) |
| التاريخ الميلادي: |
2017
|
| موقع: | عمان |
| الصفحات: | 1 - 117 |
| رقم MD: | 1239463 |
| نوع المحتوى: | رسائل جامعية |
| اللغة: | الإنجليزية |
| الدرجة العلمية: | رسالة ماجستير |
| الجامعة: | الجامعة الاردنية |
| الكلية: | كلية الدراسات العليا |
| الدولة: | الاردن |
| قواعد المعلومات: | Dissertations |
| مواضيع: | |
| رابط المحتوى: |
| المستخلص: |
مشكلة البائع المتجول (Traveling Salesman Problem -TSP) هي مشكلة معروفة والتي تصف بائع يريد زيارة مجموعة من المدن والعودة إلى المدينة التي بدأ منها بأقل تكلفه بشرط أن يزور كل مدينة مرة واحدة فقط. بسبب أن هذه المشكلة مهمة وتعتبر من المشاكل الصعب حلها (NP-Hard problem)، العديد من الباحثين حاولوا إيجاد طريقة أفضل لحل هذه المشكلة باستخدام شبكات متصلة مختلفة. في هذه الرسالة، صممنا وطبقنا خوارزمية الجينات المتوازية-(Genetic Algorithm (GA ومستعمرة النمل المتوازية ((Ant Colony Optimization- ACO لحل مشكلة البائع المتجول على شبكة ربط شجرة المكعبات المتسلسلة، والتي تعتبر شبكة حديثة نسبيا تدمج شبكة المكعب وشكبة الشجرة. وأيضا قمنا بتقييم خوارزمياتنا بشكل تحليلي وبالمحاكاة من ناحية الوقت اللازم للاتصال، الوقت اللازم للحساب، الوقت التنفيذ الكلي، التسريع النسبي والكفاءة النسبية. علاوة على ذلك قارنا نتائج خوارزمية الجينات ومستعمرة النمل على شبكة ربط شجرة المكعبات المتسلسلة مع نفس الخوازرميات على شبكة المكعب وشكبة الشجرة. في عمليات المحاكاة، استخدمنا خرائط من (VLSI Data Sets) كمدخلات: وهذه الخرائط هي DKF و XMF، حيث أن كل خريطة لها خصائصها: كمثال DKF تحتوي على 3954 مدينة، وهذه المدن موزعة بشكل مربع وتقريبا بشكل متوازن: بينما خريطة XMC تحتوي على 10150 مدينة وهذه المدن موزعة بشكل مستطيل وتقريبا بشكل متوازن أيضا. وأضفنا أيضا مرحلة تهيئة للبيانات لتقسيم المدخلات إلى أجزاء صغيرة، والتي تقود إلى تقليل عدد السكان المطلوب لخوارزمية الجينات ولمستعمرة النمل، والتي حسنت الوقت والمساحة المطلوبة بشكل ملحوظ. وأخيرا، النتائج أظهرت أن خوارزمية الجينات ومستعمرة النمل لحل مشكلة البائع المتجول على شبكة ربط شجرة المكعبات المتسلسلة وشبكة المكعب تقريبا تعطي نفس النتائج من ناحية الوقت التنفيذ الكلي، التسريع النسبي والكفاءة النسبية، وأفضل من حل مشكلة البائع المتجول باستخدام خوارزمية الجينات ومستعمرة النمل على شكبة الشجرة للخرائط التي تحتوي على عدد كبير من المدن بين 3954 -10150 مدينة. علاوة على ذلك، وجدنا أن مستعمرة النمل أفضل من خوارزمية الجينات من ناحية تكلفة الزيارة للمدن، حيث أن أفضل نتائج حصلنا عليها من مستعمرة النمل على شبكة ربط شجرة المكعبات المتسلسلة باستخدام 128 جهاز (خريطة 84.1% XMC وخريطة83.7% DKF ). |
|---|
عناصر مشابهة
-
The 0-1 Knapsack Problem on Chained-Cubic Tree Interconnection Network
بواسطة: العموش ، أحمد موسى عويس منشور: (2017) -
Evaluation of Algorithms for Solving Traveling Salesman Problem
بواسطة: كنانة، آمنة جميل منشور: (2023) -
Constructing Initial Solutions For The Multiple Vehicle Pickup And Delivery Problem With Time Windows
بواسطة: Hosny, Manar Ibrahim منشور: (2012) -
An Improved GA with Initial Population Technique for the Travelling Salesman Problem
بواسطة: أبو قديري، سلام عامر منشور: (2017) -
Enhanced Ant Colony Algorithm with Tabu Search and Memory Solution for Solving Scheduling Problems
بواسطة: بيدس، عزت هشام منشور: (2019)
