عنوان الإطروحه |
Solving Travelling Salesman Problem Using Group Constructive Crossover and Cost-Based Mutation
|
تاريخ مناقشة الاطروحه |
2014-12-18 |
اسم الطالب |
سهيله فرحان احمد ابوعويضه
|
المشرف |
خالد محمد عبدالرحمن بطيحة |
|
المشرف المشارك |
وفاء صليبي الشرفات
|
اعضاء لجنة المناقشة |
| قاسم احمد قاسم الردايدة |
| عمر علي شطناوي |
| جهاد قبيل عوده النهود |
|
الكلية |
كلية الامير الحسين بن عبدالله لتكنولوجيا المعلومات |
القسم |
علم الحاسوب |
الملخص بالعربية |
في هذا البحث قدنا خوارزمية لحل مشكلة البائع المتجول عن طريق تطوير mutation و crossover باستخدام الخوارزمية الجينية , وقد تم تسمية crossover الخاص في هذا البحث ب Group Constructive Crossover (GCX) and أما mutation قد تم تسميته ب cost-based mutation, وقد تم تطبيق الأنواع المختلفة للخوارزمية الجينية حتى يتم استخدام أفضل نوع للخوارزمية الجينية للوصول لأفضل الحلول لحل مشكلة البائع المتجول. وتتجلى أهمية هذا البحث انه تم مقارنته مع خوارزميتين وهم Sequential Constructive crossover (SCX) and The ordered clustered travelling salesman problem: A Hybrid Genetic Algorithm (HGA) , وقد تم تطبيق مشكلة البائع المتجول بشكليها وهم : وهما مشكلة البائع المتجول المتماثلة والغير متماثلة استنادا على أستخدم قاعدة بيانات قياسية تسمى TSPLIB. والنتائج أظهرت أن الخوارزمية التي تم تقديمها في هذا البحث أفضل من SCX و HGA في معظم الحالات. |
الملخص بالانجليزي |
The Traveling Salesman Problem (TSP) is an NP-complete problem combinatorial optimization problem and has been one of important subjects which have been widely addressed extensively by mathematicians and computer science. This research proposed an algorithm by enhancing crossover and mutation operation using genetic Algorithm (GA) technique with their probabilities which called Group Constructive Crossover (GCX) and cost based mutation and applying different types of GA; Simple Genetic Algorithm (SGA), Steady State Genetic Algorithm (SSGA) and Group Genetic Algorithm (GGA) to demonstrate best GA type to reach an optimal solution. The efficiency of the proposed algorithm is compared as against some existing crossover operators; namely, Sequential Constructive crossover (SCX) and The ordered clustered travelling salesman problem: A Hybrid Genetic Algorithm (HGA) for some symmetric travelling salesman problem (STSP) and Asymmetric Travelling salesman problem (ATSP) using dataset benchmark called TSPLIB. The experimental result show that the proposed algorithm is very effective in terms of solution quality |
رقم ISN |
4358 |
|
للحصول على الرسالة كملف يرجى تزويد المكتبة برقم ISN
|