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

  • سال انتشار: 1392
  • محل انتشار: همایش ملی مهندسی کامپیوتر و فناوری اطلاعات
  • کد COI اختصاصی: NCCEB01_027
  • زبان مقاله: فارسی
  • تعداد مشاهده: 2963
دانلود فایل این مقاله

نویسندگان

فاطمه مهدی زاده سماکوش

دانشگاه آزاد اسلامی واحد علوم و تحقیقات آیت ا... آملی،

حمید جزایری

دانشگاه صنعتی نوشیروانی بابل،

مهدی یداللهی

دانشگاه آزاد اسلامی واحد علوم و تحقیقات آیت ا... آملی،

چکیده

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

کلیدواژه ها

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

مقالات مرتبط جدید

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.