تعداد نظرات
0 دیدگاه
تعداد لایک
5 پسندیدن
تاریخ انتشار
دوشنبه ۲۲ مهر ۱۳۹۸
بازدید
52 نفر
الگوريتم هاي تخصيص داده پويا
§ دغدغه اصلي سيستم هاي پايگاه داده توزيع شده قطعه قطعه کردن و تخصيص پايگاه داده اصلي مي باشد واحد قطعه داده مي تواند يک فايل باشد که در اين حالت موضوع تخصيص همان تخصيص فايل خواهد بود مشکل تخصيص داده يک مسئله NP-complete مي باشد
الگوريتم هاي استاتيکالگوريتم ژنتيکالگوريتمSimulated EvolutionالگوريتمThe Mean Field Annealing (MFA)الگوريتم تخصيص داده جستجوي تصادفي همسايگیالگوريتمهای تخصيص پوياالگوريتم شمارنده سادهالگوريتمLoad Sensitive counterالگوريتمIncrementalالگوريتمoptimalالگوريتمThresholdالگوريتم هاي تخصيص داده پويا - پایگاه داده
مقدمه
§ نياز به هيوريستيکهاي سريع براي توليد راه حل هاي موثر مي باشد
§ تخصيص بهينه اشيا پايگاه داده به طور شديد بستگي به استراتژي اجراي پرس وجو که به وسيله پايگاه داده توزيع شده پياده سازي شده دارد
§ هزينه اصلي در اجراي پرس و جو در سيستمهاي پايگاه داده توزيع شده هزينه انتقال داده هنگام انتقال يک رابطه در موقع درخواست پرس و جو از يک سايت و انتقال آن از يک سايت متفاوت ميباشد.
§ هدف اصلي الگوريتم هاي تخصيص داده تعيين نسبت دادن فرگمنتها به سايتهاي مختلف براي کمينه کردن هزينه انتقال داده در اجراي يک مجموعه از پرس و جو ها مي باشد
§ هزينه اصلي در اجراي پرس و جو در سيستمهاي پايگاه داده توزيع شده هزينه انتقال داده هنگام انتقال يک رابطه در موقع درخواست پرس و جو از يک سايت و انتقال آن از يک سايت متفاوت ميباشد.
§ هدف اصلي الگوريتم هاي تخصيص داده تعيين نسبت دادن فرگمنتها به سايتهاي مختلف براي کمينه کردن هزينه انتقال داده در اجراي يک مجموعه از پرس و جو ها مي باشد
الگوريتم هاي استاتيک :
n الگوريتم تخصيص داده پارامترهاي زير را به عنوان ورودي مي گيرد :
q گراف وابستگي قطعه داده
q هزينه انتقال واحد داده اي بين سايتها
q محدوديتهاي تخصيص روي تعداد قطعه داده که مي تواند به سايت تخصيص داده شود
q تعداد تکرار اجراي پرس و جو از سايتها
q فرض کنيد ri,j نشان دهنده نيازمندي سايت i به قطعه داده j مي باشد
q الگوريتم ژنتيک براي مسئله تخصيص داده به صورت زير مي باشد :
q population را مقداردهي اوايه کن هر کدام از population هاي انفرادي اتصال نمايش دودويي تخصيص تصادفي اوليه هر قطعه داده مي ياشد.
q Population را ارزيابي کن.
q تعداد generation=0
q تا وقتي که no of generation MAX GENERATION انجام بده
q Individual ها را از population بعدي انتخاب کن
q Crossover و Mutation را براي Individual ها انتخاب شده انجام بده
q Population را ارزيابي کن
q تعداد generation را يکي اضافه کن
q اتمام حلقه While
q تخصيص نهايي را با انتخاب fittest individual مشخص مي کند اگر تخصيص نهايي قابل امکان نباشد سايتي که از نظر قطعه داده بار اضافي دارد بار آن را به سايتي منتقل مي کند که کمترين هزينه انتقال را دارد .
الگوريتم Simulated Evolution
n تفاوت اصلي الگوريتم ژنتيک با الگوريتم Simulated Evolution :
q الگوريتم ژنتيک روي crossover دارد که يک مکانيزم احتمالي مي باشد و که براي تبادل اطلاعات بين راه حلها براي شناسايي بهترين راه حل مناسب مي باشد
q الگوريتم Simulated Evolution از mutation به عنوان مکانيزم جستجوي اوليه استفاده مي کند
n اولين chromosome را براساس مسئله داده توليد کن و اين chromosome را براي توليد population اوليه تغيير بده.
n از هيوريستيک نگاشت براي توليد راه حل براي هر chromosome استفاده کن.
n راه حل بدست آمده را ارزيابي کن
n تعداد generation=0
n تا وقتي که no of generations MAX GENERATION انجام بده
n Chromosome ها را براي population بعدي انتخاب کن
n براي اين مجموعه کروموزوم ها crossover و mutation انجام بده
n از هيوريستيک نگاشت براي توليد راه حل براي هر chromosome استفاده کن.
n راه حل بدست آمده را ارزيابي کن
n تعداد generation ها را يکي اضافه کن
n پايان حلقه While
n بهترين راه حل پيدا شده تاکنون را به خروجي ببر
الگوريتم The Mean Field Annealing (MFA)
n اوليه را بدست آور قرار بده T=T0
n ميانگين spin ها را مقداردهي اوليه کن s = [s00, s01, . . . , sk−1,m−1 هر si j با يک عدد تصادفي بين 0 و 1 مقداردهي اوليه مي شود
n تا وقتي که temperature در بازه cooling مي باشد انجام بده
n تا وقتي که E کاهش مي يابد انجام بده
n قطعه داده i را به صورت تصادفي انتخاب کن
n Mean field ، spin ها را در رديف i محاسبه کن براي مثال : Φi j , ∀ j
n مجموع روبرو را محاسبه کن: ∑eΦij/T
n
ارائه شده توسط : جم نما
در وب سایت : جم نما
ثبت دیدگاه برای این مطلب
نظرات شما عزیزان
هیچ نظری برای این پست ارسال نشده است
