خوارزمية البحث في الحي المتغير
المحتويات
في البداية، البحث في الحي المتغير هي خوارزمية تنحدر من ضمن فئة خوارزميات الأدلة العليا والتي تهدف لإيجاد وابتكار طرق بحث نحصل من خلالها على حلول لمشاكل ذي حجم عالي أو معلوماتها المتوفرة غير كافية أو غير مكتملة في وقت قصير وبجودة جيدة إلا أنها لا تضمن مثالية الحل الموجود. البحث في الحي المتغير تقوم بعملية بحث داخلي محسنة ومطورة حيث يتم استكشاف بنية الفضاء البحثي الممكن لهدف إيجاد حل أفضل من الحل الحالي والهروب من القاع الذي يحتويها عن طريق تغيير الحي القريب من الحل الحالي بالتناوب من ضمن مجموعة أحياء معرفة مسبقا. عامةً ليس من الصعب العثور على الحل الأمثل الداخلي لأي مشكلة في الخوارزميات ولكن من الصعب العثور على الحل الأمثل العالمي الأمثل وذلك لأن الكثير من الخوارزميات مثل خوارزمية البحث الداخلي تعلق وتتم محاصرة في القاع الذي يحتوي على الحل الأمثل الداخلي ومن ثم لن يمكنها الوصول الحل الأمثل العالمي. لذلك تم تقديم هذه الخوارزمية من قبل ملادينوفيتش وهانسن في سنة 1997م بهدف التغلب على مصيدة الحل الأمثل الداخلي. مبدئياً تم تصميم هذه الخوارزمية لحل مشاكل التقليص ولكن يمكن تحويلها واستخدامها بسهولة في مشاكل التعظيم. ونتناول فيما يلي مزيدًا من التفاصيل.
أشكال خوارزمية البحث في الحي المتغير
وفي السياق ذاته، البحث في الحي المتغير الأساسية: تستعمل خوارزمية البحث الداخلي البسيطة وتعتمد على إستراتيجية الحل الأفضل في الحي المجاور خلال مرحلة التطوير، ويتم فيها تغيير الأحياء بشكل متتالي.
في هذا الإطار، هنالك الكثير من الأشكال التي تم تطويرها لخوارزمية البحث في الحي المتغير، والتي تدل على مرونة هذه الخوارزمية وقابلية تغييرها حسب معطيات الحل الموجودة والأهداف المطلوبة؛ ومنها:
في هذا الإطار، البحث في الحي المتغير المنحرف: تأخذ بعين الاعتبار الفرق بين الحل المبدئي الأول والحل القائم.
من جهة ثانية، البحث في الحي المتغيرالمصغرة: تتجاهل مرحلة التطوير ويتم اعتماد مرحلة الاضطراب وتغيير الحي فقط.
الهيكل العام
في هذا الإطار، التطور الأفضل: وفيه يتم دراسة وبحث جميع الحلول الممكنة في الحي المجاور للحل الحالي، وسيتم اعتبار أفضل حل بينهم هو الحل القائم بعد انتهاء عملية البحث في ذلك الحي.
وعلى صعيد آخر، الهيكل العام لخوارزمية لبحث في الحي المتغير يتكون من خطوتين: التهيئة والخطوة الأساسية:
وعلى صعيد آخر، هنالك الكثير من الاجراءات الممكن استخدامها لتغيير الحي الحالي الذي تتم فيه خوارزمية البحث ومنها نذكر أربعة:
وفي هذا الصدد، خوارزمية الهبوط في الحي المجاور (The Variable Neighborhood Descent): وهي نوع من أنواع البحث في الحي المتغير وتستغل حقيقة أن احتمالية أن يكون الحل الأمثل الداخلي بالنسبة لجميع الأحياء المستعملة هو حل أمثل عالمي، أكبر من احتمالية الحل الأمثل الداخلي الموجود بالنسبة لحي واحد فقط. وتقوم هذه الخوارزمية في البحث في جميع الأحياء المعرَفة بطريقة متتالية أو متداخلة على عكس عملية البحث الداخلي التي يتم تطبيقها لحي واحد فقط. ويمكن أن تستعمل واحدة من استراتيجيات البحث الداخلي سواء التطور الأول أو التطور الأفضل.
من جانب آخر، التطور الأول: عندما يتم إيجاد أول حل أفضل من الحل الحالي، سيتم اعتباره الحل القائم وسيكون بداية لعملية بحث داخلي أخرى.
وعلى صعيد آخر، التغيير الأنبوبي للحي: إذا تم إيجاد حل أفضل من الحل الحالي في أحد الأحياء، سيتم استكمال البحث في ذلك الحي. هذا النوع من التغيير يؤدي لتحقيق فكرة تكثيف البحث.
وفي هذا السياق، المرحلة الثالثة\ تغيير الحي: يتم فيها مقارنة الحل الموجود في المرحلة السابقة 𝑥” بالحل الحالي 𝑥:
من جانب آخر، إذا كان الحل 𝑥 أفضل من الحل 𝑥”، يستكمل البحث في الحي الذي يليه في الترتيب وسيتم بدء عملية اضطراب جديدة.
في هذا الإطار، يتم في هذه المرحلة اختيار حل جديد عشوائياً لبدء عملية البحث الداخلي وتهدف هذه المرحلة للهروب من القاع الذي يحتوي على الحل الأمثل الداخلي ولتجنب البحث في نفس الحلقة والتي غالباً ما تتكون عندما يتم ايجاد الحل بطريقة جبرية؛ فاحتمالية اختيارنفس الحل مرتين عند استخدام الطريقة العشوائية جداً قليلة مقارنةً بالطريقة الجبرية. الحل المختار في هذه المرحلة غالباً يحمل البعض من ميزات الحل الحالي. هذا الحل سيتم استخدامه في عملية البحث الداخلي من أجل العثور على حل أمثل داخلي جديد ولكن يجب أن لا يكون حل بعيد جداً عن الحل الحالي لأن ذلك سيؤدي إلى تكوين عملية بحث داخلي متعددة البدايات مع ايجاد حل عشوائي جديد في كل مرة مختلف كلياً عن السابق. وخصوصاً أن في بعض من المشاكل، يُفضل أن يتم تكثيف البحث في حي مجاور قريب، وهذا ما أدى إلى تقديم عملية الاضطراب المكثف والذي يركز على ايجاد حلول ضمن نطاق قريب جداً من الحل الأمثل الداخلي، حيث يتم الأخذ بعين الاعتبار مدى حساسية دالة الهدف لأي تغيير بسيط في متغيرات الدالة.
من جهة ثانية، التغيير المتتالي للحي: عندما يتم العثور على حل قائم قادر على تحسين الحل الحالي، سيتم استئناف عملية البحث في أول حي من جديد بالنسبة للترتيب المعرف للأحياء في المجموعة الخاصة بالحل القائم الجديد. أما في حالة لم يتم العثور على حل يُحسن الحل الحالي، البحث يُستكمل في الحي التالي.
وفي هذا السياق، التغيير الحلقي للحي: يتم استكمال البحث في الحي التالي سواء تم ايجاد حل أفضل أم لا.
وفي السياق ذاته، المرحلة الثانية\ التطوير: يعتبر الحل الموجود من مرحلة الاضطراب هو نقطة البداية لإجراء عملية البحث الداخلي ويتم فيها استخراج حل أفضل ويرمز له بـ 𝑥”.
ومن جهة أخرى، التغيير المنحرف للحي: يتم قبول كلا النوعين من الحلول؛ المحسنة وغير المحسنة للحل الحالي. الهدف وراء هذا النوع من التغيير هو للسماح بالاستكشاف في مناطق أو أحياء بعيدة عن الحل القائم وبهذا يتم تحقيق التنوع في البحث. لذلك يتم تقييم الحلول بالارتكاز على قيمة دالة الهدف للحل القائم والحل الحالي فضلًا عن الفرق بين القيمتين.
التهيئة: وهي الخطوة الأولى يتم فيها:
وفي هذا السياق، تتم عملية تطوير وتحسين الحل الحالي في خوارزمية البحث في الحي المتغير عن طريق خوارزمية البحث الداخلي المعروفة:
مرحلة التطوير (Improvement Phase)
وفي السياق ذاته، اختيار مجموعة الأحياء حسب معطيات المشكلة والهدف منها ويرمز إليها عادةً بـ Nk مع ضرورة أن تكون مجموعة محدودة k=1 .. kmax.
من جهة ثانية، إذا كان الحل 𝑥” أفضل من الحل 𝑥، سيتم استبدال الحل الحالي 𝑥 بـ 𝑥” ويتم اعتباره الحل القائم ويتم إعادة عملية البحث من أول حي مجاور k=1.
من جهة ثانية، خوارزمية البحث الداخلي (Local Search Algorithm): والتي تقوم على البحث على حل أفضل في الحي المجاور المعرف مسبقاً للحل الحالي 𝑥 بشكل تدريجي. وما أن يتم ايجاده، سيتم اعتباره الحل القائم وتنتهي عملية البحث باعتبار الحل القائم النهائي هو الحل الأمثل الداخلي بالنسبة لبنية الحي المجاورة لـ 𝑥. توجد استراتيجيتان معروفتان لخوارزمية البحث الداخلي:
- مرحلة تغيير الحي (Neighborhood Change)
- في هذه المرحلة يتم اتخاذ قرارين:
- الأول: أي حي سيتم استكشافه لاحقاً؟
- والثاني: هل سيتم قبول الحل المستخرج من عملية التطوير كحل قائم أم لا؟
كذلك، ويجدر بالذكر هنا، أن في خوارزمية البحث في الحي المتغير الأساسية، يتم استخدام مجموعة الأحياء التي تم تعريفها في عملية التهيئة في مرحلة الاضطراب فقط ولا يتم استخدامها في عملية التطوير، حيث أن في هذه المرحلة يتم استخدام حي مجاور واحد للحل الموجود في مرحلة الاضطراب 𝑥’ ويكون حي مستقل عن الأحياء المعرَفة في المجموعة. ولكن هنالك الكثير من الأشكال لخوارزمية البحث في الحي المتغير التي تم تطويرها، يتيح البعض منها استخدام نفس مجموعة الأحياء المجاورة في المرحلتين؛ الاضطراب والتطوير.
مرحلة الاضطراب (Shaking Phase)
ومن ناحية أخرى، المرحلة الأولى\ الاضطراب: ويتم فيها عشوائياً اختيار حل من أي حي من الأحياء المجاورة التي تم تعريفها مسبقاً في خطوة التهيئة ويرمز عادةً للحل الموجود بـ 𝑥’.
من جانب آخر، إنتاج الحل المبدئي الأول ويرمز إليه بالرمز 𝑥. يمكن إنتاج الحل المبدئي عن طريق اتباع إجراءات جبرية معينة أو يمكن اختياره بطريقة عشوائية. أو يمكن تطبيق القواعد لحل معطى أو محدد من البداية. هنالك الكثير من الدراسات التي توصي باتباع إجراءات مبدئية لإيجاد الحل الأول الذي سيتم استخدامه في الخوارزمية من مبدأ أن تصميم هذه الاجراءات قد يساعد في العثور على الحل الأمثل الداخلي في وقت أقصر وبجودة أفضل؛ إلا أنه لم يتم إثبات ذلك إلى الآن، فبعض الأبحاث أظهرت نتيجة معاكسة؛ حيث تم الوصول إلى الحل الأمثل الداخلي عند اختيار الحل المبدئي بطريقة عشوائية أسرع وبجودة أفضل من الحلول المبنية على إجراءات مبدئية.
وفي السياق ذاته، الخطوة الأساسية: ستتم الخوارزمية في البحث إلى أن تصل إلى شرط إنهاء عملية البحث، والذي يتم اختياره مسبقاً، في كثير من الأحيان يُحدد كالوقت الأقصى الممكن استغراقه لوحدة المعالجة المركزية في البحث، أو عدد المرات التي يتم فيها تكرار عملية البحث. تتكون الخطوة الأساسية من ثلاث مراحل:
تعريف ثوابت جديدة k1 و kstep
من جانب آخر، بهذا التغيير البسيط يُمكن التحكم والسيطرة في عملية تنويع وتكثيف البحث عن طريق اختيار قيمة الثابت بحيث يتناسب مع العملية المختارة. في حالة أن الهدف هو تنويع البحث سيتم اختيار قيم عالية للثوابت، أما في حالة الهدف هو تكثيف البحث فسيتم اختيار قيم منخفضة للثوابت.
ومن ناحية أخرى، نيابة عن بدء عملية الاضطراب في k=1؛ سيتم بدء العملية في k=k1، ونيابةً عن استكمال العملية في الحي المتتالي k:=k+1، سيتم استكماله في k=k1+kstep.
التطبيقات
من جهة ثانية، خوارزمية البحث في الحي المتغير يمكن تطبيقها في الكثير من المجالات وحل مشاكل الاستمثال المعروفة مثل:
- مشاكل التحليل العنقودي
- مشاكل الجدولة
- مشاكل توجيه المركبات
- مشاكل تصميم الشبكات
صياغة خوارزمية البحث في الحي المتغير الأساسية
بعض المتغيرات في خوارزمية البحث في الحي المتغير
علاوةً على ذلك، أو تطبيق عملية البحث الداخلي لجميع الحلول في المجموعة الفرعية ومن ثم اختيار الحل الأمثل من بينها.
وعلى صعيد آخر، عادةً يتم الحصول على الحل في مرحلة الاضطراب بطريقة عشوائية، ولكن يمكن تعديل هذه المرحلة للحصول على الحل الأفضل من بين مجموعة فرعية للحلول من الحي k ويمكن أن يتم ذلك من خلال:
علاوةً على ذلك، توجد الكثير من الإضافات التي يمكن إضافتها لصياغة الخوارزمية والتي من الممكن أن تحسن الحل بشكل أفضل وفي وقت أسرع، نذكر منها اثنين:
من أجل السيطرة على مرحلة تغيير الحي:
ومن جهة أخرى، تطبيق عملية بحث داخلي للحل الأمثل من بين المجموعة الفرعية للحلول.
خوارزمية
استمثال (توضيح)
مشاكل الذكاء الاصطناعي
- المشاكل البيولوجية مثل رصف تسلسل الجينات.
- روابط مهمة
- الأدلة العليا
المقدمة
ومن جهة أخرى، تم تقديم خوارزمية البحث في الحي المتغير بناءً على التصوارات التالية:
ومن جهة أخرى، أما البحث في الحي المتغير هي عملية بحث تتم في أكثر من حي واحد وتؤدي نفس المهمة في تطوير وتحسين الحل المبدئي، مع القدرة للهروب من القاع الذي يحتوي على الحلول المثلى الداخلية بهدف الوصول إلى الحل الأمثل العالمي. عند استخدام أكثر من حي واحد في عملية البحث، يجب أن يتم الإجابة على الأسئلة التالية:
من جانب آخر، الفرق بين خوارزمية البحث الداخلي وخوارزمية البحث في الحي المتغير
وفي هذا السياق، المرحلة الثالثة: تغيير الحي (Neighborhood Change) وتستعمل لتوجيه الخوارزمية لاستكشاف فضاء الحل بشكل أفضل ومنتظم.
علاوةً على ذلك، الإجابة لهذه الأسئلة تعتمد على المشكلة التي يتم العمل على حلها، المعلومات المتوفرة، والهدف الذي يُسعى إليه من أجل حل المشكلة. وإجابة هذه الأسئلة قد تكون من أهم العوامل المساعدة في نجاح تطبيق الخوارزمية.
ومن ناحية أخرى، «الحل الأمثل الداخلي لبنية حي معينة ليس بالضرورة هو الحل الأمثل الداخلي لبنية حي آخر». الفكرة تعود إلى أن كل بنية حي لديها خصائص طوبولجية لعملية البحث الخاصة بها تختلف عن الأحياء الأخرى، لذلك في كل حي سيتم تطبيق عملية البحث بطريقة مختلفة عن الأخرى.
وفي هذا الصدد، خوارزمية البحث الداخلي تقوم بعملية البحث في حي واحد فقط للحل المبدئي بهدف تحسين الحل وتطويره من خلال عدة تغييرات داخلية متسلسلة والتي بدورها ستطور قيمة دالة الهدف إلى أن يتم الوصول إلى الحل الأمثل الداخلي ومن ثم تتوقف العملية.
وعلى صعيد آخر، خوارزمية البحث في الحي المتغير تستكشف الحي البعيد والقريب من الحل الحالي حسب معطيات وأهداف الحل المطلوب وتنتقل من الحل الحالي إلى أحد الأحياء المجاورة في حالة أن الحل في الحي المجاور أفضل من الحل الحالي فقط. تقوم هذه الخوارزمية بالاستكشاف بطريقة منتظمة على ثلاث مراحل:
التصورات خلف تقديم خوارزمية البحث في الحي المتغير
من جهة ثانية، المرحلة الثانية: التطوير (Improvement Phase) وتستعمل لإيجاد حل أفضل من الحل الحالي.
وعلى صعيد آخر، «في كثير من المشاكل، الحلول المثلى الداخلية لحي واحد أو أكثر تكون قريبة من بعضها». وهذا التصور يقترح على التركيز في زيادة استكشاف الحي القريب من الحل الحالي والذي بصورة أخرى يدعم فكرة تكثيف البحث في الحي القريب.
- أي بنية من الأحياء المجاورة سيتم استخدامها؟ وكم حي سيتم استخدامه في الخوارزمية؟
- كيف سيتم ترتيب الأحياء؟
- ما هي الاستراتيجية التي سيتم اعتمادها في عملية التغيير بين الأحياء؟
من جانب آخر، «الحل الأمثل العالمي هو حل أمثل داخلي بالنسبة إلى جميع الأحياء المستعملة في الدراسة». ويتم عكس هذا التصور في الخوارزمية عن طريق استخدام انتقالات معقدة من أجل العثور على الحل الأمثل الداخلي بالنسبة إلى جميع الأحياء وهذا التصور يدعم فكرة التنويع في البحث.
علاوةً على ذلك، المرحلة الأولى: الاضطراب (Shaking Phase) وتستعمل للهروب من القاع الذي يحتوي على الحل الأمثل الداخلي.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟