بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
جایابی ماشین مجازی با استفاده از اتوماتای یادگیر برای کاهش انرژی
چکیده
امروزه رایانش ابری به عنوان یکی از چالش برانگیزترین موضوعات تحقیق در فناوری اطلاعات مطرح است. مراکز داده، از جمله مخازنی هستند که با قدرت پردازشی خود میتوانند نیازهای رایانشی بسیاری از کاربران را برآورده سازند. یکی از مشکلات و چالشهای موجود در خصوص این مراکز داده، مصرف زیاد انرژی آنها است. مصرف زیاد انرژی مراکز داده، باعث افزایش هزینه برای ارائه دهندگان سرویسهای رایانش ابری و همچنین انتشار گازهای CO2 میشود. بنابراین ارائه یک روش موثر برای کاهش مصرف انرژی توسط مراکز، به شدت توسط محققان در نظر گرفته شده است. در سالهای اخیر، تلاشهای زیادی برای کاهش توان مصرفی مراکز داده ابری صورت گرفته است و رویکردهای زیادی در جهت کاهش توان مصرفی از قبیل رویکردهای سخت افزاری، رویکرد-های نرم افزاری و رویکردهای با استفاده از فناوری مجازیسازی ارائه شده است. جایابی ماشین مجازی، فرآیند انتخاب میزبان مناسب برای ماشین مجازی است. هدف جایابی میتواند به حداکثر رساندن توان استفاده از منابع موجود و یا صرفهجویی در انرژی به دلیل خاموش کردن برخی از سرورهای فیزیکی باشد. در این مقاله، یک روش جدید با استفاده از از اتوماتای یادگیر برای حل مصالحه بین کاهش مصرف انرژی و کاهش تخطی از توافقات سطح سرویس در جایابی پویای ماشینهای مجازی ارائه دادهایم.
واژگان کلیدی: جایابی ماشین مجازی،تلفیق ماشین مجازی،اتوماتای یادگیر
1
-1 مقدمه
یکی از مولفههای اصلی در رایانش ابری، مراکز داده1 است. در سالهای اخیر توسعه دهندگان خدمات ITC مانند IBM، مایکروسافت، گوگل و سایر سازمانهای مشابه، برای افزایش کارایی در محاسبات، مراکز داده را توسعه دادهاند. از طرفی تمرکز توسعه دهندگان و طراحان مراکز داده بر روی کارایی موجب گردید، که مصرف انرژی در این مراکز نادیده گرفته شود.
هزینهای مصرف انرژی مراکز داده در سال 2006 برابر 4,5 بیلیون دلار بوده است که در[1] پیشبینی کرد با این روند افزایش در سال 2011 این هزینه به دو برابر خواهد رسید. همچنین مراکز داده %1,5 از کل انرژی ایالات متحده آمریکا را مصرف میکنند.[2] مراکز داده فیسبوک، گوگل و یوتیوب به ترتیب %10,52 ، %7,74 و %3,27 کل انرژی مصرفی بخش IT را مصرف میکنند.[3] مصرف انرژی مراکز داده معادل مصرف 25000 خانوار است.[4] صرف انرژی بالا علاوه بر هزینههای عملیاتی، منجر به افزایش درجه حرارت خواهد شد و نیز قابلیت اطمینان و طول عمر منابع سختافزاری را کاهش خواهد داد. همچنین به دلیل تولید قابل ملاحظهای دی اکسید کربن (CO2) و انتشار گازهای گلخانهای جنبههای زیست محیطی را نیز مورد توجه قرار میدهد.[5] از این رو استفاده از تکنیکهای مدیریت توان مصرفی ضروری به نظر میرسد.[6] خوشبختانه تلاشهای در زمینه کاهش توان مصرفی در بخشهای، توان مصرفی پردازنده[7]، مدیریت توان مصرفی دستگاههای ذخیرهسازی و مدیریت توان مصرفی شبکه انجام گرفته است.[8]
انرژی مصرف شده توسط یک سرور در یک مرکز دادهها شامل منابع مختلفی است. هر سرور دارای ظرفیت منابعی مانند CPU، RAM و تجهیزات شبکه و منابع ذخیرهسازی است. همانطور که در شکل (1) مشاهده میشود در مقایسه با دیگر منابع سیستم، CPU انرژی بیشتری را نسبت به دیگر منابع مصرف میکند.[9]
شکل (1) میزان توان مصرفی منابع مختلف یک سرور[9]
مهمترین عامل در هدر رفتن انرژی در مراکز داده ابری، سرورهای بیکار هستند، که بهرهوری 2پایینی از مصرف منابع سختافزاری دارند(در ادامه این پایاننامه مفاهیم سرور، ماشین فیزیکی و میزبان یکسان در نظر گرفته میشود). زیرا سرورها دارای تناسب انرژی نیستند. به عبارت دیگر، سرورها در زمانهای که دارای بار کاری سبک یا بیکار هستند، انرژی زیادی را نسبت به زمانی که در حداکثر بهرهوری از منابع خود هستند، مصرف میکنند.[10] برای مثال، پژوهشگران شرکت گوگل در طی شش ماه 5000 ماشین فیزیکی گوگل را مورد مطالعه قرار دادند و متوجه شدند، بیشتر زمانها ماشینهای فیزیکی دارای بهرهوری بین 10 تا 40 درصد بودهاند و به ندرت بهرهوری آنها به %100 نزدیک شده است. نتایج این گزارش در شکل((2 نشان داده شده است.
شکل((2 گزارش بهرهوری از یک نمونه 5000 تایی سرورهای گوگل در طی مدت شش ماه [11]
یکی از راههای کاهش مصرف انرژی توسط مراکز داده رویکرد مجازیسازی3 است. تکنیکهای مجازیسازی این امکان را میدهند که چندین ماشین مجازی4 بر روی یک ماشین فیزیکی5 یا سرور قرار گیرند13]،.[12 لذا مقدار سختافزار در حال کار را کاهش و بهرهوری منابع را بهبود بخشد. از دیگر مزایای مجازیسازی میتوان به انتقال VMها به صورت نسبتاً آسان از یک ماشین مجازی به ماشین مجازی دیگر تحت تکنیکی به نام مهاجرت زنده6 ماشین مجازی اشاره کرد. مهاجرت زنده ماشین مجازی انتقال VMهای در حال اجرا، از یکPM به یک PM دیگر است به طوری که وقفهای در اجرای VMها رخ ندهد.[14] هر PM با توجه به درخواست و نیاز VM بخشی از منابع در دسترس ( مانند CPU، RAM، پهنای باند و..) را برای اجرای VM به آن اختصاص میدهد. از این رو ممکن است بر روی یک سرور تعداد محدودی VM قرار گیرند. درنتیجه برخی PMها در حالت بهرهوری پایینی از مصرف منابع خود قرار میگیرد. روش جدید توسعه داده شده، برای رسیدگی به این مشکل، مهاجرت است. با استفاده از مهاجرت، تمام VMهای که بر روی PMهایی که دارای بهرهوری پایین هستند، به PM دیگر منتقل میشوند و PMهای بیکار به حالت خواب یا خاموش تغییر حالت می-دهند. از این رو تعداد PMهای فعال را کم میشوند. که به این روند "تلفیق ماشین فیزیکی"7 نیز گویند. سوالی که دراینجا وجود دارد این است که ماشین مجازی به کدام ماشین فیزیکی انتقال داده شود؟ که این مورد تحت عنوان" جایابی ماشین مجازی8 "شناخته میشود. در واقع جایابی ماشین مجازی پیدا کردن ماشین فیزیکی مناسب برای ماشین مجازی است.[15]
جایابی ماشینهای مجازی در دو زمان مختلف انجام میگردد. در حالت اول زمانی است که یک VM جدید ایجاد میشود، که باید این ماشین مجازی ایجادشده به یک میزبانی که قادر است منابع مورد نیاز آن را تامین کند، نگاشت یابد و یا به عبارتی تخصیص داده شود؛ که به آن جایابی اولیه گویند. دوم زمانی است که با توجه به شرایط و عملکرد خاص لازم است که ماشینهای مجازی به یک ماشین فیزیکی دیگر مهاجرت داده شود. در این هنگام باید میزبانی مقصد که قرار است این ماشین مجازی را بپذیرد، مشخص گردد. در واقع جایابی ماشین مجازی فرآیند یافتن میزبان مناسب برای ماشین مجازی است. به عبارتی دیگر جایابی ماشین مجازی نگاشت ماشینهای مجازی به ماشین فیزیکی مناسب است. [15 ]
در محیطی که در آن تعداد کمی از ماشینهای مجازی و فیزیکی وجود دارد، امکانپذیر است که برای مدیریت ماشینهای مجازی از یک اپراتور استفاده شود. با افزایش تعداد ماشینهای مجازی و فیزیکی وضعیت غیرقابل کنترل میشود و خودکار سازی عملیاتها لازم به نظر میرسد. حتی در یک محاسبه خودکارجایابی، تعداد نگاشت ممکن برای یک مجموعه از ماشینهای مجازی و فیزیکی مورد ارزیابی قرارمیگیرد. رابطه (1) تعداد نگاشتهای ممکن را نشان میدهد.[16]
(1) (تعداد ماشینهای مجازی) (تعداد میزبان فیزیکی)= تعداد نگاشتها چنین فضای راه حل بزرگ باعث میشود که تقریبا برای هر الگوریتم نگاشت ماشین مجازی به ماشین فیزیکی، جایابی دقیق آن عملا در زمانهای قابل قبول غیرممکن
شود. از این رو، فناوری اکتشافی جایابی هوشمند مورد نیاز است تا جستجو ی یک راه حل را محدود کند و طرح نزدیک به جایابی بهینه را بدست بیاورد.[17] مسئله جایابی ماشینهای مجازی در تمامی الگوریتمهای ارائه شده، به طور خلاصه این گونه بیان میشود:
· تعداد M ماشینهای فیزیکی در دسترس وجود دارد. ظرفیت منابع آنها شامل CPU ، ابعاد پهنای باند شبکه و ... است.
· تعداد N ماشین مجازی ایجاد گردیده است تا سرویسهایی کاربران را پاسخ دهد. نیازهای این ماشینهای مجازی از طریق ابعاد حافظه، CPU و پهنای باند شبکه و ... که در دسترس باشد، پاسخ داده میشود.
· باید یک نگاشت بین VMها و PMها پیدا کنیم، که نیاز منابع هر VM با PM مربوطه برآورده شود، در حالی که تعداد ماشینهای فیزیکی فعال به حداقل برسد.
در صورت پیدا کردن چنین نگاشتی، باید مراقبت باشیم که مجموع نیاز منابع VMهای جایابی شده در PM، از ظرفیت کل ماشین فیزیکی تجاوز نکند. زیرا در این صورت باعث کاهش کیفیت سرویس میگردد، که نتیجه آن تخطی از توافقات سطح سرویس میباشد. در صورت بروز این مشکل، با استفاده از مهاجرت ماشین مجازی آن را رفع میکنند. در ادامه مقاله در بخش 2 با کارهای مربوطه و در بخش 3 با روش پیشنهادی آشنا می شویم
3
-2 کارهای مربوطه
بـرای حــل مســئله جایــابی ماشــین هــای مجــازی تحقیقــات متنــوعی بــا اســتفاده از الگــوریتم هــای اکتشــافی (First Fit(FF), Best Fit(BF),..) و بــر اســاس برنامه نویسی محدودیت، برنامه نویسی عدد تصادفی، الگوریتمهای تکاملی و ... انجام شده است.
در [18] با استفاده از الگوریتم حریصانه BF9 و یک خوشه بندی10 سلسله مراتبی طی دو مرحله به جایابی ماشینهای مجازی پرداخته و در فاز اول ماشینهای مجازی با ترافیک بالا را در ماشین فیزیکی یکسان قرار میدهد. در مرحله بعدی بر اساس خوشه بندی منابع، عمل جایابی ماشین مجازی را انجام میدهد. آنها برشهای کمینه درخت باینری را برای بهینه کردن موضوعات شبکه استفاده میکنند. هدف آنها کاهش تعداد گرههای فعال و کم کردن مصرف انرژی کلی بود.
در [19] ، برای جایابی ماشین مجازی از BFD استفاده میکند و هدف آنها علاوه بر کاهش انرژی، کاهش ترافیک شبکه نیز میباشد. آنها با مدل کردن ارتباط بین ماشینهای مجازی و وزن دهی به این ارتباطات، ماشینهای مجازی و وزنهای آنها را به صورت گراف در آورده و با یک الگوریتم بازگشتی این گراف وزن دار را با توجه به وزنهای یالهای آن به یک مدل سلسله مراتبی در آورده و برای جایابی ماشین مجازی ترافیک شبکه را مد نظر قرار میدهد. برای مهاجرت ماشین مجازی در صورت پایین بودن بهرهوری سرور فیزیکی را مد نظر قرار داده و مهاجرت را بدون کاهش کارایی در نظر میگیرد.
در [20] بلاگلازوف و همکارانش، برای حل مسئله انرژی از تکنیک تلفیق ماشین مجازی استفاده کردند. به منظور حل مصالحه بین کاهش انرژی و کاهش تخطی از SLA را با استفاده از حد آستانه بالا وحد آستانه پایین ماشینهای میزبان دارای بار اضافه و ماشینهای دارای کسر بار را تشخیص میدهد. در صورتی که میزبانی دارای بهره-وری پایین تر از حد آستانه داشته باشد باید ماشینهای مجازی آن به یک میزبان دیگر انتقال داده شوند. سپس میزبان دارای بهرهوری صفر به حالت خاموش در آید. آنها از روش BFD برای حل مسئله جایابی استفاده می کردند و الگوریتم انها به MBFD معروف اشت .برای مراحل تلفیق ماشین مجازی از سیاستهای مختلف برای تشخیص میزبانهای دارای سربار اضافی و سیاستهای انتخاب ماشین مجازی متفاوتی را برای کار خود در نظر گرفتند و انها را با هم مقایسه کردند. نتایج بدست آمده از روش آنها نشان داد که سیاست LRMMT11 بهترین نتیجه را از نظر انرژی دارا است. همچنین پارامتری دیگری را که به صورت ضرب مقدار توان مصرفی و درصد تخطی از توافقات سطح سرویس است را برای مقایسه سیاستها در نظر گرفتند.
در [21] ، ماشین مجازی انتخاب میشود که کمترین مقدار ضرب نقطه ای دو بردار منابع و ظرفیت را دارد. برای رسیدن به بهرهوری مناسب لازم است که ماشین مجازی که مقدار CPU بیشتر و حافظه کمتر را نیاز دارد، بر روی ماشین فیزیکی که کمترین مقدار CPU و بیشترین مقدار حافظه را دارد قرار داده شود. اشکال این روش آن است که به دلیل در نظر نگرفتن طول بردارها ممکن است انتخاب اشتباهی را انجام دهد. روش ارائه شده آنها در بخش بعدی بیشتر شرح داده میشود.
در [22]، محققان به صورت ضرب نقطه ای بردار منابع و ظرفیت موجود میزبان و با قرار دادن یک حد آستانه برای حل مشکل مهاجرت زنده، پرداختهاند. در مدل ارائه شده یک Event Evoker وجود دارد که بازخوردی از اطلاعات شامل شروع VM و اندازه VM و مهاجرت VM و... را از منابع دریافت میکند. طرح و نقشه جایابی را به فوق ناظر ارسال میکند و برای مهاجرت اندازه و تعداد مهاجرت VM را مد نظر قرار میدهد، تا از مهاجرتهای پی در پی و غیر مفید جلوگیری کند. انرژی مصرفی را با یک حد آستانه کنترل میکند و برای مسئله Bin Packing از الگوریتم تغییر یافته FF استفاده میکند.
در [23] گودرزی و همکارانش، در دانشگاه کالیفرنیا با استفاده از ایجاد چندکپی12 از VM و با استفاده از برنامه نویسی پویا و جستجوی محلی به حل مسئله جایابی ماشین مجازی پرداختهاند و با استفاده از این چند کپی مصالحه بین انرژی مصرفی و کارایی را بهبود بخشیدهاندمعمولاً. چندکپی برای افزایش قابلیت اطمینان مورد کابرد قرار میگیرد. ایده این گونه است که VM اصلی وظیفه ارائه سرویس درخواست شده از ارائه دهنده را به عهده دارد. بقیه VMها غیر فعال نگه داشته میشوند تا زمانی که مورد نیاز باشد. بدین صورت به وسیلهی این ماشینهای مجازی غیر فعال دسترس پذیری بالا میرود و بهروری افزایش مییابد و انرژی مصرفی کاهش مییابد. انها برای حل مسئله Bin Packing از برنامه نویسی پویا و جستجوی خطی برای جایابی VMها استفاده کرده اند.
در[24] کرد و همکارانش، برای جایابی ماشین مجازی روشی ارائه دادند که هدفشان حل مصالحه کاهش انرژی و تخطی از SLA بود. آنها برای این کار از حداقل ضریب همبستگی برای جایابی ماشین مجازی استفاده کردند. برای حل مسئله مصالحه کاهش انرژی و تخطی از SLA، از آنالیز سلسله مراتب فازی13 استفاده کردند. همچنین یک مدل ارائه دادند که برای مدیریت به صورت متمرکز بود. الگوریتم ارائه شده برای آنها به این صورت بود که هر ماشین مجازی که میخواست یک میزبان را انتخاب کند، میزبانی را انتخاب میکرد که حداقل مصرف انرژی و و حداقل ضریب همبستگی را بین VMهای که بر روی آن میزبان دارد را انتخاب میکرد.
در[25] برای کاهش مصرف انرژی مبتنی بر جایابی یک الگوریتم سلسله مراتبی با استفاده از الگوریتم زنبور عسل ارائه دادند که با استفاده از خوشه بندی ماشینهای مجازی بر اساس CPU بهترین مکان را برای ماشین مجازی تعیین میکرد و همچنین تاخیر انتقال را نیز کاهش میداد و برای جلو گیری از کاهش کارایی سعی بر کمینه کردن مهاجرت زنده ماشین مجازی داشت.
در [26] محققان، با استفاده از الگوریتم کلونی مورچه بر روی تعادل بهرهوری منابع سرورها تمرکز کردند. هدفشان کاهش توان مصرفی و همچنین کاهش اتلاف منابع بود. برای این کار از جبر برداری استفاده کردند. آنها ظرفیتهای میزبان، تقاضایهای ماشینهای مجازی و بهرهوری منابع را به صورت برداری مدل کردند و یک ماتریس برای جایابی ماشین مجازی در نظر گرفتند؛ که درآیهیهای آن نشان دهنده ماشین فیزیکی بود که ماشین مجازی را میزبانی میکرد. همچنین برای ائلاف منابع به صورت برداری رفتار میکردند و با استفاده از الگوریتم کلونی مورچه از بین نگاشتهای ممکن نگاشت بهینه را بدست میآوردند.
در [27] با استفاده از کلونی مورچه به مسئله یکپارچه سازی بار کاری پرداخته است. مسئله بستهبندی چند بعدی را با الگوریتم بهینهسازی کلونی مورچه حل کرده است. در الگوریتم پیشنهادی آنها، هر مورچه تمام بستهها (به عنوان مثال، (VMs، و تمام Bin ها (به عنوان مثال، دستگاه فیزیکی) را دریافت میکند و با استفاده از یک قاعده تصمیمگیری احتمالی، که مطلوبیت کار انجام شده برای یک مورچه را توصیف میکند؛ انتخاب میزبانها را شروع میکند. مقدار فرمونها را به روز رسانی میکند و با احتمال ماشین مجازی دوم را در این میزبان قرار میدهد. این قانون بر اساس اطلاعاتی که در مورد غلظت فرمون جاری مورچهها است، آنها را نسبت به انتخاب امیدوار کننده-ترین آیتم راهنمایی میکند. از این رو، با توجه به مقدار فرمون و اطلاعات، بسته ای را انتخاب خواهد کرد که بالاتر احتمال را دارد. این طبیعت تصادفی از الگوریتم اجازه می-دهد تا مورچهها برای کشف تعداد زیادی از راه حلهای بالقوه را بیابند. در نهایت، بعد از آنکه همه راه حل مورچهها ساخته شدهاند، مقدار فرمون (تبخیر یا افزایش) را بر اساس یک قانون به روز رسانی فرمون انجام میدهند.
در [28]، مسئله انرژی با استفاده از جایابی VM در معماری ابر را با منابع چند بعدی فرموله کردهاند. آنها با استفاده از سه الگوریتم جستجوی محلی و یک الگوریتم ژنتیکی راه حلی برای کاهش توان مصرفی مراکز داده ارائه دادند، اما پایداری آن ضعیف بود. آنها برای اینکار به جز منبع CPU، دیگر منابع محاسباتی مانند RAM و دیسک را نیز مورد نظر خود قرار دادند. آنها میزبانها را همگن و ماشینهای مجازی را ناهمگن فرض کردند. مسئله را به صورت مسئله بسته بندی چند بعدی بستهها در نظر گرفتهاند.
در [29] یک روش جدید بر اساس اتوماتای یادگیر برای جایگزینی پویای ماشینهای مجازی در مراکز داده به منظور کاهش مصرف انرژی ارائه داده شده است. کاهش مهاجرت زنده و مجبور کردن گره بیکار به حالت غیر فعال یا خواب از سیاستهای اصلی این روش را تشکیل میدهند. هر گره فیزیکی در مراکز داده ابر، یک اتوماتا است که که یادگیری آن، قبول یا رد ماشین مجازی از گره مبدا به مقصد است. هر اتوماتای یادگیر دارای دو عمل که فقط یکی از آنها در یک زمان فعال است. با توجه به بهرهوری پردازنده، چهار وضعیت وضعیت بیکار، وضعیت میانگین، وضعیت فعال وضعیت بیش از استفاده14 تقسیم می کرد و میزبانهای را که بهره وری پردازندههای آنها برابر صفر است آنها را به عنوان یک میزبان خاموش در نظر میگیرد. همانند زنجیره مارکوف انتقال از یک حالت به حالت دیگر معادل است تغییر حالت از یک گره به گره دیگر پس از پذیرش ماشین مجازی است. برای مدیریت مناسب مهاجرت ماشین های مجازی رفتار میزبان را به صورت میزبان- فرستنده، گیرنده- میزبان، و بی طرف دسته بندی کردهاند. هر میزبان بر اساس وضعیت کنونی خود میتوان در حالتهای مختلف قرار گرفته و یا در حالت قبلی باقی بماند. ضرایب پاداش و جریمه اتوماتای یادگیر، مقداری است که با توجه به وضعیت گره منبع و مقصد مقدارش تعیین میشود. گره مقصد با استفاده از پاسخ محیط، در تکرار بعدی استفاده میکند تا تخصیص جدیدی که ایجاد میشود به زمانبندی بهینه نزدیکتر باشد. این تکرار به تعداد بسیار زیادی انجام میشود تا جایابی مناسب را پیدا کنند و تغییر دیگری در تصمیم خود ندهد. آنها فقط بر روی انرژی متمرکز شدند لذا تخطی از SLA با این روش بیش از دیگرروش های ارائه شده است.
-3 روش پیشنهادی
روش پیشنهادی: در رویکرد پیشنهادی از اتوماتای یادگیر به عنوان ابزاری برای جایابی ماشین مجازی مناسب استفاده می شود و پارامترضریب همبستگی چندگانه نیز به کار گرفته می شود. دلیل این کار این است که بیشترین همبستگی بین منابع استفاده شده توسط ماشینهای مجازی روی یک میزبان احتمال تبدیل شده به میزبان که دارای بار اضافی است را افزایش میدهد. در این بخش ابتدا با اتوماتای یادگیر و سپس ضریب همبستگی چندگانه آشنا و الگوریتم پیشنهادی خود را رائه میدهیم.
1-3 اتوماتای یادگیر
یک اتوماتای یادگیر یک مدل انتزاعی است که میتواند تعداد محدودی عمل را انجام دهد. هر عمل انتخاب شده توسط محیطی تصادفی ارزیابی میشود و پاسخی به اتوماتای یادگیر داده میشود. اتوماتا از این پاسخ استفاده نموده و عمل خود را برای مرحله بعد انتخاب میکند. محیط تصادفی را میتوان با سه تایی تعریف کرد که دراینجا مجموعه ورودیها، مجموعه خروجیها و
که مجموعه احتمالهای جریمه شدن است. اگر i دو مقداری باشد، i=0 به عنوان پاداش در نظر گرفته میشود وi=1 به عنوان جریمه در نظر گرفته میشود. Ci احتمال آنکه عمل i نتیجهی نامطلوب داشته باشد، است. در محیط پایدار مقادیر Ci بدون تغییر میماند، حال آنکه این مقادیر در محیط ناپایدار این مقادیر در طی زمان تغییر می-کنند. شکل (3) ارتباط بین اتوماتای یادگیر و محیط را نشان میدهد.[30]
شکل( (3 ارتباط بین محیط و اتوماتا [30]
اتوماتای یادگیر به دو گروه اتوماتای یادگیر با ساختار ثابت و اتوماتای یادگیر با ساختار متغیر تقسیم میشوند. در این پایان نامه از اتوماتای یادگیر با ساختار متغیر استفاده شده است که مختصری آن را شرح میدهیم.
2-3 اتوماتای یادگیر با ساختار متغیر :
اتوماتای یادگیر با ساختار متغیر توسط 5 تایی نشان داده میشود.
· نشان دهنده مجموعه اعمال اتوماتای یادگیر
· نشان دهنده مجموعه ورودیهای اتوماتا
· بردارهای احتمال انتخاب عملها
• الگوریتم یادگیری
· و احتمال جریمه شدن هر عمل است.
اگر اتوماتای یادگیر عمل i را در مرحله iام انتخاب کند و پاسخ مطلوب از محیط دریافت نماید. احتمال Pi(n) افزایش یافته و سایر احتمالها کاهش مییابند و برای پاسخ نامطلوب احتمال Pi(n) کاهش یافته و سایر احتمالها افزایش مییابند. تغییرات به گونهای صورت میگیرد تا حاصل جمع Pi(n) همواره ثابت و مساوی یک باقی بماند.
الف- پاسخ مطلوب رابطه((1 بدست میآید.
)1(
ب)پاسخ نامطلوب از رابطه((2 بدست میآید.
(2)
در روابط فوق پارامتر پاداش و b پارامتر جریمه است.. زمانیکه وb با هم برابر باشند الگوریتم را 15 LRPمینامند.[95]
در واقع در رویکرد پیشنهادی هنگامی که چندین میزبانی دارای منابع کافی بوده و فقط در یکی از شرایط کمترین انرژی مصرفی و یا کمترین ضریب همبستگی صدق کنند. با استفاده از اتوماتا و پاسخهای محیط یکی از آنها به عنوان میزبان برای ماشین مجازی جاری انتخاب میشود.
2-3 ضریب همبستگی چندگانه
ضریب همبستگی چند گانه در آنالیز رگراسیون چندگانه برای ارزیابی کیفیت پیشگویی متغیر وابسته استفاده میشود. مقدارآن به مربع بین مقادیر پیش بینی شده و مقدار واقعی متغیر وابسته، بستگی دارد مقدار متغیر وابسته y، به وسیله یک مجموعه متغیرهای توضیحی x1,x2,…[3 بدست میآید. رابطه iامین مشاهده از متغیر y به صورت yi با P متغیر توضیحی به صورت رابطه (3)بدست میآید.
(3)
که در آن
:yi مقدار مورد iام متغیر کمی وابسته است.
