الوسم: خوارزميات

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

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

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

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

سلوك نحل العسل

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

كفاءة البحث مفتاح البقاء

كما هو واضح، فآلية التواصل بالفيرومونات جد مهمة في حياة النحلة وحاسمة في استمرارية المستعمرة. فباستخدام مركب كميائي معين من الفيرومونات يمكن أن تحفز النحلة مجموعتها لرد فعل على هجوم ما. إضافةً، فعند إيجاد النحلة لمصدر رحيق معين، وتعود حاملة إياه، تصدر مجموعة من الفيرومونات كإشارة. ومن ثم تقوم النحلة برقصتها لتحديد المكان والجودة للنحلات المجاورة.

عند تعدد مصادر الرحيق، أثبتت الدراسات أن السلوك المنظم للمستعمرة قادر على توزيع النحلات الجامعة على هذه المصادر بطريقة فعالة. وذلك من أجل جمع أقصى قدر من الرحيق. فكي تستطيع المستعمرة النجاة خلال فصل الشتاء، يتوجب جمع ما لا يقل عن 15 كيلوغرام من العسل أو ما قد يصل إلي 50 كيلوغرام، حسب النوع والمنطقة.

كفاءة البحث كمصدر إلهام

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

خوارزميات النحل

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

لكن انطلاقا من الأدبيات العلمية والأوراق البحثية نجد أن خوارزمية نحل العسل Honeybee Algorithm قد تم تطويرها سنة 2004 على يد كريغ توفي Craig A. Tovey من معهد جورجيا للتكنولوجيا، و سونيل نكراني Sunil Nkarani من جامعة أوكسفورد. وفي أواخر 2004 وبداية 2005 طور عالم الرياضيات والحاسوب شين شي يانغ Xin She Yang من جامعة كامبريدج خوارزمية النحلة الافتراضية Virtual Bee Algorithm، لحل مشاكل التحسين العددية. هذه الخوارزمية قادرة على مواجهة المشاكل المستمرة و المتقطعة.

وفي وقت لاحق من سنة 2005 طور حداد Haddad و أفشار Afshar وزملاءهما خوارزمية تحسين تزاوج نحل العسل Honeybee mating Optimization. والتي استخدمت في تصميم الخزانات والتعنقد clustering. وفي نفس الفترة الزمنية طور كارابوجا D. Karaboga خوارزمية النحل الاصطناعية Artificial Bee Algorithm للتحسين العددي.

خوارزمية نحل العسل

يتم توجيه النحل العامل في خوارزمية نحل العسل Honeybee Algorithm نحو عدد من مصادر الطعام. من أجل الحصول على أكبر كمية من الرحيق. عملية التوجيه هذه تقوم على عدد من العوامل، مثل تركيز الرحيق في المنطقة المعنية وكذلك قربها من المستعمرة. وسنجد أن عملية التوجيه هذه مشابهة لعملية توزيع خوادم استضافة الويب allocation of web-hosting servers على الإنترنت. وبالتالي، كان هذا المشكل من أوائل المسائل التي تم حلها بواسطة خوارزميات النحل، وبالضبط خوارزمية نحل العسل.

باعتبار Wi(j) قوة تذبذب رقصة النحلة i خلال خطوة التنفيد j، نجد أنه من الممكن تحديد احتمالية اتباع نحلة معينة للمصدر المشار إليه بعد مشاهدة الرقصة بواسطة عدد من الصيغ وذلك اعتمادًا على المتحور المستعمل، فنجد الصيغة المطبقة في خوارزمية نحل العسل كالتالي:

يمثل العدد الصحيح الطبيعي nf عدد النحلات العاملة الباحثة، و t دورة البحث الحالية. وبالتالي عدد النحلات المراقبة للرقصات هو N-nf أي مجموع النحلات ناقص عدد النحلات غير المتفرغة، بسبب بحثها.

يمكن كذلك تحديد معادلة لاحتمالية الاستكشاف ممثلة بصيغة إحصائية أخرى، فنجد الصيغة الغاوسية الجديدة:

عند عدم رقص أي نحلة نجد:

ما يعني أن النحلات ستبحث عشوائيًا.

في متحورات أخرى، عند تطبيقها لحل المشاكل المتقطعة مثل مشاكل الجدولة، تقوم النحلة الباحثة بأداء رقصة معينة في مدة زمنية محددة τ = γ fp. بحيث تعبر fp عن ربحية أو غنى منطقة الطعام، أي حقل الزهور وتركيز الرحيق بها. بينما γ هي معامل تحجيم للتحكم في الفترة الزمنية للرقصة. بالطبع الربحية مرتبطة بالدالة الهدف.

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

على غرار خوارزميات مستعمرة النمل، فخوارزمية نحل العسل HBA، جد فعالة في التعامل مع مشاكل التحسين المتقطعة مثل مشاكل التوجيه والجدولة. لكن في مواجهة التحسين المستمر، فهي غير مباشرة، وبالتالي في حاجة إلى بعض التعديلات.

خوارزمية النحلة الافتراضية

طورت خوارزمية النحلة الافتراضية Virtual Bee Algorithm من طرف Xin She Yang سنة 2005 من أجل مواجهة المشاكل المستمرة والمتقطعة. بحيث تتشابه في عدد من خصائصها خوارزمية استمثال عناصر السرب Particle Swarm Optimization أكثر من خوارزميات النحل الأخرى، ويقصد ب”الاستمثال” التحسين. في هذه الخوارزمية تمثل الدالة الهدف قيم الرحيق الافتراضية، بينما الحلول المحتملة هي مواقع غنية، بكميات متفاوتة، بالرحيق. كما أن قوة الرقصة تعتمد فقط على تركيز الرحيق، والذي يمكن اعتباره هنا معاملًا للملائمة fitness للحلول المحتملة.

في مواجهة المشاكل المتقطعة يتم ربط الدالة الهدف، مثل دالة تحديد الطريق الأقصر، مباشرة بربحية عملية استكشاف الرحيق. والتي بدورها ترتبط عملية استكشاف الرحيق، بقوة رقصة النحلة.

انطلاقًا من هذا، نلاحظ وجود تشابه كبير بين هذه الخوارزمية وسابقتها، خوارزمية نحل العسل. لكن رغم وجود هكذا تشابه، إلا أنه عند تدقيق النظر في آلية بحث النحلات، نجد الاختلافات. إذ أنها لا تحتاج للعودة للخلية من أجل إخبار نظيراتها بما اكتشفته، بحيث يمكنها بث محتوى الرقصة عن بعد لجميع النحلات. وبالتالي يصبح الحل الأمثل الحالي معلومًا عند كل نحلة باحثة ومؤثرًا على عملية اتخاد القرار الفردية. فنجد من هذا إختلافًا بنيويًا، لا يجعل منها تختلف عن خوارزمية نحل العسل فحسب، بل وتختلف كذلك عن كل خوارزميات النحل الأخرى.

خوارزمية مستعمرة النحل الاصطناعية

في هذه الخوارزمية، خوارزمية مستعمرة النحل الاصطناعية Artificial Bee Colony Algorithm، يتم تقسيم نحلات المستعمرة لثلاث أنواع. النحلات العاملة، والنحلات الكشافة، والنحلات المراقبة. فنجد لكل مصدر طعام نحلة عاملة واحدة تبحث محليًا عن الحل المحلي الأمثل. فيما يحاكي عملية استخراج الرحيق والانتقال من زهرة إلي أخرى. كما أن التخلي عن مصدر طعام معين، عند نضوبه أو انخفاض ربحيته، يعني مباشرة تحول نحلته العاملة إلي نحلة كشافة. فتبحث النحلة الكشافة بشكل عشوائي عن مصادر طعام أخرى.

تتشارك النحلات العاملة والنحلات الكشافة معلوماتها مع النحلات المراقبة، والتي تتمركز في الخلية. هذه الأخيرة، فيما بعد، تقرر منطقة بحثها متخذتةً بعين الاعتبار المعلومات التي وصلت إليها. لتصبح هي الأخرى نحلات عاملة وتنضم للفريق.

تطبيقات خوارزميات النحل

لكونها خوارزميات ناجحة، يمكن تطبيقها لحل مختلف أنواع المشاكل التحسينية. فنجد خوارزميات النحل حاضرة في كل مجالات التحسين الحوسبي فمن تطبيقاتها نجد:

• تدريب الخلايا العصبية الاصطناعية.
• تدريب نماذج الذكاء الاصطناعي.
• التعلم العميق.
• التصميم الصناعي.
• مخطط الرقابة Control Chart في الهندسة الصناعية.

وتبقى التطبيقات الحالية كثيرة، والأخرى الممكنة لا حصر لها فالبحث لا زال جاريًا، والأفق مفتوح.

مصادر

1. Nature Inspired Optimization Algorithms by Xin She Yang
2. أطروحة دكتوراه للدكتور أبوبكر كوش.
3. Wikipedia

الخفافيش حيوانات مذهلة. فإضافة لكونها الثدييات الوحيدة المجنحة، لديها قدرة متقدمة أيضًا على تحديد واستكشاف محيطها بالصدى. ويقدر أن هنالك حوالي 1000 نوع مختلف من الخفافيش، وتمثل ما يصل إلى 20٪ من جميع أنواع الثدييات. ووزن الخفاش يتراوح من حوالي 1.5 غرام – إلى غرامين ما يمثل الخفافيش الصغيرة – إلى ما يتجاوز الكيلوغرام، أي الخفافيش العملاقة ذات الأجنحة التي يناهز طولها، عند التمدد، المترين.

تستخدم معظم الخفافيش قدرتها على الاستشاعر و التوجه بالصدى بنسب متفاوتة في حياتها اليومية. لكن بين كل أنواعها، الخفافيش الصغيرة Microchiroptera أو Microbats هي الأكثر اعتمادًا واستخدامًا لهذه القدرة. في حين أن الخفافيش الكبيرة نسبيًا والخفافيش العملاقة Megachiroptera لا تستعملها كثيرًا، أو قد تستغني عنها تمامًا.

معظم الخفافيش الصغيرة آكلة حشرات. وتستعمل في نشاطاتها اليومية نوعًا من أنواع السونار، أو ما يسمى بالإنجليزية Echolocation وتعني تحديد الموقع بالصدى. فتستخدم قدرتها هذه في البحث عن فريستها، وتحديد موقع جحورها. وكذلك استكشاف محيطها لتجنب المعوقات والعقبات.

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

تظهر الدراسات أن الخفافيش الصغيرة تستخدم التأخر الزمني بين إصدار الصوت وإلتقاط الصدى. كما تستخدم الفرق الزمني بين الالتقاط من أذن إلي أخرى، واختلافات مستوى الصدى لبناء بنية ثلاثية الأبعاد لمحيطها. ما يمكنهم من التعرف على المسافة، واتجاه الهدف، ونوع الفريسة، وحتى سرعة حركة الفريسة – والتي غالبا ما تكون حشرات صغيرة. وما يدعو للعجب هو أن الدراسات والملاحظات تشير إلى كون الخفافيش الصغيرة قادرة على التمييز بين الفرائس التي تستهدفها انطلاقًا من تأثير دوبلر Doppler المولد بفعل حركة أجنحة هذه الحشرات. فيعني هذا عمليًا أن الخفافيش تبصر باستخدام الصوت، وليست في حاجة لابصار شيء. هذا ما يفسر ميلها نحو النشاط الليلي رغم قدرتها على الإبصار نهارًا. وذلك رغم عدم قدرتها على الرؤية ليلًا مثل القطط والحيوانات الليلية الأخرى.

خصائص البحث بالصدى

رغم استمرار نبضات الصدى لأجزاء قليلة من الألف من الثانية، من 8 إلي 10 مللي ثانية، فإن لها ترددًا ثابتًا يتراوح بين 25 كيلو هرتز و150 كيلو هرتز. عمومًا نجد متوسط هذا التردد عند أغلب أنواع الخفافيش بين 25 و 100 كيلو هرتز. في حين أن أنواعًا قليلة فقط تصل ل 150 كيلو هرتز.
تختلف مدة استمرار النبضات وعددها حسب الظروف والنوع. فنجد أن الخفافيش الصغيرة تستطيع إصدار ما يتراوح بين 10 و 20 نبضة فوق صوتية خلال كل ثانية. هذه النبضات قادرة على الاستمرار بين 5 و 20 جزء من الألف من الثانية. لكن عند عملها على اصطياد فريستها واقترابها منها، قد يتسارع عدد هذه النبضات لما قد يصل إلي 200 نبضة فوق صوتية في الثانية الواحدة. وإن دل كبر هذا العدد على شيء فإنه يدل على مدى قوة قدرة أدمغة هذه الخفافيش على معالجة هذا الكم الكبير من المعلومات بهامش زمني صغير، وأن لها أذانًا جيدة للغاية. فتجد الدراسات أن وقت دمج أذن الخفافيش integration time يتراوح بين 300 و400 مللي ثانية. لكن أذان البشر أفضل بوقت دمج لا يتجاوز 100 جزء من الألف من الثانية.

نظرًا لكون سرعة الصوت في الهواء عند درجة حرارة الغرفة، أي 20 درجة سيلسيوس، تقارب 340 متر في الثانية. فإن الطول الموجي λ لكل نبضة يتراوح بين 2 و 14 مللي متر. باعتبار ترددها بين 25 و 150 كيلو هرتز. من الواضح أن هكذا أطوال موجية تجاور أطوال وأحجام فرائس هذه الخفافيش. والمثير للدهشة حقًا هو أن النبضات المنبعثة يمكن أن تعلو ويصل مستواها ل 110 ديسيبل. وكذلك من حسن حظ هذه الخفافيش أن تردد أصواتها يوجد في منطقة الموجات فوق الصوتية، إذ كانت لتباد من قبل البشر الأوائل أو حتى قبل ذلك من المفترسات الأخرى، فصوت بتلك الحدة ليس مزعجًا فقط بل وقد يسبب إجهادًا نفسيًا.

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

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

استنباط آلية عمل خوارزمية الخفاش

إن استنبطنا بعضًا من خصائص آلية بحث الخفافيش بالصدى، يمكننا تطوير عدد من الطرق الخوارزمية الصالحة للتطبيق في مواجهة المشاكل التحسينية. ومن أجل هذا، يمكن أن نخلص لثلاث أفكار رئيسية، وهي المفاهيم التي ستعتمدها خوارزمية الخفاش في تنفيذها:

1. جميع الخفافيش قادرة على إدراك المسافة التي تفصلها بين الأجسام التي تحيط بها. كما أنها أيضًا قادرة على التمييز بين هذه الأجسام، إن كانت طرائد أو فقط معوقات.
2. تحلق الخفافيش بسرعة معينة قد تختلف من نقطة لأخرى. إضافة لإمكانية تعديل تردد موجات نبضاتها، وبالتالي الطول الموجي، و كذلك التحكم في عدد النبضات في الثانية.
3. ورغم إمكانية تغيير مستوى الصوت بطرق مختلفة إلا أننا نفترض تغيره بين قيمتين A 0 موجبة وA min سالبة.

آلية عمل خوارزمية بحث الخفاش

حركة الخفافيش

عند محاكاة هذه الآلية يتوجب علينا تعريف الخفافيش الافتراضية. وذلك بوضع قواعد تحدد كيفية تغير وتحديث مواضعها وسرعاتها في فضاء مستمر متعدد الأبعاد. الشيء الذي يمكننا تحقيقه استنادًا لعدد من الصيغ والمعادلات، وهي كالتالي:

لكون الفضاء المدروس متعدد الأبعاد فإننا نتعامل مع متجهات، نجد بيتا عبارة عن متجهة عشوائية من التوزيع المنتظم، ذات مقادير محصورة بين 0 و 1. وتمثل *X الحل الحالي الأمثل والذي نحصل عليه بعد مقارنة جميع الحلول التي وجدتها الخفافيش الافتراضية. ولكون التردد والطول الموجي، والذي هو سرعة الصوت، ثوابت، يمكننا استخدام أي منهما في المعادلة الثانية من أجل ضبط تغير السرعة. وفي التنفيذ، يمكن وضع f min = 0 كمقدار أدنى للتردد و f max = O(1) انطلاقًا من حجم فضاء البحث. وعند وضع الخفافيش الافتراضية، يتم منحهم قيم تردد موزعة بين القيمتين الدنيا والقصوى.

وفيما يخص البحث المحلي، فعند انتقاء الأفضل بين الحلول الحالية التي يقدمها كل خفاش، يتم توليد حل عشوائي جديد لكل واحد انطلاقًا من صيغة سير عشوائي random walk وتكون كالتالي:

من وجهة نظر تنفيذية، يستحسن إضافة معلمة σ لتحجيم مدى الخطوة. وبالتالي تتغير معادلة السير العشوائي للصيغة التالية:

مستوى الصوت وإصدار النبضات

عند كل دورة تكرار، يجب تحديث قيم مستوى الصوت A0، و معدل إصدار النبضات ri وفقًا لبعضها البعض. وذلك لكون خفض الخفافيش لمستوى الصوت المنبعث عند اقترابها من فريستها. كما تزيد من عدد النبضات التي تصدرها خلال الثانية الواحدة. ولا يوجد شرط أو مانع من تحديد قيم مختلفة لمستوى الصوت بدئيًا في كل تنفيذ، فيمكننا اختيار A0 = 1 و A min = 0. ما يعني افتراضًا أن الخفاش بدئيًا يكون بقرب فريسته ويتوقف مؤقتًا عن إصدار أي صوت. ويمكن تلخيص كل هذا اعتمادًا على الصيغ التالية:

بحيث نجد أن ألفا α و غاما γ ثوابت. وهذه الثوابت تشبه نظيرتها في خوارزمية التخمير المحاكى بحيث يمكن تشبيه ألفا بمعدل التبريد في جدولة التلدين. فلكل 1>ألفا>0، و 0<غاما، نجد:

وتتطلب عملية اختيار معلمات الضبط بعضًا من التجربة والخطأ. فبدئيًا يجب أن يصدر كل خفاش مستوى صوت مختلف، مما يمكن الوصول إليه باعتماد العشوائية. فيمكننا، على سبيل المثال، أخد 1 كقيمة بدئية لمستوى الصوت و مقدار أخر بين 0 و 1 كقيمة لمعدل النبضات. وسيتم تحديث هذه القيم فقط عند تحسن قيمة الحل الأفضل الحالي، مما يعني اقتراب أحد الخفافيش من فريسته، أي في حالتنا هذه الحل الأمثل.

تحليل التقارب

قام جورج هوانغ G.Q. Huang وزملاؤه ببحث تفصيلي ومعمق لتحليل آلية تقارب خوارزمية الخفاش وذلك باستخدام نظرية معالجة ماركوف المتناهية finitie Markov process theory. ما مكنهم من أن يخلصوا لكون خوارزمية الخفاش تحقق جميع شروط ضمان التقارب للحل الأمثل في تحسين الدوال الهدف غير المقيدة Unconstrained objective functions. وبالنسبة للدوال المقيدة وغير الخطية، تتقارب هذه الخوارزمية للحل الأمثل باستعمال ضبط معين، initialization of orthogonal Latin squares.

واقترح الفريق أيضًا متحورًا مغايرًا بسرعة تقارب أعلى، وأطلقوا عليه اسم خوارزمية الخفاش المعدلة Modified Bat Algorithm، أو اختصارا MBA. كما بينوا أيضا قدرة هذا المتحور على مواجهة المشاكل التحسينية الضخمة بكفاء أعلى.

متحورات خوارزمية الخفاش

تعمل خوارزمية الخفاش الأساسية بشكل جيد في مواجهة الدوال الهدف المستمرة. ولكن للتعامل مع المشاكل ذات الدوال غير المستمرة ومعالجة المشاكل التوافقية، نجد أن هنالك حاجة إلى بعض التعديلات وابتكار متحورات جديدة. لذلك طور ناكامورا وزملاؤه الباحثين ما يسمى بخوارزمية الخفاش الزوجية Binary Bat Algorithm، أو اختصارًا BBA. من أجل حل هذة المشكلة لمواجهة الدوال الهدف المتقطعة.

ومن أجل غايات وأهداف مماثلة نجد العديد من المتحورات مختلفة الاستعمالات مثل:

• خوارزمية خفاش المنطق الضبابي Fuzzy Logic Bat Algorithm.
• خوارزميات الخفاش متعددة الأهداف Multi-objective Bad Algorithm، من طرف نفس مطور خوارزمية الخفاش الأصل شين شي يانغ.
• خوارزمية الخفاش الفوضوية Chaotic Bat Algorithm.

بالإضافة إلى العديد من المتحورات والامتدادات الأخرى.

تطبيقات خوارزمية الخفاش

يرجع تعدد متحورات خوارزمية الخفاش في الأساس لقوتها ومدى فعاليتها. فنجد أنه منذ تطويرها في سنة 2010 من طرف عالم الرياضيات والحاسوب شين شي يانغ Xin She Yang، تم استخدامها في كل مجالات التحسين الحوسبي. كما تم دراسة فاعليتها في مواجهة أغلب المشاكل التحسينية المعروفة. ومن بين هذه التطبيقات نجد:

• معالجة المشاكل التحسينية المستمرة مثل التصميم الصناعي والهندسة المعمارية.
• تحسين المشاكل التوافقية والجدولة، ما يمكن من حل مختلف مشاكل NP الصعبة.
• المشاكل المعاكسة وتقدير المعلمات، مثل مشاكل تصميم الإلكترونيات الدقيقة وتدبير نقل الحرارة.
• معالجة الصور والذكاء الاصطناعي.

مصادر

1. Nature Inspired Optimization Algorithms by Xin She Yang

النمل حشرات اجتماعية، تعيش في مستعمرات منظمة يتراوح عدد أعضائها بين المليونين إلي خمسة وعشرون مليون نملة. وعند بحثها عن المؤن، تتعاون مجموعات النمل فيما بينها بمختلف الطرق. فنجد من بينها، تركها لمركبات كميائية ذات رائحة معينة، أو فيرومونات من أجل التواصل مع بعضها البعض. واعتمادًا على هذه الفيرومونات تستطيع كل نملة تتبع كل مسار مشبع بها. وعند إيجاد النمل لمصدر طعام تقوم بوضع علامة كيميائية، أي وضع علامة عليه باستخدام فيروموناتها، إضافة لترك آثار كيميائية في المسار المؤدي إلى المصدر ذهابًا و إيابًا لمساعدة بقية المجموعة. تلك العمليات المعقدة أدت إلى استخدام خوارزمية مستعمرة النمل Ant Colony Algorithm في حل المشكلات الحوسبية المعقدة، فكيف حدث ذلك؟ وكيف تعمل تلك الخوارزمية؟

إنطلاقًا من البحث الأولي، والذي يكون عشوائيًا والمكلف في الوقت والجهد، تتغير تركيزات الفيرومونات من مسار لأخر. فتتبع النملات الباحثة المسار الأكثر تشبعًا. ويرجع هذا التشبع إلي تزايد عدد النملات اللاتي اتخدن هذا المسار. فباتخاد النمل لمسار محدد مرة تلو الأخرى يصبح، عمليًا، المسار المفضل. وذلك يرجع بالطبع لكونه يفيض بالفيرمونات المتروكة كعلامة من كل نملة سلكته. وهكذا تظهر طرق عديدة مفضلة نحو مصادر الطعام المكتشفة، والتي تكون غالبا هي أقصر طريق. وطريقة العمل هذه عبارة عن مثال من أمثلة ميكانيزمات رد الفعل الإيجابي positive feedback mechanisms.

السلوك المنظم للنمل

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

فبالرغم من عدم تواجد رقيب يصدر الأوامر والإرشادات، نجد أن السلوك المنظم موجود لا محالة، وبتلقائية. لذلك، فسلوك من هذا القبيل ليس غريبًا في الطبيعة، ونجده حاضرًا في عدد من العمليات والظواهر الطبيعية مثل تشكل الأنماط في جلود بعض الحيوانات وتعاون الحيوانات والحشرات التي تعيش في مجموعات فيما بينها، مثل النحل والطيور، وغيرهم.

أنماط البحث الاستثنائية

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

في اليوم الأول يقوم النمل بالتجوال بطريقة عشوائية لاستكشاف محيطه، فيتحرك باتجاه معين مسافة عدة مئات من الأمتار تم يتفرع لتغطية و استكشاف مساحة أكبر. وفي اليوم التالي يختار اتجاه أخر منحرفًا عن مسار اليوم السابق بزاوية مضبوطة تساوي °123، وبالتالي تغطية مساحة كبيرة أخرى. في اليوم الذي يليه، يختار مرة أخرى اتجاه مختلفا بنفس الزاوية. بهذه الطريقة يقوم أفراد المجموعة بتغطية المنطقة كاملة في غضون أسبوعين و بعدها ينتقلون لمنطقة جديدة للاستقرار بها مؤقتًا واستكشافها والاستفادة من مواردها.

الملفت للنظر في هذا الأمر أن النمل لا يختار زاوية °120 بل °123 بالضبط، ما يكنهم بحلول اليوم الثالث من ترك زاوية °10 عن اتجاه اليوم الأول. ما يعني أن النمل سيغطي كل المنطقة الدائرية في غضون أربعة عشر يوما بدون تغطية أي مساحة تم البحث فيها مسبقا. ما يجعل من هذه الظاهرة جد رائعة وفريدة في عالم الحيونات والحشرات.

مراحل البحث في خوارزمية مستعمرة النمل Ant Colony Algorithm

للتبسيط نأخد مسارين فقط بين مصدر الطعام و المستعمرة، يمكن تحليل المراحل كما التالي:

• المرحلة الأولى: كل النملات لا تزال في بيتها، ولا يوجد أي تركيز من الفيرومونات في محيطها.
• المرحلة الثانية: تبدأ النملات بحثها العشوائي أي لكل من الطريقين احتمالية مساوية للآخر في أن يؤخد، أي 0.5 في حالتنا هذه. ومن المؤكد أن الطريق الثاني أطول وبالتالي الوقت المطلوب لقطعه، والوصول للطعام، أكبر.
• المرحلة الثالثة: تصل النملات التي اتخذت الطريق الأقصر أسرع من نظيراتها، اللواتي سلكن الطريق الأطول، لمصدر الطعام. والآن من الواضح أن النمل الذي سيتبعهم في البحث سيواجه نفس المعضلة، معضلة اتخاد الطريق المناسب، لكن هذه المرة الطريق الأقصر متاح نظرًا للفيرومونات وبتركيز أعلى نظرًا لسرعة عودة النمل، وبالتالي احتمالية أعلى في اختياره.
• المرحلة الرابعة: تعود نملات أكثر وأكثر من الطريق الأقصر ما يزيد بشكل كبير من تركيز الفيرومونات في هذا الأخير. ما يقلص بشكل كبير احتمالية سلوك الطريق الأخر. وبالتالي كل المستعمرة ستستخدم الطريق الأقصر، أي أن عملية تحسين المسار قد تمت بنجاح.

آلية عمل خوارزمية مستعمرة النمل Ant Colony Algorithm

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

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

احتمالية اختيار المسار

في مشكلة توجيه الشبكة network routing، تكون احتمالية اختيار نملة في نقطة i التوجه نحو نقطة j ممثل بواسطة الصيغة التالية:

ما يعني أن المسار الأقصر هو الذي سيُسلك لكون مدة عبوره أصغر وبالتالي تركيز الفيرومونات عالٍ به. وهذه الصيغة الاحتمالية تعكس حقيقة أن النمل سيتبعون دائما المسار الأكثر تشبعًا بالفيرومونات. ففي الحالة الأبسط عند كون α=β=1، تكون هذه الاحتمالية مطابقة تماما لنسب التراكيز. وقيم المقام تقوم بمعايرة normalize هذه الاحتمالية لتحصر بين 0 و 1.

معدل تبخر الفيرومونات

يتغير تركيز الفيرومونات بمرور الزمن، فتتقلص تدريجيًا، بسبب التبخر، اعتمادًا على صيغة محددة. والأفضلية التي تكسبنا هذه الخاصية هي قدرتها على تمكيننا من تجنب الحلول المحلية. ففي أغلب حالات عدم تواجد هذه الألية، تصبح المسارات المتخذة عشوائيًا من طرف مجموعة البحث الأولى، مسارات مفضلة. وتمكننا المعادلة التالية، والتي تأخد معدل γ لاضمحلال وتبخر الفيرومونات، من تقليص هذه القيم بتقدم الزمن:

إن كانت γt أصغر بكثير من 1، و تغير الزمن Δt =1، نغير المعادلة للصيغة المبسطة التالية:

دراسة تقارب خوارزمية مستعمرة النمل

يمكن إثبات قدرة عدد من متحورات خوارزمية مستعمرة النمل Ant Colony Algorithm، على التقارب نحو الحل الأمثل للمشكل المعالج خلال مدة زمنية محدودة. لكن مثل أغلب خوارزميات الأدلة العليا Metaheuristic Algorithms، من الصعب تقدير سرعة التقارب نظريًا. وهو ما يضطرنا لدراستها تجريبيًا بتغيير معلمات ضبطها. فبهكذا دراسة تم التوصل لكون أن سرعة تنفيذ الخوارزمية جد حساسة لمعلمات الضبط هذه وخصوصًا معدل تبخر الفيرومونات.

متحورات وامتدادات

تعتبر خوارزمية مستعمرة النمل Ant Colony Algorithm من مواضيع البحث المثيرة. فنظرا لإمكانياتها الهائلة نجد أن المجتمع العلمي المتخصص قد قدم عدد ضخما من المتحورات و الامتدادات انطلاقا من الخوارزمية الأصل المطورة من طرف دوريغو، ونجد من بين أشهرها:

• الخوارزمية الأصل، خوارزمية مستعمرة النمل أو كما تمت تسميتها نضام النمل Ant System، واختصارًا AS.
• المتحور Max-min Ant System، أو اختصارا MMAS. وتختلف هذه الأخيرة عن المتحورات الأخرى، بحصر نسب الفيرمونات في كل المسارات بين مقدارين معينين، وكون الدورة الحالية الأمثل هي فقط قادرة على ترك نسب أعلى من الفيرمونات في مسارها.
• خوارزمية نظام تصنيف النمل Rank-based Ant System.
• مستعمرة النمل العمودية المستمرة Continuous orthogonal Ant System.
• خوارزميات النمل الافتراضية Virtual Ant Algorithms، لحل مشاكل التحسين التقليدية متعددة الأبعاد.
• نظام النمل النخبوي Elitist Ant System، يهدف هذا المتحور لجعل عملية الاستكشاف تتمحور حول الحل الأمثل الحالي. وذلك بجعل كل المسارات مرتبطة بالمسار الحالي الأفضل.
• خوارزمية نظام مستعمرة النمل Ant Colony System، أو ACS. بحيث تختلف عن الأصل في 3 نقط أساسية وهي: اختيار المسار منحاز لقدرتنا على استغلاله على مدار التكرارت التالية. تغير النملات معدل الفيرمونات في المسار المختار بكم مختلف من مسار لأخر. عند نهاية كل دورة، النملة الأفضل وحدها مخولة لتغيير نسب الفيرمونات في المسارات المتعددة، والتي ستتخدها المستعمرة في الدورة التالية.

تطبيقات خوارزمية مستعمرة النمل ومتحوراتها

تتكون الأنظمة المعقدة من عقد متفردة، لذلك يمكن تمديد هذه الخوارزمية لحل مشاكل توجيه جد معقدة Complex routing problems بطريق فعالة. ففي الواقع نجد أن خوارزمية مستعمرة النمل ومتحوراتها قد تم تطبيقها لحل المشكلات الضخمة الآتية:

• مشكل توجيه الإنترنت Internet routing problem.
• مشكل البائع المتجول Traveling Salesman Problem.

و أيضا عدد من المشاكل المتنوعة في مختلف المجالات نذكر منها:

• مشاكل الجدولة Scheduling Problems.
• مشاكل توجيه السيارات Vehicle Routing Problems.
• مشاكل التوزيع Assignment Problems.
• مشاكل المجموعات الرياضية Set Problems.
• تحجيم الأجهزة في تصميم إلكترونيات النانو Device sizing problem in nanoelectronics physical design.
• تصميم الأنتينات.
• معالجة الصور.
• التصميم الصناعي.
• القطاع البنكي والمصرفي.
• التنقيب عن البيانات.

و الكثير غيرها.

مصادر

1. GeeksforGeeks
2. Wikipedia
3. Nature-Inspired Optimization Algorithms

في الرياضيات، النزول التدرجي gradient descent أو ما يسمى أيضا النزول الأشد انحدار، يعتبر من خوارزميات تحسين الدرجة الأولى أي الخوارزميات التحسينية التي تستعمل المشتقة الأولى للدالة الهدف. وبالطبع استخدامها لهذه المشتقة يعني أن الدالة متصلة و مستمرة على مجموع نقاط الفضاء البحثي، أي الجزء الذي يعنينا من مجال تعريفها. وتهدف خوارزمية النزول التدرجي إلى إيجاد القيمة الأدنى لدالة قابلة للاشتقاق.

تتمحور آلية عمل هذه الخوارزمية حول فكرة أخذ عدد من الخطوات في المنحى المعاكس للتدرج negative gradient، أو التدرج التقريبي، في النقطة الحالية. وذلك لكون هذا المنحى هو منحى النزول الأشد إنحداراً steepest descent. وعلى النقيض، التقدم باتجاه منحى التدرج سيقودنا بالطبع للقيمة القصوى أو قيمة قصوى محلية للدالة.

أصول خوارزمية النزول التدرجي

عموما، تم الاجماع على نسب هذه الخوارزمية إلي عالم الرياضيات أوغستين لوي كوشي A.L. Cauchy. والذي كان أول من اقترحها في سنة 1847. تم اقتراح طريقة مشابهة، بشكل مستقل، من طرف جاك هادامار أيضًا سنة 1907. كما تم دراسة خاصيات هذه الخوارزميات للتقارب حول الحل الأمثل في المشاكل التحسينية غير الخطية، أول مرة، من طرف هاسكل كاري Haskell Curry سنة 1944. وتم دراسة خوارزمية النزول التدرجي واستخدامه، وقدمت أعداد كبيرة من الإسهامات، من متحورات وطرق استخدام أفضل، بشكل كبير في السنوات التي تلت.

مثال لفهم آلية عمل خوارزميات النزول التدرجي

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

باستعمال هكذا مقاربة ستجد نفسك، في النهاية، قد وصلت أسفل الجبل، أو بلغت حفرة تمتلأ بالماء ليلاً مما قد يتسبب في موتك.

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

في هذه المماثلة، يعبّر الشخص الخاضع لهذه الصعوبات عن الخوارزمية، كما يمثل المسار الذي يسلكه نقاط الفضاء التي ستمر الخوارزمية منها عند تعدد التكرارات. ويمثل الانحدار ممال الدالة عند نقطة القياس. كما يمثل الجهاز الذي يحدد الانحدار، عملية الاشتقاق. ويعتبر أسفل الجبل، القيمة الدنيا للدالة أي الحل الأمثل، بينما الحفر والبحيرات الجبلية تعبر عن الحلول المحلية للدالة أي النقاط الدنيا المحلية. إضافة لذلك، نجد أن منحى الحركة هو سالب الانحدار negative gradient، أي (x)F∇-. كما أن المدة الزمنية بين كل قياس باستعمال الجهاز، هي الخطوة γn.

شرح رياضي لآلية عمل خوارزمية النزول التدرجي

لارتكاز هذه الخوارزمية بشكل أساسي على دراسة الدالة الهدف (x)F متعددة المتغيرات، المعرفة والقابلة للاشتقاق، يكون تناقصها عند أقصى قيمة عند الذهاب من النقطة الحالية باتجاه المنحى المعاكس للتدرج (x)F∇-.

مع العلم أن x متغير متعدد الأبعاد أي نقطة في فضاء متعدد الأبعاد. بحيث تمثل n دورة التكرار الحالية. نبدأ ب n=0 أو الدورة صفر أي القيمة البدئية قبل بداية التكرارات. تمثل γn حجم الخطوة الذي يمكن أن يتغير من دورة لأخرى.

أهمية حجم الخطوة γ ومنحى النزول

بما أن اختيار خطوة صغيرة سيبطئ سرعة التقارب، واختيار أخرى كبيرة سيقود للانحراف عن الحل. فإن إيجاد إعدادات ضبط مناسبة للخطوة γ أمر محوري في وصولنا لما نبتغيه، ما يعني إيجاد الحل الأمثل بأقصى سرعة ممكنة وبالتالي أقل استهلاك للقوة الحوسبية computational power. كما من المهم أيضا عدم اتباع المنحى الأكثر انحدارًا دائمًا، بحيث يمكن أن يكون الانحدار الأصغر أكثر ديمومة ويستمر لمسافة أكبر ويقودنا ربما لحل أفضل.

للحرص على تحقيق كل هذا، يوجد عدد من الطرق الرياضية منها:

• البحث الخطي الذي يستوفي شروط وولف Wolfe conditions.
• البحث الخطي التراجعي backtracking line search.
• طريقة Barzilai–Borwein، الموضحة في الأسفل.

يكون التقارب لحل محلي أمرًا مضموناً دائمًا. وإن كانت الدالة الهدف محدبة convex، يكون التقارب للحل الأمثل مسلمًا به نظرًا لتطابق الحلين المحلي والأمثل.

متحورات خوارزمية النزول التدرجي

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

نزول الدفعة التدرجي Batch Gradient Descent

هذه الخوارزمية تعالج كل أمثلة التعلم عند كل دورة تكرار. لذا لا ينصح استخدامها عند ضخامة عدد الأمثلة، وذلك لأن استعمالها يصبح مكلف حوسبيًا computationally expensive. ومن إيجابيات هذه الخوارزمية أنها دائمًا ما تتقارب نحو حل جيد، وكلما ازداد عدد الأمثلة قلت نسب الخطأ. لكن كسلبيات، نجد تباطؤها عند معالجتها لعدد كبير من الأمثلة، وهذه الأمثلة التي من الممكن أن تكون متكررة أو متشابهة، مما يعني عدم جدوى معالجتها عند كل دورة.

نزول الدفعة المصغرة التدرجي Mini-batch Gradient Descent

بدلًا من معالجة كل الأمثلة عند كل دورة نقسم الأمثلة لمجموعات صغيرة ونقوم بمعالجتها كل على حدى. دائمًا ما نأخد حجم العينات من أُس 2 أي 2 4 8 16 32 64 128 256 …… يرجع هذا لكون عدد من الهاردوير، مثل وحدة معالجة الرسوميات GPU، تحقق سرعة تنفيذ جيدة عند تقسيم هذه العينات بهذه الطريقة.

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

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

خوارزمية النزول التدرجي التصادفية Stochastic Gradient Descent

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

مصادر

1. Medium
2. GeeksforGeeks
3. Wikipedia
4. TowardsDataScience

الخوارزميات في جوهرها هي عبارة عن سلسلة من التعليمات البسيطة التي يمكن نهجها لتحقيق غاية ما. إذا ما بحثنا، نجد من بينها الخوارزميات العودية وإذا بحثنا بين هذه الأخيرة نجد الخوارزميات التحسينية، مثل الخوارزمية التالية والتي تستخدم لإيجاد الجذور المربعة لأي عدد حقيقي موجب:

ما يحدد كفاءة الخوارزمية هو سرعة تقاربها convergence speed. ومن السهل إثبات صحة أن الجذور المربعة لأي عدد أولي هي أعداد غير كسرية، أي أنها أعداد برقم لا نهائي من الأعداد بعد الفاصلة، وبالتالي لا يمكن حسابها. لكن باستخدام هذه الخوارزمية يمكننا التقارب لإيجاد حل مرضٍ بالدقة التي نريد.

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

فما هي الخوارزميات المستوحاة من الطبيعة؟ و كيف ظهرت؟ وما أبرزها؟ ما هي استعمالاتها؟ وما الخصائص التي تتشارك فيها هذه الخوارزميات؟

ما هي الخوارزميات التحسينية المستوحاة من الطبيعة ؟

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

ظهور الخوارزميات التحسينية

ظهرت الخوارزميات التحسينية في بداية القرن التاسع عشر على يد عدد من علماء الرياضيات «ك ويستراس K.T.W Weierstrass»، و«شتاينر J. Steiner»، و«هاميلتون W.R.Hamilton»، و«جاكوبي C.G.J Jacobi».

ظهور الخوارزميات التحسينية المستوحاة من الطبيعة

على مر التاريخ وخصوصًا في الفترات الأولى، اعتمدت مقاربتنا نحن البشر في حل المشاكل التي نواجهها ولا تزال على التجربة والخطأ. أي أنها مقاربة تفاعل مع النظام المراد استكشافه خطوة بخطوة metaheuristic approach. فعدد كبير من الاكتشافات تم عن طريق التفكير خارج الصندوق أو بالصدفة، وهذا ما يعنيه الحدس heuristic. ورغم ذلك نجد أن أول استعمال مسجل لاستخدام هذه المقاربة كطريقة علمية رياضية meta-heuristic method لحل المشاكل problem-solving كان على الأرجح خلال فترة الحرب العالمية الثانية على يد عالم الرياضيات والحوسبة الغني عن التعريف «ألان تورنغ». استخدم تورنغ تلك التقنيات لفك تشفير إتصالات الألمان وكسر آلية تشفيرها Enigma. ورغم كون هذه الطريقة غير مضمونة الوصول للنتائج المرجوة إلا أن استعمالها في مشروعه كان نجاحًا باهرًا، ما أعطى دول الحلفاء ورقة رابحة لإنهاء الحرب لصالحهم.

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

في نفس الوقت، كان العالم والمهندس «جون هولاند John Holland» يعمل رفقة زملائه في جامعة ميشيغان على استكشاف وإنتاج أول الخوارزميات الجينية. وهو ما توج لاحقًا بنشر مجموع أبحاثه في كتابه «Adaptation in natural and artificial systems» سنة 1975. بعدها تم كتابة مئات الكتب وآلاف المقالات عن هذا الموضوع.

الأعوام التي تلت كانت جد حافلة بحيث شهدت تطوير مختلف أنواع الخوارزميات وفتح مجالات بحثية خاصة بكل منها.قاد ذلك الحراك عدد من الرواد مثل عالم الرياضيات «شين شي يانغ Xin-She Yang» مطور خوارزميات مثل «بحث الوقواق CS»، و«خوارزمية الخفاش BA»، و«خوارزمية اليراعة FA»، وغيرهم.

أمثلة على الخوارزميات المستوحاة من الطبيعة

حتى الآن، تم تقديم عدد كبير من الخوارزميات المستنبطة من الطبيعة، رفقة عدد أكبر من متحوراتها الأكثر تخصصًا. يمكن لهذه الخوارزميات أن تستخدم في مختلف المجالات، من بينها نجد:

• الخوارزميات الجينية أو Genetic Algorithms، إختصارًا GA.
• خوارزميات إستمثال عناصر السرب أو Particle Swarm Optimization، اختصارًا PSO Algorithms.
• خوارزمية التطور التافضلي Differential evolution، اختصار DE Algorithm.
• الخوارزمية مستعمرة النحل الاصطناعية Artificial Bee Colony، اختصارًا ABC Algorithm.
• خوارزمية التحسين مستعمرة النمل Ant Colony Optimization، اختصارًا ACO Algorithm.
• الخوارزمية بحث الوقواق Cuckoo Search، اختصارًا CS Algorithm.
• خوارزمية الخفاش Bat Algorithm، اختصارًا BA.
• خوارزمية اليراعة Firefly Algorithm، اختصارًا FA.
• الخوارزمية المنيعة Immune Algorithm، اختصارًا IA.
• خوارزمية التحسين الذئب الرمادي Grey Wolf Optimization، اختصارًا GWO Algorithm.
• الخوارزمية البحث التجاذبي Gravitational Search، اختصارًا GS Algorithm.
• خوارزمية البحث التناغمي Harmony Search، اختصارًا HS Algorithm.

ما الخصائص المشتركة بين الخوارزميات التحسينية المستوحاة من الطبيعة ؟

عند ملاحظة هذه الخوارزميات نجد أن لها بنية متشابهة رغم أن كل واحدة منها محددة في إطارها الخاص. من بين هذه التشابهات نجد أن المقاربة التي تنتهجها أغلب الخوارزميات التحسينية المستنبطة من الطبيعة في معالجة المشاكل التي صممت لحلها يمكن تلخيصها في أربع خطوات، وهي:

• وضع الساكنة البدئية. لتحقيق هذا، هناك العديد من المقاربات منها الاختيار العشوائي للساكنة 0، … .

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

• حساب معامل التوافق fitness value والتحقق من شروط إنهاء التنفيذ termination conditions. فإضافة إلى تحديد حجم الساكنة البدئية وكيفية بنائها، يجب أيضًا وضع المدخلات مثل المتغيرات التي تتدخل في كيفية التنفيذ وشروط وقف التنفيذ وإرجاع الحل. فأغلب الخوارزميات التحسينية تستعين بشروط للخروج من دورة التنفيذ المتمثلة في البدء، ثم المعالجة، ثم الفلترة. من بين هذه الشروط نجد:

• العدد الأقصى للتكرارات.
• العدد الأقصى للتكرارات عند عدم تغير الحل المحلي الأمثل Local Optima، أي الفرد صاحب أكبر معامل توافق أو عدد من الأفراد الأكثر توافقًا. فإن لم يتغير لعدد من التكرارات، يتم اعتباره أفضلها كحل أمثل Global Optima. أو أن التقرب للحل الأمثل غير ممكن وفي كلتا الحالتين يتم إرجاع هذا الفرد أو الساكنة الحالية ككل باعتبارها حلًا، ثم وقف التنفيذ.
• عتبة الدقة، أي نسبة الدقة التي يحق للخوارزمية عند تحققها وقف التنفيذ. وعند هذه الخطوة نقوم بفلترة الساكنة الناتجة عن الخطوة الثالثة وذلك بترتيبها أولًا حسب معامل توافقها وأخذ الأكثر توافقًا. وحجم الساكنة الذي نأخذه هنا لا يمكن أن يكون إلا أصغر من أو يساوي السعة القصوى.
• يحسب معامل الكفاءة أو التوافق fitness value باستعمال دالة نعرفها حسب الحاجة. على سبيل المثال، حساب المسافة بين النقطة والتي تليها إن كانت الساكنة عبارة عن سلسلة من النقط في فضاء متجهي وجمعها كمعامل توافق.

•تحديث الساكنة باستخدام عدد من العمليات من بينها الدمج والتحوير. فعند عدم تحقيق أي شرط من شروط الخروج، تستمر سلسلة التنفيذ ونتقدم بذلك إلى الخطوة الثالثة والتي يتم خلالها «الدمج- crossover» بشكل عشوائي بين أفراد الساكنة وإضافة الناتج إلي الساكنة الحالية. يمكن أن نفكر في هذا على أنه تزاوج وإنتاج جيل جديد يحمل صفات أسلافه. بعد هذا نقوم بنسخ الساكنة ووضع طفرات عشوائية بها random mutations ونضيفها بدورها إلي الساكنة الكلية. ونعود بعدها للخطوه الثانية.

•إرجاع المخرجات ووقف التنفيذ. فعند تحقق أحد شروط الخروج، يتم إرجاع الساكنة الحالية باعتبارها حلاً وإنهاء التنفيذ.

مفاهيم مهمة لفهم الخوارزميات المستوحاة من الطبيعة

• الطريقة «الحدسية – heuristic» هي مقاربة لحل المشاكل باستعمال طرق فعالة لكن غير مضمونة النتائج أو عقلانية في بعض الأحيان. لكن الحدسية فعالة وكافية لتحقيق المقاربة approximation وللوصول لنتائج سريعة وتحقيق أهداف متعددة على المدى القصير.

• «الأدلة العليا metaheuristic» وهي في علم الحاسوب والرياضيات إجراءات أو إرشادات عالية المستوى مصممة لإيجاد أو إبتكار أو اختيار طريقة بحث خوارزمية «حدسية» قادرة على توفير حل مقبول لمشكلة تحسينية. نلجأ إليها خاصة عند عدم توافر معلومات أو قوة حوسبية كافية تخولنا استخدام الطرق التقليدية.

أهم التحديات التي تواجه الخوارزميات المستوحاة من الطبيعة

عرفت الثلاثون سنة الأخيرة تقديم عدد كبير من خوارزميات الأدلة العليا meta-heuristic Algorithms بحيت نجد أن هذا الإنتاج متطورًا بشكل أسي أي بسرعة متضاعفة. ما جعلنا نرى في الآونة الأخيرة صدور خوارزميات الأدلة العليا بشكل يومي، وهو ما دفع بدوره تطوير الخوارزميات التحسينية والخوارزميات التحسينية المستوحاة من الطبيعة لمنحى أسي كذلك. أسهم ذلك بشكل كبير في تقديم حلول ناجحة وفعالة للمشاكل التحسينية في مجال الذكاء الاصطناعي وعدد من المجالات الهندسية الأخرى.

لكن رغم هذا التقدم الكبير و النجاح الباهر الذي حققته هذه الخوارزميات وهذا المجال البحثي، لا يزال هناك تحديات كبيرة أمامه والتي يمكن تلخيصها في أربع نقط أساسية:

• نقص البحث الكافي في النظريات البنيوية والأدوات التي تستخدمها هذه الخوارزميات مثل:

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

°وضع أساس صلب من النظريات الرياضية لدعم الخوارزميات التحسينية المستنبطة من الطبيعة، مثل تحليل التعقيد الزمني time complexity، واختبار التقارب convergence proof. ومن المهم تقديم نظرية رياضية شاملة للموازنة بين التناقض بين التقارب لحل محلي convergence to a local optima وبطء التقارب slow convergence.

• نجد أن الخوارزميات التحسينية المستوحاة من الطبيعة أقل قدرة على حل المشاكل التحسينية المستمرة Continuous optimization problems في البيئات الحقيقة المعقدة. وهنا نجد أن البيئات التي نطبق عليها هذه الخوارزميات هي في الأصل معقدة، متعددة الأبعاد و الأهداف، وتهدد الدقة ومستهلكة للوقت. وفي بعض الأحيان تكون دالة تقييم الملائمة غير محددة. لذا فهذا النوع من المشاكل يشكل تحدياً كبيراً للخوارزميات التحسينية ككل رغم الجهود التي بذلت لتجاوزها.

• لا يوجد الكثير من الدراسات المشتركة inter-disciplinary researchs بينها وبين المجالات المستخدمة فيها والمجالات ذات الصلة، وذلك رغم كونها تحمل إمكانات كبيرة ذات فائدة مشتركة.

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

إمكانات خوارزميات الطبيعة

من هنا يتضح لنا أن التوجه البحثي المستقبلي في مجال الخوارزميات التحسينية يجب أن يتمحور حول معالجة هذه المشاكل؛ و ذلك بتقوية تحليل نظري متين لهذه الخوارزميات.

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

مجالات استخدام الخوارزميات التحسينية

تستخدم الخوارزميات التحسينية و بالتالي الخوارزميات المستلهمة من الطبيعة منها في عدد من المجالات للتعامل مع عدد من المشاكل العملية. ففي ظل تطور الحوسبة، أصبحت الخوارزميات التحسينية أكثر أهمية ورواجًا في عدد من المجالات الهندسية. ومن استعمالاتها نجد:

• الطرق التحسينية الكلاسيكية في الحساب Optimization methods.
• الأنظمة المعلوماتية Information systems.
• هندسة التصنيع و الأنظمة الصناعية Industrial Engineering and Manufacturing systems.
• التصميم الهندسي Engineering design.
• سلسلة الإنتاج Supply chain management.
• الفلترة الرقمية Digital filter design.
• معالجة الصور Image processing.
• تعلم الآلة Machine learning.
• تصميم المفاضلات والمكاملات الرقمية Digital integrator and differentiator design.
• التعرف على الوجوه Face recognition.
• الشبكات العصبية الاصطناعية Artificial neural networks.

وغيرها.

المصادر:

1. ScienceDirect
2. Scholarly
3. Community Encyclopedia
4. Geeks for Geeks
5. Hindawy