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

الموجز

خوارزميات البحث المحلي تمثل إحدى تقنيات التحسين (optimization problems) التي تعتمد على تحسين حل واحد تدريجيًا من خلال إجراء تعديلات متكررة على الحل داخل فضاء البحث.

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

وقد طُبِّقت هذه الخوارزميات على مجموعة واسعة من المشكلات، منها الجدولة (scheduling)، وتخصيص الموارد (resource allocation)، والخدمات اللوجستية (logistics)، وحتى التعلم الآلي (machine learning).

البحث المحلي في مقابل البحث الشامل

تعد خوارزميات البحث المحلي إحدى تقنيات التحسين الأساسية المستخدمة لحل مشكلات التحسين الصعبة حسابيًا، إذ تركز على استكشاف جوار حل معين، بهدف اختيار الحلول الأعلى جودة {{الحل الأمثل: أفضل حل ممكن في فضاء البحث وفقًا لدالة الهدف، بحيث يحقق أعلى قيمة في مسائل التعظيم أو أدنى قيمة في مسائل التصغير مقارنة بجميع الحلول الأخرى الممكنة.}} من بين مجموعة من الحلول المرشحة[1]، بخلاف خوارزميات البحث الدقيقة أو الشاملة (exact search methods) التي تستكشف جميع الحلول الممكنة في فضاء البحث، ما يؤدي إلى تكلفة حسابية مرتفعة، خاصة في المشكلات ذات الأبعاد الكبيرة.

تُستخدم خوارزميات البحث المحلي بكفاءة في معالجة طيف واسع من مشكلات التحسين عبر مجالات متعددة، مثل الجدولة، وتخصيص الموارد، والخدمات اللوجستية، والتعلم الآلي[2].

تبدأ خوارزميات البحث المحلي بحل أولي، ثم تنتقل إلى حل أجود عبر خطوات بسيطة غير مكلفة، وهكذا تتكرر هذه العملية وصولًا إلى حل أمثل[3]. في كل خطوة، يُقيَّم الحل الجديد باستخدام دالة هدف (objective function) خاصة بمشكلة التحسين[4]، فإذا أظهر الحل الجديد تحسنًا، يُنتقَل إليه، وتستمر هذه الدورة وصولًا إلى حل أمثل أو تحقق شرط توقف[5]، مثل بلوغ قيد زمني أو بلوغ حد معين من عدد تقييمات الحلول المستكشَفة[6]. يوضح [الشكل 1] مبدأ عمل خوارزميات البحث المحلي.

حذف الصورة؟

سيؤدي هذا إلى نقل الصورة إلى سلة المهملات.

حذف إلغاء

تتفوق خوارزميات البحث المحلي في إيجاد حلول للمشكلات تكون ذات فضاء بحث كبير، وذلك من خلال تركيزها على استكشاف المناطق الواعدة، ما يتيح لها الوصول إلى حل أمثل أو شبه أمثل بسرعة أكبر مقارنة بخوارزميات البحث الدقيقة[7]. ويشمل فضاء البحث الخاص بمشكلة التحسين جميعَ الحلول الممكنة، إذ يمكن تمثيل كل حل بنقطة ضمن فضاء البحث. وتسمى مجموعة الحلول الواقعة ضمن نطاق محدود في فضاء البحث بـ "الحي" (neighborhood). وتعتمد خوارزميات البحث المحلي على إيجاد أفضل حلٍّ ضمن الحيّ الحالي، ثم الانتقال إلى حي جديد عبر إجراء تعديلات صغيرة على الحلِّ الحالي، مع إعادة تقييم جودة الحل باستخدام دالة الهدف[8]، التي تعمل بمنزلة بوصلة توجِّه تلك الخوارزميات نحو الحلول الأفضل، إذ تُسنِد قيمةً لكل حل فتعبّر عن مدى جودته في سياق المشكلة[9].

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

مفاهيم عامة

آلية العمل

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

الحي

حذف الصورة؟

سيؤدي هذا إلى نقل الصورة إلى سلة المهملات.

حذف إلغاء

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

الأمثل محليًا والأمثل كليًا

يقسم فضاء البحث في مشكلات التحسين عدة مناطق من الحي، ويُعد الحل الذي يتفوق على جميع جيرانه ضمن الحي الواحد هو الحل الأمثل محليًا (local optimum). أما إذا كان الحل هو الأفضل بين جميع الحلول في فضاء البحث، فيُسمّى الحل الأمثل كليًا (global optimum) [الشكل 2][14]. وتهدف خوارزميات التحسين إلى الوصول إلى الحل الأمثل كليًا على مستوى فضاء البحث، وقد تستخدم استراتيجيات متعددة لتجنّب الوقوع في فخ الحل الأمثل محليًا، إذ قد تعجز الخوارزمية عن الانتقال إلى مناطق أخرى من فضاء البحث، وتظل محصورة ضمن حيِّ أحد الحلول المثلى محليًا.

أشهر أنواعها

يمكن تصنيف خوارزميات البحث المحلي وفق استراتيجياتها في استكشاف الحي وآلياتها في الهروب من فخ الحل الأمثل المحلي. ومن أبرز هذه الخوارزميات: تسلّق التل (hill climbing)، ومحاكاة الصلب (simulated annealing)، ومحاكاة الطوفان العظيم (great deluge)، وبحث التابو (tabu search)، والبحث المحلي المتكرر (iterated local search). وتتميّز كل خوارزمية بنهجٍ خاص في استكشاف فضاء البحث والتعامل مع الحلول المثلى المحلية.

خوارزمية تسلق التل

تحاكي خوارزمية تسلق التل عمليةَ الصعود التدريجي للتل نحو القمة، ولا تتطلب معرفة مسبقة بشدة التدرج أو اتجاهه، إذ تُولِّد حلولًا جديدة ضمن الحي الحالي وتختبرها بشكل متكرر، مع اعتماد الحل الجديد إذا كان أفضل من الحل الحالي. وتستمر هذه العملية حتى يتعذّر تحقيق أي تحسين إضافي، ما يدل على الوصول إلى حل أمثل محلي[15]. وتوضح [الخوارزمية 1] الصيغةَ العامة لآلية العمل، فكما يتضح منها، تعتمد خوارزمية تسلق التل على إجراء تعديلات بسيطة، غالبًا عشوائية، على نسخةٍ من الحل الحالي (ح’)، بهدف توليد حلول جديدة. وقد تؤدي هذه التعديلات إلى حلول أفضل أو أسوأ. ومع تكرار العملية، يُحتَفظ دائمًا بالحلول الأفضل، ما يقود في النهاية إلى حل أمثل محلي.

[الخوارزمية 1] - الصيغة العامة لآلية عمل خوارزمية تسلق التل

خوارزمية محاكاة الصلب

تُعد خوارزمية محاكاة الصلب، التي طُوِّرت في منتصف ثمانينيات القرن العشرين، من أبرز خوارزميات التحسين المستخدمة لإيجاد حلول لمشكلات معقدة. وتستوحي فكرتها من عملية التلدين في علم المعادن، إذ تُسخن المادة ثم تُبرَّد تدريجيًا للوصول إلى حالة أكثر استقرارًا وأقل طاقة[16]. وتختلف عن خوارزمية تسلق التل في آلية قبول الحلول الجديدة، إذ تستبدل بالحل الحالي (ح) الحلَّ الجديد (ح’) إذا كان أفضل كما في تسلق التل. أما إذا كان الحلُّ الجديد أسوأ، فقد يُقبَل إذا وُلِّدَتْ قيمة عشوائية أصغر من مقدار التغير في الطاقة (Δط) الذي يُحسَب وفق المعادلة (1):

\[\Delta ط=e^{\frac{\text{جودة الحل }(ح')-\text{جودة الحل }(ح)}{م}}\]

حيث تمثل ( \(e\)) العدد النيبيري، وقيمته 2.71828 تقريبًا، وتمثل (م) مُعامِل الحرارة (قيمة أكبر من صفر). تسمح هذه الآلية بقبول بعض الحلول الأسوأ، بهدف تجنّب الوقوع في فخ الحل الأمثل المحلي، عبر محاكاة عملية النزول عن التل بهدف استكشاف طريق جديدة تؤدي إلى تلة أخرى.

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

[الخوارزمية 2] - صيغة عامة لخوارزمية محاكاة الصلب

محاكاة الطوفان العظيم

حذف الصورة؟

سيؤدي هذا إلى نقل الصورة إلى سلة المهملات.

حذف إلغاء

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

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

[الخوارزمية 3] - الآلية العامة لعمل خوارزمية الطوفان العظيم

بحث التابو

اقتُرحت خوارزمية بحث التابو عام 1986، وتتميز باستخدام الذاكرة لتخزين معلومات متعلقة بعملية البحث. وقد استُخدمت هذه الخوارزمية في كثير من تطبيقات التحسين، لا سيما في المسائل التوافقية (combinatorial problems). تتبع هذه الخوارزمية المبدأ العام للبحث المحلي، إذ يُستبدَل بالحل الحالي حلٌّ مجاور أفضل عند العثور عليه. وعندما تكون جميعُ الحلول المجاورة أقلَّ جودة، يمكن للخوارزمية قبول حل أسوأ، بهدف تجنب الوقوع في فخ الحل الأمثل المحلي، إذ يتم اختيار أفضل حل متاح ضمن الحي، حتى وإن لم يكن أفضل من الحل الحالي، لضمان استمرار عملية البحث، ويُعتمد هذا الحل حلًّا حاليًّا جديدًا. قد تؤدي إعادة زيارة الحلول السابقة إلى توليد دورات تكرارية، ولذلك تُستخدم قائمة التابو (tabu list) لمنع إعادة زيارة بعض الحلول مؤقتًا[18].

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

إلى جانب التحديات العامة في تصميم خوارزميات البحث المحلي، مثل تعريف الحي وتوليد الحل الأولي، تُعد كيفية إدارة قائمة التابو من أبرز التحديات في تصميم هذه الخوارزمية، إذ تهدف إلى منع إعادة زيارة الحلول خلال فترة زمنية محددة. ومن الجوانب المعقدة في تصميم الخوارزمية أيضًا عمليةُ تحديد معايير السماح بتجاوز قيود التابو (aspiration criteria) لتجنب الوقوع في فخ الحل الأمثل محليًا. وتوضح [الخوارزمية 4] الصيغة العامة لآلية عمل بحث التابو.

[الخوارزمية 4] - صيغة عامة لخوارزمية بحث التابو

البحث المحلي المتكرر

تعد خوارزمية البحث المحلي المتكرر امتدادًا لخوارزمية تسلق التل، مع إضافة آلية إعادة التشغيل (restart mechanism). ففي خوارزمية تسلق التل قد تتوقف عملية البحث عند حل أمثل محلي، لذلك تُستخدم آلية إعادة التشغيل للانتقال إلى نقطة جديدة في فضاء البحث، ثم إعادة تطبيق البحث المحلي للوصول إلى حل أفضل[19]. وفي نهاية التنفيذ، يتم إرجاع أفضل حل تم التوصل إليه. وتهدف عملية إعادة التشغيل إلى تجنب الوقوع في فخ الحل الأمثل المحلي.

يمكن تلخيص آلية عمل الخوارزمية بالخطوات التالية: يُطبَّق البحث المحلي (مثل تسلق التل) لفترة محددة، وبعد انتهاء هذه الفترة، تقرر الخوارزمية إما البقاء في المنطقة الحالية نفسها أو الانتقال إلى منطقة جديدة وإعادة عملية البحث فيها.

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

[الخوارزمية 5] - الصيغة العامة لخوارزمية البحث المحلي المتكرر

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

المراجع

Burke, Edmund K. & Yuri Bykov. “The Late Acceptance Hill-Climbing Heuristic.” European Journal of Operational Research. vol. 258, no. 1 (2017). pp. 70-78.

Cagnoni, Stefano et al. (eds.). “Combinations of Local Search and Exact Algorithms.” Applications of Evolutionary Computing. Berlin: Springer, 2003.

Daumé III, Hal &Aarti Singh. Proceedings of the 37th International Conference on Machine Learning. PMLR, 2020.

Dueck, Gunter. “New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel.” Journal of Computational Physics. vol. 104, no. 1 (January 1993). pp. 86-92.

Gendreau, Michel & Jean-Yves Potvin (eds.). Handbook of Metaheuristics, 3rd ed. Cham: Springer, 2019.

Johnson, David S., Christos H. Papadimitriou & Mihalis Yannakakis. “How Easy Is Local Search?.” Journal of Computer and System Sciences. vol. 37, no. 1 (1988). pp. 79-100.

Prajapati, Vishnu Kumar, Mayank Jain, & Lokesh Chouhan. “Tabu Search Algorithm (TSA) A Comprehensive Survey.” A paper presented at the 3^rd International Conference on Emerging Technologies in Computer Engineering: Machine Learning and Internet of Things (ICETCE-2020). IEEE. Jaipur, India. 7-8 February 2020.

Sangaiah, Arun Kumar, Min Sheng & Zhikui Zhang (eds.). Computational Intelligence for Multimedia Big Data on the Cloud with Engineering Applications. New York: Academic Press, 2018.

Voß, Stefan et al. (eds.). Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization. Berlin: Springer, 1998.

[1] Irina Dumitrescu & Thomas Stützle, “Combinations of Local Search and Exact Algorithms,” in: Stefano Cagnoni et al. (eds.), Applications of Evolutionary Computing, vol. 2611 (Berlin: Springer, 2003).

[2] Stefan Voß et al. (eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization (Berlin: Springer, 1998).

[3] David S. Johnson, Christos H. Papadimitriou & Mihalis Yannakakis, “How Easy Is Local Search?,” Journal of Computer and System Sciences, vol. 37, no. 1 (1988), pp. 79-100.

[4] Dumitrescu & Stützle, op. cit.

[5] Johnson, Papadimitriou & Yannakakis, op. cit.

[6] Voß et al., op. cit.

[7] Ibid.

[8] Johnson, Papadimitriou & Yannakakis, op. cit.

[9] Mohamed Abdel-Basset, Laila Abdel-Fatah & Arun Kumar Sangaiah, “Metaheuristic Algorithms: A Comprehensive Review,” in: Arun Kumar Sangaiah, Min Sheng & Zhikui Zhang (eds.), Computational Intelligence for Multimedia Big Data on the Cloud with Engineering Applications (New York: Academic Press, 2018). pp. 185-231.

[10] Chi Jin, Praneeth Netrapalli & Michael I. Jordan, “What Is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?,” in: Hal Daumé III & Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, vol. 119 (PMLR, 2020), pp. 4880-4889.

[11] Helena R. Lourenço, Olivier C. Martin & Thomas Stützle, “Iterated Local Search: Framework and Applications,” in: Michel Gendreau & Jean-Yves Potvin (eds.), Handbook of Metaheuristics, 3^rd ed. (Cham: Springer, 2019).

[12] Voß et al., op. cit.

[13] Dumitrescu & Stützle, op. cit.

[14] Jin, Netrapalli & Jordan, op. cit.

[15] Edmund K. Burke & Yuri Bykov, “The Late Acceptance Hill-Climbing Heuristic,” European Journal of Operational Research, vol. 258, no. 1 (2017), pp. 70-78.

[16] Daniel Delahaye, Supatcha Chaimatanan & Marcel Mongeau, “Simulated Annealing: From Basics to Applications,” in: Michel Gendreau & Jean-Yves Potvin (eds.), Handbook of Metaheuristics, 3^rd ed. (Cham: Springer, 2019), pp. 1-35.

[17] Gunter Dueck, “New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel,” Journal of Computational Physics, vol. 104, no. 1 (January 1993), pp. 86-92.

[18] Vishnu Kumar Prajapati, Mayank Jain, & Lokesh Chouhan, “Tabu Search Algorithm (TSA) A Comprehensive Survey,” a paper presented at the 3^rd International Conference on Emerging Technologies in Computer Engineering: Machine Learning and Internet of Things (ICETCE-2020), IEEE, Jaipur, India, 7-8 February 2020.

[19] Lourenço, Martin & Stützle, op. cit.