یک روش ترکیبی برای حل مساله تناظر گراف

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

Keywords:

تناظر گراف , آتاماتاهای یادگیر , الگوریتم های ژنتیک