IRE: Inductive Rule Extraction

استخراج قانون استقرائی

IRE: Inductive Rule Extraction

استخراج قانون استقرائی

روابط یادگیری در ZCS وXCS

شرح سیستم دسته بند سطح صفر

این سیستم با آشکارساز[1] محیط را حس و ورودی سیستم را دریافت و اثرگذار[2] با موتور عمل در ارتباط است. علاوه بر این محیط هر دفعه تقویت عددی را فراهم می‌کند که در اینجا پاداش نامیده می‌شود. در اوایل کار هالند ایده اصلی یک سیستم سنجش و یادگیر در یک محیط برای بدست آوردن پاداش ارائه شد.

[P] یا جمعیت شامل مجموعه دستهبندهای فعلی و از الفبای باینری به علاوه نماد # که نشان دهنده "بی‌تفاوت" می باشد ساخته شده است. پس از دریافت وضعیت محیط از آشکارساز شرط هر دسته بند با آن مقایسه می‌شود. اگر هر بیت به جز # از شرط دسته بندها در آشکارساز صدق کند، آن دسته بند به مجموعه نظیر یا تطبیق[3] [M] اضافه می‌شود.

سپس یک عمل از میان اعضای تطبیق انتخاب می‌شود. روش های ممکن و مفیدی برای انتخاب عمل وجود دارد اما سیستم دسته بند سطح صفر شاید ساده ترین روش تصادفی را انتخاب ‌کند: یک چرخ رولت[4] با توجه به قدرت اعضای تطبیق. بنابراین یک عمل خاص با احتمال مساوی از جمع قدرت دسته بندهای تطبیق آن عمل تقسم بر مجموع قدرت دسته بندهای تطبیق بدست می آید. سپس مجموعه عمل [A] که شامل همه اعضای [M] که برابر عمل a است شکل می‌گیرد. در نهایت a به واسط اثرگذار ارسال و متناسب با آن موتور عمل آن را در محیط اجرا می‌کند. قابلیت تعمیم سیستم دسته بند سطح صفر در مجموعه عمل[5] [A] بیان شده است.

شرطهای دسته بند‌های موجود در [A] ممکن است شامل # هایی باشد به طوری که با بیش از یک ورودی منطبق شود. شرایط به طور کلی متفاوت است: تعداد مختلف از # وجود دارد و یا بیت مشخص شده ممکن است در موقعیت های مختلف باشد. این تنوع منعکس کننده جستجوی سیستم دسته بند سطح صفر برای "بهترین" دسته بند در هر موقعیت است.

به طور کلی دسته بندهایی دارای بیشترین قدرت نسبی هستند تا زمانی که مطابق با بیشترین تعداد ورودی باشد. به نظر می‌رسد بیشترین فشار ذاتی در سیستم دسته بند سطح صفر و سیستم های شبیه آن به سمت چنین دسته‌بند‌هایی باشد. تقویت در سیستم دسته بند سطح صفر یا تخصیص اعتبار، چرخهای پیرامون [A] و نیز مجموعه عملِ مرحله-زمان قبلی [A]_-1 است. این چرخه به این صورت است که

1. یک بخش ثابت β (0< β<=1) از قدرت هر عضو [A] از قدرت اعضای آن کسر می‌شود و در سطل B که در ابتدا خالی است قرار داده می‌شود. اگر S_[A] جمع قدرت های اعضای [A] باشد، نتیجه کسر βS_[A] از S_[A] در سطل قرار داده می‌شود.

2. اگر سیستم بلافاصله[6] پاداش r_imm را از محیط بعد از انجام عمل a دریافت کرد یک کمیت βr_imm/|A| به قدرت هر دسته بندی در [A] اضافه می‌شود (|A| تعداد دسته بندها در [A] است). نتیجه افزایش S_[A] بوسیله βr_imm است.

3. دسته‌بند‌ها در [A]_-1 (اگر خالی نباشد) قدرت خود را به وسیله ϒB/|A-1| افزایش می‌دهند. در اینجا ϒ فاکتور کاستن است (0< ϒ <=1)، B جمع مقدار قرار داده شده در سطل در مرحله است. و |A-1| تعداد دسته‌بند‌ها در [A]_-1.

4. [A] با [A]_-1 جایگزین و سطل خالی می‌شود. به طور کلی برای دیدن اثری از این روند در S_[A]، مفید است که [A]´ را به عنوان مجموعه عمل پیرو[7] [A] در زمان، تعریف شود. که روند را می‌توان تغییر و به صورت زیر نوشت:

(1)	S_[A]← S[A] – βS_[A] + β_rimm + βϒS_[A]´

این عبارت می‌تواند به موازات bucket brigade هالند دیده شود با سه استثنا اصلی که عبارتند از:

· نادیده گرفته شدن ویژگیهای دسته بند

· وجود نداشتن هیچ "رقابت پیشنهاد[8]"

· کاهش مقدار “brigade” یا "دسته" بوسیله فاکتور 1-ϒ در هر مرحله

چرخه تقویتی یک مرحله دیگر هم دارد که قدرت دسته بندی ها در مجموعه های مختلف [M] – [A] توسط یک کسر کوچک β≈Ƭ کاهش می‌یابد. با استفاده از "tax" یا " مالیات" (Ƭ) و ترکیب آن با چرخِ رولتِ انتخاب عمل.

کشف یا تولید دسته بند که شامل الگوریتم مولفه ای از سیستم دسته بند سطح صفر است با عملیات پوشش کامل می‌شود. عملیات الگوریتم ژنتیک در چرخه با نرخ متوسطی عمل می‌کند. هر زمان که احتیاج باشد الگوریتم ژنتتیک دو دسته‌بند بر اساس قدرت انتخاب و عملیات برش و یا جهش را با احتمال ثابتی انجام و فرزندان در جمعیت درج می‌شوند. برای نگهداری [P] در اندازه پایدار دو دسته بند متناسب با احتمال معکوس نقاط قوت خود حذف می‌شوند. قدرت اولیه دسته بندهای فرزند برابر است با مجموع قدرت والدین و فرزند که نیمی‌از قدرت والدین از آنها کم می‌شود و به کپی آنها اختصاص می‌یابد. اگر برش رخ دهد دقتها به آنها بازنشانده می‌شود. نرخ فراخوانی الگوریتم ژنتیک مسئله مطلقی است. اگر بیش از حد سریع اجرا شود قدرت ها به طور متوسط بیش از حد اعمال می‌شود و اگر بیش از حد به آرامی ‌اجرا شود سیستم به نرخ بهبود خوبی نمی‌رسد. در سیستم دسته بند سطح صفر نرخ الگوریتم ژنتیک توسط یک احتمال فراخوانی طبق زمان-مرحله کنترل می‌شود که باید توسط کاربر انتخاب شود.

عملیات پوشش زمانی رخ می‌دهد که مجموعه [M] خالی باشد یعنی دسته بند در [P] منطبق نشده باشد یا وقتی مجموع قدرت در [M]، S[M]، کمتر از کسر ϕ متوسط قدرت جمعیت باشد. پوشش یک دسته‌بند جدید با همه شرایط ورودی و شامل تعداد تعیین شدهای # را ایجاد می‌کند. عمل دسته بند جدید به صورت تصادفی انتخاب می‌شود و قدرت آن میانگین قدرت جمعیت گذاشته می‌شود. دسته بند جدید در [P] درج می‌شود و یک دسته بند در الگوریتم ژنتیک حذف می‌شود. پس از آن سیستم [M] جدید را شکل و چرخه به طور معمول ادامه می‌یابد.

خلاصه ای از لیست پارامترها

v N اندازه جمعیت.

v P_# احتمال وقوع # در شرطِ یک دسته بند که از طریق پوشش ساخته شده و شرط دسته بندهایی که به صورت تصادفی در جمعیت تولید می‌شود.

v S₀ قدرت اختصاصی به دستهبندهای جمعیت اولیه.

v β نرخ یادگیری برای بروز رسانی قدرت تحت bucket brigade.

v ϒ فاکتور کاهش برای bucket brigade.

v Ƭ کسری از قدرت که از دسته بندی های [M] – [A] کسر می‌شود.

v X احتمال برش در فراخوانی الگوریتم ژنتیک.

v μ احتمال جهش در فرزندان. جهش شامل 0،1 و # .

v ρ میانگین تعداد دسته بندی های ساخته شده بوسیله الگوریتم ژنتیک در زمان – مرحله انجام چرخه.

v ϕ اگر مجموع قدرت [M] کمتر از ϕ بار متوسط قدرت [P] شود پوشش رخ می‌دهد.

XCS

XCS محبوبترین مدل طبق خانواده میشیگان است. تناسب افراد بر اساس دقت پیش‌بینی هر قانون است. و الگوریتم Bucket Brigade به طور کامل جای خود را به یادگیری تقویتی داده است. همچنین واگذاری اعتبار بر پایه دقت یا سودمندی دسته بندها قرار گرفته است. الگوریتم ژنتیک در زیر جمعیتهایی که فقط شامل مجموعه تطبیق است و در موقعیتهای یکسان به کار گرفته شدهاند استفاده می‌شود.

تفاوتهایی بین سیستم دسته بند سطح صفر و XCS در تعریف تناسب دسته ها مکانیزم الگوریتم ژنتیک و عمل انتخابی پیچیده تر که تناسب مبتنی بر درستی را ممکن می‌سازد وجود دارد. چند تفاوت XCS با سیستم دسته بند یادگیر عبارتند از:

· لیست پیغام داخلی یا پیشنهاد قاعده ندارد.

· پاداش به دسته بندها توسط یک تکنیک بر پایه یادگیری تقویتی تعمیم داده شده است.

· الگوریتم ژنتیک به جای کار روی جمعیت بر روی مجموعه تطبیق یا آخرین – عمل کار می‌کند.

· تناسب دسته بندها به جای محاسبه خودشان بر پایه صحت پیشگوییهای دسته بند است.

شرح مختصر این سیستم به صورت زیر میباشد:

ü جمعیتی از قوانین که در مراحل مختلف سیستم مورد استفاده قرار می‌گیرد:

v [P]: جمعیتی که شامل تمام قوانین تکامل یافته است. این جمعیت را می‌توان از مجموعه ای از قوانین شناخته شده، خالی یا داشتن[9]، برای هر کلاس یا یک قانون کاملا عمومیِ‌واحد به طور تصادفی تولید کرد.

v [M]: این مجموعه نظیر، مجموعه ای از قوانین فعال شده به وسیله نمونه ورودی است.

v [A]: زمانی که یک کلاس پیشبینی شده از قوانین در [M] انتخاب شد، مجموعه عمل [A] شامل همه قوانین پیشبینی این کلاس ساخته می‌شود.

v [A]-1: مجموعه عمل سیکل قبلی است.

ü نمایش قانون

هر قانون یک قسمت شرط و یک قسمت عمل دارد. در مسائل دسته بند قسمت عمل یک کلاس مرتبط است. شرط یک رشته با تعدادی نماد باینری که با استفاده از الفبای سه تایی ساخته شده است {"#"،"0"،"1"} علامت # نشان دهنده بی تفاوت است. هر دستهبند معمولا شامل پارامتر های زیر است:

v P: تخمین از مقدار پاداش دریافتی از محیط اگر آن دسته بندها به درستی در نمونه کار کند و عمل پیشنهادی در محیط اعمال شود.

v ε: تخمین خطای پیشبینی در دسته بند که تخمینی از میانگین تفاوت بین پاداش دریافتی و مقدار تخمینی دسته بند مزبور است.

v f: تناسب دسته بند

v exp: تعداد نمونه هایی است که با قسمت شرط این دسته بند منطبق شده است.

v t_s: آخرین زمانی که الگوریتم ژنتیک در مجموعه عمل استفاده شده و این دسته بند درگیر شده است.

v a_s: تخمین اندازه مجموعه عمل که دسته بند مزبور در آن شرکت کرده است.

v num: تعداد میکرو-دسته بندهایی که نشان دهنده ماکرودسته بند است یعنی این دسته بند نشان دهنده چند دسته بند دیگر است. قوانین در XCS می‌توانند با دیگر دسته بندها تلفیق شوند و ماکرو-دسته بندها را بسازند. در این حالت دسته هایی که از لحاظ شرط و عمل یکسان هستند را یکبار در جمعیت نشان داد ولی با این پارامتر تعداد واقعی آنها را مد نظر قرار داد.

· پارامترهای XCS

v N: حداکثر سایز جمعیت

v β: نرخ یادگیری برای p، e و f

v α1 و e0 و v برای محاسبه تناسب دسته بندها استفاده می‌شود.

v :Θ_GAآستانه فعال شدن الگوریتم ژنتیک است. الگوریتم ژنتیک فعال می‌شود اگر تعداد متوسط آخرین استفاده بیشتر از آستانه باشد.

v Θ_del: آستانه حذف دسته بند است. اگر مقدار expدسته بند بیشتر از این آستانه باشد، می‌توان آن را با توجه به تناسب حذف کرد.

v Δ: درصد زیر میانگین تناسب [P] است که در آن تناسب یک دسته بند تعدیلشده احتمال حذف آن است.

· چرخه کار

v ساخت [M] از [P] با هر نمونه ورودی

v اگر [M] خالی است یا برخی از کلاسها در [M]پیشبینی نشده است عملیات پوشش فعال و یک دسته بند جدید ساخته می‌شود که در آن از نسخه تعمیم یافته نمونه ورودی و استفاده از یک کلاس پوشش نیافته در [M] است.

v از [M] یک پیشبینی برای هر کلاس بر اساس مقدار p و f هر دسته بندی ساخته می‌شود.

v یک کلاس از محاسبات پیشبینی انتخاب و [A] ساخته می‌شود. سیستم یک نتیجه[10] بر اساس این پیشبینی را باز می‌گرداند.

· الگوریتم ژنتیک

الگوریتم ژنتیک به صورت دورهای بر اساس Θ_GA فعال و بر روی [M] اجرا می‌شود. الگوریتم ژنتیک والدین را از [M] انتخاب و یک سیکل الگوریتم ژنتیک به صورت کامل انجام می‌شود. اما دو فرزند در [P] بدون جایگزینی با والدین درج می‌شود. اگر تعداد دسته بندها در [P] به N برسد برخی از دسته بندها باید حذف شود.

· انتخاب دسته بندها برای حذف

هر دسته بند دارای یک احتمال حذف است که محاسبه آن به شرح زیر است:

v احتمال حذف دسته بند متناسب با تخمین اندازه مجموعه نظیری محاسبه می‌شود که در آن دسته‌بند می‌تواند ظاهر ‌شود. در این روش همه دستهبندهای زیرجمعیت تعداد مساوی از منابع می‌گیرند.

v احتمال در صورتی که دسته بند به اندازه کافی با تجربه باشد و تناسب آن کمتر از میانگین تناسب [P] باشد می‌تواند افزایش یابد.

· دسته بندهای ماکرو

وقتی افراد جدیدی در جمعیت اضافه می‌شوند سیستم بررسی می‌کند که آیا افراد جدید با دیگر افراد جمعیت برابر است یا نه. اگر مساوی باشد دستهبند جدید اضافه نمی‌شود و عدد مربوط به این دسته‌بند افزایش می‌یابد.

مولفه کارایی

با توجه به ورودی یک مجموعه نظیر [M] به صورت معمول شکل گرفته است. سپس یک سیستم پیشبینی[11] P(a_i) برای هر عمل a_i در [M] ارائه می‌کند. چندین راه برای تعیین P(a_i) وجود دارد. ما در درجه اول یک تناسب – وزنیِ میانگین برای پیشبینی دستهبندهای انتخابی a_i را داریم. احتمالاً روشی می‌خواهد که حاصل "بهترین حدس" برای سیستم به عنوان بازدهی – ورودی ویا خروجی – دریافت کند اگر a_i انتخاب شود. مقدار P(a_i) جایی در یک آرایه پیشبینی [12]است (برخی از مکانها مقداری دریافت نمی‌کنند اگر عمل مربوطهای در [M] نداشته باشند) که انتخاب شده است.

بسیاری از روشهای"انتخاب – عمل" شدنی هستند. سیستم ممکن است به سادگی عملی با پیشبینی بیشتر را انتخاب کند. برای اختصار ما این عمل انتخابی را قطعی در نظر می‌گیریم.

روش دیگر این است که این عمل به صورت احتمالاتی با احتمال انتخاب P(a_i) انتخاب شود که چرخِ رولتِ انتخابِ عمل نامیده می‌شود. در بعضی موارد ممکن است عمل کاملا به صورت تصادفی انتخاب شود که عملها با پیشبینی های تهی نادیده گرفتن P(a_i) می شوند.

هنگامی‌که عمل انتخاب شد سیستم مجموعه عمل[A] متشکل از دسته بندهای انتخابی در [M] که از عمل انتخابی حمایت می‌کند را شکل می‌دهد. این عمل به اثرگذار ارسال و بلافاصله پاداش r_imm ممکن است یا ممکن نیست توسط محیط بازگردد.

مولفه تقویتی

مولفه تقویتی در XCS شامل بروز رسانی پارامترهای دستهبند p ، ε و F در مجموعه عمل مرحله زمانی قبلی [A]_-1، است. مقدار p به وسیله روش یادگیری تقویتی تنظیم می‌شود، که در شکل به صورت ترکیبی از حداکثر P(a_i) از آرایه پیشبینی، "کاستن[13]" آن به وسیله مضرب (0 <γ ≤1) γ و اضافه کردن پاداش خارجی از زمان-گام قبلی نشان داده شده است. مقدار بدست آمده P نامیده می‌شود که برای تعدیل پیشبینی p_j در دسته‌بند‌های [A]_-1 طبق استاندارد Widrow-Hoff استفاده می‌شود و از پارامتر β (0< β≤1) که بصورت β(P- p_j) + p_j ← p_j است، استفاده می‌شود (β برابر نرخ یادگیری است). اگر چه برای هر دسته بند در [A]_-1 ، بروز رسانی درواقع به وسیله اولین بازمحاسبه تناسب F_j با استفاده از مقدار فعلی ε_j شروع می‌شود. همچنین ε_j خود از P و مقدار فعلی p_j استفاده می‌کند. تکنیک Widrow-Hoff برای مقداردهی ε_j نسبت به تفاوت|P-p_j| استفاده شده که به صورت β(|P- p_j|- ε_j) + ε_j ←ε_j است. در پایان p_j همانطور که در بالا توضیح داده شد مقدار دهی شده است. (مقدار دهی F و ε لفظ " مولفه تقویتی " را می‌سازد).

روش Widrow-Hoff برای p و ε استفاده شده و برای قسمت F تنها پس از یک دسته بند حداقل β/1 تنظیم شده است. قبل از آن مقادیر جدید در هر مورد میانگینِ مقادیر قبلی و فعلی است. برای مثال، مقدار p_j در چهارمین مقدار دهی فقط یک – چهارم جمع چهار مقدار اولیه P خواهد بود اگر> 4 β/ 1. این تکنیک دو مرحله ای باعث حرکت سریعتر به مقدار میانگین "درست" می‌شود که باعث می‌شود سیستم کمتر به تنظیمات پارامترهای اولیه و احتمالا خودسرانه حساس شود. این تکنیک MAM[14] نامیده و توسط Venturini در سال 1994 معرفی گردیده است. برای پیگیری تعداد بروز رسانی ها یک دسته بند پارامتر سابقه[15] که هر زمان که در [A] باشد افزایش می‌یابد را نگهداری می‌کند.

مولفه اکتشاف

همانطور که در شکل دیده می‌شود الگوریتم ژنتیک روی قسمت مجموعه نظیر [M] اعمال می‌شود. که دو دسته از [M] با احتمال به نسبت تناسب آن ها انتخاب کپی و عمل پیوند زنی یا برش را روی کپی ها با احتمال χ و عمل جهش را با احتمال µ انجام می‌دهد. اگر [P] شامل کمتر از N عضو باشد کپیها در جمعیت درج و حذف جبرانی رخ نمی‌دهد. در غیر این صورت دو دسته بند به طور تصادفی از [P] حذف می‌گردد. دو روش تجربی برای حذف دسته بند پیشنهاد می‌شود:

· هر دسته بند تخمین اندازه مجموعه نظیر که در آن رخ می‌دهد را نگه می‌دارد. تخمین هر زمان که دسته بند در [M] شرکت کند با استفاده از روش MAM با نرخ β ، بروز می‌شود. احتمال حذف دسته بند متناسب است با تخمین اندازه مجموعه نظیر که موجب می‌شود در تمام مجموعه نظیر به یک اندازه باشد، به گونه ای که منابع دسته بند کم و بیش به یک انداره اختصاص می‌یابد.

· احتمال حذف دسته بند در (1) است، به جز اگر تناسب آن کمتر از یک کسر کوچک δ از میانگین تناسب جامعه باشد. بعد از آن احتمال (1) میانگین تناسب تقسیم بر تناسب دسته بند چند برابر می‌شود. برای مثال فرض کنید δ برابر 0.1 است در نتیجه چنین دسته بند با تناسب پایین احتمال حذف 10 برابری نسبت به دیگر دستهبندها دارد.

نرخ وقوع الگوریتم ژنتیک با هدف تخصیص منابع تقریبا به طور مساوی بین مجموعه نظیرهای مختلف انجام می‌شود. بسته به شرایط ممکن است در برخی از مجموعه های نظیر بیشتر از دیگران رخ دهد. اما در کل نرخ تولید مثل در واحد زمان تقریبا ثابت است. برای اجرای الگوریتم ژنتیک هر دسته بند در بدو تولد از یک شمارنده می‌خواند که در هر مرحله از زمان افزایش یافته و نشان[16] می‌شود. وقتی یک مجموعه نظیر شکل می‌گیرد، XCS متوسط زمان-نشان[17] دستهبند را محاسبه و اگر تفاوت بین آن میانگین و شمارنده فعلی بیشتر از آستانه Θ باشد الگوریتم ژنتیک را اجرا می‌کند. این تکنیک و تکنیک حذف باعث می‌شوند دسته بندها تقریبا به طوری مساوی به قسمت های مختلف تخصیص یابند.

در کنار الگوریتم ژنتیک مولفه اکتشاف شامل یک مکانیزم پوشش برای دو شرایط خاص است.

· گاهی اوقات اتفاق می‌افتد که دسته بند ورودی معینی ندارد – [M] تهی است. در این مورد XCS به سادگی یک دسته‌بند با شرط نظیر ورودی شرطی که از آشکارساز دریافت می‌کند و یک عمل به صورت تصادفی ایجاد می‌کند. دسته بند جدید در [P] درج و یک دسته بند حذف می‌شود. پس از آن سیستم یک [M] جدید را شکل می‌دهد و فرآیند به طور معمول ادامه می‌یابد.

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

محاسبه تناسب

تناسب یک دسته بند در هر زمان متعلق به [A]_-1 یا [A] در مسئله های تک – مرحله ای بروز می‌شود. از دید کلی تر تناسب توسط یک کمیت که وابسته به دقت[18] درستی یک دسته‌بند نسبت به دقت دیگر دسته بند‌ها در مجموعه بروز می‌شود. سه گام در محاسبه وجود دارد. اول محاسبه دقت هر دستهبند (k_j). دقت به عنوان یک تابع ارزش فعلی ε_j تعریف می‌شود. تعدادی تابع کاربردی داریم که یکی از بهترینهای آن است:

k_j= exp[(ln α)( ε_j- ε₀)/ ε₀)] برای ε_j> ε₀ در غیر این صورت1، این تابع به صورت نمایی برای ε_j> ε₀ افت می‌کند. نرخ به گونهای است که ε_j=2ε₀ برابر است با α (0 < α<1)، بنابراین α کوچکتر یعنی نزول تندتر. بعد محاسبه دقت نسبی (‌_j' κ) برای هر دستهبند که از تقسیم آن بر جمع دقتها در مجموعه بدست می‌آید. در نهایت از دقت نسبی برای تنظیم تناسب دستهبند F_j مورد استفاده در تکنیک MAM استفاده می‌شود. اگر تناسب در زمان کمتر از β/1 تنظیم شود آنگاه+ β( k´_j - F_j ) F_j ← F_j . در غیر این صورت F_j از میانگین مقدار جاری و قبلی k´_j بدست می‌آید.

دسته بند ماکرو [19]

هرگاه XCS دستهبند جدید ایجاد می‌کند، یا هنگام مقداردهی اولیه جمعیت اسکن شده تا ببیند دسته‌بند جدید دارای شرایط و عمل دستهبندهای موجود است یا نه. اگر چنین است اگر دستهبند جدید به جمعیت اضافه شده بود یک فیلد تکثر[20] در دستهبند موجود است که یکی افزایش می‌یابد. و اگر دستهبند با شرط و عمل یکسان وجود نداشت دستهبند جدید به جمعیت با مقداردهی اولیه یک برای فیلد تکثر اضافه می‌شود. در اصل یک تکنیک برنامه نویسی است که به سرعت [P] را با هر ورودی تطبیق می‌دهد.