دوره 14، شماره 2 - ( 6-1396 )                   جلد 14 شماره 2 صفحات 75-96 | برگشت به فهرست نسخه ها



DOI: 10.18869/acadpub.jsdp.14.2.75

XML English Abstract Print


Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Sadati Tileboni S A, Jazayeriy H, Valinataj M. Genetic algorithm with intelligence chaotic algorithm and heuristic multi-point crossover to graph coloring problem. JSDP. 2017; 14 (2) :75-96
URL: http://jsdp.rcisp.ac.ir/article-1-392-fa.html
ساداتی تیله بنی سید علی، جزایری حمید، ولی نتاج مجتبی. الگوریتم ژنتیک با حهش آشوبی هوشمند و ترکیب چند نقطه‌ای مکاشفه‌ای برای حل مسئله‌ی رنگ‌آمیزی گراف. پردازش علائم و داده‌ها. 1396; 14 (2) :75-96

URL: http://jsdp.rcisp.ac.ir/article-1-392-fa.html


دکتری - استادیار دانشگاه صنعتی (نوشیروانی) بابل
چکیده:   (162 مشاهده)

تخصیص مقدار رنگی به هر یک از گره‌های گراف، به گونه‌ای که هیچ دو گره‌ی مجاوری دارای رنگ یکسانی نباشد و کمترین مقدار رنگی استفاده شود را مسئله‌ی رنگ‌آمیزی گراف گویند. این مسئله به عنوان یکی از مسائل NP-hard شناخته می‌شود که کاربردهای مختلفی در زمینه‌ی تخصیص پهنای باند، اختصاص حافظه به برنامه‌ها و همچنین، طراحی مدارهای مجتمع دارد. در مقاله‌ی حاضر، از الگوریتم ژنتیک و پدیده‌ی آَشوب برای حل این مسئله استفاده شده است. در روش پیشنهادی حاضر، عملگر ترکیب چند نقطه‌ای مکاشفه‌ای به نام CMHn معرفی شده است. این عملگر، با انتخاب چند نقطه‌ی برش در والدین و معتبر کردن یکی از زیر بخش‌های والدین (دومین زیربخش هر والد می‌تواند معتبر یا غیر معتبر باشد) آنها را با هم، با استفاده از روشی ابتکاری ترکیب می‌کند. برای این‌که بتوان از بهینه‌ی محلی فرار کرد و همچنین، برای یافتن فضای جستجوی جدید، از عملگر جهش استفاده می‌شود. در این مقاله، عملگر جهش آشوبی هوشمند معرفی شده است که با استفاده از فرمولی گره‌هایی که برای جهش مناسب‌ترند را انتخاب و بر روی آنها جهش را اعمال می‌کند. همچنین، نیمی از جمعیت اولیه با استفاده از روش ابتکاری و نیمی از آن با روش تصادفی تولید شده‌اند. به منظور ارزیابی الگوریتم پیشنهادی از نمونه گراف‌های DIMACS استفاده شده است. نتایج بدست آمده نشان می‌دهد که روش پیشنهادی در اکثر گراف‌ها، به خصوص گراف‌های بسیار بزرگ (wap)، جواب بهتری نسبت به تحقیقات مشابه ارائه می‌دهد.

متن کامل [PDF 6922 kb]   (66 دریافت)    
نوع مطالعه: پژوهشي | موضوع مقاله: مقالات پردازش داده‌های رقمی
دریافت: ۱۳۹۴/۴/۱۶ | پذیرش: ۱۳۹۵/۱۲/۱۵ | انتشار: ۱۳۹۶/۷/۲۹ | انتشار الکترونیک: ۱۳۹۶/۷/۲۹

ارسال نظر درباره این مقاله : نام کاربری یا پست الکترونیک شما:
کد امنیتی را در کادر بنویسید

ارسال پیام به نویسنده مسئول


کلیه حقوق این وب سایت متعلق به فصل‌نامة علمی - پژوهشی پردازش علائم و داده‌ها می باشد.