fa الگوریتم ژنتیک با جهش آشوبی هوشمند و ترکیب چند‌نقطه‌ای مکاشفه‌ای برای حل مسئله رنگ‌آمیزی گراف مقالات پردازش داده‌های رقمی Paper پژوهشي Research <p class="AuthorName" dir="RTL" style="margin-bottom:0in;margin-bottom:.0001pt; text-indent:0in"><b><span b="" lang="FA" style="font-family:">تخصیص مقدار رنگی را به هر یک از گره‌های گراف، به‌گونه‌ای که هیچ دو گره مجاوری دارای رنگ یکسانی نباشد و کمترین مقدار رنگی استفاده شود، مسئله رنگ‌آمیزی گراف گویند. این مسئله به‌عنوان یکی از مسائل </span></b><span dir="LTR">NP-hard</span><span dir="RTL"></span><span dir="RTL"></span><b><span b="" lang="FA" style="font-family:"><span dir="RTL"></span><span dir="RTL"></span> شناخته می‌شود که کاربردهای مختلفی در زمینه تخصیص پهنای باند، اختصاص حافظه به برنامه‌ها و همچنین، طراحی مدارهای مجتمع دارد. در مقاله حاضر، از الگوریتم ژنتیک و پدیده آَشوب برای حل این مسئله استفاده شده است. در روش پیشنهادی حاضر، عمل‌گر ترکیب چند‌نقطه‌ای مکاشفه‌ای به نام </span></b><span dir="LTR">CMHn</span><span dir="RTL"></span><span dir="RTL"></span><b><span b="" lang="FA" style="font-family:"><span dir="RTL"></span><span dir="RTL"></span> معرفی شده است. این عمل‌گر، با انتخاب چند نقطه برش در والدین و معتبر‌کردن یکی از زیر بخش‌های والدین (دومین زیربخش هر والد می‌تواند معتبر یا غیر معتبر باشد) آنها را با هم، با استفاده از روشی ابتکاری ترکیب می‌کند. برای اینکه بتوان از بهینه محلی فرار کرد و همچنین، برای یافتن فضای جستجوی جدید، از عمل‌گر جهش استفاده می‌شود. در این مقاله، عمل‌گر جهش آشوبی هوشمند معرفی شده است که با استفاده از فرمولی گره‌هایی را که برای جهش مناسب‌ترند، انتخاب و بر روی آنها جهش را اعمال می‌کند. همچنین، نیمی از جمعیت اولیه با استفاده از روش ابتکاری و نیمی از آن با روش تصادفی تولید شده است. به‌منظور ارزیابی الگوریتم پیشنهادی از نمونه گراف‌های </span></b><span dir="LTR">DIMACS</span><span dir="RTL"></span><span dir="RTL"></span><b><span b="" style="font-family: "><span dir="RTL"></span><span dir="RTL"></span> <span lang="FA">و </span></span></b><span dir="LTR">Queen</span><span dir="RTL"></span><span dir="RTL"></span><b><span b="" style="font-family:"><span dir="RTL"></span><span dir="RTL"></span> <span lang="FA">استفاده شده است. نتایج به‌دست‌آمده نشان می‌دهد که روش پیشنهادی در بیش‌تر گراف‌ها، به‌خصوص گراف‌های بسیار بزرگ (</span></span></b><span dir="LTR">wap</span><span dir="RTL"></span><span dir="RTL"></span><b><span b="" lang="FA" style="font-family:"><span dir="RTL"></span><span dir="RTL"></span>) و گراف‌های </span></b><span dir="LTR">Queen</span><span dir="RTL"></span><span dir="RTL"></span><b><span b="" style="font-family:"><span dir="RTL"></span><span dir="RTL"></span> <span lang="FA">جواب بهتری نسبت به تحقیقات مشابه ارائه می‌دهد.</span></span></b></p> <p><strong>Graph coloring is a way of coloring the vertices of a graph such that no two adjacent&nbsp;</strong><a href="https://en.wikipedia.org/wiki/Vertex_(graph_theory)" title="Vertex (graph theory)"><strong>vertices</strong></a><strong> have the same color. Graph coloring problem (GCP) is about finding the smallest number of colors needed to color a given graph. The smallest number of colors needed to color a graph G, is called its chromatic number. GCP is a well-known NP-hard problems and, therefore, heuristic algorithms are usually used to solve it. GCP has many applications such as: bandwidth allocation, register allocation, VLSI design, scheduling, Sudoku, map coloring and so on. </strong><br> <strong>We try genetic algorithm (GA) and chaos theory to solve GCP. We proposed a heuristic algorithm called CMHn to implement multi-point crossover operation in GA. To generate initial population, a fast greedy algorithm is used. In this algorithm, the degree of each node and the number colors in its neighbor is used to assign a color to each node. Mutation operation in GA is used to explore the search space and scape from the local optima. In this study, a chaotic mutation operation is presented to select some vertices and change their color.&nbsp; The crossover and mutation parameters in the proposed algorithm is tuned based on some experiment.</strong><br> <strong>To evaluate the proposed algorithm, some experiment is conducted on DIMACS</strong><strong> data set. Among DIMACS sample graphs, <em>DSJ, Queen, Le450, Wap</em> are well-known challenging samples for graph coloring. The proposed algorithm is executed 10 times on each sample and the best, worst and mean results are reported.</strong><br> <strong>Results show that the proposed algorithm can effectively solve GCP and have comparable outcome with the recent studies in this field. The proposed method outperforms other algorithms on very large graphs (<em>Wap</em> graphs).&nbsp;</strong><br> &nbsp;</p> مسئله رنگ‌آمیزی گراف, الگوریتم ژنتیک, روش ابتکاری, ترکیب چند نقطه‌ای مکاشفه‌ای, جهش آشوبی هوشمند Graph coloring problem, genetic algorithm, heuristics, multi-point crossover, chaotic mutation 75 96 http://jsdp.rcisp.ac.ir/browse.php?a_code=A-10-800-1&slc_lang=fa&sid=1 Seyyed Ali Sadati Tileboni سید علی ساداتی تیله بنی seyyedali.sadati@nit.ac.ir 10031947532846005470 10031947532846005470 No دانشگاه صنعتی (نوشیروانی) بابل Hamid Jazayeriy حمید جزایری jhamid@nit.ac.ir 10031947532846005471 10031947532846005471 Yes دانشگاه صنعتی (نوشیروانی) بابل Mojtaba Valinataj مجتبی ولی نتاج m.valinataj@nit.ac.ir 10031947532846005472 10031947532846005472 No دانشگاه صنعتی (نوشیروانی) بابل