سال انتشار: ۱۳۸۳

محل انتشار: دهمین کنفرانس سالانه انجمن کامپیوتر ایران

تعداد صفحات: ۶

نویسنده(ها):

امین فاضل دهکردی – دانشکده مهندسی کامپیوتر دانشگاه صنعتی شریف
کارو لوکس – گروه مهندسی برق و کامپیوتر دانشگاه تهران

چکیده:

دراین مقاله روشی برای مساله رنگ آمیزی گراف با استفاده از الگوریتم pso ارایه شده است PSO یک روش بهینه سازی تکاملی است که ازرفتار اجتماعی گروه پرندگان یا دسته ماهی ها الهام گرفته شده است الگوریتم PSO معمولا برای بهینه سازی توابع غیرخطی با متغیرهای پیوسته به کار می رود در حالیکه در مساله رنگ آمیزی گراف با یک فضای جستجوی گسسته سروکار داریم بنابراین با اعمال تغییراتی در الگوریتم PSO پایه و اضافه کردن توابعی جهت بررسی و نسبت دهی رنگ ها به راس ها ی گراف مورد نظر از آن برای حل مساله رنگآمیزی گراف استفاده شده است. کارایی الگوریتم پیشنهادی به کمک یک مجموعه استاندارد ازمثالهای مساله رنگ امیزی گراف بررسی شده است.