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

الخوارزمية الوراثية (بالإنجليزية: Genetic Algorithms)‏ هي طريقة من طرق الاستمثال والبحث. يمكن تصنيف هذه الطريقة كإحدى طرق الخوارزميات التطورية التي تعتمد على تقليد عمل الطبيعة من منظور دارويني.

تستعمل الخوارزمية الوراثية تقنية بحث لإيجاد حلولِ مضبوطة أَو تقريبية تحقق الأمثلية. الخوارزميات الوراثية تصنف على أنها من طرق البحث الشامل الاستدلالي (بالإنجليزية: Global search heuristics)‏. وهي أيضا فئة معينة من الخوارزميات التطورية المعروفة كذلك بالحساب التطوري (بالإنجليزية: evolutionary computation)‏ التي تستخدم تكنولوجيا مستوحاة من البيولوجيا التطورية مثل التوريث والطفرات والاختيار والتهجين (crossover).

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

المنهج

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

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

توجد الخوارزميات الجينية في التطبيقات المعلوماتية الإحيائية (bioinformatics) وعلوم الحاسوب والهندسة والاقتصاد والكيمياء والصناعات التحويلية (manufacturing) والرياضيات والفيزياء وغيرها من الميادين.

خطوات الخوارزمية الجينية

التهيئة (initialization)

في البداية العديد من الحلول الفردية تُوَلَد عشوائيا على شكل أولي للكورموسومات. يعتمد حجم الكورموسومات على طبيعة المشكلة، ولكن عادة ما يوجد عدة مئات أو آلاف من الحلول الممكنة. بشكل تقليدي يتم توليد الكورموسومات بشكل عشوائي، حيث تغطي مجموعة كاملة من الحلول الممكنة فضاء البحث (search spaces)وفي بعض الأحيان، فإن هذا الحل قد يكون «المصنف» في حالة الوصول إلى الحل الأمثل (optimal solution).

الاختيار

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

الاستنساخ

هي عملية لتوليد جيل ثان من الكورموسومات التي تم انتقاؤها من خلال عملية الاختيار ومن ثم عمل عميلة التهجين (crossover) والطفرة (mutation)لإنتاج الأبناء.

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

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

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

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

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

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

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

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

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

الطفرة

هي عملية تغير مفاجأة في الأبناء الناتجة من عملية التهجين بحيث تكون تغير في شكل الكروموسوم عن طريق تغير أحد مكونات الكروموسوم (تغير bit) هذه العملية ليست ناتجة من الآباء.

عملية الاستنساخ في النهاية تؤدي إلى إنتاج الكورموسومات جديدة فيتم تطبيق عليها الدالة الأمثلية لإنتاج أبناء جدد.

الإنهاء

عملية إيجاد جيل جديد تستمر حتى يحدث أحد أسباب الإنها ءو هي:

1. الوصول إلى الحل الأفضل.
2. الوصول إلى العدد من الأجيال المطلوب.
3. الوصول إلى قيمة معينة (budget) مثل حساب (الزمن/المال).
4. الوصل إلى قيمة صغرى محلياً (local minimum) وعدم المقدرة على الخروج منها.
5. التخمين.
6. باستخدام مجموعة من الأسباب السابقة.

الشيفرة التضليلية (Pseudo-code) للخوارزمية

1. اختيار مجموعة البيانات الكورموسومات (Population).
2. حساب الدالة الأمثلية لكل كروموسوم.
3. إعادة
   1. اختيار أفضل آباء لعملية إنتاج الأبناء.
   2. توليد جيل جديد باستخدام التهجين والطفرة.
   3. تقيم للابن الجديد بالاعتماد على الدالة الأمثلية.
   4. عمل تغير للكروموسومات الأصلية بالاعتماد على قيم الأبناء.
4. أكمل حتى الانتهاء

الإشكال

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

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

مصطلحات الخوارزميات الجينية

رغم أن تطبيق هذه الطريقة عادة يتلخص في عملية استمثال فإنها لها مصطلحاتها الخاصة نظرا لأصولها الراجعة أو المرتبطة بنظرية التطور. من أهم هذه المصطلحات:

• الاصطفاء (selection): وهي عملية اصطفاء الكروموزومات أي الأفراد أي الحلول التي ستشارك في عملية التكاثر أي التي سيتم عليها لاحقا عملية مزج أجزائها مع أجزاء حلول أخرى أو تغير جزء من أجزاء هذا الحل
• الفرد أو الكروموزوم: هي الحلول المتاحة والتي يتم معالجتها
• الجين: هو أصغر جزء من الفرد وأصغر جزء حامل للمعلومة. حيث يتم عادة تشفير متغيرات الدالة التي تخضع للاستمثال لتكون في الشكل الثنائي (صفر وواحد). البت يسمى جين
• السكان (population): هي مجموع الحلول المتاحة
• دالة الكفاءة (fitness function): هي الدالة التي تعطي نتيجتها احتمال دخول فرد ما في الاصطفاء وتوريث خاصياته. حيث أن الحلول الأمثل تعطى حظا أكبر للدخول في عملية التكاثر وتوريث الخاصيات أو التغيير.
• دالة التشفير: هي طريقة تشفير الحل أي متغيرات عملية الاستمثال (تشفير ثنائي مثلا لمتغير ينتمي للأعداد الحقيقية)
• دالة فك التشفير: دالة فك التشفير هي الدالة العكسية لدالة التشفير التي نحتاجها لقرائة الحل النهائي الذي تعطيه الخوارزمية الجينية
• تلاقح (crossover): عملية يتم خلالها تبادل أجزاء حلول (قيمة متغيرات) بين الأفراد أو الصبغيات أو الكروموزومات التي تم اصطفائها سابقا للدخول في هذه العملية
• الطفرات (mutation): عملية تغير على صبغية معينة أي طفرة أو تغير يطرؤ على إحدى متغيراته

طريقة العمل

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

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

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

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

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

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

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

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

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

المقالة الرئيسة: مسألة البائع المتجول

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

مسألة الثماني ملكات

المقالة الرئيسة: مسألة الثماني ملكات

تتوزع الملكات بشكل عشوائي حيث تمثل مجموعة الملكات بمجموعة أرقام {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%

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

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

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

انظر أيضا

• الأدلة العليا
• الذكاء الاصطناعي القابل للتفسير