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

خوارزمية جينية قائمة على الوكلاء — بحث تطوري موزع عبر وكلاء مستقلين

قدّمه
Adamidis, P. & Petridis, V. (early formal treatment); broader community development in 1990s
السنة
1990s
النوع
Hybrid evolutionary-agent simulation
العائلة
Simulation / optimization

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

حجم الخط

ماذا تفعل؟

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

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

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

التاريخ

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

متى تُستخدم

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

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

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

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

نقاط القوة

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

التطبيقات

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

كيف يعمل

كيف يعمل

1

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

2

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

3

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

4

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

5

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

6

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

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

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

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

كيف تختلف ABGA عن خوارزمية GA المتوازية القياسية؟

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

ما هي طوبولوجيا الهجرة التي يجب أن أختارها؟

تعتبر طوبولوجيات الحلقة والشبكة نقاط انطلاق قياسية: فهي تحد من تدفق الهجرة وتحافظ على التنوع. تسرع طوبولوجيات العالم الصغير (عدد قليل من الروابط بعيدة المدى المضافة إلى حلقة) انتشار الحلول الجيدة دون انهيار التنوع. يجب تجنب الطوبولوجيات المتصلة بالكامل بشكل عام ما لم ترغب في سلوك تقارب سريع.

كم عدد الوكلاء وما هو حجم المجموعة الفرعية المناسب؟

يتمثل الحدس الشائع في 4-16 وكيلًا بأحجام مجموعات فرعية تتراوح بين 20-50 فردًا لكل منها، ليصبح إجمالي المجموعة قابلاً للمقارنة بما تستخدمه خوارزمية GA القياسية. عدد قليل جدًا من الوكلاء يلغي ميزة التنوع في البنية؛ عدد كبير جدًا من الوكلاء بأحجام مجموعات فرعية صغيرة يعانون من الانجراف. هناك حاجة إلى ضبط تجريبي على المشكلة المحددة.

هل يمكن استخدام ABGA للتحسين متعدد الأهداف؟

نعم، ولكن يجب إضافة آليات باريتو إضافية (مثل ترتيب NSGA-II داخل كل وكيل). تساعد بنية الوكيل بعد ذلك في الحفاظ على تقريب أفضل لواجهة باريتو. هذا هو أساس متغيرات ABGA متعددة الأهداف.

هل تضمن ABGA العثور على الأمثل العالمي؟

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

طرق ذات صلة

المصادر

  1. Adamidis, P., & Petridis, V. (1996). Co-operating populations with different evolution behaviors. Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC 1996), 188-191. IEEE.

    افتح مرجع المنشور
    تم النسخ.
  2. Genetic algorithm. Wikipedia.

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