حل مشكلة اضطراب جدول مواعيد الرحلات الجوية باستخدام ال Meta-heuristics Solving the flight perturbation problem with meta-heuristics

السلام عليكم ورحمة الله

اخوانى الافاضل بارك الله فيكم

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

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

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

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

ولكننى للأسف لم انتهى من الترجمة لكل المشاركات بعد , ولكى الزم نفسى بإنهاء هذا الامر ان شاء الله , فسأقوم بوضع المشاركات تباعا عندما انتهى منها.

وحتى نترك المشاركات فى هذا الموضوع مترابطه ومتصله , سأقوم بفتح موضوع اخر لتلقى الأسئلة والإستفسارات والنقاشات ان شاء الله تعالى.



البحث الأصلي:  مشكلة اضطراب جدول مواعيد الرحلات الجوية.pdf (303.09كيلو )

حل مشكلة اضطراب جدول مواعيد الرحلات الجوية باستخدام الـ Meta-Heuristics
Solving theflight perturbation problem with meta-heuristics
Tobias Andersson
Journal of Heuristics (2006) 12: 37–53
الكلمات المفتاحية:Aircraft recovery, Irregular operations, Operational airline scheduling, Simulated annealing, Tabusearch and Path relinking
================================================
مقـــدمــــــــــة:

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

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

1) تأجيل مواعيد بعض الرحلات: لو كان التأجيل محدود ومقبول.
2) إلغاء بعض الرحلات: وإعادة توزيع المسافرين على رحلات جديدة.
3) عمل تبديل بين بعض الطائرات من نفس النوع: بحيث تؤدى الطائرة B الرحلة الجوية بدلا عن الطائرة A.
4) عمل تبديل بين بعض الطائرات من انواع مختلفه: وهنا يجب ان تكون الطائرة البديله قادرة على استيعاب عدد المسافرين على الطائرة الأصلية.

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

1) مشكلة إضطراب جدول مواعيد الرحلات الجوية: وهى العصب الأساسى لهذا البحث.
2) مشكلة إسترضاء المسافر: حيث ان المسافر سيتأثر بشكل مباشر بأى تأخير او إلغاء للرحلات. وبالتالى على الشركة ان تحاول اعادة توزيع وتخصيص رحلات جديدة للمسافرين المتضررين , وربما تضطر ان تدفع لهم بعض التعويضات لإسترضائهم.
3) مشكلة إضطراب جدول طاقم الطائرة: لكل طاقم يعمل على رحلة ما جدول خاص به , بحيث انه سينتقل بعد الرحلة A الى رحلة اخرى B وهكذا , وربما تكون على نفس الطائرة او طائرة اخرى. وبالتالى اى اضطراب فى جدول مواعيد الرحلات , سيؤثر بشكل مباشر على جدول مواعيد طاقم الطائرة , وعلى الشركة ان تجد جدول بديل للطاقم المتضرر.
4) مشكلة جدول الصيانة الدورى للطائرات: عند تخصيص طائرة بديلة لتنفيذ رحلة جوية بدلا عن الطائرة الاصلية , فالطبيعى ان لهذه الطائرة جدول صيانه محدد حسب جدول رحلاتها الاصلى , وبعد التعديل الجديد ستحتاج الى تعديل جدول الصيانه الخاصة بها.

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

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

1) يجب ان يتم تحديد زمن بداية تطبيق الحل الجديد , وتسمى هنا بــ "وقت البدأ".
2) الجدول الجديد سيتم تطبيقه لمدة محددة تسمى "مدة التنفيذ"
3) عند انتهاء مدة التنفيذ سننتقل الى العمل بالجدول الأصلى , وتسمى هذه اللحظة بـ "وقت الانتهاء".

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

1) تأجيل مواعيد بعض الرحلات delay.
2) الغاء بعض الرحلات cancel.
3) عمل تبديل بين الطائرات من نفس النوع swap.
4) عمل تبديل بين الطائرات من انواع مختلفه , مع التأكد من سماحية سعة كلطائرة لعدد المسافرين عليها swap-f.

ويمكننا الأن بسهولة استنتاج الخصائص الجيدة التى يجب ان تتوفر فى الجدول الجديد المقترح وهى:

1) يجب الحصول على الجدول الجديد فى اسرع وقت ممكن (اشار بعض الباحثين الى انه يجب ان يكون اقل من ثلاث دقائق).
2) يجب ان يتم تطبيق الجدول الجديد لفترة محددة (مدة التنفيذ).
3) يجب ان يتوافق الجدول الجديد تماما مع الجدول الأصلى عند "وقت الإنتهاء" لضمان العودة بسلام للجدول الأصلى.
4) يجب ان يتم بناء الجدول الجديد بأقل عدد من التغيرات (الإجراءات) وذلك لتخفيض التكلفة.

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

1) حساب التكلفة الفعلى:
2) استخدام طريقة الأوزان:

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

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

1) فى حالة تأخير الرحلة ستكون التكلفه هو حاصل ضرب عدد المسافرين فى عدد دقائق التأخير فى وزن التأخير.
2) اما فى حالة الإلغاء سيتم حساب التكلفة لتكون حاصل ضرب عدد المسافرين فى وزن الإلغاء.
3) وأخيرا فى حالة التبديل , ستكون التكلفه عبارة عن وزن التبديل نفسه (لأن المسافر غير متضرر فى هذه الحالة).

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

ما معنى كلمة"حل" او "جدول مقترح"؟

المعنى ببساطه هو ان كل شركة طيران لديها عدد محدد من الطائرات , وتتعامل مع عدد محدد من المطارات. ومعروف ان كل طائرة ستقوم بتنفيذ عدد محدد من الرحلات المتتابعة , بحيث تقوم الطائرة بتنفيذ الرحلة الاولى من المطار A الىالمطار B ومن ثم تقوم بتنفيذ الرحلةالثانية من المطار B الى المطار C وتستمر هكذا تنفذ الرحلات المخططه لها بشكل تتابعى. وبتجميع كل هذه الرحلات بشكل تتابعى لطائرة محددة X , سنحصل على المسار الخاص بهذه الطائرة X. وبتجميع كل هذه المسارات لجميع الطائرات التابعة للشركة سنحصل على جدول مواعيد الرحلات الخاص بهذه الشركة. وهذا ما نسميه هنا "حلا للمسألة". فى الشكل التالى يمكننا تخيل الوضع بالنظر الى مسار الطائرة X بالازرق , ومسار الطائرة Y بالاحمر.

ارفق صورة : monthly_12_2009/post-52814-1261660660266.jpg

مثال لمسار طائرتين

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

عامة لكى نقول ان الحل I افضل من او متغلب على الحل J فأنه يجب ان يكون الحل I يحتاج تكاليف اقل من J وفى نفس الوقت عدد التغيرات التى يحتاجها لكل اجراء (تأجيل ,الغاء , تبديل) أقل من عدد التغيرات المناظرة التى يحتاجها الحل J. عندها نقول ان الحل I متغلب على الحل J. اما لو كان الحلان متقاربان فى التكاليف , وكان احدهما يستخدم عدد تغييرات اكثر من الاخر فى احد الإجراءات (مثلا التأجيل) وعدد تغييرات اقل من الاخر فى اجراء اخر (مثلا التبديل) , فنقول ان الحلول غير متغلبة على بعضها.

3) الخوارزميات المستخدمة لحل المشكلة.


فى هذا الجزء من البحث يبدأ الباحث باستعراض خوارزميات الذكاء الاصطناعى التى سيستخدمها ان شاء الله لحل مشكلة اضطراب جدول الرحلات الجوية. فى الحقيقة فإن الباحث سيستخدم طريقتين من اكثر الطرق شهرة فى الـ Meta-Heuristics. و الـ Meta-Heuristics هى فرع من اكبر فروع الذكاء الاصطناعى , وتضم تحتها العديد من الطرق المختلفه , ومنها الطريقتين محل الدراسة هنا وهما خوارزمية الـ Tabu Search وخوارزمية الـ Simulated Annealing.

ولكن قبل التعرض لفكرة عمل الخوارزميتين السابقتين , فإن الباحث يعطينا فكرة سريعة عن خوارزمية الـ Local Search , وهى الخوارزمية التى تعتبر الأصل لجميع خوارزميات الـ Meta-Heuristics ، ولكن لأن بها عيوب معينه فجاءت باقى خوارزميات الـ Meta-Heuristics لتطور وتعالج بعض العيوب الموجوده فى خوارزمية الـ LocalSearch. فدعونا نأخذ عنها فكرة سريعة

1) خوارزمية الـ Local Search

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

الرسم التوضيحى التالى يبين فكرة عمل خوارزمية الـ Local Search



والرسم المتحرك التالى , يعطى تقريب لعملية البحث عن القيمة الصغرى لمنحنى ما باستخدام خوارزمية الـ Local Search.


مثال لفكرة عمل خوارزمية الـ Local Search


ولكن كما نرى فى الرسم المتحرك السابق , فإن اكبر عيوب هذه الخوارزمية , انها غالبا تعود بأفضل حل قريب من الحل الإبتدائى والذى نسميه علميا "الحل المحلى Local Optimum", وقديكون هناك الكثير من "الحلول المحلية" لنفس المشكلة. ولكننا بالطبع نهدف الى الوصول الى افضل الحلول مطلقا والذى نسميه "الحل العام Global Optimum" وبالتالى مشكلة استخدام خوارزمية الـ Local Search أنها ستعود لنا بأقرب حل محلى يقابلها , ولن تستطيع الإفلات منه للوصول للحل العام , لأنها لا تقبل التحديث الا لو كان الحل الجديد افضل من الحل الحالى , وحيث ان جميع الحلول القريبة من الحل المحلى هى حلول اسوء منه , فإنه بالوصول الى الحل المحلى فلن نستطيع ابدا الهروب منه. وهذا ما تحاول الخوارزميات الجديدة فى الـ Meta-Heuristics تفاديه , وكل خوارزمية تفعل ذلك بطريقه خاصة بها.



2) خوارزمية الـ Tabu Search

فى هذه الخوارزمية , فإن طريقة الحصول على حل لمشكلة ما , يتبع نفس الاسلوب السابق فى الـ Local Search , ولكن بإضافة خاصيتين جديدتين لضمان الوصول الى افضل الحلول الممكنه "الحل العام Global Optimum" , وذلك بالهروب من الحلول المحلية التى قد تقابلنا اثناء البحث عن الحل العام.

تبدأ خوارزمية الـ Tabu Search العمل بتوليد حل اولى عشوائيا , وهو ما يسمى بالحل الإبتدائى وليكن Sol ثم نقوم بإنشاء لائحة نسميها لائحة المحرمات Tabu List او اختصارا TL ونسجل فيها الحل الإبتدائى Sol. ثم نقوم -بطريقة ما- بتوليد مجموعة حلول جديد فى جوار الحل الحالى واختيار افضلها وليكن *Sol , فإن لم يكن *Sol مسجل فى لائحة المحرمات TL فسيتم قبوله وعمل التحديث بوضع *Sol=Sol حتى لو كان الحل الجديد *Sol اسوء من الحل الحالى Sol ثم يتم إضافة Sol (الحالى) الى لائحة المحرمات TL. ونستمر فى تكرار هذه العملية بتوليد حلول جديدة حول الحل الحالى Sol واختيار افضلها وليكن *Sol وإن لم يكن مسجل فى لائحة المحرمات يتم قبوله ووضع *Sol=Sol وإضافة Sol الجديد فى لائحة المحرمات TL. ويستمر هذا الامر حتى شرط التوقف والعودة بأفضل حل حصلنا عليه خلال عملية البحث.

وهنا لنا وقفات لتوضيح الأمر اكثر.

- ذكرنا اننا سننشأ لائحة جديدة هنا تسمى "لائحة المحرمات TL" وسنضيف اليها الحلول الجديدة تباعا بعد اعتمادها. ودور هذه اللائحة هو منع العودة مرة اخرى لحل تم زيارته سابقا , وذلك حتى نتجنب الوقوع فى حلقه مفرغه. فكما نلاحظ فإنه قبل قبول الحل الجديد *Sol فإننا نختبره هل هو مسجل فى TL ام لا؟ فإن كان مسجل سيتم تجاهله والعوده لتوليد مجموعة حلول جديدة بجوار Sol واختيار افضلها وهكذا. وان لم يكن مسجل بلائحة المحرمات TL فسيتم قبوله وعمل التحديث. وهذه اول خاصية اضافتها خوارزمية الـ Tabu Search لخوارزمية Local Search.

- نلاحظ ايضا انه بعد التأكد من ان الحل الجديد *Sol حل غير محرم , فإنه يتم التحديث مباشرة بوضع *Sol=Sol بدون التأكد من ان *Sol افضل من Sol , فلماذا نفعل ذلك؟ نفعل ذلك لنتأكد انه لو واجهت الخوارزمية "حل محلى Local Search" فإنها ستكون قادرة على الهروب منه , لأنها تقبل احسن حل فى جوار الحل الحالى حتى لو كان حل اسوء من الحل الحالى. وهذه الخاصية الثانية التى اضافتها خوارزمية الـ Tabu Search لخوارزمية Local Search.

- شرط التوقف هنا , سيعتمد على رغبة المستخدم. وغالبا يكون شرط التوقف عبارة عن عمل عدد محدود من التكرارات وليكن 1000 او 100000. لكن المهم ان يكون هناك شرط للتوقف , وإلا ستسمر الخوارزمية فى العمل الى مالا نهاية.

- لائحة المحرمات TL , غالبا يكون طولها محدود ويتم تخزين اخر عدد محدد من الحلول. فلو قلنا مثلا ان طولها 5 ، فهذا معناه انها ستحتفظ بأخر 5 حلول فقط تم الحصول عليهم , وليس كل الحلول التى تم الحصول عليها. وعندما تمتلئ الـ TL فإننا سنضيف الحل الجديد اليها ونقوم بحذف اقدم الحلول منها.

- يفضل عمل متغير بإسم BestSol ليحتفظ بأفضل حل تم الحصول عليه اثناء عمل الخوارزمية. وعند الحصول على حل جديد Sol يتم مقارنته بـ BestSol فلو كان Sol افضل من BestSol يتم وضع BestSol=Sol.


الصورة التالية توضح طريقة عمل خوارزمية الـ Tabu Search



والرسم المتحرك التالى , يعطى تقريب لعملية البحث عن القيمة الصغرى لمنحنى ما باستخدام خوارزمية الـ Tabu Search.



مثال لفكرة عمل خوارزمية الـ Tabu Search


3) خوارزمية الـ Simulated Annealing

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

والفكرة فى خوارزمية الـ Simulated Annealing هنا بالمثل. بحيث اننا نبدأ بتوليد حل اولى او ما يسمى بالحل الإبتدائى Sol واختيار قيمة كبيرة جدا لدرجة الحرارة. ثم نقوم بتوليد احد الحلول وليكن *Sol فى جوار الحل الحالى Sol, والأن لإتخاذ قرار بتحديث الحل الحالى من عدمه , فهذا يعتمد على قيمة دالة تسمى دالة الإحتمال Prob تأخذ قيمة درجة الحرارة T والفرق بين مدى كفاءة الحل الجديد *Sol ومدى كفاءة الحل الحالى Sol وتعود لنا بقيمة بين الصفر و الواحد. وعنه تقوم الخوارزمية بحساب قيمة دالة الإحتمال (القيمة دائما بين 0 و 1) ثم توليد عدد حقيقى عشوائى rand ايضا بين 0 و1. فإذا كان قيمة دالة الاحتمال اكبر من rand فسيتم قبول الحل الجديد *Sol ويتم وضع *Sol=Sol. وسيتم تكرار هذه الخطوات بحيث يتم توليد حل جديد *Sol بجوار Sol وحساب قيمة دالة الاحتمال للحل الجديد , ولو كانت اكبر من الرقم العشوائى rand (بين 0 و 1) فسنقوم بتحديث الحل الحالى ووضع *Sol=Sol. وبعد عدد محدد من الدورات (حسب رغبة المستخدم) سنقوم بتخفيض قيمة درجة الحرارة بوضع t=at حيث a عدد بين 0 و 1. وبعد تخفيض درجة الحرارة سنقوم بتكرار الخطوات السابقة وتوليد حلول جديدة وهكذا. وعندما يتحقق شرط التوقف ستتوقف الخوارزمية وتعود بأفضل حل خلال رحلة البحث.

توضيحات:

- نبدأ الخوارزمية بقيمة كبيرة جدا لدرجة الحرارة t تعتمد على المشكلة نفسها , فمثلا يمكن وضع t=1000 او t=10000 وهكذا.

- دالة الاحتمال هى من اهم الخصائص فى خوارزمية الـ Simulated Annealing , وقيمتها دائما تقع بين 0 و 1 حسب قيمة t وحسب جودة الحل *Sol بالمقارنة بالحل Sol. لكى تنجح الخوارزمية فى ايجاد حل جيد , فيجب ان تحقق دالة الاحتمال هذه بعض الشروط وهى:

- غالبا يتم تخفيض درجة الحراراة بعد عدد ثابت من الدورات وليكن مثلا 10. فهذا يعنى ان البحث سيقوم بعمل 10 دورات حول الحل الحالى Sol وسيقوم بالتحديث بـ *Sol اعتمادا على قيمة دالة الاحتمال. وبعد الـ 10 دورات سيتم تخفيض الحرارة وعمل 10 دورات اخرى بقيمة t الجديدة وهكذا حتى انتهاء عملية البحث.

- يفضل عمل متغير بإسم BestSol ليحتفظ بأفضل حل تم الحصول عليه اثناء عمل الخوارزمية. وعند الحصول على حل جديد Sol يتم مقارنته بـ BestSol فلو كان Sol افضل من BestSol يتم وضع BestSol=Sol.




مثال على دالة الإحتمال:


بفرض ان هى الدالة المستهدفه فى المشكله محل الدراسه (Fitness Function) واننا نريد تعظيم هذه الدالة اى ايجاد قيمة X التى تعطى اكبر قيمة للدالة z (مثل تعظيم دالة الربح فى مشكلة اضطراب جدول رحلات الطيران). اى اننا سنقول ان الحل X افضل من الحل Y اذا كانت . الان بفرض الحل الحالى فى خوارزمية الـ Simulated Annealing هى Sol والحل الجديد هو *Sol. وبفرض ان وان درجة الحرارة هى t. فإن اشهر دالة احتمال تستخدم فى الابحاث العلميه هى

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

فعلى سبيل المثال , لو كانت t=1000 وكانت فإن قيمة دالة الاحتمال ستكون وهى قيمة محصورة بين 0 و 1 كما قلنا سابقا.



الصورة التالية توضح طريقة عمل خوارزمية الـ Simulated Annealing






4) خوارزمية الـ Path-Relinking

فى الحقيقة فإن خوارزمية الـ Path-Relinking تم تقديمها عام 1993 كإمتداد لخوارزمية الـ Tabu Search. وكل فكرة الخوارزميه ببساطه , انه بعد تطبيق خوارزمية الـ Tabu Search فإنه فى النهاية يمكننا الحصول على مجموعة حلول جيدة (افضل الحلول التى ظهرت خلال عملية البحث) مرتبه حسب افضليتها , وحيث ان كل الحلول جيدة , فإنه لو تم ايجاد حلول بينيه (بين الحلول الجديدة) تجمع بعض الصفات المشتركة من هذه الحلول الجيدة , فإنه هناك احتمال كبير ان نجد من ضمن هذه الحلول البينيه من هو افضل من الحلول الاصلية.

تعتمد خوارزمية الـ Path-Relinkingعلى اخذ حلين جيدين من نتائج خوارزمية الـ Tabu Search. احد هذه الحلول نسميه الحل الإبتدائى Sol_S والحل الأخر نسميه الحل المرشد (او الحل الدليل) Sol_G. والمطلوب هوالتحرك ابتداءا من الحل الإبتدائى عبر مسار ما حتى الوصول الى الحل المرشد. وعلى هذا المسار الذى سنسلكه من الحل الإبتدائى حتى الحل المرشد , هناك احتمال كبير بوجود حلول اخرى افضل من الحل الإبتدائى والحل المرشد , اعتمادا على ان هذه الحلول الجديدة تمتلك صفات مشتركة من الحلين الجيدين (على اساس ان جيل الأبناء غالبا يكون افضل من جيل الأباء).

وتعتمد الخوارزمية هنا على حصر الفروق بين الحل الإبتدائى Sol_S والحل الدليل Sol_G. فلو قلنا مثلا هناك n فرق بين الحلين , بحيث لو تمت معالجة (تعديل) هذه الفروق فى الحل الابتدائى , فإنه بالتأكيد سنصل الى الحل الدليل. وتبدأ الخوارزميه بتحديد لائحة الفروق بين الحلين , ثم عمل تعديل على الحل الابتدائى Sol_S فى المنطقه التى تحتوى الفرق الاول بحيث يتطابق مع الحل المرشد فى هذ المنطقه , ونسمى هذا الحل الجديد بالمحاولة الاولى , ثم نعود ونقوم بعمل تعديل فى الحل الابتدائى (الاصلى) فى المنطقه التى تحتوى الفرق الثانى , بحيث تتطابق مع الحل الدليل فى هذه المنطقه ونسمى الحل الناتج بالمحاوله الثانية وهكذاحتى نتعامل مع كل الفروق بين Sol_S و Sol_G. فلو كان عدد الفروق n فإنه سينتج لدينا n حل (محاولة) جديد , نقوم باختيار افضل هذه الحلول ونسميه Sol₁ ثم ننتقل من الحل Sol_S الى الحل Sol₁. ونقوم بعمل نفس الخطوات السابقه. اى انه سيكون لدينا الان n-1 فرق بين الحل الدليل Sol_G و الحل Sol₁ ونقوم كل مرة بتعديل فرق واحد فى Sol₁ بحيث يتطابق مع Sol_G فى المنطقه التى تحتوى الفرق , ونقوم باختيار افضل حل فى الحلول الجديدة ونسميه Sol₂. وما تم عمله مع Sol_S و Sol₁ سيتم مع Sol₂ وهكذا. وكما نرى فإن كل مرحلة تقوم بالتخلص من احد الفروق بين الحل الحالى والحل الدليل , وبعد عدة خطوات n+1 سينطبق الحل الحالى على الحل الدليل.

مجموعة الحلول التى حصلنا عليها خلال رحلتنا من Sol_S حتى Sol_G نسميها المسار من Sol_S حتى Sol_G وكلنا أمل ان يكون احد هذه الحلول على هذا المسار افضل من الحلين Sol_S و Sol_G.

الرسم المتحرك التالي يوضح خطوات عمل خوارزمية الـ Path-Relinking

Resized to 80% (was 810 x 560) - Click image to enlarge