تحقیق - پایان نامه - مقاله و پروژه

دانشگاهی : استفاده از الگوریتم ژنتیک و منطق فازی برای بهینه سازی منابع بازار براساس شبکه بندی- قسمت ۵

۲-۲-۳ تعریف زمانبندی Nimrod/G24
Nimrod/G و GRACE،واسطه گرهایی برای مدیریت منابع و زمانبندی برنامه های کاربردی تعویض پارامتر می باشند.این سیستمها قادرند قیود کیفیت سرویس مد نظر کاربر را لحاظ کنند و زمانبندی را به صورت اقتصادی انجام دهند.
از طریق این سیستمها،می توان منابع و سرویس های گرید را در زمان اجرا،بر حسب ظرفیت،هزینه و دسترسی پذیری آنها،جهت تامین نیازمندیهای کاربران،به انها اجاره داد.
۲-۳مروری سریع بر الگوریتم ژنتیک۲۵
الگوریتم در سال ۱۹۷۰ توسط هلند،دیجونگ و گلدبرگ ارایه شده است.این الگوریتم جز کلاس الگوریتم های بهینه سازی تصادفی قرار دارد.این الگوریتم برای بهینه سازی مسایل پیچیده با فضای جستجوی ناشناخته مناسب است.به طور مختصر گفته می شود که الگوریتم ژنتیک یک تکنیک برنامه نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مساله استفاده می کند.مسئله ای که باید حل شود ورودی است و راه حل ها طبق یک الگوی کدگذاری می شود و متریک که تابع برازندگی هم نام دارد هر راه حل کاندید را ارزیابی می کند که اکثر آنها به صورت تصادفی انتخاب می شوند.
کلاً این الگوریتم ها از بخش های زیر تشکیل می شوند:
تابع برازش،نمایش،انتخاب و تغییر.
الگوریتم ژنتیک یک تکنیک جستجو در علم کامپیوتر برای یافتن راه حل بهینه در مسایل جستجو است.الگوریتم های ژنتیک یکی از انواع الگوریتم های تکاملی اند که از علم زیست شناسی مثل وراثت، جهش، انتخاب ناگهانی،انتخاب طبیعی و ترکیب الهام گرفته شده است.
۲-۳-۱ روش های نمایش۲۵
اولین گام برای بکارگیری و پیاده سازی یک الگوریتم ژنتیک نمایش جوابهای مسئله به صورت یک کروموزوم است.در حقیقت این عمل یک مفهوم کلیدی در الگوریتم های ژنتیک می باشد.کدینگ را می توان به دو نوع رشته ای و غیر رشته ای تقسیم کرد.در کدینگ رشته ای هدف تبدیل جوابهای مسئله به رشته ای از اعداد است.گاهی این رشته متشکل از صفرها و یک هاست.در اینصورت رشته دودویی نامیده می شود.اگر عناصر رشته از مقادیر دیگری تشکیل شده باشد با رشته غیر دودویی مواجه می شویم که این نوع کدینگ در مسائل بهینه سازی کاربرد بسیار کمی داشته و تنها در مسایل بسیار خاص استفاده می شود.
تعداد بیت های که برای کدگذاری متغیر استفاده می شود به دقت مورد نظر برای جوابها،محدوده تغییر پارامترها و رابطه بین پارامترها وابسته است.رشته یا دنباله ای از بیت ها که بعنوان شکل کد شده یک جواب از مسئله مورد نظر می باشد کروموزوم نامیده می شود.در حقیقت بیت های یک کروموزوم نقش ژن ها در طبیعت را بازی می کنند.یکی از ویژگی های اصلی الگوریتم ژنتیک آن است که متناوباً بر روی فضای کدینگ و فضای جواب کار می کنند.عملیات ژنتیک بر روی فضای کدینگ یا کروموزوم ها اعمال می شود در حالیکه انتخاب و ارزیابی بر روی فضای جواب عمل می نماید.شکل زیر بیانگر همین مطلب است:
decoding
Solution Space
Coding Space
encoding
Evaluation Selection
Genetic Operations
درهنگام استفاده از کدینگ با سه مفهوم اساسی زیر روبرو هستیم:
-قانونمند بودن کروموزوم
-موجه بودن کروموزوم
-منحصربفرد بودن ترسیم
قانونمندی کروموزوم مربوط به زمان بکارگیری عملیات ژنتیک می باشد.یعنی گاهی اوقات ممکن است کروموزوم هایی تولید شود که با هیچ عضوی از فضای جواب متناظر نباشد.
موجه بودن یک کروموزوم مربوط بحالتی است که بعد از رمزگشایی،همه محدودیت های مسئله را ارضا می کند،در غیر اینصورت کروموزوم غیر موجه خواهد بود.شکل زیر بیانگر دو مفهوم فوق است:
Feasible area
illegal
infeasible
Coding Space
Solution Space
encoding
یکی از روش های معمول نمایش به صورت رشته ای باینری است:رشته های ۰و۱٫یک روش حل دیگر کد کردن راه حل ها در آرایه ای از اعداد صحیح یا اعشاری است،که دوباره هر جایگاه یک جنبه از ویژگی ها را نشان می دهد.این راه حل در مقایسه با قبلی پیچیده تر و مشکل تر است.سومین روش برای نمایش صفات در یک GA،یک رشته از حروف است،که هر حرف دوباره نمایش دهنده یک خصوصیت از راه حل است.
خاصیت تمام این روش ها این است که آنها تعریف سازنده ایی را که تغییرات تصادفی در آنها ایجادمی کنند را آسان می کند:۰ را به ۱ و برعکس،اضافه یا کم کردن ارزش یک عدد یا تبدیل یک حرف به حرف دیگر.
به طور کلی روش نمایش به دامنه مسئله بستگی دارد.
مثال هایی از روش نمایش عبارتند از:
-دوتایی {۱و۰}
-سه تایی{۲و۱و۰}
-چهارتایی{۳و۲و۱و۰}
-عدد صحیح {…و۱۲و۱۱و…و۳و۲و۱}
-حقیقی {…و۱۲۶،۴و۵۹۱،۱و۸۵۴،۲}
۲-۳-۲مراحل الگوریتم ژنتیک۲۵
۲-۳-۳ ایجاد جمعیت اولیه
اولین مرحله بعد از تعیین تکنیکی که برای تبدیل هر جواب به یک کروموزوم بکار می رود ایجاد یک جمعیت اولیه از کروموزوم هاست.در این مرحله جواب اولیه معمولاً بصورت تصادفی تولید می شود.البته در بعضی موارد با توجه به نوع مسئله و برای بالا بردن سرعت همگرایی الگوریتم از روش های ابتکاری نیز استفاده گردیده است.به هر حال عمومی ترین و فرآگیرترین روش،استفاده از یک رویکرد تصادفی است.

در پایین درج شده است

mop