شبکه های پتری تصادفی وسیله‌ای برای مطالعه سیستم‌ها می‌باشند. تئوری شبکه پتری تصادفی اجازه میدهد که یک سیستم بتواند بوسیله آن بصورت یک مدل ریاضی مدل شود. از رفتار پویا و ساختار سیستم مدل شده توسط آنالیز شبکه پتری تصادفی، اطلاعات بسیار مفیدی اتخاذ میگردد که این اطلاعات می‌تواند جهت ارزشیابی، حدسهای برای ایجاد، بهبود یا تغییرات در سیستم استفاده شود. شبکههای پتری تصادفی برای آنالیز سیستمهایی گسترده کاربرد بسزایی دارند. یکی از مشکلات شبکه پتری تصادفی عدم تطبیق پذیری آنها میباشد و بهمین دلیل در شبکههای پتری تصادفی امکان دسترسی به اطلاعات قبلی وجود ندارد. اگر در هر زمان بیش از یک گذار فعال باشد، هر کدام میتوانند به‌عنوان شلیک بعدی محسوب شوند. این ویژگی شبکه پتری حقیقتی را تداعی میکند که چنانچه چندین واقعه همزمان اتفاق افتد و وقوع رویدادها یکسان نباشد، هریک از رویدادها می‌تواند رخ دهد و وقوع رویدادها در طول زمان، تغییر نمیکند و این برخلاف دنیای واقعی و پویا میباشد، و شبیه سازی مشابه اجرای برنامه اصلی است، هدف آنست که از مدل شبیه سازیشده برای بررسی عملکرد سیستم استفاده شود و بدینوسیله مشکلات و نقاط ضعف مدل مشخص میگردد ولی ابزار شبکه پتری تصادفی به تنهایی نمیتواند در جهت بهبود و رفع مشکلات کاری انجام دهد و وضعیت بهینه بعدی را نمیتوان پیشگویی نمود. در این پایان‌نامه، هدف ما ایجاد یک شبکه پتری تصادفی تطبیقی مبتنی بر اتوماتای یادگیر و کاربرد آن در تخصیص منابع در گرید های محاسباتی و اقتصادی می باشد. شبکه پتری تصادفی تطبیقی از طریق اطلاعات بدست آمده از حالات قبلی سیستم و واکنشهای محیط پویا، حالت بهینه بعدی را پیشگویی نموده و وضعیت جاری سیستم را بروز و احتمال وقوع رویدادها را در طول زمان تغییر میدهد و باعث میشود رویدادها بر اساس احتمال وقوعشان فعال شوند. بروز شدن وضعیتهای سیستم بر اساس واکنش محیط پویا کمک شایانی در یادگیری و آموزش شبکههای پتری میکند در اینجا، تطبیقی بودن شبکه های پتری در کاربردهای مختلف مورد بررسی قرار گرفته اند. در این پروژه از ابزار شبیهسازی SPNP برای شبیهسازی شبکه پتری تصادفی استفاده میگردد. در ادامه، کاربرد مدل تطبیقی پیشنهاد شده در قسمت اول، در گرید محاسباتی مورد مطالعه و بررسی قرار میگیرد. در این بررسی ایده ای اکتشافی با توجه به الگوریتم های زمانبندی در گریدهای محاسباتی پیشنهاد می شود و نتایج آن با روشهای Min.min و Max.min مقایسه شده است. در قسمت دوم تخصیص منابع در گرید اقتصادی با توجه به الگوریتم هوشند اتوماتای یادگیر در حالتهای مختلف مورد بررسی قرار می گیرد. برای این منظور در گرید اقتصادی از مدل تطبیقی ارائه شده برای تخصیص بهینه منابع در گرید با توجه به معیار زمان استفاده میگردد. در اینجا با در نظر گرفتن مستقل بودن کارهای تخصیص یافته به منابع و تخصیص یکباره و یک مرحله ای ایده ای بر اساس اتوماتای یادگیر ارائه شده و با ایده های قبلی که توسط آقایان بویا و مهدوی فر ارائه شده اند بررسی شده است. الگوریتم پیشنهادی ALATO که براساس اتوماتای یادگیر ارائه شده است نسبت به الگوریتم های مشابه مدت زمان کمتری را صرف جستجو و تخصیص منابع در گرید اقتصادی می کند.
کلمات کلیدی: شبکه پتری تصادفی، تطبیقی بودن، گرید محاسباتی، زمانبندی، اتوماتای یادگیر، بهینه‌سازی زمان
فهرست مطالب
فصل دوم: کارهای پیشین... 6
2-2- شبکههای پتری تصادفی... 6
2-2-1- تکنیکهای تحلیل در شبکه پتری تصادفی.. 10
2-2-1-1-1- محدودیتهای درخت دسترسی.. 13
2-2-1-2- معادلات ماتریس.... 13
2-2-2- بهبود کارایی در شبکه پتری تصادفی.. 14
2-2-3- بهبود کارائی در شبکههای پتری تصادفی عمومی.. 16
2-2-3-1- ساختار شبکه پتری تصادفی عمومی.. 17
2-2-3-2- توزیع عمومی تعداد دفعات فعال شدن.. 21
2-2-3-3- روابط با مدل‌های دیگر. 22
2-2-3-4- تجزیه ساختاری شبکههای پتری تصادفی.. 24
2-2-4- خلاصه و نتیجه گیری.. 25
2-3-2- تاریخچه‌ی اتوماتای یادگیر. 28
2-3-3- اتوماتای یادگیر تصادفی (SLA). 29
2-3-4- الگوریتم‌های یادگیری.. 32
2-3-4-1- الگوریتم‌های یادگیری استاندارد. 32
2-3-4-2- الگوریتم‌های یادگیری مدل S. 34
2-3-4-2-1- الگوریتم ............... 35
2-3-4-2-2- الگوریتم ................. 35
2-3-4-2-3- الگوریتم ................. 36
2-3-5- الگوریتم‌های یادگیری با ساختار ثابت... 36
2-3-5-1- اتوماتای دو حالته ......... 36
2-3-5-2- توسعه‌های اتوماتای دوحالته .......... 38
2-3-5-3- اتوماتای حافظه‌دار با دو عمل ............ 38
2-3-5-4- اتوماتای کرینسکی .......... 40
2-3-5-5- اتوماتای کرایلوف ........... 41
2-3-5-6- اتوماتای ........... 41
2-3-5-7- اتوماتای مهاجرت اشیاء. 41
2-3-7- خلاصه و نتیجه‌گیری.. 43
2-4-2- طبقه‌بندی سیستم‌های گرید.. 46
2-4-3- توانمندی‌های گرید محاسباتی.. 47
2-4-3-1- بهره برداری از منابع بدون استفاده. 48
2-4-3-2- موازیسازی پردازندهها 49
2-4-3-3- برنامه‌های کاربردی.. 50
2-4-3-4- منابع مجازی و سازمانهای مجازی برای ایجاد همکاری.. 50
2-4-3-5- دسترسی به منابع اضافی.. 51
2-4-4-1- تعاریف و نیازمندی‌ها 52
2-4-4-2- مدل انتزاعی سیستم مدیریت منبع.. 53
2-4-5- خلاصه و نتیجه‌گیری.. 60
فصل سوم: شبکه پتری تصادفی تطابقی... 62
3-2- کارهای انجام شده در یادگیری شبکه پتری.. 63
فصل چهارم: کاربرد شبکه پتری تصادفی در گرید محاسباتی... 84
4-2- مرور اجمالی بر گرید محاسباتی.. 84
4-3- کارهای مرتبط در زمانبندی گرید محاسباتی به کمک شبکه پتری.. 85
4-5- شبیه سازی ایده پیشنهادی.. 91
4-6- خلاصه و نتیجه گیری و کارهای آینده. 97
فصل پنجم: پیاده سازی شبکه پتری تصادفی تطابقی در گرید اقتصادی... 99
5-1- مروری بر الگوریتم های موجود و الگوریتم پیشنهادی.. 99
5-1-1- مراحل مشترک الگوریتم‌ها 100
5-2-2- الگوریتم BTO و الگوریتم ABTO.. 100
5-2- شبیه سازی الگوریتم ها 116
5-2-2- مدل شبکه پتری تصادفی تطابقی در محیط گرید.. 117
5-2-3- پیاده سازی الگوریتم ها 121
5-2-8-1- بهینه سازی زمان در یک هزینه و زمان معین(حالت اول). 128
5-2-8-2- بهینه سازی زمان در زمان معین با بودجه‌های مختلف (حالت دوم). 133
5-2-8-3- بهینه‌سازی زمان در ناهمگونی‌های مختلف(حالت سوم). 139
فصل ششم: نتیجه‌گیری و پیشنهادها. 146
7-2- مروری بر نرم افزار SPNP. 155
7-2-1- راه اندازی در ویندوز XP. 155
7-2-2- فایلهای خروجی در SPNP. 155
7-3-1-1- قسمت اصلی کد الگوریتم Min.min. 164
7-3-1-2- قسمت اصلی کدMax.Min و الگوریتم HSPN.. 166
7-4- کد الگوریتم دوم و شبیه سازی آن در SPNP. 167
7-4-1- کد نزولی کردن کارها و کد تخصیص کارها در میان افزار. 167
7-4-2- کد الگوریتم های گرید اقتصادی در CSPL.. 170
7-4-3- الگوریتم زمانبندی و تخصیص کارها به منابع مختلف... 173
یک مدل شبکه پتری تصادفی تطبیقی مبتنی بر اتوماتاهای یادگیری و کاربردهای آن درتخصیص منابع در شبکه های گرید