مشكلة تخصيص الموارد - الذكاء الاصطناعي - ثالث ثانوي

250 .5 خوارزميات التحسين واتخاذ القرار سيتعرف الطالب في هذه الوحدة على عدة خوارزميات وتقنيات تساعده في إيجاد أكثر الحلول كفاءة لمشكلات التحسين المعقدة، كما سيتعلم طريقة عمل خوارزميات التحسين وخوارزميات اتخاذ القرار، وطريقة تطبيقها لحلّ مشكلات متعلقة بالعالم الواقعي ترتبط بتخصيص الموارد والجدولة وتحسين المسارات. أهداف التعلم بنهاية هذه الوحدة سيكون الطالب قادرًا على أن : و يصنف طرائق التحسين لمعالجة مشكلات معقدة. و يصف خوارزميات اتخاذ القرار المختلفة. يستخدم البايثون لحلّ مشكلات تخصيص الموارد المتعلقة بفرق العمل. يحل مشكلات الجدولة باستخدام خوارزميات التحسين. > يستخدم البايثون لحل مشكلات الجدولة. > يستخدم البرمجة الرياضية لحل مشكلات التحسين. V يعرف مشكلة حقيبة الظهر (Knapsack Problem). > يُعرف مشكلة البائع المتجول (Traveling Salesman Problem). الأدوات > مفكرة جوبيتر (Jupyter Notebook) Ministry of Education 2024-1446

رابط الدرس الرقمي الدرس الأول مشكلة تخصيص الموارد خوارزميات التحسين في الذكاء الاصطناعي Optimization Algorithms in Al و الله www.ien.edu.sa يُستخدم الذكاء الاصطناعي في مختلف الصناعات لاتخاذ قرارات تتسم بالكفاءة والدقة ، ويُعدُّ القيود (Constraints) : استخدام خوارزميات تعلُّم الآلة إحدى طرائق الذكاء الاصطناعي المستخدمة في اتخاذ القرارات. هي بمثابة شروط تقيد وكما تعلمت في الوحدة السابقة، فإن خوارزميات تعلم الآلة تقوم بتمكين الذكاء الاصطناعي من الحل، مثل الحد الأقصى التعلم بواسطة البيانات ومن ثَمّ القيام بالتنبؤات أو تقديم التوصيات. على سبيل المثال، في مجال لوزن الطرد الذي يمكن الرعاية الصحية، يُمكن استخدام الذكاء الاصطناعي للتنبؤ بنتائج المرضى والتوصية بخُطط علاجية بناءً على البيانات التي جمعت من حالات مماثلة. وفي مجال التمويل، يمكن استخدام الذكاء الاصطناعي في اتخاذ قرارات استثمارية بواسطة تحليل مجموعات كبيرة من البيانات شحنه. : (Objective Functions) المالية وتحديد الأنماط التي تبين المخاطر أو الفرص المحتملة. وعلى الرغم من أن خوارزميات الدوال الموضوعية تعلم الآلة تحظى بشعبية متزايدة إلا أنها ليست النوع الوحيد من خوارزميات الذكاء الاصطناعي التي يُمكن استخدامها في اتخاذ القرارات، فهناك طريقة أخرى تتمثل في استخدام خوارزميات هي معايير تحدد مدى اقتراب التحسين التي تُستعمل بوجه عام لإيجاد أفضل حل لمشكلة محدّدة بناءً على قيود وأهداف معينة. الحل المقدم من النتائج يهدف التحسين إلى تحقيق التصميم الأفضل بالنسبة لمجموعة من المعايير أو القيود ذات الأولوية، المطلوبة، مثل تقليل مسافة وتشمل تعزيز عوامل معينة مثل: الإنتاجية، والموثوقية، وطول العمر، والكفاءة، وفي الوقت نفسه السفر الشاحنة توصيل. تقليل عوامل أخرى مثل: التكاليف، والفاقد ، والتوقف عن العمل، والأخطاء. مشكلات التخصيص Allocation Problems تُعدُّ مشكلات التخصيص من مشكلات التحسين الشائعة؛ ففيها يتم تخصيص مجموعة من الموارد مثل: العمال، أو الآلات، أو الأموال لمجموعة من المهام أو المشاريع بأعلى كفاءة ممكنة، وتنشأ هذه المشكلات في مجموعة واسعة من المجالات بما فيها التصنيع والخدمات اللوجستية وإدارة المشاريع والتمويل، ويُمكن صياغتها بطرائق مُختلفة بناءً على قيودها وأهدافها. في هذا الدرس ستتعرّف على مشكلات التخصيص وخوارزميات التحسين المستخدمة لحلّها. الدالة الموضوعية (Objective Function) هي زيادة عدد العناصر المعالجة والمرسَلة. شكل 5.1: استخدام خوارزميات التحسين في مستودع 251 وزارة التعليم Ministry of Education 2024-1446 www 14 E wwwww လ القيد (Constraint) هو تحديد الوزن. LLFII TIFIL

252 بعد ذلك، ستشاهد عددًا من الأمثلة، ولكل مثال منها قيود ودوال موضوعية خاصة به. القيود الدوال الموضوعية - وضع أُطر زمنية للتوصيل؛ لضمان توصيل الطرود وفق تقليل (Minimizing) وقت التوصيل ومسافة إطار زمني محدد. السفر؛ لخفض التكلفة وتحسين الكفاءة. شركات النقل توفير سعة مركبات التوصيل؛ لضمان استخدام المركبة - زيادة Maximizing) عدد الطرود في كل مركبة؛ المناسبة لكل عملية توصيل، ومقدرتها على حمل الكمية اللازمة من الطرود. لتقليل عدد الرحلات اللازمة - زيادة Maximizing رضا العملاء من خلال - توفير السائقين والموظفين ، ومراعاة تقسيم أوقات عملهم؛ توصيل الطرود في وقت محدد وفق إطار زمني لضمان كفاءة العمل، وعدم تكليفهم بأعمال فوق قدرتهم. محدد. تَوَفُّر الطائرات وجداول الصيانة؛ لضمان إجراء الصيانة الجيدة لها، ومدى جاهزيتها للرحلات قيود مراقبة الحركة الجوية؛ لتجنب التأخير وتقليل جدولة استهلاك الوقود. خطوط الطيران - - تقليل (Minimizing) تأخر رحلات الطيران أو إلغائها؛ لزيادة رضا العملاء. زيادة (Maximizing استغلال الطائرات؛ لتقليل التكاليف وتحسين الكفاءة. - مراعاة حاجة المسافر وتفضيلاته؛ لجدولة رحلات الطيران الأنسب للمسافرين. - - زيادة (Maximizing) الإيرادات من خلال عمل عروض خاصة على رحلات الطيران عالية الطلب وتعديل أسعار التذاكر بناءً على الطلب. سعة الإنتاج والمهلة الزمنية؛ لضمان تصنيع المنتجات في - تقليل (Minimizing) تكاليف الإنتاج من خلال الوقت المناسب. توفير المواد وسعة التخزين؛ لتجنُّب نفاد المخزون أو المصنعون تكدسه. تقلبات الطلب؛ لتعديل جداول الإنتاج بناء على التغيرات في طلبات العملاء. - - تحسين استخدام الموارد وتقليل الفاقد. زيادة Maximizing) كفاءة الإنتاج من خلال جدولة دورات الإنتاج؛ لتقليل أوقات التجهيز والتبديل. زيادة (Maximizing) رضا العملاء من خلال ضمان توفير المنتجات عند الحاجة إليها. سعة تخزين محدودة تتطلب إدارة دقيقة لمستويات - زيادة Maximizing) الربح من خلال ضمان وجود مستويات كافية من مخزون السلع ذات هامش المخزون. - فترات مهلة التسليم وتنوّعها، التي تؤثر على مقدار الربح العالي. المخزون الذي يجب الاحتفاظ به في أي وقت. إدارة المخزون في الشركات - توفير ميزانية؛ لشراء مخزون. - مراعاة الطلب على الكهرباء وتقلباته. شركات الطاقة - توفر المواد الخام وموارد الطاقة الضرورية. قيود النقل والتوزيع مثل: سعة الشبكة والمسافة بين مصانع توليد الطاقة والمستهلكين. - - تقليل (Minimizing) تكاليف التخزين من خلال تحسين مستويات المخزون بناءً على توقعات الطلب. زيادة (Maximizing) رضا العملاء من خلال ضمان توفر المنتجات المناسبة في الوقت المناسب وفي المكان المناسب، وبتقليل نفاد المخزون والتأخير والمشكلات الأخرى التي قد تؤثر على تجربة العملاء. تقليل Minimizing) تكلفة توليد الكهرباء وتوزيعها من خلال تحسين استخدام الموارد. تقليل ( Minimizing) هدر الطاقة وفشل الخدمات. وزارة التعليم Ministry of Education 2024-1446

253 وزارة التعليم Ministry of Education 2024-1446 يُمكن نمذجة كل التطبيقات الواردة سابقًا في صورة مشكلات معقدة لها عدد كبير من الحلول الممكنة. على سبيل المثال، فكّر في مشكلة تخصيص الموارد المعهودة التي تركّز على تشكيل فريق، حيث تنشأ المشكلة عندما يكون لديك: مجموعة كبيرة من العمّال يمتلكون مهارات مختلفة. مُهمَّة تتطلب مجموعةً فرعية محدَّدة من المهارات لأجل إكمالها. . ويتمثل الهدف في تكوين فريق بأقل عدد ممكن من العمال، مع الالتزام في الوقت نفسه بالقيد (Constraint) الذي ينص على توفّر جميع المهارات المطلوبة في أعضاء الفريق؛ لأداء المهمة. على سبيل المثال، تخيل سيناريو بسيطًا يوجد فيه خمسة عمال: M العامل الأول المهارات: م1، م3، م6 العامل الثاني المهارات: م2 م3 العامل الثالث المهارات: م1 م2 ، م3 العامل الرابع المهارات: م2، م4 العامل الخامس المهارات: م5 . تتطلب المهمَّة المراد إنجازها كل المهارات: م1 ، م2، م3 ، م4، م5، م6. القوة المفرطة (Brute-force) : يتمثل الحلّ القائم على القوة المفرطة (Brute Force ) في أخذ كل فِرق العمّال الممكنة في الاعتبار، والتركيز على الفرق التي تتوفّر فيها جميع المهارات المطلوبة، واختيار الفريق الأقل عددًا ، وعلى افتراض أن كل فريق يتكون من شخص واحد على الأقل، فيُمكنك أن تُشكّل واحدًا وثلاثين فريقًا مختلفًا يتكون كل منهم من خمسة عمال. هي طريقة من طرائق حلّ المشكلات تتضمن التجريب المنهجي لجميع الحلول الممكنة للمشكلة بهدف الوصول إلى الحل الأمثل، بغض النظر عن التكلفة الحاسوبية. تكوينها هو: • بالنسبة للفريق المكوّن من عامل واحد ، هناك خمس طرائق لاختيار عامل واحد من بين العمال الخمسة. العدد الإجمالي للفرق بالنسبة للفريق المكوّن من عاملين اثنين ، هناك عشر طرائق لاختيار عاملين من بين العمال الخمسة. المختلفة التي يُمكنك بالنسبة للفريق المكون من ثلاثة عمّال، هناك عشر طرائق لاختيار ثلاثة عمال من بين العمال الخمسة. بالنسبة للفريق المكون من أربعة عمّال، هناك خمس طرائق لاختيار أربعة عمال من بين العمال الخمسة. ويمكن حساب العدد بالنسبة للفريق المكون من خمسة عمّال ، هناك طريقة واحدة لاختيار كل العمال الخمسة. يكشف تقييم كل الفرق الإحدى والثلاثين عن أفضل حلّ ممكن يتمثل في تكوين فريق يشمل العمّال: الأول والرابع والخامس وسيغطي هذا الفريق كل المهارات الست المطلوبة، وسيشمل الفريق ثلاثة عمّال ، ولا يمكن تغطية كل المهارات بفريق يشتمل على عدد عمال أقل من ذلك، مما يجعل هذا الحلّ هو الحل العامل الأول الأمثل (Optimal Solution). وهناك حلّ آخر يتمثل في تكوين فريق يشمل العمّال: الأول والثاني والثالث والخامس، وعلى الرغم من أن هذا الفريق يغطي كل المهارات الست إلا أنه يتطلب أيضًا عمالًا أكثر مما يجعل هذا الحلّ ممكنًا، ولكنه العامل الأول ليس الحل الأمثل. 5+10+10+5+1=31 أيضًا وفقًا للمعادلة: العامل الرابع .25 -1 العامل الخامس المهارات: م1، م3، م6 المهارات: م2، م4 المهارات: م5 العامل الثاني العامل الثالث العامل الخامس المهارات م1، م3 ، م 6 المهارات م 2 م 3 المهارات ،م1 م2 م3 المهارات م5

الطبيعة الخاصة بأسلوب القوة المفرطة تضمن دائمًا إيجاد الحل الأمثل، متى أمكن ذلك، ولكن فحص كل الفرق الممكنة يُعد عملية مكلّفة حاسوبيًا ، فمثلًا: إذا كان لديك ستة عمّال، فسيكون عدد الفرق الممكنة: 63 = 1 - 26 . • إذا كان لديك عشرة عمال، فسيكون عدد الفرق الممكنة: 1,023 = 1 – 210 . إذا كان لديك خمسة عشر عاملًا، فسيكون عدد الفرق الممكنة: 32,767 = 1 – 215 . إذا كان لديك عشرون عاملًا، فسيكون عدد الفرق الممكنة: 1,048,575 = 1 – 220 . إذا كان لديك خمسون عاملًا، فسيكون عدد الفرق الممكنة : 1,125,899,906,842,623 = 1 - 250 . من الواضح في مثل هذه المواقف أن حصر عدد الفرق لكل الحلول الممكنة ليس حتى بالنسبة لعدد معتدل من 50 عاملًا، خيارًا عمليًّا ، ولذلك تم اقتراح طرائق تحسين أخرى لمعالجة المشكلات المعقدة فإن عدد الفرق المحتملة يتضخم إلى أكثر عن طريق البحث في خيارات الحلول الممكنة بأسلوب أكثر كفاءة من أسلوب القوة المفرطة، ويُمكن بوجه عام تصنيف هذه الطرائق في ثلاث فئات: طرائق الاستدلال Heuristic Methods) البرمجة القيدية (Constraint Programming) البرمجة الرياضية ( Mathematical Programming) الحل الأمثل Optimal Solution من كوادريليون (1015=Quadrillion). من الممكن أن تكون هناك العديد من الحلول المثلى، كأن يكون لديك عدة فرق تشمل ثلاثة عمّال وبإمكانها أن تستوفي كل المهارات المطلوبة، كما أنه من الممكن ألا يوجد حلّ لبعض المشكلات، على سبيل المثال: إذا كانت المهمة تتطلب المهارة السابعة وهي لا تتوفّر في أي عامل من العمال، فلن يكون هناك حل للمشكلة. طرائق الاستدلال (Heuristic Methods) + الإيجابيات تتميز الاستدلالات بالكفاءة الحاسوبية، تقوم طرائق الاستدلال - Heuristic Methods) في العادة على التجربة ويُمكنها أن تتناول المشكلات المعقدة، أو البديهة، أو الفطرة السليمة، وليس على التحليل الرياضي الدقيق، ويُمكن كما يمكنها أن تجد حلولا ذات جودة استخدامها لإيجاد حلول جيدة بشكل سريع، ولكنها لا تضمن الوصول إلى الحلّ عالية إذا استخدمت لها استدلالات الأمثل ( أفضل حل يمكن الحصول عليه ) ، ومن الأمثلة على الخوارزميات الاستدلالية معقولة. ، الخوارزميات الجشعة ( Greed Algorithms ، ومحاكاة التلدين (Simulated Annealing) ، والخوارزميات الجينية ( Genetic Algorithms - السلبيات وتحسين مستعمرة النمل (Ant Colony Optimization) . تُستخدم هذه الطرائق لا تضمن الوصول إلى الحل الأمثل، كما . في العادة لحلّ المشكلات المعقدة التي تستغرق وقتًا حاسوبيًا طويلًا جدًّا، ولكن لا أن بعض الاستدلالات تتطلب ضبطـا يُمكنها إيجاد حلول دقيقة، وستتعلّم في الدروس القادمة المزيد عن هذه الخوارزميات كبيرًا حتى تُؤدي إلى نتائج جيدة. + الإيجابيات يُمكن للبرمجة القيدية أن تتعامل مع البرمجة القيدية Constraint Programming) البرمجة القيدية (Constraint Programming - CP) تحلّ مشكلات قيود معقدة وأن تجد أفضل الحلول التحسين عن طريق نمذجة القيود وإيجاد حلّ يخضع لجميع القيود، وهذا الأسلوب مفيد بشكل خاص في المشكلات التي بها عدد كبير من القيود أو التي السلبيات تتطلب تحسين عدة أهداف. يُمكن أن تكون هذه الطرائق مكلّفة حاسوبيًا في المشكلات الكبيرة. وزارة التعليم Ministry of Education 2024-1446 254

255 البرمجة الرياضية (Mathematical Programming) + الإيجابيات تتعامل البرمجة الرياضية مع مجموعة واسعة من مشكلات التحسين وهي غالبًا تضمن الوصول إلى الحل الأمثل. - السلبيات البرمجة الرياضية - Mathematical Programming) هي مجموعة من التقنيات التي تستخدم نماذج رياضية؛ لحلّ مشكلات التحسين ، وتشمل: البرمجة الخطية (Linear Programming) ، والبرمجة الرباعية (Quadratic Programming)، والبرمجة غير الخطية (Nonlinear Programming) وبرمجة الأعداد الصحيحة المختلطة (Mixed-Integer Programming) ، وتُستخدم هذه التقنيات على نطاق واسع في الكثير من المجالات بما فيها علم الاقتصاد والهندسة وعمليات البحث. تلعب يُعدُّ كلٌّ من التكلفة الحاسوبية أساليب البرمجة الرياضية دورًا مهما في التعلُّم العميق (Deep Learning) ، وتمتلك للمشكلات الكبيرة وتعقيد نماذج التعلم العميق عددًا كبيرًا من المعاملات التي تحتاج أن تتعلّم من البيانات، حيث إنشاء الصيغة الرياضية تُستخدم خوارزميات التحسين لتعديل مُعاملات النموذج من أجل تقليل دالة التكلفة التي المناسبة مرتفعين بالنسبة تقيس الفرق بين مخرجات النموذج المتنبأ بها والمخرجات الصحيحة. تم تطوير العديد لمشكلات العالم الواقعي من خوارزميات التحسين الخاصة بنماذج التعلّم العميق مثل: خوارزمية آدم (Adam) ، وخوارزمية الاشتقاق التكيفي (AdaGrad) ، وخوارزمية نشر متوسط الجذر التربيعي الله المعقدة. .(RMSprop) مثال عملي : تحسين مشكلة تشكيل الفريق A Working Example: Optimization for the Team-Formation Problem سيوضّح هذا الدرس استخدام خوارزمية القوة المفرطة (Brute-Force Algorithm ) ، والخوارزمية الاستدلالية الجشعة (Greedy Heuristic Algorithm) لحلّ مشكلة اتخاذ القرار المرتكزة على مشكلة تخصيص الموارد القائمة على الفريق والتي تم وصفها سابقًا، ، بعد ذلك ستتم مقارنة نتائج هاتين الخوارزميتين. (Greedy Heuristic Algorithm) يُمكن استخدام الدالة التالية لإنشاء أمثلة عشوائية لمشكلة تشكيل الفرق، وتسمح هذه الدالة للمستخدم أن يُحدِّد أربعة مُعاملات هي: العدد الإجمالي الخوارزمية الاستدلالية الجشعة للمهارات التي يجب أن تؤخذ بعين الاعتبار، والعدد الإجمالي للعمال المتوفرين، وعدد المهارات التي يجب أن تتوفّر في أعضاء الفريق بشكل هي أسلوب استدلالي لحل المشكلات جماعي حتى ينجزوا الهِمَّة، والعدد الأقصى للمهارات التي يمكن أن يمتلكها وفيه تقوم الخوارزمية ببناء الحلّ خطوةً خطوةً، وتختار الخيار الأمثل وبعد كل عامل. ذلك، تقوم الدالة بإنشاء وإظهار مجموعة عمّال لديهم عدة مهارات مُختلفة، وعدة مهارات مطلوبة، وتستخدم هذه الدالة المكتبة الشهيرة Random التي يُمكن استخدامها في إخراج عيّنة أعداد عشوائية من مجموعة أعداد معيّنة أو عناصر عشوائية من قائمة معينة. دانگ محليا في كل مرحلة، حتى تصل في النهاية إلى حل شامل ونهائي. وزارة التعليم Ministry of Education 2024-1446 import random def create_problem_instance(skill_number, #total number of skills worker_number, # total number of workers required_skill_number, # number of skills the team has to cover max_skills_per_worker #max number of skills per worker ):

256 # creates the global list of skills s1, s2, s3, ... skills = ['s' + str(i) for i in range(1, skill_number+1)] worker_skills = dict() # dictionary that maps each worker to their set of skills for i in range(1, worker_number+1): # for each worker # makes a worker id (w1, w2, w3, ...) worker_id = 'w' + str(i) # randomly decides the number of skills that this worker should have (at least 1) my_skill_number = random.randint(1, max_skills_per_worker) # samples the decided number of skills my_skills = set(random.sample(skills, my_skill_number)) # remembers the skill sampled for this worker worker_skills[worker_id] = my_skills #randomly samples the set of required skills that the team has to cover required_skills = set(random.sample(skills, required_skill_number)) # returns the worker and required skills return {'worker_skills':worker_skills, 'required_skills':required_skills} ستقوم الآن باختبار الدالة الواردة سابقًا من خلال إنشاء نسخة من مشكلة معطياتها كالتالي: عشر مهارات إجمالية، وستة عمّال، وتتطلب خمس مهارات كحد أقصى لكل عامل. x10 تحتاج المشكلة إلى عشر مهارات إجمالية x5 x6 عمال مهارات مطلوبة شكل :52 رسم توضيحي للمثال الخاص بالمشكلة بسبب الطبيعة العشوائية للدالة، ستحصل على نسخة مختلفة من المشكلة في كل مرة تقوم فيها بتشغيل هذا المقطع البرمجي. x5 بحد أقصى خمس مهارات لكل عامل وزارة التعليم Ministry of Education 2024-1446

257 وزارة التعليم Ministry of Education 2024-1446 # the following code represents the above test sample_problem = create_problem_instance(10, 6, 5, 5) # prints the skills for each worker for worker_id in sample_problem[ 'worker_skills']: print(worker_id, sample_problem['worker_skills'][worker_id]) print() # prints the required skills that the team has to cover print('Required Skills:', sample_problem['required_skills']) w1 {'s10'} w2 {'s2', 's8', 's5', 's6'} w3 {'s7', 's2', 's4', 's5', 's1'} W4 {'s9', 's4'} w5 {'s7', 'S4'} w6 {'s7', 's10'} Required Skills: {'s6', 'S8', 'S7', 'S5', '59'} عدد ممكن تتمثل الخطوة التالية في إنشاء خوارزمية حل (Solver) ، وهي خوارزمية تحسين يُمكنها أن تحدِّد أقل : لفريق العمال الذي يُمكن اعتماده لإستيفاء كل المهارات المطلوبة. اتخاذ القرار بخوارزمية القوة المفرطة Decision Making with a Brute-Force Algorithm ستطبق أول خوارزمية حلّ أسلوب القوة المفرطة الذي يعتمد على التعداد الشامل لكل الفرق الممكنة وأخذها بعين الاعتبار، وستستخدم هذه الخوارزمية أدوات combinations توافيق من وحدة itertools؛ لتوليد كل الفرق المكنة ذات العدد المحدد. سيتم توضيح الأداة بالمثال البسيط أدناه: # used to generate all possible combinations in a given list of elements from itertools import combinations L = ['w1', 'w2', 'w3', 'w4'] print('pairs', list(combinations(L, 2))) # all possible pairs print('triplets', list(combinations(L, 3))) # all possible triplets pairs [('w1', 'w2'), ('w1', 'w3'), ('w1', 'w4'), ('w2', 'w3'), ('w2', 'w4'), ('w3', 'w4')] triplets [('w1', 'w2', 'w3'), ('w1', 'w2', 'w4'), ('w1', 'w3', 'w4'), ('w2', 'w3', 'w4')]

وزارة التعليم Ministry of Education 2024-1446 بعد ذلك، يُمكن إنشاء الدالة التالية لحلّ مشكلة تكوين الفريق بأسلوب القوة المفرطة، وهذه الخوارزمية تأخذ بعين الاعتبار جميع أحجام الفرق الممكنة، وتنشىء الفرق بناءً على الأعداد الممكنة، ثم تحصر الفرق التي تستوفي كل المهارات المطلوبة وتحدّد الفريق الأقل عددًا: def brute_force_solver(problem): worker_skills = problem[ 'worker_skills ' ] required_skills = problem[ 'required_skills'] worker_ids = list(worker_skills.keys()) # gets the ids of all the workers worker_num = len(worker_ids) # total number of workers all_possible_teams = [] # remembers all possible teams best_team = None #remembers the best (smallest) team found so far #for each possible team size (singles, pairs, triplets, ...) for team_size in range(1, worker_num+1): # creates all possible teams of this size teams = combinations(worker_ids, team_size) for team in teams: # for each team of this size skill_union = set() #union of skills covered by all members of this team for worker_id in team: #for each team member # adds their skills to the union skill_union.update(worker_skills[worker_id]) # if all the required skills are included in the union if required_skills.issubset(skill_union): # if this is the first team that covers all required skills # or this team is smaller than the best one or if best_team == None or len(team) < len(best_team): best_team team #makes this team the best one = return best_team #returns the best solution من الممكن ألا يكون هناك حلّ لنسخة المشكلة الواردة، فإذا كانت مجموعة المهارات المطلوبة تشمل مهارة لا يمتلكها و أي عامل من العمّال المتواجدين ، فلن تجد طريقة لإنشاء فريق يغطي كل المهارات ، وفي مثل هذه الحالات ستظهر بعدم وجود حلّ. الخوارزمية المذكورة سابقًا النتيجة يُمكنك الآن استخدام المقطع البرمجي التالي لاختبار خوارزمية الحلّ بالقوة المفرطة وفقًا للمثال الذي تم إنشاؤه سابقا: # uses the brute-force solver to find the best team for the sample problem best_team = brute_force_solver(sample_problem) print(best_team) ('w2', 'w3', 'w4') 258

259 وزارة التعليم Ministry of Education 2024-1446 من المؤكد أن خوارزمية الحلّ بالقوة المفرطة ستجد أفضل حلّ ممكن، أي: أقلّ الفِرق عددًا طالما أن هناك حلٌّ ممكن، ولكن كما تم مناقشته في بداية هذا الدرس فإن طبيعة الخوارزمية الشمولية تُؤدي إلى زيادة هائلة في التكلفة الحاسوبية المشكلة. حجم كلما زاد يُمكن توضيح ذلك من خلال إنشاء نُسخ لمشكلات متعددة من حيث تزايد عدد العمال، ويُمكن استخدام المقطع البرمجي التالي لتوليد نسخ متنوعة من مشكلة تكوين الفريق، حيث يتنوع عدد العمّال ليكون: 5 و 10 و 15 و20 ، ثم يتم توليد 100 نسخة بعدد العمّال، وتشمل كل النسخ المهارات الإجمالية العشر ، والمهارات الثمان المطلوبة، والخمس مهارات كحد أقصى لكل عامل: [] #5 workers problems_with_5_workers problems_with_10_workers = [] #10 workers problems_with_15_workers = [] # 15 workers problems_with_20_workers = [] #20 workers for i in range(100): #repeat 100 times problems_with_5_workers.append(create_problem_instance(10, 5, 8, 5)) problems_with_10_workers.append(create_problem_instance(10, 10,8, 5)) problems_with_15_workers.append(create_problem_instance(10, 15, 8,5)) problems_with_20_workers.append(create_problem_instance(10, 20, 8,5)) تقبل الدالة التالية قائمة بنُسخ المشكلة وخوارزمية الحلّ بالقوة المفرطة، وتُستخدم هذه الخوارزمية لإجراء العمليات الحسابية ثم استخراج الحلّ لجميع النسخ، كما أنها تُسجل الوقت الإجمالي المطلوب (بالثواني) لحساب الحلول وكذلك العدد الإجمالي للنسخ التي يمكن إيجاد حلّ منها: import time def gets_solutions(problems,solver): total_seconds = 0 # total seconds required to solve all problems with this solver total_solved = 0 # total number of problems for which the solver found a solution solutions = [ ] # solutions returned by the solver for problem in problems: start_time = time.time() # starts the timer best_team = solver(problem) # computes the solution end_time = time.time() # stops the timer solutions.append(best_team) #remembero the solution total_seconds += end_time-start_time # computes total elapsed time if best_team != None: #if the best team is a valid team total_solved += 1 print("Solved {} problems in {} seconds".format(total_solved, return solutions total_seconds))

يستخدم المقطع البرمجي التالي هذه الدالة وخوارزمية الحلّ بالقوة المفرطة لحساب الحلول الممكنة لمجموعات البيانات التي تم إنشاؤها سابقًا والمكونة من workers ( خمسة عمال ) ، وworkers-10 (عشرة _عمال)، وworkers-15 ( خمسة عشر عاملًا ) ، وworkers-20 (عشرين عاملًا ) : brute_solutions_5 = gets_solutions(problems_with_5_workers, = solver brute_force_solver) brute_solutions_10 = gets_solutions(problems_with_10_workers, solver = brute_force_solver) brute_solutions_15 = gets_solutions(problems_with_15_workers, solver = brute_force_solver) brute_solutions_20 = gets_solutions(problems_with_20_workers, solver = brute_force_solver) Solved 23 problems in 0.0019948482513427734 seconds Solved 80 problems in 0.06984829902648926 seconds Solved 94 problems in 2.754629373550415 seconds Solved 99 problems in 109.11902689933777 seconds على الرغم من أن الأعداد المطلوبة سُجلت بواسطة الدالة ( )gets_solutions إلا أنها ستكون متفاوتة نظرا للطبيعة العشوائية لمجموعات البيانات، وسيكون هناك نمطان ثابتان على الدوام هما: • زيادة عدد العمّال تُؤدي إلى عدد أكبر من نُسخ المشكلات التي من الممكن إيجاد حلّ لها ، وهذا النمط من الحلول معقول ومتوقع؛ لأن وجود عدد كبير من العمال يزيد من احتمال وجود عامل واحدٍ على الأقل يمتلك مهارة واحدة مطلوبة ضمن مجموعة العمّال المتاحة. زيادة عدد العمّال يؤدي إلى زيادة كبيرة ( أُسيَّة) في الزمن الحاسوبي، وهذا متوقع حسب التحليل الذي تم إجراؤه في بداية هذا الدرس، وبالنسبة لمجموع العمّال ممن هم بعدد خمسة وعشرة، وخمسة عشر ، وعشرون عاملًا، فإن عدد الفِرق الممكنة يساوي: 31 ، 1023 ، 32767 ، و1048575 على الترتيب. بصفة عامة، وبالنظر إلى عدد العمّال المعطى ، فإن عدد الفرق الممكنة يساوي 1-2 ، وهذا العدد سيصبح كبيرًا لتقييمه حتى بالنسبة للقيم الصغيرة لـ N . كذلك بالنسبة لأي مشكلة بسيطة بها قيد واحد ( يغطي جميع المهارات المطلوبة) وهدف واحد ( تقليل حجم الفريق) ، فإن القوة المفرطة قابلة للتطبيق فقط على مجموعات البيانات الصغيرة جدا، وذلك بالتأكيد ليس حلا عمليًّا لأي من مشكلات التحسين المعقدة التي نواجها في الواقع والتي أشرنا إليها في بداية هذا الدرس. اتخاذ القرار باستخدام خوارزمية استدلالية جشعة Decision Making with a Greedy Heuristic Algorithm تتعامل الدالة التالية مع هذا القيد بواسطة تنفيذ خوارزمية تحسين تعتمد على الأسلوب الاستدلالي الجشع، حيث تقوم الخوارزمية تدريجيًا بتكوين الفريق عن طريق إضافة عضو واحد في كل مرة، فالعضو الذي أضيف مؤخرًا يكون دائمًا العضو الذي يمتلك معظم المهارات التي لم توجد في سابقه، وتستمر العملية حتى تستوفي جميع المهارات المطلوبة. هو الدالة الاستدلالية الجشعة (Greedy Heuristic المستخدمة في هذا المثال هي معيار لاختيار عامل يتوفر فيه أكبر عدد من المهارات التي تُستوفى في الفريق إلى الآن، ويمكن استخدام دالة استدلالية أخرى، مبنية على إضافة العامل الذي يتوفر فيه العدد الأكبر من المهارات أولا. وزارة التعليم Ministry of Education 2024-1446 260

261 وزارة التعليم Ministry of Education 2024-1446 def greedy_solver(problem): worker_skills = problem['worker_skills'] required_skills = problem['required_skills'] # skills that still have not been covered uncovered_required_skills = required_skills.copy() best team = [] # remembers only the skills of each worker that are required but haven't been covered yet uncovered_worker_skills = {} for worker_id in worker_skills: # remembers only the required uncovered skills that this worker has uncovered_worker_skills [worker_id] = worker_skills [worker_id]. intersection(uncovered_required_skills) # while there are still required skills to cover while len(uncovered_required_skills) > 0: best_worker_id = None # the best worker to add next # number of uncovered skills required for the best worker to cover best_new_coverage = 0 for worker_id in uncovered_worker_skills: # uncovered required skills that this worker can cover تُظهر الدالة ()intersections مجموعة جديدة تحتوي فقط على المهارات المشتركة من جميع مهارات العمال الموجودة في worker_skills ، والمهارات المطلوبة التي لم تستوف في .uncovered_worker_skills my_uncovered_skills = uncovered_worker_skills [worker_id] # if this worker can cover more uncovered required skills than the best worker so far if len(my_uncovered_skills) > best_new_coverage: best_worker_id=worker_id # makes this worker the best worker best_new_coverage=len (my_uncovered_skills) if best_worker_id != None: # if a best worker was found best team.append(best_worker_id) # adds the worker to the solution #removes the best worker's skills from the skills to be covered uncovered_required_skills = uncovered_required_skills - uncovered_worker_skills [best_worker_id] for worker_id in uncovered_worker_skills: # remembers only the required uncovered skills that this worker has uncovered_worker_skills [worker_id] = uncovered_worker_skills [worker_id].intersection (uncovered_required_skills) else: # no best worker has been found and some required skills are still uncovered return None # no solution could be found return best_team

وزارة التعليم Ministry of Education 2024-1446 لا تأخذ خوارزمية الحلّ الجشعة كل الفِرق الممكنة بعين الاعتبار ولا تضمن إيجاد الحل الأمثل، ولكنها كما هو موضّح أدناه أسرع بكثير من خوارزمية الحلّ التي تعتمد علي القوة المفرطة، ومع ذلك يُمكنها أن تُنتج حلولا جيدة، هي في الغالب حلول مثلى، ومن المؤكد أن تجد هذه الطريقة حلا إذا كان موجودًا. يستخدم المقطع البرمجي التالي خوارزمية الحلّ الجشعة لحساب حلول مجموعات البيانات: workers-5 (خمسة عمال ) ، و workers-10 ( عشرة عمال ) ، و workers-15 ( خمسة عشر عاملًا ) ، وworkers-20 (عشرين عاملًا) التي تم استخدامها سابقًا لتقييم خوارزمية الحلّ بالقوة المفرطة: greedy_solutions_5 = = solver gets_solutions(problems_with_5_workers, greedy_solver) greedy_solutions_10 = gets_solutions(problems_with_10_workers, solver = greedy_solver) greedy_solutions_15 = gets_solutions(problems_with_15_workers, solver = greedy_solver) greedy_solutions_20 = gets_solutions(problems_with_20_workers, solver = greedy_solver) Solved 23 problems in 0.0009970664978027344 seconds Solved 80 problems in 0.000997304916381836 seconds Solved 94 problems in 0.001995086669921875 seconds Solved 99 problems in 0.0019943714141845703 seconds والآن يتضح الفرق في السرعة بين الخوارزميتين؛ حيث يُمكن تطبيق خوارزمية الحلّ الجشعة على النسخ المتعلقة بالمشكلات الكبيرة جدًا، كما في المثال التالي: # creates 100 problem instances of a team formation problem with 1000 workers problems_with_1000_workers = [] for i in range(100): #repeats 100 times problems_with_1000_workers.append(create_problem_instance(10, 1000, 8, 5)) # solves the 100-worker problems using the greedy solver greedy_solutions_1000 = gets_solutions(problems_with_1000_workers, solver = greedy_solver) Solved 100 problems in 0.09574556350708008 seconds 262

263 وزارة التعليم Ministry of Education 2024-1446 مقارنة الخوارزميات Comparing the Algorithms بعد أن تم توضيح ميزة السرعة لخوارزمية الحلّ الاستدلالية الجشعة، تتمثل الخطوة التالية في التحقق من جودة الحلول التي تُنتجها ، حيث تقبل الدالة التالية الحلول التي أنتجتها الخوارزمية الجشعة وخوارزمية القوة المفرطة على نفس مجموعة نُسخ المشكلات، ثم تبيّن النسب المئوية للنسخ التي تقوم كلتا الخوارزميتين بذكر الحل الأمثل لها ( الفريق الأقل عددا ) : def compare(brute_solutions,greedy_solutions): total_solved = 0 same_size = 0 for i in range(len(brute_solutions)): if brute_solutions[i] != None: # if a solution was found total_solved += 1 # if the solvers reported a solution of the same size if len(brute_solutions[i]) == len(greedy_solutions[i]): same_size += 1 return round(same_size / total_solved, 2) يُمكن الآن استخدام الدالة ( )compare المقارنة فاعلية الخوارزميتين المطبقتين على الخمسة عمال، والعشرة عمال ، والخمسة عشر عاملًا، والعشرين عاملًا. print(compare(brute_solutions_5,greedy_solutions_5)) print(compare(brute_solutions_10,greedy_solutions_10)) print(compare(brute_solutions_15, greedy_solutions_15)) print(compare(brute_solutions_20,greedy_solutions_20)) 1.0 0.82 0.88 0.85 توضّح النتائج أن الخوارزمية الاستدلالية الجشعة يُمكنها أن تجد باستمرار الحلّ الأمثل لحوالي 80 أو أكثر من كل نُسخ المشكلات القابلة للحلّ. وفي الواقع، يُمكن التحقق بسهولة من أن حجم الفريق الذي تنتجه الخوارزمية الاستدلالية الجشعة حتى في النسخ التي تفشل في إيجاد الحلول المثلى لها يكون قريبًا جدًا من حجم أفضل فريق ممكن. إذا تمت إضافة ذلك إلى ميزة السرعة الهائلة ، تجد أن الخوارزمية الاستدلالية خيار عملي أكثر للتطبيقات الواقعية وستكتشف في الدرس التالي تقنيات تحسين أكثر ذكاءً، وستتعرّف على كيفية تطبيقها على مشكلات مختلفة.

وزارة التعليم Ministry of Education 2024-1446 تمرينات ما مزايا وعيوب استخدام كلِّ من: خوارزمية القوة المفرطة والخوارزمية الاستدلالية الجشعة في حل مشكلات التحسين ؟ 1 2 حلل طريقة استخدام الخوارزميات الاستدلالية الجشعة لإيجاد الحلول المثلى في مشكلات التحسين. 264

265 3 أنشئ خوارزمية حلّ جشعة لتحسين مشكلة تكوين أعضاء فريق من خلال إكمال المقطع البرمجي التالي بحيث تستخدم خوارزمية الحلّ الاستدلالية الجشعة لتكليف أعضاء الفريق بالمهمة : وزارة التعليم Ministry of Education 2024-1446 def greedy_solver (problem): worker_skills-problem['worker_skills'] #worker skills for this problem required_skills=problem['required_skills'] # required skills for this problem uncovered_required_skills = required_skills. best team [ ] # best solution uncovered_worker_skills={} for worker_id in worker_skills: () # skills not covered uncovered_worker_skills [worker_id] = worker_skills[worker_id]. (uncovered_required_skills) while len(uncovered_required_skills) > 0: best_worker_id= # the best worker to add next best_new_coverage=0 #number of uncovered required skills covered by the best worker for worker_id in uncovered_worker_skills: # for each worker my_uncovered_skills-uncovered_worker_skills[worker_id] # if this worker can cover more uncovered required skills than the best worker so far len(my_uncovered_skills)>best_new_coverage: if best_worker_id=worker_id #makes this worker the best worker best_new_coverage= (my_uncovered_skills) if best_worker_id != : # if a best worker was found (best_worker_id) # adds the worker to the solution best_team. #removes the best worker's skills from the skills to be covered uncovered_required_skills-uncovered_required_skills - uncovered_ worker_skills [best_worker_id] # for each worker for worker_id in uncovered_worker_skills: # remembers only the required uncovered skills that this worker has uncovered_worker_skills[worker_id] =uncovered_worker_ skills[worker_id]. (uncovered_required_skills) else: # no best worker has been found and some required skills are still uncovered return # no solution could be found return best_team

266 4 اذكر ثلاث مشكلات تحسين مختلفة من العالم الواقعي، وفي كل مشكلة: • اضرب مثالا على دالة موضوعية. • اضرب مثالين على القيود إن وُجدَتْ. 5 إذا قمت بزيادة عدد العمّال في خوارزمية القوة المفرطة، كيف يؤثر ذلك على المشكلة من حيث عدد الحلول والزمن الحسابي؟ وزارة التعليم Ministry of Education 2024-1446