PDA

View Full Version : سوال: رنگ آميزی گراف به کمک الگوريتم ژنتيک



darioush01
دوشنبه 30 دی 1387, 23:03 عصر
سلام
من می خوام مسئله رنگ آميزی گراف رو با کمک الگوريتم ژنتيک پياده سازی کنم . می دونم الگوريتم ژنتيک چطوريه اما نمی دونم در اين مسئله اون رو چطور بايد به کار بگيرم يعنی الان کروموزوم چي ميشه ؟ ميشه کمکم کنين . ممنون ميشم . راهنمايی شما می تونه واسه استارت کار کمک بزرگی باشه .

darioush01
چهارشنبه 02 بهمن 1387, 16:40 عصر
يعنی کسی نيست چيزی بدونه ؟؟؟

BOB
دوشنبه 07 بهمن 1387, 10:15 صبح
سلام

مثلا ميتوان هر كروموزوم را به عنوان مجموعه گره‌هاي گراف در نظر گرفت. يعني براي يك گراف با N گره، كروموزومي با طول N (داراي تعداد N ژن) در نظر گرفته و مقادير هر ژن نيز بيانگر يكي از رنگهاي مورد استفاده باشند.
حال با جابه‌جايي ژنها در كروموزوم بوسيله الگوريتم ژنتيك، مي‌توان به آرايش و تركيبي بهينه رسيد كه در آن هيچ دو گره‌ مجاوري داراي رنگ يكسان نباشند.

اين مسئله (Graph coloring) شباهت بسياري به مسئله فروشنده دورهگرد (TSP) دارد. مسئله Tsp به عنوان يكي از معروف ترين مسائل مشكل، داراي محيط و فرضيات بسيار ساده‌اي بوده كه به همين دليل به دفعات و با استفاده از الگوريتمهاي مختلف، راه حلهاي متفاوتي براي آن ارائه شده است.

تقريبا اكثر راه‌حلهاي ارائه شده براي Tsp به Graph coloring نيز قابل تعميم هستند.

يك نمونه پياده سازي رنگ آميزي گراف با ژنتيك:
http://www.genetic-programming.org/sp2003/Shen.pdf

موفق باشيد

BOB
یک شنبه 20 بهمن 1387, 11:20 صبح
سلام

در تكميل اين بحث، فكر ميكنم سريعترين راه پياده‌سازي گراف اين مسئله استفاده از ماتريس مجاورت (W[i, j] = Matrix N*N) است.
پس از آن هم مهمترين قسمت برنامه، طراحي تابع برازش Fitness مسئله است.

اصولا در تمام مسائل حل شده با GA مهمترين بخش از همه آنها طراحي تابعي مناسب، دقيق، سريع و كم هزينه براي برازش كروموزومهاست و در واقع مهمترين دليل واگرا شدن نسلها و به پاسخ نرسيدن احتمالي الگوريتم، وجود نقص در اين تابع مي‌باشد.

يك تابع برازش بايد بتواند هم در نسلهاي اوليه (كه كروموزومها با يكديگر تفاوت بيشتري داشته) برازندگي را تشخيص داده و هم در نسلهاي بعدي كه كروموزومها شباهت زيادي به يكديگر پيدا كرده و ميزان اختلاف آنها ناچيز ميشود.

براي اين مسئله احتمالا استفاده از "تعداد كل رنگهاي تكراري = A" و "تعداد رنگهاي تكراري همجوار = B" و "تعداد رنگهاي مورد استفاده = C" به اين شكل مناسب باشد:




Rank[i] = (B[i]+1) / (A[i]+2) + C[i] * (B[i]+1)
P[i] = (Sigma(Rank) - Rank[i]) / Sigma(Rank)



كه مقادير ثابت 1 و 2 به دليل جلوگيري از صفر شدن A و B در حالات خاص و خطاي محاسباتي مورد استفاده قرار گرفته‌اند و P احتمال برازش بدست آمده براي هر كروموزوم خواهد بود.