الگوریتم بهینه سازی ازدحام گربه های پیشرفته

بهینه سازی ازدحام گربه ها

در تکنیک بهینه سازی ازدحام گربه ها، دو رفتار اصلی آنها، با دو زیر مدل بنام حالت ردیابی و جستجو مدل شده است. با روشی از ترکیب این دو حالت به نسبت تعریف شده، الگوریتم بهینه سازی ازدحام گربه ها، عملکرد خوبی را از خود نشان می دهد. در این الگوریتم، همانند بهینه سازی ازدحام ذرات، مکان گربه ها گویای یک پاسخ است و این الگوریتم با استفاده از گربه ها و مدل کردن رفتار آنها به حل مسائل بهینه سازی می پردازد. در بهینه سازی ازدحام گربه ها ابتدا تصمیم گرفته می شود که از چند گربه استفاده شود هر گربه دارای موقعیتی است که دارای M بعد می باشد. در کنار این موقعیت هر گربه دارای یک سرعت برای هر بعد و یک مقدار برازندگی است که نشان دهنده میزان برازندگی آن گربه می باشد. این برازندگی توسط تابع برازش بدست می ید همچنین علاوه بر موارد ذکر شده، هر گربه دارای یک نشانه پرچم نیز می باشد که برای شناسائی اینکه گربه در حالت ردیابی و یا در حالت جستجو است، بکار می رود.
در این پایان نامه به منظور کاهش مصرف انرژی و همچنین کاهش زمان اجرای درخواست کاربران، الگوریتم بهینه سازی ازدحام گربه ها طوری تغییر داده می شود که با بهره گیری از آن بتوان به شکل موثری، منابع به وظایف در زیرساخت ابری، اختصاص داده شود. در راهکار پیشنهادی از مجموعه ای از گربه ها استفاده خواهد شد که تعدادی از آنها در حالت جستجو و همزمان تعدادی دیگر در حالت ردیابی قرار دارند. هر گربه بیانگر یک نگاشت وظیفه منبع می باشد و بر اساس حالتیکه گربه در آن قرار دارد، بهروزرسانی می-شود. اختصاص مقدار برازش به گربه ها باعث می شود که هزینه نگاشت را حداقل کرد. در هر بار تکرار، مجموعه ای از گربه های جدید انتخاب می شود تا در وضعیت جستجو قرار گیرند. در نهایت بهترین مکان در بین گربه ها در واقع بیانگر بهترین نگاشتی خواهد بود که در بین سایر نگاشت ها، کمترین هزینه را ایجاد می کند. بر همین اساس در ادامه، ابتدا حالت های جستجو و ردیابی به عنوان زیر مدلی برای مدل کردن رفتار جستجوی گربه جهت یافتن هدف مورد نظر، که در این تحقیق سرورهای پردازشی است، مورد بررسی قرار می گیرد.

حالت جستجو
چهار عامل اصلی در حالت جستجوی هر گربه به صورت ذیل تعریف می شود:

1- جستجوی منبع حافظه (SMP ): این عامل برای تعریف اندازه حافظه جستجو برای هر گربه تعریف می شود که موقعیت های جستو شده توسط گربه را نشان می دهد. گربه یکی از موقعیت هائی را که در حافظه اش می باشد را بر اساس توابع برازش انتخاب می کند.
2- تعداد ابعادی که تغییر می کنند (CDC ): این عامل تعداد ابعادی را که تغییر خواهد کرد را تعیین می کند.
3- جستجو در محدوده تعریف شده ابعاد (SRD ): این عامل نرخ تغییرات برای بعد انتخاب شده را نشان می دهد. در حابت جستجوف اگر بعدی برای تغییر انتخاب شد، تفاوت بین مقدار جدید و قدیم آن خارج از محدوده ای که توسط SRD تعریف شده است، نخواهد بود.
4- توجه به موقعیتی که در آن است (SPC ): این عامل یک متغیر بولین می باشد که تعیین می کند آیا نقطه ای که گربه در حال حاضر در آن ایستاده یکی از کاندیدهای حرکت خواهد بد یا خیر.این مقدار تاثیری بر روی ارزش SMP نخواهد داشت. الگوریتم کلی در حالتیکه گربه در وضعیت جستجو قرار دارد به شرح زیر است:
مرحله اول مربوط به ایجاد کردن j کپی از موقعیت کنونی گربه k ام (Catk) که j=SMP است. اگر ارزش SPC درست باشد در اینصورت j=(SMP-1) می شود و آنگاه موقعیت فعلی را بعنوان یکی از کاندیداها حفظ می کند. در مرحله دوم برای هر کپی، با توجه به CDC بصورت تصادفی، SRD درصد از مقادیر کنونی یا زیاد می شود و به مقادیر قبلی اضافه می شود. در مرحله سوم میزان تابع برازندگی (FS) برای همه نقاط کاندید محاسبه می شود. در قدم چهارم اگر تمام FSها دقیقاً برابر نبودند، احتمال انتخاب هر موقعیت کاندید، با توجه به برازش نرمال شده آن موقعیت محاسبه می شود و در غیر اینصورت احتمال انتخاب همه موقعیت های کاندید برابر قرار داده می شود. رابطه زیر چگونگی محاسبه برازش نرمال شده یک نقطه کاندید را با توجه به میزان برازندگی آن نقطه نشان میدهد.

که در رابطه فوق:

P_i: احتمال مربوط به گربه کاندید جاری cat_i

FS_i: مقدار برازش گربه cat_i

FS_max: حداکثر میزان تابع برازش

FS_min: حداقل میزان تابع برازش

با توجه به آنکه در راهکار پیشنهادی هدف اصلی تابع شایستگی پیدا کردن راه حل مینیمم می­باشد و بعبارتی هدف اصلی آن کاهش میزان مصرف انرژی و منابع است پس در این حالت FS_b = FS_max خواهد بود. نهایتاً در مرحله آخر بصورت تصادفی موقعیتی برای حرکت از موقعیت­های کاندید انتخاب می­شود و موقعیت cat_k تغییر می­یابد.

حالت ردیابی

از راهکار زیر به منظور مدل کردن رفتار گربه هنگام ردیابی هدف استفاده می شود. زمانیکه گربه به حالت ردیابی می رود با توجه به سرعتش در هر بعد، حرکت می کند و فضای محلی را از طریق انتقال به بهترین موقعیت، جستجو می کند. عمل ردیابی را می توان در سه مرحله زیر بیان کرد:

مرحله اول: بهنگام سازی سرعت برای هر بعد (vk,d) با توجه به رابطه زیر:

x_best,d موقعیتی از گربه را نشان می­هد که بیشترین مقدار برازندگی را دارد و X_k,d موقعیت گربه kام می­باشد. c₁ عددی ثابت و r₁ یک عدد تصادفی در بازه [0,1] است.

مرحله دوم: بررسی می­شود که سرعت­ها در محدوده­ تعریف شده باشند. در صورتیکه سرعتی بیشتر بود با حداکثر مقدار ممکن در محدوده مورد نظر جایگزین می­شود.

مرحله سوم: بهنگام سازی موقعیت گربه  kام با توجه به رابطه زیر:

x_k,d = x_k,d + k_k,d

بعبارتی دیگر در این مرحله، مجموعه جواب های حاصل از بهترین مکان گربه در تکرار جاری، بهروزرسانی می شود. همانطورکه مشاهده شد، بهینه سازی ازدحام گربه ها از دو زیرمدل حالت جستجو و ردیابی استفاده می کند، نحوه ترکیب این دو زیرمدل، جهت انجام عملیات زمانبندی، در بخش بعدی تشریح می شود.

زمانبندی مبتنی بر بهینه سازی ازدحام گربه ها

هدف اصلی از زمانبندی وظایف استفاده بهینه از منابع در دسترس می باشد بطوریکه زمینه ساز افزایش کیفیت سرویس فراهم شود. در این تحقیق منظور از کیفیت سرویس، کاهش زمان اجرای وظایف و همچنین کاهش میزان مصرف انرژی می باشد که از این طریق زمینه سازی کاهش هزینه ها و همچنین کمینه کردن زمان اجرای درخواست کاربران فراهم می شود. به منظور کاهش هزینه های ارایه خدمات به کاربران، ارایه دهندگان خدمات ابری دارای سیاست های متفاوتی هستند و در واقع بر اساس نوع کاربر و خدمات مورد نظر، سیاست های متفاوتی را در پیش می گیرند. اما در این تحقیق که هدف اصلی آن کاهش هزینه مصرف منابع می باشد، پارامترهای ارزیابی میزان مصرف منابع در ادامه تعریف می شود