بخشی از پاورپوینت
اسلاید 1 :
به نام خدا
حل مسئله ی کوتاه ترین مسیر در گره های تصادفی در صورت همبستگی بین هزینه یالها با استفاده از بازی بین اتوماتای یادگیر
اسلاید 2 :
فهرست :
مقدمه
تعریف مسئله
چند اصطلاح که بهتر است با آنها آشنا باشید
الگوریتم پیشنهادی
نتایج شبیه سازی ها
مراجع
اسلاید 3 :
برای حل مساله کوتاهترین مسیر در گرافهای قطعی ، الگوریتمهای متفاوتی نظیر دایجسترا و فلویدوارشال وجود دارد. اما این الگوریتمها در صورتی که وزن یالها به صورت پویا تغییر کنند ، قادر به یافتن راه حل بهینه نمی باشند.بدین جهت الگوریتم هایی برای مسائل کوتاهترین مسیر در گرافهای پویا ، مطرح شده اند این الگوریتم ها نیز برای گرافهای تصادفی(که وزن یال های آن متغیر های تصادفی است) از کارایی بالایی برخوردار نیستند.
مقدمه :
اسلاید 4 :
1_الگوریتم میبدی_بیگی: برای حل مسئله ی کوتاه ترین مسیر بین دو گره در گرافهای تصادفی.
2_میسرا_اومن: برای یافتن کوتاه ترین مسیر بین یک مبدا و دیگر گره ها در یک گراف تصادفی.
3_میسرا_اومن: برای یافتن تمام جفت گره های گراف دریک گراف تصادفی.
4_یک الگوریتم مبتنی بر بازی بین اتوماتای یادگیر برای یافتن کوتاه ترین مسیر بین یک مبدا و دیگر گره ها در یک گراف تصادفی.
اقدامات انجام شده :
اسلاید 5 :
تعریف مسئله :
فرض: یک شبکه با n گره و یک گره مقصد ؛ یال ها در دو حالت دارای ازدحام و بدون ازدحام قراردارند.
هدف: یافتن استراتژی بهینه (یال بهینه) برای رسیدن به گره مقصد.
نحوه همبستگی بین یال ها: توسط تابع احتمال شرطی.
اسلاید 6 :
ابتدا باید وضعیت یال پیموده شده, مشخص شود؛ سپس متوسط زمانی در هر یال محاسبه میشود .برای هریال آستانه ازدحام مشخص شده است که متوسط زمانی سفر در هریال با آن آستانه مقایسه میشود تا در هر حالت مشخص شود که سفر دارای ازدحام است یا بدون ازدحام. برای هریک از انواع سفر ها فرمولی ارائه شده است.
تعریف مسئله :
اسلاید 7 :
چند اصطلاح که بهتر است با آنها آشنا باشید :
1- اتوماتای یادگیر:
یک مدل انتزاعی است که تعداد محدودی عمل را میتواند انجام دهد. هر عمل انتخاب شده توسط محیطی احتمالی ارزیابی شده و پاسخی به اتوماتای یادگیر داده می شود. اتوماتای یادگیر از این پاسخ استفاده نموده وعمل خود را برای مرحله بعد انتخاب میکند.
اسلاید 9 :
چند اصطلاح که بهتر است با آنها آشنا باشید :
2- اتوماتای یادگیر توزیع شده (DLA):
اتوماتای یادگیر توزیع شده شبکه ای از اتوماتای یادگیر است که برای حل یک مساله با یکدیگر همکاری می نمایند. انتخاب یک اقدام توسط یک اتوماتا در شبکه، اتوماتای متناظر با این اقدام را فعال می سازد. در هر زمان فقط یک اتوماتا در شبکه فعال می باشد.
اسلاید 11 :
3- بازی بین اتوماتاهای یادگیر:
در بازی بین اتوماتاهای یادگیر شبکه ای از اتوماتاهای یادگیر برای حل مساله همکاری مینمایند. در این شبکه در هر مرحله تمامی اتوماتاهای یادگیر فعالی شده و سپس هر یک از انها یکی از اعمال خود را انتخاب مینماید. اعمال انتخاب شده در محیط اجرا و با توجه به نتیجه اعمال به انها پاداش و یا جریمه داده میشود. یالهای ورودی هر گره در این شبکه به عنوان عملهای اتوماتای یادگیر متناظر با ان گره درنظر گرفته شده اند.
اسلاید 13 :
الگوریتم پیشنهادی :
در الگوریتم پیشنهادی از بازی بین اتوماتاهای یادگیر برای پیداکردن کوتاه ترین مسیر بین یک گره و دیگر گره های گراف استفاده میشود.
اسلاید 14 :
الگوریتم پیشنهادی :
برای حل این مسئله هر گره شبکه به یک گروه متشکل از ۴ اتوماتای یادگیر(QLA ) که با محیط تصادفی در ارتباط میباشند مجهز می باشد. در هر زمان با توجه به شرایط محیط فقط دو اتوماتای یادگیر از ۴ اتوماتای یادگیر در هر گره فعال خواهند بود: ۲ اتوماتای یادگیر برای زمانیکه محیط در حالت ازدحام باشد و ۲ اتوماتای دیگر برای زمانی که که محیط در حالت بدون ازدحام باشد. یکی از ۲ اتوماتای فعال در هر زمان وظیفه یادگیری همبستگی را به عهده دارند که اتوماتای یادگیرنده همبستگی نامیده می شوند و اتوماتای یادگیر فعال دیگر وظیفه یادگیری یال بهینه را به عهده دارد که اتوماتای یادگیرنده یال بهینه نامیده می شوند.
مرحله 1 _معرفی و انتخاب اتوماتاها :
اسلاید 15 :
تمام QLA ها در شبکه فعال میشوند و با توجه به حالت گره متناظر اتوماتاهای مربوط به آن فعال شده و یکی از عمل های خود را انتخاب میکند. به عبارتی در هر QLA دو اتوماتا فعال میشود. اتاماتای همبستگی حالت مناسب را انتخاب میکند و اتاماتای یادگیرنده ی یال بهینه یک یال از یال های خروجی گره متناظر با QLA را انتخاب میکند.
انتخاب اتاماتا :
مرحله 1 _معرفی و انتخاب اتوماتاها :
اسلاید 17 :
الگوریتم پیشنهادی :
یال انتخاب شده با آستانه ی ازدحام مقایسه میشود تا در حالت ازدحام بودن یا نبودن یال مشخص شود.
با توجه به حالت یال انتخاب شده به اتوماتای یادگیرنده ی همبستگی پاداش یا جریمه تعلق میگیرد.
پاداش : چنانچه عمل ازدحام توسط اتوماتای یادگیر انتخاب شده باشد ویال نیز درحالت ازدحام باشد.(وزن یال بیشتر از آستانه ازدحام) همچنین اگر عمل بدون ازدحام توسط اتوماتای یادگیر انتخاب شده باشد ویال نیز درحالت بدون ازدحام باشد.
در غیر اینصورت جریمه داده میشود.
مرحله 2 _پاداش و جریمه ی اتوماتای یادگیرنده همبستگی
اسلاید 18 :
الگوریتم پیشنهادی :
باتوجه به حالت گره رابطه ی مناسب انتخاب میشود. سپس این مقدار با مقدار آستانه مقایسه میشود .
پاداش : چنانچه مقدار محاسبه شده کمتر یا برابر با آستانه پویا باشد , به عمل انتخاب شده توسط اتاماتای یادگیر پاداش داده میشود .
در غیر اینصورت جریمه داده میشود.
سپس مقدار آستانه به روز رسانی میشود.
مرحله 3 _پاداش و جریمه ی اتوماتای یادگیرنده یال بهینه:
اسلاید 19 :
الگوریتم پیشنهادی :
اگر شرط خاتمه الگوریتم برقرار باشد , اجرای الگوریتم متوقف میشود ؛ در غیر اینصورت کنترل به مرحله ی 2 انتقال پیدا میکند .
شبه کد الگوریتم
مرحله 4 _خاتمه الگوریتم:
اسلاید 20 :
نتایج شبیه سازی ها :
در این مقاله برای اولین بار الگوریتمی برای حل مسئله ی کوتاهترین مسیر گرافهای تصادفی پیشنهاد گردید. الگوریتم پیشنهادی سعی میکند با حداقل تعداد نمونه گیری مسیر بهینه را در هرگره با توجه به وضعیت یال مشخص کند.
نتایج آزمایش ها کارایی الگوریتم پیشنهادی را نشان می دهد.
