ارائه ی یک روشجدید مبتنی برالگوریتم زنبور برای رنگآمیزی گراف
- سال انتشار: 1392
- محل انتشار: اولین همایش منطقه ای بهینه سازی و روش های محاسبه نرم در مهندسی برق و کامپیوتر
- کد COI اختصاصی: ELECOM01_110
- زبان مقاله: فارسی
- تعداد مشاهده: 1171
نویسندگان
، دانشجوی کارشناسی ارشد مهندسی کامپیوتر، دانشگاه آزاد اسلامی واحد شبستر
استادیار گروه کامپیوتر، دانشکده فنی مهندسی، دانشگاه بوعلی سینا، همدان
استادیار گروه کامپیوتر، دانشکده فنی مهندسی، دانشگاه آزاد اسلامی واحد شبستر
چکیده
مسئله رنگآمیزی گراف، عبارت است از رنگآمیزی یک گراف بدون جهت، با استفاده از حداقل K رنگ مختلف ، به طوری که هیچ دو راس مجاوری همرنگ نباشند و یکی از قدیمیترین و مشهورترین مسائل در تئوری گراف است که امروزه کاربردهای متعددی در مسائل مختلف دارد. مسئله رنگآمیزی به عنوان یک مسئله NP-Hard است، بنابراین استفاده از روشهای قطعی جهت پیدا کردن جواب قابل قبول برای آن، مناسب نمیباشند. لذا، روشهای هوش مصنوعی و پردازش تکاملی، برای پیدا کردن جواب قابل قبول مورد استفاده قرار میگیرد. در این مقاله یک روش جدید مبتنی بر هوش ازدحامی به نام الگوریتم کلونی زنبور (ABCGC) برای مسئلهی رنگآمیزی گراف ارائه شده است. یکی از الگوریتمهای موجود ارائه شده برای رنگ آمیزی گراف، استفاده از الگوریتم مبتنی بر مورچه (ABAC) برای رنگآمیزی می باشد. از این رو در این مقاله برای ارزیابی الگوریتم پیشنهادی، آن را با الگوریتم مبتنی بر مورچه (ABAC) مقایسه کردیم و نتایج محاسباتی بر روی نمونههای آزمایشی بیانگر بهبود این الگوریتم نسبت به الگوریتم ABAC برای مسئله رنگآمیزی گراف میباشد.کلیدواژه ها
رنگآمیزی گراف، الگوریتم کلونی زنبور، الگوریتم مبتنی بر مورچه، هوش ازدحامیمقالات مرتبط جدید
اطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.