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

دالة خوارزمية حل البحث المحلي Local_search_solver() Function

تطبق الدالة التالية (local_search_solver) خوارزمية حل البحث المحلي القائم على المبادلة لمشكلة التباطؤ الموزون للدالة الواحدة (SMWT). حيث تقبل هذه الدالة أربعة معاملات وهي:

• نسخة المشكلة. • خوارزمية استدلالية جشعة تستخدمها دالة ()greedy_solver لحساب حل أولي. • دالة swap_selector المستخدمة لانتقاء مهمتين سيتبادلان موقعهما في الجدول. على سبيل المثال، إذا كان الحل الحالي للمشكلة المكونة من أربع مهام هو [0, 3, 2, 1]. وقررت دالة swap_selector أن يحدث مبادلة بين المهمة الأولى والمهمة الأخيرة، سيكون الحل المرشح هو [1, 3, 2, 0]. • max_iterations عدد صحيح يحدد عدد المبادلات التي يجب تجربتها قبل أن تتوصل الخوارزمية للحل الأفضل في حينه.

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

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

def local_search_solver(problem, greedy_heuristic, swap_selector, max_iterations): # gets the information for this problem durations, weights, deadlines=problem['durations'], problem['weights'], \ problem['deadlines'] job_num = len(durations) # gets the number of jobs # uses the greedy solver to get a first schedule # this schedule will be then iteratively refined through local search greedy_sol = greedy_solver(problem, greedy_heuristic) # the best schedule so far best_schedule, best_tardiness, best_finish_times = greedy_sol['schedule'], \ greedy_sol['tardiness'], greedy_sol['finish_times'] # local search for i in range(max_iterations): # for each of the given iterations # chooses which two positions to swap pos1, pos2 = swap_selector(best_schedule) new_schedule = best_schedule.copy() # create a copy of the schedule # swaps jobs at positions pos1 and pos2 new_schedule[pos1], new_schedule[pos2] = new_schedule[pos2], \ new_schedule[pos1]

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

دالة خوارزمية حل البحث المحلي Local_search_solver() Functionتطبق الدالة التالية (local_search_solver) خوارزمية حل البحث المحلي القائم على المبادلة لمشكلة التباطؤ الموزون للدالة الواحدة (SMWT). حيث تقبل هذه الدالة أربعة معاملات وهي:• نسخة المشكلة. • خوارزمية استدلالية جشعة تستخدمها دالة ()greedy_solver لحساب حل أولي. • دالة swap_selector المستخدمة لانتقاء مهمتين سيتبادلان موقعهما في الجدول. على سبيل المثال، إذا كان الحل الحالي للمشكلة المكونة من أربع مهام هو [0, 3, 2, 1]. وقررت دالة swap_selector أن يحدث مبادلة بين المهمة الأولى والمهمة الأخيرة، سيكون الحل المرشح هو [1, 3, 2, 0]. • max_iterations عدد صحيح يحدد عدد المبادلات التي يجب تجربتها قبل أن تتوصل الخوارزمية للحل الأفضل في حينه.في كل تكرار، تنتقي الخوارزمية مهمتين للتبديل بينهما، ثم تنشئ جدولاً جديدًا تتم فيه هذه المبادلة. وكل شيء في الجدول الجديد بخلاف ذلك سيكون مطابقًا للجدول الأصلي. إذا كان للجدول الجديد تباطؤ موزون أقل من الجدول الأفضل الذي تم إيجاده حتى الآن، فإن الجدول الجديد يصبح هو الأفضل بدلاً منه. خوارزمية الحل هذه لها نفس مخرجات خوارزمية الحل الجشعة وخوارزمية حل القوة المفرطة.سلوك خوارزميات التحسين القائمة على البحث المحلي يتأثر بشكل كبير بالاستراتيجية المستخدمة بطريقة تكرارية لتعديل الحل.--- SECTION: Python Code for local_search_solver --- def local_search_solver(problem, greedy_heuristic, swap_selector, max_iterations):# gets the information for this problem durations, weights, deadlines=problem['durations'], problem['weights'], \ problem['deadlines']job_num = len(durations) # gets the number of jobs# uses the greedy solver to get a first schedule # this schedule will be then iteratively refined through local search greedy_sol = greedy_solver(problem, greedy_heuristic) # the best schedule so far best_schedule, best_tardiness, best_finish_times = greedy_sol['schedule'], \ greedy_sol['tardiness'], greedy_sol['finish_times']# local search for i in range(max_iterations): # for each of the given iterations# chooses which two positions to swap pos1, pos2 = swap_selector(best_schedule)new_schedule = best_schedule.copy() # create a copy of the schedule# swaps jobs at positions pos1 and pos2 new_schedule[pos1], new_schedule[pos2] = new_schedule[pos2], \ new_schedule[pos1]2023 - 1447--- VISUAL CONTEXT --- **CODE_BLOCK**: Python Code for local_search_solver Description: A block of Python code implementing the local_search_solver function, including comments explaining its parts: getting problem information, using a greedy solver for an initial schedule, and an iterative local search loop for swapping job positions. Context: This code block provides a practical implementation example of the local search algorithm described in the text, demonstrating how the parameters (problem, greedy_heuristic, swap_selector, max_iterations) are used.**HIGHLIGHT_BOX**: Untitled Description: A pink rectangular box containing a highlighted statement about the behavior of local search improvement algorithms. Context: This box emphasizes a key characteristic of local search algorithms: their behavior is significantly influenced by the iterative strategy used to modify the solution.