بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
پیش بینی نقص نرم فساربااستفاده از ترکیبمدل شبکو یای عصبیً الگٌریتم فرااکتشافی جیش قٌرباغو یا
چکیده
وجود نقص ها در سیستم نرم افزاری یک تهدید جدی برای کیفیت نرم افزار به شمار میرود، زیرا موجب به انطباق ناپذیری محصول با نیاز مشتری میشوند. پیش بینی نقص نرم افزار یکی از زمینه های مهم در مهندسی نرم افزار میباشد که برای بهبود کیفیت نرم افزار و یافتن نواقص نرم افزار، بهکار میرود.یکی از مدل های کارا در زمینه پیش بینی نقص ، شبکه های عصبی چندلایه با الگوریتم آموزشی پس انتشار خطا میباشد .از نقاط ضعف الگوریتم آموزشی پس انتشار خطا , احتمال به دام افتادن شبکه عصبی در نقاط مینیمم محلی میباشد. به دلیل قابلیت الگوریتم های فرااکتشافی در خروج از دام مینیمم های محلی و یافتن مینیمم سراسری, در این مقاله، به منظور بهبود دقت الگوریتم آموزشی شبکه عصبی در پیش بینی نقص نرم افزار, از ترکیب الگوریتم فرااکتشافی جهش ترکیبی قورباغه ها به همراه الگوریتم پس انتشار خطا استفاده شده است.نتایج پیاده سازی الگوریتم جدید ترکیبی و مقایسه آن با الگوریتم آموزشی پس انتشار خطا, نشان دهنده برتری الگوریتم پیشنهادی در زمینه پیش بینی نقص نرم افزار میباشد.
-1 مقدمه
پیشبینی نقص های موجود در محصول نرم افزاری یکی از مسائل قابل توجه در زمینه مهندسی نرم افزار می باشد و کمک حائز اهمیتی در صرفه جویی زمانی در فرآیند تولید و نگه داری نرم افزار به ما می کند. پیدا کردن مدل های مطلوب برای پیش بینی نقص نرم افزار امروزه تبدیل به یکی از مهمترین اهداف انجمن مهندسین نرم افزار شده است.چندین شیوه مختلف پیش بینی نقص نرم افزار در طی یازده سال گذشته بسط و توسعه داده شده اند.[1,2] شیوه-های مطرح شده ازمنابع داده, فاکتورها, مدلها و معیارهایارزیابی متفاوتی استفاده کرده اند.از پرکاربردترین منابع داده, مجموعه دادههای عمومی موجود در مخزن ناسا می-باشد که از سال 2005 ایجاد شده و در دسترس همگان قرار گرفته است.[1] فاکتورهای محصول,1 به طور مستقیم از کد منبع به دست میآید و یکی از کاراترین فاکتورها در زمینه پیش بینی نقص نرم افزار میباشد. معروف ترین مدلهای پیش بینی نقص نرم افزار شامل دسته های آماری2 ,یادگیری ماشین3 ویا ترکیبی از این دو دسته میباشد [3,4]
. از زمانی که پیش بینی و برآورد نقص نرم افزار یک مسئله بغرنج شده است، هیچ مدلی تا بحال نبوده است که تامین کننده یک راه حل کامل باشد. درسالهای اخیر, استفاده از مدلهای پیش بینی نقص مبتنی بریادگیری ماشین مورد توجه قرار محققین گرفته است.[1,5] از جمله مدلهای مبتنی بر یادگیری ماشین, میتوان مدلهای مبتنی بر درخت تصمیمگیری,4 نزدیکترین k همسایه,5 مدل naïve , bayes ماشین بردار پشتیبان,6 شبکههای عصبی7 و.... را نام برد. شبکه های عصبی پرسپترون چندلایه (MLP) به-همراه الگوریتم آموزشی پس انتشار خطا, یکی از مدل های کاربردی در زمینه پیش بینی میباشد.[6,7,8,9] یافتن وزن-های بهینه به منظور بدست آوردن خطای مینیمم سراسری در الگوریتم آموزشی پس انتشار خطا, به سادگی امکان پذیر نمیباشد. الگوریتم های فرااکتشافی8 متعددی با الهام از فرآیندهای فیزیکی و بیولوزیک در طبیعت بهوجود آمده اند. با توجه به جستجوی تصادفی و تکرار شونده الگوریتم های فرااکتشافی در فضای مساله ، این الگوریتم ها قادر به یافتن جواب بهینه برای حل مساله میباشند. تا کنون تکنیک های فرااکتشافی متعددی از قبیل الگوریتم ژنتیک, [10] الگوریتم بهینه سازی ازدحام ذرات [11] ، الگوریتم کلونی مورچه ها[12] به منظور بهبود آموزش پس انتشار خطا استفاده شده است.
در این مقاله, از ترکیب الگوریتم فرااکتشافی جهش ترکیبی قورباغه ها(9(SFL به همراه الگوریتم آموزشی پس انتشار خطا استفاده شده است تا وزنهای بهینه ای جهت آموزش شبکه عصبی چندلایه پیدا شوند و شبکه عصبی در طول فرآیند پیش بینی نقص نرم افزار، در دام نقاط مینیمم محلی نیفتد در ادامه مقاله در بخش 2 درباره شبکه های عصبی پرسپترون چندلایه با الگوریتم آموزشی پس انتشار خطا بحث شده است ، در بخش 3 الگوریتم جهش قورباغه ها عنوان شده است و در بخش 4 ایده پیشنهادی ترکیبی مطرح گردیده و در بخش 5 نتایج پیاده سازی، مقایسه با استفاده از داده های سه پروژه ناسا , مطرح گردیده است . در آخر نتیجه گیری کلی آورده شده است.
-2 شبکه های عصبی پرسپترون چندلایه
شبکه عصبی پرسپترون چند لایه((MLP از نوع شبکه های عصبی پیشخور10 هستند. [13] در شبکه های پرسپترون چندلایه هر نرون در هر لایه به تمام نرون های لایه قبل متصل میباشد.به چنین شبکههایی, شبکههای کاملا مرتبط میگویند. شکل1، یک شبکه پرسپترون با دو لایه مخفی و سه نرون در هر لایه مخفی و یک نرون در لایه خروجی را نشان میدهد.
لایه ورودی یک لایه انتقال دهنده و وسیله ای برای تهیه کردن داده ها میباشد. آخرین لایه یا لایه خروجی شامل مقادیر پیش بینی شده بهوسیله شبکه میباشد و خروجی مدل را معرفی می-کند. لایه های میانی یا مخفی که از نرونهای پردازشگر تشکیل شده اند, محل پردازش داده ها میباشند. خروجی شبکه طبق فرمول 1 بدست می آید .
مسیر رفت، الگوی آموزشی به شبکه اعمال می شود و تأثیرات آن از طریق لایه های میانی به لایه خروجی انتشار می یابد تا اینکه نهایتاً خروجی واقعی شبکه MLP، به دست می آید. در این مسیر، پارامترهای شبکه (ماتریس های وزن و بردارهای بایاس)، ثابت در نظر گرفته می شوند. در مسیر برگشت، سیگنال خطا طبق فرمول 2 تشکیل شده است و در شبکه انتشار مییابد .
در تابع خطا, E خطای موجود در تکرار t ام است. w(t) وزن موجود بین اتصالات در تکرار tام است. dk خروجی بهدست آمده و ok خروجی واقعی میباشد. n تعداد الگوها و k تعداد گره های خروجی میباشد. مقدار خطا، پس از محاسبه، در مسیر برگشت از لایه خروجی و از طریق لایه Yi= fi () های شبکه به سمت پاسخ مطلوب حرکت کند.پارامترهای که Yi خروجی شبکه و xi ورودی شبکه میباشند. وزنهای اتصالی بین گرههای ورودی و خروجی است. بایاس میباشد. fi تابع انتقال است.
-1-2آموزش شبکه های عصبی پرسپترون چندلایه
الگوریتم یادگیری پس انتشار خطا11 نخستینبارتوسط Paul Werbos در سال 1794 مطرحگردیذ که یکی از رایج ترین الگوریتم ها جهت آموزش شبکه های عصبی MLP می باشد. [14] فرایند پس انتشار خطا از دو مسیر اصلی تشکیل می شود. مسیر رفت12 و مسیر برگشت. 13 در
شبکه MLP باتوجه به سیگنال خطای منتشر شده و طبق فرمول 3 ، تغییر و تنظیم می گردند
.
به طوری W Lji، وزن نرون j ام در لایـه iام اسـت. α، نـرخ یادگیری14 و F، میانگین مربعات خطا مـی باشـد. در شـبکه های MLP، میـانگین مربـع خطـا، در حالـت کلـی خیلـی پیچیده است و از تعـداد زیـادی نقطـه اکسـترمم در فضـای پارامترهای شبکه برخوردار می باشد. بنابراین الگوریتم پـس انتشار خطا با شروع از روی یک سری شرایط اولیه وزنهای شبکه، به نقطه مینیمم سراسری و با شروع از یک مجموعـه شرایط اولیه دیگر به تقاط مینیمم محلی در فضای پارامترها همگرا می گردد، بنابراین زمانی کـه الگـوریتم BP همگـرا می شود، نمی توان مطمئن شد کـه بـه یـک جـواب بهینـه رسیده باشیم.
قرار میگیرد ، دومین راه حل در ممپلکس دوم و m مین راه حل در ممپلکس m م سپس مجدد m+1 مین راه حل در ممپلکس اول قرار میگیرد . این روند تا توزیع تمامی قورباغه ها ادامه مییابد. در شکل 2 روند توزیع قورباغه ها در ممپلکس ها نشان داده شده است.
-3 الگوریتم جهش ترکیبی قورباغه ها (SFL)
الگوریتم جهش ترکیبی قورباغه ها, یک الگوریتم جستجوی فرااکتشافی جدید مبتنی بر جمعیت اولیه از خانواده الگوریتم های ممتیک است که از تکامل طبیعی گروهی از قورباغه ها زمانی که به دنبال محل با بیشترین ذخیره غذایی در دسترس میگردند، الهام گرفته است . [15]
از ویژگی های این الگوریتم، توانایی حل مسائل غیر خطی، مسائل پیچیده با ابعاد بزرگ و سرعت مناسب در همگرایی آن است.
روند الگوریتم SFL بدین صورت است که در ابتدا یک جمعیت اولیه ای شامل N جواب شدنی P={X1,X2,..XN} به صورت تصادفی در فضای مساله تولید میشود. در یک مساله S بعدی ( S تعداد متغیرها) ، موقیع قورباغه (پاسخ) i ام در فضای جستجو به عنوان یک راه حل قابل قبول در مساله بهینه سازی در نظر گرفته می شود و آنرا به صورت بردارXi=[xi1, xi2,….,xis] T نشان میدهند( xi موقعیت قورباغه i ام و ( i=1,…,N سپس با استفاده از تابع برازندگی تعریف شده هر یک از جواب های مساله ارزیابی میگردند. در مرحله بعدی قورباغه ها با توجه به مقادیر شایستگی شان به صورت نزولی مرتب میشوند . سپس در مرحله بعد، راه حل ها به m زیر گروه مساوی تقسیم میشوند که به هریک از این زیر گروه ها یک ممپلکس گفته میشود. در هر ممپلکس n راه حل مساله قرار میگیرد . (n=N/m ) بدین صورت که نخستین راه حل ( راه حل ها با بالاترین مقدار شایستگی) در ممپلکس اول روال جستجوی محلی الگوریتم SFL شبیه به الگوریتم بهینه سازی ازدحام ذرات است و صرفا به منظور بهبود بدترین راه حل ( نه همه راه حل ها ) در هر ممپلکس انجام میگیرد. ابتدا در هر کدام از ممپلکس ها قورباغه هایی با بدترین و بهترین میزان شایستگی مشخص و به ترتیب با Xw و Xb نشان داده میشوند. همچنین راه حلی که دارای بهترین شایستگی در میان کل جمعیت است با Xg مشخص میشود. در ادامه در طی فرآیند تکامل ممپلکس ها، در هر ممپلکس ، موقعیت بدترین راه حل یعنیXw به سمت بهترین راه حل Xb به روز رسانی میشود. موقعیت جدید راه حل بدتر با استفاده از قانون پرش قورباغه ها به صورت زیر و طبق فرمول 4و5 بدست می آید . [15]
در رابطه فوق r یک عدد تصادفی بین صفر و یک است و Dmax حداکثر مقدار تغییرات مجاز در موقعیت قورباغه در یک پرش است.چنانچه این تغییر موقعیت جوابی با شایستگی بهتر تولید کرد ، این جواب جایگزین Xw می-گردد. در غیر این صورت محاسبات انجام شده با استفاده از فرمول های 4 و 5 و با جایگزینی بهینه سراسری Xg به جای بهینه محلی Xb تکرار میشود. در صورتی که باز هم بهبودی در جواب صورت نگیرد Xw حذف و یک راه حل جدید به صورت تصادفی جایگزین آن می شود. این سیر تکاملی برای برای تعداد گام های تکاملی ممتیک ( تعداد تکرارهای جستجوی محلی) که از قبل مشخص شده است ، در هر ممپلکس تکرار میشود. پس از اتمام فرآیند جستجوی محلی در ممپلکس ها ، تمامی اعضای جمعیت ، ترکیب شده و بر اساس میزان شایستگی آنها مجدد به صورت نزولی مرتب میشوند. سپس دوباره به چند زیر مجموعه تقسیم شده و روند گفته شده مجدد تکرار میشود. تکامل جمعیت در ممپلکس ها (فرآیند جستجوی محلی) و ترکیب دوباره کل جمعیت تا جایی ادامه مییابد که شرط توقف الگوریتم ( اتمام تعداد تکرار ها یا رسیدن به یک درصد خطای از پیش تعریف شده) برآورده گردد در این صورت الگوریتم SFL خاتمه یافته و جواب با بهترین مقدار شایستگی به عنوان بهترین جواب گزارش میشود.
