حل مشكلة رحلة رجل المبيعات باستخدام طريقة تمثيل و عمليات جديدة في الخوارزميات الجينية
Other Title(s)
Solving the traveling salesman problem by using new implementation and operators in genetic algorithms
Dissertant
Thesis advisor
عبابنة، إسماعيل محمد
العتوم، جلال يوسف
Comitee Members
العكور، محمد علي أحمد
القصاب، موفق محمد توفيق
سلامة، وليد خالد
University
Al albayt University
Faculty
Prince Hussein Bin Abdullah Faculty for Information Technology
Department
Department of Computer Science
University Country
Jordan
Degree
Master
Degree Date
2003
Arabic Abstract
الخوارزميات الجينية هي خوارزميات بحث تعتمد على نظرية الوراثة التي أتى بها دارون و تعتب ر حلا عمليا لمسائل الأمثلية مثل رحلة رجل المبيعات.
اقترحت في دراسات سابقة طرق لتمثيل الكروموزوم و عمليات جينية لحل مشكلة رحلة رجل المبيعات و قد اتحذت هذه الدراسات واحدا من اتجاهين، اعتمد فيي الأول تمثيل الكروموزوم بسلسلة من الأرقام الصحيحة و يؤدي هذا إلى تعقيد العمليات الجينية و زيادة وقت التنفيذ.
و استعين بالأمثلية المحلية للأبناء الذي يزيد من وقت تنفيذ الخوارزميات الجينية الذي يزيد من وقت تنفيذ الخوارزميات الجينية لتحسين الحلول الناتجة.
أما الاتجاه الثاني فقد اعتمد على تمثيل الكروموزوم بمصفوفة ثنائية و يؤدي هذا إلى تقليل وقت تنفيذ الغمليات الجينية و لكن لم يتم استخدام الطرق التقريبية لإنتاج حلول أفضل و كذلك يحتاج هذا التمثيل إلى حجم كبير من الذاكرة.
يقترح في هذه الدراسة تمثيل الكروموزوم بمصفوفة ثنائية عليا لتقليل حجم الذاكرة اللازمة كما تقترح عملية تزاوج جديدة تعتمد على طريقة تقريبية لإنتاج حلول أفضل.
تبين النتائج لعدد من مسائل رحلة رجل المبيعات القياسية مختلفة الحجم (29-1577 مدينة) و التي تم تنفيذ الخوارزمية المقترحة عليها أن الخوارزمية المقترحة توصلت إلى الحل الأمثل لبعض المسائل و إلى خل قريب من الحل الأمثل للبعض الآخر.
كما تبين مقارنة الخزوارزمية المقترحة بخوارزمية سنوى أن طريقة التمثيل المقترحة للكروموزوم تقلل من حجم الذاكرة اللازم للتمثيل الثنائي، و إن استحدام الطرق التقريبية في عملية التزاوج حسن من جودة الحلول الناتجة من حيث قربها من الحل الأمثل و الزمن اللازم للحل.
Main Subjects
Information Technology and Computer Science
Topics
No. of Pages
98
Table of Contents
فهرس المحتويات / الموضوعات.
الملخص / المستخلص.
الفصل الأول : رحلة رجل المبيعات.
الفصل الثاني : الخوارزميات الجينية.
الفصل الثالث : الدراسات السابقة.
الفصل الرابع : وصف الخوارزمية المقترحة.
الفصل الخامس : النتائج العملية للدراسة المقترحة.
الفصل السادس : مقارنة الدراسة المقترحة بدراسة سنوي.
الفصل السابع : الخلاصة.
قائمة المراجع.
American Psychological Association (APA)
الرشيدي، نائف طاهر علي. (2003). حل مشكلة رحلة رجل المبيعات باستخدام طريقة تمثيل و عمليات جديدة في الخوارزميات الجينية. (أطروحة ماجستير). جامعة آل البيت, الأردن
https://search.emarefa.net/detail/BIM-319428
Modern Language Association (MLA)
الرشيدي، نائف طاهر علي. حل مشكلة رحلة رجل المبيعات باستخدام طريقة تمثيل و عمليات جديدة في الخوارزميات الجينية. (أطروحة ماجستير). جامعة آل البيت. (2003).
https://search.emarefa.net/detail/BIM-319428
American Medical Association (AMA)
الرشيدي، نائف طاهر علي. (2003). حل مشكلة رحلة رجل المبيعات باستخدام طريقة تمثيل و عمليات جديدة في الخوارزميات الجينية. (أطروحة ماجستير). جامعة آل البيت, الأردن
https://search.emarefa.net/detail/BIM-319428
Language
Arabic
Data Type
Arab Theses
Record ID
BIM-319428