علوم الحاسوب من التطور: مقدمة في الخوارزميات الجينية

الصورة عن طريق هال جيتوود على Unsplash

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

في محاولة لاختبار بعض ما تعلمته حتى الآن ، وتبادل نتائجي مع بقية العالم ، قررت أن أجمع سلسلة من المقالات حول هذا الموضوع.

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

الحياة على الارض

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

Venus Flytrap عبارة عن نبات آكلة اللحوم يتغذى بشكل أساسي على الحشرات والعناب.تستخدم بعض الخفافيش تحديد الموقع بالصدى للتنقل والبحث عن الفرائس وخلافا للاعتقاد السائد ، فإن الخفافيش ليست في الحقيقة أعمى ؛ هناك نوع من الخفافيش المعروفة باسم The Flying Foxes لديها بالفعل بصيرة أفضل من البشر.لا يمكن أن تطير Flying Fish بنفس الطريقة التي تعمل بها الطيور ، ومع ذلك ، يمكن لهذه الأسماك أن تقفز قفزات قوية ذاتية الحركة من الماء حيث تمكنها زعانفها الشبيهة بالأجنحة الطويلة من الانزلاق لمسافات طويلة فوق سطح الماء.

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

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

الساعاتي الأعمى

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

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

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

ما هي الخوارزميات الجينية ولماذا نحتاجها؟

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

تطرح مشكلة البائع المتجول السؤال التالي: "بالنظر إلى قائمة المدن والمسافات بين كل زوج من المدن ، ما هو أقصر طريق ممكن يزور كل مدينة ويعود إلى المدينة الأصلية؟" كومبيناتوريال الأمثل.

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

كيف تعمل الخوارزميات الجينية؟

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

والخطوات هي كما يلي:

1. إنشاء مجموعة أولية من الحلول الممكنة N (الحساء البدائي)

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

2. رتب حلول السكان حسب اللياقة (البقاء للأصلح ، الجزء 1).

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

في مشكلة البائع المتجول ، يمكن أن تكون وظيفة اللياقة البدنية عبارة عن حساب لإجمالي المسافة المقطوعة بواسطة الحل. حيث تعادل مسافة أقصر اللياقة البدنية العالية.

3. اعدام الحلول الأضعف (البقاء للأصلح ، الجزء 2)

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

تعرف الخطوتين 3 و 4 مجتمعين بالاختيار.

4. تولد حلول أقوى (البقاء للأصلح ، الجزء 3)

ثم يتم إقران الحلول المتبقية مع بعضها البعض من أجل التزاوج وإعادة إنتاج النسل. خلال هذه العملية ، في أبسط أشكالها ، سوف يساهم كل من الوالدين بنسبة٪ من جيناتهم (بطبيعتها هي 50/50) لكل من نسلهم ، حيث P1 (G)٪ + P2 (G)٪ = 100 ٪. عملية تحديد أي من جينات الوالدين التي سيرثها النسل تعرف باسم كروس.

5. تحور جينات النسل (طفرة)

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

من المهم ملاحظة أنه لا يلزم حدوث طفرة مع كل ذرية ، كما يمكن أن يكون تردد الطفرة المطلوب معلمة للخوارزمية.

في الخوارزميات الجينية ، يُعرف الاختيار والتقاط والتحول باسم العوامل الوراثية.

6. الإنهاء

سيتم تكرار الخطوات من 2 إلى 5 حتى نقطة إنهاء محددة مسبقًا. يمكن أن تكون نقطة الإنهاء هذه واحدة مما يلي:

  1. تم تخصيص الحد الأقصى للوقت / الموارد.
  2. لقد مر عدد الأجيال الثابتة.
  3. لا يمكن تجاوز مدى ملاءمة الحل المهيمن من قبل أي أجيال مستقبلية.

تقارب الحل

1. العالمية الأمثل

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

2. المحلية الأمثل

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

الأمثل العالمي مقابل الأمثل المحلي

ماذا سيحدث إذا لم تكن هناك طفرات؟

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

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

بدون طفرات ، لن يكون لدينا طفرات ، وبدون طفرات ، لن يكون لدينا امتياز X-men.

ماذا سيحدث إذا لم يكن حجم السكان كبيرًا بدرجة كافية؟

لقد كنت مؤخرًا في Jukani Wildlife Sanctuary في Plettenberg ، حيث تشرفت بمقابلة نمر أبيض. لقد كان حيوانًا مهيبًا حقًا. لقد كان كبيرًا ، وبدا ضارًا ، وكان أيضًا 80٪ أعمى ويزداد سوءًا مع مرور السنين.

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

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

النمر الأبيض الذي التقيته في محمية جوكاني للحياة البرية في أبريل 2019. إنه يبدو مهيبًا ، لكنه يعاني.

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

الصورة بواسطة redcharlie على Unsplash.

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

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

ملك هابسبورغ تشارلز الثاني ملك إسبانيا. كان والده عم والدته ، وجعل تشارلز ابنهما وابن أخيه وابن عمه الأول على التوالي.

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

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

تغليف

حسنا ، هذا يجب أن يغطي الأساسيات. إذا كان لديك أي أسئلة أو طلبات أو طفرات جينية للمساهمة ، فيرجى ترك تعليق أدناه.

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