An Improved GA with Initial Population Technique for the Travelling Salesman Problem
| العنوان بلغة أخرى: |
التحسين على الخوارزمية الجينية من خلال المدخلات الاولية لحل مشكلة البائع المتجول |
|---|---|
| المؤلف الرئيسي: | أبو قديري، سلام عامر (مؤلف) |
| مؤلفين آخرين: | العبادي، محمد علي حسين (مشرف) |
| التاريخ الميلادي: |
2017
|
| موقع: | مؤتة |
| الصفحات: | 1 - 56 |
| رقم MD: | 951050 |
| نوع المحتوى: | رسائل جامعية |
| اللغة: | الإنجليزية |
| الدرجة العلمية: | رسالة ماجستير |
| الجامعة: | جامعة مؤتة |
| الكلية: | عمادة الدراسات العليا |
| الدولة: | الاردن |
| قواعد المعلومات: | Dissertations |
| مواضيع: | |
| رابط المحتوى: |
عدد مرات التحميل
10
| المستخلص: |
تعتبر الخوارزميات الجينية (Genetic Algorithms) من إحدى الخوارزميات التابعة للخوارزميات التطورية (Evolutionary Algorithms)، حيث برزت أهميتها في حل العديد من المشاكل المعقدة (Complex problems)، وتمتلك العديد من الحلول البديلة، بحيث يكون الحل الناتج أقرب للحل الأمثل. تحاول الخوارزميات الجينية الوصول للحل الأمثل بناء على مبدأ داروين في الاصطفاء الطبيعي (Natural Selection): "البقاء للأفضل"، وتطبق ثلاث عمليات أساسية في عملية البحث: الانتخاب والعبور، والطفرة، وذلك للحصول على العديد من الأفراد في كل جيل، ومن ثم اختيار الأفضل من هذه الأفراد. تعتبر عملية إنشاء الجيل البدائي (Initial Population) من أول خطوات تطبيق الخوارزميات الجينية وتعتبر من الخطوات المهمة في تنويع الأفراد، حيث تعتمد هذه العملية على اختيار جيل بدائي عشوائي بدون أي تقنية معينة، ونظرا لاهتمام الأبحاث في الحصول على التنويع في الأفراد للجيل البدائي وبالتالي تجنب الوقوع في التقارب السابق (Premature Convergence)، ظهرت العديد من التقنيات التي تحاول إيجاد الاختلاف والتنويع في الأفراد وبالتالي الوصول للحل الأمثل أو الأقرب للأمثل. في هذه الأطروحة قمنا باقتراح طريقة لاختيار أفراد الجيل البدائي التي تعتمد على مبدأ تحليل الانحدار (Regression Analysis)، تسمى " Regression Based Technique For GA’s Population Initialization (Reg)"، وتعتمد هذه الطريقة على تقسيم المدن إلى أربعة فئات وفي كل مرة وتعاد هذه العملية. وفي النهاية يتم ربط المجموعات بمسار محلي (Local path) ومن ثم ربطها بمسمار واحد عام (Global path). لقد قمنا بتطبيق التقنية على مشكلة البائع المتجول (TSP)، ومقارنة هذه التقنية بطرق مختلفة موجودة مسبقا، وأظهرت النتائج تفوق التقنية المعتمدة على الانحدار على الطرق الأخرى. حيث أظهرت التقنية المقترحة تفوق في الأداء في المعايير التالية: نسبة الخطأ (Error Rate)، معدل التقارب (Average Convergence). |
|---|
عناصر مشابهة
-
Improving Initial Population for GA Using Multi Linear Regression Based Technique (MLRBT): Experimental on the Travelling Salesman Problem
بواسطة: الطراونه، صخر حسان منشور: (2019) -
Evaluation of Algorithms for Solving Traveling Salesman Problem
بواسطة: كنانة، آمنة جميل منشور: (2023) -
Dragonfly Algorithm with Adaptive Parameters Tuning for Solving Traveling Salesman Problem
بواسطة: أبو سمرة، إيناس توفيق صبحي منشور: (2018) -
THE TRAVELING SALESMAN PROBLEM: LITERATURE SURVEY AND COMPARISON OF TWO COMPUTATIONAL METHODS
بواسطة: Ghalib, Hani M. منشور: (1979) -
Travelling Salesman Problem over Chained-Cubic Tree Using Genetic Algorithm and Ant Colony
بواسطة: الكوفحي، خالد أحمد عبدالعزيز منشور: (2017)
