loop الـ genetic algorithm (الخوارزمية الجينية) | ML-101

الـ loop من أولها لآخرها

الدرس 13.1 قال إن الـ genetic algorithm أربع قرارات — الـ representation، والـ fitness، والـ selection، والـ variation. والدرس ده بيخلّي كل واحد فيهم ملموس. وكل اللي جاي تحت واقع جوه loop واحدة مبتتغيّرش:

1. اعمل population ابتدائية من candidates عشوائيين. 2. قيّم الـ fitness بتاعة كل candidate. 3. وطول ما فيه ميزانية: اختار الـ parents بالـ selection، وأعد تركيبهم بالـ crossover، وهزّ الأبناء بالـ mutation، وقيّم الأبناء، وقرّر أنهي candidates يكوّنوا الـ population الجاية. 4. رجّع أحسن candidate شفته في أي وقت — وده، زي ما قسم الـ elitism بيشرح، مش أوتوماتيك أحسن candidate في آخر population.

خد بالك التكلفة واقعة فين. الـ selection والـ crossover والـ mutation عمليات حسابية على data structures قصيرة، وعمليًا ببلاش. الخطوة 2 هي اللي الفلوس بتتصرف فيها: لو الـ fitness معناها تدريب model، فـ population من 50 على مدار 100 جيل يعني 5,000 run تدريب. وكل اختيار parameter تحت هو في الحقيقة قرار عن إزاي تصرف التقييمات دي.

الـ encoding: الاختيار اللي بيقيّد كل حاجة

الـ representation هو أول قرار لأن عوامل الـ variation لازم تشتغل عليه. اختار وحش وهتلاقي الـ crossover بتاعك بيطلّع أبناء مش حلول صحيحة أصلًا. أربع encodings بيغطّوا تقريبًا كل حاجة:

الـ bit strings. الصورة الكلاسيكية، واللي هولاند (1975) حلّلها وجولدبرج (1989) بنى عليها أمثلته المحلولة. كل bit مفتاح، أو مجموعة bits بتشفّر رقم بيتفك لمدى. ومناسبة تمامًا لاختيار الـ subsets: مع 40 feature مرشّحة، string من 40 bit هي الـ subset.

فك encoding L bit لرقم حقيقي محدود

x = x_{\min} + \frac{x_{\max} - x_{\min}}{2^{L} - 1} \sum_{i=0}^{L-1} b_i \, 2^{i}

المجموع بيقرا الـ L bit كرقم صحيح unsigned بين 0 واتنين أُس L ناقص واحد، والكسر بيعيد scaling الرقم ده على المدى اللي يهمّك. والنتيجة اللي تستاهل تاخد بالك منها هي الـ resolution: الـ L bit بيدّوك العدد ده من القيم المختلفة ومش أكتر، فـ encoding من 10 bits لـ learning rate بين 0 و1 ميقدرش يعبّر غير عن خطوات قد 0.001 تقريبًا. ولو الـ parameter متصل بجد، فالـ real-valued encoding بيتجنّب السقف ده خالص.

الـ real-valued vectors. رقم عشري واحد لكل parameter، وده الاختيار الطبيعي للكميات المتصلة زي قوة الـ regularization أو coefficient filter. مفيش خطوة فك encoding ولا حد للـ resolution، بس العوامل بتتغيّر: قلب الـ bits مالوش معنى ومكانه بييجي الـ Gaussian perturbation.

الـ permutations (التباديل). لما الحل يبقى ترتيب — ترتيب زيارة فريق لعشرين موقع، أو ترتيب العمليات في جدولة — الـ candidate بيبقى permutation، والصحة بتبقى قيد صارم: كل عنصر لازم يظهر مرة واحدة بالظبط. وده الـ encoding اللي الـ crossover الساذج بيتكسر فيه، زي ما هيبان تحت.

الأشجار. لما اللي بيتطوّر يبقى تعبير أو برنامج، الـ candidate بيبقى شجرة: operators في الـ internal nodes، ومتغيّرات وثوابت في الأوراق. والـ crossover بيبدّل الـ subtrees. ده الـ representation اللي بيستخدمه الـ genetic programming والـ symbolic regression، والدرس 13.4 بيرجع له.

اختبار الـ encoding الكويس

اسأل أي representation بتفكّر فيه سؤال واحد: هل الـ crossover والـ mutation الطبيعيين بتوعه بيطلّعوا candidates صحيحين؟ لو الإجابة أيوه، الطريقة كلها بتفضل بسيطة. ولو لأ، فإنت دلوقتي محتاج إجراءات repair أو constraint handling — ودي تكلفة حقيقية، وجزء من موضوع الدرس 13.3. وسؤال تاني أخف: هل القيم اللي معناها قريب مكتوبة بشكل قريب؟ في الـ binary encoding العادي، 127 هي 01111111 و128 هي 10000000 — رقمين ورا بعض كل bit فيهم مختلف، فمفيش mutation واحدة تقدر تنقلك من واحد للتاني. واقلب نفس الـ bit العالي في 127 تاخد 255. فالقرب في القيمة مش قرب في الـ encoding، وعشان كده غالبًا بيتفضّل الـ real-valued encoding، أو الـ Gray code اللي فيه الرقمين المتتاليين بيختلفوا في bit واحد بالظبط.

الـ selection: اختيار الـ parents

الـ selection هو الخطوة الوحيدة اللي بتستشير الـ fitness، فمنه بييجي اتجاه البحث. وتلات مخططات بيغطّوا الممارسة المعتادة.

الـ tournament selection (انتقاء المباريات). اختار k candidates عشوائي من الـ population وخلّي أحسنهم يبقى parent. كرّر ده لكل مقعد أبوّة. وحجم الـ tournament k هو مقبض الـ selection pressure: k = 2 لطيف وبيعدّي الـ candidates الضعاف كتير، أما k الكبير فمعناه إن مفيش حد بيخلّف غير الـ candidates القريبين من الأحسن. وبراد ميلر وديفيد جولدبرج (1995) حلّلوا الـ tournament selection بالصيغة دي بالظبط. وهو كمان المفضّل عمليًا لسببين عاديين: مش محتاج مجموع كلّي ولا sorting، مقارنات بس، ومبيتأثّرش بإضافة ثابت على كل قيم الـ fitness.

الـ roulette wheel، أو الـ fitness-proportionate selection. دّي كل candidate قطاع من عجلة متناسب مع الـ fitness بتاعته، وبعدين لفّها. برمجيًا: اعمل المجموع التراكمي لقيم الـ fitness، واسحب رقم عشوائي منتظم بين 0 والمجموع، وخد الـ candidate اللي المدى التراكمي بتاعه فيه الرقم ده. وليه نقطتين ضعف حقيقيين. الـ fitness لازم تبقى مش سالبة عشان القطاعات يبقى ليها معنى، فالـ loss أو الـ error لازم يتحوّلوا الأول. وزي ما الدرس 13.1 بيّن بمثال 10 قصاد 9 اللي بقى 1000 قصاد 999، الضغط اللي بيطبّقه بيعتمد على المقياس والإزاحة العشوائيين لقيم الـ fitness بتاعتك.

الـ rank-based selection (الانتقاء المبني على الرتبة). اعمل sort للـ population ودّي كل candidate احتمال selection من الـ rank بتاعه، وارمي قيم الـ fitness الخام خالص. جيمس بيكر (1985) اقترح ده بالظبط عشان يفصل الـ selection pressure عن مقياس الـ fitness. والشكل المعتاد خطّي في الـ rank بمعامل ضغط واحد:

الـ linear rank-based selection

p_i = \frac{1}{N}\left( s - 2(s-1)\,\frac{i-1}{N-1} \right), \qquad 1 \le s \le 2

الـ rank i = 1 هو أحسن candidate وi = N هو الأوحش. الاحتمالات مجموعها 1 لأي s في المدى، وأحسن candidate بياخد s/N والأوحش (2 − s)/N. وعند s = 1 كل candidate بياخد 1/N بالظبط — مفيش ضغط خالص، يعني اختيار أبوّة عشوائي. وعند s = 2 الأحسن بياخد ضعف النصيب المتوسط والأوحش مبياخدش حاجة. وفايدة الـ parameterization دي إن s معناه نفس الحاجة أيًّا كانت أرقام الـ fitness بتاعتك.

الـ crossover: إعادة تركيب parentين

الـ crossover (التهجين) هو العامل اللي بيخلّي العيلة دي مختلفة عن كل طريقة بحث بنقطة واحدة. بيتطبّق باحتمال p_c؛ وباحتمال 1 − p_c الـ parentين بيتنسخوا زي ما هما. والمعدلات في المدى من 0.6 لـ 0.9 هي نقطة البداية المنتشرة، ورسالة دي يونج سنة 1975 هي الدراسة التجريبية البدرية لإعدادات زي دي — خدها كـ defaults معقولة تبدأ منها، مش قيم مثالية متقاسة لمسألتك.

الـ one-point crossover. اختار مكان قطع ودّي الابن كل اللي قبل القطع من الـ parent A وكل اللي بعده من الـ parent B. الـ two-point crossover. اختار قطعين وبدّل الحتة اللي في النص. الـ uniform crossover. قرّر كل مكان لوحده برمي عملة، فتاخد الـ gene ده من A أو من B.

والفرق بينهم هو أنهي بنية بتنجو. الـ one-point crossover بيخلّي الـ genes اللي واقعة قريبة من بعض على الـ string مع بعض، ونادرًا ما بيفصلها — فمع binary encoding القرار العشوائي إنك كتبت أنهي parameter في أنهي مكان بيبدأ يفرق. والأثر المكاني ده هو موضوع تحليل هولاند سنة 1975 عن أنهي patterns بتنجو من الـ recombination. أما الـ uniform crossover فمالوش أي تفضيل مكاني خالص، ودي بالظبط قوّته وضعفه: مفيش حاجة مميّزة، ولا فيه بلوك طويل من الـ genes المتوافقة في أمان.

وللـ real-valued vectors فيه اختيار رابع مالوش مقابل في الحالة المنفصلة — اخلط الـ parentين بدل ما تقطعهم:

الـ arithmetic (blend) crossover

\mathbf{x}_{\text{child}} = \lambda \, \mathbf{x}_A + (1-\lambda) \, \mathbf{x}_B, \qquad \lambda \in [0,1]

ابن على الخط المستقيم بين الـ parents بتوعه، وλ مسحوبة عشوائي. وليه خاصية تستاهل تبقى واخد بالك منها مش تتفاجئ بيها: كل ابن واقع جوه الصندوق اللي ممدود بين الـ parentين، فالـ blending لوحده ميقدرش غير يقلّص المنطقة اللي الـ population بتغطّيها. والـ mutation هي اللي بتخلّي البحث قادر يخرج منها.

الـ permutations محتاجة عامل خاص بيها. اقطع ترتيبين زيارة عند نقطة والزقهم وغالبًا هتاخد كلام فاضي — مسار بيزور الموقع 3 مرتين وعمره ما بيزور الموقع 7. والـ order crossover (تهجين الترتيب) بيحل ده بالبنا: انسخ حتة متصلة من الـ parent A للابن، وبعدين املا الأماكن الفاضية بالعناصر اللي الابن لسه ناقصها، وخدها بالترتيب اللي بتظهر بيه في الـ parent B.

الـ order crossover، محلول

الـ parent A هو 1 2 3 4 5 6 7 8 والـ parent B هو 3 7 5 1 6 8 2 4. انسخ الأماكن من 4 لـ 6 من A، فالابن بيبدأ كده: _ _ _ 4 5 6 _ _. والعناصر الناقصة هي 1 و2 و3 و7 و8؛ وبتظهر في الـ parent B بالترتيب 3 وبعدين 7 وبعدين 1 وبعدين 8 وبعدين 2. املا الأماكن الفاضية من الشمال لليمين بداية من المكان 7، ولف للأول: المكان 7 بياخد 3، والمكان 8 بياخد 7، وبعدين الأماكن 1 و2 و3 بياخدوا 1 و8 و2. والابن هو 1 8 2 4 5 6 3 7 — permutation صحيحة ورثت سلسلة محطّات ورا بعض من A والترتيب النسبي لكل اللي فاضل من B. والصحة مش متصلّحة بعد ما حصلت؛ دي مستحيل تتكسر.

الـ mutation، والـ trade-off في المعدل

الـ mutation (الطفرة) هي العامل اللي يقدر يدخّل مادة مكانتش عند أي parent. الـ crossover مبيعملش غير إنه يخلط اللي موجود أصلًا في الـ population، فمن غير الـ mutation القيمة اللي ضاعت من كل candidate تبقى ضاعت للأبد.

الـ bit flip. عدّي على كل bit واقلبه باحتمال p_m. ولأن القلبات مستقلة، العدد المتوقّع للـ bits اللي اتغيّرت في الابن هو طول الـ string مضروب في المعدل ببساطة:

القلبات المتوقّعة لكل ابن

\mathbb{E}[\text{flips}] = L \, p_m

مجموع L تجربة Bernoulli مستقلة. وعشان كده معدل mutation قد مقلوب طول الـ string نقطة بداية منتشرة للدرجة دي — بيخلّي التغيير المتوقّع bit واحد بالظبط لكل ابن، أيًّا كان طول الـ string. واقرا المعادلة بالعكس كمان: معدل ثابت قد 0.01 معناه قلبة متوقّعة واحدة على string من 100 bit وعشرة على string من 1000 bit، فالمعدل المنسوخ من مسألة تانية مش شايل نفس المعنى.

الـ Gaussian perturbation. لـ real-valued vector، زوّد Gaussian noise متوسطه صفر على كل مكوّن: x′ = x + σ ε حيث ε مسحوبة من توزيع طبيعي معياري. وهنا σ هي حجم الخطوة وهي المقابل لمعدل الـ bit flip؛ ومن الممارسات المنتشرة إنك تصغّرها مع تقدّم الـ run، فالأجيال البدرية تستكشف على نطاق واسع والأجيال المتأخرة تصقل.

الـ swap. لـ permutation، بدّل العنصرين اللي في مكانين متختارين عشوائي. وزي الـ order crossover، ميقدرش يطلّع candidate مش صحيح.

الـ trade-off في فقرة واحدة. معدل واطي قوي فالتنوّع عمره ما بيرجع: الـ population بتعمل convergence، والـ crossover بين parents شبه بعض بيبطّل يطلّع أي جديد، والـ run بتقف — ودي الـ premature convergence بتاعة الدرس 13.1 جاية من طريق تاني. ومعدل عالي قوي فالأبناء بيبطّلوا يشبهوا الـ parents بتوعهم، فالبنية الكويسة بتتدمّر بنفس سرعة ما الـ selection بيلاقيها وتبقى دفعت تمن population عشان تعمل random search. ورسالة دي يونج سنة 1975 هي الشغل التجريبي البدري هنا، والإعدادات اللي اتشهرت بيها — population بالعشرات، ومعدل crossover عالي، ومعدل mutation صغير في حدود bit واحد في الألف — لسه مكان معقول تبدأ منه. عاملها كـ defaults تتظبط على منحنى الـ fitness بتاعك، مش كحقائق.

الـ elitism: إنك تخسر أحسن حل bug حقيقي

دي خاصية في الـ loop بتفاجئ الناس أول مرة يشوفوها. الـ selection عشوائي، فممكن أحسن candidate في الـ population ببساطة ميتختارش. وحتى لو اتختار، الـ crossover والـ mutation مدمّرين بالتصميم، فاللي بيدخل الجيل الجاي نسخة متعدّلة. اجمع الحاجتين وهتلاقي إن أحسن fitness في الـ population ممكن تقل من جيل للي بعده. ومفيش حاجة في الـ loop زي ما اتوصفت لحد دلوقتي بتمنع ده.

وفيه حمايتين معتادين وإنت عايز واحدة منهم على الأقل. الـ elitism (الاحتفاظ بالنخبة) بينسخ أحسن e candidates للجيل الجاي من غير تغيير، فبيضمن رياضيًا إن أحسن fitness في الـ population مبتقلّش؛ وe = 1 أو نسبة صغيرة من الـ population حاجة معتادة. وبشكل منفصل، وأرخص كمان، احتفظ بسجل الأحسن على الإطلاق بره الـ population: كل ما تقيّم candidate يعدّي الحالي، خزّن نسخة منه. ورجّع ده في الآخر، مش أحسن واحد في آخر جيل.

اقرا منحنى الـ fitness بتاعك بعناية

المنحنى اللي طالع بنعومة في أغلب الرسومات المنشورة هو منحنى الأحسن لحد دلوقتي، ومنحنى الأحسن لحد دلوقتي ميقدرش ينزل بحكم التعريف — فمبيثبتش أي حاجة عن إذا كانت الـ loop بتاعتك بتحفظ أي حاجة. ارسم أحسن fitness في الـ population الحالية كمان. لو الأثر ده نزل فإنت بتخسر حلول، وأي run توقّفها بدري ممكن ترجّع حاجة أوحش من اللي لقيته أصلًا. ومتبالغش في التصحيح: الـ elitism بـ e كبير هو selection pressure باسم تاني، فبيزقّ لانهيار التنوّع بتاع الدرس 13.1 بنفس الموثوقية اللي بيزقّ بيها tournament حجمه زيادة.

الـ replacement: generational ولا steady-state

الـ generational replacement (الاستبدال الجيلي) بيبني N ابن وبيبدّل الـ population كلها بيهم في خطوة واحدة. بسيط، ومتوازي بسهولة تامة — التقييمات الـ N مستقلة، وينفع تتنفّذ كلها في نفس الوقت — وهو المخطط الأكتر احتياجًا للـ elitism، لأنه بيرمي كل الـ parents.

الـ steady-state replacement (الاستبدال المستقر) بيطلّع ابن أو اتنين في كل iteration ويدخّلهم في الـ population الموجودة، ويطلّع حد منها: أوحش candidate، أو أقدمهم، أو الأشبه بالـ parents بتوع الابن. ومفيش حاجة بتستنّى حدود الجيل، فالـ gene الكويس بيبدأ يتعاد استخدامه على طول. وده بيخلّي الـ selection pressure الفعّال أعلى بنفس الإعدادات الاسمية، ودي حاجة ليها حدّين: تقدّم أسرع، وانهيار تنوّع أسرع لو مكنتش بتراقب.

وبين الطرفين فيه فكرة إنك تبدّل جزء بس من الـ population في كل دورة — الـ generation gap (فجوة الجيل)، اللي دي يونج (1975) درسها كـ parameter صريح. وأي حاجة بين فرد واحد والـ population كلها متاحة ليك، وده مقبض تاني على نفس الـ trade-off.

مقبض الـ exploration والـ exploitation، كـ parameters ملموسة

الـ exploration (الاستكشاف) والـ exploitation (الاستغلال) شعار لحد ما تقدر تسمّي الإعدادات اللي بتحرّكه. وفي الـ genetic algorithm تقدر:

ناحية الـ exploration: population N أكبر؛ وحجم tournament k أصغر، أو rank pressure s أقرب لـ 1؛ ومعدل mutation أو σ Gaussian أعلى؛ وelites أقل؛ وgenerational replacement مش steady-state. ناحية الـ exploitation: k أكبر أو s أقرب لـ 2؛ وelites أكتر؛ وsteady-state replacement؛ وσ أصغر، خصوصًا في آخر الـ run.

وتشخيصين بيخلّوا الـ tuning تجريبي مش خرافات. الأول، ارسم التنوّع جنب الـ fitness — انتشار الـ population، بأي طريقة قِسته، سواء بمتوسط المسافة بين كل اتنين على الـ real vectors أو بنسبة الأماكن اللي لسه متثبّتتش على الـ bit strings. انهيار التنوّع في أول كام جيل معناه ضغط زيادة؛ وتنوّع فاضل عالي مع أحسن fitness بالعافية بتتحرّك معناه ضغط ناقص. التاني، افتكر الميزانية بتاعتك بتشتري إيه فعلًا: N مضروب في عدد الأجيال هو عدد تقييمات الـ fitness، وحاصل الضرب ده مش عدد الأجيال هو فاتورتك. ومضاعفة الـ population بتقسم الأجيال اللي تقدر عليها على اتنين.

أهم اللي اتعلّمته

الـ loop ثابتة: initialization، وتقييم، وبعدين تكرار الـ selection والـ crossover والـ mutation والتقييم والـ replacement — ورجّع أحسن candidate شفته في أي وقت.
تقييم الـ fitness هو اللي مسيطر على التكلفة. حجم الـ population مضروب في عدد الأجيال هو عدد التقييمات اللي بتشتريه.
الـ encodings هي الـ bit strings، والـ real-valued vectors، والـ permutations، والأشجار. والاختبار الصح هو هل العوامل الطبيعية بتطلّع candidates صحيحين.
الـ tournament selection بيخلّي الضغط مقبض صريح عن طريق حجم الـ tournament (ميلر وجولدبرج، 1995)؛ والـ rank selection بيطلّع مقياس الـ fitness من الصورة (بيكر، 1985)؛ والـ roulette selection حسّاس للمقياس والإزاحة مع بعض.
الـ one-point والـ two-point crossover بيحافظوا على الـ genes اللي جنب بعض فبيخلّوا المكان على الـ string ليه معنى؛ والـ uniform crossover من غير تحيّز مكاني؛ والـ permutations محتاجة عامل بيحافظ على الترتيب زي الـ order crossover.
القلبات المتوقّعة لكل ابن هي L مضروب في معدل الـ mutation، وعشان كده معدل قد مقلوب طول الـ string نقطة بداية منتشرة.
من غير الـ elitism أحسن fitness في الـ population ممكن تقل من جيل للي بعده. احتفظ بالـ elites، واحتفظ بنسخة الأحسن على الإطلاق، وارسم أحسن الـ population مش منحنى الأحسن لحد دلوقتي بس.
الـ generational replacement بسيط ومتوازي؛ والـ steady-state بينشر الـ candidates الكويسين على طول وبيعلّي الضغط الفعّال. والـ generation gap واقعة بينهم.
الـ exploration والـ exploitation مش مزاج لكن ست إعدادات ملموسة: N، وk أو s، ومعدل الـ crossover، ومعدل الـ mutation أو σ، وعدد الـ elites، ومخطط الـ replacement.