بحث تابو

يُعدّ البحث المحظور (TS) طريقة بحث فوقية تستخدم أساليب البحث المحلي في التحسين الرياضي . وقد ابتكره فريد دبليو. غلوفر عام 1986 ^{[ 1 ]} وتمّ صياغته رسميًا عام 1989. ^{[ 2 ] [ 3 ]}

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

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

تعتمد خوارزمية البحث المحظور على هياكل ذاكرة تصف الحلول التي تمت زيارتها أو مجموعات القواعد التي يحددها المستخدم. ^{[ 2 ]} إذا تمت زيارة حل محتمل مسبقًا خلال فترة زمنية قصيرة معينة، أو إذا انتهك قاعدة ما، فإنه يُصنف على أنه " محظور" ( tabu ) حتى لا تنظر الخوارزمية في هذا الاحتمال بشكل متكرر.

كلمة "تابو" مشتقة من الكلمة التونغية التي تشير إلى الأشياء التي لا يجوز لمسها لأنها مقدسة. ^{[ 4 ]}

البحث المحظور هو خوارزمية فوقية يمكن استخدامها لحل مشاكل التحسين التوافقي (المشاكل التي يكون فيها الترتيب الأمثل واختيار الخيارات مرغوبًا فيه).

تشمل التطبيقات الحالية للبحث المحظور مجالاتٍ عديدة، منها تخطيط الموارد ، والاتصالات، وتصميم الدوائر المتكاملة واسعة النطاق ، والتحليل المالي، والجدولة، وتخطيط المساحات، وتوزيع الطاقة، والهندسة الجزيئية، والخدمات اللوجستية، وتصنيف الأنماط ، والتصنيع المرن، وإدارة النفايات، واستكشاف المعادن، والتحليل الطبي الحيوي، والحفاظ على البيئة، وغيرها الكثير. في السنوات الأخيرة، نشرت مجلاتٌ في مجالاتٍ متنوعة مقالاتٍ تعليمية ودراساتٍ حسابية توثّق نجاحات البحث المحظور في توسيع نطاق المشكلات التي يمكن معالجتها بفعالية، مما يُسفر عن حلولٍ غالبًا ما تتجاوز جودتها بشكلٍ ملحوظ تلك التي تم الحصول عليها بالطرق المُطبقة سابقًا. يمكن الاطلاع على قائمةٍ شاملةٍ بالتطبيقات، بما في ذلك وصفٌ موجزٌ للمكاسب المُحققة من التطبيقات العملية، في المرجع ^{[ 5 ].}

يستخدم البحث المحظور إجراء بحث محلي أو بحث في الجوار للانتقال بشكل متكرر من حل محتمل واحد${\displaystyle x}$إلى حل محسّن${\displaystyle x'}$في جوار${\displaystyle x}$تستمر عملية البحث المحلي حتى يتم استيفاء معيار إيقاف معين (عادةً ما يكون حدًا لعدد المحاولات أو عتبة معينة للنتيجة). غالبًا ما تتعثر إجراءات البحث المحلي في المناطق ذات النتائج المنخفضة أو المناطق التي تستقر فيها النتائج. لتجنب هذه المشاكل واستكشاف مناطق من فضاء البحث التي قد لا تستكشفها إجراءات البحث المحلي الأخرى، يستكشف البحث المحظور بعناية جوار كل حل أثناء تقدم عملية البحث. الحلول المقبولة في الجوار الجديد،${\displaystyle N^{*}(x)}$يتم تحديدها من خلال استخدام هياكل الذاكرة. وباستخدام هذه الهياكل، يتقدم البحث بالانتقال بشكل متكرر من الحل الحالي.${\displaystyle x}$إلى حل محسّن${\displaystyle x'}$في${\displaystyle N^{*}(x)}$.

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

تشكل هذه البنى الذاكرية ما يُعرف بقائمة المحظورات، وهي مجموعة من القواعد والحلول الممنوعة المستخدمة لتصفية الحلول التي سيتم قبولها في الحي.${\displaystyle N^{*}(x)}$ليتم استكشافها من خلال البحث. في أبسط صورها، قائمة المحظورات هي مجموعة قصيرة المدى من الحلول التي تمت زيارتها في الماضي القريب (أقل من${\displaystyle n}$قبل عدة دورات، حيث${\displaystyle n}$ يمثل عدد الحلول السابقة المراد تخزينها (ويُسمى أيضًا فترة الحظر). في الغالب، تتكون قائمة الحظر من سمات تغيرت نتيجة الانتقال من حل إلى آخر. ولتسهيل الوصف، يُفهم أن "الحل" يُرمز إليه ويُمثل بهذه السمات.

يمكن تقسيم هياكل الذاكرة المستخدمة في البحث المحظور تقريبًا إلى ثلاث فئات: ^{[ 6 ]}

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

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

قد تكفي الذاكرة قصيرة المدى وحدها لتحقيق حلول أفضل من تلك التي تُتوصل إليها طرق البحث المحلي التقليدية، ولكن غالبًا ما تكون البنى متوسطة وطويلة المدى ضرورية لحل المشكلات الأكثر تعقيدًا. ^{[ 7 ]} غالبًا ما يُقارن البحث المحظور بأساليب استكشافية أخرى ، مثل التلدين المحاكي ، والخوارزميات الجينية ، وخوارزميات تحسين مستعمرات النمل ، وتحسين البحث التفاعلي، والبحث المحلي الموجه ، أو البحث التكيفي العشوائي الجشع . بالإضافة إلى ذلك، يُدمج البحث المحظور أحيانًا مع أساليب استكشافية أخرى لإنشاء أساليب هجينة. ينشأ أكثر أنواع البحث المحظور الهجين شيوعًا من دمج البحث المحظور مع البحث المبعثر ، ^{[ 8 ] [ 9 ]} وهو فئة من الإجراءات القائمة على السكان والتي تشترك في جذور مع البحث المحظور، وغالبًا ما تُستخدم في حل مشكلات التحسين غير الخطية الكبيرة.

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

الأفضل ← s0sCurr ← s0أفضل مرشح ← s0tabuList ← []tabuList.push ( s0 )​​بينما ( لا يوجد شرط إيقاف ())sNeighborhood ← getNeighbors ( sCurr )أفضل لياقة للمرشح ← - ∞for ( sCandidate in sNeighborhood )إذا لم تكن قائمة tabuList تحتوي على ( sCandidate )و ( اللياقة ( المرشح ) > أفضل لياقة للمرشح ) )أفضل مرشح ← مرشح ثانويأفضل مرشح للياقة البدنية ← اللياقة البدنية ( أفضل مرشح )نهايةنهايةإذا كانت ( أفضل لياقة للمرشح هي -∞ )استراحة ؛نهايةsCurr ← أفضل مرشحإذا كانت ( أفضل لياقة مرشح > اللياقة ( الأفضل ))الأفضل ← أفضل مرشحنهايةtabuList.push ( bestCandidate )​​إذا كان حجم قائمة التبويبات أكبر من الحد الأقصى لحجم التبويباتtabuList.removeFirst ( )​نهايةنهايةإرجاع الأفضل

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

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

دالة اللياقة هي عادةً دالة رياضية تُرجع قيمةً أو تُحقق معايير الطموح - على سبيل المثال، يمكن اعتبار معيار الطموح هو العثور على فضاء بحث جديد. ^{[ 4 ]} إذا كان أفضل مرشح محلي لديه قيمة لياقة أعلى من أفضل مرشح حالي (السطر 20)، يُعيّن كأفضل مرشح جديد (السطر 21). يُضاف أفضل مرشح محلي دائمًا إلى قائمة المحظورات (السطر 23)، وإذا كانت قائمة المحظورات ممتلئة (السطر 24)، يُسمح لبعض العناصر بالانتهاء (السطر 25). عمومًا، تنتهي صلاحية العناصر من القائمة بنفس ترتيب إضافتها. سيختار الإجراء أفضل مرشح محلي (حتى لو كانت لياقته أسوأ من أفضل مرشح حالي) لتجنب الوصول إلى الحل الأمثل المحلي.

تستمر هذه العملية حتى يتم استيفاء معيار التوقف المحدد من قبل المستخدم، وعند هذه النقطة يتم إرجاع أفضل حل تم رؤيته أثناء عملية البحث (السطر 28).

تُستخدم مسألة البائع المتجول (TSP) أحيانًا لتوضيح فعالية البحث المحظور. ^{[ 7 ]} تطرح هذه المسألة سؤالًا مباشرًا: بالنظر إلى قائمة من المدن، ما هو أقصر مسار يمر بكل مدينة؟ على سبيل المثال، إذا كانت المدينتان  أ و ب  متجاورتين، بينما المدينة  ج أبعد، فإن المسافة الإجمالية المقطوعة ستكون أقصر إذا  تمت زيارة المدينتين أ و ب تباعًا قبل زيارة المدينة  ج. ولأن إيجاد الحل الأمثل يُعدّ مسألة صعبة الحل (NP-hard )، فإن طرق التقريب القائمة على الاستدلال (مثل البحث المحلي) مفيدة في ابتكار حلول قريبة من الحل الأمثل. وللحصول على حلول جيدة لمسألة البائع المتجول، من الضروري استغلال بنية الرسم البياني. وتُعدّ أهمية استغلال بنية المسألة موضوعًا متكررًا في طرق الاستدلال الميتاهوريستية، ويُعدّ البحث المحظور مناسبًا تمامًا لهذا الغرض. وقد مكّنت فئة من الاستراتيجيات المرتبطة بالبحث المحظور، والتي تُسمى طرق سلسلة الطرد، من الحصول على حلول عالية الجودة لمسألة البائع المتجول بكفاءة. ^{[ 10 ]}

من جهة أخرى، يمكن استخدام بحث تابو بسيط لإيجاد حل مُرضٍ لمسألة البائع المتجول (أي حل يُلبي معيار الكفاءة، وإن لم يكن بالجودة العالية التي يُمكن الحصول عليها باستغلال بنية الرسم البياني). يبدأ البحث بحل أولي، يُمكن توليده عشوائيًا أو وفقًا لخوارزمية الجوار الأقرب . لإنشاء حلول جديدة، يتم تبديل ترتيب زيارة مدينتين في حل مُحتمل. تُستخدم المسافة الإجمالية للتنقل بين جميع المدن لتقييم مدى مثالية حل مُعين مُقارنةً بآخر. ولمنع التكرار - أي زيارة مجموعة مُعينة من الحلول بشكل مُتكرر - وتجنب الوقوع في الحلول المُثلى المحلية ، يُضاف الحل إلى قائمة التابو إذا تم قبوله في جوار الحل.${\displaystyle N^{*}(x)}$.

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

• عرض مرئي لخوارزمية البحث المحظور (تطبيق صغير)
• المؤتمر الدولي للأساليب الاستدلالية الميتاهوريستية (MIC 2011) – أوديني
• أرشيف مجتمع البحث التفاعلي ، بتاريخ 2 يونيو 2010، على موقع Wayback Machine.
• مؤتمر LION حول تقنيات التعلم والتحسين الذكي، مؤرشف بتاريخ 8 نوفمبر 2010 على موقع Wayback Machine.