الحوسبة التطورية

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

الحوسبة التطورية (EC) في علوم الحاسوب هي مجموعة من الخوارزميات لتحسين الحلول الشاملة، مستوحاة من التطور البيولوجي ، وهي فرع من فروع الذكاء الحسابي والحوسبة المرنة يدرس هذه الخوارزميات. [ 1 ] [ 2 ] [ 3 ] وبعبارة أخرى، هي مجموعة من خوارزميات حل المشكلات القائمة على التجربة والخطأ والمبنية على السكان، وتتميز بطابع التحسين الاستدلالي أو العشوائي .

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

تُتيح تقنيات الحوسبة التطورية إمكانية إنتاج حلول مُحسّنة للغاية في نطاق واسع من المشكلات، مما يجعلها شائعة في علوم الحاسوب . وتوجد العديد من المتغيرات والامتدادات المُناسبة لأنواع مُحددة من المشكلات وهياكل البيانات. كما تُستخدم الحوسبة التطورية أحيانًا في علم الأحياء التطوري كإجراء تجريبي حاسوبي لدراسة الجوانب المشتركة للعمليات التطورية العامة.

تاريخ

يعود مفهوم محاكاة العمليات التطورية لحل المشكلات إلى ما قبل ظهور الحواسيب، كما في حالة آلان تورينج الذي اقترح طريقة البحث الجيني عام 1948. [ 4 ] تشبه آلات تورينج من النوع B الشبكات العصبية البدائية ، حيث كانت الروابط بين الخلايا العصبية تُتعلّم عبر نوع من الخوارزمية الجينية . أما آلاته من النوع P، فتشبه طريقة التعلم المعزز ، حيث توجه إشارات المتعة والألم الآلة لتعلم سلوكيات معينة. مع ذلك، لم تُنشر ورقة تورينج البحثية حتى عام 1968، وتوفي عام 1954، لذا لم يكن لهذا العمل المبكر تأثير يُذكر على مجال الحوسبة التطورية الذي تطور لاحقًا. [ 5 ]

بدأ مجال الحوسبة التطورية بشكل جدي في خمسينيات وستينيات القرن العشرين. [ 4 ] وشهدت تلك الفترة عدة محاولات مستقلة لاستخدام عملية التطور في الحوسبة، والتي تطورت بشكل منفصل لمدة 15 عامًا تقريبًا. وظهرت ثلاثة فروع في مجالات مختلفة لتحقيق هذا الهدف: استراتيجيات التطور ، والبرمجة التطورية ، والخوارزميات الجينية . ثم ظهر فرع رابع، هو البرمجة الجينية ، في أوائل تسعينيات القرن العشرين. وتختلف هذه المناهج في طريقة الاختيار، والطفرات المسموح بها، وتمثيل البيانات الجينية. وبحلول تسعينيات القرن العشرين، بدأت الفروق بين الفروع التاريخية تتلاشى، وصِيغ مصطلح "الحوسبة التطورية" عام 1991 للدلالة على مجال يشمل جميع النماذج الأربعة. [ 6 ]

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

في عام 1964، قدّم إنجو ريشنبرغ وهانز -بول شفيل نموذج استراتيجيات التطور في ألمانيا. [ 6 ] ولأن تقنيات التدرج الهبوطي التقليدية تُنتج نتائج قد تتعثر في الحد الأدنى المحلي، اقترح ريشنبرغ وشفيل استخدام الطفرات العشوائية (المطبقة على جميع معلمات متجه الحل) للخروج من هذه الحدود الدنيا. يتم توليد الحلول الفرعية من الحلول الأصلية، ويُحتفظ بالحل الأكثر نجاحًا للأجيال اللاحقة. استُخدمت هذه التقنية لأول مرة من قِبلهما لحل مسائل التحسين في ديناميكا الموائع بنجاح . [ 7 ] في البداية، طُبقت تقنية التحسين هذه دون استخدام الحواسيب، بالاعتماد على النرد لتحديد الطفرات العشوائية. وبحلول عام 1965، أصبحت الحسابات تُجرى بالكامل بواسطة الحاسوب. [ 6 ]

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

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

لعبت شخصيات أخرى عديدة دورًا في تاريخ الحوسبة التطورية، على الرغم من أن أعمالهم لم تندرج دائمًا ضمن أحد الفروع التاريخية الرئيسية لهذا المجال. أجرى نيلز آل باريسيلي أولى عمليات المحاكاة الحاسوبية للتطور باستخدام الخوارزميات التطورية وتقنيات الحياة الاصطناعية عام 1953، ونُشرت النتائج الأولى عام 1954. [ 9 ] وكان أليكس فريزر رائدًا آخر في خمسينيات القرن العشرين ، حيث نشر سلسلة من الأبحاث حول محاكاة الانتقاء الاصطناعي . [ 10 ] ومع تزايد الاهتمام الأكاديمي، أتاحت الزيادة الهائلة في قدرة الحواسيب تطبيقات عملية، بما في ذلك التطور التلقائي لبرامج الحاسوب. [ 11 ] تُستخدم الخوارزميات التطورية الآن لحل المشكلات متعددة الأبعاد بكفاءة أعلى من البرامج التي يُنتجها المصممون البشريون، وكذلك لتحسين تصميم الأنظمة. [ 12 ] [ 13 ]

التقنيات

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

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

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

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

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

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

الخوارزميات التطورية وعلم الأحياء

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

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

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

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

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

تم تقديم الأوتوماتا التطورية [ 19 ] [ 20 ] [ 21 ] ، وهي تعميم لآلات تورينج التطورية [ 22 ] [ 23 ] ، بهدف دراسة خصائص الحوسبة البيولوجية والتطورية بدقة أكبر. وتتيح هذه الأوتوماتا، على وجه الخصوص، الحصول على نتائج جديدة حول قدرة التعبير في الحوسبة التطورية [ 21 ] [ 24 ] . ويؤكد هذا النتيجة الأولية المتعلقة بعدم قابلية الحسم في التطور الطبيعي والخوارزميات والعمليات التطورية. ويمكن للأوتوماتا التطورية المحدودة ، وهي أبسط فئة فرعية من الأوتوماتا التطورية التي تعمل في الوضع النهائي، قبول لغات عشوائية على أبجدية معينة، بما في ذلك اللغات غير القابلة للتعداد التكراري (مثل لغة القطرية) واللغات القابلة للتعداد التكراري ولكن غير التكرارية (مثل لغة آلة تورينج العالمية) [ 25 ] .

ممارسون بارزون

تتسم قائمة الباحثين النشطين بطبيعتها بالديناميكية وعدم الشمولية. وقد نُشر تحليل شبكي للمجتمع في عام 2007. [ 26 ]

المنشورات

المجلات

على الرغم من أن المقالات التي تتناول الحوسبة التطورية أو تستخدمها منتشرة في الأدبيات العلمية، إلا أن العديد من المجلات مخصصة للحوسبة التطورية:

المؤتمرات

تشمل المؤتمرات الرئيسية في مجال الحوسبة التطورية ما يلي:

انظر أيضاً

مراجع

  1. ↑ دي يونغ، كينيث أ. (2006). الحوسبة التطورية: منهج موحد . كامبريدج، ماساتشوستس: مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 978-0-262-52960-0.
  2. ^ كروس ، رودولف. مستغيم، سناز؛ بورجيلت، كريستيان؛ براون، كريستيان؛ شتاينبريشر، ماتياس (2022). “الذكاء الحسابي”. الذكاء الحسابي: مقدمة منهجية . نصوص في علوم الكمبيوتر ( الطبعة الثالثة). شام: سبرينغر الدولية للنشر. ص 2 – 3. دوى : 10.1007 / 978-3-030-42227-1 . رقم ISBN   978-3-030-42226-4.
  3. ↑ تشاتورفيدي، ديفيندا ك. (2008)، "مقدمة في الحوسبة المرنة"، الحوسبة المرنة ، المجلد 103، برلين، هايدلبرغ: سبرينغر، الصفحات 1-10 ، doi : 10.1007/978-3-540-77481-5_1 ، ISBN   978-3-540-77480-8
  4. 1 2 إيبن، أ. إي.؛ سميث، ج. إي. (2015)، الحوسبة التطورية: الأصول ، سلسلة الحوسبة الطبيعية، برلين، هايدلبرغ: سبرينغر، ص 13-24 ، doi : 10.1007/978-3-662-44874-8_2 ، ISBN  978-3-662-44873-1
  5. ↑ بورجين، مارك؛ إيبرباخ، يوجين (12 أبريل 2013). "تورينج التطوري في سياق الآلات التطورية". arXiv : 1304.3762 [ cs.AI ].
  6. 1 2 3 4 5 فوغل، ديفيد ب.، محرر. (1998). الحوسبة التطورية : السجل الأحفوري . نيويورك: مطبعة IEEE. ISBN  0-7803-3481-7. OCLC 38270557 . 
  7. ^ فيشر، توماس (1986)، “Kybernetische Systemanalyse einer Tuchfabrik zur Einführung eines Computergestützten Dispositionssystems der Fertigung”، DGOR ، Berlin، Heidelberg: Springer، p. 120، دوى : 10.1007/978-3-642-71161-9_14 ، ISBN  978-3-642-71162-6
  8. ↑ ميتشل، ميلاني (1998). مقدمة في الخوارزميات الجينية . مطبعة معهد ماساتشوستس للتكنولوجيا. doi : 10.7551/mitpress/3927.001.0001 . ISBN 978-0-262-28001-3.
  9. ^ باريتشيلي، نيلز آل (1954). "نماذج رقمية من عمليات التطور". الطرق : 45 – 68.
  10. ↑ فريزر، أ. س. (1958). "تحليلات مونت كارلو للنماذج الوراثية". مجلة نيتشر . 181 (4603): 208-209 . Bibcode : 1958Natur.181..208F . doi : 10.1038/181208a0 . PMID: 13504138. S2CID : 4211563 .  
  11. ↑ كوزا، جون ر. (1992). البرمجة الجينية: حول برمجة الحواسيب عن طريق الانتقاء الطبيعي . مطبعة معهد ماساتشوستس للتكنولوجيا . ISBN 978-0-262-11170-6.
  12. ↑ أونوبولو، غودفري سي.؛ بابو، بي في (21 يناير 2004). تقنيات التحسين الجديدة في الهندسة . سبرينغر. ISBN 9783540201670تم الاطلاع عليه بتاريخ 17 سبتمبر 2016 .
  13. ↑ جمشيدي م (2003). "أدوات التحكم الذكي: وحدات التحكم الضبابية، والشبكات العصبية، والخوارزميات الجينية". المعاملات الفلسفية للجمعية الملكية أ . 361 (1809): 1781-1808 . Bibcode : 2003RSPTA.361.1781J . doi : 10.1098 / rsta.2003.1225 . PMID 12952685. S2CID 34259612 .  
  14. ↑ كامبيلو، فيليبي؛ أرانها، كلاوس (20 يونيو 2018). "معجم الوحوش التطورية: معجم للخوارزميات التطورية، وخوارزميات الأسراب، وغيرها من الخوارزميات القائمة على الاستعارة" . doi : 10.5281/zenodo.1293352 .
  15. ↑ كوديلا، جاكوب (12 ديسمبر 2022). "مشكلة حاسمة في تقييم وتحليل أساليب الحوسبة التطورية" . مجلة نيتشر للذكاء الآلي . 4 (12): 1238-1245 . arXiv : 2301.01984 . doi : 10.1038/s42256-022-00579-0 . ISSN 2522-5839 . S2CID 254616518 .  
  16. ↑ "المعلومات البيولوجية" . موسوعة ستانفورد للفلسفة . مختبر أبحاث الميتافيزيقا، جامعة ستانفورد. 2016.
  17. ↑ جي جي دياز أوتشوا (2018). "الآليات المرنة متعددة المقاييس: الحوسبة والتطور البيولوجي". مجلة التطور الجزيئي . 86 (1): 47-57 . Bibcode : 2018JMolE..86...47D . doi : 10.1007/ s00239-017-9823-7 . PMID 29248946. S2CID 22624633 .  
  18. ↑ أ. دانشن (2008). "البكتيريا كحواسيب تصنع حواسيب" . مجلة FEMS لعلم الأحياء الدقيقة ، 33 (1): 3-26 . doi : 10.1111/j.1574-6976.2008.00137.x . PMC 2704931. PMID 19016882 .  
  19. ↑ بورغين، مارك؛ إيبرباخ، يوجين (2013). "آلات تورينغ التطورية المولدة بشكل متكرر والأتمتة التطورية". في شين-شي يانغ (محرر). الذكاء الاصطناعي، والحوسبة التطورية، والأساليب فوق الحدسية . دراسات في الذكاء الحسابي. المجلد 427. سبرينغر-فيرلاغ. الصفحات 201-230 . doi : 10.1007/978-3-642-29694-9_9 . ISBN   978-3-642-29693-2.
  20. ↑ بورجين، م. وإيبرباخ، إ. (2010) الآلات التطورية المحدودة والدورية، في وقائع مؤتمر الحوسبة التطورية لعام 2010 (CEC'2010)، برشلونة، إسبانيا، 2010، ص 1379-1386
  21. 1 2 بورجين، م.؛ إيبرباخ، إ. (2012). "الأتمتة التطورية: التعبيرية والتقارب في الحوسبة التطورية". مجلة الكمبيوتر . 55 (9): 1023-1029 . doi : 10.1093/comjnl/bxr099 .
  22. ↑ إيبرباخ إي. (2002) حول التعبيرية في الحوسبة التطورية: هل الحوسبة التطورية خوارزمية؟، وقائع المؤتمر العالمي للحوسبة الذكية 2002، هونولولو، هاواي، 2002، 564-569.
  23. ↑ إيبرباخ، إي. (2005) نحو نظرية الحوسبة التطورية، أنظمة بيولوجية، المجلد 82، الصفحات 1-19.
  24. ↑ إيبرباخ، يوجين؛ بورجين، مارك (2009). "الأتمتة التطورية كأساس للحوسبة التطورية: كان لاري فوجل على حق". مؤتمر IEEE للحوسبة التطورية لعام 2009. IEEE. الصفحات 2149-2156 . doi : 10.1109/CEC.2009.4983207 . ISBN  978-1-4244-2958-5. S2CID 2869386 . 
  25. ↑ هوبكروفت، جيه إي، وموتاني، آر، وأولمان، جيه دي (2001) مقدمة في نظرية الأوتوماتا واللغات والحوسبة، أديسون ويسلي، بوسطن/سان فرانسيسكو/نيويورك
  26. ↑ جيه جيه ميريلو وسي. كوتا (2007). "من هو الباحث الأكثر اتصالاً في مجال الحوسبة التطورية؟ تحليل مركزية الشبكة المعقدة للمؤلفين في الحوسبة التطورية". arXiv : 0708.2021 [ cs.CY ].

فهرس