دانلود پایان نامه ارشد با موضوع الگوريتم، يادگير، دريافت

است، صورت مي‌گيرد.
الگوريتمهاي تخمين‌زن اوليه از جمله الگوريتم تعقيبي تاتاچار و ساستري[119] ، بردار احتمال عمل را براساس ويژگيهاي دراز مدت110 محيط بروز مي‌کنند، در حاليکه الگوريتمهاي يادگيري استاندارد و اتوماتاهاي يادگير با ساختار ثابت اين کار را براساس خصوصيات کوتاه مدت محيط انجام مي‌دهند. با توجه به اهميت هردو دسته ويژگي کوتاه مدت و دراز مدت محيط در کاربردهاي مختلف، اومن [120 , 121] دسته ديگري از اين الگوريتمها را ارائه نموده که هر دو جنبه را مد نظر قرار مي‌دهند. در زيربخشهاي بعدي به تعريف و بررسي انواع اين الگوريتمها براساس[121]مي‌پردازيم.
الگوريتم تعقيبي پيوسته CPRP 111
همانگونه که اشاره شد، اولين الگوريتم تعقيبي، يعني الگوريتم تعقيبي پيوسته، توسط تاتاچار و ساستري[119] براي اولين بار مطرح گرديد. اين الگوريتم بر مبناي تخمين‌هاي دراز مدت عمل مي‌نمايد. اين الگوريتم از سه مرحله تشکيل شده است. اولين مرحله، مشتمل است بر انتخاب عمل بر مبناي توزيع احتمال . خواه اتوماتا پاداش گرفته و يا جريمه شده باشد، مرحله دوم مؤلفه‌اي از را تخمين دريافت پاداشش بيشينه(عمل بهينه جاري) است، افزايش داده و احتمال تمام عمل‌هاي ديگر را کاهش مي‌دهد. قوانين بروز رساني احتمالات را در قالب برداري، بصورت زير مي‌توان نشان داد:
(‏7-11)

که در آن عملي است که هم‌اکنون، طبق تخمين‌ها به عنوان عمل بهينه شناخته مي‌شود.
اين معادله نشان مي‌دهد که بردار احتمال عمل به سمت عمل داراي بيشترين تخمين دريافت پاداش حرکت مي‌نمايد.
مرحله آخر عبارتست از برز رساني تخمين مداوم پاداش گرفتن احتمالها. براي محاسبه بردار تخمين‌هاي دريافت پاداش که با نشان داده مي‌شود، دو بردار اضافه ديگر نيز در نظر گرفته مي‌شوند: و ، که تعداد دفعاتي است که عمل iام انتخاب شده و تعداد دفعاتي است که عمل پاداش دريافت نموده است شکل 7-2 ، اين الگوريتم را بصورت فرماليته بيان مي‌کند.
پارامترها:

سرعت پارامتر يادگيري با شرط
m
انديس مؤلفه بيشينه بردار تخمين دريافت پاداش ،

بردار يکه با r مؤلفه که مؤلفه mام آن 1 است.

تعداد دفعاتي که عمل iام تا زمان t پاداش دريافت کرده است، با شرط

تعداد دفعاتي که عمل iام تا زمان t انتخاب شده است، با شرط
شكل ‏7-1) پارامترهاي الگوريتم تعقيبي پيوسته CPRP
الگوريتم:
Initialize
Initialize by choosing each action a number of times.
Repeat
Step 1) At time t pick according to probability distribution. Let.
Step 2) If is the action with the current highest reward estimate, update as
Step 3) Update according to the following equations for the action chosen
End Repeat
شكل ‏7-2) الگوريتم تعقيبي پيوسته CPRP
اين الگوريتم، در طراحي، از اين نظر که به هنگام دريافت پاداش يا جريمه را بروز مي‌نمايد، شبيه الگوريتم LRP است. تفاوت اين دو در اينست که LRP به سمت عملي که اخيراً بيشتر پاداش گرفته حرکت مي‌کند، اما CPRP به سمت عملي مي‌رود که بيشترين تخمين دريافت پاداش را داشته است. در [119,120] ، ثابت گرديد که الگوريتم CPRP، است.
الگوريتم تعقيبي گسسته DPRI112
در 1990، اومن [120] نسخه گسسته الگوريتم تعقيبي را معرفي نمود. اين الگوريتم، صرف‌نظر از نگرش دراز مدت به محيط، ويژگيهاي کوتاه مدت آن را نيز در قالب پاسخ اخير محيط، مورد استفاده قرار مي‌دهد. اين الگوريتم براساس الگوي Reward-Inaction شکل گرفته و تنها تفاوت آن با نسخه پيوسته، در قانون بروز رساني احتمالات(مرحله دوم الگوريتم) است. در اينجا تغييرات در مقادير گسسته صورت مي‌گيرد.
در DPRI هنگاميکه عملي پاداش دريافت مي‌کند، احتمال تمام عملهايي که متناظر با بيشترين تخمين نيستند به اندازه کاهش مي‌يابد که و N پارامتر تجزيه مي‌باشد. براي 1 نگه‌داشتن مجموع احتمالها، احتمال عملي که تخمين آن بيشينه است به اندازه تمام اين ها افزوده مي‌گردد. هنگاميکه عمل جاري جريمه مي‌شود، هيچ‌گونه بروز رساني صورت نمي‌گيرد. اين الگوريتم بصورت فرماليته درشکل 4-7, آمده است.

پارامترها:
m
انديس مؤلفه بيشينه بردار تخمين دريافت پاداش ،

تعداد دفعاتي که عمل iام تا زمان t پاداش دريافت کرده است، با شرط

تعداد دفعاتي که عمل iام تا زمان t پاداش دريافت کرده است، با شرط
N
پارامتر تجزيه

کوتاه‌ترين گام حرکت
شكل ‏7-3) پارامترهاي الگوريتم تعقيبي گسسته DPRI

الگوريتم:
Initialize
Initialize by choosing each action a number of times.
Repeat
Step 1) At time t pick according to probability distribution. Let.
Step 2) Update according to the following equations:
Step 3) Update according to the following equations for the action chosen
End Repeat
شكل ‏7-4) الگوريتم تعقيبي گسسته DPRI
اومن[104] ثابت کرد که اين الگوريتم هميشه در محيطهاي ايستا همگرا مي‌شود و يک الگوريتم است.
الگوريتم تعقيبي پيوسته CPRI113
اين الگوريتم به عنوان تعميمي از الگوريتم تاتاچار و ساستري به الگوي Reward-Inaction، اولين بار توسط اومن[121] معرفي و همگرايي آن بررسي گرديد. اين الگوريتم بسيار شبيه الگوريتم DPRI بوده و فقط قانون بروز رساني احتمالات آن متفاوت مي‌باشد که در شکل 6-7, بصورت فرماليته بيان شده است.
پارامترها:

سرعت پارامتر يادگيري با شرط
m
انديس مؤلفه بيشينه بردار تخمين دريافت پاداش ،

بردار يکه با r مؤلفه که مؤلفه mام آن 1 است.

تعداد دفعاتي که عمل iام تا زمان t پاداش دريافت کرده است، با شرط

تعداد دفعاتي که عمل iام تا زمان t انتخاب شده است، با شرط
شكل ‏7-5) پارامترهاي الگوريتم تعقيبي پيوسته CPRI
الگوريتم:
Initialize
Initialize by choosing each action a number of times.
Repeat
Step 1) At time t pick according to probability distribution. Let.
Step 2) If is the action with the current highest reward estimate, update as
Step 3) Update according to the following equations for the action chosen
End Repeat
شكل ‏7-6) الگوريتم تعقيبي پيوسته CPRI

الگوريتم تعقيبي گسسته DPRP114
با ترکيب استرتژي گسسته‌سازي و الگوي Reward-Penalty، اومن [105] الگوريتم تعقيبي گسسته DPRP را ارائه نموده و همگرايي آن را مورد بررسي قرار داد. اين الگوريتم در نشان داده شده است.
پارامترها:
m
انديس مؤلفه بيشينه بردار تخمين دريافت پاداش ،

تعداد دفعاتي که عمل iام تا زمان t پاداش دريافت کرده است، با شرط

تعداد دفعاتي که عمل iام تا زمان t پاداش دريافت کرده است، با شرط
N
پارامتر تجزيه

کوتاه‌ترين گام حرکت
الگوريتم:
Initialize
Initialize by choosing each action a number of times.
Repeat
Step 1) At time t pick according to probability distribution. Let.
Step 2) Update according to the following equations:
Step 3) Update according to the following equations for the action chosen
End Repeat
شكل ‏7-7) الگوريتم تعقيبي گسسته DPRP
7-5- آتوماتاي يادگير سلولي115 (CLA)
آتوماتاي يادگير سلولي، يک مدل رياضي براي سيستمهايي با اجزاي ساده‌ است، بطوريکه رفتار هر جزء بر اساس رفتار همسايگانش و نيز تجربيات گذشته‌اش تعيين و اصلاح مي‌شود. اجزاء ساده تشکيل دهنده اين مدل، از طريق کنش و واکنش با يکديگر رفتار پيچيده‌اي از خود نشان مي‌دهند، بنابراين از آن مي‌توان در مدل‌سازي بسياري از مسائل بهره برد. اين مدل اولين بار در ‎[27] معرفي شد و سپس فعاليتهايي جهت بررسي کاربردهاي گوناگون آن ‎[28] صورت گرفت. سرانجام در ‎[33] بيگي و ميبدي، اين مدل را بصورت رياضي مورد تحليل قرار داده و رفتار همگرايي آن را مطالعه نمودند که نتيجه قضاياي مهمي در باب قابليت همگرايي اين مدل به پاسخ بهينه محلي خود، مي‌باشد.
هر اتوماتاي يادگير سلولي، از يک اتوماتاي سلولي تشکيل شده است که هر سلول آن به يک يا چند اتوماتاي يادگير مجهز مي‌باشد که حالت اين سلول را مشخص مي‌سازد. مانند اتوماتاي سلولي، قانون محلي در محيط حاکم است و اين قانون تعيين مي‌کند که آيا عمل انتخاب شده توسط يک اتوماتا در سلول بايد پاداش داده شود ويا اينکه جريمه شود. دادن پاداش و يا جريمه باعث بروز درآورده شدن ساختار اتوماتاي يادگير سلولي بمنظور نيل به يک هدف مشخص مي‌گردد. ايده اصلي اتوماتاي يادگير سلولي، که زير مجموعه اي از اتوماتاي يادگير سلولي تصادفي محسوب مي‌شود، استفاده از اتوماتاي يادگير براي محاسبه احتمال انتقال حالت در اتوماتاي سلولي تصادفي مي‌باشد. اتوماتاي يادگير سلولي را مي‌توان به دو دسته غيرهمگام116 و همگام117 تقسيم کرد. در مدل عمگام، تمام سلولها با يک ساعت سراسري هماهنگ شده و به طور همزمان اجرا مي‌شوند.
تعريف ‏7-2- اتوماتاي يادگير سلولي: اتوماتاي يادگير سلولي d-بعدي يک چندتايي است به طوريکه:
– يک شبکه از d-تايي‌هاي مرتب از اعداد صحيح مي‌باشد. اين شبکه مي‌تواند يک شبکه متناهي، نيمه متناهي يا متناهي باشد.
– يک مجموعه متناهي از حالتها مي‌باشد.
– A، يک مجموعه از اتوماتاهاي يادگير(LA) است که هر اتوماتاي يادگير به يک سلول نسبت داده مي‌شود.
– يک زير مجموعه متناهي از مي‌باشد که بردار همسايگي خوانده مي‌شود.
– قانون محلي CLA مي‌باشد، بطوريکه مجموعه مقاديري است که مي‌تواند به عنوان سيگنال تقويتي پذيرفته شود.
7-6- آتوماتاي يادگير سلولي باز118(OCLA)
آتوماتاي يادگير سلولي که در بخش قبل معرفي گرديد، بسته مي‌باشد چراکه تعامل ميان CLA و محيط خارجي را مورد توجه قرار نمي‌دهد. در حقيقت در اين مدل، امتياز اتوماتاهاي يادگير فقط براساس وضعيت همسايه‌هاي آنها تعيين مي‌گردد. اما در بسياري از کاربردها به شرايطي برمي‌خوريم که علاوه بر همسايه‌ها، يک محيط خارجي نيز در تعيين امتياز اتوماتاهاي يادگير تأثيرگذار است. براي رفع اين محدوديت موجود در CLA و توسعه آن به کاربردهاي گسترده‌تر، اولين بار در[122] توسط بيگي و ميبدي ايده اتوماتاي يادگير سلولي باز ارائه گرديد. در اين مدل، علاوه بر محيط محلي119 يک اتوماتاي يادگير، دو محيط ديگر يعني محيط سراسري120 و محيط گروهي121 نيز براي آن در نظر گرفته شده است. هر CLA داراي يک محيط سراسري است که تمامي اتوماتاهاي يادگير آن را تحت تأثير قرار مي‌دهد و يک محيط گروهي براي هر دسته از اتوماتاهاي يادگير مي‌باشد.شکل 7-9, چگونگي اتصال يک سلول(اتوماتاي يادگير) نوعي از OCLA را با انواع محيطهاي آن نشان مي‌دهد.

شكل ‏7-8) اتصال يک سلول نوعي با انواع محيطها و OCLA
عملکرد OCLA با پيشرفت الگوريتم، بدين ترتيب مي‌باشد. در تکرار kام، هر اتوماتاي يادگير يکي از عملهايش را انتخاب مي‌کند. فرض کنيد ?i عمل انتخابي توسط اتوماتاي يادگير Ai باشد. عملهاي هريک از اتوماتاهاي يادگير به محيطهاي محلي، گروهي و سراسري آنها اعمال مي‌گردد. سپس تمامي اتوماتاهاي يادگير، سيگنال امتياز خود را دريافت مي‌کنند که اين سيگنال ترکيبي است از پاسخ‌هاي محيطهاي سراسري، گروهي و محلي. اين پاسخ‌هاي بوسيله قانون محلي با يکديگر ترکيب مي‌گردند. سرانجام، تمامي اتوماتاهاي يادگير بردارهاي احتمال عمل خود را براساس سيگنال دريافتي بروز مي‌نمايند.
همانگونه که بيگي و ميبدي در [122]ثابت نموده‌اند، اين مدل همانند CLA ساده، براي قوانين جابجايي‌پذير، مي‌تواند به نقاط بهينه محلي همگرا شود.
7-7- آتوماتاي يادگير سلولي ناهمگام122 (ACLA)
اتوماتاهاي يادگير سلولي که تا کنون مورد بررسي و