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

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

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

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

ما يحدد كفاءة الخوارزمية هو سرعة تقاربها 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