محتوى المقال
مقدمة
المفاهيم الرئيسة
مراحل الخوارزمية الجينية
- مرحلة إنشاء المجتم عالعشوائي
- مرحلة التوافق
- مرحلة الاختيار
- مرحلة التهجين
- مرحلة الطفرة
- مرحلة الجيل الجديد
تطبيقات الخوارزمية الجينية
الملخص
المصادر
مقدمة
مقالنا اليوم يتضمن نكهة خاصة من علم الأحياء مضافة إلى التقنية.
الخوارزمية الجينية هي خوارزمية التي تحاكي نظرية التطور البيولوجي للعالم دارون، والتي تتضمن أن الجينات الوراثية يتغير ترتيبها مع الزمن من الآباء إلى الأحفاد وأن الفصيلة الأقوى هي التي ستكون قادة على البقاء (الشاهد في هذا المقال).
الجينات المتوارثة من الآباء إلى الأبناء إلى الأحفاد يتغير ترتيبها مع مرور الزمن مثلًا، لدينا خليتين لأبوين كل منهما يحتوي على 47 كروموسوم. الجيل التالي ستكون كروموسومات السلالة الناتجة هي خليط من الأبوين، وربما يكون هناك بعض الطفرات. وينتج عن التغير في الجينات تغير في الصفات الوراثية الملحوظة.
تندرج الخوارزمية الجينية تحت عدة مجالات مثل:
- الذكاء الاصطناعي
- ألعاب المتاهات
- حل المشكلات بخوارزميات البحث.
- طرائق التحسين.
المفاهيم الرئيسة
الخوارزمية الجينية: هي إيجاد الطريق الأمثل لحل مشكلة ما عن طريق التغيير في بيانات المشكلة ودوال حسابية تشبه التغيير الوراثي الحيوي في مجال التطور الحيوي.
المجتمع (Population): هو أشرطة الوراثة التي تتكون من الجينات الظاهرة في المشكلة.
الجيل (Generation): هو المظهر للنسخة والجيل الجديد هو النسخة بعد المعالجة ويكون النسخة الأحدث.
المورثة، أو الجين (Gene): هي الوحدة الأساسية للوراثة وهي جزء من الشريط الوراثي، يكون في الخوارزمية الجينية عبارة عن رقم وحيد، في الغالب على نظام العد الثنائي.
الصبغي، أو كروموسوم (Chromosome): هو الشريط الوراثي في المجتمع، يتكون في الخوارزمية الجينية في الغالب من سلسة أرقام على نظام العد الثنائي.
النمط الوراثي (Genotype): هي مجموعة البيانات الوراثية (الأرقام) الموجودة في الجيل.
النمط الظاهري (phenotype): هي المواصفات الناتجة عن التغير في الجينات الملحوظ بالعين المجردة.
دالة التوافق (Fitness): هي دالة تستخدم في الخوارزميات التطورية لتقييم مدى قيمة توافق الحل الحالي للمشكلة المطروحة.
درجة التوافق (Fitness Score): هي نتيجة توافق كل فرد (جين) في المجتمع.
الاختيار (Selection): هي المرحلة التي يتم فيها النمط الوراثي لأعلى قيمة توافق.
التهجين (Crossover): هي المرحلة التي يتم فيها تهجين شريط وراثي ناتج عن انتقال مواصفات من أب ومواصفات أخرى من أم، في الخوارزمية الجينية يكون خلط على طريقة محددة بين سلسلتي أرقام ويكون الناتج ولدين.
التزاوج (Mating): هو موقع في السلسلة يتم التهجين عندها.
أب (Parent): الشريط الوراثي الذي يتم تهجينه.
السلالة (Offspring): الشريط الوراثي الذي نتج عن التهجين.
الطفرة (Mutation): هي تغير غير محدد يطرأ على أحد جينات الشريط الوراثي يغير في مواصفات الجيل التالي.
مراحل الخوارزمية الجينية
1- إنشاء مجتمع عشوائي
في هذه الخطوة يتم إنشاء عرض للبيانات على شكل مصفوفة مربعة الأبعاد. تختلف طرق العرض من مشكلة إلى أخرى لكن في الخوارزمية الجينية يغلب استخدام نظام العد الثنائي (0و1).
2- التوافق
دالة التوافق
هذه المرحلة تقيس جودة وفاعلية كل جين في المجتمع الحالي وتتحضر القيم لمرحلة الاختيار.
3- الاختيار
دالة التوافق
هذه المرحلة تقيس جودة وفاعلية كل جين في المجتمع الحالي وتتحضر القيم لمرحلة الاختيار.
يوجد العديد من دوال وطرق الاختيار وهي طريقة لترشيح أفضل الجينات المقاربة الحل.
مثلا يكون اختيار شريطي وراثة (مجموعتين من الأفراد):
في هذه المرحلة ممكن أن تكون نهاية الخوارزمية في حال وجدت الحل المثالي.
في حال لم تجد الحل المصال ستنتقل إلى الخطوات التالية
بعض الدوال:
1. دالة عجلة روليت وهي تعمل نفس مبدأ عجلة روليت المستخدمة في الألعاب
وهي من أشهر الدوال المستخدمة في اختيار القيم.
2. دالة اختيار البطل (Tournament selection)
طرق اختيار أخرى:
- اختيار الرتبة (Rank selection)
- اختيار بولتزمان (Boltzmann selection)
- اختيار الحالة المستقرة (Steady state selection)
- اختيار الاقتطاع (Truncation selection)
- اختيار القيمة المحلية (Local selection)
- اختيار التشويش (Fuzzy selection)
4- التهجين
اختيار موقع التهجين ويعبر عنها بمصطلح التزاوج، حيث يتم اختيار موقع يتم تبديل الجينات عند بين شريطي وراثة. كم هو موضح في الصورة التالية:
5- الطفرة
مرحلة إحداث الطفرة
في هذه المرحلة يتم تغيير جين واحد (قلب) على الشريط نفسه فإذا كان واحد يصبح صفرا والعكس صحيح، كما في الصورة
6- الجيل الجديد
بعد إتمام الخطوات ستكرر العملية على الناتج الأخير بعد عمليات التهجين والطفرة والاختيار على كامل الأشرطة الوراثية في المجتمع.
تطبيقات الخوارزمية الجينية
يوجد الكثير من المشكلات التي يمكننا حلها بواسطة الخوارزمية الجينية مثل المتاهات ومسار الروبوت الذكي، والأبحاث في دراسة الأمراض من خلال تغير البروتين في الحبل الوراثي.
الملخص
- تم تعريف مفاهيم الخوارزمية الجينية وشرحها
- تم ذكر بعض دوال الاختيار وشرح وتفصيل بعضها
- تم تمثيل الخوارزمية الجينية
- تطبيقات الخوارزمية الجينية تشمل الألعاب والجينات والمتاهات، ومسار الروبوت.
المصادر
- Lee, Chang-Yong. (2003). Entropy-Boltzmann selection in genetic algorithms. IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics: a publication of the IEEE Systems, Man, and Cybernetics Society. 33. 138-49. 10.1109/TSMCB.2003.808184.
- David E. Goldberg. 1989. Genetic Algorithms in Search, Optimization and Machine Learning (1st. ed.). Addison-Wesley Longman Publishing Co., Inc., USA.
- https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3
- https://www.mathworks.com/help/gads/what-is-the-genetic-algorithm.html
- (كشف المسار للروبوت) https://github.com/Yaaximus/genetic-algorithm-path-planning
