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

الموسوعة الحرة

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

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

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

يمكن تطبيق إجراء الاختيار للتكاثر المستخدم في وقت مبكر [ 1 ] على النحو التالي:

  1. يتم تطبيع قيم اللياقة التي تم حسابها ( دالة اللياقة )، ​​بحيث يكون مجموع جميع قيم اللياقة الناتجة مساوياً لـ 1.
  2. يتم حساب قيم اللياقة المتراكمة المعيارية: قيمة اللياقة المتراكمة للفرد هي مجموع قيمة لياقته الخاصة بالإضافة إلى قيم اللياقة لجميع الأفراد السابقين؛ يجب أن تكون قيمة اللياقة المتراكمة للفرد الأخير 1، وإلا فقد حدث خطأ ما في خطوة التطبيع.
  3. يتم اختيار رقم عشوائي R بين 0 و 1.
  4. الشخص المختار هو أول شخص تكون قيمته المعيارية المتراكمة أكبر من أو تساوي R.

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

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

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

أساليب الاختيار

تختلف الطرق المذكورة بشكل رئيسي في ضغط الاختيار، [ 2 ] [ 3 ] والذي يمكن ضبطه بواسطة مُعامل استراتيجية في اختيار الترتيب الموصوف أدناه. كلما زاد ضغط الاختيار، تسارع تقارب المجموعة نحو حل معين، وقد لا يتم استكشاف فضاء البحث بشكل كافٍ. يمكن مواجهة هذا التقارب المبكر [ 4 ] من خلال هيكلة المجموعة بشكل مناسب. [ 5 ] [ 6 ] هناك ارتباط وثيق بين نموذج المجموعة المستخدم وضغط الاختيار المناسب. [ 5 ] إذا كان الضغط منخفضًا جدًا، فمن المتوقع ألا تتقارب المجموعة حتى بعد وقت حساب طويل. لمزيد من طرق الاختيار والتفاصيل، انظر [ 7 ] [ 8 ] .

اختيار عجلة الروليت

في عملية اختيار الأفراد باستخدام عجلة الروليت ، تتناسب احتمالية اختيار فردٍ ما للتكاثر في الجيل التالي طرديًا مع لياقته؛ فكلما كانت لياقته أفضل، زادت فرصة اختياره. ويمكن تمثيل عملية اختيار الأفراد بتدوير عجلة روليت تحتوي على عدد من الخانات يساوي عدد الأفراد في الجيل الحالي، وتختلف أحجام هذه الخانات تبعًا لاحتمالية اختيار كل فرد.أنا{\displaystyle i}يساويصأنا=وأناΣج=1شمالوج{\displaystyle p_{i}={\frac {f_{i}}{\Sigma _{j=1}^{N}f_{j}}}}، أينوأنا{\displaystyle f_{i}}هل اللياقة البدنيةأنا{\displaystyle i}وشمال{\displaystyle N}حجم الجيل الحالي (لاحظ أنه في هذه الطريقة يمكن رسم فرد واحد عدة مرات).

أخذ العينات العشوائي الشامل

يُعد أخذ العينات العشوائي الشامل تطوراً لاختيار عجلة الروليت مع الحد الأدنى من الانتشار وبدون تحيز.

اختيار الرتبة

في اختيار الترتيب، لا يعتمد احتمال الاختيار مباشرةً على اللياقة، بل على ترتيب لياقة الفرد ضمن المجموعة. [ 9 ] لا يلزم توفر قيم اللياقة الدقيقة نفسها، بل يكفي تصنيف الأفراد وفقًا لجودتهم.

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

اختيار الرتبة الخطية

يُستخدم الترتيب الخطي، الذي يعود إلى بيكر، [ 11 ] [ 12 ] بشكل متكرر. [ 5 ] [ 10 ] [ 13 ] وهو يسمح بتحديد ضغط الاختيار بواسطة المعاملsص{\displaystyle sp}والتي يمكن أن تأخذ قيمًا بين 1.0 (بدون ضغط انتقائي) و2.0 (ضغط انتقائي مرتفع). الاحتماليةP{\displaystyle P}لن{\displaystyle n}المراكز التصنيفيةRأنا{\displaystyle R_{i}}يتم الحصول عليها على النحو التالي:

P(Rأنا)=1ن(sص-(2sص-2)أنا-1ن-1)1≤أنا≤ن،1≤sص≤2wأناتحP(Rأنا)≥0،∑أنا=1نP(Rأنا)=1{\displaystyle P(R_{i})={\frac {1}{n}}{\Bigl (}sp-(2sp-2){\frac {i-1}{n-1}}{\Bigr )}\quad \quad 1\leq i\leq n,\quad 1\leq sp\leq 2\quad {\mathsf {with}}\quad P(R_{i})\geq 0,\quad \sum _{i=1}^{n}P(R_{i})=1}

تعريف آخر للاحتماليةP{\displaystyle P}بالنسبة للمناصبأنا{\displaystyle i}هو: [ 9 ]

P(أنا)=2*(ن-أنا+1)ن*(ن+1){\displaystyle P(i)={\frac {2*(n-i+1)}{n*(n+1)}}}

اختيار الرتبة الأسية

يتم تعريف اختيار الرتبة الأسية على النحو التالي: [ 9 ]

P(أنا)=wن-أنا∑ك=1نwن-ك،0≤w≤1{\displaystyle P(i)={\frac {w^{ni}}{\sum _{k=1}^{n}{w^{nk}}}},0\leq w\leq 1}

اختيار الحالة المستقرة

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

اختيار البطولة

يُعد اختيار المشاركين في البطولة طريقة لاختيار فرد من بين مجموعة من الأفراد. ويتم اختيار الفائز في كل بطولة للمشاركة في المرحلة الانتقالية.

تحديد الاقتطاع

في عملية اختيار القطع ، يتم فرز الأفراد وفقًا لمدى ملاءمتهم ويتم اختيار جزء (من 10٪ إلى 50٪) من أفضل الأفراد للجيل التالي. [ 9 ]

الاختيار النخبوي

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

اختيار بولتزمان

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

اختيار المعجم

تعتمد معظم خوارزميات الاختيار على اختيار الجينومات الفردية بناءً على قيم اللياقة العددية، والتي غالبًا ما تُستخلص من حالات تدريبية متعددة. في المقابل، يأخذ اختيار Lexicase في الاعتبار الأداء في كل حالة تدريبية على حدة، بدلاً من تجميع مقاييس الأداء عبر حالات متعددة. وهو يأخذ الحالات في الاعتبار بترتيبات عشوائية مختلفة، وبالتالي بأولويات مختلفة، لكل عملية اختيار. [ 15 ] [ 16 ] [ 17 ]

انظر أيضاً

مراجع

  1. ↑ هولاند، جون هـ. (1992). التكيف في الأنظمة الطبيعية والاصطناعية . أطروحة دكتوراه، جامعة ميشيغان، 1975. كامبريدج، ماساتشوستس: مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 0-585-03844-9. OCLC 42854623 . 
  2. ↑ باك، توماس (1994). "الضغط الانتقائي في الخوارزميات التطورية: توصيف لآليات الانتقاء". وقائع المؤتمر الأول لمعهد مهندسي الكهرباء والإلكترونيات حول الحوسبة التطورية. المؤتمر العالمي لمعهد مهندسي الكهرباء والإلكترونيات حول الذكاء الحسابي . أورلاندو، فلوريدا، الولايات المتحدة الأمريكية: معهد مهندسي الكهرباء والإلكترونيات. الصفحات 57-62 . doi : 10.1109/ICEC.1994.350042 . ISBN  978-0-7803-1899-1. S2CID 195867383 . 
  3. ↑ غولدبيرغ، ديفيد إي.؛ ديب، كاليانموي (1991)، "تحليل مقارن لأساليب الاختيار المستخدمة في الخوارزميات الجينية"، أسس الخوارزميات الجينية ، المجلد 1، إلسيفير، الصفحات 69-93 ، CiteSeerX 10.1.1.101.9494 ، doi : 10.1016/b978-0-08-050684-5.50008-2 ، ISBN    978-0-08-050684-5، S2CID 938257 ، تم الاسترجاع بتاريخ 2023-01-09 
  4. ↑ ليونغ، يي؛ غاو، يونغ؛ شو، زونغ-بن (سبتمبر 1997). "درجة تنوع السكان - منظور حول التقارب المبكر في الخوارزميات الجينية وتحليل سلسلة ماركوف الخاصة بها". معاملات IEEE في الشبكات العصبية . 8 (5): 1165-1176 . doi : 10.1109/72.623217 . ISSN 1045-9227 . PMID 18255718 .  
  5. 1 2 3 جورجيس-شلويتر، مارتينا (1990). الخوارزميات الجينية وهياكل السكان - خوارزمية متوازية ضخمة (أطروحة دكتوراه). دورتموند، ألمانيا: جامعة دورتموند، كلية علوم الحاسوب.
  6. ↑ ألبا، إنريكي؛ دورونسورو، برنابي (2008). الخوارزميات الجينية الخلوية . سلسلة واجهات بحوث العمليات/علوم الحاسوب. نيويورك: سبرينغر. ISBN 978-0-387-77610-1.
  7. ↑ إيبن، أ. إي.؛ سميث، ج. إي. (2015). "اللياقة، والاختيار، وإدارة السكان". مقدمة في الحوسبة التطورية . سلسلة الحوسبة الطبيعية. برلين، هايدلبرغ: سبرينغر. ص 79-98 . doi : 10.1007/978-3-662-44874-8 . ISBN  978-3-662-44873-1. S2CID 20912932 . 
  8. ↑ دي يونغ، كينيث أ. (2006). الحوسبة التطورية : منهج موحد . كامبريدج، ماساتشوستس: مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN  978-0-262-25598-1. OCLC 69652176 . 
  9. 1 2 3 4 جانود، إسماعيل؛ جرادات، يوسف؛ مسعود، محمد ز.؛ مناصرة، أحمد؛ علياء، محمد (22 ديسمبر 2021). "دور عوامل اختيار الخوارزمية الجينية في إطالة فترة استقرار شبكات الاستشعار اللاسلكية: دراسة مقارنة" . الإلكترونيات . 11 (1): 28. doi : 10.3390/electronics11010028 .
  10. 1 2 ويتلي، داريل (1989)، "خوارزمية جينيتور وضغط الانتقاء: لماذا يُعدّ تخصيص التجارب التناسلية بناءً على الترتيب هو الأفضل"، في شافير، جيه دي (محرر)، وقائع المؤتمر الدولي الثالث حول الخوارزميات الجينية (ICGA) ، سان فرانسيسكو، كاليفورنيا، الولايات المتحدة الأمريكية: دار مورغان كوفمان للنشر، الصفحات 116-121 ، ISBN  978-1-55860-066-9
  11. ↑ بيكر، جيمس إي. (1985)، "أساليب الاختيار التكيفي للخوارزميات الجينية"، في غريفنستيت، جون جيه. (محرر)، وقائع المؤتمر الدولي الأول حول الخوارزميات الجينية وتطبيقاتها (ICGA) ، هيلزديل، نيو جيرسي: إل. إيرلبوم أسوشيتس، ص 101-111 ، ISBN  0-8058-0426-9
  12. ↑ بيكر، جيمس إي. (1987)، "الحد من التحيز وعدم الكفاءة في خوارزمية الاختيار"، في غريفنستيت، جون جيه. (محرر)، وقائع المؤتمر الدولي الثاني حول الخوارزميات الجينية وتطبيقاتها (ICGA) ، هيلزديل، نيو جيرسي: إل. إيرلبوم أسوشيتس، ص 14-21 ، ISBN  0-8058-0158-8
  13. ^ هوفميستر، فرانك. باك، توماس (1991)، “الخوارزميات الجينية واستراتيجيات التطور: أوجه التشابه والاختلاف”، في هانز بول شويفيل؛ مانر ، رينهارد (محرران)، حل المشكلات الموازية من الطبيعة ، المجلد. 496، برلين، هايدلبرغ: Springer-Verlag، الصفحات من 455 إلى 469، دوى : 10.1007/bfb0029787 ، ISBN   978-3-540-54148-6
  14. ↑ سيفاناندام، إس إن (2013). مبادئ الحوسبة المرنة . ديبا، إس إن. نيودلهي: وايلي. ISBN 978-1-118-54680-2. OCLC 891566849 . 
  15. ↑ سبيكتور، لي (2012-07-07). "تقييم نمط المشكلة من خلال الأداء التفاضلي لاختيار المعجم في البرمجة الجينية: تقرير أولي" . وقائع المؤتمر السنوي الرابع عشر المصاحب للحوسبة الجينية والتطورية . GECCO '12. نيويورك، نيويورك، الولايات المتحدة الأمريكية: رابطة آلات الحوسبة. الصفحات 401-408 . doi : 10.1145/2330784.2330846 . ISBN  978-1-4503-1178-6.
  16. ↑ هيلموث، توماس؛ سبيكتور، لي؛ ماثيسون، جيمس (أكتوبر 2015). "حل المشكلات المعقدة باستخدام اختيار ليكسيكايس". معاملات IEEE في الحوسبة التطورية . 19 (5): 630-643 . doi : 10.1109/TEVC.2014.2362729 . ISSN 1941-0026 . 
  17. ↑ بولدي، رايان؛ بريش، مارتن؛ سوبانيا، دومينيك؛ لاليجيني، ألكسندر؛ هيلموت، توماس؛ روثلاف، فرانز؛ أوفريا، تشارلز؛ سبيكتور، لي (2024-12-02). "اختيار معجمي مُصغّر مُستنير: تحديد حالات تدريب مُنتجة لحل المشكلات بكفاءة" . الحوسبة التطورية . 32 (4): 307-337 . doi : 10.1162/evco_a_00346 . ISSN 1530-9304 . PMID 38271633 .