سرویس انتزاعی
۱
۲
۳
۴
۵
۶
۶
۱
۳
۳
۵
۴
شکل ۳-۵ : نحوه نمایش جواب‌ها در رویکرد‌های فرا مکاشفه‌ای
همان طور که در شکل بالا مشخص است ۶ فرایند وجود دارد که هر فرایند توسط یک سرویس انتزاعی که پیاده سازی‌های متنوعی دارد قابل انجام می‌باشد. در جواب نمایش داده شده از ۷ سرویس واقعی موجود برای انجام سرویس انتزاعی ۱، سرویس واقعی ششم انتخاب شده است. برای سرویس انتزاعی دوم که عملکرد متفاوت با سرویس انتزاعی اول دارد نیز ۷ پیاده سازی متنوع وجود دارد که از میان آن‌ها سرویس واقعی ۱ انتخاب شده است و به همین ترتیب برای مابقی سرویس‌های انتزاعی نیز سرویس‌های واقعی در محدوده مجاز انتخاب می‌شوند.
( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )
۳-۵-۲ رویکرد ژنتیک
در بسیاری از مسائل با تابع هدفی روبه رو هستیم که سعی در بهینه نمودن آن داریم. رویکرد ژنتیک که اولین بار توسط جان هالند [۴۰] پیشنهاد شد روش بهینه سازی الهام گرفته از طبیعت می‌باشد که مبتنی بر تکرار است و اصول اولیه آن از علم ژنتیک اقتباس شده است. ژن‌ها و کروموزوم‌ها عامل اصلی انتقال خواص بیولوژیکی از هر نسلی به نسل بعدی می‌باشند به طوری که هر کروموزوم خود متشکل از تعدادی اجزاء بنام ژن می‌باشد. اساس این رویکرد قانون تکامل داروین است که می‌گوید موجودات ضعیف‌تر از بین می‌روند و موجودات قوی‌تر باقی می‌مانند بنابراین در این رویکرد احتمال تولید نسل از کروموزوم‌های قوی‌تر که هر یک از آن‌ها می‌تواند یک حالت از ترکیب وب سرویس‌ها باشند بیشتر از کروموزوم‌های ضعیف‌تر است.
رویکرد ژنتیک به عنوان یک رویکرد محاسباتی بهینه سازی با در نظر گرفتن مجموعه‌ای از نقاط فضای جواب مسئله، در هر تکرار محاسباتی به طور موثر نواحی مختلف فضای جواب را جستجو می‌کند در این رویکرد نسل اول به طور تصادفی ایجاد شده و جستجو‌ها در فضای مسئله بر اساس یک مکانیزم انتخاب صورت می‌گیرد تا با یافتن پاسخ‌های بهتر به سمت یک جواب بهینه حرکت کند و به این دلیل که در هر تکرار چندین نقطه از فضای جستجو را در نظر می‌گیرد بنابراین احتمال برخورد به بهینه محلی کاهش می‌یابد.
۳-۵-۲-۱ ساختار کلی الگوریتم ژنتیک
در ابتدا توسط مکانیزمی جواب‌های مسئله که هرکدام حالتی از ترکیب سرویس‌ها می‌باشند به صورت یک کروموزوم نمایش داده می‌شوند و در ادامه مجموعه‌ای از کروموزوم‌ها، که در حقیقت مجموعه‌ای از جواب‌های مسئله هستند به عنوان یک جمعیت آغازین[۴۹] به وجود می‌آیند. تعداد جمعیت اولیه پارامتری بوده همچنین هر یک از کروموزوم‌ها نیز به طور تصادفی ایجاد می‌شوند. حال با بهره گرفتن از تابع برازندگی که توضیح آن در بخش ۳-۴ آمده است میزان برازندگی تمامی کروموزوم‌ها که در جمعیت اولیه وجود دارند را محاسبه می‌کنیم.
در گام بعد جمعیت جدید از جمعیت اولیه شکل می‌گیرد در این مرحله توسط عملگر‌های ژنتیک اقدام به ایجاد کروموزوم‌های جدید می‌کنیم. از بین کروموزوم‌های موجود در جمعیت اولیه با توجه به میزان برازندگی آن‌ها، ۲ کروموزوم را به عنوان والد انتخاب می‌کنیم(هر چه میزان برازندگی بیشتر شانس انتخاب نیز بیشتر می‌شود) و با بهره گرفتن از عملگر تقاطع کروموزوم‌های والد را با یکدیگر ترکیب و کروموزوم فرزند را شکل می‌دهیم و با بهره گرفتن از عملگر جهش و با توجه به احتمال جهش تغییرات کوچکی در هر کروموزوم ایجاد می‌کنیم. تولید جمعیت فرزندان از والدین به همین ترتیب ادامه پیدا می‌کند تا جمعیت کل به حد مطلوبی که کاربر تعیین کرده است برسد.
در ادامه بعد از تولید تمامی کروموزوم‌های فرزند از والدین، با بهره گرفتن از تابع برازندگی، برازنده‌ترین کروموزوم‌ها از بین کروموزوم‌های والد و فرزند انتخاب می‌شوند به طوری که تعداد کروموزوم‌های منتخب برابر با اندازه جمعیت اولیه باشد.
تا اینجای کار یک تکرار یا یک نسل از رویکرد طی شده است و پس از طی چندین نسل به همین شکل رویکرد به سمت جواب بهینه همگرا می‌شود. حالت‌های مختلفی را می‌توان برای خاتمه رویکرد در نظر گرفت:
شرط خاتمه رویکرد می‌تواند طی کردن تعداد معینی تکرار باشد که بیش از آغاز رویکرد توسط کاربر مشخص می‌شود. همچنین در صورتی که بعد از چندین نسل هیچ بهبودی در برازندگی کروموزوم‌ها به وجود نیاید رویکرد می‌تواند متوقف شود.
در این تحقیق هر نسل جمعیتی برابر با ۱۰۰ کروموزوم دارد. جمعیت اولیه به صورت تصادفی تولید می‌شود. ۲۰% از کروموزوم‌های خوب که بیشترین برازندگی را دارند به صورت خودکار به نسل بعد کپی می‌شوند. با بهره گرفتن از عملگر تقاطع دو نقطه‌ای ۷۹% کروموزوم‌های نسل بعد تولید می‌شوند.۱% از کروموزوم‌های باقیمانده نسل بعد با بهره گرفتن از عملگر مهاجرت[۵۰] از طریق تولید کروموزوم‌های تصادفی جدید تکمیل می‌شود [۴۱].
ساختار کلی یک الگوریتم ژنتیک در زیر آمده است.
Procedure: Genetic Algorithm
initializing population(Composition Services)
While (not termination cordination) do:
Computing fitness values of all Composition Services
Using crossover operation to build a ne
w composition service
Mutation operation
Selecting Composition Services based on fitness values
Building new population
End.
شکل ۳-۶ : ساختار کلی الگوریتم ژنتیک
۳-۵-۲-۲ مفاهیم کلیدی الگوریتم ژنتیک
برای پیاده سازی رویکرد ژنتیک مباحث کلیدی ذیل باید مورد بررسی قرار گیرند:
۳-۵-۲-۲-۱ ایجاد جمعیت اولیه
بعد از آنکه هر یک از جواب‌های مسئله که همان ترکیبی از سرویس‌ها می‌باشند را به یک کروموزوم تبدیل کردیم به عنوان اولین مرحله در رویکرد ژنتیک لازم است مجموعه‌ای از جواب‌ها را به صورت تصادفی تولید و به عنوان جمعیت اولیه انتخاب نماییم هرچند می‌توان در بعضی از موارد برای بالا بردن سرعت همگرایی از روش‌های مکاشفه‌ای نیز استفاده نمود یعنی بجای استفاده از یک رویکرد تصادفی در ایجاد جمعیت اولیه از جواب‌های حاصله از دیگر رویکرد‌های مکاشفه‌ای استفاده شود.
۳-۵-۲-۲-۲ عملگر‌های ژنتیک
یکی از مهم‌ترین بخش‌های رویکرد ژنتیک تولید کروموزوم‌های جدید از ترکیب کروموزوم‌های موجود می‌باشد این فرایند توسط عملگر‌های ژنتیک به نام عملگر تقاطع و جهش صورت می‌گیرد. در بعضی از عملگر‌های تقاطع تنها یک کروموزوم در نظر گرفته می‌شود و کروموزوم فرزند از طریق آن یک کروموزوم تولید می‌شود اما در بعضی دیگر از عملگر‌ها بیش از یک والد با یک دیگر ترکیب می‌شوند تا کروموزوم فرزند تولید شود.
حالت‌های مختلفی را می‌توان برای عملگر تقاطع در نظر گرفت که بعد از مشاهده نتایج بدست آمده از شبیه سازی، در این تحقیق از عملگر تقاطع دو نقطه‌ای استفاده می‌شود که نسبت به دیگر عملگر‌های تقاطع، نتایج بهتری در آزمایشات داشته است.
نحوه اجرای عملگر تقاطع دو نقطه‌ای بدین صورت می‌باشد که در آن دو کروموزوم که نقش والد را دارند در نسل فعلی با بهره گرفتن از چرخ رولت انتخاب می‌شوند. در ادامه دو موقعیت p1 و p2 به عنوان موقعیت‌های ترکیب به طور تصادفی بین ۱ و تعداد ژنهای موجود در یک کروموزوم تعیین می‌شوند. روش ایجاد کروموزوم فرزند به صورت زیر می‌باشد:
فرزند ۱: ابتدا ژنهای ۱ تا P1 را از والد۱ انتخاب و ژنهای P1 تا P2 را از والد۲ و در نهایت ژنهای P2 تا n را از والد۱ انتخاب می‌کنیم.
فرزند۲: ابتدا ژنهای ۱ تا P1 را از والد۲ انتخاب و ژنهای P1 تا P2 را از والد۱ و در نهایت ژنهای P2 تا n را از والد۲ انتخاب می‌کنیم.
