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

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

بداية سأعرض بعض المثطلحات الهامة في الخوارزميات الجينية:

population:

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

Chromosome:

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

Generations:

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

Selection:

آلية اختيار كرموزومات من الجيل الحالي للتعديل عليهم وتحسينهم ونقلهم للجيل التالي وهنالك العدد من الآليات التي سنستعرضها لاحقاً.

FitnessFunction:

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

CrossOver:

عملية التصالب هي أحد العمليات التي نستخدمها من أجل التعديل على كرموزومين تم اختيارهم بأحد الطرق السابقة وهنالك عدد من آليات التصالب والتي سمراها فيما بعد.

Mutation:

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

Termination:

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