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

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

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

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

تم تطوير وتطبيق عدد كبير من تحورات الخوارزميات الجينية، على نطاق واسع، لحل مختلف المشاكل التحسينية. من مسألة تلوين المخطط graph coloring إلي التعرف على الأنماط pattern recognition. ومن الأنظمة غير المتصلة discrete systems مثل مشكلة البائع المتجول traveling salesman problem إلي المستمرة continuous systems مثل التصميم الفعال للأجنحة الحاملة في الهندسة الجوية airfoil efficient design. ومن الأسواق المالية إلي الأمثلة متعددة الأهداف multi-objective engineering.

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

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

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

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

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

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

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

1. يتنافس أفراد الساكنة على حقوق التزاوج أي حق الخضوع لعمليات التقاطع crossover والتطفر mutation.
2. الأفراد الأكثر ملائمة أي الأصلح fittest ينتجون الحصة الأكبر من الجيل التالي.
3. تنتقل جينات الأباء عبر الأجيال، ويبقى الأفضل، مما يصقل أفراد الساكنة جيلًا بعد جيل.
4. لا يعني الانتقال من جيل إلي جيل اندثار الآباء. فرغم أن متوسط الملائمة لكل جيل يكون أكبر من الذي سبقه، لكن يمكن أن يكون معامل ملائمة فرد أفضل من الأبناء.

معامل الملائمة

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

كل جيل جديد لديه في المتوسط ​​”جينات أفضل” أكثر من الأجيال السابقة، نظرًا لكون متوسط ​​اللياقة أعلى. وبالتالي فإن كل جيل جديد لديه “حلول جزئية” أفضل من الأجيال السابقة. وعند توقف معامل الملائمة عن الارتفاع لعدد من الأجيال المتتالية، يحدث إقرار التقارب. أي أن الساكنة الناتجة هي الأمثل والفرد الأكثر ملائمة هو الحل.

العمليات الأساسية في الخوارزميات الجينية

• عملية الانتقاء selection

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

• عملية الدمج أو التقاطع crossover

تكافئ هذه العملية مفهوم التزاوج بين أفراد الساكنة. تتمثل في اختيار فردين من الساكنة الحالية وتحديد عدد من الجينات عشوائيًا وتمريرها للخلف (الأبناء). بالطبع عدد جينات الأباء هو نفسه عدد جينات الأبناء ولكون الاختيار عشوائي لا يكون عدد الجينات من الأم أو الأب نفسه عدد الجينات من الأب أو الأم. أي التوزيع ليس 50 | 50.

• التطفر mutation

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

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

1. هذه الخوارزميات قوية.
2. قادرة على توفير حلول في فضاءات إحتمال عملاقة.
3. على خلاف خوارزميات الذكاء الاصطناعي الأخرى، لا ينتهي التنفيد بفعل التشويش أو تغير المدخلات.

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

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

مصادر

1. geeksforgeeks
2. ScienceDirect