تصميم الـ fitness function (دالة الملاءمة) | ML-101

الـ fitness function (دالة الملاءمة) مش تفصيلة في التنفيذ — دي صياغة المسألة نفسها. وتصميمها الوحش هو أكتر سبب منتشر لفشل الـ genetic algorithm.

الـ fitness هي الهدف

الـ genetic algorithm مالهاش رأي في مسألتك. مبتشوفش شبكة الطرق، ولا ميزانية الراديو، ولا العميل. كل اللي بتشوفه هو الرقم الواحد اللي الـ fitness function بترجّعه لكل candidate، وبعدين الـ selection بيكتّر أي حاجة بتاخد رقم عالي. ودي الآلية كلها. وعشان كده الـ fitness function مش تفصيلة في التنفيذ: هي صياغة مسألتك، مكتوبة باللغة الوحيدة اللي البحث يقدر يقراها.

Holland (1975) حط في كتابه Adaptation in Natural and Artificial Systems الإطار اللي فيه الـ selection بيشتغل على population من البُنى على حسب عائد متقاس، وكتاب Goldberg (1989) هو المعالجة المرجعية اللي جت بعده. وفي الاتنين الـ fitness هي البيئة: غيّرها تغيّر الـ population هتبقى إيه. وكل اللي في الدرس ده طالع من الحقيقة الواحدة دي.

القاعدة الوحيدة اللي البحث بيطيعها

الـ genetic algorithm بتكبّر الـ function اللي إنت كتبتها، مش الهدف اللي كان في دماغك. وكل أشكال الفشل في الدرس ده فجوة بين الحاجتين دول. فلما run تطلّع كسبان مالوش معنى، اتّهم الـ fitness function قبل ما تتّهم الـ operators.

كافئ النتيجة، مش السلوك

أكتر طريقة منتشرة تكتب بيها fitness function وحشة إنك تتخيّل إنت كنت هتحل المسألة إزاي، وبعدين تقيّم الـ candidates على قد ما بيقلّدوك. افترض إنك بتطوّر جدول duty cycle لـ sensor شغّال على بطارية، وعايزه يعيش أطول فترة ممكنة ويفضل مفيد. هيبقى مغري إنك تكافئ سلوك «سيب الراديو مقفول»، لأنك عارف إن الراديو بيستهلك أغلب الطاقة. اعمل كده والبحث هيلاقي بالظبط اللي طلبته: جدول الراديو فيه مقفول، وبطارية بتعيش كتير، ومفيش أي بيانات بتوصل خالص.

والحل إنك تقيس النتيجة اللي تهمّك فعلًا — عدد القرايات المفيدة اللي وصلت لكل شحنة بطارية — وتسيب البحث يكتشف لوحده إن ده محتاج الراديو يفضل مقفول أغلب الوقت. الـ fitness function اللي بتشفّر طريقتك المفترضة متقدرش غير إنها تعيد اكتشاف طريقتك. أما اللي بتشفّر النتيجة فحرّة تلاقي حاجة أحسن.

ولما النتيجة تبقى فعلًا مينفعش تتقاس واضطرّيت تستخدم proxy، فعامله كفرضية مش كهدف: افحص الفرد الكسبان بإيدك قصاد الهدف الحقيقي قبل ما تثق فيه. والوحدة 14 بتقابل نفس الخطر من الناحية التانية، واسمه هناك الـ reward hacking (قرصنة المكافأة) — الـ agent بيحسّن اللي إنت قِسته، مش اللي إنت قصدته.

مثال محلول: توزيع الـ sensors

خلّينا محدّدين: عندك 40 موقع مرشّح لـ sensors بيئية على أرض متقسّمة لـ 200 خلية grid. كل موقع بيغطّي مجموعة خلايا معروفة وليه تكلفة تركيب معروفة، ومعاك ميزانية ثابتة. وزي الدرس 13.2، الـ candidate هو binary string طولها 40 — الـ bit i بيساوي 1 لو الموقع i اتستخدم.

وأول fitness function بديهية هي «عدد الخلايا المختلفة المتغطّية». شغّلها والـ population هتعمل convergence ناحية strings كلها تقريبًا وحايد: تغطية لأقصى حد، وفاتورة أضعاف الميزانية. مفيش حاجة في الـ function دي بتجيب سيرة الفلوس، فمفيش سبب يخلّي البحث يهتم بيها. والمثال الواحد ده شايل باقي الدرس — فيه هدفين متعارضين، وقيد صارم، وخطوة تقييم بتاخد وقت حقيقي.

المسائل اللي فيها كذا هدف

التغطية لازم تعلى والتكلفة لازم تقل. ومفيش إجابة واحدة أحسن لده، فيه مجموعة trade-offs مقبولة، والسؤال هو أنهي واحد منهم الـ algorithm مسموح لها ترجّعه.

الـ weighted sums (المجاميع الموزونة)

أبسط طريقة بتطوي الأهداف في رقم واحد بـ weights بتختارها مسبقًا.

fitness الـ weighted sum

F(\mathbf{x}) = \sum_{i=1}^{m} w_i \, \tilde{f}_i(\mathbf{x}), \qquad w_i \ge 0, \quad \sum_{i=1}^{m} w_i = 1

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

وفيه قيدين صريحين. الأول إن الـ weights قرار خدته قبل ما تشوف أي حاجة من الـ trade-off، وإن الـ run الواحدة بترجّع trade-off واحد. والتاني إن الـ weighted sum ميقدرش يرجّع غير حلول واقعة على الجزء الـ convex من سطح الـ trade-off؛ أما الـ trade-offs اللي مستخبية في جزء concave من السطح ده فمينفعش توصلها بأي اختيار للـ weights.

الـ Pareto dominance والـ front

الطريقة البديلة بترفض طي الأهداف من أساسه. بنقول إن حل dominates (يهيمن على) حل تاني لو مش أقل منه في جودة أي هدف وأحسن منه فعلًا في هدف واحد على الأقل.

الـ Pareto dominance (بتكبير كل الأهداف)

\mathbf{a} \succ \mathbf{b} \iff \big(\forall i:\; f_i(\mathbf{a}) \ge f_i(\mathbf{b})\big) \;\wedge\; \big(\exists j:\; f_j(\mathbf{a}) > f_j(\mathbf{b})\big)

اقراها كده: الحل a مش أوحش في أي حتة وهو أحسن في حتة ما. والحلول اللي مفيش حاجة في الـ population بتهيمن عليها بتكوّن الـ non-dominated set؛ أما الـ non-dominated set في فضاء البحث كله فهي الـ Pareto front (جبهة باريتو).

الـ genetic algorithm اللي فيها كذا هدف بترجّع تقريب للـ front ده بدل نقطة واحدة، وبعدين البني آدم بيختار منها وهو شايف بالظبط كل خلية تغطية زيادة بتكلّف قد إيه. وده عادةً الـ output الأنفع، لأن الـ weights في الحقيقة مكانتش معروفة مسبقًا.

نظرة على NSGA-II

الـ elitist multi-objective genetic algorithm المرجعية هي NSGA-II، من Deb وPratap وAgarwal وMeyarivan (2002). تلات أفكار، ويستاهل تميّز كل واحدة فيهم:

الـ fast non-dominated sorting — بيقسم الـ population لـ fronts. الـ front الأول هو الـ non-dominated set، والتاني هو اللي بيبقى non-dominated بعد ما تشيل الأول، وهكذا. والـ rank الأقل دايمًا مفضّل.
الـ crowding distance (مسافة الازدحام) — الفيصل عند التعادل جوه الـ front، لأن مفيش عضو في الـ front أحسن من التاني بحكم التعريف. بيقدّر قد إيه فضاء الأهداف فاضي حوالين كل حل وبيفضّل الحلول اللي في المناطق المتفرّقة. وده اللي بيحافظ على انتشار الـ front اللي راجع بدل ما يتكتّل.
الـ elitism بالدمج — الـ parents والأبناء بيتجمّعوا في مجموعة واحدة، وبعدين بيترتّبوا بـ rank الـ front، وجوه الـ front بالـ crowding distance، وبعدين بيتقصّوا لحجم الـ population تاني. فمينفعش حل كويس يضيع بالغلط، ودي نفس الحجة اللي اتقالت للـ elitism في الدرس 13.2.

الطريقة	بترجّع إيه	بتناسب إمتى	القيد
هدف واحد مع penalty	حل واحد	هدف حقيقي واحد والباقي قيود	محتاج اختيار كويس لـ weights الـ penalty
الـ weighted sum	trade-off واحد	لما الـ trade-off يبقى معروف مسبقًا فعلًا	مبيوصلش للأجزاء الـ concave من سطح الـ trade-off
الـ Pareto front (NSGA-II)	انتشار من الـ trade-offs	لما بني آدم يختار بعد ما يشوف الاختيارات	آلية أتقل، والـ front محتاج عرض وقراية

التعامل مع الـ constraints

الميزانية في مثال الـ sensors مش هدف بيتعمل عليه trade-off — دي حيطة. وفيه أربع طرق مرجعية تعلّم بيها الـ genetic algorithm إن فيه حيطة، وبيختلفوا في قد إيه من فضاء البحث بيفضل صالح للاستخدام.

الـ penalized fitness

F(\mathbf{x}) = f(\mathbf{x}) - \sum_{j=1}^{k} \lambda_j \, \max\!\big(0,\, g_j(\mathbf{x})\big)^{2}

كل constraint بيتكتب بحيث الانتهاك يخلّي القيمة g موجبة، والـ penalty بتكبر مع حجم الانتهاك. وتربيعها معناه إن تجاوز صغير للميزانية بيكلّف شوية وتجاوز كبير بيكلّف كتير، فالبحث بيفضل قادر يشوف الاتجاه اللي راجع لمنطقة الـ feasibility.

الـ penalty

بتليّن الحيطة

اطرح حد متناسب مع الانتهاك. الأفراد اللي مش feasible بتفضل في الـ population وتقدر تورّث genes مفيدة.

الـ rejection

اسمها كمان death penalty

دّي أي candidate مش feasible أوحش fitness ممكنة. بسيطة، بس مالهاش لازمة لما الحلول الـ feasible تبقى نادرة — مفيش حاجة البحث يطلعها.

الـ repair

صلّحه وبعدين قيّمه

حوّل الـ candidate اللي مش feasible لـ candidate feasible قريب قبل التقييم — هنا: شيل الـ sensors الأقل جدوى اقتصادية لحد ما الفاتورة تتظبط.

operators بتحافظ على الـ feasibility

الحيطة بتبقى مستحيل توصلها

صمّم الـ crossover والـ mutation بحيث ميقدروش يطلّعوا ابن مش صالح. والـ order crossover على الـ permutations (الدرس 13.2) هو المثال الكلاسيكي.

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

افحص الـ feasibility لوحدها

بلّغ دايمًا إذا كان أحسن فرد feasible كحقيقة مستقلة، مش كحاجة بتتستنتج من الـ fitness بتاعته. فالنتيجة اللي عليها penalty والنتيجة الـ feasible فعلًا رقمين من نفس النوع، والخلط بينهم هو الطريق لإنك تقدّم تصميم مش feasible كأنه الحل.

الـ premature convergence وضياع التنوّع

قوة الـ genetic algorithm جاية من إعادة تركيب حلول مختلفة. فلما الـ population تبقى نسخ شبه متطابقة من فرد واحد، الـ crossover بين اتنين منهم بيطلّع نفس الفرد تاني، والـ mutation بتفضل المصدر الوحيد للجديد — وده random walk بطيء جدًا. ده هو الـ premature convergence (التقارب المبكر): الـ run بتبطّل تتحسّن قبل ما تلاقي حاجة كويسة بكتير، ومن بره بتبان بالظبط زي run خلصت.

إزاي تكشفه

أحسن fitness ناقص المتوسط — ارسم الاتنين لكل جيل. لو الفجوة انهارت ناحية الصفر بدري يبقى الـ population بقت متماثلة.
عدد الـ genotypes المختلفة — عِدّ الأفراد الفريدين في كل جيل. والوقوع الحاد البدري هو أوضح إشارة موجودة.
ترددات الـ alleles لكل gene — في الـ binary encoding: نسبة الـ population اللي شايلة 1 في كل مكان. والأماكن اللي بتتشبّع عند 0 أو 1 هي أماكن الـ crossover مبقاش بيستكشفها.
متوسط المسافة بين كل اتنين — مسافة Hamming للـ binary strings، والمسافة الإقليدية للـ real vectors. وده القياس المباشر للحاجة اللي قلقان منها.

إزاي تقاومه

التنوّع بيضيع لما الـ selection pressure يبقى عالي بالنسبة للـ variation اللي الـ operators بتوفّره، فكل إجراء مضاد بيعدّل ناحية من الناحيتين في التوازن ده.

قلّل الـ selection pressure — حجم tournament أصغر، أو rank selection بدل الـ fitness-proportionate selection (الدرس 13.2). غالبًا أرخص حل وأول حاجة تتجرّب.
علّي معدل الـ mutation، أو علّيه بشكل adaptive لما مقياس تنوّع ينزل تحت حد معيّن.
الـ fitness sharing (تشارك الملاءمة) — خلّي الأفراد اللي شبه بعض يتنافسوا على نصيب مشترك من الـ fitness، فالزحمة بتتعاقب على إنها زحمة. وطرق الـ niching من النوع ده مشروحة في Goldberg (1989).
الـ crowding replacement — الابن الجديد بياخد مكان الفرد الأشبه بيه مش الأوحش في الـ population، فالمناطق المختلفة بتفضل مسكونة.
الـ restarts — أعد initialization الـ population مع الاحتفاظ بأرشيف لأحسن الحلول اللي لقيتها. رخيصة، وكتير بتبقى أنفع من الـ tuning.
الـ island models — كذا subpopulation بيتطوّروا منفصلين مع migration من وقت للتاني، فلو واحدة عملت convergence الباقيين مبيعملوش.

الـ fitness sharing

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

حساب التكلفة

في تقريبًا كل تطبيق واقعي، تقييم الـ fitness هو اللي مسيطر على وقت التشغيل. الـ selection والـ crossover والـ mutation شوية عمليات arrays، أما التقييم الواحد فممكن يبقى simulation، أو دورة build وtest، أو تدريب model كامل. فالرقم المهم مش عدد الأجيال لكن العدد الكلي للتقييمات.

ميزانية التقييمات

N_{\text{eval}} = P \cdot G, \qquad T_{\text{wall}} \approx \frac{N_{\text{eval}} \cdot t_{\text{eval}}}{K}

P حجم الـ population، وG عدد الأجيال، وt تكلفة التقييم الواحد، وK عدد الـ workers المتوازيين. والحد P اللي في الأول هو الـ population الابتدائية، اللي بتتقيّم قبل ما أي جيل يشتغل.

حط الأرقام: population من 100 فرد على 200 جيل يساوي 100 × 200 = 20,000 تقييم. وبثانيتين لكل تقييم ده بيبقى 40,000 ثانية — يعني أكتر من إحداشر ساعة بشوية على core واحد، أو حوالي واحد وعشرين دقيقة متوزّعة على اتنين وتلاتين worker. ومفيش حاجة في ده قياس لمسألة معيّنة؛ ده الضرب اللي المفروض تعمله قبل ما تبدأ الـ run مش بعدها.

طرق تصرف بيها الميزانية أحسن:

اعمل cache للنتايج على حسب الـ genotype. مع convergence الـ population نفس الفرد بيتقيّم تاني على طول. وdictionary بيربط الـ genotype بالـ fitness بتاعته مش أكتر من كام سطر، وممكن يشيل جزء كبير من الشغل في آخر الـ run.
قيّم بالرخيص الأول. قيّم على subsample من البيانات أو على simulation مختصرة، وبعدين أعد تقييم اللي نجوا بس بالتكلفة الكاملة. وخلّي بالك إن ده بيخلّي الـ fitness فيها noise، وده بيضعّف الـ selection.
استخدم surrogate model. اعمل fit لـ model رخيص لسطح الـ fitness من التقييمات اللي معاك، وافحص بيه الـ candidates، ومتدفعش التمن الكامل غير للي شكلهم واعد. ودي نفس فكرة الـ surrogate model اللي الـ Bayesian optimization بيستخدمها في الدرس 10.2.
اقطع بدري. لو candidate مش هيقدر يعدّي الأحسن الحالي في نص تقييمه، وقّفه.
نفّذ بالتوازي. كل فرد في الجيل بيتقيّم لوحده، فالـ generational genetic algorithm بتكبر بشكل شبه خطي مع عدد الـ workers. ودي ميزة بنيوية حقيقية على طرق البحث اللي تسلسلية بحتة.

احسب قبل ما تشغّل

حدّد ميزانية التقييمات الأول، وبعدين اختار حجم الـ population وعدد الأجيال عشان يناسبوها. الاتنين مهمين وبينهم trade-off: الـ population الكبيرة بتستكشف أكتر في الجيل الواحد بس بتسيب أجيال أقل لنفس الميزانية. والإعلان عن «run بـ 500 جيل» مالوش معنى لحد ما القارئ يعرف P وتكلفة التقييم الواحد.

أهم النقط

الـ fitness هي صياغة المسألة، فاتّهمها الأول لما الـ run تبوظ. كافئ النتيجة مش السلوك اللي إنت مفترض إنه بيطلّعها. ولكذا هدف: يا إما تدّيهم weights — بعد الـ rescaling، ومع إنك عارف إن الـ weighted sum مبيوصلش للأجزاء الـ concave من سطح الـ trade-off — يا إما ترجّع Pareto front، وده اللي NSGA-II (Deb et al.، 2002) بتعمله بالـ non-dominated sorting والـ crowding distance والقص الـ elitist. اتعامل مع الـ constraints بالـ penalty أو الـ rejection أو الـ repair أو operators بتحافظ على الـ feasibility، وبلّغ عن الـ feasibility دايمًا لوحدها بعيد عن الـ fitness. راقب التنوّع بفجوة الأحسن ناقص المتوسط وبعدد الـ genotypes المختلفة، وقاوم ضياعه بتقليل الـ selection pressure والـ fitness sharing والـ crowding والـ restarts والتقسيم لجزر. وفي الآخر: حط الميزانية بالتقييمات مش بالأجيال، فتقييم الـ fitness هو المكان اللي الوقت بيروح فيه.