این سایت در حال حاضر پشتیبانی نمی شود و امکان دارد داده های نشریات بروز نباشند
پردازش علائم و داده ها، جلد ۱۴، شماره ۲، صفحات ۷۵-۹۶
عنوان فارسی الگوریتم ژنتیک با جهش آشوبی هوشمند و ترکیب چند‌نقطه‌ای مکاشفه‌ای برای حل مسئله رنگ‌آمیزی گراف
چکیده فارسی مقاله تخصیص مقدار رنگی را به هر یک از گره‌های گراف، به‌گونه‌ای که هیچ دو گره مجاوری دارای رنگ یکسانی نباشد و کمترین مقدار رنگی استفاده شود، مسئله رنگ‌آمیزی گراف گویند. این مسئله به‌عنوان یکی از مسائل NP-hard شناخته می‌شود که کاربردهای مختلفی در زمینه تخصیص پهنای باند، اختصاص حافظه به برنامه‌ها و همچنین، طراحی مدارهای مجتمع دارد. در مقاله حاضر، از الگوریتم ژنتیک و پدیده آَشوب برای حل این مسئله استفاده شده است. در روش پیشنهادی حاضر، عمل‌گر ترکیب چند‌نقطه‌ای مکاشفه‌ای به نام CMHn معرفی شده است. این عمل‌گر، با انتخاب چند نقطه برش در والدین و معتبر‌کردن یکی از زیر بخش‌های والدین (دومین زیربخش هر والد می‌تواند معتبر یا غیر معتبر باشد) آنها را با هم، با استفاده از روشی ابتکاری ترکیب می‌کند. برای اینکه بتوان از بهینه محلی فرار کرد و همچنین، برای یافتن فضای جستجوی جدید، از عمل‌گر جهش استفاده می‌شود. در این مقاله، عمل‌گر جهش آشوبی هوشمند معرفی شده است که با استفاده از فرمولی گره‌هایی را که برای جهش مناسب‌ترند، انتخاب و بر روی آنها جهش را اعمال می‌کند. همچنین، نیمی از جمعیت اولیه با استفاده از روش ابتکاری و نیمی از آن با روش تصادفی تولید شده است. به‌منظور ارزیابی الگوریتم پیشنهادی از نمونه گراف‌های DIMACS و Queen استفاده شده است. نتایج به‌دست‌آمده نشان می‌دهد که روش پیشنهادی در بیش‌تر گراف‌ها، به‌خصوص گراف‌های بسیار بزرگ (wap) و گراف‌های Queen جواب بهتری نسبت به تحقیقات مشابه ارائه می‌دهد.
کلیدواژه‌های فارسی مقاله
عنوان انگلیسی Genetic Algorithm with Intelligence Chaotic Algorithm and Heuristic Multi-Point Crossover for Graph Coloring Problem
چکیده انگلیسی مقاله 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).   
کلیدواژه‌های انگلیسی مقاله
نویسندگان مقاله سید علی ساداتی تیله بنی | seyyed ali sadati tileboni
دانشگاه صنعتی نوشیروانی بابل
سازمان اصلی تایید شده: دانشگاه صنعتی نوشیروانی بابل (Babol noshirvani university of technology)

حمید جزایری | hamid jazayeriy
دانشگاه صنعتی نوشیروانی بابل
سازمان اصلی تایید شده: دانشگاه صنعتی نوشیروانی بابل (Babol noshirvani university of technology)

مجتبی ولی نتاج | mojtaba valinataj
دانشگاه صنعتی نوشیروانی بابل
سازمان اصلی تایید شده: دانشگاه صنعتی نوشیروانی بابل (Babol noshirvani university of technology)

نشانی اینترنتی http://jsdp.rcisp.ac.ir/browse.php?a_code=A-10-800-1&slc_lang=fa&sid=fa
فایل مقاله اشکال در دسترسی به فایل - ./files/site1/rds_journals/1315/article-1315-570068.pdf
کد مقاله (doi)
زبان مقاله منتشر شده fa
موضوعات مقاله منتشر شده مقالات پردازش داده‌های رقمی
نوع مقاله منتشر شده پژوهشی
برگشت به: صفحه اول پایگاه   |   نسخه مرتبط   |   نشریه مرتبط   |   فهرست نشریات