آموزش کدنویسی الگوریتم کرم شب‌ تاب : حرکت کرم شب‌تاب و به‌روز کردن برد همسایگی

آموزش کدنویسی الگوریتم کرم شب‌ تاب

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

حرکت کرم‌های شب‌تاب

در جریان حرکت کرم‌های شب‌تاب در این الگوریتم، هر کرم به‌صورت احتمالی و راندوم به‌سوی یکی دیگر از همسایگانش که لوسی‌فرین بالاتری دارد حرکت می‌کنند و در حقیقت لوسی‌فرین بیشتر به‌منزله درخشندگی بیشتر است و با این اوصاف کرم‌ها به‌سمت کرم دیگری می‌روند که دارای درخشندگی بیشتر است. همان‌طور که در تصویر زیر مشاهده می‌کنید، شعاع تصمیم‌گیری و شعاع حسگری کرم‌ها قابل مشاهده است و در قسمت b کرم‌های موجود در الگوریتم بر اساس میزان لوسی‌فرین (درخشندگی) طبقه‌بندی شده‌اند. برای توضیح بیشتر باید بدانید که کرم ۱ بیشترین لوسی‌فرین را دارا است و rd نیز بدین معناست که در آن گستره، کرم قادر است همسایگان خود را تشخیص دهد و هر کرم دیگری که در این محدوده قرار گیرد، در واقع همسایه کرم به‌حساب می‌آید. البته باید بدین نکته نیز توجه داشت که کرم‌، کرم‌های همسایه را از نظر مقدار لوسی‌فرین مقایسه می‌کند. rs نیز به‌معنای شعاع بیشترین حد تصمیم‌گیری است و البته در جریان تکرار‌های الگوریتم GSC شعاع تصمیم کرم‌ها بر اساس شرایط موجود تغییر می‌کند. اما باید بدین نکته نیز توجه داشت که شعاع تصمیم‌گیری هر کرم از شعاع حسگری آن بیشتر نمی‌شود. شعاع حسگری نیز به‌معنای حداکثر توانایی کرم‌ها برای مشاهده کرم‌های دیگر است. اما در این بین فرمولی نیز برای سنجش احتمال حرکت وجود دارد که بر این اساس هر کرم شب‌تاب به‌نام i که به‌سمت همسایه j که درخشندگی بالایی دارد می‌رود، بدین شکل محاسبه می‌شود: (توجه داشته باشید که کرم با درخشش بیشتر با رتبه ۱ نمایش داده می‌شود).

حال باید بدین نکته نیز توجه داشت که در این رابطه (Ni(t مجموعه‌ای از کرم‌های شب‌تاب همسایه کرم i در زمان (pij(t است و فاصله اقلیدسی بین کرم‌های شب‌تاب i و j نیز در زمان (t و rdi(t نشان‌دهنده بردهمسایگی متغیر مربوط به‌کرم شب‌تاب i در زمان t است. حال اگر در نظر بگیریم که کرم شب‌تاب j توسط کرم شب‌تاب i با احتمال p انتخاب شده است، می‌توانیم برای محاسبه حرکت زمان گسسته به‌شکل زیر وارد عمل شویم:

در فرمول فوق، (Xi(t نشان‌دهنده بردار m بعدی مکان کرم شب‌تاب i در زمان t است. گفتنی است که II.II نیز عملگر نرم اقلیدس را نشان می‌دهد و s اندازه گام حرکت در مثال است.

به‌روز کردن برد همسایگی

باید برنامه‌نویسان توجه داشته باشند که به‌هر کرم شب‌تاب i یک همسایگی تخصیص می‌یابد که برد شعاعی rid آن به‌طور طبیعی دینامیک است (rid کوچکتر مساوی rs و rs بزرگ‌تر از ۰). اگر برد حسگری هر کرم شب‌تاب کل فضای جستجو را پوشش دهد در این صورت تمام کرم‌ها به‌سمت بهینه سراسری حرکت می‌کنند و با این کار بهینه‌های محلی نادیده گرفته خواهند شد و به‌همین دلیل است که برد شناسایی آن‌ها کوچک‌تر از کل مجموعه است. باید بدین نکته نیز توجه داشت که چون اطلاعات از پیش دانسته درباره تابع هدف (یا همان مثالی در خصوص تعداد قله‌ها یا فاصله بین قله‌ها) برای مسئله در نظر گرفته نمی‌شود، به‌همین دلیل به‌سادگی نمی‌توان برد همسایگی ثابت و البته مناسبی را برای تمام تابع‌های هدف در نظر گرفت. برای مثال انتخاب برد همسایگی rd برای تابع هدف‌هایی با کمترین فاصله میان قله‌هایی با بیشتر از rd نسبت به‌تابع‌هایی که این فاصله برای آن‌ها کمتر از rd است مناسب به‌نظر می‌رسد. با این اوصاف GSO از یک برد همسایگی تطبیقی برای شناسایی وجود قله‌های چندگانه در مسائل بهینه‌سازی توابع استفاده می‌کند.

برنامه نویسان متلب باید به این نکته نیز در خصوص الگوریتم‌های فراابتکاری توجه داشته باشند که در هر تکرار الگوریتم GSO، برد همسایگی هر کرم شب‌تاب با فرص r0 به‌عنوان برد همسایگی اولیه هر کرم rid(0) = r0 به‌شکل زیر محاسبه می‌شود:

توجه کنید که در فرمول فوق، B مربوط به پارامتر ثابت و nt مربوط به پارامتری برای کنترل تعداد همسایگی هر کرم است.

همان‌طور که در تصویر زیر مشاهده می‌کنید، نتیجه بهینه‌سازی تشخیص تومور سینه با استفاده از GSO قابل انجام است.

در تصویر زیر نیز می‌توانید فولوچارت الگوریتم کرم شب‌تاب را مشاهده نمایید:

در تصویر زیر می‌توانید بهینه‌سازی تکاملی کرم شب‌تاب را مشاهده کنید:

کد‌های زیر نیز سورس کد (کد اصلی) الگوریتم کرم شب‌تاب هستند که می‌توانید از تمام یا بخشی از آن‌ها استفاده کنید:

// Name : Firefly.cpp

// Authors : Dr. Iztok Fister and Iztok Fister Jr.

// Version : v1.0

// Created on : Jan 23, 2012

//============================================================================

/* Classic Firefly algorithm coded using C/C++ programming language */

/* Reference Paper*/

/*I. Fister Jr., X.-S. Yang, I. Fister, J. Brest, Memetic firefly algorithm for combinatorial optimization,

in Bioinspired Optimization Methods and their Applications (BIOMA 2012), B. Filipic and J.Silc, Eds.

Jozef Stefan Institute, Ljubljana, Slovenia, 2012 */

/*Contact:

Iztok Fister (iztok.fister@uni-mb.si)

#include

#define DUMP ۱

#define MAX_FFA 1000

#define MAX_D ۱۰۰۰

using namespace std;

int D = 1000; // dimension of the problem

int n = 20; // number of fireflies

int MaxGeneration; // number of iterations

int NumEval; // number of evaluations

int Index[MAX_FFA]; // sort of fireflies according to fitness values

double ffa[MAX_FFA][MAX_D]; // firefly agents

double ffa_tmp[MAX_FFA][MAX_D]; // intermediate population

double f[MAX_FFA]; // fitness values

double I[MAX_FFA]; // light intensity

double nbest[MAX_FFA]; // the best solution found so far

double lb[MAX_D]; // upper bound

double ub[MAX_D]; // lower bound

double alpha = 0.5; // alpha parameter

double betamin = 0.2; // beta parameter

double gama = 1.0; // gamma parameter

double fbest; // the best objective function

typedef double (*FunctionCallback)(double sol[MAX_D]);

/*benchmark functions */

double cost(double sol[MAX_D]);

double sphere(double sol[MAX_D]);

/*Write your own objective function */

FunctionCallback function = &cost;

// optionally recalculate the new alpha value

double alpha_new(double alpha, int NGen)

{

double delta; // delta parameter

delta = 1.0-pow((pow(10.0, -4.0)/0.9), 1.0/(double) NGen);

return (1-delta)*alpha;

}

// initialize the firefly population

void init_ffa()

{

int i, j;

double r;

// initialize upper and lower bounds

for (i=0;i

{

lb[i] = 0.0;

ub[i] = 2.0;

}

for (i=0;i

{

for (j=0;j

{

r = ( (double)rand() / ((double)(RAND_MAX)+(double)(1)) );

ffa[i][j]=r*(ub[i]-lb[i])+lb[i];

}

f[i] = 1.0; // initialize attractiveness

I[i] = f[i];

}

// implementation of bubble sort

void sort_ffa()

{

int i, j;

// initialization of indexes

for(i=0;i

Index[i] = i;

// Bubble sort

for(i=0;i

{

for(j=i+1;j

{

if(I[i] > I[j])

{

double z = I[i]; // exchange attractiveness

I[i] = I[j];

I[j] = z;

z = f[i]; // exchange fitness

f[i] = f[j];

f[j] = z;

int k = Index[i]; // exchange indexes

Index[i] = Index[j];

Index[j] = k;

}

// replace the old population according the new Index values

void replace_ffa()

{

int i, j;

// copy original population to temporary area

for(i=0;i

{

for(j=0;j

{

ffa_tmp[i][j] = ffa[i][j];

}

// generational selection in sense of EA

for(i=0;i

{

for(j=0;j

{

ffa[i][j] = ffa_tmp[Index[i]][j];

}

void findlimits(int k)

{

int i;

for(i=0;i

{

if(ffa[k][i]

ffa[k][i] = lb[i];

if(ffa[k][i] > ub[i])

ffa[k][i] = ub[i];

}

void move_ffa()

{

int i, j, k;

double scale;

double r, beta;

for(i=0;i

{

scale = abs(ub[i]-lb[i]);

for(j=0;j

{

r = 0.0;

for(k=0;k

{

r += (ffa[i][k]-ffa[j][k])*(ffa[i][k]-ffa[j][k]);

}

r = sqrt(r);

if(I[i] > I[j]) // brighter and more attractive

{

double beta0 = 1.0;

beta = (beta0-betamin)*exp(-gama*pow(r, 2.0))+betamin;

for(k=0;k

{

r = ( (double)rand() / ((double)(RAND_MAX)+(double)(1)) );

double tmpf = alpha*(r-0.5)*scale;

ffa[i][k] = ffa[i][k]*(1.0-beta)+ffa_tmp[j][k]*beta+tmpf;

}

findlimits(i);

}

void dump_ffa(int gen)

{

cout

}

/* display syntax messages */

void help()

{

cout

cout Firefly [-h|-?] [-l] [-p] [-c] [-k] [-s] [-t]”

cout Parameters: -h|-? = command syntax”

cout -n = number of fireflies”

cout -d = problem dimension”

cout -g = number of generations”

cout -a = alpha parameter”

cout -b = beta0 parameter”

cout -c = gamma parameter”

}

int main(int argc, char* argv[])

{

int i;

int t = 1; // generation counter

// interactive parameters handling

for(int i=1;i

{

if((strncmp(argv[i], “-h”, ۲) == ۰) || (strncmp(argv[i], “-?”, ۲) == ۰))

{

help();

return 0;

}

else if(strncmp(argv[i], “-n”, ۲) == ۰) // number of fireflies

{

n = atoi(&argv[i][2]);

}

else if(strncmp(argv[i], “-d”, ۲) == ۰) // problem dimension

{

D = atoi(&argv[i][2]);

}

else if(strncmp(argv[i], “-g”, ۲) == ۰) // number of generations

{

MaxGeneration = atoi(&argv[i][2]);

}

else if(strncmp(argv[i], “-a”, ۲) == ۰) // alpha parameter

{

alpha = atof(&argv[i][2]);

}

else if(strncmp(argv[i], “-b”, ۲) == ۰) // beta parameter

{

betamin = atof(&argv[i][2]);

}

else if(strncmp(argv[i], “-c”, ۲) == ۰) // gamma parameter

{

gama = atof(&argv[i][2]);

}

else

{

cerr

return -1;

}

// firefly algorithm optimization loop

// determine the starting point of random generator

srand(1);

// generating the initial locations of n fireflies

init_ffa();

#ifdef DUMP

dump_ffa(t);

#endif

while(t

{

// this line of reducing alpha is optional

alpha = alpha_new(alpha, MaxGeneration);

// evaluate new solutions

for(i=0;i

{

f[i] = function(ffa[i]); // obtain fitness of solution

I[i] = f[i]; // initialize attractiveness

}

// ranking fireflies by their light intensity

sort_ffa();

// replace old population

replace_ffa();

// find the current best

for(i=0;i

nbest[i] = ffa[0][i];

fbest = I[0];

// move all fireflies to the better locations

move_ffa();

#ifdef DUMP

dump_ffa(t);

#endif

t++;

}

cout

return 0;

}

// FF test function

double cost(double* sol)

{

double sum = 0.0;

for(int i=0;i

sum += (sol[i]-1)*(sol[i]-1);

return sum;

}

double sphere(double* sol) {

int j;

double top = 0;

for (j = 0; j

top = top + sol[j] * sol[j];

}

return top;

}

همان‌طور که در این مقاله از متلب‌آنالیز مطالعه کردید، با بخش دیگری از این زبان برنامه‌نویسی آشنا شدیم و دانش خود را در زمینه الگوریتم‌های فراابتکاری و البته الگوریتم کرم شب‌تاب افزایش دادیم. توجه داشته باشید که از طریق بخش دانلود رایگان در وب‌سایت متلب‌آنالیز می‌توانید مقالات و کتاب‌های مختلفی را در زمینه متلب و برنامه‌نویسی دانلود و مطالعه کنید. نظرات خود را در جهت بهبود کیفیت مقالات با ما از طریق بخش دیدگاه‌ها در میان بگذارید.

دپارتمان متلب آنالیز

عضویت در خبرنامه