یک الگوریتم ترکیبی برای حل مسئله خوشهبندی سیستمهای نرمافزاری GALA

خوشهبندی سیستمهای نرمافزاری، یک روش بسیار مناسب جهت افزایش قابلیت درک سیستم و نیز یک راهکار مناسب برای سهولت نگهداری سیستمهای نرمافزاری میباشد. برای خوشهبندی یک سیستم نرمافزاری، ابتدا ساختار سیستم را با یک گراف که به گرافMDGمعروف است، مدل میکنند. در این گراف، راسها بهعنوان پیمانهها و یالها بهعنوان روابط بین پیمانههای سیستم در نظر گرفته میشوند. سپس، این گراف به یک الگوریتم خوشهبندی داده میشود تا به خوشههای معنادار افراز شود. افراز گراف، یک مسئلهNP-Complete میباشد و به همین دلیل الگوریتمهای تقریبی متعددی برای آن گزارش شده است. در این مقاله یک الگوریتم تقریبی برای حل مساله خوشهبندی سیستمهای نرمافزاری پیشنهاد میگردد. این الگوریتم، یک الگوریتم ترکیبی میباشد که از ترکیب اتوماتای یادگیر مهاجرت اشیا و الگوریتم ژنتیک حاصل شده است. نشان داده شده است که با استفادههمزمان از الگوریتمهای ژنتیکی و آتوماتای یادگیر در فرایند جستجو، سرعت رسیدن به جواب افزایش مییابد و همچنین از بدامافتادن الگوریتم در بهینههای محلی جلوگیری میشود. یکی دیگر از نکات مثبت این الگوریتم علاوه بر کیفیت نتایج، پایداری بالایالگوریتم میباشد. به منظور ارزیابی، الگوریتم پیشنهادی با تعدادی از الگوریتمهای موجود مقایسه گردیده است. نتایج آزمایشها نشان از برتری الگوریتم پیشنهادی دارد.

کلیدواژه ها:

آتوماتای یادگیر ، الگوریتم ژنتیکی ، خوشهبندی نرمافزاری ، گراف وابستگی پیمانهای