بخشی از مقاله
چکیده
امروزه سرویسدهی به کاربران از مسائل اصلی و چالشهای پیشروی کاربران برای توسعهی وب است. به همین دلیل، تحقیقات گستردهای بر روی نحوهی ترکیب سرویسهای وب برای پاسخ بهینه از نظر زمان و هزینه برای کاربران ارائه گردیدهاست. مسألهی دیگری که باید به آن توجه شود، وجود سناریوهای مختلف برای ترکیب سرویسهای مختلف وب و طراحی سیستمهایی است که معماری انعطافپذیری برای ارضای نیازهای کاربران داشته باشند. به همین دلیل، نرم افزارهایی که امروزه طراحی میشوند،
باید دارای شرایط بهینهای برای ترکیب سرویسهای وب باشند. در این مقاله، سناریوهای مختلف ترکیب سرویس های وب را مورد بررسی قرار میدهیم و برای ساختن بهترین پاسخ در فضای جستجوی سرویسها، از الگوریتم ترکیبی ژنتیک و کلونی مورچگان - HACOGA - برای افزایش احتمال یافتن پاسخ بهینه استفاده میکنیم. نتایجی که از پیادهسازی این روش در نرمافزار MATLAB بدست میآید، کارکرد بهتر الگوریتم ترکیبی ژنتیک و کلونی مورچگان را برای یافتن پاسخهای بهینه نسبت به الگوریتم ژنتیک بهینه شده، نشان میدهند.
مقدمه
امروزه سیستمهای سرویسگرا بهخاطر امکان فعالیت در محیطهای توزیعی ناهمگن از اهمیت ویژهای برخوردارند. کاربر اینگونه سیستمها از سرویسهایی که مولفههای سیستم ارائه میدهند، استفاده میکند. نیازهای کاربر در اغلب اوقات، توسط سرویسهای منفرد موجود رفع نمیگردد و میبایست با ترکیب تعدادی از سرویسها به سرویس مورد نظر دست یافت. یکی از مسائل مطرح در زمینهی سیستمها، چگونگی ترکیب سرویسها و نحوهی مدیریت آنها است. تاکنون روشهای مختلفی برای عمل ترکیب ارائه شدهاست
- Beardwood, Halton, & Hammersley, 1959; Clarke & Wright, . - 1964; Golden & Stewart, 1985; John, 1975; Lin & Kernighan, 1973; Platzman & Bartholdi III, 1989 ما در این مقاله بهدنبال راهی برای مدیریت ترکیب سرویسها با توجه به لایههای معماری سرویسگرا هستیم. با توجه به مشکلات سرعت همگرایی و همچنین افتادن در بهینهی محلی در روش های موجود، به دنبال روشی بودیم تا در مسألهی ترکیب سرویسها در مقیاس بزرگ علاوه بر همگرایی و سرعت مناسب در پاسخگویی از سوی الگوریتم ارایهشده، بهینگی روش هم بهخوبی قابل نمایش باشد.
راهکار پیشنهادی برای این مسأله، ترکیب دو الگوریتم ژنتیک و کلونی مورچگان و همزمانی اجرای این دو الگوریتم است. این دو الگوریتم در صورتیکه همزمان اجرا شوند و جوابهای خود را با هم تبادل کنند، میتوانند پاسخگوی بهینگی و عدم افتادن در بهینه ی محلی باشند. در این مقاله، جوابهای اولیهی الگوریتم کلونی مورچگان برای جهشکردن - عبورکردن - جوابهای الگوریتم ژنتیک از جوابهای بهینهی محلی و جوابهای الگوریتم ژنتیک برای وسیعکردن دامنهی جستجوی مورچهها بهکاربرده شدهاست.
درادامه، ابتدا نگاهی به کارهای پیشین در این رابطه خواهیم پرداخت و سپس به معرفی سیستمهای سرویسگرا و تعاریف مرتبط با آن میپردازیم و از تعاریف این قسمت در بخشهای بعدی استفاده میکنیم. پسازآن، به معرفی و طرح مسأله می پردازیم. سپس با ارائهی روش پیشنهادی، راهی برای ترکیب بهینهی سرویسهای وب به صورت پویا معرفی کرده و پس از ارزیابی اولیهی آن، به طور تجربی با نتایج آن آشنا میشویم. در بخش پایانی هم نتایج بدست آمده از این تحقیق را تحلیل کرده و ارائه میکنیم.
کارهای پیشین
الگوریتمهای ژنتیک و کلونی مورچگان در بسیاری از زمینهها مثل مسألهی فروشندهی دورهگرد، مسألهی کولهپشتی، بهینهسازی مجموعهی آزمایش، شبکههای عصبی، هوش مصنوعی و انتقال سیگنال مورداستفاده قرارگرفتهاند. اما این الگوریتمها ذاتاً ناقص هستند. الگوریتم ژنتیک دارای اشکالاتی مثل جستجوی محلی ضعیف، همگرایی کند است و در مقابل گیر افتادن در بهینهی محلی آسیبپذیر است. الگوریتم کلونی مورچگان کمبودهایی مثل شروع کند و رکود در بدستآوردن فرومون اولیهی کافی دارد.
بهخاطر مشکلات موجود در هر الگوریتم، محققین زیادی الگوریتمهایی برای بهبود آنها ابداع کردند. Zhang CW در - Zhang, Su, & Chen, 2006 - از الگوریتم ژنتیک کدنویسی چندبعدی برای حل مسألهی ترکیب سرویس چند مسیره استفادهکردهاست، اما این الگوریتم از برخی ساختارهای پیچیده پشتیبانی نمیکند. Hui Ma در - Ma, Wang, - & Zhang, 2015 روش ترکیبی برای ترکیب سرویس ارائهکرده که برنامهنویسی ژنتیک و جستجوی حریصانهی تصادفی را ترکیب میکند.
اما روش بسیار پیچیده و ناکارآمدی است. Stutzle و همکارانش در - Stutzle & Hoos, 1997 - یک الگوریتم 1 MMAS ارائه کردهاند که ایدهی اصلی آن محدودکردن فرومون در مسیر و بهروزرسانی جزئی فرومونها برای فائقآمدن بر رکود است. Luis H. V. در - Nakamura, Cunha, Estrella, Santana, & Santana, 2013 - برنامهنویسی پویا و الگوریتم کلونی مورچگان را برای حل مسألهی ترکیب سرویسهای وب با هم درآمیخته است، با این تفاوت که تنها گردشهای ترکیبی ترتیبی مدنظر قرارگرفتهاند.
ZhengDe Zhao و همکارانش در - Zhao, Hong, & Wang, 2015 - تحقیقاتی را در مورد استفاده از ادغام الگوریتمهای ژنتیک و کلونی مورچگان در ترکیب سرویسهای وب انجام دادند. در این روش الگوریتم بهبود یافتهی آنها از ادغام الگوریتمهای ژنتیک و کلونی مورچگان برای حل پیچیدگی زمانی ترکیب استفاده کردهاست. در مرحلهی اول، مسیر بهینهی سراسری بوسیلهی الگوریتم ژنتیک یافت میشود و در مرحلهی بعد، راهحل بهینهی کلی با اجرای الگوریتم کلونی مورچگان بدست میآید. سرعت همگرایی این الگوریتم ترکیبی، کاهشیافته و زمان ترکیب سرویس در آن افزایش مییابد. پیچیدگی زمانی آن، بسیار بهتر از الگوریتمهای سنتی است. هر چند زمان اجرایش برای تعداد فزایندهی سرویسها قابل پذیرش نیست. در نهایت این الگوریتم از لحاظ سرعت همگرایی و بهینگی مؤثر نیست.
تعاریف مفاهیم اولیه
معماری سرویسگرا، سبکی از معماری است که از اتصال سست سرویسها جهت انعطافپذیری و تعاملپذیری کسبوکار و بهصورت مستقل از فناوری، پشتیبانی میکند و از ترکیب مجموعهی سرویسهای مبتنی برکسبوکار تشکیلشده که این سرویسها انعطافپذیری و پیکربندی پویا را برای فرایندها محقق میکنند. ترکیب سرویس، یکی از پنج مرحلهی معرفیشده در مدلسازی معماری سرویسگرا به شمار میآید. این مراحل عبارتند از:
شناسایی سرویس، توصیف سرویس، عینیت بخشیدن به سرویس، ترکیب سرویس و پیادهسازی سرویس. در این مقاله تنها بر روی فاز ترکیب سرویس و روشهای موجود در آن تمرکز شدهاست. ترکیب سرویس، به فرایند توسعه یک سرویس مرکب گفته می شود. برای مقایسهی کیفی سرویسها، تابع QoS، کیفیت را به صورت کمی در میآورد. رفع هرنیازی برای کاربر امتیازی دارد که با آن کیفیت کلی سرویس، ارزیابی و در مقایسهها استفاده میشود. نحوهی محاسبه QoS بهصورت رابطهی 1 است . - Benatallah, Sheng, & Dumas, 2003 - در رابطهی 1، کاربر به برآوردهشدن نیاز -iام امتیاز wi را داده و سرویس s با کیفیت Scorei توانسته است این نیاز را مرتفع نماید.
بهخاطر استفادهی جامع از سرویسها، آنها اغلب به گونهای طراحی میشوند که مشخصهی کارکرد آنها بتواند مسائل ساده را برای انجام عملیات اتمیک حل کند. برای حل مسائل پیچیدهتر، توسعهدهندگان نرم افزار، ترکیبی مناسب از آنها را برگزیده و با اجرای یکبهیک آنها در توالی خاصی، به حل مسألهی طرحشده میرسند. این توالی در برنامهی اجرای مرتبط با مسأله مشخص میشود.
برای هر عمل در فضای سیستم، ممکن است چندین سرویس وجود داشتهباشد که آنها را سرویس نامزد2 مینامیم. اجرای سرویسها طبقبرنامه، باعث اجرای سرویس مرکب میشود. در فضای سیستم، برای هر عمل، سرویسهای نامزد زیادی توسط تامینکنندگان مختلف ارائه میشود که انتخاب سرویس مناسب از بین آنها توسط کاربر کاری دشوار و تقریبا ناممکن است - Ambite et al., 2002; Arpinar, Zhang, - Aleman-Meza, & Maduko, 2005، پس با ترکیب خودکار سرویسها3، یک سیستم کامپیوتری میتواند از انبوه
