تعیین درخت پوشای مینیمم با الگوریتم ژنتیک در متلب

درخت پوشای کمینه

درخت پوشای کمینه یا درخت پوشای مینیمم درختی است که از یک گراف G کامل، بدون جهت و وزن دار (شامل تمام راس‌ها و حداقل یال‌ها) تشکیل می‌شود. به بیان دیگر می‌توان گفت، درخت پوشای G درختی است که مجموعه‌ای از یال‌ها را شامل می‌شود که تمام رئوس را پوشش می‌دهد. در واقع تمام رئوس G در درخت پوشا وجود دارند به شرطی که هیچ حلقه یا دوری ایجاد نشود و درخت همبند نیز باشد. درخت پوشای کمینه (Minimum Spanning Tree) یک درخت پوشا است که داری کمترین هزینه (مجموع هزینه یال‌ها) باشد.

الگوریتم ژنتیک

الگوریتم ژنتیک روشی برای بهینه سازی است و کارکرد آن بر اصول انتخاب طبیعی حاکم بر ژنتیک طبیعی استوار است. در این الگوریتم اطلاعات تاریخی از چگونگی تکامل، به شکلی کارا استخراج شده و در روند جستجو استفاده می‌شود. الگوریتم ژنتیک روشی قدرتمند بوده و بر روی دسته وسیعی از مسائل به‌خوبی عمل می‌کند.

الگوریتم ژنتیک بر روی جمعیتی از راه حل‌های بالقوه یا کروموزوم‌ها که هر یک می‌توانند به‌عنوان پاسخی از مسئله تلقی شوند، با اعمال عملگرهای ژنتیکی به جستجوی راه حل نهایی می‌پردازند. در الگوریتم ژنتیکی، بسیاری از مکانیزم‌هایی که در زیست شناسی وجود دارد، نظیر انتخاب ژن برتر، ترکیب ژن‌ها، جهش ژن‌ها، مهاجرت افراد جمعیت، محلی بودن گونه‌ها و … شبیه سازی می‌شوند. در این الگوریتم‌ها، جستجو بر روی مجموعه‌هایی از راه حل‌ها به‌صورت موازی انجام می‌شود، درحالی‌که در روش‌های سنتی جستجو به‌صورت ترتیبی است.

تعیین درخت پوشای مینیمم با الگوریتم ژنتیک

در این سورس کد همانند دیگر روش‌های حل مسئله، با استفاده از توابع CostFun به تعیین درخت پوشای کمینه با استفاده از الگوریتم ژنتیک پرداخته شده است. پس از اجرای سورس کد، گراف به صورت خودکار شروع به طراحی می‌شود و در نهایت، در بهینه‌ترین حالت ممکن که قابل انجام با الگوریتم ژنتیک می‌باشد جا به جایی گره‌ها و طراحی گراف به اتمام می‌رسد. این سورس کد دارای ۱۰ فایل می‌باشد که فایل GA.m فایل اصلی بوده و تمامی فراخوانی توابع و تعریف Iteration ها در این فایل انجام می‌گیرد.

قسمتی از سورس کد تعیین درخت پوشای مینیمم با الگوریتم ژنتیک

%% Initialization

empty_individual.Position=[];
empty_individual.Cost=[];
empty_individual.Sol=[];
pop=repmat(empty_individual,nPop,1);

for i=1:nPop
    
    % Initialize Position
    pop(i).Position=unifrnd(VarMin,VarMax,VarSize);
    
    % Evaluation
    pop(i).Cost=CostFunction(pop(i).Position);
    
end
% Sort Population
Costs=[pop.Cost];
[Costs, SortOrder]=sort(Costs);
pop=pop(SortOrder);

% Store Best Solution
BestSol=pop(1);

% Array to Hold Best Cost Values
BestCost=zeros(MaxIt,1);

% Store Cost
WorstCost=pop(end).Cost;

تصاویر خروجی سورس کد تعیین درخت پوشای مینیمم با الگوریتم ژنتیک در متلب

درباره سورس کد تعیین درخت پوشای مینیمم با الگوریتم ژنتیک

سورس کد تعیین درخت پوشای مینیمم با الگوریتم ژنتیک در متلب در محیط Matlab نوشته و اجرا شده است این سورس کد توسط تیم پشتیبانی پی استور تست و اجرا شده است. کیفیت اثر توسط پی استور تضمین می‌شود و دارای نشان تضمین کیفیت پی استور می‌باشد. برای دانلود اثر آن را خریداری فرمایید به محض خرید لینک دانلود در دسترس خواهد بود.