شرح الخوارزميات الجينية

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

صواريخ تطير من أسفل الميدان ملتفة حول جدار نحو هدف أخضر، مع رسم أفضل طيران بخط متقطع
صواريخ تطير من أسفل الميدان ملتفة حول جدار نحو هدف أخضر، مع رسم أفضل طيران بخط متقطع

الفكرة

في ستينيات القرن العشرين وسبعينياته حوّل جون هولاند (John Holland) في جامعة ميشيغان نظرية داروين إلى خوارزمية، ووصفها في كتابه Adaptation in Natural and Artificial Systems (التكيف في الأنظمة الطبيعية والاصطناعية) الصادر عام 1975. وفي الفترة نفسها تقريبًا طوّر إنغو ريشنبرغ (Ingo Rechenberg) وهانس-باول شفيفل (Hans-Paul Schwefel) في ألمانيا استراتيجيات التطور للتصميم الهندسي. والوصفة المشتركة: احتفظ بمجتمع من الحلول المرشحة، وقيّمها، ودع الأفضل منها يتكاثر مع التنوع، وكرّر ذلك أجيالًا كثيرة.

جون هولاند، الذي وصف الخوارزميات الجينية في كتابه Adaptation in Natural and Artificial Systems الصادر عام 1975.
جون هولاند، الذي وصف الخوارزميات الجينية في كتابه Adaptation in Natural and Artificial Systems الصادر عام 1975.

الجينات والمجتمع

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

دالة اللياقة

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

الانتقاء

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

التهجين والطفرة

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

النخبوية والاستكشاف والاستغلال

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

الحلول المثلى المحلية

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

استكشفها بنفسك

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

الأسئلة المتداولة

هل الخوارزمية الجينية نوع من الذكاء الاصطناعي؟

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

هل تجد الخوارزمية الجينية دائمًا أفضل إجابة؟

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

ما الفرق بين الخوارزمية الجينية واستراتيجيات التطور؟

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

لماذا تكون الصواريخ خرقاء جدًا في البداية؟

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

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

افتح ملعب الخوارزمية الجينية