An improved GA with initial population technique for the travelling salesman problem

العناوين الأخرى

التحسين على الخوارزمية الجينية من خلال المدخلات الأولية لحل مشكلة البائع المتجول

مقدم أطروحة جامعية

Abu Qadiri, Salam Amir

مشرف أطروحة جامعية

al-Abbadi, Muhammad Ali Husayn
al-Hasanat, Ahmad Bashir

أعضاء اللجنة

al-Kasasibah, Muhammad Sharari Zamil
al-Hammuri, Awni Mansur

الجامعة

جامعة مؤتة

الكلية

كلية تكنولوجيا المعلومات

القسم الأكاديمي

قسم الحاسوب

دولة الجامعة

الأردن

الدرجة العلمية

ماجستير

تاريخ الدرجة العلمية

2017

الملخص الإنجليزي

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

التخصصات الرئيسية

تكنولوجيا المعلومات وعلم الحاسوب

عدد الصفحات

55

قائمة المحتويات

• APA
• MLA
• AMA

لغة النص

الإنجليزية

نوع البيانات

رسائل جامعية

رقم السجل

BIM-780528