قضیه طرحواره هالند

 قضیه طرحواره هلند که قضیه بنیادی الگوریتم‌های ژنتیک[1] نیز نامیده می‌شود [۱]، نابرابری است که از دانه‌بندی درشت[2] معادله‌ای برای دینامیک تکاملی[3] ناشی می‌شود. قضیه طرحواره می‌گوید که طرحواره‌های کوتاه و مرتبه پایین[4] با برازندگی بالاتر از متوسط[5] ​​به طور تصاعدی در فرکانس در نسل‌های متوالی افزایش می‌یابد. این قضیه توسط جان هالند در دهه 1970 مطرح شد. در ابتدا به طور گسترده‌ای به عنوان پایه‌ای برای توضیح قدرت الگوریتم‌های ژنتیک در نظر گرفته شد. با این حال، این تفسیر مفاهیم در چندین نشریه مورد نقد قرار گرفته است، [2] که در آن قضیه طرحواره به عنوان یک مورد خاص از معادله قیمت[6] با تابع شاخص طرحواره به عنوان اندازه‌گیری ماکروسکوپی نشان داده شده است.

طرحواره الگویی است که زیرمجموعه‌ای از رشته‌ها را با شباهت در موقعیت‌های رشته خاصی مشخص می‌کند. طرحواره‌ها حالت خاصی از مجموعه‌های استوانه‌ای[7] هستند و از این رو فضای توپولوژیکی[8] را تشکیل می‌دهند.

 شرح

رشته‌ای دودویی با طول 6 را در نظر بگیرید. طرحواره 1*10*1 مجموعه تمام رشته‌های طول 6 را با 1 در موقعیت های 1، 3 و 6 و 0 در موقعیت 4 توصیف می‌کند. * یک نویسه جانشین[9] (فرانویسه می‌تواند جایگزینی برای دیگر نویسه یا نویسه‌ها در یک رشته باشد.) است، به این معنی که موقعیت‌های 2 و 5 می‌توانند مقدار 1 یا 0 داشته باشند. ترتیب طرحواره o(H) به عنوان تعداد موقعیت‌های ثابت در قالب تعریف می‌شود، در حالی که طول تعریف[10] δ(H) فاصله بین اولین و آخرین موقعیت خاص است. ترتیب 1*10*1 4 است و طول تعریف آن 5 است. تناسب یک طرحواره برازش متوسط ​​همه رشته‌های مطابق با طرحواره است. تناسب یک رشته، اندازه‌گیری مقدار راه‌حل مسئله کدگذاری‌شده است، همانطور که توسط یک تابع ارزیابی خاص مسئله محاسبه می‌شود. با استفاده از روش‌های ایجاد شده و عملگرهای ژنتیکی الگوریتم‌های ژنتیک، قضیه طرحواره بیان می‌کند که طرحواره‌های کوتاه و مرتبه پایین با برازندگی بالاتر از حد متوسط ​​در نسل‌های متوالی به‌طور تصاعدی افزایش می‌یابند. به صورت معادله ۱ بیان می‌شود.

۱)                                                                        

اینجا m(H, t) تعداد رشته‌های متعلق به طرحواره H در نسل t است،