سال انتشار: ۱۳۸۶

محل انتشار: پانزدهیمن کنفرانس مهندسی برق ایران

تعداد صفحات: ۸

نویسنده(ها):

مصطفی حقیرچهرقانی – گروه تحقیقاتی پایگاه داده ها، مرکز کنترل و پردازش هوشمند، دانشکده بر
مسعود رهگذر – گروه تحقیقاتی پایگاه داده ها، مرکز کنترل و پردازش هوشمند، دانشکده بر
کارو لوکس – گروه تحقیقاتی پایگاه داده ها، مرکز کنترل و پردازش هوشمند، دانشکده بر

چکیده:

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