تحليل وقت تشغيل (1 + 1) EA في حساب تتابعات الإدخال والإخراج الفريدة

حساب تتابعات الإدخال والإخراج الفريدة (UIO) هو مشكلة أساسية وصعبة في اختبار التوافق للآلات ذات الحالة المحدودة (FSM). لقد أظهرت الأبحاث التجريبية السابقة أن الخوارزميات التطورية (EAs) يمكن تطبيقها بنجاح لإيجاد UIOs لبعض الآلات ذات الحالة المحدودة. ومع ذلك، قبل أن يمكن التوصية بالخوارزميات التطورية كتقنية عملية لحساب UIOs، من الضروري فهم إمكانات وقيود هذه الخوارزميات بشكل أفضل في هذه المشكلة. على وجه الخصوص، هناك حاجة إلى مزيد من البحث لتحديد الفئات الحلقية للمشكلة التي تكون فيها EAs ممكنة، والفئات الحلقية التي تكون فيها EAs أفضل بشكل مثبت من استراتيجيات البحث العشوائي. تقدم هذه الورقة تحليلات نظرية ورقمية صارمة لوقت تشغيل (1 + 1) EA والبحث العشوائي على عدة فئات حلقية مختارة من هذه المشكلة. توضح التحليلات النظرية أولاً، أنه توجد فئات حلقية تكون فيها EA فعالة، بينما يفشل الاختبار العشوائي تمامًا. ثانيًا، تم تقديم فئة حلقية تعتبر صعبة لكل من الاختبار العشوائي وEA. أخيرًا، تم تقديم فئة حلقية محددة بمعايير يمكن تعديل صعوبتها. تقدّر الدراسة العددية الثوابت في التعبيرات التقريبية الناتجة عن التحليل النظري، وتغير وقت التشغيل. تتناسب النتائج العددية بشكل جيد مع النتائج النظرية، حتى للأحجام الصغيرة من حالات المشاكل. معًا، توفر هذه النتائج تصنيفًا نظريًا أوليًا لإمكانات وقيود (1 + 1) EA على مشكلة حساب UIOs.