الخوارزمية الجينية لحل مشكلة الحقيبة. مقالة دكتور فادي نجادت .

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

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

حل مثالي
يستخدم حل مشكلة الحقيبة المحمولة Recursion with memoization لإيجاد الحل الأمثل. تغطي الخوارزمية جميع الحالات الممكنة من خلال النظر في كل عنصر يتم اختياره ولم يتم اختياره. نتذكر الحل الأمثل للمشكلة الفرعية في جدول التجزئة ، ونعيد استخدام الحل بدلاً من إعادة الحساب.

memo = {}

def knapsack(W, w, v, n):
    if n == 0 or W == 0:
        return 0

    # if weight of the nth item is more than the weight
    # available in the knapsack the skip it
    if (w[n - 1] > W):
        return knapsack(W, w, v, n - 1)

    # Check if we already have an answer to the sunproblem
    if (W, n) in memo:
        return memo[(W, n)]

    # find value of the knapsack when the nth item is picked
    value_picked = v[n - 1] + knapsack(W - w[n - 1], w, v, n - 1)

    # find value of the knapsack when the nth item is not picked
    value_notpicked = knapsack(W, w, v, n - 1)

    # return the maxmimum of both the cases
    # when nth item is picked and not picked
    value_max = max(value_picked, value_notpicked)

    # store the optimal answer of the subproblem
    memo[(W, n)] = value_max

    return value_max

تعقيد وقت التشغيل
يعمل الحل أعلاه مع تعقيد O (n.W) حيث n هو العدد الإجمالي للعناصر و W هو الوزن الأقصى الذي يمكن أن تحمله الحقيبة. على الرغم من أنه يبدو كحل متعدد الحدود ، إلا أنه بالفعل حل زمني زائف متعدد الحدود.

بالنظر إلى أن الحساب يجب أن يحدث بواسطة عامل W ، فإن الحد الأقصى لمرات تنفيذ الوظيفة سيكون متناسبًا مع القيمة القصوى لـ W والتي ستكون 2 ^ m حيث m هو عدد البتات المطلوبة لتمثيل الوزن W.

هذا يجعل تعقيد الحل أعلاه O (رقم 2 ^ م). تعتبر القيمة الرقمية للمدخل W أسية في طول الإدخال ، وهذا هو السبب في أن خوارزمية الوقت الزائفة متعددة الحدود لا تعمل بالضرورة في وقت متعدد الحدود فيما يتعلق بطول الإدخال.

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

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

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

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

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

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

الحقيبة باستخدام الخوارزمية الجينية
لنفترض أن لدينا حقيبة ظهر يمكنها حمل 15 كجم من الوزن كحد أقصى. لدينا 4 عناصر A و B و C و D ؛ لها أوزان 7 كجم و 2 كجم و 1 كجم و 9 كجم ؛ والقيمة 5 دولارات و 4 دولارات و 7 دولارات و 2 دولارات على التوالي. دعونا نرى كيف يمكننا إيجاد حل عالي الجودة لمشكلة الحقيبة باستخدام خوارزمية وراثية ، وفي هذه العملية ، نفهم كل خطوة فيها.

التمثيل الفردي
الفرد في الخوارزمية الجينية هو حل محتمل. نجد أولاً طريقة لتمثيلها بحيث تسمح لنا بالتطور. بالنسبة لمشكلة حقيبة الظهر لدينا ، فإن هذا التمثيل بسيط جدًا ومباشر ؛ كل فرد عبارة عن سلسلة n-bit حيث تتوافق كل بت مع عنصر من العناصر n التي لدينا.

نظرًا لأن لدينا 4 عناصر ، فسيتم تمثيل كل فرد بسلسلة من 4 بتات وسيشير الموضع i في هذه السلسلة إلى ما إذا كنا قد اخترنا هذا العنصر في حقيبتنا أم لا ، اعتمادًا على ما إذا كان البت 1 أو 0 على التوالي.

انتقاء الأفراد
الآن بعد أن انتهينا من التمثيل الفردي ، نختار مجموعة عشوائية من الأفراد الذين سيشكلون مجموعتنا الأولية. كل فرد هو حل محتمل للمشكلة. ومن ثم بالنسبة لمشكلة الحقيبة ، من مساحة بحث 2 ^ n ، نختار عددًا قليلاً من الأفراد بشكل عشوائي.

الفكرة هنا هي تطوير السكان وجعلهم أكثر لياقة بمرور الوقت. نظرًا لأن مساحة البحث متسارعة ، فإننا نستخدم التطور لنقترب بسرعة من حل عالي الجودة (لا يلزم أن يكون مثاليًا). بالنسبة لمشكلة حقيبة الظهر التي نحن بصددها ، دعونا نبدأ بالأفراد الستة التالية (الحلول المحتملة) باعتبارهم سكاننا الأساسيين.

def generate_initial_population(count=6) -> List[Individual]:
    population = set()

    # generate initial population having `count` individuals
    while len(population) != count:
        # pick random bits one for each item and 
        # create an individual 
        bits = [
            random.choice([0, 1])
            for _ in items
        ]
        population.add(Individual(bits))

    return list(population)

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

بالنسبة لمشكلة حقيبة الظهر الخاصة بنا ، يمكننا تحديد معامل اللياقة للفرد (محلول) على أنه مجموع قيم العناصر المختارة في الحقيبة وفقًا لسلسلة البت إذا كان الوزن الإجمالي للعناصر المختارة أقل من وزن حقيبة الظهر. يمسك. معامل اللياقة للفرد هو 0 إذا كان الوزن الإجمالي للعنصر المختار أكبر من الوزن الذي يمكن أن تحمله الحقيبة.

بالنسبة لسلسلة البت 1001 ، سيكون معامل الملاءمة

total_value  = (1 * v(A)) + (0 * v(B)) + (0 * v(C)) + (1 * v(D))
             = ((1 * 5) + (0 * 4) + (0 * 7) + (1 * 2))
             = 5 + 0 + 0 + 2
             = 7

total_weight = (1 * w(A)) + (0 * w(B)) + (0 * w(C)) + (1 * w(D))
             = ((1 * 7) + (0 * 2) + (0 * 1) + (1 * 9))
             = 7 + 0 + 0 + 9
             = 16

Since, MAX_KNAPSACK_WEIGHT is 15
the fitness coefficient of 1001 will be 0

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

def fitness(self) -> float:
    total_value = sum([
        bit * item.value
        for item, bit in zip(items, self.bits)
    ])

    total_weight = sum([
        bit * item.weight
        for item, bit in zip(items, self.bits)
    ])

    if total_weight <= MAX_KNAPSACK_WEIGHT:
        return total_value

    return 0

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

أحد معايير الاختيار الجيدة هو Tournament Selection ، الذي يختار عشوائياً شخصين ويدير دورة افتراضية. الشخص الذي لديه معامل لياقة أعلى يفوز.

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

def selection(population: List[Individual]) -> List[Individual]:
    parents = []

    # randomly shuffle the population
    random.shuffle(population)

    # we use the first 4 individuals
    # run a tournament between them and
    # get two fit parents for the next steps of evolution

    # tournament between first and second
    if population[0].fitness() > population[1].fitness():
        parents.append(population[0])
    else:
        parents.append(population[1])

    # tournament between third and fourth
    if population[2].fitness() > population[3].fitness():
        parents.append(population[2])
    else:
        parents.append(population[3])

    return parents

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

لا يحدث التقاطع دائمًا في الطبيعة ؛ ومن ثم نحدد معلمة تسمى معدل التقاطع ، والتي تقع نسبيًا في النطاق من 0.4 إلى 0.6 بالنظر إلى أنه في الطبيعة ، نرى معدلًا مشابهًا للتقاطع أثناء تكوين النسل.

بالنسبة لمشكلة حقيبة الظهر لدينا ، نبقيها بسيطة وننشئ طفلين من أبوين لائقين بحيث يحصل كلاهما على النصف من كل والد والنصف الآخر من الوالد الآخر. هذا يعني في الأساس أننا نجمع نصف العناصر من كل من الفرد ونشكل الطفلين.

def crossover(parents: List[Individual]) -> List[Individual]:
    N = len(items)

    child1 = parents[0].bits[:N//2] + parents[1].bits[N//2:]
    child2 = parents[0].bits[N//2:] + parents[1].bits[:N//2]

    return [Individual(child1), Individual(child2)]

طفره
الطفرة هي عملية تطورية تحدث تحورًا عشوائيًا للفرد. هذا مستوحى من الطفرة التي تحدث في الطبيعة ، والفكرة الأساسية هي أنه في بعض الأحيان تحصل على بعض التغييرات العشوائية غير المتوقعة في الفرد.

تمامًا مثل عملية التقاطع ، لا تحدث الطفرة دائمًا. ومن ثم ، فإننا نحدد معلمة تسمى معدل الطفرة ، وهي منخفضة جدًا نظرًا لمعدل الطفرة في الطبيعة. يتراوح المعدل عادةً بين 0.01 و 0.02. تغير الطفرة الفرد ، ومع هذا التغيير ، يمكن أن يكون لها معامل لياقة أعلى أو أقل ، تمامًا كما يحدث في الطبيعة.

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

def mutate(individuals: List[Individual]) -> List[Individual]:
    for individual in individuals:
        for i in range(len(individual.bits)):
            if random.random() < MUTATION_RATE:
                # Flip the bit
                individual.bits[i] = ~individual.bits[i]

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

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

بالنسبة لمشكلة حقيبة الظهر لدينا ، نحدد معدل التكاثر ، واعتمادًا على ما نقرر نقله إلى الجيل التالي مباشرة. نحافظ على معدل التكاثر عند 0.30 مما يعني أن 30٪ من الوقت ، الوالدان الأصلح ينتقلان إلى الأجيال القادمة.

خلق الأجيال
نكرر العملية بأكملها من الانتقاء والتكاثر والتقاطع والطفرة حتى نحصل على نفس عدد الأطفال مثل السكان الأصليين ، ونطلق عليه الجيل الأول. نكرر نفس العملية مرة أخرى ونخلق الأجيال اللاحقة.

عندما نستمر في إنشاء مثل هذه الأجيال ، سنلاحظ أن متوسط معامل اللياقة البدنية يزيد ويتقارب إلى نطاق ثابت. توضح الصورة أعلاه كيف تتقارب قيمتنا مع 12 على مدى 500 جيل للمشكلة المحددة. الحل الأمثل للمسألة المطروحة هو 16 ، واقتربنا من 12.

def next_generation(population: List[Individual]) -> List[Individual]:
    next_gen = []
    while len(next_gen) < len(population):
        children = []

        # we run selection and get parents
        parents = selection(population)

        # reproduction
        if random.random() < REPRODUCTION_RATE:
            children = parents
        else:
            # crossover
            if random.random() < CROSSOVER_RATE:
                children = crossover(parents)

            # mutation
            if random.random() < MUTATION_RATE:
                mutate(children)

        next_gen.extend(children)

    return next_gen[:len(population)]

شرط الإنهاء
يمكننا الاستمرار في توليد أجيال بعد أجيال بحثًا عن الحل الأمثل ، لكن لا يمكننا الاستمرار إلى ما لا نهاية ، حيث نحتاج إلى شرط إنهاء. شرط الإنهاء الجيد محدد ومحدّد. على سبيل المثال ، سنصل بحد أقصى إلى 500 أو 1000 جيل أو حتى نحصل على نفس متوسط معامل اللياقة لآخر 50 قيمة.

يمكن أن يكون لدينا حالة إنهاء مماثلة لمشكلة حقيبة الظهر لدينا حيث وضعنا غطاءً عند 500 جيل. الفرد الذي يتمتع بأقصى معامل لياقة هو حلنا عالي الجودة. يبدو التدفق العام شيئًا كهذا.

def solve_knapsack() -> Individual:
    population = generate_initial_population()

    avg_fitnesses = []

    for _ in range(500):
        avg_fitnesses.append(average_fitness(population))
        population = next_generation(population)

    population = sorted(population, key=lambda i: i.fitness(), reverse=True)
    return population[0]

تعقيد وقت التشغيل
تعقيد وقت تشغيل الخوارزمية الجينية لتوليد حل عالي الجودة لمشكلة الحقيبة ليس أسيًا ، ولكنه متعدد الحدود. إذا عملنا مع الحجم السكاني لـ PAnd يتكرر حتى أجيال G ، وكان F هو تعقيد وقت التشغيل لوظيفة اللياقة ، فإن التعقيد الكلي للخوارزمية سيكون O (PGF).

نظرًا لأن المعلمات معروفة قبل بدء التنفيذ ، يمكنك توقع الوقت المستغرق للوصول إلى الحل. وبالتالي ، فإننا نعثر على حل غير مثالي ولكن عالي الجودة لمشكلة حقيبة الظهر سيئة السمعة في التوقيت متعدد الحدود.

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

كفاءة الخوارزمية الجينية
أثناء مناقشة عملية الخوارزمية الجينية ، رأينا أن هناك العديد من المعلمات التي يمكن أن تزيد أو تقلل من كفاءة الخوارزمية ؛ تشمل بعض العوامل

سكان
حجم المجتمع الأولي أمر بالغ الأهمية في تحقيق الكفاءة العالية للخوارزمية الجينية. بالنسبة لمشكلة الحقيبة على الظهر ، بدأنا بمشكلة أبسط تتكون من 4 عناصر ، أي مساحة بحث لا تزيد عن 16 عنصرًا ، وعدد سكان أولي هو 6. لقد أخذنا مجموعة مشكلة صغيرة كهذه فقط لكي نلف رؤوسنا حول الفكرة.

في العالم الحقيقي ، تعمل الخوارزميات الجينية على مساحة بحث أكبر بكثير وتبدأ عادةً بحجم مجتمع من 500 إلى 50000. ويلاحظ أنه إذا لم يؤثر الحجم الأولي للسكان على وقت تنفيذ الخوارزمية ، فإنه يتقارب بشكل أسرع مع عدد سكان أكبر من عدد سكان أصغر.

عبور
كما ناقشنا أعلاه ، هناك العديد من وظائف Crossover التي يمكننا استخدامها ، مثل Single Point Crossover و Two-point Crossover و Multi-Point Crossover. تعتمد وظيفة التقاطع التي ستعمل بشكل أفضل مع مشكلة ما تمامًا على المشكلة المطروحة. ويلاحظ بشكل عام أن التقاطع ذو النقطتين يؤدي إلى أسرع تقارب.

يمكنك العثور على الكود المصدري الكامل للخوارزمية الجينية التي تمت مناقشتها أعلاه من هنا
https://github.com/arpitbbhayani/genetic-knapsack

https://arpitbhayani.me/blogs/genetic-knapsack

شارك المقال

اترك تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني.