حل مسئله همانندی گرافی با استفاده از الگوریتم ژنتیک و الگوریتم ACO

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

کلیدواژه ها:

الگوریتم ژنتیک ، الگوریتم ACO ، همانندی گرافی