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

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

قدّمه
Holland, J. H.
السنة
1975
النوع
Stochastic evolutionary metaheuristic
العائلة
Simulation / optimization

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

حجم الخط

ماذا تفعل؟

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

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

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

التاريخ

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

متى تُستخدم

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

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

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

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

نقاط القوة

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

التطبيقات

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

كيف يعمل

كيف يعمل

1

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

2

حساب اللياقة f(x_i) لكل فرد في المجموعة باستخدام دالة الهدف (أو بديل لها). تحدد اللياقة جودة الحل؛ اللياقة الأعلى تعني حلاً أفضل. بالنسبة لمشكلات التصغير، غالبًا ما تُعرّف اللياقة على أنها مقلوب دالة التكلفة أو تحويل لها.

الصيغة
f(x_i), \quad i = 1, \ldots, N
3

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

الصيغة
P(\text{select } x_i) = \frac{f(x_i)}{\sum_{j=1}^{N} f(x_j)}
4

باحتمالية p_c (عادة 0.6–0.9)، يتم إعادة دمج أزواج من الآباء المختارين لإنتاج النسل. يتبادل التهجين أحادي النقطة، أو ثنائي النقطة، أو الموحد المادة الوراثية بين كروموسومات الآباء، مما يخلق أطفالًا يرثون الصفات من كليهما. يدفع هذا العامل استغلال اللبنات الأساسية الجيدة.

5

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

6

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

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

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

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

كيف تختلف الخوارزمية الجينية العشوائية عن الخوارزمية الجينية القياسية؟

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

ما هو الحجم المناسب للمجموعة؟

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

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

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

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

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

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

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

طرق ذات صلة

المصادر

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

    ردمك: 978-0262581110
    تم النسخ.
  2. Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA.

    ردمك: 978-0201157673
    تم النسخ.