دالة الملاءمة ليست تفصيلًا في التنفيذ — إنها صياغة المسألة نفسها. وسوء تصميمها هو السبب الأكثر شيوعًا لفشل الخوارزمية الجينية.
الملاءمة هي الهدف
لا رأي للخوارزمية الجينية في مسألتك. فهي لا ترى شبكة الطرق، ولا ميزانية الراديو، ولا العميل. كل ما تراه هو الرقم الواحد الذي تُرجعه دالة الملاءمة لكل مرشح حل، ثم يضاعف الانتقاء كل ما يحصل على رقم مرتفع. هذه هي الآلية بأكملها. ولهذا فإن دالة الملاءمة ليست تفصيلًا في التنفيذ: هي صياغة مسألتك، مكتوبة باللغة الوحيدة التي يستطيع البحث قراءتها.
وضع Holland (1975) في كتابه Adaptation in Natural and Artificial Systems الإطار الذي يعمل فيه الانتقاء على مجتمع من البُنى وفق عائد مقيس، وكتاب Goldberg (1989) هو المعالجة المرجعية التي تلته. وفي كليهما تكون الملاءمة هي البيئة: غيّرها فتُغيّر ما يصير إليه المجتمع. وكل ما في هذا الدرس ينبع من هذه الحقيقة الواحدة.
تعظّم الخوارزمية الجينية الدالة التي كتبتها، لا الهدف الذي كان في ذهنك. وكل صور الفشل في هذا الدرس هي فجوة بين هذين الأمرين. فعندما ينتج تشغيل ما فائزًا بلا معنى، اتّهم دالة الملاءمة قبل أن تتّهم المُشغِّلات.
كافئ النتيجة، لا السلوك
الطريقة الأكثر شيوعًا لكتابة دالة ملاءمة سيئة هي أن تتخيّل كيف كنت أنت ستحل المسألة، ثم تُقيّم المرشحين بمقدار تقليدهم لك. لنفترض أنك تُطوّر جدول دورة العمل لمستشعر يعمل بالبطارية، وتريده أن يستمر أطول فترة ممكنة وأن يظل مفيدًا. من المغري أن تكافئ سلوك «إبقاء الراديو مغلقًا»، لأنك تعلم أن الراديو يستهلك معظم الطاقة. افعل ذلك وسيجد البحث بالضبط ما طلبته: جدول بالراديو مغلق، وبطارية تدوم طويلًا، ولا بيانات مُسلَّمة على الإطلاق.
والحل هو قياس النتيجة التي تهمك فعلًا — عدد القراءات المفيدة المُسلَّمة لكل شحنة بطارية — وترك البحث يكتشف بنفسه أن هذا يستلزم إبقاء الراديو مغلقًا معظم الوقت. دالة الملاءمة التي تُرمّز طريقتك المفترضة لا تستطيع إلا أن تعيد اكتشاف طريقتك. أما تلك التي تُرمّز النتيجة فهي حرة في إيجاد شيء أفضل.
وحين تكون النتيجة غير قابلة للقياس فعلًا واضطررت إلى استخدام مؤشر بديل، فتعامل معه كفرضية لا كهدف: افحص الفرد الفائز يدويًّا أمام الهدف الحقيقي قبل أن تثق به. وتلتقي الوحدة 14 بالخطر نفسه من الاتجاه المقابل، حيث يُسمّى قرصنة المكافأة — فالوكيل يُحسّن ما قِسته، لا ما قصدته.
مثال محلول: توزيع المستشعرات
لنكن محددين: لديك 40 موقعًا مرشحًا لمستشعرات بيئية على أرض مقسّمة إلى 200 خلية شبكية. كل موقع يغطي مجموعة معروفة من الخلايا وله كلفة تركيب معروفة، ولديك ميزانية ثابتة. وباتّباع الدرس 13.2، يكون المرشح سلسلة ثنائية بطول 40 — البتّة i تساوي 1 إذا استُخدم الموقع i.
ودالة الملاءمة الأولى البديهية هي «عدد الخلايا المتمايزة المغطاة». شغّلها وسيتقارب المجتمع نحو سلاسل تكاد تكون كلها آحادًا: أقصى تغطية، وفاتورة تبلغ أضعاف الميزانية. لا شيء في تلك الدالة يذكر المال، فلا سبب لدى البحث أن يهتم به. وهذا المثال الواحد يحمل بقية الدرس — فيه هدفان متنازعان، وقيد صارم، وخطوة تقييم تستهلك وقتًا حقيقيًّا.
المسائل متعددة الأهداف
يجب أن ترتفع التغطية وتنخفض الكلفة. ولا توجد إجابة واحدة أفضل لذلك، بل مجموعة من التسويات المقبولة، والسؤال هو أيّها يُسمح للخوارزمية بإرجاعه.
المجاميع الموزونة
أبسط المقاربات تطوي الأهداف في رقم واحد بأوزان تختارها مسبقًا.
وهنا قيدان صريحان. الأول أن الأوزان قرار اتخذته قبل أن ترى أي شيء من المقايضة، وأن التشغيل الواحد يُرجع تسوية واحدة. والثاني أن المجموع الموزون لا يستطيع إلا إرجاع حلول تقع على الجزء المحدَّب من سطح المقايضة؛ أما التسويات المنزوية في جزء مقعّر من ذلك السطح فلا يمكن الوصول إليها بأي اختيار للأوزان.
هيمنة باريتو والجبهة
المقاربة البديلة ترفض طيّ الأهداف من أصله. يُقال إن حلًّا يهيمن على آخر إذا كان لا يقل عنه جودةً في كل هدف ويتفوق عليه فعليًّا في هدف واحد على الأقل.
تُرجع الخوارزمية الجينية متعددة الأهداف تقريبًا لتلك الجبهة بدلًا من نقطة واحدة، ثم يختار الإنسان منها وهو يرى تمامًا ما تكلفه كل خلية تغطية إضافية. وهذا عادةً هو المُخرَج الأنفع، لأن الأوزان لم تكن معروفة مسبقًا في الحقيقة.
لمحة عن NSGA-II
الخوارزمية الجينية النخبوية المرجعية متعددة الأهداف هي NSGA-II، من Deb وPratap وAgarwal وMeyarivan (2002). ثلاث أفكار، ويجدر تمييز كل واحدة منها:
- الترتيب السريع غير المهيمن عليه — يُقسّم المجتمع إلى جبهات. الجبهة الأولى هي المجموعة غير المهيمن عليها، والثانية هي ما يصبح غير مهيمن عليه بعد إزالة الأولى، وهكذا. والرتبة الأدنى مفضّلة دائمًا.
- مسافة الازدحام — الفاصل عند التعادل داخل الجبهة، إذ لا يتفوق أي عضو في الجبهة على آخر بحكم التعريف. وهي تُقدّر مدى خلاء فضاء الأهداف حول كل حل وتفضّل الحلول في المناطق المتناثرة. وهذا ما يحفظ انتشار الجبهة المُرجعة بدلًا من تكتّلها.
- النخبوية بالدمج — يُجمع الآباء والأبناء في مجموعة واحدة، ثم تُرتَّب برتبة الجبهة، وداخل الجبهة بمسافة الازدحام، ثم تُقتطع عودًا إلى حجم المجتمع. فلا يمكن أن يُفقد حل جيد بالخطأ، وهي الحجة نفسها التي سيقت للنخبوية في الدرس 13.2.
| المقاربة | ما تُرجعه | متى تناسب | القيد |
|---|---|---|---|
| هدف واحد مع عقوبة | حل واحد | هدف حقيقي واحد والبقية قيود | يحتاج اختيارًا جيدًا لأوزان العقوبة |
| المجموع الموزون | تسوية واحدة | حين تكون المقايضة معروفة مسبقًا فعلًا | لا يبلغ الأجزاء المقعّرة من سطح المقايضة |
| جبهة باريتو (NSGA-II) | انتشار من التسويات | حين يختار إنسان بعد رؤية الخيارات | آلية أثقل، والجبهة تحتاج عرضًا وقراءة |
التعامل مع القيود
الميزانية في مثال المستشعرات ليست هدفًا يُقايَض به — إنها جدار. وهناك أربع طرائق مرجعية لتعليم الخوارزمية الجينية وجود جدار، وهي تختلف في مقدار فضاء البحث الذي تُبقيه صالحًا للاستخدام.
واختيار معاملات العقوبة هو الجزء الذي يحتاج حكمًا. فإن كانت صغيرة جدًّا كان الفائز حلًّا غير مجدٍ اشترى التغطية بمال لا يملكه. وإن كانت كبيرة جدًّا تصرّفت العقوبة تصرّف الرفض: لا يستطيع البحث عبور حاجز غير مجدٍ قليلًا للوصول إلى منطقة مجدية أفضل على الجانب الآخر، وهو غالبًا المسار الذي يحتاجه بالضبط.
أبلِغ دائمًا عمّا إذا كان أفضل فرد مجديًا كحقيقة مستقلة، لا كشيء يُستنتج من ملاءمته. فالنتيجة المعاقَبة والنتيجة المجدية فعلًا رقمان من النوع نفسه، والخلط بينهما هو الطريق إلى تقديم تصميم غير مجدٍ كأنه الحل.
التقارب المبكر وفقدان التنوع
تأتي قوة الخوارزمية الجينية من إعادة تركيب حلول مختلفة. فحين يصبح المجتمع مكوّنًا من نسخ شبه متطابقة من فرد واحد، ينتج التهجين بين اثنين منها الفرد نفسه من جديد، وتبقى الطفرة المصدر الوحيد للجديد — وهي مشي عشوائي بطيء جدًّا. هذا هو التقارب المبكر: توقّف التشغيل عن التحسّن قبل أن يجد شيئًا جيدًا بوقت طويل، ومن الخارج يبدو تمامًا كتشغيل انتهى.
كيف تكتشفه
- أفضل ملاءمة ناقص المتوسط — ارسم الاثنين لكل جيل. فانهيار الفجوة نحو الصفر مبكرًا يعني أن المجتمع صار متماثلًا.
- عدد الأنماط الجينية المتمايزة — عُدّ الأفراد الفريدين في كل جيل. والهبوط الحاد المبكر هو أوضح إشارة موجودة.
- ترددات الأليلات لكل جين — في الترميز الثنائي: نسبة المجتمع التي تحمل 1 في كل موضع. والمواضع التي تتشبّع عند 0 أو 1 هي مواضع لم يعد التهجين يستكشفها.
- متوسط المسافة الزوجية — مسافة هامنج للسلاسل الثنائية، والمسافة الإقليدية للمتجهات الحقيقية. وهي القياس المباشر للشيء الذي يقلقك.
كيف تقاومه
يُفقد التنوع حين يكون ضغط الانتقاء عاليًا نسبةً إلى التنويع الذي تُوفّره المُشغِّلات، فكل إجراء مضاد يُعدّل أحد طرفي هذا التوازن.
- خفّض ضغط الانتقاء — حجم مسابقة أصغر، أو انتقاء بالرتبة بدلًا من الانتقاء التناسبي مع الملاءمة (الدرس 13.2). غالبًا أرخص حل وأول ما يُجرَّب.
- ارفع معدل الطفرة، أو ارفعه تكيفيًّا حين يهبط مقياس تنوع دون حد معين.
- تشارك الملاءمة — اجعل الأفراد المتشابهين يتنافسون على نصيب مشترك من الملاءمة، فيُعاقب الحشد على كونه حشدًا. وطرائق التخصيص من هذا النوع مشروحة في Goldberg (1989).
- الاستبدال بالازدحام — يحل الابن الجديد محل الفرد الأشبه به لا محل الأسوأ في المجتمع، فتبقى المناطق المتمايزة مأهولة.
- إعادة التشغيل — أعِد تهيئة المجتمع مع الاحتفاظ بأرشيف لأفضل الحلول الموجودة. رخيصة، وكثيرًا ما تكون أنفع من الضبط.
- نماذج الجزر — عدة مجتمعات فرعية تتطور منفصلة مع هجرة عارضة، فلا يؤدي تقارب أحدها إلى تقارب الباقي.
حساب الكلفة
في كل تطبيق واقعي تقريبًا يهيمن تقييم الملاءمة على زمن التشغيل. فالانتقاء والتهجين والطفرة عمليات مصفوفية قليلة، أما التقييم الواحد فقد يكون محاكاة، أو دورة بناء واختبار، أو تدريب نموذج كامل. لذا فالرقم المهم ليس عدد الأجيال بل العدد الكلي للتقييمات.
أدخِل الحساب: مجتمع من 100 فرد على 200 جيل يساوي 100 × 200 = 20,000 تقييم. وبثانيتين لكل تقييم يصبح ذلك 40,000 ثانية — أي ما يزيد قليلًا على إحدى عشرة ساعة على نواة واحدة، أو نحو واحد وعشرين دقيقة موزّعة على اثنين وثلاثين عاملًا. ولا شيء في ذلك قياسٌ لمسألة معينة؛ إنه الضرب الذي ينبغي أن تجريه قبل بدء التشغيل لا بعده.
طرائق لصرف الميزانية بشكل أفضل:
- خزّن النتائج بحسب النمط الجيني. مع تقارب المجتمع يُعاد تقييم الفرد نفسه باستمرار. وقاموس يربط النمط الجيني بملاءمته لا يزيد على أسطر قليلة، وقد يحذف جزءًا كبيرًا من العمل في أواخر التشغيل.
- قيّم بثمن رخيص أولًا. قيّم على عينة فرعية من البيانات أو على محاكاة مختصرة، ثم أعِد تقييم الناجين فقط بالكلفة الكاملة. وانتبه أن هذا يجعل الملاءمة ضجيجية، وهو ما يُضعف الانتقاء.
- استخدم نموذجًا بديلًا. لائم نموذجًا رخيصًا لمشهد الملاءمة من التقييمات المتوفرة لديك، وافحص به المرشحين، ولا تدفع الثمن الكامل إلا للواعدين. وهذه هي فكرة النموذج البديل نفسها التي يستخدمها التحسين البايزي في الدرس 10.2.
- اقطع مبكرًا. إذا لم يستطع مرشح تجاوز الأفضل الحالي في منتصف تقييمه، فأوقفه.
- وازِ التنفيذ. كل فرد في الجيل يُقيَّم مستقلًّا، فتتوسّع الخوارزمية الجينية التوالدية توسّعًا شبه خطي مع عدد العمّال. وهذه ميزة بنيوية حقيقية على طرائق البحث المتسلسلة بحتًا.
حدّد ميزانية التقييمات أولًا، ثم اختر حجم المجتمع وعدد الأجيال لتلائمها. فكلاهما مهم وبينهما مقايضة: المجتمع الكبير يستكشف أكثر في الجيل الواحد لكنه يتيح أجيالًا أقل للميزانية نفسها. والإعلان عن «تشغيل 500 جيل» لا يعني شيئًا حتى يعرف القارئ P وكلفة التقييم الواحد.
الملاءمة هي صياغة المسألة، فاتّهمها أولًا عندما يسوء التشغيل. كافئ النتيجة لا السلوك الذي تفترض أنه ينتجها. ولعدة أهداف: إمّا أن توزنها — بعد إعادة التحجيم، ومع علمك بأن المجموع الموزون لا يبلغ الأجزاء المقعّرة من سطح المقايضة — أو أن تُرجع جبهة باريتو، وهو ما تفعله NSGA-II (Deb et al.، 2002) بالترتيب غير المهيمن عليه ومسافة الازدحام والاقتطاع النخبوي. تعامل مع القيود بالعقوبة أو الرفض أو الإصلاح أو المُشغِّلات الحافظة للجدوى، وأبلِغ عن الجدوى دائمًا على حدة من الملاءمة. راقب التنوع بفجوة الأفضل ناقص المتوسط وبعدد الأنماط الجينية المتمايزة، وقاوم فقدانه بخفض ضغط الانتقاء وتشارك الملاءمة والازدحام وإعادة التشغيل والتقسيم إلى جزر. وأخيرًا: ضع الميزانية بالتقييمات لا بالأجيال، فتقييم الملاءمة هو حيث يذهب الوقت.