مقارنة خوارزميات حل مشكلة التباطؤ الموزون - كتاب الذكاء الإصطناعي - الصف 12 - الفصل 1 - المملكة العربية السعودية

يستخدم المقطع البرمجي التالي استراتيجيتي المبادلة مع خوارزمية حل البحث المحلي لحل المشكلة التي تم إنشاؤها في بداية هذا الدرس:

print(local_search_solver(sample_problem, weighted_deadline_heuristic, random_swap, 1000)) print(local_search_solver(sample_problem, weighted_deadline_heuristic, adjacent_swap, 1000))

{'schedule': [3, 4, 2, 1, 0], 'tardiness': 83, 'finish_times': [15, 21, 30, 41, 57]} {'schedule': [3, 4, 2, 1, 0], 'tardiness': 83, 'finish_times': [15, 21, 30, 41, 57]}

تُظهر النتائج أفضل جدول [0, 1, 2, 4, 3] لهذا المثال، وإجمالي التباطؤ 83، وأزمنة إكمال المهام (ستنتهي المهمة 3 في الوحدة 15 من الزمن، وتنتهي المهمة 4 في الوحدة 21 منه، وهكذا).

Comparing Solvers

يستخدم المقطع البرمجي التالي الدالة ()create_problem_instance لتوليد مجموعتي بيانات:

• مجموعة بيانات من 100 نسخة لمشكلة التباطؤ الموزون للدلالة الواحدة، وفي كل منها 7 مهام. • مجموعة بيانات من 100 نسخة لمشكلة التباطؤ الموزون للدلالة الواحدة، وفي كل منها 30 مهمة.

سيتم استخدام مجموعة البيانات الأولى لمقارنة أداء جميع خوارزميات الحل الموضحة في هذا الدرس:

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

سيتم استخدام مجموعة البيانات الثانية لمقارنة جميع خوارزميات الحل باستثناء خوارزمية حل القوة المفرطة البطيئة جدًا بالنسبة للمشكلات المشتملة على 30 مهمة.

#Dataset 1 problems_7 = [] for i in range(100): problems_7.append(create_problem_instance(7, [5, 20], [5, 50], [1, 3])) #Dataset 2 problems_30 = [] for i in range(100): problems_30.append(create_problem_instance(30, [5, 20], [5, 50], [1, 3]))

وزارة التعليم 277 Ministry of Education 2023 - 1447

يستخدم المقطع البرمجي التالي استراتيجيتي المبادلة مع خوارزمية حل البحث المحلي لحل المشكلة التي تم إنشاؤها في بداية هذا الدرس: print(local_search_solver(sample_problem, weighted_deadline_heuristic, random_swap, 1000)) print(local_search_solver(sample_problem, weighted_deadline_heuristic, adjacent_swap, 1000)) {'schedule': [3, 4, 2, 1, 0], 'tardiness': 83, 'finish_times': [15, 21, 30, 41, 57]} {'schedule': [3, 4, 2, 1, 0], 'tardiness': 83, 'finish_times': [15, 21, 30, 41, 57]} تُظهر النتائج أفضل جدول [0, 1, 2, 4, 3] لهذا المثال، وإجمالي التباطؤ 83، وأزمنة إكمال المهام (ستنتهي المهمة 3 في الوحدة 15 من الزمن، وتنتهي المهمة 4 في الوحدة 21 منه، وهكذا). --- SECTION: مقارنة خوارزميات الحل --- Comparing Solvers يستخدم المقطع البرمجي التالي الدالة ()create_problem_instance لتوليد مجموعتي بيانات: • مجموعة بيانات من 100 نسخة لمشكلة التباطؤ الموزون للدلالة الواحدة، وفي كل منها 7 مهام. • مجموعة بيانات من 100 نسخة لمشكلة التباطؤ الموزون للدلالة الواحدة، وفي كل منها 30 مهمة. سيتم استخدام مجموعة البيانات الأولى لمقارنة أداء جميع خوارزميات الحل الموضحة في هذا الدرس: 1. خوارزمية حل القوة المفرطة. 2. خوارزمية الحل الجشعة المتضمنة على استدلال خاص بالموعد النهائي. 3. خوارزمية الحل الجشعة المتضمنة على استدلال خاص بالموعد النهائي الموزون. 4. خوارزمية حل البحث المحلي المتضمنة على مبادلات عشوائية وخوارزمية الحل الجشعة ذات استدلال خاص بالموعد النهائي لإيجاد الحل الأولي. 5. خوارزمية حل البحث المحلي المتضمنة على مبادلات عشوائية وخوارزمية الحل الجشعة ذات استدلال خاص بالموعد النهائي الموزون. 6. خوارزمية حل البحث المحلي المتضمنة على مبادلات متجاورة وخوارزمية الحل الجشعة ذات استدلال خاص بالموعد النهائي. 7. خوارزمية حل البحث المحلي المتضمنة على مبادلات متجاورة وخوارزمية الحل الجشعة ذات استدلال خاص بالموعد النهائي الموزون. سيتم استخدام مجموعة البيانات الثانية لمقارنة جميع خوارزميات الحل باستثناء خوارزمية حل القوة المفرطة البطيئة جدًا بالنسبة للمشكلات المشتملة على 30 مهمة. #Dataset 1 problems_7 = [] for i in range(100): problems_7.append(create_problem_instance(7, [5, 20], [5, 50], [1, 3])) #Dataset 2 problems_30 = [] for i in range(100): problems_30.append(create_problem_instance(30, [5, 20], [5, 50], [1, 3])) وزارة التعليم 277 Ministry of Education 2023 - 1447