Improving initial population for GA using multi linear regression based technique (MLRBT) : experimental on the travelling salesman problem
العناوين الأخرى
التحسين على الخوارزمية الجينية من خلال إنشاء الجيل البدائي لحل مشكلة البائع المتجول
مقدم أطروحة جامعية
al-Tarawinah, Sakhr Hasan Muhammad
مشرف أطروحة جامعية
الجامعة
جامعة مؤتة
الكلية
كلية تكنولوجيا المعلومات
القسم الأكاديمي
قسم الحاسوب
دولة الجامعة
الأردن
الدرجة العلمية
ماجستير
تاريخ الدرجة العلمية
2019
الملخص العربي
الخوارزمية الجينية GA Genetic Algorithms ) ) هي واحدة من تقنيات البحث الارشادية القوية تستخدم بنجاح في حل مشكلات العديد من التطبيقات المختلفة؛ البحث في GAS لن يتوقف أبدا للحصول على نتائج افضل لتحسين أداء النظرية الجينية ( GAS )، اقترحت العديد من الأعمال و الطرق للتحسين من خلال تضمين ميزة التنوع و تحسين الخصائص في أشكال مختلفة.
تطبيقات النظرية الجينية تبدأ عن طريق الجيل البدائي او الاولي ( Initial Population ) التي تعتبر الخطوة الأولى عند تطوير أو تحسين الأنظمة الذكية.
واحدة من أكثر المعايير لإنشاء الجيل البدائي او الأولي و أكثرها شيوعا هي طريقة التوليد العشوائي.
يتم تحسين أداء الخوارزمية من خلال زيادة سرعة إيجاد الحلول، و تحسين التنوع الفردي، و الجودة.
و بالتالي، تم تطوير تقنية جديدة لإيجاد حيز العمل او جيل اولي لتوليد مجموعات جديدة من للحصول على نتائج افضل في GAS.
تقترح هذه الأطروحة تقنية سكانية أولية جديدة تسمى تقنية الانحدار الخطي المتعدد للخوارزمية الجينية ( Multi Linear Regression Based Technique ( MLRET لإيجاد أساس لتوليد جيل بدائي.
أظهرت تجاربنا نتائج واعدة و افضل من غيرها مما قورنت به في تحسين أداء الخوارزمية الجينية لحل مشكلة البائع المتجول ( TSP ).
في طريقتنا المقترحة، تقوم بإنشاء خط انحدار جديد على المحور السيني X و من ثم خط انحدار على المحور الصادي ل ليتقاطعا و ليس بالضرورة ان يتعامدان ينتج رسم بياني مقسم إلى أربعة مجموعات فرعية كل قسم يحتوي على نفس عدد المدن تقريبا، كل مجموعة تنقسم بشكل متكرر إلى أن كل قسم الى اربع مدن او اقل لكل مجموعة فرعية.
و في النهاية يتم ربط المجموعات بمسار محلي و من ثم ربطها بمسار واحد عام .
لقد قمنا بتطبيق التقنية على مشكلة البائع المتجول ( TSP ).
أظهرت النتائج أن التقنية المقترحة ( MLRBT ) هي أفضل التقنيات أداء مقارنة مع طرق موجودة مسبقا بناء على معايير الأداء لكل تقنية، بما في ذلك : معدل الخطأ ( Error Rate ) ، و معدل التقارب ( Average Convergence ).
الملخص الإنجليزي
Genetic algorithms (GAs) are a powerful heuristic search techniques that are used successfully to solve problems for many different applications; research on GAs will never stop to improve the performance.
To improve the performance of GA, many works proposed enhanced strategies by embedding the diversity-maintenance feature in different forms.
Application of GAs starts by seeding the initial population which is considered as the first step when developing smart systems.
One of the most popular initial populations is random generation method, which is considered as one of the most important GAs parameters that improves the GA performance to find the optimal solution.
Indeed, enhancing Gas performance is achieved by increasing the speed of finding solution, improving individual diversity, and quality.
Thus, a new population seeding technique has been developed to generate new populations for GA input parameters.
This thesis proposes a new initial population technique called Multi Linear Regression Based Technique (MLRBT) for GA‟s initial population.
Our experiments showed promising results in improving the Gas performance to solve Travelling Salesman Problem (TSP).
In our proposed method we create a new regression line on Y axis and rotate the line to be interrupts the X axis.
It produces graph divided to four subgroups ; each group split recursively for each subgroup.
The experiments were carried out using the well-known Travelling Salesman Problem (TSP) instances obtained from the TSPLIB, which is the standard library for TSP problems.
Results showed that the proposed technique (MLRBT) is the best performing techniques compared to Random, NN and Regression Based Technique RBT based on the performance criteria for each technique, including: Error Rate, Average Convergence and final solution Error Rate.
التخصصات الرئيسية
تكنولوجيا المعلومات وعلم الحاسوب
عدد الصفحات
49
قائمة المحتويات
Table of contents.
Abstract.
Abstract in Arabic.
Chapter One : Introduction.
Chapter Two : Related works.
Chapter Three : Methodology.
Chapter Four : Experimental results and discussion.
References.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
al-Tarawinah, Sakhr Hasan Muhammad. (2019). Improving initial population for GA using multi linear regression based technique (MLRBT) : experimental on the travelling salesman problem. (Master's theses Theses and Dissertations Master). Mutah University, Jordan
https://search.emarefa.net/detail/BIM-1382279
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
al-Tarawinah, Sakhr Hasan Muhammad. Improving initial population for GA using multi linear regression based technique (MLRBT) : experimental on the travelling salesman problem. (Master's theses Theses and Dissertations Master). Mutah University. (2019).
https://search.emarefa.net/detail/BIM-1382279
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
al-Tarawinah, Sakhr Hasan Muhammad. (2019). Improving initial population for GA using multi linear regression based technique (MLRBT) : experimental on the travelling salesman problem. (Master's theses Theses and Dissertations Master). Mutah University, Jordan
https://search.emarefa.net/detail/BIM-1382279
لغة النص
الإنجليزية
نوع البيانات
رسائل جامعية
رقم السجل
BIM-1382279
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر
