تاريخ التسجيل: 2005-07-21
مشاركات: 13
|
د.محمد خطيب
حل المشاكل اعتمادا ً على النمل:
ACO AntColonyOptimization طريقة بحث حدسية عامة تستخدم النمل الاصطناعي وذلك لإيجاد حلول جديدة لمسائل الأمثلة التركيبية المعقدة (combinatorial optimization). إن سلوك النمل الصناعي يعتمد على آثار النمل الحقيقي مع قدرات إضافية لجعلها أكثر فعالية مثل ذاكرة لحفظ الأحداث الماضية. كل فرد يبني حلولا ً للمشكلة المطروحة، ويستخدم معلومات مجمعة عن ميزات المشكلة وأدائه الخاص لتغيير نظرة النمل إلى المشكلة. إن خوارزمية ACO تشير إلى أي حالة من مرحلة ما بعد التجريبية(meta-huristic). Colorni,Dorigo,Maniezzo استخدموا هذه الطريقة في مشكلة البائع الكلاسيكية ، في هذه المشكلة يجب على الشخص أن يتنقل بين مجموعة من المدن بحيث يزور كل مدينة مرة واحدة فقط. مستعمرة النمل التي أنشأت تتنقل عشوائيا ً في حلقات تضم كل المدن. خلال الخطوة الأولى يفضل الانتقال إلى أقرب المدن. بعد إتمام الدورة الأولى يوضع حمض النمل على كامل الطريق، إن كمية الحمض الذي يوضع على الطريق تتناسب عكسا ً مع طول الطريق، كلما كان الطريق أقصر كلما كانت كمية الحمض أكثر.
تبدأ المستعمرة رحلتها من جديد لكن هذه المرة تفضل المستعمرة الطرق التي تكون تركيز الحمض فيها عالية بالإضافة إلى أنها تفضل الطرق الأقصر. يتبخر حمض النمل بمعدل ثابت والطرق التي لا تمر فيها المستعمرة تصبح غير مفضلة. يسافر النمل الذكي على طول الطرق من المستودع إلى المدن وبالعكس وبتأثير الـ Pheromons ستحدد أي طريق ستختار , إن مستويات الـ Pheromons على الطرق تحدث اعتماداً على نوعية الحلول التي وجدها النمل . تم استخدام طريق أمثلة مستعمرة النمل من قبل ( بلانت ) لحل مسألة تخطيط الفضاء . تهتم المسألة تحديداً بمحاولة وضع نشاطات بشكل أمثلي ضمن فضاء محدد , فمثلاً يمكن لعملية امثله تريد أن توضّع مهمات إدارية وموظفين ضمن مجموعة من المكاتب في مبنى . وفي هذه الحالة , يمكن أن تكون عملية تصغير كمية الحركة ( حركة الناس والورق ) أكثر فعالية ضمن البناء . تم تطوير تجربة مملكة النمل للتطبيق على مسألة التأخير الكلي لآلة وحيدة في هذه المسألة يجب على الآلة جدولة سلسلة الأعمال الواجب عليها تنفيذها والهدف هو تقليل زمن التأخير الكلي للأعمال , حيث أن التأخير يعرف على أنه الفرق بين وقت نهاية تنفيذ العمل والوقت الأصلي للعمل .
تختار النملات بشكل مستقل أعمال متتالية إلى أن تنتهي عملية جدولة الأعمال , يتم اختيار الأعمال اعتماداً على مدى جودة العمل الظاهرية ( اعتماداً على وقته الأصلي ) ومدى حسن اختيار العمل ( اعتماداً على مستويات الفورمون المتروكة في الخلف ) . يتم تقييم كل سلسلة من الأعمال ويتم تحديث خطوط الفورمون اعتمادا على أفضل حل . نفذ ( سونغ و شو ) خوارزمية بحث اعتماداً على عملية بحث النمل عن الطعام لحل مسألة استهلاك الطاقة. في هذه المسألة يجب علينا تصغير كلفة الطاقة في حين بلوغ الطاقة الكلية المطلوبة وتوليد كهرباء ضمن حدود الإنتاج لكل مولد . تقوم النملات الذكيات بالتحرك من محطة إلى محطة موزعين الطاقة الكلية المطلوبة إلى حين تشغيل كل المحطات . يعتمد اختيار المولد التالي في طريق النملة على مستويات الآثار التي تركتها النملات الأخريات والكلفة المدركة لاستخدام المولد .
بعض التطبيقات الأخرى لطريقة أمثلة مستعمرة النمل ( ACO ) هي جدولة سائقي الباصات , تلوين البيان وتجزئته , توزيع الحمل في شبكات الإتصالات , عمليات التوجيه في الشبكات التي تعتمد على الطرود . قامت بعض الأبحاث المذكورة سابقاً باختيار أداء التجريبات المعتمدة على النمل ومقارنة النتائج مع الخوارزمية الجينية , وغيرها من طرائق البحث . في العديد من حالات اختبار مسألة البائع المتجول يظهر أن طريقة النمل أفضل من الخوارزمية الجينية وطريقة ( Simulated annealing ) ولكنها ليست أفضل من طريقة ( tabu search ) . إن نتائج توجيه العربات كانت أفضل من أجل تجريبية النمل مقارنة مع ( Simulated annealing ) و( Natural network ) لمجموعة من / 14 / مسألة , ولكنها لم تكن أفضل من / 3 / من خوارزميات tabu search ) ) . كان أداء طريقة النمل أفضل في مسألة التأخير الكلي لآلة وحيدة في / 125/ مسألة فرعية مقارنة لطريقتين مختلفتين لـ ( Simulated annealing ) . تم الحصول على كلفة أقل بقليل عن استخدام طريقة النمل مقارنة مع الخوارزمية الجينية على عينة اختبار صغيرة لمسألة استهلاك الطاقة . وبشكل عام, يبدو أن تقنيات النمل تعطينا أداءً أفضل من تقنيات العلم الطبيعي المشروحة سابقاً ولكنها ليست أفضل من طريقة
tabu search ) ) .
سلوكيات أخرى للحشرات :
هناك العديد من التصرفات التي تسلكها الحشرات والتي تقع ضمن إطار ذكاء السرب والتي يمكن تطبيقها على حل المسائل . تقوم مجموعات خاصة من النمل بترتيب صغارها اعتماداً على عدة مراحل من التطور. على الرغم من ذلك فإن عدة أنواع من الصغار يمكن أن تبدأ بالانتشار بشكل عشوائي في مناطق محددة من العش , فإن البيوض واليرقات الأصغر ستكون في المركز في النهاية واليرقات الأكبر على الأطراف . ويعود تفسير ذلك إلى أن النملات ستميل إلى ترتيب الأشياء اعتماداً على التطابق حيث أن الأشياء التي تبدو غير مناسبة في مجموعة ستلتقط وتحرك وسيتم وضعها قريباً من الأشياء الشبيهة بها . لقد طبق الباحثون هذا السلوك من قبل على مسائل تهتم بالفرز والتجميع لمعلومات قاعدة المعطيات, ومثال على ذلك : بنك يحاول تحديد الزبائن الذين يمكن أن يتلقوا قبولاً على قروض اعتماداً على عدة معلومات . ومسائل أخرى يمكن أن تستفيد من هذا المنهج مثل , تحليل حركة البورصة , تصميم خطوط الإنتاج , تحليل نماذج المزاودات الالكترونية , وتوزيع الإعلانات بشكل ديناميكي في موقع ما اعتماداً على سلوك الزوار لهذا الموقع .
في نمط من السلوك الجماعي ستقوم النملات بالعمل سوياً للحصول على فريسة أو قطعة طعام كبيرة (لا يمكن لشخص واحد حملها ) تدعى العملية بعملية النقل التعاوني . عند دفع القطعة ستقوم كل نملة بتغير موضعها ومحاذاتها بشكل دوري إلى أن تتحرك القطعة باتجاه العش . تم تنفيذ هذا السلوك في مجال الروبوتيك , حيث تقوم مجموعة من الأجهزة التي تعمل على انفصال بتنفيذ مهمة , مثل ان تقوم بتحريك صندوق إلى مركز ساحة ما . هناك أنواع أخرى من المسائل التي يمكن حلها عن طريق استخدام نمذجة هذا السلوك مثل : تصميم خطوط التجميع , الموازنة , وخاصة في البيئات الصناعية المرنة . سيجتمع العمال في فريق من أجل المهمات الغير عادية لتحقيق الفعالية الكلية القصوى للخط ويمكن حل العديد من المسائل بطريقة مشابهة . تقوم النملات بتنفيذ مهمات اعتماداً على العمر وتقوم النملات الأكبر بالبحث عن الطعام بينما تبقى النملات الشابّة في الخلية لترعى الصغار , ويمكن أن يتغير ترتيب هذه المهمات عند تحسس الحاجة لذلك . فمثلاً عند ندرة الطعام ستقوم النملات الشابّة أيضاً بجمع الطعام . تم تطبيق هذا السلوك على العمليات المرنة في الصناعة , مثلاً : تقوم قطعة غالية في جهاز تجميع بعمل محدد ولكنه يمكن تغير هذا العمل إذا كان ذلك يبدو أكثر فائدة . وبشكل مشابه تنفذ النملات مهمات استنادا إلى توصيفات أعمار محددة , وهي بشكل أساسي الباحثات عن الطعام , الحراس , والمسؤلات عن صيانة العش .... ألخ .
يقوم الحراس باستكشاف المنطقة المحيطة بالعش والبحث عن أي إشارة خطر , وتحديد المسار العام التي ستأخذه الباحثات عن الطعام . تقوم عاملات الصيانة بالحفاظ على مدخل العش نظيفاً وإزالة الوحل من داخل العش , وتقوم بعض العاملات الأخريات بفرز وصيانة الكومة , وبالطبع تقوم النملات في بعض الأحيان بتبديل أدوارها عند حدوث حالة طارئة , ولكن بشك عام فإن تصنيفات العاملات ثابتة . ربما أنه من الممكن تطوير تجريبيات توظف مفهوم أكثر من نمط من النمل ونشاطاتها , التي تعمل بشكل متزامن لحل مسألة ما بفاعلية أكبر . إن تعليم الطرق بالأثر ليس محصوراً بالنمل فقط , فبدلاً من القيام برقصة من أجل التواصل مع الآخرين وإخبارهم عن أماكن الطعام , تقوم بعض أنواع النمل بترك علامات عطرية بين العش ومصدر الطعام . إن عملية ترك الأثر هذه هي عملية غير منتظمة , وسيتبخر هذا الأثر خلال دقائق , وفي بعض الأحيان فإن هذا غير كاف لقيادة النملات الأخريات إلى الطعام , ولذلك سيقوم مستكشف بقيادة النملات إلى مصدر الطعام . يمكن أن تقوم النملات أيضاً بتعليم مصادر الطعام غير المنتجة من أجل الإشارة إلى النملات الأخريات أن لا تضيع وقتاً هناك في محاولة استخراج الغذاء . تقوم أنواع محددة من الفراش بالبحث عن الطعام ولكنها لا تحضر الطعام إلى العش , تترك الفراشات عادة نوعين من الخطوط خلفها , تغذية مسبقة وتغذية لاحقة . تعلم خطوط التغذية المسبقة ( الاستكشافية ) الطريق الذي ستسلكه الفراشة ويمكن أن يدل الفراشات الأخريات إلى الطعام ويمكن أن لا يدل .
إن خطوط التغذية اللاحقة جعلت من أجل أن تكون خطوط لقيادة الآخرين إلى مصدر الطعام . مقابل ذلك فإن بعض أنواع الفراش يقوم بترك خطوط تغذية لاحقة في مواقع استراحة جديدة مبعدين صفة أن تكون هذه الخطوط خطوط مؤدية إلى مصادر الطعام , ولكنه قد يكون هناك شيء ما ذو قيمة في هذا التصرف . يمكن استخدام هذا المنهج لجعل عمليات البحث غير مقصورة على الحل الامثل المحلي وجعل عملية البحث أكثر فاعلية .
مازال العلماء يبحثون في مجال سلوك الحشرات الاجتماعي , وقد بدأ الباحثون تواً في تطبيق ما يسمى بذكاء الأسراب في التصميم التجريبي . تظهر الدراسات التي تمت إلى هذا الوقت وخاصة في مجال تقنيات مستعمرات النمل , تظهر احتمال أن يسهم هذا المنهج في أيجاد حلول جيدة للعديد من أنماط المسائل العملية والتي من الصعب جداً حلها بغير هذه الطريقة. ومازال العديد من سلوك الحشرات الجماعية الأخرى تحت البحث . لقد بدأ العالم تواً يرى الطاقة الهائلة التي يمكن الحصول عليها من السلوكيات البسيطة لهذه الحشرات.
|
أرسل من قبل 
