استفاده از الگوريتم هاي تكاملي با ساختار كروموزوم دوپارچه براي حل مسأله رنگ آميزي گراف
در اين مقاله، چندين روش تكاملي براي حل مسأله رنگ آميزي گراف معرفي مي شود. روش هاي تكاملي ارائه شده، براي حل اين مسأله مبتني بر ساختار كروموزوم دوپارچه متشكل از قسمت مشخص كننده ترتيب رنگ آميزي و قسمت مشخص كننده استراتژي رنگ آميزي مي باشد. بر طبق نتايج آزمايشات، روش چند عضوي داراي جهش هوشمند كه در آن جمعيت هر نسل تنها از فرزندان نسل قبلي توليد مي شوند، برتر از ديگر رو شها بوده است. آزمايشات بر روي 6 گراف از 3 سري متفاوت گراف هاي استاندارد مسابقات dimacs انجام گرفته است. در مقايسه با نتايج برنامه هاي شركت كرده در اين مسابقات، نتايج حاصل از بهترين روش ارائه شده، رضايت بخش است و غير از يك برنامه، از ساير برنامه ها بهتر بوده است. ضمن آنكه از مزاياي اين كار نسبت به الگوريتمهاي تكاملي ارائه شده قبلي، اين است كه در اينجا، نيازي به اجراي متوالي برنامه با تعداد رنگ هاي متفاوت نيست، همچنين، ساختار كامل تر كروموزوم، كه بيان كننده رنگ آميزي يكتا از گراف است، و عملگر جهش مبتني بر دانش مسأله از ديگر ويژگي هاي آن است.
|