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

الحلقة من أولها إلى آخرها

قال الدرس 13.1 إن الخوارزمية الجينية أربعة قرارات — التمثيل، والملاءمة، والانتقاء، والتنويع. وهذا الدرس يجعل كلًّا منها ملموسًا. وكل ما يأتي أدناه يقع داخل حلقة واحدة لا تتغير:

1. أنشئ مجتمعًا ابتدائيًا من مرشحين عشوائيين. 2. قيّم ملاءمة كل مرشح. 3. وما بقيت ميزانية: اختر الآباء بالانتقاء، وأعد تركيبهم بالتهجين، واضطرب الأبناء بالطفرة، وقيّم الأبناء، وقرر أي المرشحين يشكّل المجتمع التالي. 4. أعِد أفضل مرشح رأيته على الإطلاق — وهو، كما يشرح قسم الاحتفاظ بالنخبة، ليس تلقائيًا أفضل مرشح في المجتمع الأخير.

لاحظ أين تقع الكلفة. الانتقاء والتهجين والطفرة عمليات حسابية على بنى معطيات قصيرة، وهي مجانية عمليًا. الخطوة 2 هي حيث يُنفق المال: إذا كانت الملاءمة تعني تدريب نموذج، فمجتمع من 50 على مدى 100 جيل هو 5,000 جولة تدريب. وكل اختيار معامل أدناه هو في الحقيقة قرار عن كيفية إنفاق تلك التقييمات.

الترميز: الاختيار الذي يقيّد كل شيء

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

سلاسل البتات. الصورة الكلاسيكية، وهي التي حللها هولاند (1975) وبنى عليها غولدبرغ (1989) أمثلته المحلولة. كل بت مفتاح، أو تُرمّز مجموعة بتات عددًا يُفكَّك إلى مجال. وهي تلائم اختيار المجموعات الجزئية تمامًا: مع 40 ميزة مرشحة، سلسلة من 40 بت هي مجموعة جزئية.

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

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

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

الانتقاء: اختيار الآباء

الانتقاء هو الخطوة الوحيدة التي تستشير الملاءمة، فمنه يأتي اتجاه البحث. وثلاثة مخططات تغطي الممارسة المعيارية.

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

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

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

التهجين: إعادة تركيب أبوين

التهجين هو العامل الذي يجعل هذه العائلة مختلفة عن كل طريقة بحث أحادية النقطة. يُطبَّق باحتمال p_c؛ وباحتمال 1 − p_c يُنسخ الأبوان كما هما. والمعدلات في المجال 0.6 إلى 0.9 هي نقطة البداية الشائعة، ورسالة دي يونغ لعام 1975 هي الدراسة التجريبية المبكرة لإعدادات كهذه — خُذها افتراضات معقولة للبدء منها، لا قيمًا مثالية مقيسة لمسألتك.

التهجين أحادي النقطة. اختر موضع قطع وامنح الابن كل ما قبل القطع من الأب A وكل ما بعده من الأب B. التهجين ثنائي النقطة. اختر قطعين وبادل القطعة الوسطى. التهجين المنتظم. اقرر كل موضع باستقلال برمي عملة، آخذًا ذلك الجين من A أو من B.

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

ولمتجهات القيم الحقيقية خيار رابع لا نظير له في الحالة المنفصلة — امزج الأبوين بدلًا من قطعهما:

التباديل تحتاج عاملها الخاص. اقطع ترتيبَي زيارة عند نقطة وألصقهما وستحصل عادةً على كلام فارغ — مسار يزور الموقع 3 مرتين ولا يزور الموقع 7 أبدًا. وتهجين الترتيب يحل هذا بالبناء: انسخ قطعة متصلة من الأب A إلى الابن، ثم املأ المواضع الفارغة بالعناصر التي ما زال الابن يفتقدها، آخذًا إياها بالترتيب الذي تظهر به في الأب B.

الطفرة، ومقايضة المعدل

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

قلب البت. زُر كل بت واقلبه باحتمال p_m. ولأن القلبات مستقلة، فإن العدد المتوقع للبتات المتغيرة في الابن هو طول السلسلة مضروبًا في المعدل ببساطة:

الاضطراب الغاوسي. لمتجه حقيقي القيمة، أضف ضجيجًا غاوسيًا صفري المتوسط إلى كل مكوّن: x′ = x + σ ε حيث ε مسحوبة من توزيع طبيعي معياري. هنا σ هي حجم الخطوة وهي نظير معدل قلب البت؛ ومن الممارسات الشائعة تقليصها مع تقدم الجولة، فتستكشف الأجيال المبكرة على نطاق واسع وتُصقل الأجيال المتأخرة.

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

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

الاحتفاظ بالنخبة: فقدان أفضل حل خلل حقيقي

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

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

الاستبدال الجيلي أو المستقر

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

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

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

مقبض الاستكشاف والاستغلال، كمعاملات ملموسة

الاستكشاف والاستغلال شعار حتى تستطيع تسمية الإعدادات التي تحركه. وفي الخوارزمية الجينية تستطيع:

نحو الاستكشاف: مجتمع N أكبر؛ وحجم مباراة k أصغر، أو ضغط رتبة s أقرب إلى 1؛ ومعدل طفرة أو σ غاوسية أعلى؛ ونُخب أقل؛ واستبدال جيلي لا مستقر. نحو الاستغلال: k أكبر أو s أقرب إلى 2؛ ونُخب أكثر؛ واستبدال مستقر؛ وσ أصغر، وبخاصة في أواخر الجولة.

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