A modified heuristic procedure for NP-complete problems supported by genetic algorithm

المؤلف

al-Saati, Najla A.

المصدر

al- Rafidain Journal of Computer Sciences and Mathematics

العدد

المجلد 1، العدد 1 (30 يونيو/حزيران 2004)، ص ص. 117-135، 19ص.

الناشر

جامعة الموصل كلية علوم الحاسبات و الرياضيات

تاريخ النشر

2004-06-30

دولة النشر

العراق

عدد الصفحات

19

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

الرياضيات

الموضوعات

الملخص AR

يرتكز هذا العمل على عملية تحوير قانون حدسي ذكي يستخدم في حل المسائل الـ (NP-Complete) و قد تمت دراسة أحد القوانين الحدسية لمسائل التعيين من نوع (Flow Shop Problem) و تحويره ليستخدم في حل إحدى مسائل الذكاء الاصطناعي الشائعة و التقليدية و هي مسألة البائع المتجول (Traviling Salesman Problem).

و من أجل إنجاح هذا التحوير يجب أن تتم دراسة التشكيل الرياضي للمسألة بعناية و دراسة إمكانية إعادة تشكيل الصيغة الرياضية بما يتلاءم مع طبيعة القانون الحدسي.

و قد يتطلب ذلك تقديم تحويرات بسيطة في القانون الحدسي نفسه بسبب بعض الاختلافات الملحوظة كالتناظر (Symmetry) الموجود في بيئة مسألة البائع المتجول و غيرها من الاختلافات.

و لتحسين الحلول الناتجة من استخدام الحدس تضاف البرمجة الوراثية في هذا العمل، حيث أن استخدام التبادل و الطفرات الوراثية سيتيح للحل الحدسي الجيد خطأ أوفر للتحسن و الاقتراب من الحلول المثلى.

الملخص EN

This work is based on the process of modifying an intelligent heuristic rule used in solving NP-Complete problems, where a study and a modification of a Flow Shop assignment heuristic has been carried out to solve a well-known classic Artificial Intelligent problem, which is the traveling Salesman problem.

For this modification to be carried out successfully, the problem’s mathematical formulation had to be studied carefully and the possibility of reformulating the problem to be more suitable for the heuristic procedure.

This may require some changes in the heuristic procedure itself, these adjustments were due to the noticeable differences like the symmetric property present in the traveling salesman problem environment and some other differences.

Genetic programming is added to improve the results obtained by the used heuristic, where the use of crossover and mutation procedures will provide better chances for the near optimal solution to be improved towards optimal solutions.

The test problem is made on cities that lie on the regular square grid, which simplify the calculations of distance traveled between any two cities.

Programs were written using C programming language, and timers were used to measure the elapsed time of calculations in order to assess the efficiency of the.

نمط استشهاد جمعية علماء النفس الأمريكية (APA)

al-Saati, Najla A.. 2004. A modified heuristic procedure for NP-complete problems supported by genetic algorithm. al- Rafidain Journal of Computer Sciences and Mathematics،Vol. 1, no. 1, pp.117-135.
https://search.emarefa.net/detail/BIM-361219

نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)

al-Saati, Najla A.. A modified heuristic procedure for NP-complete problems supported by genetic algorithm. al- Rafidain Journal of Computer Sciences and Mathematics Vol. 1, no. 2 (2004), pp.117-135.
https://search.emarefa.net/detail/BIM-361219

نمط استشهاد الجمعية الطبية الأمريكية (AMA)

al-Saati, Najla A.. A modified heuristic procedure for NP-complete problems supported by genetic algorithm. al- Rafidain Journal of Computer Sciences and Mathematics. 2004. Vol. 1, no. 1, pp.117-135.
https://search.emarefa.net/detail/BIM-361219

نوع البيانات

مقالات

لغة النص

الإنجليزية

الملاحظات

Includes bibliographical references : p. 134-135

رقم السجل

BIM-361219