بهینه سازی رسم گراف دارای چندتابع هدف با الگوریتم ژنتیک

گراف در شاخه های علوم کامپیوترمانند طراحی و نمایش پایگاه داده ها، مهندسی نرم افزار، نمایش داده ها و غیره کاربرد فراوان دارد. ترسیم گراف و نمایش قابل قبول آن یکی از مهم ترین قسمت ها در این گونه سیستم ها می باشد. مسیله رسم گراف به صورت خوانا و قابل فهم را می توان با استفاده از روشهای بهینه سازی با چند تابع هدف حل نمود. معیارهایی چون تعداد برخورد یالها، میزان تقارن رسم، اندازه وضوح زاویه ای ترسیم و غیره را می توان در قالب توابع هدف بهینه سازی نمود. در این مقاله، جهت رسم از روش SPEA که بر الگوریتم ژنتیک استوار است، استفاده شده است. با معرفی معیار آسان و جدید تعادل نیروی وارد برگره ها، در این مقاله شکل های متقارن بیشتری از گراف تولید می شود. همچنین، در محاسبه معیارها شرایط خاصی اعمال شده است که این تغییرات باعث تولید نمونه های بهتری از رسم می گردد. با استفاده از روش بهینه سازی چند تابعی در انتهای یک بار اجرای الگوریتم، چندین رسم بهینه از یک گراف در اختیار کاربر قرار می گیرد. این در حالی است که تعداد نسل مورد نیاز الگوریتم ژنتیک نیز کاهش می یابد.

Keywords:

الگوریتم ژنتیک , الگوریتم SPEA , بهینه سازی با چند تابع هدف , گراف