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

در این مقاله از الگوریتم رقابت استعماری برای حل مسئله یافتن بزرگترین زیر گراف کامل استفاده شده است. مسئله یافتن بزرگترین زیر گراف کامل یکی از مسائل NP-Hard است که در کاربرهای عملی همچون داده کاوی، نظریه کد گذاری، شبکه های اجتماعی مورد استفاده قرار میگیرد. در سالهای اخیر الگوریتم های هوش جمعی برای حل این مسئله به کاررفته است اما به دلیل اینکه الگوریتم رقابت استعماری همگرایی سریع به پاسخ دارد، از این الگوریتم به کار گرفته شده است. الگوریتم پیشنهادی بر روی 39 گراف از گراف های استاندار برای مسئله یافتن بزرگترین گراف کامل،DIMACS شبیه سازی شده است. نتایج نشان میدهد حدود 74% گرافها، الگویتم پیشنهادی میتواند بزرگترین زیر گراف کامل را پیدا کند و برای گراف های که نمیتواند بزرگترین زیر گراف کامل را پیدا کند، بهترین جواب را دارد. همچنین میانگین اندازه زیر گراف کامل هم در برخی از گرافها بهبود یافته است.

Keywords:

الگوریتم رقابت استعماری , مسئله یافتن بزرگترین زیر گراف کامل , NP-Hard , بهینه سازی