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

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

المقدمة

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

1. المرحلة الأولى: الاضطراب (Shaking Phase) وتستخدم للهروب من القاع الذي يحتوي على الحل الأمثل الداخلي.
2. المرحلة الثانية: التطوير (Improvement Phase) وتستخدم لإيجاد حل أفضل من الحل الحالي.
3. المرحلة الثالثة: تغيير الحي (Neighborhood Change) وتستخدم لتوجيه الخوارزمية لاستكشاف فضاء الحل بشكل أفضل ومنتظم.

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

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

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

1. أي بنية من الأحياء المجاورة سيتم استخدامها؟ وكم حي سيتم استخدامه في الخوارزمية؟
2. كيف سيتم ترتيب الأحياء؟
3. ما هي الاستراتيجية التي سيتم اعتمادها في عملية التغيير بين الأحياء؟

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

التصورات خلف تقديم خوارزمية البحث في الحي المتغير

تم تقديم خوارزمية البحث في الحي المتغير بناءً على التصوارات التالية:

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

الهيكل العام

الهيكل العام لخوارزمية لبحث في الحي المتغير يتكون من خطوتين: التهيئة والخطوة الأساسية:

• التهيئة: وهي الخطوة الأولى يتم فيها:

1. اختيار مجموعة الأحياء حسب معطيات المشكلة والهدف منها ويرمز إليها عادةً بـ N_k مع ضرورة أن تكون مجموعة محدودة k=1 .. k_max.
2. إنتاج الحل المبدئي الأول ويرمز إليه بالرمز 𝑥. يمكن إنتاج الحل المبدئي عن طريق اتباع إجراءات جبرية معينة أو يمكن اختياره بطريقة عشوائية. أو يمكن تطبيق القواعد لحل معطى أو محدد من البداية. هنالك الكثير من الدراسات التي توصي باتباع إجراءات مبدئية لإيجاد الحل الأول الذي سيتم استخدامه في الخوارزمية من مبدأ أن تصميم هذه الاجراءات قد يساعد في العثور على الحل الأمثل الداخلي في وقت أقصر وبجودة أفضل؛ إلا أنه لم يتم إثبات ذلك إلى الآن، فبعض الأبحاث أظهرت نتيجة معاكسة؛ حيث تم الوصول إلى الحل الأمثل الداخلي عند اختيار الحل المبدئي بطريقة عشوائية أسرع وبجودة أفضل من الحلول المبنية على إجراءات مبدئية.

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

1. المرحلة الأولى\ الاضطراب: ويتم فيها عشوائياً اختيار حل من أي حي من الأحياء المجاورة التي تم تعريفها مسبقاً في خطوة التهيئة ويرمز عادةً للحل الموجود بـ 𝑥’.
2. المرحلة الثانية\ التطوير: يعتبر الحل الموجود من مرحلة الاضطراب هو نقطة البداية لإجراء عملية البحث الداخلي ويتم فيها استخراج حل أفضل ويرمز له بـ 𝑥”.
3. المرحلة الثالثة\ تغيير الحي: يتم فيها مقارنة الحل الموجود في المرحلة السابقة 𝑥” بالحل الحالي 𝑥:

• إذا كان الحل 𝑥” أفضل من الحل 𝑥، سيتم استبدال الحل الحالي 𝑥 بـ 𝑥” ويتم اعتباره الحل القائم ويتم إعادة عملية البحث من أول حي مجاور k=1.
• إذا كان الحل 𝑥 أفضل من الحل 𝑥”، يستكمل البحث في الحي الذي يليه في الترتيب وسيتم بدء عملية اضطراب جديدة.

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

مرحلة الاضطراب (Shaking Phase)

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

مرحلة الاضطراب

𝑥’= يتم الاختيار عشوائياً من مجموعة الأحياء (𝑥’ ∈ Nk (𝑥

مرحلة التطوير (Improvement Phase)

تتم عملية تطوير وتحسين الحل الحالي في خوارزمية البحث في الحي المتغير عن طريق خوارزمية البحث الداخلي المعروفة:

•  خوارزمية البحث الداخلي (Local Search Algorithm): والتي تقوم على البحث على حل أفضل في الحي المجاور المعرف مسبقاً للحل الحالي 𝑥 بشكل تدريجي. وما أن يتم ايجاده، سيتم اعتباره الحل القائم وتنتهي عملية البحث باعتبار الحل القائم النهائي هو الحل الأمثل الداخلي بالنسبة لبنية الحي المجاورة لـ 𝑥. توجد استراتيجيتان معروفتان لخوارزمية البحث الداخلي:

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

• خوارزمية الهبوط في الحي المجاور (The Variable Neighborhood Descent): وهي نوع من أنواع البحث في الحي المتغير وتستغل حقيقة أن احتمالية أن يكون الحل الأمثل الداخلي بالنسبة لجميع الأحياء المستخدمة هو حل أمثل عالمي، أكبر من احتمالية الحل الأمثل الداخلي الموجود بالنسبة لحي واحد فقط. وتقوم هذه الخوارزمية في البحث في جميع الأحياء المعرَفة بطريقة متتالية أو متداخلة على عكس عملية البحث الداخلي التي يتم تطبيقها لحي واحد فقط. ويمكن أن تستخدم واحدة من استراتيجيات البحث الداخلي سواء التطور الأول أو التطور الأفضل.

مرحلة تغيير الحي (Neighborhood Change)

في هذه المرحلة يتم اتخاذ قرارين:

1. الأول: أي حي سيتم استكشافه لاحقاً؟
2.  والثاني: هل سيتم قبول الحل المستخرج من عملية التطوير كحل قائم أم لا؟

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

• التغيير المتتالي للحي: عندما يتم العثور على حل قائم قادر على تحسين الحل الحالي، سيتم استئناف عملية البحث في أول حي من جديد بالنسبة للترتيب المعرف للأحياء في المجموعة الخاصة بالحل القائم الجديد. أما في حالة لم يتم العثور على حل يُحسن الحل الحالي، البحث يُستكمل في الحي التالي.

التغيير المتتالي للحي

إذا كانت (f(𝑥”) < f(𝑥 𝑥 = 𝑥’, k = 1 غير ذلك؛k=k+1

• التغيير الحلقي للحي: يتم استكمال البحث في الحي التالي سواء تم ايجاد حل أفضل أم لا.

التغيير الحلقي للحي

لكل k=k+1 إذا كانت (f(𝑥”) < f(𝑥 إذاً 𝑥 = 𝑥”

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

التغيير الأنبوبي للحي

إذا كانت (f(𝑥”) < f(𝑥 إذاً: 𝑥 = 𝑥’ غير ذلك: k=k+1

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

التغيير المنحرف للحي

إذا كانت (If f(𝑥”) - f(𝑥) < α(𝑥”, 𝑥 إذاً: 𝑥 = 𝑥’ k = 1 غير ذلك: k=k+1

أشكال خوارزمية البحث في الحي المتغير

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

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

صياغة خوارزمية البحث في الحي المتغير الأساسية

الخطوة 0: التهيئة	اختر بنية الأحياء المجارة Nk, k=1 .. kmax اختر الحل المبدئي الأول 𝑥
الخطوة 1: إنهاء الخوارزمية	إذا كان t > tma𝑥  ، أوقف الخوارزمية. الحل القائم هو الحل الأمثل التقريبي
الخطوة 2: الخطوة الأساسية	كرر التسلسل التالي إلى أن لا يمكن العثور على حل يحسَن الحل القائم اضبط k= 1 أعد التسلسل التالي حتى k= kmax
	الاضطراب: اختر 𝑥’ = عشوائياً من (Nk (𝑥
	البحث الداخلي: اختر بنية حي مجاور للحل الحالي كرر 𝑥’ = 𝑥 أبحث عن 𝑥’ الأفضل في الحي   إذا كانت (f (𝑥”) ≤ f (𝑥’ أرجع 𝑥”
	تغيير الحي: إذا كانت (f(𝑥”) ≤ f(𝑥 أذاً 𝑥 = 𝑥” k = 1 غير ذلك: k=k+1

بعض المتغيرات في خوارزمية البحث في الحي المتغير

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

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

1. تطبيق عملية بحث داخلي للحل الأمثل من بين المجموعة الفرعية للحلول.
2. أو تطبيق عملية البحث الداخلي لجميع الحلول في المجموعة الفرعية ومن ثم اختيار الحل الأمثل من بينها.

• من أجل السيطرة على مرحلة تغيير الحي:

1. تعريف ثوابت جديدة k₁ و k_step
2.  نيابة عن بدء عملية الاضطراب في k=1؛ سيتم بدء العملية في k=k₁، ونيابةً عن استكمال العملية في الحي المتتالي k:=k+1، سيتم استكماله في k=k₁+k_step.

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

التطبيقات

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

1. مشاكل التحليل العنقودي
2. مشاكل الجدولة
3. مشاكل توجيه المركبات
4. مشاكل تصميم الشبكات
5. مشاكل الذكاء الاصطناعي
6. المشاكل البيولوجية مثل رصف تسلسل الجينات.

روابط مهمة

الأدلة العليا

خوارزمية

استمثال (توضيح)