An improved GA with initial population technique for the travelling salesman problem
Other Title(s)
التحسين على الخوارزمية الجينية من خلال المدخلات الأولية لحل مشكلة البائع المتجول
Dissertant
Thesis advisor
al-Abbadi, Muhammad Ali Husayn
al-Hasanat, Ahmad Bashir
Comitee Members
al-Kasasibah, Muhammad Sharari Zamil
al-Hammuri, Awni Mansur
University
Mutah University
Faculty
Information Technology College
Department
Computer Science Department
University Country
Jordan
Degree
Master
Degree Date
2017
English Abstract
Genetic Algorithm (GA) is a branch of so-called evolutionary algorithm (EA) that plays a significant role for the solution of complex problems with huge search space.
GA involves three basic operations after creating the initial population: selection, crossover and mutation.
Thus, the GA first task is to create an initial population.
The traditional GAs with random population technique are simple and efficient, however the generated population may contain poor fitness.
Low quality or poor fitness of individuals may lead to take long time to converge to an optimal solution.
Therefore, the fitness or quality of initial population of individuals plays a significant role in determining an optimal or near-optimal solution.
In this thesis, we proposed a new method for the initial population seeding based on regression analysis called regression based technique for GA’s population initialization (RBT).
RBT technique divides a large-scale TSP problem to small sub-problems.
The resulting sub-problems are repeatedly classified to fit into four categories to obtain local optimal solutions.
We analyzed the performance of the traditional population seeding techniques, Random and NN and along with the proposed technique RBT.
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.
The experimental analysis was carried out using the statistical test tools: ANOVA, Duncan and LSD.
Results showed that the proposed technique (RBT) is the best performing techniques compared to Random and NN based on the performance criteria for each technique, including : Error Rate, Average Convergence and final solution Error Rate, Keywords: GAs, population seeding technique, Traveling Salesman Problem, TSPLIB
Main Subjects
Information Technology and Computer Science
No. of Pages
55
Table of Contents
Table of contents.
Abstract.
Abstract in Arabic.
Chapter One : Introduction.
Chapter Two : Literature review.
Chapter Three : Methodology.
Chapter Four : Experimental results and discussion.
References.
American Psychological Association (APA)
Abu Qadiri, Salam Amir. (2017). An improved GA with initial population technique for the travelling salesman problem. (Master's theses Theses and Dissertations Master). Mutah University, Jordan
https://search.emarefa.net/detail/BIM-780528
Modern Language Association (MLA)
Abu Qadiri, Salam Amir. An improved GA with initial population technique for the travelling salesman problem. (Master's theses Theses and Dissertations Master). Mutah University. (2017).
https://search.emarefa.net/detail/BIM-780528
American Medical Association (AMA)
Abu Qadiri, Salam Amir. (2017). An improved GA with initial population technique for the travelling salesman problem. (Master's theses Theses and Dissertations Master). Mutah University, Jordan
https://search.emarefa.net/detail/BIM-780528
Language
English
Data Type
Arab Theses
Record ID
BIM-780528
