الانتقال إلى المحتوى
العودة إلى نتائج البحث

الخوارزمية الجينية متعددة الأهداف (MOGA) — البحث التطوري عن الحلول المثلى لباريتو

قدّمه
Schaffer, J. D. (early MOGA); Goldberg, D. E. (GA foundations)
السنة
1984
النوع
Population-based evolutionary optimizer
العائلة
Simulation / optimization

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

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

الفكرة الحدسية وراء الطريقة

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

التاريخ

نشأت الخوارزميات الجينية متعددة الأهداف من خوارزمية جينية تقييمية متجهة (VEGA) لـ Schaffer في عام 1984، وهي أول خوارزمية جينية تتعامل صراحة مع أهداف متعددة. قام كتاب Goldberg لعام 1989 بتوحيد التصنيف القائم على باريتو كاستراتيجية مبدئية لتعيين اللياقة. نضج المجال بسرعة مع MOGA لـ Fonseca و Fleming (1993)، و NSGA لـ Srinivas و Deb (1994)، و NSGA-II الرائد (Deb et al.، 2002)، والذي أصبح المعيار المرجعي للمجال ولا يزال الخوارزمية التطورية متعددة الأهداف الأكثر استشهادًا.

متى تُستخدم

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

الحدود والاعتبارات

  • تتزايد التكلفة الحسابية مع حجم المجموعة السكانية وعدد تقييمات الوظائف؛ يمكن أن يكون كل تقييم للمحاكاة المعقدة مكلفًا.
  • التقارب إلى جبهة باريتو الحقيقية غير مضمون - النتائج هي تقريبات استدلالية حساسة لاختيارات المعلمات الفائقة (حجم المجموعة السكانية، معدل التهجين، معدل الطفرة).
  • يتدهور الأداء مع زيادة عدد الأهداف عن ثلاثة أو أربعة (تحسين الأهداف المتعددة يتطلب خوارزميات متخصصة مثل NSGA-III أو MOEA/D).
  • يتطلب ضبطًا دقيقًا للمشغلات الجينية وصيانة التنوع لتجنب التقارب المبكر أو تغطية الجبهة الضعيفة.
  • لا يوفر حلاً موصى به واحدًا - لا يزال الاختيار النهائي من جبهة باريتو يتطلب أحكامًا قيمية أو قاعدة قرار ثانوية.

لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.

نقاط القوة

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

التطبيقات

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

كيف يعمل

كيف يعمل

1

إنشاء مجموعة أولية من N حلول مرشحة (كروموسومات) عشوائيًا أو باستخدام استدلالات المجال، مع ترميز كل حل كمتجه للمتغيرات القرار. تحديد k وظائف هدف f1(x)، f2(x)، ...، fk(x) لتقليلها أو زيادتها في وقت واحد.

2

تقييم جميع وظائف الهدف k لكل فرد في المجموعة السكانية. تعكس اللياقة جودة الحل عبر الأهداف وتنوع التغطية عبر مساحة الهدف.

3

ترتيب الأفراد حسب عدم الهيمنة: يهيمن الحل x على الحل y إذا كان على الأقل جيدًا بنفس القدر في جميع الأهداف وأفضل بشكل صارم في هدف واحد على الأقل. تحديد الجبهة غير المهيمنة (مرشحات جبهة باريتو) وتعيين أولوية اختيار أعلى للأفراد الأقل هيمنة. مقاييس التنوع مثل مسافة التكدس تمنع التكتل في منطقة ضيقة من الجبهة.

4

تطبيق الاختيار (مثل الاختيار بالبطولة) لتفضيل الأفراد ذوي الرتب الأعلى، ثم تطبيق التهجين لدمج أزواج من الآباء والطفرة لإدخال التباين. آليات النخبوية تحافظ على أفضل الحلول غير المهيمنة التي تم العثور عليها عبر الأجيال.

5

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

الأخطاء الشائعة

  • معاملة جميع الحلول على جبهة باريتو على أنها صالحة بنفس القدر دون إشراك خبراء المجال لاتخاذ قرار المفاضلة النهائي يمكن أن يؤدي إلى اختيارات عشوائية أو غير مبررة بشكل جيد.
  • استخدام مجموعة سكانية صغيرة جدًا ينتج جبهات متفرقة وغير ممثلة؛ مجموعة سكانية كبيرة جدًا تضخم الحساب دون فائدة متناسبة.
  • تجاهل معالجة القيود - يجب معاقبة الحلول غير الصالحة أو إصلاحها بشكل صريح؛ الفشل في القيام بذلك يشوه البحث نحو المناطق غير الصالحة.
  • تطبيق MOGA على مشاكل تحتوي على أكثر من أربعة أهداف دون التبديل إلى خوارزمية أهداف متعددة ينتج جبهات مزدحمة وغير مفيدة حيث تكون جميع الحلول تقريبًا غير مهيمنة.
  • الإبلاغ فقط عن جبهة باريتو النهائية دون تشخيصات التقارب (الحجم الفائق عبر الأجيال) يجعل من المستحيل تقييم ما إذا كانت الخوارزمية قد تقاربت بالفعل.

الأسئلة الشائعة

كيف تختلف MOGA عن تشغيل خوارزمية جينية أحادية الهدف باستخدام مجموع مرجح للأهداف؟

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

ما هي جبهة باريتو ولماذا هي مهمة؟

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

كم عدد الأهداف التي يمكن لـ MOGA التعامل معها بفعالية؟

تعمل متغيرات MOGA القياسية مثل NSGA-II بشكل جيد لهدفين أو ثلاثة أهداف. بعد أربعة أهداف، ينمو نسبة الحلول غير المهيمنة بسرعة (لعنة الأبعاد في مساحة الهدف)، مما يجعل جبهة باريتو كبيرة وضغط الاختيار ضعيفًا. يوصى بخوارزميات الأهداف المتعددة (NSGA-III، MOEA/D، IBEA) لأربعة أهداف أو أكثر.

ما معيار التوقف الذي يجب أن أستخدمه؟

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

هل يمكن لـ MOGA التعامل مع القيود؟

نعم، من خلال تقنيات معالجة القيود: دوال العقوبة التي تقلل من لياقة الحلول غير الصالحة، واختيار البطولة الصالحة (الحلول الصالحة تتفوق دائمًا على الحلول غير الصالحة في الاختيار)، أو مشغلات الإصلاح التي تسقط الحلول غير الصالحة مرة أخرى إلى المنطقة الصالحة. يؤثر الاختيار على سلوك التقارب ويجب أن يكون متعمدًا.

طرق ذات صلة

المصادر

  1. Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley.

    ردمك: 9780201157673
    تم النسخ.
  2. Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.

    افتح مرجع DOI
    تم النسخ.