Archive for category Tabu Search Algorithm

شرح خوارزمية Tabu Search Algorithm

facebook-groupالسلام عليكم ورحمة الله وبركاته

نعود اليكم مع خوارزمية جديدة تتحدث عن احد طرائق البحث الذكية, وتدعى
Tabu Search Algorithm

في البداية سنشرح مصدر اسم الخوارزمية ومعناه

Tabu: تأتي بمعنى محظور, ممنوع او محرم, وسنلاحظ اثناء شرح الخوارزمية بأن هنالك قائمة توضع فيها مجموعة الحلول التي لا يتوجب العودة واستخدمها مرة ثانية, تدعى هذه القائمة باسم “Tabu List”  اي القائمة المحظورة. ومن هنا جاء اسم الخوارزمية Tabu Search Alorithm.

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

في البداية سنبدأ بتعريف هذه الخوارزمية:

خوارزمية البحث تابو  Tabu Search Algorithm

تندرج خوارزمية البحث تابوTabu Search algorithm  تحت تصنيف الخوارزميات العشوائية Stochastic Algorithms.

عبارة عن احد طرائق البحث التجريبية, والتي تستخدم طرائق البحث المحلي local search methods من اجل ايجاد حلول لمسائل الامثلة الرياضية mathematical optimization.

في البداية دعونا نعرف ب طرائق البحث المحلي local search methods لنستطيع بعدها ان نفهم ماذا اضافت خوارزمية البحث تابو لها.

طرائق البحث المحلي – في الجوار local (neighborhood) search:

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

لكن للاسف فإن طرائق البحث المحلية عرضة لان تعلق ضمن مناطق امثلية محلية local optimality ضمن فضاء الحل, او عند هضبات من فضاء الحل, حيث تكون كافة الحلول المتواجدة هنالك متشابهه.

هنا يأتي دور خوارزمية البحث تابوTabu search algorithm  , حيث انها تقوم على تحسين اداء طرائق البحث المحلي local search methods عبر تخفيف الشروط الاساسية لطرائق البحث المحلية.
في البداية, تقبل الخوارزمية التحرك والانتقال الى حل اسوء في حال لم يتواجد اي حل افضل ضمن الجوار الحالي ( وهي تمثل الحالة عندما يعلق البحث عند نهاية محلية صغرى local minimum ).
بالاضافة الى ذلك, يتم اضافة هذه الخطوة والحركة الى قائمة الحظر- ومن هنا جاء اسم الخوارزمية Tabu اي محظور وممنوع – بحيث تمنع عملية البحث من العودة الى نفس الحلول التي تمت زيارتها سابقا.

عملية تنفيذ خوارزمية البحث تابو يتطلب استخدام بنى للذاكرة memory structures التي تخزن توصيف للحلول التي تمت زيارتها سابقا, او مجموع من القواعد المزودة من قبل المستخدمين.
إذا كان هنالك حل محتمل قد تمت زيارته سابقا خلال فترة زمنية قصيرة, او في حال انتهك هذا الحل احد القواعد, عندها يتم وضع علامة على هذا الحل على انه “محضور” “Tabu-Forbidden”, وبالتالي فإن الخوارزمية لن تعود الى هذا الحل مجددا.

تطبيقات خوارزمية البحث تابوا Tabu search algorithm

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

  • توسيع حدود المشاكل التي يمكن للخوارزمية التعامل معها على نحو فعال
  • بالاضافة الى جودة الحلول التي انتجتها هذه الخوارزمية حيث انها في كثير من الاحيان فاقت من حيث الجودة تلك الحلول التي تم الحصول عليها من قبل الطرق التي طبقت سابقا

حيث تنوع مجال تطبيقات الخورازمية بشكل كبير, سنذكر فيما يلي على سبيل الذكر لا الحصر بعض تطبيقات الخوارزمية:

  • مجال تخطيط الموارد resource planning
  • مجال الاتصالات telecommunications
  • التحليل المالي financial analysis
  • مسائل الجدولة scheduling
  • Space planning
  • توزيع الطاقة energy distribution
  • الهندسة الجزيئية molecular engineering
  • الخدمات اللوجستية مخلهسفهؤس
  • تصنيف النماذج pattern classification
  • الحفاظ على البيئة environmental conservation

التوصيف الاساسي للخوارزمية Basic Description

كما وضحنا سابقا, فإن خوارزمية البحث تابو TS تستخدم اجرائيات بحث محلية ضمن الجوار Local or neighborhood search, حتى تقوم بشكل متكرر بالانتقال من حل محتمل x الى حل محسن اخر x’  ضمن جوار الحل x.

وتستمر هذه التكرارات الى حين الوصول الى احد شروط التوقف ( عادة ما تتمثل بالوصول الى عدد تكرارات محدد, او تحقيق عتبة محددة).

غالبا ما تعلق اجرائيات البحث المحلي ضمن مناطق محلية.
من اجل تجنب مثل هذه المطبات, واستكشاف فضاء البحث بشكل افضل, مع عدم ترك العديد من المناطق غير المستكشفة, جاءت خوارزمية البحث تابو TS لتستكشف بعناية جوار كل حل من الحلول مع تقدم البحث.
حيث يتم تحديد الحلول المقبولة ضمن كل جوار جديد N^*(x), باستخدام هياكل وبنى للذاكرة memory structures.
وبالاستفادة من هياكل الذاكرة هذه, يتم الانتقال من الحل الحالي x الى الحل المحسن x’ ضمن الجوار الحالي N^*(x)

تشكل هياكل الذاكرة هذه ما يعرف باسم قوائم تابو – اي القوائم المحضورة – tabu list, وهي عبارة عن مجموعة من القواعد والحلول المحضورة التي تستخدم لتصفية الحلول التي يتم قبولها من كل جوار N^*(x) يتم البحث فيه.

بشكل مبسط, إن قائمة تابو tabu list  عبارة عن مجموعة قصيرة الامد short-term set من الحلول التي تمت زيارتها ضمن الماضي القريب ( اقل من n تكرار, حيث ان n يمثل عدد الحلول السابقة التي تم تخزينها – ويدعى ايضا باسم tabu tenure – فترة الحظر).

وكما ذكرنا فإن خوارزمية البحث تابو TS تعتمد على بنى وهياكل للذاكرة لتخزين الحلول السابقة خلال فترة محددة بالاضافة الى تخزين القواعد ضمن هذه الذواكر.

إذن فقد حان الوقت الآن لنتحدث بشيء من التفصيل عن انماط وانواع هذه الذواكر

انواع الذواكر Types of memory

يمكن تصنيف انواع هياكل وبنى الذاكرة المستخدمة في خوارزمية البحث تابو TS الى ثلاث فئات:

  • ذاكرة قصيرة الامد Short-term memory: وتحوي على قائمة بالحلول التي تم اخذها مؤخرا بعيد الاعتبار. في حال تواجد احد الحلول المحتملة ضمن القائمة المحضورة tabu list , عندها لن يتم اعادة زيارة واستخدام هذا الحل حتى يصل الحل الى مرحلة انتهاء صلاحية تواجده ضمن قائمة تابو tabu list.
  • ذاكرة متوسطة الامد intermediate-term memory: وتحوي على قواعد تسمى بقواعد التكثيف intensification rules , وتهدف الى توجيه البحث نحو المناطق الواعدة من فضاء البحث.
  • ذاكرة طويلة الامد long-term memory: وتحوي على قواعد تسمى بقواعد التنويع diversification rules, ومهمتها قيادة البحث نحو مناطق جديدة ضمن فضاء البحث بحيث تضمن تنوع الحلول.
    مع هذا النوع من الذواكر طويلة الامد تستخدم عدة استراتيجيات منها : توليد حلول من مركبات ناردة الاستخدام, وبالتالي تحييد الاجيال المتولدة الجديدة من اعادة استخدام نفس المركبات المستخدمة عادة لتوليد الحلول. وبالتالي تضمن تنوع الحلول ضمن فضاء البحث.

بشكل عملي من الممكن ان تتداخل كل من الذاكرة قصيرة الامد short-term memory مع الذاكرة متوسطة الامد intermediate-term memory.

سنطرح مثال على الذواكر متوسطة الامد: المثال: الذاكرة التي تحتفظ بمعلومات فيما يخص الحلول الممنوعة أو المرغوبة التي تحتوي مثلا على صفات محددة ( على سبيل المثال الحلول التي تحوي  قيم غير مرغوبة او مرغوبة بالنسبة لمتحولات محددة certain variables).
او قد تحوي بنية الذاكرة على معلومات بحيث تمنع او تشجع تحركات محددة.

اما بالنسبة للذاكرة قصيرة الامد short-term memory فإنه يتم تصنيف بعض الصفات المختارة من الحلول التي تمت زيارتها مؤخرا على انها “tabu-active”. وبالتالي فإن الحلول التي تحوي على عناصر من “Tabu-active”  تعد حلولاً محظورة.
هنالك ما يعرف باسم Aspiration criteria وهي عبارة عن طريقة تستخدم بهدف تجاوز القيود الموجودة ضمن القائمة المحظورة tabu list, يعني ذلك في حال تواجد احد الحلول ضمن قائمة الحظر tabu list, فإنه هنالك احتمالية بأن يتم اعادة زيارة هذا الحل في حال كان يحوي على خواص وصفات موجودة ضمن قائمة السماح allowed set والتي تحوي على الصفات التي اذا وجدت بالحل يعتبر الحل جيد بما فيه الكفاية من حيث الجودة او التنوع.
اي باختصار فإن Aspiration ceiterion  تستخدم لكي تسمح باستخدام واعادة زيارة الحلول التي تعتبر افضل من الحل الحالي.

المخطط  ادناه يوضح خوارزمية بحث تابو TS ويوضح مهام كل من:

  • قائمة الحظر Tablu list
  • وقائمة السماح allow list using aspiration criterion

 

choosing best admissible candidate

ان استخدام ذاكرة قصيرة الامد short-term memory لوحدها ممكن ان يكون كافي من اجل ايجاد حل جيد متفوق على الحلول التي يمكن ايجادها باساليب البحث المحلية التقليديةconventional local search methods, ولكن بنى وهياكل الذاكرة متوسطة وطويلة الامد غالبا ما تكون ضرورية من اجل حل المسائل الاصعب.

في بعض الاحيان قد يتم دمج خوارزمية البحث تابو TS مع بعض الخوارزميات والتجريبيات الاخرى بهدف انتاج طرائق هجينة hybrid methods. واشهر مثال على ذلك يتمثل بدمج خوارزمية البحث تابو TS مع خوارزمية Scatter Search والتي هي عبارة عن اجرائية بحث تعتمد على التجمع population-based procedure, وتشترك بمجموعة من النقاط مع خوارزمية البحث تابو, وغالبا ما يتم استخدامها من اجل حل مسائل الامثلة  الكبيرة الغير خطيةالغير خطية non-linear optimization problems.

الاجرائية Procedure

الكود الترميزي ادناه يمثل نسخة مبسطة من خوارزمية البحث تابو Tabu search algorithm, حيث يتم استخدام الذاكرة قصيرة الامد فقط ضمن هذه الخوارزمية

العبارة “fitness” عبارة عن تابع يقوم بحساب وتقيييم الحل المرشح, لحساب مدى جودته.

algorithm.JPG

اضغط على الصورة لتكبيرها

توضح الخوارزمية السابقة الشرح المذكور سابقا.

بالنهاية نلخص بمايلي:

تتميز خوارزمية البحث تابو TS بمرونتها التي تعود الى استخدامها للذاكرة, حيث تسمح لها هذه البنية باستغلال معلومات البحث بشكل شمولي اكثر من الانظمة التي تعتمد على بنية ثابتة للذاكرة rigid memory systems, او الانظمة عديمة الذاكرة memoryless systems.

وتتميز هذه الخوارزمية Tabu Search Algorithm بأنها سهلة التطبيق: اي انه يمكن استخدامها وتطبيقها بالبداية بشكل مبسط جدا, لتقوم بوظيفتها الاساسية, ومن ثم يمكن تطويرها والتعديل عليها فيما بعد.
تعتبر خوارزمية Tabu Search بمثابة الاب الكبير لعائلة كبيرة من الطرائق المشتقة منها, والتي تستخدم بنى خاصة للذاكرة من اجل اتمام عملية البحث, مثل:

  • Reactive Tabu Search
  • Parallel Tabu Search

———————

نكتفي بهذا القدر من الشرح لخوارزمية البحث تابو TS, لنعود ونلتقي بكم مرة اخرى ان شاء الله مع خوارزمية جديدة

ومن المرجح ان تكون خوارزميتنا القادمة هي خوارزمية Bacterial Foraging Optimization Algorithm بناء على طلب الباحثين عن العلم

والى ذلك الحين استودعكم الله والسلام عليكم ورحمة الله وبركاته

مع تحيات:

م. نور الصباحي

الترجمة المصطلح
خوارزمية البحث تابو Tabu Search Algorithm
بنية او هيكلية الذاكرة memory structure
مسائل الامثلة Optimization problems
اجرائية تجريبية heuristic procedure
خوارزميات الامثلة العامة Global Optimization algorithm
فضاء البحث Search space
مسائل الامثلة Optimization problems
هيكلية , بنية Structure
طرائق هجينة hybrid methods
طرائق البحث المحلية التقليدية conventional local search methods
References
Tabu Search Tutorial

http://www.ida.liu.se/~zebpe83/teaching/rtes/papers/tabu_search.pdf

 

Clever Algorithms: Nature-Inspired Programming Recipes – Tabu Search

http://www.cleveralgorithms.com/nature-inspired/stochastic/tabu_search.html

 

Tabu Search Algorithm

https://en.wikipedia.org/wiki/Tabu_search

 

 

Advertisements

, , , , ,

أضف تعليق