التصنيف: ذكاء اصطناعي

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

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

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

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

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

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

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

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

عند تعدد مصادر الرحيق، أثبتت الدراسات أن السلوك المنظم للمستعمرة قادر على توزيع النحلات الجامعة على هذه المصادر بطريقة فعالة. وذلك من أجل جمع أقصى قدر من الرحيق. فكي تستطيع المستعمرة النجاة خلال فصل الشتاء، يتوجب جمع ما لا يقل عن 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

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

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

التناغم و الترددات

تحدد هذه النغمة المثالية اعتمادًا على المعايير الجمالية للمستمع، وهو ما يستوجب ضبط جودة جمالية الأدوات الموسيقية عبر تحديد درجة النغمة pitch، أي التردد frequency، و الطابع الصوتي timbre، أي جودة الصوت quality، والذروة amplitude، أي جهارة الصوت loudness. وتحدد الدروة انطلاقًا من المحتوى التناغمي والذي يحدد بدوره بناء على الشكل الموجي وتضمين الإشارة الصوتية.

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

أو

ما يعني أن ل A4 رقم نغمة يساوي 69، لأن ترددها هو 440 وبالتالي لوغاريتم 1 هو صفر ومنه p=69. وعلى هذا السلم نجد أن حجم الجواب، أو الأوكتاف هو 12 وحجم نصف النغمة هو 1. كما أن النسبة بين تردد نغمتين تبعدان جواب عن بعضهما هو 2:1. وبالتالي تردد نغمة يضاعف أو يخفض إلي النصف عند تغيرها بجواب. على سبيل المثال ل A2 تردد 110Hz، بينما تردد A5 هو 880Hz. لذا فرغم كون تحديد الجمالية أمر غير موضوعي ويعتمد على أذن السامع، يمكننا وضع تقدير معياري لتقدير التناغم. وذلك بالاعتماد على نسبة التردد المنسوبة لعالم الرياضيات اليوناني القديم فيثاغورس.

كمثال نجد أن جواب بنسبة تردد 1:2 جذاب عند لعبه معا، نفس الشيء لنسبة التردد 2:3. لكن من غير المرجح لأي نغمة عشوائية مثل الممثلة أعلاه أن تصدر أي صوت جميل.

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

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

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

1. الذاكرة التناغمية

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

2. ضبط النغمات

لتعديل النغمة قليلًا، في المكون الثاني، نستعمل طريقة تمكننا من ضبط التردد بكفاءة. نظريا يمكن تعديل النغمة بطريقة خطية أو غير خطية. لكن في التطبيق نجد أن التعديل الخطي هو المستعمل. باعتبار X old هي النغمة الحالية، نجد أن النغمة الجديدة X new تولد بواسطة الصيغة أدناه:

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

3. خلق العشوائية

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

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

متحورات خوارزمية البحث التناغمي

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

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

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

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

وقد قدم عمران ومادهافي المتحور Global-best Harmony Search مستلهمين أفكارًا من خوارزميات استمثال عناصر السرب Particle Swarm Optimization. في هذا المتحور يقوم تعديل النغمة انطلاقا من أفضل حل من الذاكرة التناغمية فقط، بدون اعتبار لعرض النطاق bp. وهو ما أضاف قدرات تعلم اجتماعي social learning فريدة لهذه الطريقة. وقد تم التأكد من أن أداء هذا المتحور أفضل من أداء الخوارزمية الأصل تجريبيًا.

تقدم الخوارزمية المتحورة DLHS Dynamic Local-best Harmony Search مقاربة خوارزمية تنطوي على تقسيم الساكنة الحالية إلي ساكنات فرعية، تتطور بشكل مستقل عن بعضها البعض. غير أن هذه الذاكرات الفرعية تجتمع لتكوين الذاكرة التناغمية الحالية بعد بحثها عن الحل الأمثل على حدى في مجالاتها المحلية الخاصة، مستوحاةً من النسخ المحلية لخوارزمية استمثال عناصر السرب PSO والمتحور GHS، ومقترحةً من طرف “كوان كي بان” وزملائه.

من خلال سياستها هذه واستراتيجية البحث المحلية المبسطة ، فإن المتحورة DLHS قادرة على تحقيق توازن مرضٍ بين الاستكشاف exploration والاستغلال exploitation في البحث. فنجد من بين تطبيقاتها أنها طبقت بنجاح لمواجهة مشكل الجدولة lot-streaming flow shop القائم على تقسيم عملية ما لمجموعة من العمليات المصغرة والتي تنفذ بطريقة متداخلة.

وعلى هذا المنوال، نجد العديد من المتحورات الأخرى التي استلهمت من سابقاتها منها Particle Swarm Harmony Search PSHS من طرف جيم. وإلخ.

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

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

مصادر
Hindawi
ScienceDirect
Nature Inspired Optimization Algorithm by Xin She Yang

في الرياضيات، النزول التدرجي 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

يهدف التحسين optimization في الخوارزميات إلى إيجاد مجموعة من المدخلات للدالة الهدف objective function، ما ينتج عنه قيمة قصوى أو دنيا لهذه الدالة. هذه المشكلة تلخص هدف عدد من خوارزميات الذكاء الاصطناعي، مثل الانحدار اللوجستي logistic regression وتدريب الشبكات العصبية الاصطناعية artificial neural networks. وعلى الأرجح، هناك المئات من الخوارزميات التحسينية المعروفة ومتغيراتها. وكذلك توجد عشرات الخوارزميات التي يمكنك الاختيار منها لحل مشكلتك، في مكتبات الكود البرمجي العلمية المعروفة scientific code libraries. إذاً فمن الصعب معرفة الخوارزمية الأفضل للاستعمال في حل مشكلتك التحسينية.

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

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

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

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

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

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

القيم الدنيا والقصوى

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

مفاهيم رياضية مهمة لفهم عملية التحسين

• المشتقة الأولى first-order derivative: الدالة القابلة للاشتقاق هي الدالة التي نستطيع حساب مشتقتها في أي نقطة من نقاط مجالها، أي الفضاء المدروس. فمشتقة الدالة في نقطة هي معدل أو مقدار التغير، تغير الدالة، في تلك النقطة، أو ما يسمى بالميل.
• التدرج gradient: يطلق على مشتقة دالة متعددة المتغيرات بالتدرج. أي دالة بأكثر من متغير واحد. وهذه المشتقة هي عبارة عن متجه. بحيث يمثل كل عنصر من عناصر هذه المتجه مشتقة جزئية للمتغير المكافئ لها.
• المشتقة الجزئية partial derivative: تمثل كذلك معدل أو مقدار التغير في نقطة بدلالة متغير باعتبار كل المتغيرات الأخرى ثابتة.
• المشتقة الثانية second-order derivative: وهي مشتقة المشتقة، بحيث تمثل تغير التغير. أي تغيرُ تغيرِ الدالة الهدف. وهي الأخرى يمكن أن تتواجد في نقطة من الفضاء أو لا، أي يمكن أن تكون المشتقة قابلة للاشتقاق أو غير قابلة.
• المصفوفة الهيسية hessian matrix: لكل دالة متعددة المتغيرات وقابلة للاشتقاق مرتين أو أكثر مصفوفة هيسية تعبر عن قيمة مشتقتها الثانية، والتي يمثل كل عنصر فيها المشتقة الجزئية من الدرجة الثانية لكل متغير.

الدالة الهدف القابلة للاشتقاق

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

خوارزميات التأطير

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

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

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

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

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

يطلق عموما على هذه الخوارزميات، خوارزميات النزول التدرجي gradient descent algorithms. وتوفر خوارزمية النزول التدرجي الكلاسيكية الإطار العام لنظيرتها التصادفية، والمسمات بخوارزمية النزول التدرجي التصادفية stochastic gradient descent algorithm المستعملة في تدريب نماذج الشبكات العصبية الاصطناعية في التعلم العميق.

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

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

الدالة الهدف غير القابلة للاشتقاق

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

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

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

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

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

• Cyclic Coordinate Search
• Powell’s Method
• Hooke-Jeeves Method
• Nelder-Mead Simplex Search

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

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

• التخمير المحاكى simulated annealing.
• الاستراتيجية التطورية evolution strategy.
• خوارزمية الإنتروبيا cross-entropy method.

خوارزميات الساكنة

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

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

• الخوارزميات الجينية genetic algorithms.
• خوارزمية التطور التفاضلي differential evolution.
• خوارزمية استمثال عناصر السرب particle swarm optimization.

المصادر

1. ScienceDirect
2. Machine Learning Mastery