الگوريتم ژنتيك با جهش آشوبي هوشمند و تركيب چند‌نقطه‌اي مكاشفه‌اي براي حل مسئله رنگ‌آميزي گراف

Genetic Algorithm with Intelligence Chaotic Algorithm and Heuristic Multi-Point Crossover for Graph Coloring Problem

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

Graph coloring is a way of coloring the vertices of a graph such that no two adjacent vertices 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. 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. The crossover and mutation parameters in the proposed algorithm is tuned based on some experiment. To evaluate the proposed algorithm, some experiment is conducted on DIMACS data set. Among DIMACS sample graphs, DSJ, Queen, Le450, Wap 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. 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 (Wap graphs).