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

الخوارزمية الجينية — التحسين التطوري

قدّمه
John Henry Holland
السنة
1975
النوع
Population-based metaheuristic

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

حجم الخط

ماذا تفعل؟

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

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

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

التاريخ

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

متى تُستخدم

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

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

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

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

نقاط القوة

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

التطبيقات

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

كيف يعمل

كيف يعمل

1

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

2

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

3

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

4

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

5

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

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

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

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

كيف تختلف الخوارزمية الجينية عن الانحدار التدرجي؟

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

كم عدد الأجيال وكم حجم السكان الذي أحتاجه؟

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

هل تضمن الخوارزمية الجينية العثور على الأمثل العالمي؟

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

متى يجب أن أختار خوارزمية جينية بدلاً من التلدين المحاكى أو تحسين سرب الجسيمات؟

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

طرق ذات صلة

المصادر

  1. Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.

    افتح مرجع المنشور
    تم النسخ.
  2. Deb, K. (2001). Multi-Objective Optimization using Evolutionary Algorithms. Wiley.

    ردمك: 9780471873396
    تم النسخ.