التطور النحوي
التطور النحوي (GE) هو حساب تطوري ، وبشكل أكثر تحديدًا، تقنية (أو نهج) برمجة وراثية (GP) طورها كونور ريان وجيه جيه كولينز ومايكل أونيل في عام 1998 [1] في مجموعة BDS في جامعة ليمريك .
كما هو الحال في أي نهج GP آخر، فإن الهدف هو العثور على برنامج قابل للتنفيذ أو جزء من البرنامج أو وظيفة، والتي ستحقق قيمة لياقة جيدة لوظيفة هدف معينة . في معظم الأعمال المنشورة حول GP، يتم التلاعب مباشرة بتعبير هيكلي شجري على غرار LISP ، بينما يطبق GE عوامل وراثية على سلسلة عدد صحيح، ثم يتم تعيينها لاحقًا إلى برنامج (أو ما شابه) من خلال استخدام قواعد نحوية، والتي يتم التعبير عنها عادةً في شكل Backus–Naur . إحدى فوائد GE هي أن هذا التعيين يبسط تطبيق البحث على لغات البرمجة المختلفة والهياكل الأخرى.
تم معالجة المشكلة
في البرمجة الجينية التقليدية الخالية من الأنواع على غرار Koza ، يجب أن تلبي مجموعة الوظائف شرط الإغلاق: يجب أن تكون جميع الوظائف قادرة على قبول مخرجات جميع الوظائف الأخرى في مجموعة الوظائف كحجج لها. عادةً، يتم تنفيذ ذلك من خلال التعامل مع نوع بيانات واحد مثل الفاصلة العائمة ذات الدقة المزدوجة. في حين تدعم أطر البرمجة الجينية الحديثة الكتابة، فإن أنظمة الأنواع هذه لها قيود لا تعاني منها Grammatical Evolution.
حل GE
تقدم GE حلاً لتقييد النوع الواحد من خلال تطوير الحلول وفقًا لقواعد نحوية محددة من قبل المستخدم (عادةً قواعد نحوية في شكل Backus-Naur ). وبالتالي، يمكن تقييد مساحة البحث، ويمكن دمج المعرفة بالمجال للمشكلة. يأتي الإلهام لهذا النهج من الرغبة في فصل "النمط الجيني" عن "النمط الظاهري": في GP، تكون الكائنات التي تعمل عليها خوارزمية البحث وما تفسره وظيفة تقييم اللياقة البدنية هي نفس الشيء. على النقيض من ذلك، فإن "الأنماط الجينية" في GE عبارة عن قوائم مرتبة من الأعداد الصحيحة التي تشفر قواعد اختيار من القواعد النحوية الخالية من السياق المقدمة. ومع ذلك، فإن النمط الظاهري هو نفسه الموجود في GP على غرار Koza: هيكل يشبه الشجرة يتم تقييمه بشكل متكرر. هذا النموذج يتماشى أكثر مع كيفية عمل علم الوراثة في الطبيعة، حيث يوجد فصل بين النمط الجيني للكائن الحي والتعبير النهائي عن النمط الظاهري في البروتينات، إلخ.
إن فصل النمط الجيني عن النمط الظاهري يسمح باتباع نهج معياري. وعلى وجه الخصوص، لا يلزم تنفيذ جزء البحث من نموذج GE بواسطة أي خوارزمية أو طريقة معينة. لاحظ أن الكائنات التي يجري GE البحث عليها هي نفسها المستخدمة في الخوارزميات الجينية . وهذا يعني، من حيث المبدأ، أنه يمكن استخدام أي حزمة خوارزمية جينية موجودة، مثل GAlib الشهير، لإجراء البحث، ولا يحتاج المطور الذي ينفذ نظام GE إلا إلى القلق بشأن تنفيذ التعيين من قائمة الأعداد الصحيحة إلى شجرة البرنامج. ومن الممكن أيضًا من حيث المبدأ إجراء البحث باستخدام بعض الطرق الأخرى، مثل تحسين سرب الجسيمات (انظر الملاحظة أدناه)؛ تخلق الطبيعة المعيارية لـ GE العديد من الفرص للهجينات كما تملي المشكلة التي يجب حلها.
لقد نجح برابازون وأونيل في تطبيق GE للتنبؤ بإفلاس الشركات، والتنبؤ بمؤشرات الأسهم، وتصنيفات الائتمان للسندات ، والتطبيقات المالية الأخرى. [ بحاجة لمصدر ] كما تم استخدام GE مع نموذج المفترس والفريسة الكلاسيكي لاستكشاف تأثير المعلمات مثل كفاءة المفترس، وعدد المنافذ، والطفرات العشوائية على الاستقرار البيئي . [2]
من الممكن إنشاء قواعد GE تكون مكافئة للبرمجة الجينية لمجموعة وظيفية/طرفية معينة.
نقد
على الرغم من نجاحاتها، كانت GE موضوعًا لبعض الانتقادات. إحدى المشكلات هي أنه نتيجة لعملية رسم الخرائط الخاصة بها، لا تحقق مشغلات GE الوراثية محلية عالية [3] [4] وهي خاصية تحظى بتقدير كبير لمشغلي الجينات في الخوارزميات التطورية. [3]
المتغيرات
على الرغم من أن GE تم وصفه في الأصل من حيث استخدام خوارزمية تطورية، وبشكل خاص خوارزمية وراثية، إلا أن هناك متغيرات أخرى موجودة. على سبيل المثال، قام باحثو GE بتجربة استخدام تحسين سرب الجسيمات لإجراء البحث بدلاً من الخوارزميات الوراثية بنتائج مماثلة لتلك الخاصة بـ GE العادي؛ يشار إلى هذا باسم "السرب النحوي"؛ باستخدام نموذج PSO الأساسي فقط، وجد أن PSO ربما تكون قادرة على تنفيذ عملية البحث في GE بنفس قدرة الخوارزميات الوراثية البسيطة. (على الرغم من أن PSO عادةً ما تكون نموذج بحث فاصلة عائمة، إلا أنه يمكن تقسيمها، على سبيل المثال، عن طريق تقريب كل متجه إلى أقرب عدد صحيح، للاستخدام مع GE.)
هناك اختلاف محتمل آخر تم تجريبه في الأدبيات وهو محاولة ترميز المعلومات الدلالية في القواعد النحوية من أجل زيادة تحيز عملية البحث. وقد أظهرت أعمال أخرى أنه باستخدام القواعد النحوية المتحيزة التي تستفيد من المعرفة بالمجال، يمكن استخدام البحث العشوائي لدفع GE. [5]
أعمال ذات صلة
كان الخوارزمية الجينية في الأصل عبارة عن مزيج من التمثيل الخطي كما تستخدمه الخوارزمية الجينية لتطوير البرمجيات (GADS) [ بحاجة لمصدر ] وقواعد صيغة باكوس ناور، والتي تم استخدامها في الأصل في الخوارزمية الجينية القائمة على الشجرة بواسطة وونغ وليونغ [6] في عام 1995 وويجهام في عام 1996. [7] كان العمل الآخر ذو الصلة المذكور في ورقة الخوارزمية الجينية الأصلية هو عمل فريدريك جروو، [8] الذي استخدم نهجًا "جنينيًا" مشابهًا مفاهيميًا، بالإضافة إلى عمل كيلر وبانزهاف، [9] والذي استخدم بشكل مماثل الجينومات الخطية.
التنفيذات
هناك العديد من التطبيقات لـ GE. وهي تشمل ما يلي.
| اسم المشروع | لغة | سنة | موقع |
| العنب | بايثون | 2022 | https://github.com/bdsul/grape |
| مختبر جيلاب | ماتلاب | 2018 | https://github.com/adilraja/GELAB |
| بوني جي إي 2 | بايثون | 2017 | https://arxiv.org/abs/1703.08535 |
| جرام إيفول | ر | 2016 | https://cran.r-project.org/web/packages/gramEvol/vignettes/ge-intro.pdf |
| باينورجين | بايثون | 2012 | http://pyneurgen.sourceforge.net/ |
| التطور النحوي | روبي | 2011 | http://www.cleveralgorithms.com/nature-inspired/evolution/grammatical_evolution.rb |
| عمر | ج، لوا | 2011 | http://nohejl.name/age/pdf/AGE-Documentation-1.0.2.pdf |
| بوني جي إي | بايثون | 2010 | https://code.google.com/archive/p/ponyge/downloads |
| جيريت | روبي | 2010 | https://github.com/bver/GERET/ |
| جيفا | جافا | 2008 | http://ncra.ucd.ie/Site/GEVA.html |
| محكمة العدل الأوروبية | جافا | 2008 | https://cs.gmu.edu/~eclab/projects/ecj/ |
| جين | سي++ | 2007 | https://ritchielab.org/research/past-research/52-grammatical-evolution-neural-networks |
| مكتبة جي إي | C++، S-Lang، tinycc | 2004 | http://bds.ul.ie/libGE/ |
انظر أيضا
- البرمجة الجينية
- التطور النحوي في لغة جافا
- البرمجة الوراثية الديكارتية
- برمجة التعبير الجيني
- البرمجة الوراثية الخطية
- برمجة متعددة التعبيرات
ملحوظات
- ^ "التطور النحوي: برامج متطورة للغة عشوائية".
- ^ ألفونسيكا، مانويل؛ سولير جيل، فرانسيسكو خوسيه (2 يناير 2015). "تطوير نظام بيئي مفترس-فريسة للتعبيرات الرياضية مع التطور النحوي". التعقيد . 20 (3): 66-83. Bibcode :2015Cmplx..20c..66A. doi :10.1002/cplx.21507. hdl : 10486/663611 .
- ^ ab Rothlauf, Franz; Oetzel, Marie (2006). "On the Locality of Grammatical Evolution". Genetic Programming . Lecture Notes in Computer Science. المجلد 3905. ص 320-330. doi :10.1007/11729976_29. ISBN 978-3-540-33143-8.
- ^ "النشر: التأثير الموضعي للتبادل والطفرة في التطور النحوي - كلية الحوسبة - جامعة كنت".
- ^ أوسوليفان، جون؛ ريان، كونور (2002)، فوستر، جيمس أ.؛ لوتون، إيفلين؛ ميلر، جوليان؛ ريان، كونور (المحررون)، "تحقيق في استخدام استراتيجيات البحث المختلفة مع التطور النحوي"، البرمجة الجينية ، المجلد 2278، برلين، هايدلبرغ: سبرينغر برلين هايدلبرغ، ص 268-277، doi :10.1007/3-540-45984-7_26، ISBN 978-3-540-43378-1تم الاسترجاع بتاريخ 2022-08-08
- ^ وونغ، مان ليونج؛ ليونج، كوونج ساك (نوفمبر 1995). "تطبيق قواعد المنطق لتحريض الوظائف الفرعية في البرمجة الجينية". وقائع مؤتمر معهد مهندسي الكهرباء والإلكترونيات الدولي لعام 1995 حول الحوسبة التطورية . المجلد 2. ص 737-740 المجلد 2. doi :10.1109/ICEC.1995.487477. ISBN 0-7803-2759-4. S2CID 16071918.
- ^ Whigham, P. (1996). "التحيز في البحث والتحيز اللغوي والبرمجة الجينية". S2CID 16631215.
{{cite web}}: مفقود أو فارغ|url=( مساعدة ) - ^ جرواو، فريديريك (1994)، تركيب الشبكة العصبية باستخدام الترميز الخلوي والخوارزمية الوراثية ، CiteSeerX 10.1.1.29.5939
- ^ كيلير، روبرت إي. (1996). "البرمجة الجينية باستخدام الطفرة والتكاثر ورسم الخرائط الجينية والنمط الظاهري من الجينومات الثنائية الخطية إلى النمط الظاهري الخطي لـ Lalr(1) فئة الورقة: البرمجة الجينية". S2CID 18095204.
{{cite web}}: مفقود أو فارغ|url=( مساعدة )
موارد
- دروس التطور النحوي.
- التطور النحوي في جافا محفوظ في 2010-03-11 على موقع واي باك مشين .
- jGE - التطور النحوي في جافا.
- مجموعة الحوسبة الحيوية وأنظمة التطوير (BDS) في جامعة ليمريك.
- صفحة التطور النحوي لمايكل أونيل، بما في ذلك قائمة المراجع.
- DRP، البرمجة الموجهة بلغة Ruby، هو نظام تجريبي مصمم للسماح للمستخدمين بإنشاء أنظمة GE/GP هجينة. يتم تنفيذه بلغة Ruby الخالصة.
- GERET، مجموعة أدوات استكشاف التطور النحوي في لغة Ruby.
- gramEvol، التطور النحوي لـ R.
