منتديات ليلاس - الخوارزمية الجينية

:besm8dg4:

الخوارزمية الجينية genetic algorithms هي طريقة من طرق الاستمثال و البحث. يمكن تصنيف هذه الطريقة كإحدى طرق الخوارزميات التطورية evolutionary algorithms التي تعتمد على تقليد عمل الطبيعة من منظور دارويني.

الخوارزمية الوراثية: هي تقنية بحث تستعمل لإيجاد حلولِ مضبوطة أَو تقريبية التي تحقيقِ الأمثلية ، الخوارزميات الوراثية تصنف كبحوث العالمية الاستدلالي(Global search heuristics), وهي أيضا فئة معينة من الخوارزميات التطورية المعروفة كذلك بِالحساب التطوريِ (evolutionary computation) التي تستخدم تكنولوجيا المستوحاة من البيولوجيا التطورية (evolutionary biology) مثل التوريث والطفرات والاختيار و التهجين (crossover).
تعتبر الخوارزميات الجينية من التقنيات الهامة في البحث عن الخيار الأمثل من مجموعة حلول متوفرة لتصميم معين، وتعتمد مبدأ داروين في الاصطفاء حيث تقوم هذه المعالجة الوراثية بتمرير المزايا المثلى من خلال عمليات التوالد المتعاقبة، وتدعيم هذه الصفات، وتكون لهذه الصفات القدرة الأكبر على دخول عملية التوالد، وإنتاج ذرية أمثل وبتكرار الدورة الوراثية تتحسن نوعية الذرية تدريجياً.
المنهج (Methodology)
الخوارزميات الجينية يتم تنفيذها باعتبارها محاكاة الكمبيوتر حيث تستخدم الكورموسومات كأفراد في العمليات التي تقوم بها لإيجاد افصل الحلول , بشكل عام الحلول تمثل بنظام الثنائي (binary ) من 0 و1 ،وأيضا يمكن استخدام رموز أخرى.
عملية التطور(evolution) تبدأ عادة من اختيار الكورموسومات(population) بشكل عشوائي وهذا يحدث في الأجيال الأخرى ،في كل جيل يتم حساب الدالة الأمثلية(fitness function) لكل الكروسومات بشكل منفرد و يتم اختيار أفضل الكورموسومات بالاعتماد على أفضل الدالة الأمثلية و من ثم عمل تهجين (دمج) وأيضا عمل طفرة ، هذه الخوارزمية تتوقف عندما نصل إلى اكبر عدد من الأجيال تم إنتاجه أو الوصل إلى أفضل تحيق من خلال الدالة الأمثلية ، إذا كان التوقف بسبب اكبر عدد من الأجيال يكون الحل الأمثل غير متحقق.
الخوارزميات الجينية توجد في التطبيقات المعلوماتية الإحيائية(bioinformatics) و علوم الحاسوب والهندسة و الاقتصاد و الكيمياء و الصناعات التحويلية ( manufacturing) و الرياضيات والفيزياء وغيرها من الميادين.
خطوات الخوارزمية الجنية
1. التهيئة(initialization )
في البداية العديد من الحلول الفردية هي مولده عشوائيا على شكل أولي للكورموسومات. حجم الكورموسومات يعتمد على طبيعة المشكلة ، ولكن عادة ما يوجد عدة مئات أو آلاف من الحلول الممكنة. بشكل تقليدي يتم تتولد الكورموسومات بشكل عشوائي ،بحيث تغطي مجموعة كاملة من الحلول الممكنة البحث الفضائي(search spaces )وفي بعض الأحيان ، فإن هذا الحل قد تكون "المصنف" في حالة الوصول إلى الحل المثل(optimal solution) .
2.الاختيار (selection )
خلال كل الأجيال المتعاقبة،هنالك نسبة من الكورموسومات الحالية هي المختارة لإنتاج جيل جديد. ويتم اختيار هذه الكورموسومات الاعتماد على الدالة الأمثلية، حيث تكون نسبة الاختيار على أفضلية الدالة الأمثلية ,وهنالك طريقة أخرى عن طريق اختيار مجموعة عشوائية من الكورموسومات، لكن هذه العملية قد تستغرق وقتا طويلا جدا.
3. الاستنساخ
(reproduction) هي عملية لتوليد جيل ثان من الكورموسومات التي تم انتقاؤها من خلال عمليةالاختيار ومن ثم عمل عميلة التهجين (crossover) والطفرة (mutation) لإنتاج الأبناء.
عملية التهجين Crossover techniques
من خلال الآباء الذين تم اختيارهم من عملية الاختيار يتم تزاوج بين كل اثنين من الآباء لإنتاج طفلين جديدين وهذه العملية تستمر حتى يتم إيجاد مجوعة جديدة من الكورموسومات بالإضافة إلى مجموعة الآباء.
توجد العديد من التقنيات التي تَستعمل في عملية التهجين
• نقطة تهجين واحدة
• هذه العملية في نهاية المطاف تنتج الجيل القادم من السكان الكورموسومات التي تختلف عن الجيل الأول، جميع البيانات تترتب بالاعتماد على هذه النقطة حيث يحدث عملية تبدل للبيانات بشرط عدم حدوث تكرار.

http://static2.filefront.com/images/...gdmqasoyxo.jpg

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

http://static2.filefront.com/images/...altvcjkhwn.jpg

• القطع والوصل
• حيث هذه العملية تعمل على قطع البيانات من منطقة تختلف عن منطقة الكروموسوم الثاني مما يودي إلى اختلاف في طول الكروموسوم.

http://static2.filefront.com/images/...akjcfsbhxt.jpg

الطفرة Mutation
هي عملية تغير مفاجأة في الأبناء الناتجة من عملية التهجين بحيث تكون تغير في شكل الكروموسوم عن طريق تغير احد مكونات الكروموسوم (تغير bit) هذه العملية ليسن ناتجة من الآباء.
عملية الاستنساخ في النهاية تؤدي إلى إنتاج الكورموسومات جديدة فيتم تطبيق عليها الدالة الأمثلية لإنتاج أبناء جدد.
4. الإنهاء (Termination) عملية إيجاد جيل جديد تستمر حتى يحدث احد أسباب الإنهاءو هي:
1. الوصول إلى الحل الأفضل .
2. الوصل إلى العدد من الأجيال المطلوب.
3. الوصول إلى قيمة معينة(budget) مثل حساب (الزمن/المال).
4. الوصل إلى (local minimum) وعدم المقدرة على الخروج منها.
5. التخمين .
6. باستخدام مجموعة من الأسباب السابقة .
5. الشيفرة التضليلية (Pseudo-code ) للخوارزمية.
1. اختيار مجموعة البيانات الكورموسومات(Population).
2. حساب الدالة الأمثلية لكل كروموسوم.
3. إعادة
1. اختيار أفضل آباء لعملية إنتاج الأبناء.
2. توليد جيل جديد باستخدام التهجين والطفرة.
3. تقيم للابن الجديد بالاعتماد على الدالة الأمثلية.
4. عمل تغير للكروموسومات الأصلية بالاعتماد على قيم الأبناء.
4. أكمل حتى الانتهاء
الإشكال
عادة ما يتم استعمال هذه الطريقة للقيام بالبحث في فضاء بحث (مجموعة عناصر يتم البحث فيها) أو في عملية إستمثال ،أي أن الهدف هو جعل دالة رياضية معينة تتخذ قيمة علوى قصوى أو دنيا قصوى و لهذه الدالة اسم خاص في مجال الخوارزميات الجينية حيث يطلق عليها اسم دالة لأمثلية fitness function.
ولتطبيق الخوارزمية الوراثية علينا أولاً أن نوجد التمثيل المناسب للمشكلة المدروسة وفق عمليات صبغية، وأشهر طرق التمثيل هي استخدام السلاسل الثنائية لتمثيل قيم المتغيرات التي تعبر عن حلّ للمشكلة المعطاة وعلى هيئة صبغيات، وبعد أن تنتج هذه الصبغيات لا بد من طرق لمعالجتها حيث يوجد أربعة عمليات وهي (النسخ، التصالب،الطفرة و العكس).
مصطلحات الخوارزميات الجينية
رغم أن تطبيق هذه الطريقة عادة يتلخص في عملية إستمثال فإنها لها مصطلحاتها الخاصة نظرا لأصولها الراجعة أو المرتبطة بنظرية التطور. من أهم هذه المصطلحات:
• الإصطفاء: و هي عملية إصطفاء الكروموزومات أي الأفراد أي الحلول التي ستشارك في عملية التكاثر أي التي سيتم عليها لاحقا عملية مزج أجزائها مع أجزاء حلول أخرى أو تغير جزء من أجزاء هذا الحل
• الفرد أو الكروموزوم: هي الحلول المتاحة و التي يتم معالجتها
• الجين: هو أصغر جزء من الفرد و أصغر جزء حامل للمعلومة. حيث يتم عادة تشفير متغيرات الدالة التي تخضع للإستمثال لتكون في الشكل الثنائي (صفر و واحد). البت يسمى جين
• ال population هي مجموع الحلول المتاحة
• دالة الأمثلية fitness function: هي الدالة التي تعطي نتيجتها احتمال دخول فرد ما في الإصطفاء و توريث خاصياته. حيث أن الحلول الأمثل تعطى حظا أكبر للدخول في عملية التكاثر و توريث الخاصيات أو التغيير.
• دالة التشفير: هي طريقة تشفير الحل أي متغيرات عملية الإستمثال (تشفير ثنائي مثلا لمتغير ينتمي للأعداد الحقيقية)
• دالة فك التشفير: دالة فك التشفير هي الدالة العكسية لدالة التشفير التي نحتاجها لقرائة الحل النهائي الذي تعطيه الخوارزمية الجينية
• تلاقح cross over: عملية يتم خلالها تبادل أجزاء حلول (قيمة متغيرات) بين الأفراد أو الصبغيات أو الكروموزومات التي تم إصطفائها سابقا للدخول في هذه العملية
• mtutation عملية تغير على صبغية معينة أي طفرة أو تغير يطرؤ على إحدى متغيراته
طريقة العمل
تقوم طريقة الخوارزميات الجينية على توليد حلول جديدة تولد حلولا من احتمالات مشفرة على الشكل المعروف ب "كروموسوم" أَو "مورّث". الكروموسومات تجمع أو تتغير لإنتاج الأفراد الجدد. وهي مفيدة لإيجاد الحل الامثل للمعضلات المتعددة الأبعاد التي يمكن فيها أن تشفر القيم للمتغيرات المختلفة فيها على شكل الكروموسوم.
ولتطبيق الخوارزمية الوراثية علينا أولاً أن نوجد التمثيل المناسب للمشكلة المدروسة وفق عمليات صبغية، وأشهر طرق التمثيل هي استخدام السلاسل الثنائية لتمثيل قيم المتغيرات التي تعبر عن حلّ للمشكلة المعطاة وعلى هيئة صبغيات، وبعد أن تنتج هذه الصبغيات لا بد من طرق لمعالجتها حيث يوجد أربعة عمليات وهي (النسخ، التصالب،الطفرة و العكس).
فالخوارزمية الوراثية مبنية على أساس تقنية الحلول المثلى تحاكي النشوء الطبيعي وذلك عن طريق تشفير الحلول الممكنة لتمثيلها على شكل سلاسل مشابهة لسلاسل الصبغي، ومن ثم تطبيق بعض العمليات البيولوجية (نسخ، تصالب، طفرة)، والعمليات الصنعية(العكس) لإنتاج الحل الأمثل.
والميزة الأهم في الخوارزمية الوراثية هي طبيعتها التكييفية، والتي تجعلها أقل حاجة لمعرفة المعادلة من أجل حلها.
فالخوارزمات الجينية هي طريقة لمحاكاة ماتفعله الطبيعة في تكاثر الكائنات الحية، واستخدام تلك الطريقة لحل مشكلات معقدة للوصول للحل الأفضل، أو أقرب حل ممكن للحل الأفضل. إذن لدينا مشكلة لها عدد كبير جدا من من الحلول أكثرها خاطئ وبعضها صحيح، وهنالك دائما الحل الأفضل والذي يصعب غالبا الوصول إليه.
ففكرة الخوارزميات الجينية تكمن في توليد بعض الحلول للمشكلة عشوائيا، ثم تفحص هذه الحلول وتقارن ببعض المعايير التي يضعها مصمم الخوارزم، وأفضل الحلول فقط هي التي تبقى أما الحلول الأقل كفاءة فيتم إهمالها عملا بالقاعدة البيولوجية "البقاء للأصلح".
والخطوة التالية هي مزاوجة أو خلط الحلول المتبقية (الحلول الأكثر كفاءة) لإنتاج حلول جديدة على غرار ما يحصل في الكائنات الحية وذلك بمزج مورثاتها (جيناتها) بحيث يحمل الكائن الجديد صفات هي عبارة عن مزيج من صفات والديه.
الحلول الناتجة من التزاوج تدخل هي أيضا تحت الفحص والتنقيح لمعرفة مدى كفاءتها واقترابها من الحل الأمثل، فإن ثبتت كفاءة الحل الجديد فإنه يبقى وإلا يُهمل، وهكذا تتم عمليات التزاوج والانتقاء حتى تصل العملية إما لعدد معين من التكرارات (يقرره مستحدم النظام) أو تصل الحلول الناتجة، أو إحداها إلى نسبة كفاءة، أو نسبة خطأ ضئيلة (يحددها المستخدم أيضا) أو حتى الحل الأفضل.

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

منقول