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

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

الگوریتم رقابت استعماری یا Imperialist Competitive algorithm که به اختصار ICA نامیده می‌شود جزو الگوریتم های تکاملی یا فرا ابتکاری هستند که به یافتن پاسخ بهینه مسائل مختلف بهینه سازی می‌پردازد. این الگوریتم با مدل سازی ریاضی فرآیند تکامل اجتماعی – سیاسی، الگوریتمی برای حل مسائل ریاضی بهینه‌سازی ارائه می‌دهد. در این پست با استفاده از فرآیند تولید جواب الگوریتم رقابت استعماری مسئله درخت پوشای کمینه در نرم افزار متلب ارائه شده است.

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

با توجه به یک گراف متصل و بدون جهت، درخت پوشا از آن گراف یک زیرگرافی است که اولاً یک درخت است و تمام رأس‌ها را با یکدیگر متصل می‌کند. یک گراف می‌تواند انواع درخت‌های مختلف را پوشش دهد. یک Minimum Spanning Tree درخت پوشای کمینه (MST) یا درخت پوشای مینیمال برای یک گراف وزنم دار، متصل و بدون جهت یک درخت پوشا با وزن کمتر یا برابر با وزن هر درخت دیگر است. وزن یک درخت، مجموع وزن‌های داده شده به هر لبه درخت است.

الگوریتم رقابت استعماری Imperialist Competitive algorithm

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

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

مراحل کلی روند الگوریتم به‌صورت زیر است.

۱- چند نقطه تصادفی روی تابع انتخاب کرده و امپراتوری‌های اولیه را تشکیل بده.

۲- مستعمرات را به سمت کشور امپریالیست حرکت بده (سیاست همسان‌سازی یا جذب).

۳- عملگر انقلاب را اعمال کن.

۴- اگر مستعمره‌ای در یک امپراتوری وجود داشته باشد که هزینه‌ای کمتر از امپریالیست داشته باشد جای مستعمره و امپریالیست را عوض کن.

۵- هزینه کل یک امپراتوری را حساب کن (با در نظر گرفتن هزینه امپریالیست و مستعمراتشان).

۶- یک (چند) مستعمره از ضعیف‌ترین امپراتوری را انتخاب کرده و آن را به امپراتوری که بیشترین احتمال تصاحب را دارد، بده.

۷- امپراتوری‌های ضعیف را حذف کن.

۸- اگر تنها یک امپراتوری باقیمانده باشد توقف کن و در غیر این صورت به ۲ برو.

فلوچارت الگوریتم رقابت استعماری بصورت زیر است.

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

 % ICA Parameters

MaxIt=500; % Maximum Number of Iterations

nPop=300; % Population Size
nEmp=10; % Number of Empires/Imperialists

alpha=1; % Selection Pressure

beta=2; % Assimilation Coefficient

pRevolution=0.5; % Revolution Probability
mu=0.1; % Revolution Rate

zeta=0.1; % Colonies Mean Cost Coefficient

%% Share (Globalize) Settings

global ProblemSettings;
ProblemSettings.CostFunction=CostFunction;
ProblemSettings.nVar=nVar;
ProblemSettings.VarSize=VarSize;
ProblemSettings.VarMin=VarMin;
ProblemSettings.VarMax=VarMax;

global ICASettings;
ICASettings.MaxIt=MaxIt;
ICASettings.nPop=nPop;
ICASettings.nEmp=nEmp;
ICASettings.alpha=alpha;
ICASettings.beta=beta;
ICASettings.pRevolution=pRevolution;
ICASettings.mu=mu;
ICASettings.zeta=zeta;

%% Initialization

% Initialize Empires
emp=CreateInitialEmpires();

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

%% ICA Main Loop

for it=1:MaxIt

% Assimilation
emp=AssimilateColonies(emp);

% Revolution
emp=DoRevolution(emp);

% Intra-Empire Competition
emp=IntraEmpireCompetition(emp);

% Update Total Cost of Empires
emp=UpdateTotalCost(emp);

% Inter-Empire Competition
emp=InterEmpireCompetition(emp);

% Update Best Solution Ever Found
imp=[emp.Imp];
[~, BestImpIndex]=min([imp.Cost]);
BestSol=imp(BestImpIndex);

% Update Best Cost
BestCost(it)=BestSol.Cost;

% Show Iteration Information
if BestSol.Sol.IsFeasible
Flag=' *';
else
Flag=[', DC = ' num2str(BestSol.Sol.q)];
end
disp(['Iteration ' num2str(it) ': Best Cost = ' num2str(BestCost(it)) Flag]);

% Plot Best Solution
figure(1);
PlotSolution(BestSol.Sol,model);
pause(0.01);

end

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

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

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