صفحة ٢٥١
انظر إلى الشكل أعلى الصفحة: عنوان الدرس الأول مشكلة تخصيص الموارد. الذكاء الاصطناعي يعتمد على خوارزميات لتحسين القرارات، وخوارزميات تعلم الآلة تساعد في اتخاذ القرارات من خلال التنبؤ أو تقديم التوصيات كما في الرعاية الصحية. القيود هي شروط تقيد الحل مثل الحد الأقصى لوزن الشحنة. الدوال الموضوعية هي معايير تحدد مدى اقتراب الحل من النتائج المطلوبة مثل تقليل مسافة السفر. مشكلات التخصيص هي تخصيص مجموعة من الموارد مثل العمال أو الآلات لمجموعة من المهام بأعلى كفاءة ممكنة. في المستودع بالأسفل، القيد هو تحديد الوزن، والدالة الموضوعية هي زيادة عدد العناصر المعالجة والمرسلة.
صفحة ٢٥٢
انظر إلى الجدول الذي يعرض أمثلة على القيود والدوال الموضوعية في قطاعات مختلفة. في شركات النقل، القيد هو وضع أطر زمنية للتوصيل، والدالة الموضوعية هي تقليل وقت التوصيل ومسافة السفر لخفض التكلفة وتحسين الكفاءة. في جدولة خطوط الطيران، القيد هو توفر الطائرات وجداول الصيانة لضمان جاهزيتها، والدالة الموضوعية هي تقليل تأخر رحلات الطيران أو إلغائها لزيادة رضا العملاء. عند المصنعين، القيد هو توفير المواد وسعة التخزين لتجنب نفاذ المخزون أو تكدسه، والدالة الموضوعية هي تقليل الإنتاج والمهلة الزمنية لضمان تصنيع المنتجات في الوقت المناسب. في إدارة المخزون للشركات، القيد هو سعة تخزين محدودة، والدالة الموضوعية هي زيادة الربح من خلال وجود مستوى كاف من المخزون ذي هامش الربح العالي. في شركات الطاقة، القيد هو مراعاة الطلب على الكهرباء وتقلباته وتوفير المواد الخام وموارد الطاقة الضرورية، والدالة الموضوعية هي تقليل تكلفة توليد الكهرباء وتوزيعها من خلال تحسين استخدام الموارد.
صفحة ٢٥٣
انظر إلى الصفحة، وتحديداً إلى مشكلة تشكيل فريق من خمسة عمال، حيث يمتلك كل عامل مهارات مختلفة، والهدف هو تكوين فريق بأقل عدد ممكن من العمال مع الالتزام بالقيد الذي ينص على توفر جميع المهارات المطلوبة. القوة المفرطة هي طريقة من طرق حل المشكلات تتضمن التجريب المنهجي لجميع الحلول الممكنة للمشكلة بهدف الوصول إلى الحل الأمثل بغض النظر عن التكلفة الحاسوبية. بالنسبة لفريق مكون من عامل واحد، هناك خمس طرائق لاختيار عامل واحد من بين العمال الخمسة. بالنسبة لفريق مكون من خمسة عمال، هناك طريقة واحدة لاختيار كل العمال الخمسة. العدد الإجمالي للفرق المختلفة التي يمكن تكوينها هو خمسة زائد عشرة زائد عشرة زائد خمسة زائد واحد يساوي واحد وثلاثين فريقاً، ويمكن حساب العدد وفقاً للمعادلة اثنان أس خمسة ناقص واحد. يكشف تقييم كل الفرق إيجاد حل ممكن يتمثل في تكوين فريق يشمل العمال الأول والرابع والخامس، وهو الحل الأمثل.
صفحة ٢٥٤
انظر إلى القائمة في أعلى الصفحة: إذا كان لديك ستة عمال فسيكون عدد الفرق الممكنة اثنان أس ستة ناقص واحد يساوي ثلاثة وستين. وإذا كان لديك خمسون عاملاً فسيكون عدد الفرق الممكنة اثنان أس خمسين ناقص واحد، وهو رقم يتضخم إلى أكثر من مليون مليار. حتى بالنسبة لعدد معتدل من خمسين عاملاً فإن عدد الفرق المحتملة يتضخم إلى أكثر من كوادرليون. لذلك تم اقتراح طراِئق تحسين أخرى لمعالجة المشكلات المعقدة عن طريق البحث في خيارات الحلول الممكنة بأسلوب أكثر كفاءة من أسلوب القوة المفرطة، ويمكن بوجه عام تصنيف هذه الطرائق إلى ثلاث فئات: طرائق الاستدلال، البرمجة القيدية، والبرمجة الرياضية. الحل الأمثل من الممكن أن تكون هناك العديد من الحلول المثلى، كأن يكون لديك عدة فرق تشمل ثلاثة عمال وبإمكانها أن تستوفي كل المهارات المطلوبة. طرائق الاستدلال تقوم في العادة على التجربة، أو البديهة، أو الفطرة السليمة، وليس على التحليل الرياضي الدقيق. البرمجة القيدية تحل مشكلات التحسين عن طريق نمذجة القيود وإيجاد حل يخضع لجميع القيود.
صفحة ٢٥٥
انظر إلى قسم البرمجة الرياضية في أعلى الصفحة: البرمجة الرياضية هي مجموعة من التقنيات التي تستخدم نماذج رياضية لحل مشكلات التحسين، وتشمل البرمجة الخطية، والبرمجة الرباعية، وبرمجة الأعداد الصحيحة والمختلطة. وتستخدم هذه التقنيات على نطاق واسع في الكثير من المجالات بما في ذلك علم الاقتصاد والهندسة وعمليات البحث. تلعب أساليب البرمجة الرياضية دوراً مهمّاً في التعلم العميق، وتمتلك المشكلات الكبيرة وتعقيد نماذج التعلم العميق عدداً كبيراً من المعاملات التي تحتاج أن تتعلم من البيانات، حيث تستخدم خوارزميات التحسين لتعديل معاملات النموذج من أجل تقليل دالة التكلفة التي تقيس الفرق بين مخرجات النموذج المتبأ بها والمخرجات الصحيحة. تم تطوير العديد من خوارزميات التحسين الخاصة بنماذج التعلم العميق مثل خوارزمية آدم وخوارزمية الاشتقاق التكيفي وخوارزمية نشر متوسط الجذر التربيعي. في المثال العملي لتشكيل الفريق، سيتم استخدام خوارزمية القوة المفرطة والخوارزمية الاستدلالية الجشعة لحل مشكلة تخصيص القرار.
صفحة ٢٥٦
انظر إلى المقطع البرمجي في أعلى الصفحة والذي يوضح كيفية إنشاء نسخة من مشكلة معطياتها كالتالي: عشر مهارات إجمالية، وستة عمال، وتتطلب خمس مهارات كحد أقصى لكل عامل. الدالة تنشئ مهارات وقاموساً يربط كل عامل بمهاراته باستخدام مكتبة عشوائية. انظر إلى الشكل خمسة نقطة اثنين الذي يوضح رسمًا توضيحيًا للمثال الخاص بالمشكلة: لدينا عشر مهارات إجمالية تحتاجها المشكلة، وستة عمال، وكل عامل لديه خمس مهارات كحد أقصى. بسبب الطبيعة العشوائية للدالة، ستحصل على نسخة مختلفة من المشكلة في كل مرة تقوم فيها بتشغيل هذا المقطع البرمجي.
صفحة ٢٥٧
انظر إلى المقطع البرمجي في أعلى الصفحة لتجربة الدالة السابقة، حيث ستظهر لك مهارات كل عامل والمهارات المطلوبة للفريق. الخطوة التالية هي إنشاء خوارزمية حل يمكنها أن تحدد أقل عدد ممكن للفريق العمال الذي يمكن اعتماده لإستيفاء كل المهارات المطلوبة. اتخاذ القرار بخوارزمية القوة المفرطة يعتمد على التعداد الشامل لكل الفرق الممكنة وأخذها بعين الاعتبار. وستستخدم هذه الخوارزمية أدوات التوافيق من وحدة إيرترتولز لتوليد كل الفرق الممكنة ذات العدد المحدد، ويتم توضيح الأداة بالمثال البسيط أدناه الذي يولد كل الأزواج والثلاثيات الممكنة لقائمة من العناصر.
صفحة ٢٥٨
انظر إلى المقطع البرمجي الذي ينشئ الدالة التالية لحل مشكلة تكوين الفريق بأسلوب القوة المفرطة. هذه الخوارزمية تأخذ بعين الاعتبار جميع أحجام الفرق الممكنة، وتنشئ الفرق بناءً على الاعداد الممكنة، ثم تحصر الفرق التي تستوفي كل المهارات المطلوبة وتحدد الفريق الأقل عدداً. من الممكن ألا يكون هناك حل لنسخة المشكلة الواردة، فإذا كانت مجموعة المهارات المطلوبة تشمل مهارة لا يمتلكها أي عامل من العمال المتواجدين، فلن تجد طريقة إنشاء فريق يغطي كل المهارات، وفي مثل هذه الحالات ستظهر الخوارزمية المذكورة سابقاً النتيجة بعدم وجود حل. يمكنك الآن استخدام المقطع البرمجي التالي لاختبار خوارزمية الحل بالقوة المفرطة وفقاً للمثال الذي تم إنشاؤه سابقاً.
صفحة ٢٥٩
انظر إلى النص في أعلى الصفحة: من المؤكد أن خوارزمية الحل بالقوة المفرطة ستجد أفضل حل ممكن، أي أقل الفرق عدداً طالما أن هناك حلًّا ممكنًا. ولكن كما تم مناقشته في بداية هذا الدرس فإن طبيعة الخوارزمية الشمولية تؤدي إلى زيادة هائلة في التكلفة الحاسوبية كلما زاد حجم المشكلة. يمكنك توضيح ذلك من خلال إنشاء نسخ لمشكلات متعددة من حيث تزايد عدد العمال، ويمكن استخدام المقطع البرمجي التالي لتوليد نسخ متنوعة من مشكلة تكوين الفريق، حيث يتنوع عدد العمال خمسة وعشرة وخمسستة وعشرين، ثم يتم توليد مئة نسخة بعدد العمال، وتشمل كل النسخ المهارات الإجمالية العشر، والمهارات الثمان المطلوبة، والخمس مهارات كحد أقصى لكل عامل. تقبل الدالة التالية قائمة بأسنسخ المشكلة وخوارزمية الحل بالقوة المفرطة، وتستخدم لإجراء العمليات الحسابية ثم استخراج الحل لجميع النسخ.
صفحة ٢٦٠
انظر إلى المقطع البرمجي في أعلى الصفحة الذي يستخدم الدالة وخوارزمية الحل بالقوة المفرطة لحساب الحلول الممكنة لمجموعات البيانات التي تم إنشاؤها سابقاً. تظهر النتائج بالأسفل أوقات التنفيذ لكل مجموعة، فمثلاً لحل ثلاثة وعشرين مشكلة استغرق الأمر زمنيًا أقل من ثانية، ولكن لحل تسعة وتسعين مشكلة استغرق الأمر مئة وتسع ثوانٍ. على الرغم من أن الأعداد المطلوبة سُجلت بواسطة الدالة إلا أنها ستكون متفاوتة نظرًا للطبيعة العشوائية لمجموعات البيانات، وسيكون هناك نمطان ثابتان على الدوام وهما: زيادة عدد العمال تؤدي إلى عدد أكبر من نسخ المشكلات التي من الممكن إيجاد حل لها، وزيادة عدد العمال تؤدي إلى زيادة كبيرة في الزمن الحاسوبي. بصفة عامة، وبالنظر إلى عدد العمال المعطى فإن عدد الفرق الممكنة يساوي اثنين أس عدد العمال ناقص اثنين، وهذا العدد سيصبح كبيراً جداً لتقييمه حتى بالنسبة للقيم الصغيرة لعدد العمال. اتخاذ القرار باستخدام خوارزمية استدلالية جشعة تتعامل الدالة التالية مع هذا القيد بواسطة تنفيذ خوارزمية تحسين تعتمد على الأسلوب الاستدلالي الجشع.
صفحة ٢٦١
انظر إلى المقطع البرمجي في أعلى الصفحة لدالة الخوارزمية الجشعة. تظهر الدالة إنترسيكشنز مجموعة جديدة تحتوي فقط على المهارات المشتركة من جميع مهارات العمال الموجودة في العمال، والمهارات المطلوبة التي لم تستوف. تبدأ الخوارزمية بإنشاء قائمة فارغة للحل ثم تبحث في كل عامل لتحديد العامل الذي يغطي أكبر عدد ممكن من المهارات المطلوبة التي لم تكن مغطاة بعد. تقوم الخوارزمية بإضافة هذا العامل إلى فريق الحل ثم تزيل مهاراته من قائمة المهارات التي يجب تغطيتها، وتستمر العملية هكذا خطوة بخطوة حتى يتم تغطية جميع المهارات المطلوبة وتكوين الفريق الأمثل.
صفحة ٢٦٢
انظر إلى أعلى الصفحة: لا تأخذ خوارزمية الحل الجشعة كل الفرق الممكنة بعين الاعتبار ولا تضمن إيجاد الحل الأمثل، ولكنها كما هو موضح أدناه أسرع بكثير من خوارزمية الحل المفرطة، ومع ذلك يمكنها أن تنتج حلولاً جيدة، هي في الغالب حلول مثلى، ومن المذكر أن تجد هذه الطريقة حلًّا إذا كان موجوداً. يستخدم المقطع البرمجي التالي خوارزمية الحل الجشعة لحساب حلول مجموعات البيانات لخمسة عمال وعشرة عمال وخمسة عشر عاملاً وعشرين عاملاً. تظهر النتائج بالأسفل أوقات التنفيذ لكل مجموعة، فمثلاً تم حل مئة مشكلة في وقت قصير جداً لا يتجاوز أجزاء من الألف من الثانية. والآن يتضح الفرق في السرعة بين الخوارزميتين؛ حيث يمكن تطبيق خوارزمية الحل الجشعة على النسخ المتعلقة بالمشكلات الكبيرة جداً كما في المثال التالي لمليون عامل.
صفحة ٢٦٣
انظر إلى المقطع البرمجي في أعلى الصفحة الذي يوضح دالة مقارنة النتائج بين خوارزمية الحل الجشعة وخوارزمية القوة المفرطة على نفس مجموعة نسخ المشكلات. تبين النسب المئوية للنسخ التي تقوم كلتا الخوارزميتين بذكر الحل الأمثل لهما. تظهر نتائج المقارنة في الأسفل أرقاماً مثل واحد صحيح للفريق المكون من خمسة عمال، وصفر وثلاثة وثمانين بالمئة للفريق المكون من عشرة عمال. توضح النتائج أن الخوارزمية الاستدلالية الجشعة يمكنها أن تجد باستمرار الحل الأمثل لحوالي ثمانين بالمئة أو أكثر من كل نسخ المشكلات القابلة للحل. في الواقع، يمكن التحقق بسهولة من أن حجم الفريق الذي تنتجه الخوارزمية الاستدلالية الجشعة حتى في النسخ التي تفشل في إيجاد الحل المثلى لها يكون قريباً جداً من حجم فريق ممكن.
صفحة ٢٦٤
انظر إلى صفحة التمارين في أعلى الصفحة. المطلوب في السؤال الأول هو ذكر مزايا وعيوب كل من خوارزمية القوة المفرطة والخوارزمية الاستدلالية الجشعة في حل مشكلات التحسين. فكر في دقة الحل لكل منهما والوقت المستغرق حاسوبياً. المطلوب في السؤال الثاني هو تحليل طريقة استخدام الخوارزميات الاستدلالية الجشعة لإيجاد الحلول المثلى في مشكلات التحسين من خلال تتبع خطوات بناء الحل تدريجياً.
صفحة ٢٦٥
انظر إلى صفحة التمارين في أعلى الصفحة، وتحديداً السؤال الثالث. المطلوب هو إنشاء خوارزمية حل جشعة لتحسين مشكلة تكوين أعضاء فريق، من خلال إكمال المقطع البرمجي التالي بحيث تستخدم خوارزمية الحل الاستدلالية الجشعة لتكليف أعضاء الفريق بالمهمة. انظر إلى الفراغات المطبوعة في الكود البرمجي وعليك تعبئتها بالمتغيرات الصحيحة المناسبة لدالة البحث الجشع مثل أسماء العمال والمهارات غير المغطاة.
صفحة ٢٦٦
انظر إلى صفحة التمارين في أعلى الصفحة، وتحديداً السؤال الرابع. المطلوب هو ذكر ثلاث مشكلات تحسين مختلفة من العالم الواقعي، مع ضرب مثال على دالة موضوعية ومثالين على القيود إن وجدت. فكر في أمثلة مثل النقل أو جدولة الرحلات أو إدارة المخزون. المطلوب في السؤال الخامس هو شرح تأثير زيادة عدد العمال في خوارزمية القوة المفرطة على كل من عدد الحلول والزمن الحاسوبي، وتذكر العلاقة الأسية التي تمت مناقشتها في الدرس.
