A Genetic Algorithm for Minimum Spanning Tree

سال انتشار: 1398
نوع سند: مقاله کنفرانسی
زبان: انگلیسی
مشاهده: 513

فایل این مقاله در 8 صفحه با فرمت PDF قابل دریافت می باشد

این مقاله در بخشهای موضوعی زیر دسته بندی شده است:

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

CSCG03_132

تاریخ نمایه سازی: 14 فروردین 1399

چکیده مقاله:

In this paper a novel approach for minimum spanning tree based on genetic algorithm is proposed. In this method, new representation of chromosome and more suitable fitness function have been defined. At first, a vector in length of complete graph edges as initial chromosome is created. For presence or absence of an edge, the corresponding value in chromosome is set to 1 or 0, respectively. Fitness function is defined based on graph weights and number of connected components. Fitness should be low as possible in each iteration. Results of experiments shows proposed method can converge with large number of nodes.

نویسندگان

Solmaz Abbasi

Electrical and Computer Engineering Department, Yazd University, Yazd, Iran

Farzane Nadi

Electrical and Computer Engineering Department, Yazd University, Yazd, Iran

Ali mohammad Latif

Electrical and Computer Engineering Department, Yazd University, Yazd, Iran