الرئيسيةعريقبحث

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

خوارزمية تستعمل بعض الآليات المستوحاة من التطور البيولوجي

☰ جدول المحتويات

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

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

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

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

الدورة

بشكل عام تتكون الخوارزمية التطورية من نقطة بداية ومن حلقة تتكرر حتى تتحقق الدقة المُحددة مُسبقا.[1]

  1. تهيئة الدائرة (تحديد نقطة أو نقاط البداية): الجيل الأول يتم اختياره عادةً بِشكل عشوائي
  2. التطور: يأخذ كل عنصر للحل خلال مرحلة التطور قيمة جودة معينة وفق مقاربته للحل الأفضل
  3. المرور بالخطوات التالية حتى يتحقق شرط التوقف:
    1. الانتقاء: اختيار أفراد الجيل للتحديث
    2. إعادة التركيب: تحديث أفراد الجيل بناء على الأفراد المُختارين
    3. التغير: تغيير عشوائي للجيل اللاحق
    4. التقييم: من جديد يأخذ كل عنصر قيمة جودة مُحدثة بناء على النقاط السابقة
    5. اختيار الجيل الجديد

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

المكونات

دالة راستريجن وهي دالة مُحدبة غير خطية وتُظهِرُ الكثير من القِيم القُصوى الموضعية، ما يُعتبَرُ عامِلاً سلبياً لإعادة التركيب (تخليق توافقات جينية جديدة).

الخوارزميات التطورية تختلف فيما بينها بشكل أساسي في العرض التطوري وفي اقتران المطابقة (fitness function) وفي المكونات التطورية: الطفرة (التغيير) وإعادة التركيب (Recombination) والإنتقاء.

الطفرة وإعادة التركيب تُعتبر مكونات للبحث في الخوارزميات التطورية والتي يتم عبرها تحديد نِطاق البحث. تطبيقها على عناصر الحل يمكن أن يضمن تحسيناً لنتيجة الخوارزمية[2]. يمكن عبر مكون الطفرة (Mutation Operator) ضم مجال جديد لدائرة البحث وعبر إعادة التركيب تأخذ النتيجة منحاً بشكل مُخطط (schemata). يعتمد نجاح البحث على استخدام المكونين كلاهما.[3]

تنفيذ العمليات البيولوجية

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

في اختيار، آباء للجيل القادم يتم اختيارهم مع وجود تحيز نحو ملائمة أعلى. استنساخ الآباء يتم من خلال النسخ مع إعادة التركيب و/أو من خلال الطفرات. إعادة التركيب تطبق على الأبوين المختارين (المرشحين) والنتائج في واحد أو اثنين من الأطفال (المرشحين الجدد). [الطفرة] تطبق على مرشح واحد والنتائج في مرشحا جديدا هذه العوامل تخلق السلالة (مجموعة من المرشحين الجدد) هؤلاء المرشحين الجدد يتنافسون مع المرشحين القدامة لمكانهم في الجيل القادم (البقاء للأفضل).

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

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

تقنيات مماثلة تختلف في تفاصيل تنفيذها وطبيعة تطبيق المشكلة المعينة.

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

التقنيات ذات الصلة

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

معرض صور

  • Two-population EA search (2).gif
  • Estimation of Distribution Algorithm animation.gif
  • Two-population EA search (3).gif
  • Two population EA animation.gif

قائمة المراجع

  • Ashlock, D. (2006), Evolutionary Computation for Modeling and Optimization, Springer, .
  • Bäck, T. (1996), Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms, Oxford Univ. Press.
  • Bäck, T., Fogel, D., Michalewicz, Z. (1997), Handbook of Evolutionary Computation, Oxford Univ. Press.
  • Eiben, A.E., Smith, J.E. (2003), Introduction to Evolutionary Computing, Springer.
  • Holland, J. H. (1975), Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor
  • Poli, R., Langdon, W. B., McPhee, N. F. (2008). A Field Guide to Genetic Programming. Lulu.com, freely available from the internet. .
  • Ingo Rechenberg (1971): Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis). Reprinted by Fromman-Holzboog (1973).
  • Hans-Paul Schwefel (1974): Numerische Optimierung von Computer-Modellen (PhD thesis). Reprinted by Birkhäuser (1977).
  • Michalewicz Z., Fogel D.B. (2004). How To Solve It: Modern Heuristics, Springer.

مقالات ذات صلة

مراجع

  1. Karsten Weicker: Evolutionäre Algorithmen. S. 25.
  2. Mitsuo Gen, Runwei Cheng: Genetic Algorithms and Engineering Optimization. S. 8.
  3. William M. Spears:The Role of Mutation and Recombination in Evolutionary Algorithms. S. 225f.

وصلات خارجية

تطبيقات

موسوعات ذات صلة :