الخوارزميات التجريبية

في علوم الحاسوب ، تُعرف الخوارزميات التجريبية (أو الخوارزميات التجريبية ) بأنها ممارسة استخدام الأساليب التجريبية لدراسة سلوك الخوارزميات . تجمع هذه الممارسة بين تطوير الخوارزميات وتجريبها: فلا تقتصر الخوارزميات على التصميم فحسب، بل تشمل أيضًا التنفيذ والاختبار في مجموعة متنوعة من المواقف. في هذه العملية، يُحلل التصميم الأولي للخوارزمية بحيث يمكن تطويرها تدريجيًا. ^{[ 1 ]}

تُكمّل أساليب الخوارزميات التجريبية الأساليب النظرية لتحليل الخوارزميات . ^{[ 2 ]} ومن خلال التطبيق المنهجي للأساليب التجريبية، ولا سيما من الإحصاء ، يُمكن في كثير من الأحيان الحصول على رؤى ثاقبة حول سلوك الخوارزميات، مثل خوارزميات الاستدلال عالية الأداء للمسائل التوافقية المعقدة التي يصعب (حاليًا) تحليلها نظريًا. ^{[ 3 ]} كما يُمكن استخدام الأساليب التجريبية لتحقيق تحسينات جوهرية في كفاءة الخوارزميات . ^{[ 4 ]}

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

تُنشر الأبحاث في مجال الخوارزميات التجريبية في العديد من المجلات، بما في ذلك مجلة ACM للخوارزميات التجريبية (JEA) ومجلة أبحاث الذكاء الاصطناعي (JAIR). إلى جانب كاثرين ماكجيوخ، تشمل قائمة الباحثين البارزين في مجال الخوارزميات التجريبية كلاً من برنارد موريه ، وجوزيبي إف. إيتاليانو ، وهولجر إتش. هوس ، وديفيد إس. جونسون ، وروبرتو باتيتي . ^{[ 9 ]}

في غياب الخوارزميات التجريبية، قد يتضمن تحليل تعقيد الخوارزمية أساليب نظرية متنوعة قابلة للتطبيق على مختلف الحالات التي يمكن استخدام الخوارزمية فيها. ^{[ 10 ]} غالبًا ما تُعدّ اعتبارات الذاكرة والتخزين المؤقت عوامل مهمة يجب مراعاتها عند الاختيار النظري لخوارزمية معقدة، أو عند تحديد منهجية تحسينها، لغرض معين. ^{[ 11 ] [ 12 ]} يُعدّ تحليل أداء البرامج تقنية ديناميكية لتحليل البرامج ، تُستخدم عادةً لإيجاد وتحليل نقاط الاختناق في كود التطبيق بأكمله ^{[ 13 ] [ 14 ] [ 15 ]} أو لتحليل التطبيق بأكمله لتحديد الكود ذي الأداء الضعيف. ^{[ 16 ]} يمكن لأداة تحليل الأداء الكشف عن الكود الأكثر صلة بمشاكل أداء التطبيق. ^{[ 17 ]}

قد يساعد محلل الأداء في تحديد متى يُفضّل اختيار خوارزمية على أخرى في موقف معين. ^{[ 18 ]} عند تحليل أداء خوارزمية معينة، كما هو الحال في تحليل التعقيد، غالبًا ما تكون اعتبارات الذاكرة والذاكرة المؤقتة أكثر أهمية من عدد التعليمات أو دورات الساعة؛ ومع ذلك، يمكن النظر إلى نتائج محلل الأداء في ضوء كيفية وصول الخوارزمية إلى البيانات بدلاً من عدد التعليمات التي تستخدمها. ^{[ 19 ]}

قد يوفر تحليل الأداء فهمًا بديهيًا لسلوك الخوارزمية ^{[ 20 ]} من خلال عرض نتائج الأداء كتمثيل مرئي. ^{[ 21 ]} وقد طُبِّق تحليل الأداء، على سبيل المثال، أثناء تطوير خوارزميات مطابقة الأحرف البديلة . اعتمدت الخوارزميات المبكرة لمطابقة الأحرف البديلة، مثل خوارزمية wildmat لريتش سالز ^{[ 22 ]} ، عادةً على الاستدعاء الذاتي ، وهي تقنية وُجِّهت إليها انتقادات بسبب أدائها. ^{[ 23 ]} طُوِّرت خوارزمية كراوس لمطابقة الأحرف البديلة بناءً على محاولة صياغة بديل غير استدعائي باستخدام حالات اختبار ^{[ 24 ]} ، تلتها تحسينات مُقترحة من خلال تحليل الأداء ^{[ 25 ]} ، مما أدى إلى استراتيجية خوارزمية جديدة وُضِعت في ضوء تحليل الأداء إلى جانب اعتبارات أخرى. ^{[ 26 ]} توفر أدوات تحليل الأداء التي تجمع البيانات على مستوى الكتل الأساسية ^{[ 27 ]} أو التي تعتمد على دعم الأجهزة ^{[ 28 ]} نتائج دقيقة بما يكفي لمساعدة مطوري البرامج في تحسين الخوارزميات لجهاز كمبيوتر أو حالة معينة. ^{[ 29 ]} يمكن أن يساعد تحليل الأداء المطورين على فهم خصائص الخوارزميات المعقدة المطبقة في المواقف المعقدة، مثل خوارزميات التطور المشترك المطبقة على مشاكل اختبارية عشوائية، وقد يساعد ذلك في تحسين التصميم. ^{[ 30 ]}

• هندسة الخوارزميات
• تحليل الخوارزميات
• تحليل الأداء (برمجة الحاسوب)
• تحسين الأداء
• تطوير البرمجيات