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

·         هدف - ارائه یک مدل رسمی برای اثربخشی فرآیند جستجوی GA.

·         در ادامه، ابتدا از طریق چارچوبی که توسط هالند [۱] رسمی شده است و توسط گلدبرگ [2] محبوبیت یافت به مسئله نزدیک می‌شویم.

·         این بر ارائه مدلی برای انتظار بقای طرحواره متمرکز است، جایی که این طبیعتاً خود یک محدودیت را نشان می‌دهد.

·         سپس به بررسی اشکالات بیشتر «قضیه طرحواره» و برخی از تلاش‌های اخیر برای ارائه بازنمایی بیشتر قضایای طرحواره.

---

·         مورد یک GA متعارف را در نظر بگیرید،

§         الفبای دودویی؛

§         افراد با طول ثابت با طول مساوی، l؛

§         انتخاب متناسب برازش؛

§         متقاطع تک نقطه‌ای؛

§         جهش عاقلانه ژن.

    تعریف 1 - طرحواره، H.

§         طرحواره زیرمجموعه ای از فضای همه افراد ممکن است که همه ژن ها برای الگوی طرح واره H مطابقت دارند.

·         اگر A نشانگر الفبای آلل های ژن باشد، A∪* الفبای طرحواره است، جایی که * نماد «نویسه» مطابقت با هر مقدار آللی است.

§         به عنوان مثال برای الفبای دودویی A ∈ {0, 1, *} که در آن *∈{0, 1}

مثال

·         برای یک فرد دوتایی با توالی ژن {0111000}، پس از آن یک (از بسیاری) طرحواره تطبیق ممکن به شکل H=[*11*0**] است

·         طرح H = [0 1 * 1 *]  مجموعه کروموزوم را مشخص می‌کند،

·         نیازی به گفتن نیست که همه طرحواره‌ها برابر نیستند، بنابراین، 1****** به ما نمی‌گوید 01**110.

·         علاوه بر این، طرح 1*****0 کل طول یک فرد را در بر می گیرد در حالی که 1*1**** نمی‌کند.

·         تعریف 2 – ترتیب طرحواره، o(H).

§         ترتیب طرحواره، o(⋅)، تعداد ژن‌های غیر «*» در طرح H است.

§         مثال، o(* * * 0 * * *) = 1

·         تعریف 3 - طرحواره تعیین طول، δ(H).

§         طول تعیین کننده طرحواره، δ(H)، فاصله بین اولین و آخرین ژن غیر «*» در طرحواره H است.

§         مثال، δ(* * * 0 * * *) = 4 – 4 = 0

·         نکته

§         برای کاردینالیته، k، طرحواره (k + 1)^l در رشته ای به طول «l» وجود دارد.

§         ما اکنون در موقعیتی هستیم که به صورت تدریجی اثر انتخاب‌های مختلف و عملگرهای جستجو مرتبط با تعریف فوق برای مورد خاص یک GA متعارف با ژن‌های دودویی را تعریف می‌کنیم.

انتخاب اپراتورها - انتخاب متناسب برازش

·         اساساً تمام چیزی که ما سعی در مدل‌سازی آن داریم، احتمال این است که افراد، h، نمونه‌های طرحواره، H، یا P (h ∈ H) باشد.

·         روش‌های مختلفی برای مدل‌سازی این موضوع وجود دارد.

§         مدل دو بخشی زیر را در نظر بگیرید،

o       احتمال انتخاب α تعداد نمونه های طرحواره H در جمعیت.

o       احتمال انتخاب μ برازش متوسط ​​طرحواره H نسبت به میانگین برازش همه افراد جمعیت

o       بنابراین،

یا             

      که در آن m(H, t) تعداد نمونه‌های طرحواره H در نسل t است.

·         لما 1 - تحت انتخاب تناسب برازش تعداد مورد  انتظار  از طرح واره H در زمان t است،