A gravity search algorithm with a distance-fitness evaluation strategy for path planning

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

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

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

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

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

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

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

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