بررسی الگوریتم ژنتیک ترکیبی افزایشی با مسئله یک‌ریختی زیرگراف
ترجمه نشده

بررسی الگوریتم ژنتیک ترکیبی افزایشی با مسئله یک‌ریختی زیرگراف

عنوان فارسی مقاله: بررسی الگوریتم ژنتیک ترکیبی افزایشی با مسئله یک‌ریختی زیرگراف
عنوان انگلیسی مقاله: Investigation of incremental hybrid genetic algorithm with subgraph isomorphism problem
مجله/کنفرانس: ازدحام و محاسبات تکاملی - Swarm And Evolutionary Computation
رشته های تحصیلی مرتبط: کامپیوتر
گرایش های تحصیلی مرتبط: مهندسی الگوریتم ها و محاسبات، محاسبات ابری
کلمات کلیدی فارسی: الگوریتم ژنتیک افزایشی، الگوریتم ژنتیک ترکیبی، مسئله یک‌ریختی زیرگراف
کلمات کلیدی انگلیسی: Incremental genetic algorithm، Hybrid genetic algorithm، Subgraph isomorphism problem
نوع نگارش مقاله: مقاله پژوهشی (Research Article)
نمایه: Scopus - Master Journals List - JCR
شناسه دیجیتال (DOI): https://doi.org/10.1016/j.swevo.2019.05.004
دانشگاه: School of Computer Science and Engineering, Seoul National University, 1 Gwanak-ro, Gwanak-gu, Seoul, 08826, Republic of Korea
ناشر: الزویر - Elsevier
نوع ارائه مقاله: ژورنال
نوع مقاله: ISI
سال انتشار مقاله: 2019
ایمپکت فاکتور: 7/893 در سال 2018
شاخص H_index: 43 در سال 2019
شاخص SJR: 1/278 در سال 2018
شناسه ISSN: 2210-6502
شاخص Quartile (چارک): Q1 در سال 2018
فرمت مقاله انگلیسی: PDF
تعداد صفحات مقاله انگلیسی: 12
وضعیت ترجمه: ترجمه نشده است
قیمت مقاله انگلیسی: رایگان
آیا این مقاله بیس است: خیر
آیا این مقاله مدل مفهومی دارد: ندارد
آیا این مقاله پرسشنامه دارد: ندارد
آیا این مقاله متغیر دارد: ندارد
کد محصول: E13124
رفرنس: دارای رفرنس در داخل متن و انتهای مقاله
فهرست انگلیسی مطالب

Abstract


1- Introduction


2- Backgrounds


3- Incremental genetic algorithm


4- Genetic framework


5- Experimental results


6- Conclusion


References

نمونه متن انگلیسی مقاله

Abstract


Graph pattern matching is a key problem in many applications which data is represented in the form of a graph, and this problem is generally defined as a subgraph isomorphism. In this paper, we analyze an incremental hybrid genetic algorithm for the subgraph isomorphism problem considering various design issues to improve the performance of the algorithm. An incremental hybrid genetic algorithm was previously suggested to solve the subgraph isomorphism problem and have shown good performance. It decomposes the problem into a sequence of consecutive subproblems which has an optimal substructure. Each subproblem is solved by the hybrid genetic algorithm and the solutions obtained are extended to be applied to the next subproblem as initial solutions. We examine a wide range of schemes that determine the overall performance of the incremental process and make a number of experiments to verify the effectiveness of each scheme with the synthetic dataset of random graphs. We show that the performance of incremental approach can be significantly improved compared to the previous representative studies by applying appropriate schemes found by the experiments. In addition, we also investigate the effect of different genetic parameters and identify the scalability of our method by conducting experiments using real world dataset with large-sized graphs.


Introduction


Graph is a simple and universal data representation to model pairwise relationships among a set of objects. One of the interesting problems encountered when handling graph data is a graph pattern matching arising from pattern recognition, knowledge discovery, biology, cheminformatics, dynamic network traffic and intelligence analysis [1–4]. And this matching is typically formulated in terms of the subgraph isomorphism problem. Given two graphs G and H, the subgraph isomorphism problem is to determine whether H contains a subgraph that is isomorphic to G and this decision problem is well-known NP-Complete [5]. Many algorithms have been proposed to solve this problem starting with the backtracking algorithm by Ullmann [6]. VF2 [7], QuickSI [8], GraphQL [9], GADDI [10] and SPath [11] improved the performance by exploiting different join orders, pruning rules, and auxiliary information from the Ullmann algorithm [12]. The maximum common subproblem, the generalized problem of the subgraph isomorphism problem, also has been tackled by many algorithms [13–15]. However, these algorithms for both problems have exponential time complexity, their scalability are limited and they only work with auxiliary information such as vertex or edge labels. On the other hand, metaheuristic algorithms, especially a genetic algorithm, have been used to address this problem [16–22]. They can usually find good quality solutions within a reasonable amount of time, but most algorithms does not have enough search capability to cover large and complex problem space of the subgraph isomorphism problem.

  • اشتراک گذاری در

دیدگاه خود را بنویسید:

تاکنون دیدگاهی برای این نوشته ارسال نشده است

بررسی الگوریتم ژنتیک ترکیبی افزایشی با مسئله یک‌ریختی زیرگراف
نوشته های مرتبط
مقالات جدید
لوگوی رسانه های برخط

logo-samandehi

پیوندها