ارائه یک الگوریتم اجتماع مورچگان به منظور بهبود در زمان انجام کارها در محیط گرید

ارائه یک الگوریتم اجتماع مورچگان به منظور بهبود در زمان انجام کارها در محیط گرید

عنوان : ارائه یک الگوریتم اجتماع مورچگان به منظور بهبود در زمان انجام کارها در محیط گریدفرمت فایل اصلی : DOC قابل ویرایش با نرم افزار ورد تعداد صفحات :87 چکیده: دراین پروژه به ارایه یک روش جدید در پردازش شبکه ای با الگوریتم مورچگانپرداخته‌ایم. مدلی که در فضای شبکه ای استفاده کردیم حراج دو طرفه پیوستهمی باشد. این مدل ها به دلیل سادگی و پویایی خود امروزه در بسیاریاز الگوریتم های مورد استفاده برای کنترل منابع و زمان بندی کارها مورداستفاده قرار می گیرند. بسیاری از این مدل ها در زمان پاسخ گویی خود هنگاممدیریت منابع دچار ضعف می باشند. در مدل حراج, حراج کنندگان قیمت های موردنظر خریداران را اعلام می کنند و خریداری که قیمت مناسب را اعلام کرده باشدمنبع را بدست می گیرد. این مساله خود باعث می شود که زمان پاسخ گویی بهدلیل درخواست خریداران افزایش یابد. در این جا ما روش جدیدی را به وسیلهالگوریتم ژنتیک در سناریو حراج دو طرفه ارایه کردیم. در این روش با هوشمندسازی منابع, بسته های درخواست پیشنهادی را به سمتی سوق دادیم هر کدام ازاین محیط های شبکه ای را می توان به صورت یک سیستم توزیع شده در نظر گرفتکه با شبکه های دیگر تعامل ندارد و حجم زیادی از داده را پوشش می دهد. یکیاز فواید این روش نسبت به روش کلاسترینگ این است که منابع می تواند از لحاظجغرافیایی در نقاط پراکنده و به صورت غیر متقارن قرار گیرد. با توجه بهتوزیع مجموعه های داده، انتخاب مجموعه منابع محاسباتی و منابع حاوی دادهباید بطور مناسب صورت پذیرفته به گونه ای که سربار ناشی از انتقال اینمجموعه ها روی گرید کمینه شود. در این تحقیق، مساله زمانبندی برنامه هاینیازمند داده مورد توجه قرار می گیرد. با توجه به اینکه زمانبندی بهینهمستلزم انتخاب مجموعه منابع مناسب می باشد. در پردازش های شبکه ای ,محیط ها پویا می باشند به این معنا که ممکن است در یک زمان منابع روشن باشد و در زمانی دیگر همان منابع خاموش باشند پیادهسازی های صورت گرفته در نرم افزار شبیه سازی GridSim مورد بررسی قرار گرفتو نتایج نشان داد که این روش جدید باعث بهبود زمان پردازش و کم شدن تعدادمراحل حراج می شود. فصل اول: مقدمه 1-1- مقدمه هدفاصلی بهبود بازدهی در پردازش شبکه ای به وسیله الگوریتم مورچگان می باشد.این فصل با طرح مساله اصلی پردازش شبکه ای اغاز می شود و اهمیت آن شرح دادهمی شود. استفاده از الگوریتم مورچگان در بسیاری از مسایل باعث بهبودبازدهی و کاهش زمان پردازش شده است. این امر زمینه ای را فراهم می آورد تااز این الگوریتم در پردازشبکه ای نیز استفاده شود.2-1- پردازش شبکه ای پردازششبکه ای به مجموعه ای از منابع که از چند نقطه مختلف برای انجام یک هدفاقدام به کار می کنند گویند. هر کدام از این محیط های شبکه ای را می توانبه صورت یک سیستم توزیع شده در نظر گرفت که با شبکه ای های دیگر تعاملندارد و حجم زیادی از داده را پوشش می دهد. یکی از فواید این روش نسبت بهروش کلاسترینگ این است که منابع می تواند از لحاظ جغرافیایی در نقاطپراکنده و به صورت غیر متقارن قرار گیرد. . با توجه به توزیع مجموعه هایداده، انتخاب مجموعه منابع محاسباتی و منابع حاوی داده باید بطور مناسبصورت پذیرفته به گونه ای که سربار ناشی از انتقال این مجموعه ها روی گریدکمینه شود. در این تحقیق، مساله زمانبندی برنامه های نیازمند داده موردتوجه قرار می گیرد. با توجه به اینکه زمانبندی بهینه مستلزم انتخاب مجموعهمنابع مناسب می باشد. در پردازش های شبکه ای ,محیط ها پویا می باشند به اینمعنا که ممکن است در یک زمان منابع روشن باشد و در زمانی دیگر همان منابعخاموش باشند . همچنین در این پردازش ها ممکن است از لحاظ سخت افزاری و نرمافزاری با هم تفاوت داشته باشند. پردازش شبکه ای دارای معماری های مختلفی می باشد که می توان به موارد زیر اشاره کرد: – GT2 – OGSA – GT3 3-1- الگوریتم مورچگان الگوریتممورچگان یک الگوریتم هیوریستیک با یک جستجوی محلی بهینه می باشد که برایمسایل ترکیبی مورد استفاده می گیرد. این روش از رفتار طبیعی مورچگان الهامگرفته است. در طبیعت مورچگان با ماده ای که از خود ترشع می کنند راه را بهبقیه مورچگان نشان می دهند. در بسیاری از پژوهش ها از روش کلونی مورچگانبرای حل مسایل NPسخت استفاده می شود. از این روش برای حل مسایلی مانندفروشنده دوره گرد, رنگ امیزی گراف و مسیر یابی استفاده می شود.اجتماعمورچگان به مجموعه ای از مورچه های هوشمند گفته می شود که به صورت گروهیرفتار می کنند. این اجتماع در محیط جستجو می کنند تا جواب بهینه را پیداکنند. درمساله زمان بندی در محیط های شبکه ای, هر کدام از این کارها به منزله یکمورچه در نظر گرفته می شود. هر کدام از این مورچه ها به دنبال منابع موردنظر خود حرکت می کنند. در زیر شبه کد اجتماع مورچگان نشان داده شده است: Procedure ACO begin Initialize the pheromone whilestopping criterion not satisfied do repeat for each ant do Chose nextnode by applying the state transition rate end for until every ant hasbuild a solution Update the pheromone end while end روش های متفاوتی برای اجتماع مورچگان وجود دارد که می توان به موارد زیر اشاره کرد :– Max-Min Ant System – Rank-based Ant System – Fast Ant System – Elitist Ant System 4-1- چالش های پردازش شبکه ای ازچالش مهم در پردازش های شبکه ای می توان به نحوه اولویت بندی و زمان بندیبه پردازه ها اشاره کرد. مساله زمان بندی در پردازش های شبکه ای از سه بخشتشکیل می شود: 1- پیدا کردن منابع که شامل منابعی است قابلیت استفاده را دارند. 2- جمع اوری اطلاعات درباره این منابع و انتخاب بهترین مجموعه از منابع. 3- کارها در این مرحله انجام می شود. مرحله پیدا کردن مجموعه بهترین منابع یکی از مسایل NP-Complete می باشد. در زمان بندی کارها دو هدف عمده وجود دارد: 1- بیشترین میزان کارایی را سیستم داشته باشد. 2- بیشترین خروجی را داشته باشد. برایهدف اول, باید روشی ارایه شود که زمان پردازش را کاهش دهد و برای هدف دوم,باید روشی ارایه شود که زمان بندی را به مجموعه ای از کارهای مستقل از همتقسیم کند. این کار باعث می شود که ظرفیت انجام کار سیستم در واحد زمانافزایش یابد. برایحل این مشکل روش های متفاوتی ارایه شده است. یکی از این روش ها نگاشت اینمساله به مساله فروشنده دوره گرد می باشد. در این روش مسیر هایی که منابعنسبت به هم دارند مهم می باشد. در پردازش شبکه ای به دلیل اینکه منابع درفواصل متفاوت و غیر متقارن نسبت به هم قرار دارند به همین دلیل در مواردیاین روش می تواند مفید عمل کند. در ادامه این پژوهش مطالب به صورت زیر ارائه گردیده است. در فصل دوم به پیش زمینه های مربوطه پرداخته ایم و کلیات روش های زمانبندی به مورچه، ژنتیک و حراج پرداخته شده است. در فصل سوم مهمترین الگوریتم ها و روشهای پیاده سازی شده در بسترۀ الگوریتم های زمان بندی ارائه گردیده است. درفصل چهارم به ارائه روش پیشنهادی می پردازیم و نتایج شبیه سازی روشپیشنهادی (Acdanp) با روش قبلی مورد ارزیابی و مقایسه قرار می گیرد. در فصل پنجم به ارائه پیشنهادات و کارهای آتی می پردازیم. ضمناً در پیوست الف کد سورس نوشته شده در محیطی Gridsim آورده شده است. فهرست مطالب: چکیده فصل 1: مقدمه 1-1- مقدمه 1-2- پردازش شبکه ای 1-3- الگوریتم مورچگان 1-4- چالش های پردازش شبکه ای فصل 2 2-1- مروری بر الگوریتم های و روش ها 2-2- زمان بندی چندسطحی پویا 2-3- اختصاص سریعترین پردازنده به بزرگترین کار 2-4- صف کارها با تکرار(WQR) 2-5- الگوریتم اجتماع مورچگان تعادلی(BACO) 2-6- روش الگوریتم ژنتیک در پردازش شبکه ای فصل 3:پیشینه تحقیق 3-1- یک سیستم مبتنی بر عامل برای مدیریت منابع( ARMS) 3-2- روش پیوندی مورچگان 3-3- در اختیار گرفتن منابع در پردازش شبکه ای به وسیله الگوریتم یادگیری تقویتی 3-4- روش‌تجربی مورچگان به وسیله تخصیص منابع با روش‌اشتراک‌زمانی در پردازش شبکه‌ای 3-5- پیک روش حراج دو طرفه پیوست 3-6- ترکیبی از الگوریتم های ژنتیک 3-7- متا زمان بند ها به منظور زمان بندی برنامه های موازی 3-8- یک روش بهبودسازی به وسیله کلونی مورچگان 3-9- یک روش مبتنی بر عامل به منظور افزایشفصل 4: ارائه روش پیشنهادی و پیاده سازی 4-1 پردازش در محیط های شبکه ای با مدل های تجاری 4-2- روش حراج دو طرفه ای در پردازش شبکه ای 4-3- نحوه پیاده سازی روش های ارایه شده 4-4- کلاس حراج کننده4-5- کلاس مربوط به کاربر 4-6- کلاس ExampleAuction.java 4-7- کلاس مربوط به منابع حراج (AuctionResource.java) فصل 5: نتیجه گیری و پیشنهادات منابع