خوارزميات وراثية

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

الخوارزمية الجينية 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)لإنتاج الأبناء.

عملية التهجين

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

توجد العديد من التقنيات التي تَستعمل في عملية التهجين:

  • نقطة تهجين واحدة

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

  • نقطتين تهجين

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

  • القطع والوصل

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

الطفرة هي عملية تغير مفاجأة في الأبناء الناتجة من عملية التهجين بحيث تكون تغير في شكل الكروموسوم عن طريق تغير أحد مكونات الكروموسوم (تغير 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: هي الدالة التي تعطي نتيجتها احتمال دخول فرد ما في الاصطفاء وتوريث خاصياته. حيث أن الحلول الأمثل تعطى حظا أكبر للدخول في عملية التكاثر وتوريث الخاصيات أو التغيير.
  • دالة التشفير: هي طريقة تشفير الحل أي متغيرات عملية الاستمثال (تشفير ثنائي مثلا لمتغير ينتمي للأعداد الحقيقية)
  • دالة فك التشفير: دالة فك التشفير هي الدالة العكسية لدالة التشفير التي نحتاجها لقرائة الحل النهائي الذي تعطيه الخوارزمية الجينية
  • تلاقح crossover: عملية يتم خلالها تبادل أجزاء حلول (قيمة متغيرات) بين الأفراد أو الصبغيات أو الكروموزومات التي تم اصطفائها سابقا للدخول في هذه العملية
  • mutation عملية تغير على صبغية معينة أي طفرة أو تغير يطرؤ على إحدى متغيراته

طريقة العمل[عدل]

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

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

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

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

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

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

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

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

مسألة البائع المتجول[عدل]

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

(Pseudo-code) مسألة البائع المتجول

مسألة 8-ملكات (8 queens problem)[عدل]

تتوزع الملكات بشكل عشوائي حيث تمثل مجموعة الملكات بمجموعة أرقام {1،2،3،4،5،6،7،8} حيث يعبر العنصر الأول عن موقع أول ملكه في أول عمود، العنصر الثاني يعبر عن موقع العنصر الثاني في العمود الثاني...... وهكذا. المطلوب توزيع الملكات بحيث لا تتواجد ملكتين في نفس الصف أو العمود أو القطر الصورة التالية تظهر المطلوب.

طريقة العمل: تقم الخوارزمية الوراثية باختيار أفضل الكورموسومات باستخدام الدالة الأمثلية من مجموعة الكورموسومات الأولية الدالة الأمثلية : تكون أعلى درجة (max) =28 (7+6+5+4+3+2+1) اقل درجة =0 حيث 7 تعني أن 8 ملوك في نفس السطر (من اليسار ال اليمن) وهكذا.

فإذا كانت الكورموسومات الأولية هكذا :

الدالة الأمثلية=28-4 =24

الدالة الأمثلية=28-5 =23

الدالة الأمثلية=28-8 =20

الدالة الأمثلية=28-17 =11

اختير أعلى دالة الأمثلية

24/(24+23+20+11) = 31%

23/(24+23+20+11) = 29%

20/(24+23+20+11) = 26%

11/(24+23+20+11) = 11%

يتم اخيار أعلى درجتين من الدالة الأمثلية ومن ثم عمل التهجين والطفرة

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

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