混合蛙跳算法的基本原理及C/C++实现

1、 混合蛙跳算法的基本原理

    对随机生成的青蛙群体F，共有n只青蛙。将青蛙按个体文化信息值的大小即适应度降序排列，然后把整个群体分成m个子群，每个子群有k只青蛙。对青蛙群体F，将第一只青蛙分入第1子群，第二只青蛙分入第2子群，第m只青蛙分入第m子群，第m+1只青蛙分入第1子群，第m+2只青蛙分入第2子群，依次类推，直到全部青蛙划分完毕，且满足关系式n=m×k。

对于青蛙群体F，具有全局最好适应度的解表示为Pg；对于每一个子群，具有最好适应度的解表示为Pb，最差适应度的解表示为Pw。首先对每个子族群进行局部搜索，即对子族群中最差适应度的青蛙个体进行更新操作，更新策略为：

Ds=min{int[rand(Pb-Pw)],Dmax}, Pb-Pw≥0 (1)

Ds=max{int[rand(Pb-Pw)],-Dmax}, Pb-Pw＜0 (2) newDw=Pw+Ds（-Dmax≦Ds≦Dmax）(3)

 其中， Ds 表示青蛙个体的调整距离，rand()表示0和1之间的随机数，Dmax表示青蛙个体允许改变的最大步长。如果最差适应度的青蛙个体更新后的解newDw优于Pw，则取代Pw，否则用Pg代替公式（1-2）中的Pb执行更新策略，如果还是没有优于Pw，则用一个随机产生的解取代Pw。重复这种更新操作，直到设定的子群内更新次数。当所有子群的局部搜索完成后，将所有子群重新混合并排序和重新划分子群，然后又进行子群内局部搜索，如此循环直到满足终止条件。

2、 混合蛙跳算法的C/C++实现

相关变量定义部分：

#define G 100  /*混合迭代次数*/
#define P 200 /*个体总数*/
#define M 20 /*族群数*/
#define I 10 /*因此，一个族群中的个体数是10*/
#define V 20 /*个体维数*/
#define N 20 /*族群内更新次数*/
#define MAX 2.048
#define MIN -2.048
#define D 2.0 /*蛙跳的最大值*/
#define R rand()%100/100.0
typedef struct {
double d[V];
double fitness;
}Individal;
Individal pw[M];/*族群中个体最差位置*/
Individal pb[M];/*族群中个体最好位置*/
Individal px;/*全体中最好位置*/
Individal individual[P];/*全部个体*/
Individal pop[M][I];/*排序后的群组*/
Individal temp[M];
Individal tem;

适应度函数：

double fitness(int a)
{int i;double sum=0;for(i=0;i<V-1;i++){sum+=100*(individual[a].d[i]*individual[a].d[i]-individual[a].d[i+1])*(individual[a].d[i]*individual[a].d[i]-individual[a].d[i+1])+(individual[a].d[i]-1)*(individual[a].d[i]-1);}return sum;     
}

void init()
{int i,j;for(i=0;i<P;i++){for(j=0;j<V;j++){individual[i].d[j]=R*(MAX-MIN)+MIN;}individual[i].fitness=fitness(i);}
}

void sort()
{int i,j,k;for(i=1;i<P;i++){for(j=0;j<P-i;j++){if(individual[j].fitness<individual[j+1].fitness){tem=individual[j];individual[j]=individual[j+1];individual[j+1]=tem;}}}k=0;/*按照规则分组*/for(i=0;i<I;i++){for(j=0;j<M;j++){pop[j][i]=individual[k];k++;}}px=individual[P-1];for(i=0;i<M;i++){pw[i]=pop[i][0];pb[i]=pop[i][I-1];}
}

void sortPop(int b)
{int i,j;for(i=1;i<I;i++){for(j=0;j<I-i;j++){if(pop[b][j].fitness<pop[b][j+1].fitness){tem=pop[b][j];pop[b][j]=pop[b][j+1];pop[b][j+1]=tem;}}}
}

void update()
{int i,j,k,l,n;double a;double b;for(n=0;n<N;n++){for(i=0;i<M;i++){    a=0.0;b=0.0;for(j=0;j<V;j++){   temp[i].d[j]=R*(pb[i].d[j]-pw[i].d[j]);if(abs(temp[i].d[j])>D){if(temp[i].d[j]>0){temp[i].d[j]=D;}else{temp[i].d[j]=-D;}}temp[i].d[j]+=pw[i].d[j];a+=temp[i].d[j]*temp[i].d[j];}temp[i].fitness=a;if(a<pw[i].fitness){pop[i][0]=temp[i];sortPop(i);pw[i]=pop[i][0];pb[i]=pop[i][I-1];}else{for(k=0;k<V;k++){temp[i].d[k]=R*(px.d[k]-pw[i].d[k]);if(abs(temp[i].d[k])>D){if(temp[i].d[k]>0){temp[i].d[k]=D;}else{temp[i].d[k]=-D;}}temp[i].d[k]+=pw[i].d[k];a+=temp[i].d[k]*temp[i].d[k];}temp[i].fitness=a;if(a<pw[i].fitness){pop[i][0]=temp[i];sortPop(i);pw[i]=pop[i][0];pb[i]=pop[i][I-1];}else{for(l=0;l<V;l++){pop[i][0].d[l]=R*(MAX-MIN)+MIN;b+=pop[i][0].d[l]*pop[i][0].d[l];}pop[i][0].fitness=b;sortPop(i);pw[i]=pop[i][0];pb[i]=pop[i][I-1];}}}}
}

void renew()
{int i,j,k;i=0;	for(j=0;j<M;j++){for(k=0;k<I;k++){individual[i]=pop[j][k]; i++;}}
}

void result()
{printf("%.8f\n",px.fitness);int i;for(i=0;i<V;i++){printf("x(%d)=%.8f\n",i,px.d[i]);}	
}

void main()
{int i;init();for(i=0;i<G;i++){sort();update();renew();}result();printf("Completed!");
}