مشكلة تحسين المسار | الوحدة الخامسة | الدرس الثالث
مشكلة تحسين المسار هو عنوان الدرس الثالث من الوحدة الخامسة التي تحمل اسم “خوارزميات التحسين واتخاذ القرار” من مقرر “الذكاء الاصطناعي” الفصل الدراسي الثاني.
سنتعرف في هذا الموضوع على كيفية استخدام البرمجة الرياضية (Mathematical Programming) لحل مشكلات التحسين (Optimization Problems)، ومعرفة مشكلة حقيبة الظهر (Knapsack Problem)، بالإضافة إلى معرفة مشكلة البائع المتجوِّل (Traveling Salesman) واستخدام البايثون لحلهما.
قم بقراءة أهداف التعلُّم بعناية، ثم أعد قراءتها وتأكَّد من تحصيل محتواها بعد انتهائك من دراسة الموضوع.
أهداف التعلُّم
- استخدام البرمجة الرياضية لحل مشكلات التحسين.
- معرفة مشكلة حقيبة الظهر.
- معرفة مشكلة البائع المتجوِّل.
هيا لنبدأ!
البرمجة الرياضية في مشكلات التحسين (Mathematical Programming in Optimization Problems)
في الموضوعين السابقين تم توضيح كيفية استخدام الخوارزميات الاستدلالية لحل أنواع مختلفة من مشكلات التحسين، وبالرغم من أن الاستدلالات بإمكانها أن تكون سريعة جدًا وتُنتج في العادة حلولًا جيدة، إلا أنها لا تضمن دائمًا إيجاد الحل الأمثل، وقد لا تكون مناسبة لكل أنواع المُشكلات، وفي هذا الموضوع ستركِّز على أسلوب تحسين مختلف وهو البرمجة الرياضية (Mathematical Programming).
تعريف هام
البرمجة الرياضية (Mathematical Programming):
هي تقنية يتم استخدامها لحل مشكلات التحسين عن طريق صياغتها على هيئة نماذج رياضية.
يمكِن للبرمجة الرياضية أن تحل العديد من مشكلات التحسين، مثل:
تخصيص الموارد، وتخطيط الإنتاج، والخدمات اللوجستية والجدولة، وتتميز هذه التقنية بأنها توفِّر حلًّا مثاليًا مضمونًا ويمكِنها التعامل مع المشكلات المعقدة ذات القيود المتعدِّدة.
يبدأ حل البرمجة الرياضية بصياغة مشكلة التحسين المُعطاة على شكل نموذج رياضي باستخدام المُتغيِّرات، حيث تمثِّل هذه المُتغيِّرات القيم التي يجب تحسينها، ثم يتم استخدامها لتحديد الدالة الموضوعية والقيود، وهما يصفان المشكلة معًا ويمكِّنان من استخدام خوارزميات البرمجة الرياضية.
تستخدِم البرمجة الرياضية متغيِّرات القرار (Decision Variables) التي تساعد متَّخِذ القرار في إيجاد الحل المناسب عن طريق ضبطها والتحكُّم فيها، كما يمكِنها أن تستخدِم متغيِّرات الحالة (State Variables) التي لا يتحكم فيها متَّخِذ القرار وتفرضها البيئة الخارجية، وبالتالي لا يمكِن ضبط متغيِّرات الحالة.
توفِّر القوائم التالية أمثلة على متغيِّرات القرار ومتغيِّرات الحالة لبعض مشكلات التحسين الشائعة:
مشكلة تحسين المسار
تتم صياغة الدالة الموضوعية كتعبير رياضي (Mathematical Expression) لتحسينها (بزيادتها أو تقليلها) بناءً على المتغيِّرات المناسبة، وتمثِّل هذه الدالة الهدف من مشكلة التحسين، مثل: زيادة الربح أو تقليل التكاليف، وتحدَّد في العادة بناءً على متغيِّرات القرار، كما تحدَّد أحيانًا بناءً على متغيِّرات الحالة، وبالمثل يمكِن صياغة القيود باستخدام المتغيِّرات والمتباينات الرياضية.
توجد عدة أنواع من البرمجة الرياضية، مثل: البرمجة الخطية (Linear Programming – LP)، والبرمجة الرباعية (Quadratic Programming – QP)، وبرمجة الأعداد الصحيحة المختلطة (Mixed Integer Programming – MIP).
يركِّز هذا الدرس على برمجة الأعداد الصحيحة المختلطة المُستخدَمة في المشكلات التي تتقيَّد فيها متغيِّرات القرار بالأعداد الصحيحة، مثل: مشكلات الجدولة أو اختيار الطريق.
مشكلة حقيبة الظهر (The Knapsack Problem)
مشكلة حقيبة الظهر 1/0 هي مثال بسيط على استخدام برمجة الأعداد الصحيحة المختلطة لصياغة الدالة الموضوعية والقيود، ويتم تعريف المشكلة على النحو التالي: لديك حقيبة ظهر بسعة قصوى تبلغ C وحدة، ومجموعة من العناصر I، بحيث يكون لكل عنصر i متغيِّران من متغيِّرات الحالة هما وزن العنصر Wi وقيمته Vi، والمطلوب هو تعبئة الحقيبة بمجموعة العناصر ذات أقصى قيمة ممكنة في حدود سعة الحقيبة.
يتم استخدام متغيِّر القرار Xi لتتبع تجميعات العناصر التي سيتم تعبئتها في حقيبة الظهر، حيث تكون Xi = 1 إذا تم اختيار العنصر i للإضافة للحقيبة، بينما تكون Xi = 0 خلاف ذلك، ويتمثَّل الهدف في انتقاء مجموعة فرعية من العناصر من I بحيث تشمل:
- القيد (Constrain): مجموع أوزان العناصر المنتقاة بها لا يزيد عن السعة القصوى C.
- الدالة الموضوعية (Objective Function): مجموعة قيم العناصر المنتقاة بها هي أقصى قيمة ممكِنة.
يوضِّح الشكل 5.6 مثالًا على مسألة حقيبة ظهر مكوَّنة من 6 عناصر بأوزان وقيم محدَّدة، وحقيبة ظهر بسعة قصوى تساوي 40 وحدة.
يقوم المقطع البرمجي التالي بتثبيت مكتبة البايثون المفتوحة المصدر mip الخاصة ببرمجة الأعداد الصحيحة المختلطة لحل نسخة مشكلة حقيبة الظهر 1/0، ويستورد الوحدات الضرورية:
مشكلة تحسين المسار
يقوم المقطع البرمجي بإنشاء القائمة x لتخزين متغيِّرات القرار الثنائية للعناصر، وتوفِّر المكتبة mip في البايثون ما يلي:
- أداة add_var(var_type=BINARY) لإنشاء المتغيِّرات الثنائية وإضافتها إلى خوارزمية الحل.
- أداة maximize() لمشكلات التحسين التي تحتاج لزيادة دالة موضوعية، أما مشكلات التحسين التي تتطلَّب تصغير الدالة الموضوعية، فتستخدِم الأداة minimize().
- أداة xsum() لإنشاء التعبيرات الرياضية التي تتضمن المجاميع (sums)، وفي المثال السابق تم استخدام هذه الأداة لحساب مجموع الوزن الإجمالي للعناصر في إنشاء قيد السّعة وحلّه.
- أداة optimize() لإيجاد حل يحسِّن الدالة الموضوعية في ظل الالتزام بالقيود، وتستخدِم الأداة برمجة الأعداد الصحيحة المختلطة للنظر بكفاءة في توليفات القيم المختلفة لمتغيِّرات القرار ولإيجاد التوليفة التي تحسِّن الهدف.
- المُعامِل =+ لإضافة قيود إضافية إلى خوارزمية الحل الموجودة.
في المقطع البرمجي أدناه تحتوي القائمة x على متغيِّر ثنائي واحد لكل عنصر، وبعد حساب الحل سيكون كل متغيِّر مساويًا للواحد إذا تم إدراج العنصر في الحل، وسيساوي صفرًا بخلاف ذلك، تستخدِم المكتبة mip بِناء الجملة x[i].x لإظهار القيمة الثنائية للعنصر ذي الفهرس i، وتَحسب خوارزمية الحل متغيِّر القرار x، ثم تجد القيمة الإجمالية والوزن الإجمالي للعناصر المنتقاة عن طريق التكرار على متغيِّر القرار x، وتجمع الأوزان والقيم لكل عنصر منتقى i، استنادًا إلى x[i]، وتعرضها كما هو موضَّح في المقطع البرمجي التالي:
مشكلة تحسين المسار
بإمكانك مراجعة محتوى موضوع “مشكلة تحسين المسار” من بدايته وحتى نهاية هذا القسم، من خلال الرابط التالي:
مشكلة البائع المُتجوِّل (Traveling Salesman Problem)
مشكلة البائع المُتجوّل (Traveling Salesman Problem – TSP) من المشكلات الأخرى التي يمكِن حلّها ببرمجة الأعداد الصحيحة المختلطة، وهي مشكلة مألوفة تُعنى بتحديد أقصر مسار يمكِن أن يسلكه بائع متجوِّل لزيارة مدنٍ معيَّنة مرة واحدة، دون أن يكرِّر زيارة أيٍّ منها، ثم يعود للمدينة الأصلية، ويصوِّر الشكل 5.7 نسخةً من هذه المشكلة.
مشكلة تحسين المسار
تمثِّل كل دائرة (عقدة) مدينة أو موقعًا يجب زيارته، وهناك حافة تربط بين موقعين إذا كان من الممكِن السفر بينهما، ويمثِّل الرقم الموجود على الحافة التكلفة (المسافة) بين الموقعين.
في هذا المثال، تم ترقيم المواقع وفقًا لترتيبها في الحل الأمثل للمشكلة، وتكون التكلفة الإجمالية للطرق 1←2←4←3←1 تساوي 10+25+30+15=80، وهو أقصر طريق ممكِن لزيارة كل مدينة مرة واحدة فقط والعودة إلى نقطة البداية.
توجد تطبيقات عملية لمشكلة البائع المُتجوِّل في الخدمات اللوجستية، والنقل، وإدارة الإمدادات والاتصالات، فهي تنتمي إلى عائلة أوسع من مشكلات تحديد الطريق التي تشمل أيضًا مشكلات شهيرة أخرى موضحة فيما يلي:
- تتضمن مشكلة تحديد مسار المركبات (Vehicle Routing Problem) إيجاد الطرق المُثلى لأسطول من المركبات لتوصيل السلع أو الخدمات لمجموعة من العملاء في ظل تقليل المسافة الإجمالية المقطوعة إلى الحد الأدنى، وتشمل تطبيقاتها الخدمات اللوجستية وخدمات التوصيل وجمع النفايات.
- تتضمن مشكلة الاستلام والتسليم (Pickup and Delivery Problem) إيجاد الطُرق المُثلى للمركبات لكي تستلم (تُحمِّل أو تُركِب) وتسلِّم (تُوصِل) البضائع أو الأشخاص إلى مواقع مختلفة، وتشمل تطبيقاتها خدمات سيارات الأجرة، والخدمات الطبية الطارئة، وخدمات النقل الجماعي.
- تتضمن مشكلة جدولة مواعيد القطارات (Train Timetabling Problem) إيجاد جداول زمنية مثالية للقطارات في شبكة سكك الحديد في ظل تقليل نسبة التأخير إلى الحد الأدنى وضمان الاستخدام الفعَّال للموارد، وتشمل تطبيقاتها النقل بالسكك الحديدية والجدولة.
يمكِن استخدام المقطع البرمجي التالي لإنشاء نسخة من مشكلة البائع المُتجوِّل، وتقبل الدالة عدد المواقع المراد زيارتها، ونطاق المسافة يمثِّل الفَرق بين المسافة الأقصر والمسافة الأطول بين موقعين، ثم تُظهِر:
- مصفوفة المسافة التي تشمل المسافة المُسندة بين كل زوج ممكِن من المواقع.
- مجموعة عناوين المواقع العددية (عنوان لكل موقع).
- الموقع الذي يكون بمثابة بداية الطريق ونهايته، ويشار إليه باسم موقع startstop (الانطلاق والتوقف).
يستخدِم المقطع البرمجي التالي الدالة الواردة سابقًا لإنشاء نسخة من مشكلة البائع المُتجوِّل، بحيث يتضمن 8 مواقع، ومسافات ثنائية تتراوح بين 5 و20:
مشكلة تحسين المسار
إنشاء خوارزمية حل القوة المُفرطة لمشكلة البائع المُتجوِّل (Creating a Brute-Force Solver for the Traveling Salesman Problem)
تستخدِم الدالة التالية خوارزمية حل القوة المُفرطة لتعداد جميع الطُرق المُمكِنة (التباديل) وإظهار أقصر مسار، وتقبل هذه الدالة مصفوفة المسافة وموقع الانطلاق والتوقف الذي تُظهره الدالة create_problem_instance().
لاحظ أن الحل الممكِن لنسخة مشكلة البائع المُتجوِّل (TSP) هي تبديل مدن، يبدأ من مدينة startstop (الانطلاق والتوقف) ثم ينتهي إليها.
تستخدِم خوارزمية حل القوة المُفرطة أداة permutations() لإنشاء كل الطُرق المُمكِنة. لاحظ أن موقع startstop (الانطلاق والتوقف) يتم استبعاده من التباديل، لأنه يجب أن يظهر دائمًا في بداية كل طريق ونهايته، فعلى سبيل المثال، إذا كانت لديك 4 مواقع 0، و1، و2، و3، وكان الموقع 0 هو موقع startstop (الانطلاق والتوقف)، ستكون قائمة التباديل المُمكِنة كما يلي:
تَحسب خوارزمية حل القوة المُفرطة المسافة الإجمالية لكل طريق، وتُظهر في النهاية الطريق ذا المسافة الأقصر.
يطبِّق المقطع البرمجي التالي خوارزمية الحل على نسخة مشكلة البائع المُتجوِّل التي تم إنشاؤها سابقًا:
على غرار خوارزميات حل القوة المُفرطة التي تم توضيحها في الدروس السابقة، لا تطبَّق هذه الخوارزمية إلا على نُسخ مشكلة البائع المُتجوِّل الصغيرة؛ لأن عدد الطُرق المُمكِنة يتزايد أضعافًا مضاعفة كلما زاد العدد N، ويساوي (N–1)!، وعلى سبيل المثال، عندما يكون N = 15، فإن عدد الطُرق المُمكِنة يساوي 14! = 87,178,291,200.
بإمكانك مراجعة محتوى موضوع “مشكلة تحسين المسار” بدايةً من عنوان “مشكلة البائع المتجول” وحتى نهاية هذا القسم، من خلال الرابط التالي:
استخدام برمجة الأعداد الصحيحة المختلطة لحل مشكلة البائع المُتجوِّل (Using MIP to Solve the Traveling Salesman Problem)
لاستخدام برمجة الأعداد الصحيحة المختلطة (MIP) لحل مشكلة البائع المُتجوِّل (TSP)، يجب إنشاء صيغة رياضية تغطي كلًا من الدالة الموضوعية وقيود مشكلة البائع المُتجوِّل.
تتطلَّب الصيغة متغيِّر قرار ثنائي Xij لكل انتقال محتمل j ← i من موقع i إلى موقع آخر j، وإذا كانت المشكلة بها عدد N من المواقع، فإن عدد الانتقالات المُمكِنة يساوي N×(N–1).
إذا كانت Xij تساوي 1، فإن الحل يتضمن الانتقال من الموقع i إلى الموقع j، وخلاف ذلك إذا كانت Xij تساوي 0، فلم يتم إدراج هذا الانتقال في الحل.
يمكِن الوصول بسهولة إلى العناصر في مصفوفة numpy ثنائية الأبعاد عبر الصيغة البرمجية [i,j]، فعلى سبيل المثال:
يستخدِم المقطع البرمجي الأداة product() من المكتبة itertools لحساب جميع الانتقالات المواقع المحتملة، فعلى سبيل المثال:
يستخدِم المقطع البرمجي التالي مكتبة البايثون mip لإنشاء خوارزمية حل برمجة الأعداد الصحيحة المختلطة، ثم يضيف متغيِّر قرار ثنائي لكل انتقال ممكِن في نسخة مشكلة البائع المُتجوِّل التي تم إنشاؤها سابقًا:
يستخدِم المقطع البرمجي السابق أداة numpy.full() لإنشاء مصفوفة numpy بحجم N×N لتخزين المتغيِّرات الثنائية x.
بعد إضافة متغيِّرات القرار x، يمكِن استخدام المقطع البرمجي التالي لصياغة وحساب الدالة الموضوعية لمشكلة البائع المُتجوِّل، حيث تقوم الدالة بالتكرار على كل انتقال ممكن j←i ويتم ضرب مسافتها dist_matrix[I,j] مع متغيِّر قرارها x[I,j]، وإذا تم إدراج الانتقال في الحل سيؤخذ x[I,j]=1 وdist_matrix[I,j] بعين الاعتبار، وبخلاف ذلك سيتم ضرب dist_matrix[i,j] في صفر ليتم تجاهُلُها:
تهدف الخطوة التالية إلى التأكُّد بأن الخوارزمية تُظهِر الحلول التي تضمن زيارة كل المواقع لمرَّة واحدة فقط، باستثناء موقع startstop (الانطلاق والتوقف) حسب ما تتطلبه مشكلة البائع المُتجوِّل، وزيارة كل موقع مرة واحدة تعني أن الطريق الصحيح يُمكِن أن:
- يصل إلى كل موقع مرة واحدة فقط.
- يغادر من كل موقع مرة واحدة فقط.
ويمكِن إضافة قيود الوصول والمغادرة هذه بسهولة كما يلي:
تشمل الصيغة الكاملة لمشكلة البائع المُتجوِّل نوعًا إضافيًا آخرًا من القيود لضمان حساب الطُرق المتصلة، ففي نسخة مشكلة البائع المُتجوِّل الواردة في الشكل التالي من المفترض أن الموقع 0 هو موقع الانطلاق والتوقف.
في هذا المثال، أقصر طريق ممكِن هو 0 ← 3 ← 4 ← 1 ← 2، بمسافة سفر إجمالية قدرها 24، ولكن عند عدم وجود قيد اتصال سيكون هناك حل صحيح آخر يشمل طريقين غير متصلين هما: 0←3←4←0 و1←2←1، وهذا الحل المتمثل في وجود طريقين يمتثل لقيود الوصول والمغادرة التي تم تعريفها في المقطع البرمجي السابق؛ لأن كل موقع يدخل له ويخرج منه مرة واحدة فقط، ولكن هذا الحل غير مقبول لمشكلة البائع المُتجوِّل.
يمكِن فرض حل يشمل طريقًا واحدًا متصلًا بإضافة متغيِّر القرار Yi لكل موقع i، وستحافظ هذه المتغيِّرات على ترتيب زيارة كل موقع في الحل.
على سبيل المثال، إذا كان الحل هو: 0 ← 3 ← 4 ← 1 ← 2 ← 0، فستكون قيم y كما يلي: y1 = 2، y4 = 1، y3 = 0، y2 = 3، والموقع 0 هو موقع الانطلاق والتوقف، ولذلك لا تؤخذ قيمة y الخاصة به بعين الاعتبار.
يمكِن استخدام متغيِّرات القرار الجديدة هذه لضمان الاتصال من خلال إضافة قيد جديد لكل انتقال j ← i لا يشمل موقع startstop (الانطلاق والتوقف).
إذا كانت Xij = 1 لانتقال j ← i وتم إدراج هذا الانتقال في الحل، فإن المتباينة الواردة في الأعلى تصبح y[j] >= y[i] + 1، ومعنى ذلك أن المواقع التي سيتم زيارتها لاحقًا لابد أن تكون قيمة y الخاصة بها أعلى، بالإضافة إلى قيود الوصول والمغادرة، وسيكون الطريق الذي لا يشمل موقع الانطلاق والتوقف صحيحًا فقط إذا:
- بدأ وانتهى بالموقع نفسه، لضمان أن يكون لكل موقع وصول واحد ومغادرة واحدة فقط.
- تم تخصيص قيم y أعلى لكل المواقع التي سيتم زيارتها لاحقًا؛ لأن y[i] يجب أن تكون أكبر من y[i] لكل الانتقالات التي تم إدراجها في الطريق، ويؤدي هذا أيضًا إلى تجنب إضافة الحافة نفسها من اتجاه مختلف، على سبيل المثال: j ← i و i ← j.
ولكن إذا كان الموقع يمثل بداية الطريق ونهايته، فلابد أن تكون قيمة y الخاصة به هي أكبر وأصغر من قيم كل المواقع الباقية في الطريق، ونظرًا لاستحالة هذا الأمر، فستؤدي إضافة قيد الاتصال إلى استبعاد أية حلول بها طرق لا تشمل موقع الانطلاق والتوقف.
على سبيل المثال، فكِّر في الطريق 1 ← 2 ← 1 الوارد في الحل المكوَّن من طريقتين لنسخة مشكلة البائع المُتجوِّل الموضحة في الشكل السابق، حيث يتطلَّب قيد الاتصال أن تكون y1 ≥ y2 + 1 وأن تكون y2 ≥ y1 + 1، وهذا مستحيل، فلذلك سيتم استبعاد الحل.
في المقابل، يتطلَّب الحل الصحيح 0←3←4←1←2←0 أن تكون y4 ≥ y3 + 1 وأن تكون y1 ≥ y4 + 1 وأن تكون y2 ≥ y1 + 1، ويمكِن تحقيق ذلك بضبط قيم y كما يأتي: y3 = 0 وy4 = 1 وy1 = 2 وy2 = 3، ولا تنطبق قيود الاتصال على الانتقالات التي تشمل موقع startstop (الانطلاق والتوقف).
تجمع الدالة التالية كل الأشياء معًا لإنشاء خوارزمية حل برمجة الأعداد الصحيحة المختلطة لمشكلة البائع المتجوِّل:
يولِّد المقطع البرمجي التالي 100 نسخة من مشكلة البائع المُتجوِّل تشمل 8 مواقع وتتراوح المسافات فيها بين 5 و20، كما أنه يستخدِم خوارزمية حل القوة المُفرطة، وخوارزمية حل برمجة الأعداد الصحيحة المختلطة لحل كل حالة، ويُظهِر النسبة المئوية للأسلوبين اللذين أظهرا طريقين لهما المسافة نفسها:
تؤكد النتائج أن خوارزمية حل برمجة الأعداد الصحيحة المختلطة تُظهِر الحل الأمثل بنسبة 100% لكل نُسخ المشكلة، ويوضِّح المقطع البرمجي التالي سرعة خوارزمية حل برمجة الأعداد الصحيحة المختلطة من خلال استخدامها لحل 100 نسخة كبيرة تتضمن كل منها 20 موقعًا:
على الرغم من أن وقت التنفيذ الدقيق سيعتمد على قوة معالجة الجهاز الذي تستخدِمه لتنفيذ مفكرة جوبيتر، إلا أنه من المفترض أن يستغرق التنفيذ بضع دقائق لحساب الحل لجميع مجموعات البيانات المئة.
وهذا بدوره مذهل إذا تم الأخذ في الاعتبار أن عدد الطُرق المُمكِنة لكل نسخة من النُسخ المئة، هي: 19! = 121,645,100,000,000,000 طريقًا مختلفًا، ومثل هذا العدد الكبير من الطُرق يفوق بكثير قدرات أسلوب القوة المُفرطة، ومع ذلك فإنه عن طريق البحث الفعَّال في هذه المساحة الهائلة الخاصة بجميع الحلول المُمكِنة يمكِن لخوارزمية حل برمجة الأعداد الصحيحة المختلطة أن تجد الطريق الأمثل بسرعة.
وعلى الرغم من مزايا البرمجة الرياضية إلا أنها تملك قيودًا خاصة أيضًا، فهي تتطلَّب فهمًا قويًا للنمذجة الرياضية وقد لا تكون مناسبة للمشكلات المعقدة التي يصعب فيها التعبير عن الدالة الموضوعية والقيود بواسطة الصيغ الرياضية، وعلى الرغم من أن البرمجة الرياضية أسرع بكثير من أسلوب القوة المُفرطة إلا أنها قد تظل بطيئة جدًا بالنسبة لمجموعات البيانات الكبيرة، وفي مثل هذه الحالات يقدِّم الأسلوب الاستدلالي الموضَّح في الموضوعين السابقين بديلًا أكثر سرعة.
بإمكانك مراجعة محتوى موضوع “مشكلة تحسين المسار” بدايةً من عنوان “استخدام برمجة الأعداد الصحيحة المختلطة لحل مشكلة البائع المتجول” وحتى نهاية الموضوع، من خلال الرابط التالي:
إلى هنا يكون قد انتهى موضوع “مشكلة تحسين المسار“، لا تنسوا مراجعة نواتج التعلُّم أعلى المقال، وانتظرونا في الموضوع القادم!