عنوان

الگوریتم‌های هوش گروهی در رنگ‌آمیزی گراف

‭۱۳۶۴۰پ‬

per

الگوریتم‌های هوش گروهی در رنگ‌آمیزی گراف

/اصغر نافع مرکید

: پردیس

، ‮‭۹۴‬

چاپی

کارشناسی ارشد

مهندسی‌کامپیوترگرایش هوش مصنوعی

‮‭۱۳۹۴/۰۲/۰۹‬

تبریز

مساله‌صی رنگ‌صآمیزی گراف یکی از مسائل بهینه سازی است که الگوریتم‌صهای زیادی درباره‌صی آن ارائه شده است .این مساله چه از لحاظ تئوری و چه از لحاظ الگوریتمی بسیار مورد بررسی قرار گرفته است .از انواع مختلف الگوریتم‌صها برای رنگ‌صآمیزی گراف می توان به الگوریتم‌صهای دقیق، یافتاری، متایافتاری و ... اشاره نمود .در حقیقت می توان گفت با ارائه‌صی هر رده از الگوریتم‌صها، رنگ‌صآمیزی گراف به نوعی توسط آن مورد بررسی قرار گرفته و نتایج متفاوتی نیز ارائه گردیده شده، هوش گروهی یکی از رده‌صهای الگوریتم‌صهای متایافتاری می باشد که اساس آن الهام گرفته شده از زندگی جمعی جانداران مانند مورچه‌صها، زنبورها، پرندگان و ... می باشد .این رده از الگوریتم‌صها را می‌صتوان جزء جدیدترین الگوریتم‌صهای ارائه شده برای مسائل بهینه سازی عنوان کرد که به صورت گسترده در زمینه‌صی رنگ‌صآمیزی گراف نیز مورد استفاده قرار گرفته‌صاند .الگوریتم ‮‭ABC‬ یکی از الگوریتم‌صهای این رده می باشد که به تازگی مطرح گردیده است .این الگوریتم در نسخه‌صی ابتدایی خود برای حل مسائل پیوسته، طراحی شده و نتایج بسیار قابل توجهی را ارائه داده است .با توجه به اینکه مساله‌صی رنگ‌صآمیزی گراف یک مساله‌صی گسسته می باشد، در این پایان‌صنامه الگوریتم ‮‭ABC‬ پایه با تغییراتی در آن برای حل مسائل ترکیبی همچون رنگ‌صآمیزی گراف، مهیا شده است .نتایج حاصله نشان می‌صدهد که تغییرات صورت گرفته در ‮‭ABC‬ پایه اثر بخش بوده و نتایج حاصله از آن برای رنگ‌صآمیزی گراف قابل توجه می‌صباشد

heuristic algorithms is swarm intelligence. These algorithms were inspired by life of some insects like ants, bees and etc. These algorithms are new and widely used for GCP. Artificial bee colony (ABC) is an algorithm in this group and in better word it is one of the newest one in this group of algorithms. This algorithm was designed for continuous problems and show very good results in this type of problems. But because the GCP is a combinatorial problem, in this thesis some changes have been done on the ABC so that it has been prepared to solving graph coloring problem. The results of proposed algorithm shows, the c -heuristic algorithms. In fact we can say that all heuristic types of algorithms have been used for GCP. One group of meta- Graph coloring problem (GCP) is one of the most studied combinatorial optimization problems. It is important in theory and practice. There have been many algorithms for graph coloring problem, including exact algorithms and meta

نافع مرکید، اصغر، پژوهشگر

بالافر، محمد علی، استاد راهنما

رضوی، سید ناصر، استاد مشاور

سیاه و سفید

نمایه‌سازی قبلی