مشخصات مقاله

عنوان: 

الگوريتم نوين جهت رنگ آميزي گراف با استفاده از آتوماتاي يادگير

نوع ارائه: پوستر
نویسنده: مطيع قادر حبيب,ميرزايي ثمرين عباس,دادجويان علي اكبر
 
 
 
عنوان همایش: كنفرانس ملي سالانه انجمن كامپيوتر ايران
نوع همایش:  انجمن هاي علمي
حامی: انجمن کامپیوتر ایران، مرکز توسعه فن آوری نیرو (متن)
زمان:  1388دوره 15
 
 
چکیده: 

رنگ آميزي گراف يکي از مسايل Np-Complete به شمار ميرود. يکي از کاربردهاي اين مساله رنگ آميزي نقشه ها است. در اين مقاله يک الگوريتم جديد براي رنگ آميزي گراف با استفاده از آتوماتاي يادگير پيشنهاد ميشود. فرآيند يادگيري با تعدادي از آتوماتاهاي تصادفي شروع ميشود. هر آتوماتا به تنهايي نمايش دهنده يک رنگ آميزي تصادفي ميباشد. با تکرار فرآيند يادگيري رنگ آميزي بهبود مييابد. در مقايسه با الگوريتمهاي ژنتيک، الگوريتم پيشنهادي سريعتر به جواب نزديک به بهينه ميرسد. دليل آن اين است که الگوريتمهاي ژنتيک به دنبال کروموزوم بهينه از ميان جمعيتها هستند و به جايگاه ژنها در کروموزومها اهميت داده نميشود ولي در الگوريتم پيشنهادي سعي ميشود تا با استفاده از آتوماتاي مهاجرت اشياء جايگاه بهينه ژنها مشخص شود. الگوريتم پيشنهادي در تعداد مراحل تکرار يادگيري کمتري در مقابل تعداد نسل الگوريتم ژنتيک به جواب بهينه نزديک ميشود. نتايج شبيه سازي حاصل از الگوريتم پيشنهادي بر روي گرافهاي مطرح با الگوريتم ژنتيک مورد مقايسه قرار گرفته است.

 
كليد واژه: آتوماتاي يادگير، آتوماتاي مهاجرت اشيا، رنگ آميزي گراف
 
مقالات نشریه ای مرتبط: 
 
مقالات همایشی مرتبط: 
 
بازدید یکساله 57   pdf-file
 
tabligh

moavenatelmi
آخرین های بلاگ
ورود به بلاگ مرکز اطلاعات علمی