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

خوارزمية تطورية
في الذكاء الاصطناعي، الخوارزمية التطورية هي مجموعة فرعية من الحسابات التطورية. الخوارزمية التطورية تستخدم بعض الآليات المستوحاة من التطور البيولوجي: الاستنساخ، الطفرة، إعادة التركيب، والاختيار. الحلول المرشحة للمشكلة الأمثل تلعب دور الأفراد في قطاع من السكان، المهمة الملائمة تحدد البيئة التي تتم فيها «حياة» الحلول (انظر أيضا رياضيات الاستمثال) تطور السكان يأخذ مكانه بعد التطبيق المتكرر للعملية أعلاه. التطور الاصطناعي يصف العملية الفردية التي تنطوي على الخوارزميات التطورية ؛الخوارزمية التطورية هي المكونات الفردية التي تساهم في التطور الاصطناعي.
الخوارزميات التطورية غالبا ما تقوم بأداء جيد لإيجاد حلول تقريبية لجميع أنواع المشاكل لأنها من الناحية المثالية لا تجعل أي افتراض حول المهمة الملائمة الكامنة وراء المشهد، وهذا التعميم هو مبين من النجاحات التي تحققت في مجالات متنوعة مثل الهندسة،الفن،علم الاحياء الاقتصاد، التسويق،علم الوراثة، عمليات البحوث، علم الإنسان الآلي، العلوم الاجتماعية الفيزياء السياسة والكيمياء
بصرف النظر عن فائدتها كمحسن للرياضيات، الاحتساب التطوري والخوارزميات استخدمت أيضا بوصفها إطارا تجريبيا يمكن من خلاله التحقق من صحة النظريات حول التطور البيولوجي والانتقاء الطبيعي، ولا سيما من خلال العمل في ميدان [الحياة الاصطناعية]. من تقنيات الخوارزميات التطورية التي تطبق على نمذجة التطور البيولوجي تقتصر عادة على الاستكشافات من العمليات التطورية الصغرى، ولكن بعض المحاكاة باستخدام الكمبيوتر، مثل تييرا وأفيدا، حاولت وضع نموذج دينامكيات التطورية العظمى.
وجود العديد من القيود على الخوارزميات التطورية من المحتمل أنه ناتج عن عدم وجود نمط وراثي واضح - لتمييز النمط الظاهري. في الطبيعة، في خلية البويضة المخصبة يخضع لعملية معقدة معروفة بالجنيني لتصبح ناضجة بالنمط الظاهري. هذا الترميز غير المباشر نحتاجه لجعل البحث الجيني أكثر قوة (أي يقلل من احتمال حدوث طفرات قاتلة)، وأيضا قد يحسن قابلية الكائن على التطور. العمل في الآونة الأخيرة في ميدان خلق المضغة المصطنعة، أو اصطناعية نظم الانمائية، تسعى لمعالجة هذه الشواغل.
الدورة
بشكل عام تتكون الخوارزمية التطورية من نقطة بداية ومن حلقة تتكرر حتى تتحقق الدقة المُحددة مُسبقا.
تهيئة الدائرة (تحديد نقطة أو نقاط البداية): الجيل الأول يتم اختياره عادةً بِشكل عشوائي
التطور: يأخذ كل عنصر للحل خلال مرحلة التطور قيمة جودة معينة وفق مقاربته للحل الأفضل
المرور بالخطوات التالية حتى يتحقق شرط التوقف:
الانتقاء: اختيار أفراد الجيل للتحديث
إعادة التركيب: تحديث أفراد الجيل بناء على الأفراد المُختارين
التغير: تغيير عشوائي للجيل اللاحق
التقييم: من جديد يأخذ كل عنصر قيمة جودة مُحدثة بناء على النقاط السابقة
اختيار الجيل الجديد
يختلف استخدام طرق الاختيار والتركيب باختلاف نوع الخوارزمية التطورية. كثيراً ما ترتبط الخوارزميات التطورية بشبكات عصبونية اصطناعية وببحث موضعي ووفق التطبيق المستخدم يكون للخوارزمية إيجابيات وسلبيات مختلفة.
المكونات
الخوارزميات التطورية تختلف فيما بينها بشكل أساسي في العرض التطوري وفي اقتران المطابقة (fitness function) وفي المكونات التطورية: الطفرة (التغيير) وإعادة التركيب (Recombination) والإنتقاء.
الطفرة وإعادة التركيب تُعتبر مكونات للبحث في الخوارزميات التطورية والتي يتم عبرها تحديد نِطاق البحث. تطبيقها على عناصر الحل يمكن أن يضمن تحسيناً لنتيجة الخوارزمية. يمكن عبر مكون الطفرة (Mutation Operator) ضم مجال جديد لدائرة البحث وعبر إعادة التركيب تأخذ النتيجة منحاً بشكل مُخطط (schemata). يعتمد نجاح البحث على استخدام المكونين كلاهما.
تنفيذ العمليات البيولوجية
عادة الحلول المرشحة المأخوذة عن تشكيل عينة عشوائية أولية من السكان تمثل الجيل الأول المهمة الملائمة يتم تطبيقها على الحلول المرشحة وأي نتائج لاحقة يوجد فئتين من المهام الرئيسية للمهمة الملائمة: واحدة حيث المهمة الملائمة لا تتغير على نحو تحسين وظيفة ثابتة أو اختبار مع مجموعة ثابتة من حالات الاختبار الأخرى حيث المهمة الملائمة هي قابلة للتغيير كما هو الحال في استخدام تمييز التخصص أو المشاركة في تطوير المجموعة من حالات الاختبار.
في اختيار، آباء للجيل القادم يتم اختيارهم مع وجود تحيز نحو ملائمة أعلى. استنساخ الآباء يتم من خلال النسخ مع إعادة التركيب و/أو من خلال الطفرات. إعادة التركيب تطبق على الأبوين المختارين (المرشحين) والنتائج في واحد أو اثنين من الأطفال (المرشحين الجدد). [الطفرة] تطبق على مرشح واحد والنتائج في مرشحا جديدا هذه العوامل تخلق السلالة (مجموعة من المرشحين الجدد) هؤلاء المرشحين الجدد يتنافسون مع المرشحين القدامة لمكانهم في الجيل القادم (البقاء للأفضل).
ويمكن أن تتكرر هذه العملية حتى يتم العثور على مرشح مع نوعية كافية (الحل) أو أخذ أفضل حد حسابي تم الوصول إليه سابقا.
تقنيات الخوارزمية التطورية
تقنيات مماثلة تختلف في تفاصيل تنفيذها وطبيعة تطبيق المشكلة المعينة.
الخوارزميات الوراثية: هذا هو النوع الأكثر شعبية من الخوارزمية التطورية من يسعى إلى حل للمشكلة في شكل سلاسل من الأرقام (تقليدي ثنائي وعلى الرغم من أنه أفضل تمثيل عادة ما تكون تلك التي تعكس شيئا عن المشكلة التي يجري حلها) وذلك بتطبيق عمليات مثل إعادة التركيب والطفرات (واحدة أحيانا وأحيانا الاثنتين) هذا النوع من الخوارزمية التطورية كثيرا ما يستخدم في مشاكل الأمثلة:
البرمجة الجينية: هنا تكون الحلول على شكل برامج الحاسوب وتتحدد المهمة الملائمة بقدرتها على حل مشكلة حسابية.
البرمجة التطورية: مثل البرمجة الجينية إلا أن هيكل هذا البرنامج هو ثابت والعوامل العددية المتغبرة يسمح بتطويرها.
استراتيجية التطورية: يتعامل مع النواقل من الارقام الحقيقية على أنها تمثيلات من الحلول وعادة ما يستخدم معدلات التكيف الذاتي للطفرة.
التقنيات ذات الصلة
تطور التفاضلية: تستند على اختلافات النواقل وبالتالي فهي في المقام الأول ملاءمة لمشاكل [التحسين العددية]
أمثلة سرب الجسيمات: استنادا على الأفكار من سلوك تدفق الحيوان كما يناسب في المقام الأول لمشاكل التحسين العددية.
أمثلة مستعمرة النمل: استنادا إلى الأفكار من مؤن النمل عن طريق فرمون الاتصالات لتشكيل المسارات في المقام الأول ملاءمة لمشاكل التحسين التوافقي.
خوارزمية مجتمع النحل الاصطناعي: استنادا إلى الأفكار في سلوك بحث النحل عن الطعام عبر تواصل بالفيرومون لتشكيل مسارات. تناسب مسائل المخططات والاستمثال التوافقي.
خوارزمية أمثلة الاعشاب الغازية: استنادا إلى الأفكار من مستعمرة سلوك الأعشاب في البحث والعثور على مكان مناسب للنمو والتكاثر.
البحث عن الانسجام: استنادا إلى الأفكار من سلوك الموسيقيين في البحث عن التجانس الأفضل هذه الخوارزمية مناسبة للأمثلة التوافقية، وكذلك الأمثلة المعلمة.
تكيف غاوسي: استنادا إلى معلومات نظرية تستخدم للوصول للحد الأقصى من العائد التصنيعي ويعني ملائمة أو المعلومات المتوسطة.
معرض صور
قائمة المراجع
Ashlock, D. (2006), Evolutionary Computation for Modeling and Optimization, Springer, ISBN 0-387-22196-4.
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. ISBN 978-1-4092-0073-4.
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.
انظر أيضا
علم الأحياء التنموي
مؤثر جيني
حياة اصطناعية
مراجع
وصلات خارجية
.دليل ميداني للبرمجة الوراثية by Poli, Langdon, and McPhee. Available as a free PDF, or.
Demo applet of an evolutionary algorithm for solving TSP's and VRPTW problems
International Society for Genetic and Evolutionary Computation- Home of the largest conference on the subject, GECCO (since January 1, 2005 reorganized to become Special Interest Group for Genetic and Evolutionary Computation of the ACM
Illinois Genetic Algorithms Laboratory (IlliGAL).
Evolutionary Algorithms Project - A project for evolutionary algorithms
The Systems Optimization Group (SOP)
Kanpur Genetic Algorithms Laboratory (KanGAL)
Evolutionary Computation Repository
Evolutionary Computing European Network Of Excellence
Hitch-Hiker's Guide to Evolutionary Computation (FAQ for comp.ai.genetic)
Evolutionary computation in manufacturing scheduling
www.talkorigins.org: Genetic Algorithms and Evolutionary Computation
Evolutionary Computation Lab at George Mason University (ECLab)
CILib - GPLed computational intelligence simulation and research environment written in Java, includes various EC implementations
Nanopond (Grey Thumb) - A very tiny (less than 1000 lines of C!) evolvable instruction set virtual machine that exhibits striking emergent behaviors.
Evolving Objects - GPLed C++ framework for evolutionary computation
E-Book - Global Optimization Algorithms - Theory and Application
Economist article - a showcase of real-world EA examples
European Centre for Soft Computing
BiSNET/e: A Cognitive Sensor Networking Architecture with Evolutionary Multiobjective Optimization
SymbioticSphere: A Biologically-inspired Architecture Network Systems with Evolutionary Multiobjective Optimization
Pervasive Adaptation is concerned with technologies used in information and communication systems which are capable of autonomously adapting to highly dynamic user contexts..
تطبيقات
تجريبي صغير من JOpt.SDK -- تطورية خوارزمية البرنامج أدوات لملعقة شاي في حل المشاكل وVRPTW
محكمة العدل الأوروبية (جافا)، شعبية التطورية حساب مجموعة الأدوات.
النتائج المضمونة (سي + +) آخر شعبية المفوضية الأوروبية مجموعة الأدوات
EvA2 (جافا)، وهو الغني المصدر المفتوح وعصام إرشادي الإطار الأمثل مع واجهة المستخدم الرسومية.
JAGA (جافا) المصدر المفتوح API لتنفيذ الخوارزميات الوراثية وتطبيقات البرمجة الجينية
(سي + +) آخر شعبية المفوضية الأوروبية مجموعة الأدوات.
Opt4J (جافا) ميتا إرشادي الأمثل بما في ذلك إطار متعدد الهدف خوارزميات التطورية
تنفيذا لجهاز الأمن السياسي في ماتلاب
محاكاة تطور مكتوبة في سلفرليغت 2
استمثال رياضي
تطور
خوارزميات تطويرية
سيبرنيطيقا
نظرية التطور