![](/images/graphics-bg.png)
Improving initial population for GA using multi linear regression based technique (MLRBT) : experimental on the travelling salesman problem
Other Title(s)
التحسين على الخوارزمية الجينية من خلال إنشاء الجيل البدائي لحل مشكلة البائع المتجول
Dissertant
al-Tarawinah, Sakhr Hasan Muhammad
Thesis advisor
University
Mutah University
Faculty
Information Technology College
Department
Computer Science Department
University Country
Jordan
Degree
Master
Degree Date
2019
Arabic Abstract
الخوارزمية الجينية GA Genetic Algorithms ) ) هي واحدة من تقنيات البحث الارشادية القوية تستخدم بنجاح في حل مشكلات العديد من التطبيقات المختلفة؛ البحث في GAS لن يتوقف أبدا للحصول على نتائج افضل لتحسين أداء النظرية الجينية ( GAS )، اقترحت العديد من الأعمال و الطرق للتحسين من خلال تضمين ميزة التنوع و تحسين الخصائص في أشكال مختلفة.
تطبيقات النظرية الجينية تبدأ عن طريق الجيل البدائي او الاولي ( Initial Population ) التي تعتبر الخطوة الأولى عند تطوير أو تحسين الأنظمة الذكية.
واحدة من أكثر المعايير لإنشاء الجيل البدائي او الأولي و أكثرها شيوعا هي طريقة التوليد العشوائي.
يتم تحسين أداء الخوارزمية من خلال زيادة سرعة إيجاد الحلول، و تحسين التنوع الفردي، و الجودة.
و بالتالي، تم تطوير تقنية جديدة لإيجاد حيز العمل او جيل اولي لتوليد مجموعات جديدة من للحصول على نتائج افضل في GAS.
تقترح هذه الأطروحة تقنية سكانية أولية جديدة تسمى تقنية الانحدار الخطي المتعدد للخوارزمية الجينية ( Multi Linear Regression Based Technique ( MLRET لإيجاد أساس لتوليد جيل بدائي.
أظهرت تجاربنا نتائج واعدة و افضل من غيرها مما قورنت به في تحسين أداء الخوارزمية الجينية لحل مشكلة البائع المتجول ( TSP ).
في طريقتنا المقترحة، تقوم بإنشاء خط انحدار جديد على المحور السيني X و من ثم خط انحدار على المحور الصادي ل ليتقاطعا و ليس بالضرورة ان يتعامدان ينتج رسم بياني مقسم إلى أربعة مجموعات فرعية كل قسم يحتوي على نفس عدد المدن تقريبا، كل مجموعة تنقسم بشكل متكرر إلى أن كل قسم الى اربع مدن او اقل لكل مجموعة فرعية.
و في النهاية يتم ربط المجموعات بمسار محلي و من ثم ربطها بمسار واحد عام .
لقد قمنا بتطبيق التقنية على مشكلة البائع المتجول ( TSP ).
أظهرت النتائج أن التقنية المقترحة ( MLRBT ) هي أفضل التقنيات أداء مقارنة مع طرق موجودة مسبقا بناء على معايير الأداء لكل تقنية، بما في ذلك : معدل الخطأ ( Error Rate ) ، و معدل التقارب ( Average Convergence ).
English Abstract
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.
Main Subjects
Information Technology and Computer Science
No. of Pages
49
Table of Contents
Table of contents.
Abstract.
Abstract in Arabic.
Chapter One : Introduction.
Chapter Two : Related works.
Chapter Three : Methodology.
Chapter Four : Experimental results and discussion.
References.
American Psychological Association (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
Modern Language Association (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
American Medical Association (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
Language
English
Data Type
Arab Theses
Record ID
BIM-1382279