آموزش کدنویسی الگوریتم کرم شب تاب
زبان برنامه نویسی متلب یکی از زبانهای برنامه نویسی محبوب و البته کاربردی است که برای دانشجویان رشتههای مهندسی و بسیاری از افراد دیگر کاربرد فراوانی دارد. این زبان برنامه نویسی که بیشتر بر پایه محاسبات ریاضی است دارای برخی از الگریتمهای فراابتکاری است که هر کدام ویژگیها و البته شرایط خاص خود را دارند. همانطور که تاکنون در مقالات مختلفی از متلبآنالیز مطالعه کردهاید، ابتدا بهآموزش مقدماتی زبان برنامه نویسی مذکور پرداختیم و حال نیز دوره جدیدی از آن را شروع کردهایم که در آن موضوع الگوریتمهای فراابتکاری مطرح شده است. همراه متلبآنالیز باشید تا با آموزش کدنویسی الگوریتم کرم شب تاب تاببیشتر آشنا شویم.
حرکت کرمهای شبتاب
در جریان حرکت کرمهای شبتاب در این الگوریتم، هر کرم بهصورت احتمالی و راندوم بهسوی یکی دیگر از همسایگانش که لوسیفرین بالاتری دارد حرکت میکنند و در حقیقت لوسیفرین بیشتر بهمنزله درخشندگی بیشتر است و با این اوصاف کرمها بهسمت کرم دیگری میروند که دارای درخشندگی بیشتر است. همانطور که در تصویر زیر مشاهده میکنید، شعاع تصمیمگیری و شعاع حسگری کرمها قابل مشاهده است و در قسمت 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
#include
#include
#include
#include
#include
#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;
}
همانطور که در این مقاله از متلبآنالیز مطالعه کردید، با بخش دیگری از این زبان برنامهنویسی آشنا شدیم و دانش خود را در زمینه الگوریتمهای فراابتکاری و البته الگوریتم کرم شبتاب افزایش دادیم. توجه داشته باشید که از طریق بخش دانلود رایگان در وبسایت متلبآنالیز میتوانید مقالات و کتابهای مختلفی را در زمینه متلب و برنامهنویسی دانلود و مطالعه کنید. نظرات خود را در جهت بهبود کیفیت مقالات با ما از طریق بخش دیدگاهها در میان بگذارید.