ألية عمل الخوارزمية الجينية
ألية عمل الخوارزمية الجينية
م. عبد الستار اسماعيل وداعه
الصفحة الرسمية الالكترونية للكاتب
الخوارزمية الجينية هي طريقة من طرق الاستمثال والبحث. يمكن تصنيف هذه الطريقة كإحدى طرق الخوارزميات التطورية التي تعتمد على تقليد عمل الطبيعة من منظور دارويني.الخوارزمية الوراثية: هي تقنية بحث تستعمل لإيجاد حلولِ مضبوطة أَو تقريبية التي تحقيقِ الأمثلية، الخوارزميات الوراثية تصنف كبحوث العالمية الاستدلالي وهي أيضا فئة معينة من الخوارزميات التطورية المعروفة كذلك بِالحساب التطوريِ والتي تستخدم التكنولوجيا المستوحاة من البيولوجيا التطورية مثل التوريث والطفرات والاختيار والتهجين. تعتبر الخوارزميات الجينية من التقنيات الهامة في البحث عن الخيار الأمثل من مجموعة حلول متوفرة لتصميم معين، وتعتمد مبدأ داروين في الاصطفاء حيث تقوم هذه المعالجة الوراثية بتمرير المزايا المثلى من خلال عمليات التوالد المتعاقبة، وتدعيم هذه الصفات، وتكون لهذه الصفات القدرة الأكبر على دخول عملية التوالد، وإنتاج ذرية أمثل وبتكرار الدورة الوراثية تتحسن نوعية الذرية تدريجياً.
Methodology
1- الخوارزميات الجينية يتم تنفيذها باعتبارها محاكاة الكمبيوتر حيث تستخدم الكورموسومات كأفراد في العمليات التي تقوم بها لإيجاد افصل الحلول، بشكل عام الحلول تمثل بنظام الثنائي من 0 و1 ،وأيضا يمكن استخدام رموز أخرى.
2- عملية التطورتبدأ عادة من اختيار الكورموسومات بشكل عشوائي وهذا يحدث في الأجيال الأخرى في كل جيل يتم حساب الدالة الأمثلية لكل الكروسومات بشكل منفرد ويتم اختيار أفضل الكورموسومات بالاعتماد على أفضل الدالة الأمثلية ومن ثم عمل تهجين (دمج) وأيضا عمل طفرة، هذه الخوارزمية تتوقف عندما نصل إلى أكبر عدد من الأجيال تم إنتاجه أو الوصل إلى أفضل تحيق من خلال الدالة الأمثلية، إذا كان التوقف بسبب أكبر عدد من الأجيال يكون الحل الأمثل غير متحقق.
3-الخوارزميات الجينية توجد في التطبيقات المعلوماتية الأحيائية وعلوم الحاسوب والهندسة والاقتصاد والكيمياء والصناعات التحويلية والرياضيات والفيزياء وغيرها من الميادين.
خطوات الخوارزمية الجينية
أولاً- التهيئــة: في البداية العديد من الحلول الفردية هي مولده عشوائيا على شكل أولي للكورموسومات. حجم الكورموسومات يعتمد على طبيعة المشكلة، ولكن عادة ما يوجد عدة مئات أو آلاف من الحلول الممكنة. بشكل تقليدي يتم تتولد الكورموسومات بشكل عشوائي ،بحيث تغطي مجموعة كاملة من الحلول الممكنة البحث الفضائي وفي بعض الأحيان، فإن هذا الحل قد تكون "المصنف" في حالة الوصول إلى الحل المثل.
ثانيـــاً- الاختيار : خلال كل الأجيال المتعاقبة، هنالك نسبة من الكورموسومات الحالية هي المختارة لإنتاج جيل جديد. ويتم اختيار هذه الكورموسومات الاعتماد على الدالة الأمثلية، حيث تكون نسبة الاختيار على أفضلية الدالة الأمثلية ،وهنالك طريقة أخرى عن طريق اختيار مجموعة عشوائية من الكورموسومات، لكن هذه العملية قد تستغرق وقتا طويلا جدا.
ثـالثــاً- الاستنساخ: هي عملية لتوليد جيل ثان من الكورموسومات التي تم انتقاؤها من خلال عملية الاختيار ومن ثم عمل عميلة التهجين والطفرة لإنتاج الأبناء.
عملية التهجين :- من خلال الآباء الذين تم اختيارهم من عملية الاختيار يتم تزاوج بين كل اثنين من الآباء لإنتاج طفلين جديدين وهذه العملية تستمر حتى يتم إيجاد مجوعة جديدة من الكورموسومات بالإضافة إلى مجموعة الآباء.
توجد العديد من التقنيات التي تَستعمل في عملية التهجين:
1- نقطة تهجين واحدة: هذه العملية في نهاية المطاف تنتج الجيل القادم من السكان الكورموسومات التي تختلف عن الجيل الأول، جميع البيانات تترتب بالاعتماد على هذه النقطة حيث يحدث عملية تبدل للبيانات بشرط عدم حدوث تكرار.
2- نقطتين تهجين: هذه العملية في نهاية المطاف تنتج الجيل القادم من السكان الكورموسومات التي تختلف عن الجيل الأول، جميع البيانات تترتب بالاعتماد على هذه النقطتين حيث يحدث عملية تبدل للبيانات بشرط عدم حدوث تكرار.
3- القطع والوصل: حيث هذه العملية تعمل على قطع البيانات من منطقة تختلف عن منطقة الكروموسوم الثاني مما يودي إلى اختلاف في طول الكروموسوم.
الطفرة : - هي عملية تغير مفاجأة في الأبناء الناتجة من عملية التهجين بحيث تكون تغير في شكل الكروموسوم عن طريق تغير أحد مكونات الكروموسوم تغير(bit) هذه العملية ليسن ناتجة من الآباء.
عملية الاستنساخ في النهاية تؤدي إلى إنتاج الكورموسومات جديدة فيتم تطبيق عليها الدالة الأمثلية لإنتاج أبناء جدد.
رابعـــاً- الإنهاء: عملية إيجاد جيل جديد تستمر حتى يحدث أحد أسباب الإنهاء و هي:
1- الوصول إلى الحل الأفضل.
2- الوصل إلى العدد من الأجيال المطلوب.
3- الوصول إلى قيمة معينة مثل حساب (الزمن/المال(
4- الوصل إلى وعدم المقدرة على الخروج منها.
5- التخمين.
6- باستخدام مجموعة من الأسباب السابقة.
خـامســـاً: الشيفرة التضليلية للخوارزمية.
1- اختيار مجموعة البيانات الكورموسومات.
2- حساب الدالة الأمثلية لكل كروموسوم.
3- إعادة
4- اختيار أفضل آباء لعملية إنتاج الأبناء.
5- توليد جيل جديد باستخدام التهجين والطفرة.
6- تقيم للابن الجديد بالاعتماد على الدالة الأمثلية.
7- عمل تغير للكروموسومات الأصلية بالاعتماد على قيم الأبناء.