📄 strict16_nonblocking.c
字号:
/* strictly-ring----16 Traffics */
///////////// Load other traffic: from the heaviest to the lightest///////////////
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<ctype.h>
#include<string.h>
#include<time.h>
#define ESC 27
#define ERRORLEVEL 0.01
#define nTraffics 2
#define PopSize 200
#define MaxGens 500
#define Granularity 48
#define PXover 0.6
#define PMutation 0.4
#define RunTime 1
#define ITEMS 8
int pack_ring(int, int, int, int, int);
void swap(int*, int*);
void initiate(void);
void crossover(void);
void mutation(void);
void load_count(int);
void distribute(int,int);
void distribute_ring(int,int);
void search_split_ring(int ,int ,int );
int temp_traffic[nTraffics][16*15],load[16*15][nTraffics][16*15];// used for distribute traffic,n,split_traffic[16*15][nTraffics][16*15]
int ring[16*15][16], traffic[nTraffics][16*15];
int fitness[PopSize*2][2], pop[PopSize*2][16*15],split_list[nTraffics][1000];
int in_load[16], out_load[16], node_load[nTraffics][16], line_load[16];
int NVars, nNodes, max_split, NTemp, nWave, count, max_line_load[nTraffics],listpoint;
int I[16*15], J[16*15], temp_node[16*15][16], ns[16*15], Lij[16][16], K[16][16];
int g;
int main()
{
FILE *fp1, *fp2;
if((fp2=fopen("16traffic.txt", "r"))==NULL)
{
printf("can't open file 2traffic.txt\n");
exit(1);
}
for(nNodes=16; nNodes>=16; nNodes--)
{
register int i, j, k;
double avemaxgen, avemax[2],run_time, L[nTraffics], ftemp;
int max[RunTime][2], maxgen[RunTime], maxmax[2], mingen;
int p, gen, display, l, run, temp, m, temp_split;
int max_line, min_Waves, max_Waves, min_ADMs, max_ADMs, nADMs;// max_node,
clock_t start_finish;
if((fp1=fopen("strict16nonblocking.res", "a"))==NULL)
{
printf("can't open file re16andor.res\n");
exit(1);
}
start_finish = clock();
printf("nNodes=%d \n", nNodes);
NVars=nNodes*(nNodes-1);
NTemp=nNodes*(nNodes-1);
for(k=0; k<nTraffics; k++)
for(i=0; i<NVars; i++)
fscanf(fp2, "%d", &traffic[k][i]);
for(k=0; k<NVars/2; k++)
{
temp=k+1;
for(i=0; i<nNodes; i++)
{ temp=temp-nNodes+i+1; if(temp<=0) break; }
j=nNodes+temp-1;
I[k]=i; J[k]=j; K[i][j]=k;
}
for(k=NVars/2; k<NVars; k++)
{
temp=k-NVars/2+1;
for(i=1; i<nNodes; i++)
{ temp=temp-i; if (temp<=0) break; }
j=temp+i-1;
I[k]=i; J[k]=j; K[i][j]=k;
}
for(i=0; i<nNodes-1; i++)
{ Lij[i][i]=0;
for(j=i+1; j<nNodes; j++)
{
Lij[i][j]=j-i;
Lij[j][i]=nNodes-j+i;
}
}
for(m=0; m<nTraffics; m++)
{
L[m]=0;
for(k=0; k<NVars; k++)
{
i=I[k]; j=J[k];
L[m]=L[m]+Lij[i][j]*traffic[m][k];
}
L[m]=2.0*L[m]/nNodes/NVars;
}
ftemp=L[0]; temp=0;
for(m=0; m<nTraffics; m++)
{
if(L[m]>ftemp)
{
ftemp=L[m]; temp=m;
}
}
if(temp)
{
L[temp]=L[0]; L[0]=ftemp;
for(i=0; i<NVars; i++)
swap(&traffic[0][i], &traffic[temp][i]);
}
for(m=0; m<nTraffics; m++)
{
load_count(m);
}
fprintf(fp1, "%d nodes strictly nonblocking with traffic=%d and g=%d.\n", nNodes, nTraffics, Granularity);
max_line=max_line_load[0];
for(m=1; m<nTraffics; m++) if(max_line<max_line_load[m]) max_line=max_line_load[m];
min_Waves=(max_line+Granularity-1)/Granularity;
max_Waves=NVars/2;
max_ADMs=NVars;
min_ADMs=ceil((min_Waves+sqrt(4*NVars*min_Waves+min_Waves*min_Waves))/2.0);
fprintf(fp1, "Maximum possible ADM's: %d \n", max_ADMs);
fprintf(fp1, "Minimum possible ADM's: %6.2f \n", min_ADMs);
fprintf(fp1, "Maximum possible Wavelengths: %d \n", max_Waves);
fprintf(fp1, "Minimum possible Wavelengths: %d \n", min_Waves);
for(run=0; run<RunTime; run++)
{
max[run][0]=10000; max[run][1]=10000;
display=10;
initiate();
temp_split=0;
/* begin evolution */
for(k=0; k<NVars; k++)
for(i=0; i<nNodes; i++)
ring[k][i]=0;
//对每个个体进行操作
for(k=0;k<NVars;k++)
for(m=0; m<nTraffics; m++)
for(l=0; l<nNodes; l++)
load[k][m][l]=0;
for(p=0; p<PopSize; p++)
{
nWave=0; nADMs=0;listpoint=0;max_split=0;
for(k=0; k<nTraffics; k++)
for(i=0; i<NVars; i++)
{temp_traffic[k][i]=traffic[k][i];split_list[k][i]=0;}
for(l=0;l<240;l++)
for(m=0;m<nTraffics;m++)
for(k=0;k<240;k++)
load[l][m][k]=0;
distribute(p,min_Waves);
//NVars=nNodes*(nNodes-1);
for(k=0; k<nWave; k++)
for(i=0; i<nNodes; i++)
if(ring[k][i]) { nADMs++; ring[k][i]=0; }
fitness[p][0]=nADMs; fitness[p][1]=nWave;
if(temp_split<max_split) temp_split=max_split;
} // end of for(p=0...)
//对计算得到的种群进行杂交变异；
for(gen=1; gen<MaxGens; gen++)
{
// printf("Generation=%d\n", gen);
crossover();
mutation();
for(p=PopSize; p<count; p++)
{
nWave=0; nADMs=0;listpoint=0;max_split=0;
for(k=0; k<nTraffics; k++)
for(i=0; i<NVars; i++)
{temp_traffic[k][i]=traffic[k][i];split_list[k][i]=0;}
for(l=0;l<240;l++)
for(m=0;m<nTraffics;m++)
for(k=0;k<240;k++)
load[l][m][k]=0;
distribute(p,min_Waves);
/*for(i=0;i<nWave;i++)
for(m=0; m<nTraffics; m++)
for(l=0; l<nNodes; l++)
if(load[i][m][l]<0||load[i][m][l]>16)
printf("load[%d][%d][%d]=%d",i,m,l,load[i][m][l]);*/
//split();
for(k=0; k<nWave; k++)
for(i=0; i<nNodes; i++)
if(ring[k][i]) { nADMs++; ring[k][i]=0; }
fitness[p][0]=nADMs; fitness[p][1]=nWave;
if(temp_split<max_split) temp_split=max_split;
} // end of for(p=PopSize...)
// order the fitness and select the PopSize hightest tifness (least AMD's and Wavelengths) individuals
for(i=0; i<PopSize; i++)
for(j=i+1; j<count; j++)
if(fitness[i][0]>fitness[j][0])
{
swap(&fitness[i][0], &fitness[j][0]);
swap(&fitness[i][1], &fitness[j][1]);
for(k=0; k<NVars; k++)
swap(&pop[i][k], &pop[j][k]);
}
else if(fitness[i][0]==fitness[j][0])
{
if(fitness[i][1]>fitness[j][1])
{
swap(&fitness[i][1], &fitness[j][1]);
for(k=0; k<NVars; k++)
swap(&pop[i][k], &pop[j][k]);
}
}
// calculation of the average number
if(max[run][0]>fitness[0][0])
{
max[run][0]=fitness[0][0];
max[run][1]=fitness[0][1];
maxgen[run]=gen;
}
else if(max[run][0]==fitness[0][0])
{
if(max[run][1]>fitness[0][1])
{
max[run][1]=fitness[0][1];
maxgen[run]=gen;
}
}
if(gen*100==display*MaxGens)
{ printf("run=%d, %d%% finished\n", run, display); display+=10; }
} //end of for(gen...)
fprintf(fp1, "max_split: %d, ", temp_split);
} // end of for(run...)
fprintf(fp1, "\n");
avemaxgen=0.0; avemax[0]=0.0; avemax[1]=0.0;
maxmax[0]=max_ADMs; maxmax[1]=max[0][1]; mingen=MaxGens;
for(run=0; run<RunTime; run++)
{
avemaxgen+=maxgen[run];
avemax[0]+=max[run][0];
avemax[1]+=max[run][1];
if(mingen>maxgen[run]) mingen=maxgen[run];
if(maxmax[0]>max[run][0])
{
maxmax[0]=max[run][0];
maxmax[1]=max[run][1];
}
else if(maxmax[0]==max[run][0])
{
if(maxmax[1]>max[run][1])
maxmax[1]=max[run][1];
}
}
avemaxgen=avemaxgen/RunTime;
avemax[0]=avemax[0]/RunTime;
avemax[1]=avemax[1]/RunTime;
// output
fprintf(fp1, "Minimum ADMs of each run: ");
ftemp=0.0;
for(i=0; i<RunTime; i++)
{
fprintf(fp1, "%d, ", max[i][0]);
ftemp+=(max[i][0]-avemax[0])*(max[i][0]-avemax[0]);
}
ftemp/=(RunTime+1);
ftemp=sqrt(ftemp);
fprintf(fp1, "\nAVE_ADMs: %4.2lf, MIN_ADMs: %d, ", avemax[0], maxmax[0]);
fprintf(fp1, "VAR_ADMs: %6.4lf\n", ftemp);
fprintf(fp1, "Minimum Wavelengths of each run: ");
ftemp=0.0;
for(i=0; i<RunTime; i++)
{
fprintf(fp1, "%d, ", max[i][1]);
ftemp+=(max[i][1]-avemax[1])*(max[i][1]-avemax[1]);
}
ftemp/=(RunTime+1);
ftemp=sqrt(ftemp);
fprintf(fp1, "\nAVE_Waves: %4.2lf, MIN_Waves: %d, ", avemax[1], maxmax[1]);
fprintf(fp1, "VAR_Waves: %6.4lf\n", ftemp);
fprintf(fp1, "Gen of Minimum ADMs is in: ");
ftemp=0.0;
for(i=0; i<RunTime; i++)
{
fprintf(fp1, "%d, ", maxgen[i]);
ftemp+=(maxgen[i]-avemaxgen)*(maxgen[i]-avemaxgen);
}
ftemp/=(RunTime+1);
ftemp=sqrt(ftemp);
fprintf(fp1, "\nAve-Gen: %8.2lf, Min-gen: %d", avemaxgen*200, mingen*200);
fprintf(fp1, "VAR_Gen: %8.2lf\n\n", ftemp*200);
start_finish=clock()-start_finish;
run_time = (double)(start_finish) / CLOCKS_PER_SEC;
fprintf(fp1, "Running time: %6.4lf\n\n", run_time);
fclose(fp1);
} //end of for(nNodes=....)
fclose(fp2);
printf("End of the program.\n\n");
return(1);
} /* end of main function */
void initiate(void)
{
int i, j, k, g, temp;
for(i=0; i<PopSize*2; i++)
{
k=i;
for(j=0; j<NVars; j++)
{
if(k>=NVars) k=0;
pop[i][j]=k++;
}
}
for(g=0; g<PopSize*2; g++)
for(k=0; k<NVars/2; k++)
{
i=rand()%NVars;
j=rand()%NVars;
temp=pop[g][i];
pop[g][i]=pop[g][j];
pop[g][j]=temp;
}
}
void swap(int *i, int *j)
{
int temp;
temp=*i; *i=*j; *j=temp;
}
void crossover(void)
{
int pop1, pop2;
int point1, point2;
int i, j, g, num, num2, temp;
int index1[16*15], index2[16*15];
// int order1[16*15], order2[16*15];
double prob;
count=PopSize;
for(i=0; i<PopSize; i+=2)
{
prob=(rand()%1000)/1000.0;
if(prob<PXover)
{
pop1=rand()%PopSize;
while((pop2=rand()%PopSize)==pop1);
point1=(rand()%(NVars-1))+1;
while((point2=(rand()%(NVars-1))+1)==point1);
if(point1>point2)
{ temp=point1; point1=point2; point2=temp; }
for(j=point1; j<point2; j++)
{
pop[count][j]=pop[pop2][j];
pop[count+1][j]=pop[pop1][j];
}
for(j=0; j<point1; j++)
{
pop[count][j]=pop[pop1][j];
pop[count+1][j]=pop[pop2][j];
}
for(j=point2; j<NVars; j++)
{
pop[count][j]=pop[pop1][j];
pop[count+1][j]=pop[pop2][j];
}
num=0;
for(j=point1; j<point2; j++)
{
for(g=point1; g<point2; g++){
if(pop[pop2][j]==pop[pop1][g])
break;
}
if(g==point2)
index1[num++]=pop[pop2][j];
}
num2=0;
for(j=point1; j<point2; j++)
{
for(g=point1; g<point2; g++){
if(pop[pop1][j]==pop[pop2][g])
break;
}
if(g==point2)
index2[num2++]=pop[pop1][j];
}
if(num!=num2)
printf("Alarming num!=num2");
for(j=0; j<num-1; j++){
for(g=j+1; g<num; g++)
{
if(index1[j]<index1[g])
{ temp=index1[j]; index1[j]=index1[g]; index1[g]=temp; }
if(index2[j]<index2[g])
{ temp=index2[j]; index2[j]=index2[g]; index2[g]=temp; }
}
}
for(g=0; g<num; g++)
{
for(j=0; j<point1; j++){
if(pop[pop1][j]==index1[g])
{
pop[count][j]=index2[g];
break;
}
}
if(j==point1)
for(j=point2; j<NVars; j++){
if(pop[pop1][j]==index1[g])
{
pop[count][j]=index2[g];
break;
}
}
}
count++;
for(g=0; g<num; g++)
{
for(j=0; j<point1; j++){
if(pop[pop2][j]==index2[g])
{
pop[count][j]=index1[g];
break;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -