Fulltext

Using ant colony algorithm to find the optimal assignment

استخدام خوارزمية مستعمرة النمل لإيجاد التخصيص الأمثل

Asmaa Salah AlDien Suliman أسماء صلاح الدين سليمان

AL-Anbar University journal of Economic and Administration Sciences مجلة جامعة الانبار للعلوم الاقتصادية والادارية
ISSN: 19988141 Year: 2019 Volume: 11 Issue: 25 Pages: 497-513
Publisher: University of Anbar جامعة الانبار

Abstract

The study examined the use of an ant colony algorithm to find the optimal assignment for a (3 × 3) application and compare its results with the results of the Hungarian method. The application requires six possible assignments because the number of possible assignments is calculated according to the following formula: (3! = 3 × 2 × 1 = 6). Since the objective function in the assignment problem is a function of minimization for the fact that the target function represents the cost function whether it represents (time or effort or money). Therefore, the purpose of the research was to use the ant colony algorithm and compare its results in the traditional method (the Hungarian method) in terms of execution time, number of repetitions and accuracy of results. It has been concluded that the lowest allocation among the six assignments is the allocation in which the value of the target function is equal to 27 and using two replicates in the ants colony, as confirmed by the results of the Hungarian method. The application used in this research includes the distribution of three tasks by the father for the boys in exchange for a sum of money so that each one of them one task and each task performed by only one of the children. It is possible to make use of the optimal allocation of assignment if the right person is assigned to perform a specific task in various areas of economic and social life. Thus, this person does not perform any other task and does not perform this task other than the person in charge and thus ensure that all (individuals) to perform certain tasks as well as the performance of all tasks by all individuals using the allocation with the least time and effort as well as the lowest possible cost.

تناول البحث استخدام خوارزمية مستعمرة النمل لإيجاد التخصيص الأمثل لتطبيق بسعة (3×3) ومقارنة نتائجها مع نتائج الطريقة الهنكارية. إذ أن التطبيق يتطلب ايجاد ست تخصيصات ممكنة وذلك لان عدد التخصيصات الممكنة تحسب على وفق الصيغة الاتية: ( )، وبما ان دالة الهدف في مشكلة التخصيص هي دالة تقليل كون دالة الهدف تمثل دالة الكلفة سواء اكانت الكلفة تمثل (وقت او جهد او مال) لذلك كان هدف البحث استخدام خوارزمية مستعمرة النمل ومقارنة نتائجها بالطريقة التقليدية (الطريقة الهنكارية) من ناحية وقت التنفيذ وعدد التكرارات ودقة النتائج. وقد تم التوصل الى ان اقل تخصيص من بين التخصيصات الستة هو ذلك التخصيص الذي تكون فيه قيمة دالة الهدف مساوية الى 27 وباستخدام تكرارين في مستعمرة النمل، وهذا ما اكدته نتائج الطريقة الهنكارية. ان التطبيق المستخدم في هذا البحث يتضمن توزيع ثلاث مهام من قبل الاب ليقوم بها الاولاد مقابل الحصول على مبلغ من المال بحيث يقوم كل واحد منهم بمهمة واحدة وكل مهمة يقوم بها واحد فقط من الاولاد. اذ يمكن الاستفادة من تحديد التخصيص الامثل في حال تكليف الشخص المناسب ليقوم بمهمة معينة في مختلف مجالات الحياة الاقتصادية والاجتماعية. بحيث لا يقوم هذا الشخص بمهمة اخرى غيرها ولايقوم بهذه المهمة غير الشخص المكلف بها وبذلك نضمن قيام جميع الاشخاص(الافراد) بمهام معينة وكذلك القيام باداء جميع المهام من قبل كل الافراد باستخدام التخصيص باقل وقت وباقل جهد وكذلك باقل كلفة ممكنة.

Keywords

Ant colony Algorithm --- assignment --- Hungarian method --- خوارزمية مستعمرة النمل، التخصيص، الطريقة الهنكارية