بخشی از مقاله
چکیده
فهم یک برنامه عامل مهمی در توسعه و نگهداری یک نرمافزار محسوب میشود به طوری که در سیستمهای نرمافزاری بزرگ بیش از 60 درصد هزینه نگهداری نرمافزار صرف فهمیدن آن میشود. پیمانهبندی نرمافزار به عنوان یکی از مراحل مهندسی معکوس، جهت فهم یک برنامه به کار برده میشود. با توجه به NP-hard بودن مسئله پیمانهبندی از الگوریتمهای تکاملی استفاده میشود. مشکل این الگوریتمها سرعت پائین آنها است. هدف این مقاله، ارئه الگوریتمی قطعی میباشد که مشکلات الگوریتمهای تکاملی را نداشته باشد.
از طرفی چون هدف پیمانهبندی کمک به مهندسان نرمافزار است الگوریتم ارائه شده سعی دارد با توجه به روابط موجود بین پیمانهها آنها را به خوشههایی با اندازه دلخواه تبدیل کند به صورتی که انسجام بالا و اتصال پائینی داشته باشند. در این مقاله 11 سیستم نرمافزاری متفاوت مورد بررسی قرار گرفته است، نتایج نشان میدهد که الگوریتم پیشنهادی پیمانههایی با کیفیت بالاتر نسبت به روشهای تکاملی و سلسلهمراتبی میدهد.
-1 مقدمه
خوشهبندی کد منبع نرمافزار یکی از چالشهای مهندسی نرمافزار است. یک خوشهبندی خوب نگهداری و گسترش نرمافزار را راحتتر میکند 2]،.[1 تقریب زده شده است که 60 درصد هزینه نگهداری نرمافزار صرف فهمیدن و درک آن میشود .[3] یک خوشهبندی خوب میتواند این هزینه را کاهش دهد. یک خوشهبندی مناسب دارای انسجام بالا1 و اتصال پایین2 است 2]،[1 اما با گسترش نرمافزار این ویژگیها از بین میرود .[4] بنابراین یک روش مناسب برای دوباره خوشهبندی نرمافزار لازم است. تلاش ما در این مقاله ارائه روشی سریع و دانش محور برای این منظور است.
هدف از خوشهبندی کمک به مهندسان نرمافزار است. انسجام بالا و اتصال پایین باعث میشود که در هنگام ایجاد تغییرات در نرمافزار این تغییرات به راحتی اعمال شود زیرا پیمانههای مرتبط اکثرا در یک خوشه قرار میگیرند و مهندسان مسئول هر خوشه آشنایی کامل با پیمانههای آن دارند. طبق مصاحبههای انجام گرفته، اندازه دلخواه خوشهها میتواند دست مهندسان را در تقسیم نیرو باز بگذارد بنابراین در این مقاله سعی شده است تا روشی جهت ایجاد خوشههای دلخواه ارائه شود.
مسئله خوشهبندی میتواند به عنوان بخشبندی گراف فراخوانی وابستگی مطرح شود و از آنجایی که بخشبندی گراف یک مسئله NP-hard است [10]، الگوریتم قطعی با زمان اجرای مناسب برای مسئله وجود نخواهد داشت بر این اساس منکوردیس و همکاران روشهای جستجو محور3 را برای خوشهبندی پیشنهاد دادند .[10] روشهای جستجو محور زیادی برای خوشهبندی کد منبع نرمافزار پیشنهاد شده است. ازجمله این روشها: روش تپهنوردی4 ، گداخت فلزات5 و الگوریتمهای ژنتیک 6 است .[11] که الگوریتمهای ژنتیک در این بین از همه قویتر عمل کردهاند.
الگوریتم ژنتیک دشواریهای فراوانی دارد از جمله تعیین جمعیت اولیه مناسب، تعیین نرخ ترکیب، نرخ جهش و شرط خاتمه و این روش زمانی استفاده میشود که آنالیز ریاضی در دسترس نباشد و الگوریتمهای قطعی موجود به جواب دلخواه نرسند. اما باید گفت که گراف وابستگی نرمافزار خود یک مفهوم ریاضی است که میتواند آنالیز شود اساس کار ما نیز بر پایه همین گراف وابستگی است که به ما کمک میکند که یک الگوریتم قطعی مناسب ارائه دهیم که دشواریهای الگوریتم ژنتیک را نداشته باشد و از طرفی چون از احتمالات استفاده نمیکند امکان شکست ندارد زیرا که هر چقدر هم که روشهای مبتنی بر جستجو قوی باشند باز هم بر پایه احتمالات عمل میکنند و این احتمال وجود دارد که هیچگاه به جواب درست نرسیم مگر این که کل فضای حالت ممکن جستجو شود که ما را به صورت مسئله میرساند که در زمانبندی مناسب نمیتوان تمام فضای حالت را جستجو کرد.
در این مقاله الگوریتمی ارائه میشود که بر اساس همسایگیهای موجود در گراف فراخوانی وابستگی یک درخت تشکیل داده و طی مراحلی خوشههای دوتایی، سهتایی و ... تا اندازه دلخواه تولید کند. در این تحقیق، نتایج [ 12] MQ و ضریب نیمرخ [12] الگوریتم پیشنهادی با 5 الگوریتم قطعی دیگر و نیز الگوریتم DAGC مقایسه شده است. تحلیل نتایج این موضوع را نشان میدهد که الگوریتم پیشنهادی قدرتمندتر عمل کرده است. در ادامه مقاله، در بخش 2 مفاهیم پایه و کارهای گذشته بررسی میشود. در بخش 3 روش پیشنهادی به همراه نتایج بیان میشود. بخش 4 شامل بحث و نتیجهگیری میباشد.
-2 کارهای گذشته و مفاهیم پایه
-1-2 کارهای گذشته
از آنجایی که هدف از پیمانهبندی کمک به گسترش دهندگان نرمافزار است، تحقیقی انجام گرفته تا روشهای معرفی شده برای انسجام بالا و اتصال پایین توسط گسترش دهندگان نرمافزار ارزیابی شوند.[5] نتایج نشان میدهد که انسجام بالا و اتصال پایین نرمافزار کافی نیستند. الگوریتم های قطعی فراوانی برای خوشهبندی ارائه شدهاند از جمله روشهای سلسلهمراتبی [7]، روش از دست رفت اطلاعات[6] 7، روش ترکیبی[8] 8 و روش ترکیبی وزندار[9] 9 که تمامی این الگوریتمها به صورت قطعی و معین سعی در پیمانهبندی کد منبع نرمافزار دارند، اما هیچ کدام جواب مطلوبی ارائه ندادهاند پس روشهای مبتنی بر جستجو [10] برای این منظور ارائه شدهاند از جمله الگوریتم ژنتیک، تپهنوردی و گداخت فلزات .[11]
-2-2 مفاهیم پایه
-1-2-2 معیار MQ
یک خوشهبندی خوب انسجام بالا و اتصال پایین دارد، برای اندازهگیری این پارامترها نسبت یالهای داخلی یک خوشه را بر مجموع یالهای داخلی و خارجی آن به دست میآورند و عدد به دست آمده را به عنوان پارامتر کیفیت خوشه در نظر میگیرند و در نهایت مجموع اعداد به دست آمده برای خوشههای مختلف را به عنوان کیفیت پیمانهبندی در نظر میگیرند.
-2-2-2 معیار ضریب نیمرخ
یکی دیگر از معیارهای دیگر تعیین کیفیت خوشهبندی ضریب نیمرخ است. در این معیار برای هر شئ موجود در یک خوشه نسبت تفریق یالهای داخلی به خارجی را به ماکزیمم آنها به دست میآورند و سپس برای یک خوشه میانگین عدد به دست آمده اشیا آن را به دست آورده و درنهایت میانگین اعداد به دست آمده برای تمام خوشهها را به عنوان معیار ضریب نیمرخ در نظر میگیرند.
-3-2-2 روشهای خوشه بندی سلسلهمراتبی
الگوریتمهای سلسلهمراتبی یک روش بالا به پایین یا پایین به بالا را دنبال میکنند. در روش پایین به بالا در هر مرحله اشیائی که بیشترین ارتباط را با هم دارند هم خوشه میشوند. در ادامه تعدادی از روشهای پایین به بالا استفاده شده در مقاله آورده شده است. الگوریتم ترکیبی شامل مراحل زیر است :[12] از یک ماتریس دادهها شامل مقادیر ویژگی دودویی استفاده میکند سطرهای این ماتریس موجودیتها وستونهای آن ویژگیها را نشان میدهد.
شباهت برای هر جفت موجودیتها را با استفاده از ماتریس دادهها محاسبه میکند. دو موجودیت با بیشترین شباهت را پیدا میکند و این دو موجودیت را در یک پیمانه ادغام میکند و این کار را تا زمانی که یک پیمانه باقی بماند انجام میدهد. در این روش پس از هم پیمانه شدن دو موجودیت بردار ویژگی آنها نیز با هم OR باینری میشوند تا بردار ویژگی جدید به وجود بیاید. هم چنین این الگوریتم از فرمول جکارد [12] برای تعیین شباهت استفاده میکند.
روش ترکیبی وزن دار - Weighted combined -
از آنجایی که الگوریتم ترکیبی خصوصیات باینری موجودیتها را OR میکند اطلاعات مربوط به تعداد موجودیتهای پیمانه که به یک ویژگی دسترسی دارند از دست میرود. الگوریتم ترکیبی وزندار [12] با حفظ اطلاعاتی در مورد تعداد موجودیتهایی در یک پیمانه که به یک ویژگی خاص دسترسی دارند، بر این کمبود غلبه میکند در نتیجه وقتی پیمانهها شکل میگیرند ویژگیها غیر دودویی میشوند و معیار تشابه نیز متناسب با ویژگیهای غیر دودویی به معیار النبرگ [12] تغییر میکند.
-4-2-2 روش DAGC
پیوند متوسط - average linkage -
در روش پیوند متوسط [12] فاصله هر موجودیت از یک پیمانه با هر موجودیت از پیمانه دیگر محاسبه و سپس متوسط فاصلههای به دست آمده به عنوان فاصله دو پیمانه درنظر گرفته میشود و ماتریس فاصله برای انجام پیمانهبندی سلسلهمراتبی براساس آن انجام میشود. فرض کنید ، و سه پیمانه باشند فاصله بین پیمانه با ⋃ با استفاده از فرمول - 6 - محاسبه می شود. در روش کدگذاری DAGC هر کروموزوم جایگشتی از گرهها گراف میباشد برای مثال با توجه به جدول - 1 - خانه mام از آرایه کروموزوم نمایانگر گره شماره m از ʽگراف است. اما محتوای آن حاوی شماره پیمانه مربوطه نیست، بلکه شماره گره دیگری از گراف مثل p در آن قرار داده میشود، اگر p بزرگتر یا مساوی m باشد آنگاه m در پیمانه جدیدی قرار داده میشود در غیر این صورت m در همان پیمانهای قرار میگیرد که p قرار داشته است.
