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

الخوارزمية التطورية الخلوية ( cEA ) هي نوع من الخوارزميات التطورية (EA) التي لا يمكن للأفراد فيها التزاوج بشكل عشوائي، ولكن كل فرد يتفاعل مع جيرانه الأقرب الذين يتم تطبيق خوارزمية تطورية أساسية عليهم (الاختيار، والتنوع، والاستبدال).

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

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

عادةً ما تكون الشبكة ثنائية الأبعاد ذات بنية حلقية، مع إمكانية زيادة أو تقليل عدد الأبعاد بسهولة (إلى بُعد واحد، أي حلقة). تُحدد جوار نقطة معينة في الشبكة (حيث يُوضع فرد) بناءً على مسافة مانهاتن بينها وبين باقي أفراد المجموعة. لكل نقطة في الشبكة جوار يتداخل مع جوارات الأفراد المجاورين. في الخوارزمية الأساسية، تكون جميع الجوارات متساوية في الحجم والشكل. أكثر الجوارات استخدامًا هما L5، المعروف أيضًا باسم جوار فون نيومان أو جوار NEWS (الشمال، الشرق، الغرب، الجنوب)، وC9، المعروف أيضًا باسم جوار مور. هنا، يرمز L إلى "خطي" بينما يرمز C إلى "مضغوط".

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

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

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

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

يمكن اعتبار خوارزمية التطور الخلوي (cEA) بمثابة آلة خلوية (CA) ذات قواعد إعادة كتابة احتمالية، حيث يُعادل أبجدية الآلة الخلوية عدد الحلول المحتملة للمسألة. وبالتالي، يمكن تطبيق المعرفة المستقاة من أبحاث الآلات الخلوية على خوارزميات التطور الخلوي.

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

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

انظر هنا للحصول على وصف كامل للأساسيات اللازمة لفهم وتصميم وتطبيق أنظمة التقييم البيئي.

• الأوتوماتون الخلوي
• التطور ثنائي الطور
• إنريكي ألبا
• الخوارزمية التطورية
• الميتاهيروستيك
• الاستدلال الميتاهوريستي المتوازي

• إي. ألبا، ب. دورونسورو، الخوارزميات الجينية الخلوية ، سبرينغر-فيرلاغ، ISBN 978-0-387-77609-52008
• AJ Neighbor, JJ Durillo, F. Luna, B. Dorronsoro, E. Alba, MOCell: خوارزمية جينية خلوية جديدة لتحسين الأهداف المتعددة، المجلة الدولية للأنظمة الذكية، 24: 726-746، 2009
• إي. ألبا، بي. دورونسورو، إف. لونا، إيه جيه نيبر، بي. بوفري، إل. هوجي، خوارزمية جينية متعددة الأهداف للخلايا لاستراتيجية البث الأمثل في شبكات MANET الحضرية ، اتصالات الحاسوب، 30(4):685-697، 2007
• إي. ألبا، بي. دورونسورو، حساب تسعة حلول جديدة هي الأفضل حتى الآن لمسألة توجيه المركبات ذات السعة المحدودة باستخدام خوارزمية جينية خلوية ، رسائل معالجة المعلومات، إلسيفير، 98(6):225-230، 30 يونيو 2006
• إم. جياكوبيني، إم. توماسيني، إيه. تيتامانزي، إي. ألبا، شدة الاختيار في الخوارزميات التطورية الخلوية للشبكات المنتظمة ، معاملات IEEE في الحوسبة التطورية، مطبعة IEEE، 9(5):489-505، 2005
• إي. ألبا، بي. دورونسورو، المفاضلة بين الاستكشاف والاستغلال في الخوارزميات الجينية الخلوية الديناميكية ، معاملات IEEE في الحوسبة التطورية، مطبعة IEEE، 9(2)126-142، 2005

• الموقع الإلكتروني الخاص بالخوارزميات التطورية الخلوية
• مجموعة أبحاث NEO في جامعة مالقة، إسبانيا. مؤرشفة بتاريخ 28 سبتمبر 2018 على موقع Wayback Machine.