books variable neighborhood search algorithm
If you do not find what you're looking for, you can use more accurate words.
خوارزمية البحث في الحي المتغير (Info)
البحث في الحي المتغير هي خوارزمية تنحدر من ضمن فئة خوارزميات الأدلة العليا والتي تهدف لإيجاد وابتكار طرق بحث نحصل من خلالها على حلول لمشاكل ذي حجم عالي أو معلوماتها المتوفرة غير كافية أو غير مكتملة في وقت قصير وبجودة جيدة إلا أنها لا تضمن مثالية الحل الموجود. البحث في الحي المتغير تقوم بعملية بحث داخلي محسنة ومطورة حيث يتم استكشاف بنية الفضاء البحثي الممكن لهدف إيجاد حل أفضل من الحل الحالي والهروب من القاع الذي يحتويها عن طريق تغيير الحي القريب من الحل الحالي بالتناوب من ضمن مجموعة أحياء معرفة مسبقا. عامةً ليس من الصعب العثور على الحل الأمثل الداخلي لأي مشكلة في الخوارزميات ولكن من الصعب العثور على الحل الأمثل العالمي الأمثل وذلك لأن الكثير من الخوارزميات مثل خوارزمية البحث الداخلي تعلق وتتم محاصرة في القاع الذي يحتوي على الحل الأمثل الداخلي ومن ثم لن يمكنها الوصول الحل الأمثل العالمي. لذلك تم تقديم هذه الخوارزمية من قبل ملادينوفيتش وهانسن في عام 1997م بهدف التغلب على مصيدة الحل الأمثل الداخلي. مبدئياً تم تصميم هذه الخوارزمية لحل مشاكل التقليص ولكن يمكن تحويلها واستخدامها بسهولة في مشاكل التعظيم.
المقدمة
خوارزمية البحث في الحي المتغير تستكشف الحي البعيد والقريب من الحل الحالي حسب معطيات وأهداف الحل المطلوب وتنتقل من الحل الحالي إلى أحد الأحياء المجاورة في حالة أن الحل في الحي المجاور أفضل من الحل الحالي فقط. تقوم هذه الخوارزمية بالاستكشاف بطريقة منتظمة على ثلاث مراحل:
- المرحلة الأولى: الاضطراب (Shaking Phase) وتستخدم للهروب من القاع الذي يحتوي على الحل الأمثل الداخلي.
- المرحلة الثانية: التطوير (Improvement Phase) وتستخدم لإيجاد حل أفضل من الحل الحالي.
- المرحلة الثالثة: تغيير الحي (Neighborhood Change) وتستخدم لتوجيه الخوارزمية لاستكشاف فضاء الحل بشكل أفضل ومنتظم.
الفرق بين خوارزمية البحث الداخلي وخوارزمية البحث في الحي المتغير
خوارزمية البحث الداخلي تقوم بعملية البحث في حي واحد فقط للحل المبدئي بهدف تحسين الحل وتطويره من خلال عدة تغييرات داخلية متسلسلة والتي بدورها ستطور قيمة دالة الهدف إلى أن يتم الوصول إلى الحل الأمثل الداخلي ومن ثم تتوقف العملية.
أما البحث في الحي المتغير هي عملية بحث تتم في أكثر من حي واحد وتؤدي نفس المهمة في تطوير وتحسين الحل المبدئي، مع القدرة للهروب من القاع الذي يحتوي على الحلول المثلى الداخلية بهدف الوصول إلى الحل الأمثل العالمي. عند استخدام أكثر من حي واحد في عملية البحث، يجب أن يتم الإجابة على الأسئلة التالية:
- أي بنية من الأحياء المجاورة سيتم استخدامها؟ وكم حي سيتم استخدامه في الخوارزمية؟
- كيف سيتم ترتيب الأحياء؟
- ما هي الاستراتيجية التي سيتم اعتمادها في عملية التغيير بين الأحياء؟
الإجابة لهذه الأسئلة تعتمد على المشكلة التي يتم العمل على حلها، المعلومات المتوفرة، والهدف الذي يُسعى إليه من أجل حل المشكلة. وإجابة هذه الأسئلة قد تكون من أهم العوامل المساعدة في نجاح تطبيق الخوارزمية.
التصورات خلف تقديم خوارزمية البحث في الحي المتغير
تم تقديم خوارزمية البحث في الحي المتغير بناءً على التصوارات التالية:
- "الحل الأمثل الداخلي لبنية حي معينة ليس بالضرورة هو الحل الأمثل الداخلي لبنية حي آخر". الفكرة تعود إلى أن كل بنية حي لديها خصائص طوبولجية لعملية البحث الخاصة بها تختلف عن الأحياء الأخرى، لذلك في كل حي سيتم تطبيق عملية البحث بطريقة مختلفة عن الأخرى.
- "الحل الأمثل العالمي هو حل أمثل داخلي بالنسبة إلى جميع الأحياء المستخدمة في الدراسة". ويتم عكس هذا التصور في الخوارزمية عن طريق استخدام انتقالات معقدة من أجل العثور على الحل الأمثل الداخلي بالنسبة إلى جميع الأحياء وهذا التصور يدعم فكرة التنويع في البحث.
- "في كثير من المشاكل، الحلول المثلى الداخلية لحي واحد أو أكثر تكون قريبة من بعضها". وهذا التصور يقترح على التركيز في زيادة استكشاف الحي القريب من الحل الحالي والذي بصورة أخرى يدعم فكرة تكثيف البحث في الحي القريب.
الهيكل العام
الهيكل العام لخوارزمية لبحث في الحي المتغير يتكون من خطوتين: التهيئة و الخطوة الأساسية:
- التهيئة: وهي الخطوة الأولى يتم فيها:
- اختيار مجموعة الأحياء حسب معطيات المشكلة والهدف منها ويرمز إليها عادةً بـ Nk مع ضرورة أن تكون مجموعة محدودة k=1 .. kmax.
- إنتاج الحل المبدئي الأول ويرمز إليه بالرمز
