دانلود سورس هوش مصنوعی رنگ آمیزی گراف با ژنتیک در #C

دانلود سورس هوش مصنوعی رنگ آمیزی گراف با ژنتیک در #C

در این سورس، پروژه هوش مصنوعی رنگ آمیزی راسی گراف با استفاده از تکنیک الگوریتم ژنتیک را مشاهده میکنید که با زبان سی شارپ #C خیلی جالب نوشته شده است.

مساله رنگ آمیزی گراف

مساله بهینه سازی رنگ آمیزی گراف تعیین حداقل تعداد رنگهای مورد نیاز برای رنگامیزی راس های گرافی معین است به گونه ای که هیچ راس مجاوری هم رنگ نباشند و این عدد مورد نظر را عدد کروماتیک گراف میگوییم.

تصمیم گیری رنگ آمیزی گراف آن است که برای یک عدد صحیح M داده شده تعیین کنیم آیا رنگ آمیزی وجود دارد که حداکثر از این M رنگ استفاده کرده و هیچ دو راس مجاوری هم رنگ نباشند. الگوریتم های زیادی مانند روش عقبگرد، شمارش فضای حالت و ... برای حالتهای تصمیم و بهینه سازی ارائه شده اند که از مرتبه چند جمله ای پیدا نشده است. در اینجا با استفاده از الگوریتم ژنتیک راه حل های بهینه ای را برای این مساله ارائه میدهیم.

الگوریتم ژنتیک

الگوریتم ژنتیک  یا (GA)  از استراتژی های جست وجوی محلی و شکلی از "جست وجوی پرتوی اتفاقی" است که در آن حالتهای پسین از طریق ترکیب دو حالت والد تولید میشود. الگوریتم ژنتیک  با مجموعه ای از k حالت که بطور تصادفی تولید شده اند، شروع میکند که جمعیت نام دارد. هر حالت یا فرد بصورت رشته ای بر روی الفبای متناهی نمایش داده میشود. هر حالت توسط یک "تابع هدف" یا یک تابع برازش ارزیابی میشود. تابع برازش باید برای حالتهای بهتر، مقادیر بزرگتری را برگرداند. در شکل خاصی از الگوریتم ژنتیک (مانند مسئله هشت وزیر) احتمال انتخاب برای تولیدمثل مستقیما متناسب با امیتاز برازش است. در ادامه حل مسئله به روش الگوریتم ژنتیک، دو زوج بطور تصادفی برای تولید مثل انتخاب میشوند. برای هر زوجی که باید جفت گیری کنند، یک نقطه پیوند بطور تصادفی بین موقعیت ها انتخاب میشود.

نظریه های الگوریتم های ژنتیک  توضیح میدهند که این کار چگونه با استفاده از ایده ی الگو انجام میشود. الگو زیر رشته ای است که بعضی از موقعیت های آن مشخص نشده باقی میمانند. رشته هایی که با الگو مطابقت میکنند نمونه هایی از الگو نامیده میشوند.  الگوریتم های ژنتیک وقتی به خوبی کار میکنند که الگوها متناظر با قطعات با معنایی از جواب باشند.  

پیاده سازب برنامه رنگامیزی راسی با تکنیک genetic

در اجرای این برنامه جالب، ابتدا رئوس و یالهای گراف ساخته میشوند. سپس آرایه ای جهت نگهداری جمعیت اولیه، آرایه ای برای نگهداری جمعیت موقت ناشی از ترکیب و متغیری برای ذخیره تعداد کرموزوم ها که بین 50 تا 100 تصادفی انتخاب میشود، تعریف شده اند. در ادامه برنامه  تابعی برای ایجاد جمعیت اولیه، تابع ارزیاب جهت بررسی تک تک کروموزوم ها یا همان جواب ها، بررسی تک تک ژن های هر کروموزوم و بررسی ژن فعلی با سایر ژن ها جهت پیدا کردن تقاطع رنگ و همچنین چک کردن همرنگ بودن رئوس مجاور نوشته شده اند. 

در آخر لیست کروموزوم ها بر اساس کمترین تداخل رنگ امیتازبندی شده و نشان داده میشوند و  تابع ترکیب به روش تک نقطه ای و تابع جهش به روش تعویض و همچنین تابع جایگزینی جمعیت​ رو ی آنها اجرا میشود.

لازم به ذکر است، توضیحات کامل در کدهای برنامه نیز نوشته شده است.

سورس پروژه هوش مصنوعی رنگ آمیزی گراف با الگوریتم ژنتیک را پس از پرداخت اینترنتی دانلود نمایید

حجم فایل : 80  KB