استراتيجية التطور

📅 آخر تحديث: ٢٩ يوليو ٢٠٢٦
✍️ نُشر في: ٢٩ يوليو ٢٠٢٦
📷 يحتوي على 20 صور
الموسوعة الحرة

استراتيجية التطور (ES) من علوم الحاسوب هي فئة فرعية من الخوارزميات التطورية ، وتُستخدم كتقنية تحسين . [ 1 ] وهي تستخدم العمليات الجينية الرئيسية: الطفرة ، وإعادة التركيب ، واختيار الآباء . [ 2 ]

تاريخ

تم ابتكار تقنية التحسين "استراتيجية التطور" في أوائل الستينيات، وتم تطويرها بشكل أكبر في السبعينيات وما بعدها من قبل إنجو ريشنبرغ وهانز بول شفيل وزملائهم. [ 1 ]

الجدول الزمني للخوارزميات المختارة في ES [ 1 ]
سنةوصفمرجع
1973تم إدخال ES عن طريق الطفرة والاختيار[ 3 ]
1994خوارزمية التكيف الذاتي غير العشوائية - يتم استخدام مخطط غير عشوائي للتحكم في حجم الخطوة التغييرية[ 4 ]
1994CSA-ES - معلومات الاستخدام من الأجيال القديمة[ 5 ]
2001CMA-ES[ 6 ]
2006خوارزمية إعادة التركيب المتعددة الموزونة - استخدام إعادة التركيب الموزونة[ 7 ]
2007Meta-ES - التجميع التدريجي للهياكل الدلالية الجزئية[ 8 ]
2008استخدام التدرج الطبيعي[ 9 ]
2010ES الطبيعي الأسي - نسخة أبسط من ES الطبيعي[ 10 ]
2014CMA-ES ذو الذاكرة المحدودة - تقليل تعقيد الوقت والذاكرة عن طريق تحليل مصفوفة التغاير[ 11 ]
2016وراثة اللياقة CMA-ES - خفض التكلفة الحسابية لتقييم اللياقة باستخدام وراثة اللياقة[ 12 ]
2017RS-CMSA ES - استخدام المجموعات الفرعية[ 13 ]
2017لا يتم استخدام MA-ES - تحديث COV والجذر التربيعي لمصفوفة COV[ 14 ]
2018ES الموزون - إعادة تركيب موزونة للدوال التربيعية المحدبة العامة[ 15 ]

طُرق

طُوِّرت استراتيجيات التطور لتحسين العمليات العددية ، ولذا فهي تعتمد على متجه من متغيرات القرار المستمرة . [ 16 ] بالنسبة للقيم المنفصلة ، ​​يمكن استخدام طرق تقريب مناسبة أو طفرات مُعدَّلة بشكل ملائم للأعداد الصحيحة. [ 17 ] ونتيجةً لذلك، في العديد من تطبيقات استراتيجيات التطور، تكون مساحة المشكلة ومساحة البحث متطابقتين. لا يمكن تحقيق هذا التمثيل المباشر ، على سبيل المثال، في العديد من التطبيقات التوافقية مثل الجدولة ، حيث تُستخدم متغيرات مُعدَّلة بشكل ملائم من استراتيجيات التطور. [ 18 ] وكما هو الحال في الخوارزميات التطورية ، تُطبَّق العمليات في حلقة تكرارية. تُسمى كل دورة من هذه الحلقة جيلاً. ويستمر تسلسل الأجيال حتى يتم استيفاء معيار الإنهاء.

تتميز تسلسلات التطور الجيني (ES) بقدرتها على التكيف الذاتي لأحجام خطوات الطفرات والتطور المشترك المرتبط بها. يُعرض تسلسل التطور الجيني بإيجاز باستخدام الصيغة القياسية، [ 19 ] [ 20 ] [ 21 ] مع الإشارة إلى وجود العديد من المتغيرات. [ 18 ] [ 22 ] [ 23 ] [ 24 ] يحتوي الكروموسوم ذو القيم الحقيقية، بالإضافة إلىن{\displaystyle n}متغيرات القرار،ن′{\displaystyle n'}أحجام خطوات الطفرةσج{\displaystyle {\sigma }_{j}}، أين:1≤ج≤ن′≤ن{\displaystyle 1\leq j\leq n'\leq n}غالبًا ما تُستخدم خطوة طفرة واحدة لجميع متغيرات القرار، أو لكل متغير خطوة خاصة به. اختيار التزاوج لإنتاجλ{\displaystyle \lambda }يكون النسل عشوائيًا، أي مستقلًا عن اللياقة. أولًا، يتم توليد أحجام خطوات الطفرة الجديدة لكل عملية تزاوج عن طريق إعادة التركيب الوسيط للوالدينσج{\displaystyle {\sigma }_{j}}مع حدوث طفرة لاحقة على النحو التالي:

σج′=σج⋅هـ(شمال(0،1)-شمالج(0،1)){\displaystyle {\sigma }'_{j}=\sigma _{j}\cdot e^{({\mathcal {N}}(0,1)-{\mathcal {N}}_{j}(0,1))}}

أينشمال(0،1){\displaystyle {\mathcal {N}}(0,1)}هو متغير عشوائي ذو توزيع طبيعي بمتوسط0{\displaystyle 0}والانحراف المعياري1{\displaystyle 1}.شمال(0،1){\displaystyle {\mathcal {N}}(0,1)}ينطبق على الجميعσج′{\displaystyle {\sigma }'_{j}}، بينماشمالج(0،1){\displaystyle {\mathcal {N}}_{j}(0,1)}يتم تحديدها حديثًا لكلσج′{\displaystyle {\sigma }'_{j}}بعد ذلك، يتم إجراء إعادة تركيب منفصلة لمتغيرات القرار، تليها عملية طفرة باستخدام أحجام خطوات الطفرة الجديدة كانحرافات معيارية للتوزيع الطبيعي. متغيرات القرار الجديدةxج′{\displaystyle x_{j}'}يتم حسابها على النحو التالي:

xج′=xج+شمالج(0،σج′){\displaystyle x_{j}'=x_{j}+{\mathcal {N}}_{j}(0,{\sigma}_{j}')}

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

المتغيرات

يعرف نظام ES نوعين من أفضل طرق الاختيار لتكوين الجيل التالي من الآباء (μ{\displaystyle \mu }- عدد الآباء والأمهات،λ{\displaystyle \lambda }- عدد النسل): [ 2 ]

  • (μ،λ){\displaystyle (\mu ,\lambda )}: الμ{\displaystyle \mu }يتم استخدام أفضل النسل للجيل التالي (عادةً)μ=λ2{\displaystyle \mu ={\frac {\lambda }{2}}}).
  • (μ+λ){\displaystyle (\mu +\lambda )}يتم اختيار الأفضل من بين مجموعة منμ{\displaystyle \mu }الآباء والأمهاتλ{\displaystyle \lambda }النسل.

يوصي باك وشويفل بقيمةλ{\displaystyle \lambda }ينبغي أن يكون حوالي سبعة أضعافμ{\displaystyle \mu }[ 20 ] حيث​μ{\displaystyle \mu }يجب عدم اختيارها صغيرة جدًا نظرًا لضغط الاختيار القوي. القيم المناسبة لـμ{\displaystyle \mu }تعتمد هذه العوامل على التطبيق، ويجب تحديدها تجريبياً. يُعد اختيار الجيل التالي في استراتيجيات التطور حتمياً، ويستند فقط إلى تصنيفات اللياقة، وليس إلى قيم اللياقة الفعلية. وبالتالي، فإن الخوارزمية الناتجة ثابتة بالنسبة للتحويلات الرتيبة لدالة الهدف.

أبسط وأقدم استراتيجية تطورية [ 1 ](1+1){\displaystyle {\mathit {(1+1)}}}تُطبَّق هذه الطريقة على مجموعة سكانية ثنائية: الحالة الحالية (الأصل) ونتيجة طفرتها. فقط إذا كانت كفاءة الطفرة لا تقل عن كفاءة الحالة الأصلية، تصبح الطفرة أصلًا للجيل التالي. وإلا، تُهمل الطفرة. وبشكل عام،λ{\displaystyle \lambda }يمكن توليد الطفرات والتنافس مع الأصل، ويسمى ذلك(1+λ){\displaystyle (1+\lambda )}. في(1،λ){\displaystyle (1,\lambda )}يصبح أفضل طفرة هو الأصل للجيل التالي، بينما يُتجاهل الأصل الحالي دائمًا. بالنسبة لبعض هذه المتغيرات، تم اشتقاق براهين على التقارب الخطي ( بالمعنى العشوائي ) على دوال الهدف أحادية النمط. [ 25 ] [ 26 ]

تُضبط أحجام الخطوات الفردية لكل إحداثية، أو الارتباطات بين الإحداثيات، والتي تُحدد أساسًا بواسطة مصفوفة التغاير الأساسية، عمليًا إما عن طريق التكيف الذاتي أو عن طريق تكييف مصفوفة التغاير ( CMA-ES ). [ 23 ] عندما تُسحب خطوة الطفرة من توزيع طبيعي متعدد المتغيرات باستخدام مصفوفة تغاير متطورة ، يُفترض أن هذه المصفوفة المُكيَّفة تُقارب معكوس مصفوفة هيسيان لمشهد البحث. وقد ثبتت صحة هذه الفرضية لنموذج ثابت يعتمد على تقريب تربيعي. [ 27 ] في عام 2025، اقترح تشن وآخرون [ 28 ] استراتيجية تطور متعددة العوامل للتحسين الموزع القائم على التوافق، حيث صُممت طريقة جديدة لتكييف الخطوة لمساعدة عدة عوامل على التحكم في حجم الخطوة بشكل تعاوني.

انظر أيضاً

مراجع

  1. سلوويك ، آدم؛ كواسنيكا ، هالينا ( 1 أغسطس 2020). "الخوارزميات التطورية وتطبيقاتها في المشكلات الهندسية" . الحوسبة العصبية وتطبيقاتها . 32 (16): 12363-12379 . doi : 10.1007/s00521-020-04832-8 . ISSN 1433-3058 . 
  2. الراشدي ، زيد؛ سياف زاده ، محمد (1 يونيو 2019). "خوارزمية استراتيجية التطور (μ+λ) في تحديد موقع الآبار، والمسار، والتحكم، والتحسين المشترك" . مجلة علوم وهندسة البترول . 177 : 1042-1058 . Bibcode : 2019JPSE..177.1042A . doi : 10.1016/j.petrol.2019.02.047 . ISSN 0920-4105 . 
  3. ^ تنفيس ، دبليو (يناير 1975). "Rechenberg، Ingo، Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. 170 S. mit 36 ​​Abb. Frommann-Holzboog-Verlag. Stuttgart 1973. Broschiert". مرجع فيديس . 86 (5): 337. دوى : 10.1002/fedr.19750860506 .
  4. ↑ أوسترماير، أندرياس؛ غاولتشيك، أندرياس؛ هانسن، نيكولاس (ديسمبر 1994). "نهج غير عشوائي للتكيف الذاتي لاستراتيجيات التطور". الحوسبة التطورية . 2 (4): 369-380 . doi : 10.1162/evco.1994.2.4.369 .
  5. ↑ أوسترماير، أندرياس؛ غاولتشيك، أندرياس؛ هانسن، نيكولاس (1994). "تكييف حجم الخطوة بناءً على الاستخدام غير المحلي لمعلومات الاختيار" . حل المشكلات المتوازية من الطبيعة - PPSN III . سلسلة محاضرات في علوم الحاسوب. المجلد 866. سبرينغر. الصفحات 189-198 . doi : 10.1007/3-540-58484-6_263 . ISBN   978-3-540-58484-1.
  6. ↑ هانسن، نيكولاس؛ أوسترماير، أندرياس (يونيو 2001). "التكيف الذاتي غير العشوائي تمامًا في استراتيجيات التطور". الحوسبة التطورية . 9 (2): 159-195 . doi : 10.1162/106365601750190398 . PMID 11382355 . 
  7. ↑ أرنولد، ديرك ف. (28 أغسطس 2006). "استراتيجيات التطور الموزون لإعادة التركيب المتعدد" . علوم الحاسوب النظرية . 361 (1): 18-37 . doi : 10.1016/j.tcs.2006.04.003 . ISSN 0304-3975 . 
  8. ↑ جونغ، جيسون جيه؛ جو، جيون سيك؛ يو، سيونغ وون (2007). "استراتيجية التطور الفائق للزحف المُركّز على الويب الدلالي" . الشبكات العصبية الاصطناعية - مؤتمر ICANN 2007. سلسلة محاضرات في علوم الحاسوب. المجلد 4669. سبرينغر. الصفحات 399-407 . doi : 10.1007/978-3-540-74695-9_41 . ISBN   978-3-540-74693-5.
  9. ^ ويرسترا، دان؛ شول، توم؛ جلاسماكرز، توبياس؛ صن، يي؛ بيترز، يناير؛ شميدهوبر ، يورغن (2014-01-01). "استراتيجيات التطور الطبيعي" . جي ماخ. يتعلم. الدقة . 15 (1): 949-980 . ISSN 1532-4435 . 
  10. ↑ غلاسماخرز، توبياس؛ شاول، توم؛ يي، صن؛ ويرسترا، دان؛ شميدهوبر، يورغن (7 يوليو 2010). "استراتيجيات التطور الطبيعي الأسي" . وقائع المؤتمر السنوي الثاني عشر حول الحوسبة الجينية والتطورية (ملف PDF) . رابطة آلات الحوسبة. الصفحات 393-400 . doi : 10.1145/1830483.1830557 . ISBN  978-1-4503-0072-8.
  11. ↑ لوشيلوف، إيليا (12 يوليو 2014). "خوارزمية CMA-ES ذات ذاكرة محدودة وفعالة حسابيًا لتحسين الأداء على نطاق واسع". وقائع المؤتمر السنوي لعام 2014 حول الحوسبة الجينية والتطورية . رابطة آلات الحوسبة. الصفحات 397-404 . arXiv : 1404.5520 . doi : 10.1145 /2576768.2598294 . ISBN  978-1-4503-2662-9.
  12. ↑ لياو، رونغ-تزو؛ تينغ، تشوان-كانغ (يوليو 2016). "تحسين استراتيجية تطور التكيف مع مصفوفة التغاير من خلال وراثة اللياقة". مؤتمر IEEE للحوسبة التطورية 2016 (CEC) . الصفحات 1956-1963 . doi : 10.1109/CEC.2016.7744027 . ISBN  978-1-5090-0623-6.
  13. ↑ أحراري، علي؛ ديب، كاليانموي؛ برويس، مايك (سبتمبر 2017). "التحسين متعدد الأنماط باستخدام استراتيجية التطور التكيفي الذاتي لمصفوفة التغاير مع مجموعات فرعية طاردة". الحوسبة التطورية . 25 (3): 439-471 . doi : 10.1162/evco_a_00182 . hdl : 1887/76707 . PMID 27070282 . 
  14. ↑ باير، هانز-جورج؛ سيندهوف، برنارد (أكتوبر 2017). "تبسيط استراتيجية تطور التكيف مع مصفوفة التغاير". معاملات IEEE في الحوسبة التطورية . 21 (5): 746-759 . Bibcode : 2017ITEC...21..746B . doi : 10.1109/TEVC.2017.2680320 .
  15. ↑ أكيموتو، يوهي؛ أوجيه، آن؛ هانسن، نيكولاس (6 سبتمبر 2020). "تحليل تحسين الجودة لاستراتيجية التطور بالتركيب الموزون على الدوال التربيعية المحدبة العامة" . علوم الحاسوب النظرية . 832 : 42-67 . arXiv : 1608.04813 . doi : 10.1016/j.tcs.2018.05.015 . ISSN 0304-3975 . 
  16. ↑ شفيل، هانز-بول (1995). "استراتيجيات التطور للتحسين العددي". التطور والبحث عن الأمثلية . سلسلة تكنولوجيا الحاسوب من الجيل السادس. نيويورك: وايلي. ص 105-151 . ISBN  978-0-471-57148-3.
  17. ↑ شفيل، هانز-بول (1995). التطور والبحث عن الأمثلية . سلسلة تكنولوجيا الحاسوب من الجيل السادس. نيويورك: وايلي. ص 108، 247. ISBN  978-0-471-57148-3.
  18. 1 2 كويلو، ف.ن؛ كويلو، إ.م؛ سوزا، م.ج.ف؛ أوليفيرا، ت.أ؛ كوتا، ل.ب؛ حداد، م.ن؛ ملادينوفيتش، ن؛ سيلفا، ر.س.ب؛ غيمارايس، ف.ج (2016). "استراتيجيات تطورية هجينة ذاتية التكيف موجهة بهياكل الجوار لمسائل التحسين التوافقي" . الحوسبة التطورية . 24 (4): 637-666 . doi : 10.1162/EVCO_a_00187 . ISSN 1063-6560 . PMID 27258842 .  
  19. ↑ شفيل، هانز-بول (1995). التطور والبحث عن الأمثلية . سلسلة تكنولوجيا الحاسوب من الجيل السادس. نيويورك: وايلي. ISBN 978-0-471-57148-3.
  20. 1 2 باك، توماس؛ شفيل، هانز-بول (1993). "نظرة عامة على الخوارزميات التطورية لتحسين المعلمات" . الحوسبة التطورية . 1 (1): 1-23 . doi : 10.1162/evco.1993.1.1.1 . ISSN 1063-6560 . 
  21. ↑ شفيل، هانز-بول؛ رودولف، غونتر؛ باك، توماس (1995)، "استراتيجيات التطور المعاصرة"، في موران، فريدريكو؛ مورينو، ألفارو؛ ميريلو، جيه جيه؛ تشاكون، بابلو (محررون)، وقائع المؤتمر الأوروبي الثالث حول التطورات في الحياة الاصطناعية ، برلين، هايدلبرغ: سبرينغر، ص 893-907 ، doi : 10.1007/3-540-59496-5_351 ، ISBN  978-3-540-59496-3
  22. ↑ باك، توماس؛ هوفميستر، فرانك؛ شفيل، هانز-بول (1991)، "مسح لاستراتيجيات التطور"، في بيليو، ريتشارد ك.؛ بوكر، لاشون ب. (محرران)، وقائع المؤتمر الدولي الرابع حول الخوارزميات الجينية (ICGA) ، سان ماتيو، كاليفورنيا: مورغان كوفمان، ISBN 978-1-55860-208-3
  23. 1 2 هانسن، نيكولاس؛ أوسترماير، أندرياس (2001). "التكيف الذاتي غير العشوائي تمامًا في استراتيجيات التطور" . الحساب التطوري . 9 (2): 159– 195. دوى : 10.1162 / 106365601750190398 . ردمك 1063-6560 . بميد 11382355 .  
  24. ↑ هانسن، نيكولاس؛ كيرن، ستيفان (2004)، "تقييم استراتيجية تطور CMA على دوال اختبار متعددة الأنماط"، في ياو، شين؛ بيرك، إدموند ك.؛ لوزانو، خوسيه أ.؛ سميث، جيم (محررون)، حل المشكلات المتوازية من الطبيعة - PPSN VIII ، المجلد 3242، برلين، هايدلبرغ: سبرينغر، الصفحات 282-291 ، Bibcode : 2004LNCS.3242..282H ، doi : 10.1007/978-3-540-30217-9_29 ، ISBN   978-3-540-23092-2
  25. ↑ أوجيه، آن (أبريل 2005). "نتائج التقارب لخوارزمية (1، λ)-SA-ES باستخدام نظرية سلاسل ماركوف غير القابلة للاختزال ϕ". علوم الحاسوب النظرية . 334 ( 1-3 ): 35-69 . doi : 10.1016/j.tcs.2004.11.017 .
  26. ↑ ياغرسكوبر، ينس (أغسطس 2006). "كيف تُقلل خوارزمية البحث الموسع (1+1) باستخدام الطفرات المتناحية من الأشكال التربيعية الموجبة المحددة". علوم الحاسوب النظرية . 361 (1): 38-56 . doi : 10.1016/j.tcs.2006.04.004 .
  27. ↑ شير، عوفر م.؛ يهودايوف، أمير (يناير 2020). "حول علاقة التغاير-هيسيان في استراتيجيات التطور". علوم الحاسوب النظرية . 801 : 157-174 . arXiv : 1806.03674 . doi : 10.1016/j.tcs.2019.09.002 .
  28. ↑ تشين، تاي يو؛ تشين، وي نينغ؛ هاو، جين كاو؛ وانغ، يانغ؛ تشانغ، جون (2025). "استراتيجية تطور متعددة العوامل مع تكيف الخطوات التعاوني والتراكمي لتحسين التوزيع ذي الصندوق الأسود". معاملات IEEE في الحوسبة التطورية . 29 (6): 2819-2833 . Bibcode : 2025ITEC...29.2819C . doi : 10.1109/TEVC.2025.3525713 . ISSN 1941-0026 . 

فهرس

  • إنجو ريشينبرج (1971): استراتيجية التطور – نظام تحسين التقنية نحو مبادئ التطور البيولوجي (أطروحة دكتوراه). أعيد طبعه بواسطة فرومان-هولزبوغ (1973). رقم ISBN 3-7728-1642-8
  • هانز بول شويفيل (1974): Numerische Optimierung von Computer-Modellen (أطروحة دكتوراه). أعيد طبعه بواسطة بيركهاوزر (1977).
  • هانز-بول شفيل : التطور والبحث عن الأمثلية . نيويورك: وايلي وأولاده، 1995. ISBN 0-471-57148-2
  • هـ. ج. باير وهـ. ب. شفيل. استراتيجيات التطور: مقدمة شاملة . مجلة الحوسبة الطبيعية، 1(1):3 – 52، 2002.
  • هانز-جورج باير: نظرية استراتيجيات التطور . سبرينغر، 27 أبريل 2001. ISBN 3-540-67297-4
  • إنجو ريشينبيرج: استراتيجية التطور '94 . شتوتغارت: فروممان هولزبوغ 1994. ISBN 3-7728-1642-8
  • ج. كلوكجيثر وهـ. ب. شفيل (1970). تجارب الفوهات ثنائية الطور ونفثات النواة المجوفة . معهد أبحاث AEG. مجموعة مشروع MDH Staustrahlrohr. برلين، جمهورية ألمانيا الاتحادية. وقائع الندوة الحادية عشرة حول الجوانب الهندسية للديناميكا المغناطيسية المائية، معهد كاليفورنيا للتكنولوجيا، باسادينا، كاليفورنيا، 24-26 مارس 1970 .
  • إم. إميريش، أو إم شير، وإتش. وانغ: استراتيجيات التطور . في: دليل الاستدلال، 1-31. دار نشر سبرينغر الدولية (2018).

مركز الأبحاث