禁忌搜索实施 [英] Tabu Search implementation
本文介绍了禁忌搜索实施的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
大家好！
我是新来的，我刚看到这个论坛我立即想到：这是给我的！
我的问题是关于实施Tabu Search的算法如下：
Hello people!
I'm new here and I just saw this forum I immediately thought: this is the one for me!
My problem is concerning the implementation of Tabu Search's algorithm which follows below:
#include<stdio.h> //to use the printf function
#include<conio.h> //to use the getche function
#include<stdlib.h>
#include<math.h> //to use the rand function
#include<time.h>
#define DIM_POP 4
#define PAR_MIN -15.0 // studying the function into established interval [-2^3, 2^3]
#define PAR_MAX 15.0
#define TABU_SIZE 4
#define TABU_TENURE 3
#define STEP_SIZE_MAX 0.01
#define RANGE_MAX (1/4)*STEP_SIZE_MAX
typedef struct
{
float point[2]; //it is a vector containing (x,y) coordinates
float fitness;
int tabu_tenure;
}info;
info tabu_list[TABU_SIZE];
int iter_best=0; /* iteration where best was found */
info best; /* best value of object function in next_neighborhood */
int S; //no. of generated neighborhood
int itcall=0; //no of calls to object function
float neighbor[2][DIM_POP];
float z(float x, float y);
void tabu_search(int max_iter, float seed_x, float seed_y, float fseed);
void neighborhood(info curr_best, info curr_neighborhood[DIM_POP]);
void insert_tabu(info p);
float distance(float p_gen[2], float point_tabu[2]);
void best_object_function(info curr_neighborhood[DIM_POP]);
int main() // the main function
{
int num; // num is the no. of iterations
int i,j;
float seed_x;
float seed_y;
float fseed;
printf("\nMaximum of the function z = -x^2-y^2 + 5 "); // introduction to the program
enter: printf("\nPlease enter the no. of iterations: ");
scanf("%d",&num); // enter the no. of iterations in num
if(num<1) // if a -ve number is inserted .. enter num again
goto enter;
srand(time(NULL)); //initializing the generator
seed_x=(PAR_MAX-PAR_MIN)*(((float)rand())/RAND_MAX)+PAR_MIN;
//printf("\nseed=%f", seed_x);
seed_y=(PAR_MAX-PAR_MIN)*(((float)rand())/RAND_MAX)+PAR_MIN;
fseed=z(seed_x,seed_y);
tabu_search(num, seed_x, seed_y, fseed);
printf("\nPress any key to end ! ");
getche(); // wait for a character from the keyboard to end
} //end of main
float z(float x, float y) // the y function that we look for it's maximum value takes (x,y) value
{
float t;
t=-(x*x)-(y*y)+5; // the function is z= - ( x^ 2 ) - (y^ 2) +5
return(t);
} // end of z function
void tabu_search(int max_iter, float seed_x, float seed_y, float fseed)
{
int iter=0; /* iteration counter */
info curr_neighborhood[DIM_POP];
for(int i=0;i<TABU_SIZE;i++) //tabu list initialization
tabu_list[i].tabu_tenure=0;
best.point[0]=seed_x;
best.point[1]=seed_y;
best.fitness=fseed;
printf("\n seed=(%f,%f) with fitness=%f", seed_x, seed_y, best.fitness);
neighborhood(best, curr_neighborhood);
iter++;
do{
neighborhood(best, curr_neighborhood);
for(int k=0;k<TABU_SIZE;k++)
{
if(iter-tabu_list[k].tabu_tenure>TABU_TENURE)
tabu_list[k].tabu_tenure=0;
}
best_object_function(curr_neighborhood);
itcall=itcall+S;
printf("\n no. iter=%d no. neigh=%d\n", iter, S);
iter++;
}while(iter<max_iter);
printf("\n best point (x,y)=(%f,%f) and best fitness f(x,y)=%f ",
best.point[0], best.point[1], best.fitness);
}
void neighborhood(info curr_best, info curr_neighborhood[DIM_POP]) /* make a neighborhood of each point of the curr_neighborhood */
{
int i;
int j;
int k;
float gen[2];
int M=0;
double dist;
int flag_tabu=0;
int flag_step=0;
float step_size=STEP_SIZE_MAX;
float point_tabu[2];
int counter=0;
S=0;
srand(time(NULL));
while(S!=DIM_POP && M!=5*DIM_POP ) //the loop stops when S=DIM_POP or when it is reached a establish max number without has found neighborhoods
{
switch (counter)
{
case 0:
gen[0]=curr_best.point[0]+(step_size*(PAR_MAX-PAR_MIN)); /* generate a neighborhood of the point ax into the established interval [PAR_MAX, PAR_MIN] */
if(gen[0]>PAR_MAX)
gen[0]=PAR_MAX;
else if(gen[0]<PAR_MIN)
gen[0]=PAR_MIN;
gen[1]=curr_best.point[1];
counter++;
break;
case 1:
gen[0]=curr_best.point[0];
gen[1]=curr_best.point[1]+(step_size*(PAR_MAX-PAR_MIN)); /* generate a neighborhood of the point ax into the established interval [PAR_MAX, PAR_MIN] */
if(gen[1]>PAR_MAX)
gen[1]=PAR_MAX;
else if(gen[1]<PAR_MIN)
gen[1]=PAR_MIN;
counter++;
break;
case 2:
gen[0]=curr_best.point[0]-(step_size*(PAR_MAX-PAR_MIN)); /* generate a neighborhood of the point ax into the established interval [PAR_MAX, PAR_MIN] */
if(gen[0]>PAR_MAX)
gen[0]=PAR_MAX;
else if(gen[0]<PAR_MIN)
gen[0]=PAR_MIN;
gen[1]=curr_best.point[1];
counter++;
break;
case 3:
gen[0]=curr_best.point[0];
gen[1]=curr_best.point[1]-(step_size*(PAR_MAX-PAR_MIN)); /* generate a neighborhood of the point ax into the established interval [PAR_MAX, PAR_MIN] */
if(gen[1]>PAR_MAX)
gen[1]=PAR_MAX;
else if(gen[1]<PAR_MIN)
gen[1]=PAR_MIN;
counter++;
default:
break;
}
M++;
for(j=0;j<TABU_SIZE;j++)
{
if(tabu_list[j].tabu_tenure!=0)
{
for(k=0;k<2;k++)
point_tabu[k]=tabu_list[j].point[k];
dist=distance(gen, point_tabu);
if(dist<RANGE_MAX)
flag_tabu++;
}
}
if(flag_tabu==0)
{
for(k=0;k<2;k++)
neighbor[k][S]=gen[k];
S++;
}
flag_tabu=0;
}
for(i=0;i<S;i++)
{
for(k=0;k<2;k++)
curr_neighborhood[i].point[k]=neighbor[k][i];
curr_neighborhood[i].fitness=z(curr_neighborhood[i].point[0],
curr_neighborhood[i].point[1]);
}
best_object_function(curr_neighborhood);
}
void insert_tabu(info p) //creating tabu list as a FIFO sistem
{
int i=0;
while(tabu_list[i].tabu_tenure!=0)
i++;
for(int k=0;k<2;k++)
tabu_list[i].point[k]=p.point[k];
tabu_list[i].fitness=p.fitness;
tabu_list[i].tabu_tenure=TABU_TENURE;
}
float distance(float p_gen[2], float point_tabu[2])
{
float dist;
dist=sqrt(pow(p_gen[0]-point_tabu[0],2)+pow(p_gen[1]-point_tabu[1],2));
return (dist);
}
void best_object_function(info curr_neighborhood[DIM_POP])
{
for(int i=0;i<S;i++)
{
if(curr_neighborhood[i].fitness>best.fitness)
{
insert_tabu(best);
best.fitness=curr_neighborhood[i].fitness;
for(int k=0;k<2;k++)
best.point[k]=curr_neighborhood[i].point[k];
iter_best=itcall;
}
else
{
insert_tabu(curr_neighborhood[i]);
}
}
printf("\n Current best point=(%f,%f)", best.point[0], best.point[1]);
}
在这段代码中我将邻域生成为十字架（参见开关盒），所以我可以生成一个最多4个邻居。我意识到这个算法每次都会产生4个邻居，而且永远不会减少：为什么？
这个代码中有些东西没有继续，但我不知道它可能是什么。也许我必须为TABU_SIZE或STEP_SIZE设置不同的值...
任何人都可以帮助我吗？
In this code I generate the neighborhood as a cross (see the switch case), so I can generate a maximum of 4 neighbors. I realised that the algorithm generates 4 neighbors every time and never less: why?
Something don't go on in this code but I don't have idea what could be. Maybe I have to set different value for TABU_SIZE or STEP_SIZE...
Could anyone help me?
推荐答案
你创建4个邻居因为如果计数器大于3，则跳出默认值的开关。你需要一些更好的终止算法。
在代码中输出更多，主要是在边缘情况。 （就像默认情况下那样）
我的建议是制作一些样本测试函数，以便更好地理解你的代码流。从非常简单的数据开始，并在推算后增加复杂性。
You create 4 neighbors because of the switch which jumps out on the default if the counter is greater than 3. You will need some better termination algorhitm.
Make more output in your code, mostly in the edge cases. (Like in that default)
My advice is to make some sample test function to better understand your code flow. Start with really simple data and increase the complexity after prooving it.
这篇关于禁忌搜索实施的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
