شرح مبسط لخوارزمية النمل

[ibr_exn 89]

تعتبر خوارزمية مستعمرات النمل The ant colony optimization algorithm (ACO) من خوارزميات البحث التي تعتمد على التجربة والخطأ والتي تعطي حل مقبول (قد يكون افضل حل وقد لا يكون) لذلك يتم استخدامها في حل المسائل التي تأخذ وقت طويل باستخدام الحاسوب مثال ذلك مسائل NP-Complete (او المسائل التي تحتاج الى تجرية كل الاحتمالات حتى تصل الى الحل المطلوب ان وجد).

فكرة الخوارزمية :

اتت فكرة الخوارزمية من محاكاة عملية البحث عن الطعام عند النمل وهي كالتالي :

1. تقوم مجموعة من النمل بالانطلاق من الخلية في عدة اتجاهات عشوائيه (هذه العملية تتم في المرة الاولى فقط في المرات اللاحقة يتم اختبار كل مسار واختيار مسار معين كما سنرى لاحقا)

2. اثناء مرورها تقوم النملة بافراز مادة تسمى فيرمون بنسبة معينة (فائدة هذه المادة معرفة الطريق الذي مرت فيه).

3. عندما تجد مصدر للطعام فهي تأخذ كمية منه وتعود الى الخلية عن طريق اختيار مسار معين (المسار الذي يحوي اكبر كمية فيرمون).ايضا عند عودتها ستقوم بافراز نفس الكمية من الفيرمون.

4.عندما تنطلق النملة من الخلية مجددا ستقوم باختبار كمية الفيرمون في كل مسار وتختار المسار الذي يحوي اكبر كمية من الفيرمون.

5. يتم تحديث كمية الفيرمون كل فترة زمنية معينه (تركيز الفيرمون يتلاشى بمرور الوقت ، عمر النمل ملايين السنوات وان لم تتلاشى كمية الفيرمون لاغرق الارض)

لاحظ ان اقصر مسار سيحوي دائما اكبر كمية من الفيرمون وبالتالي كل النمل سيمر فيه.

ميزة هذه الخوارزمية انها ديناميكية بمعنى اذا حصل عائق في اقصر مسار ستقوم النمل باختيار مسار جديد بنفس الاسلوب.

ما سبق يتعبر فكرة عامة جدا حيث ان كل مسألة لها طبيعتها ويتم التعديل في الخوارزمية لتناسب المسألة التي سيتم حلها لذلك يجب الرجوع الى كتب و ابحاث متخصصة للتعمق في فهم هذه الخوارزميه. لاحظ ايضا انه الى الان مازالت الابحاث الجديدة تستخدم هذه الخوارزمية لاعطاء نتائج ممتازة وعادة تعطي نتائج افضل من الخوارزميات الجينيه.

مزيد من التفاصيل يمكن الحصول عليها من هنا:

http://en.wikipedia.org/wiki/Ant_colony_optimization

مثال عملي مشروح :

http://www.codeproject.com/KB/recipes/GeneticandAntAlgorithms.aspx

حبذا لو يقوم جماعة السي شارب بترجمة المقال بشكل مبسط الى اللغة العربيه.

تم تعديل 1 Feb 2010 بواسطه ibr_exn

[nehad alkhan 0]

مشكورين عالموضوع الراقي صار هواي دابحث عن هالموضوع 

لاني راح استخدمها في مجال البايلوجي