strict16_nonblocking.c

源文件为个人用于优化环形网络的遗传算法程序代码

				}
			}
			if(j==point1){
				for(j=point2; j<NVars; j++){
				if(pop[pop2][j]==index2[g])
				{
					pop[count][j]=index1[g];
					break;
				}
				}
			}
		}
		count++;		  
	  if(count>=PopSize*2) break;
	  }// end of if(prob<PXover)
  }  // end of for(i=0; ...)
 }

 void mutation(void)
 {
  int i, g, point1, point2, temp;
  double prob;
  for(i=0; i<PopSize; i++)
  {
  	  if(count>=PopSize*2) break;
	  prob=(rand()%1000)/1000.0;
	  if(prob<PMutation)
	  {
		  point1=(rand()%(NVars-1))+1;		  
		  while(abs((point2=(rand()%(NVars-1))+1)-point1)<=1);
		  if(point1>point2)
		  {  temp=point1; point1=point2; point2=temp; }
		  for(g=0; g<point1; g++)
			  pop[count][g]=pop[i][g];
		  for(g=point2; g<NVars; g++)
			  pop[count][g]=pop[i][g];
		  for(g=point1; g<point2; g++)
			  pop[count][g]=pop[i][point2+point1-1-g];
			count++;		  
	  }
  }
 }

 int pack_ring(int i, int j, int m, int k, int w)
 {
	 int l;
      if(j>i)
	  {
		  for(l=i; l<j; l++)
			  if(load[w][m][l]+k>Granularity) break;
		  if(l==j) return(1);
		  return(0);
	  }
	  for(l=i; l<nNodes; l++)
		  if(load[w][m][l]+k>Granularity) break;
	  if(l==nNodes)
	  {	  for(l=0; l<j; l++)
			  if(load[w][m][l]+k>Granularity) break;
		  if(l==j) return(1);
		  return(0);
	  }
	  return(0);
 }


void distribute(int p,int min_Waves) // used for distribute traffic 
{   
	 int i, j, k, l, g1, w, m, point, point1, pack;
 for(g=0; g<NVars; g++)
  {
	  k=pop[p][g];
	  i=I[k]; j=J[k];
	  for(m=0;m<nTraffics;m++)
		  if(temp_traffic[m][k]) break;
	  if(m==nTraffics) continue;//如果所有组业务都为零，则跳过
	  pack=(temp_traffic[0][k]==0)? 1: pack_ring(i, j, 0, temp_traffic[0][k],nWave);
	  for(m=1; m<nTraffics; m++)
	  {
		  if(!pack) break;
		  pack=(temp_traffic[m][k]==0)? 1: pack_ring(i, j, m, temp_traffic[m][k],nWave);
	  }
	  if(pack)
	  {  ring[nWave][i]++; ring[nWave][j]++;
	  	for(m=0; m<nTraffics; m++)
		{if(j>i)
			for(l=i; l<j; l++)
			   load[nWave][m][l]+=temp_traffic[m][k];
		 else
		 {	for(l=i; l<nNodes; l++)
			   load[nWave][m][l]+=temp_traffic[m][k];
			for(l=0; l<j; l++)
			   load[nWave][m][l]+=temp_traffic[m][k];
		 }
		}
next3:	for(point=0;point<listpoint;point+=2)//if can't get traffic from temp_traffic to fit the wavelength, try split_list
		{	k=split_list[0][point];
			i=I[k]; j=J[k];
			for(w=nWave;w>=0;w--)	
			{	if(ring[w][i]&&ring[w][j])
				{	pack=(split_list[0][point+1]==0)? 1: pack_ring(i, j, 0, split_list[0][point+1],w);
					for(m=1; m<nTraffics; m++)
					{	if(!pack) break;
						pack=(split_list[m][point+1]==0)? 1: pack_ring(i, j, m,split_list[m][point+1],w);
					}
					if(pack)
					{  for(m=0; m<nTraffics; m++)
						{	if(j>i)
								for(l=i; l<j; l++)
									load[w][m][l]+=split_list[m][point+1];
							else	
							{	for(l=i; l<nNodes; l++)
									load[w][m][l]+=split_list[m][point+1];
								for(l=0; l<j; l++)
									load[w][m][l]+=split_list[m][point+1];
							}// end of else		 
							split_list[m][point]=split_list[m][listpoint-2];
							split_list[m][point+1]=split_list[m][listpoint-1];
							split_list[m][listpoint-2]=0;split_list[m][listpoint-1]=0;//交换，置零。
						}//end of for()
						listpoint-=2;point-=2;	//because point should point at current position
					}
				}
			}// end of for(w=nWave;w>=0;w--)
		}  // end of packing split_list 
		for(g1=g+1; g1<NVars; g1++)
		 {	 k=pop[p][g1];
			 i=I[k]; j=J[k];			 
			 for(m=0;m<nTraffics;m++)
				 if(temp_traffic[m][k]) break;
			 if(m==nTraffics) continue;//如果所有组业务都为零，则跳过
			 if(ring[nWave][i]&&ring[nWave][j])
			 {	 pack=(temp_traffic[0][k]==0)? 1: pack_ring(i, j, 0, temp_traffic[0][k],nWave);
				 for(m=1; m<nTraffics; m++)
				 {	 if(!pack) break;
					 pack=(temp_traffic[m][k]==0)? 1: pack_ring(i, j, m, temp_traffic[m][k],nWave);
				 } 
				 if(pack)
				 {	for(m=0; m<nTraffics; m++)
					 {	 if(j>i)
							for(l=i; l<j; l++)
							   load[nWave][m][l]+=temp_traffic[m][k];
						 else
						 {
							for(l=i; l<nNodes; l++)
							   load[nWave][m][l]+=temp_traffic[m][k];
							for(l=0; l<j; l++)
							   load[nWave][m][l]+=temp_traffic[m][k];
						 }
					/* for(l=0;l<240;l+=3)
		 				if(split_traffic[nWave][m][l]==i&&split_traffic[nWave][m][l+1]==j)
							split_traffic[nWave][m][l+2]+=temp_traffic[m][k];*/
					 }
					 swap(&pop[p][g+1], &pop[p][g1]);
					 g++;
				 }				 
			 }// end of if(ring[nWave][i]&&ring[nWave][j])
		 }		
	  }
	  else
	  {	  distribute_ring(p,g);
		  nWave++;	
		  k=pop[p][g];
		  i=I[k]; j=J[k];
		  ring[nWave][i]++; ring[nWave][j]++; 
		  for(m=0; m<nTraffics; m++)
		  {
			  if(j>i)
			  	  for(l=i; l<j; l++)
				  	  load[nWave][m][l]=temp_traffic[m][k];
			  else
			  {
				  for(l=i; l<nNodes; l++)
				  	  load[nWave][m][l]=temp_traffic[m][k];
				  for(l=0; l<j; l++)
				  	  load[nWave][m][l]=temp_traffic[m][k];
			  }			
		  }
		  goto next3;
	  }
  }//end of packing g individuals
  if(listpoint!=0)	//if there still remains some traffics in split_list[m][listpoint]
  {for(point=0;(point<listpoint)&&(listpoint>0);point+=2)  //先将未检验的业务尽量并入现有的ADM
	{	k=split_list[0][point];
		i=I[k]; j=J[k];
		for(w=nWave;w>=0;w--)//检查所有波长
	{	if(ring[w][i]&&ring[w][j])
		{	pack=(split_list[0][point+1]==0)? 1: pack_ring(i, j, 0, split_list[0][point+1],w);
			for(m=1; m<nTraffics; m++)
			{	if(!pack) break;
				pack=pack_ring(i, j, m,split_list[m][point+1],w);} 
			if(pack)
			{ 	for(m=0; m<nTraffics; m++)
				{	if(j>i)
						for(l=i; l<j; l++)
							load[w][m][l]+=split_list[m][point+1];
					else	
					{	for(l=i; l<nNodes; l++)	
							load[w][m][l]+=split_list[m][point+1];
						for(l=0; l<j; l++)
							load[w][m][l]+=split_list[m][point+1];
					}// end of else		 	 
					split_list[m][point]=split_list[m][listpoint-2];
					split_list[m][point+1]=split_list[m][listpoint-1];
					split_list[m][listpoint-2]=0;split_list[m][listpoint-1]=0;//交换，置零。
				}
				listpoint-=2;point-=2;
			}
		}//end of if(ring&&ring)
	}// end of for(w=nWave;w>=0;w--)
	}// end of for(point=0;(point<listpoint)&&(listpoint>0);point+=2) 
	for(point=0;point<listpoint;point+=2)//无法并入，尝试添加ADM与波长，同时listpoint不改变
	{	k=split_list[0][point];
		i=I[k]; j=J[k];		
		pack=(split_list[0][point+1]==0)? 1: pack_ring(i, j, 0, split_list[0][point+1],nWave);
		for(m=1; m<nTraffics; m++)
		{	if(!pack) break;
			pack=pack_ring(i, j, m,split_list[m][point+1],nWave);}
		if(pack)
		{ 	ring[nWave][i]++; ring[nWave][j]++;
			for(m=0; m<nTraffics; m++)
			{	if(j>i)
					for(l=i; l<j; l++)
						load[nWave][m][l]+=split_list[m][point+1];
				else	
				{	for(l=i; l<nNodes; l++)	
						load[nWave][m][l]+=split_list[m][point+1];
					for(l=0; l<j; l++)
						load[nWave][m][l]+=split_list[m][point+1];
				}// end of else	 
			}
loop:		for(point1=(point+2);point1<listpoint;point1+=2)
			{	k=split_list[0][point1];
				i=I[k]; j=J[k];
				if(ring[nWave][i]&&ring[nWave][j])
			{	pack=(split_list[0][point1+1]==0)? 1: pack_ring(i, j, 0, split_list[0][point1+1],nWave);
				for(m=1; m<nTraffics; m++)
				{	if(!pack) break;
					pack=pack_ring(i, j, m,split_list[m][point1+1],nWave);} 
				if(pack)
				{ 	for(m=0; m<nTraffics; m++)
					{	if(j>i)
							for(l=i; l<j; l++)
								load[nWave][m][l]+=split_list[m][point1+1];
						else	
						{	for(l=i; l<nNodes; l++)	
								load[nWave][m][l]+=split_list[m][point1+1];
							for(l=0; l<j; l++)
								load[nWave][m][l]+=split_list[m][point1+1];
						}// end of else		 
					 swap(&split_list[m][point1], &split_list[m][point]);
					 swap(&split_list[m][point1+1], &split_list[m][point+1]);
					}
					point+=2;
				}
			}//end of if(ring&&ring)
			}//end of for(point1=(point+2);(point1<listpoint)&&(listpoint>0);point1+=2)
		}//end of if(pack)
		else
		{	nWave++;	
			//if(point<0) point=0;
			ring[nWave][i]++; ring[nWave][j]++; 
			for(m=0; m<nTraffics; m++)
			{	if(j>i)
					for(l=i; l<j; l++)
						load[nWave][m][l]=split_list[m][point+1];
				else	
				{	for(l=i; l<nNodes; l++)
					    load[nWave][m][l]=split_list[m][point+1];
					for(l=0; l<j; l++)
						load[nWave][m][l]=split_list[m][point+1];
				}// end of else		 
			}//end of for()
			goto loop;
		}// end of else
	}// end of 添加ADM
} // end of packing split_list  if(m!=nTraffics)
	for(w=0;w<=nWave;w++)
		for(m=0;m<nTraffics;m++)
			for(l=0;l<nNodes;l++)
					load[w][m][l]=0;
	nWave++; 
	return;
}

void distribute_ring(int p, int g)    // to try to distribute all of the remaining traffic
{
  int g1,k,remain_load,i,temp,m,j,l;  
  for(g1=NVars-1; g1>g; g1--)  // for all of the genes which is smaller than g
  {
	k=pop[p][g1];
	i=I[k]; j=J[k];	
	remain_load=Granularity;
	if(ring[nWave][i]&&ring[nWave][j])
	{	if(i<j)
		{	for(m=0;m<nTraffics;m++)//对不同组的业务不同时进行
			{	for(l=i;l<j;l++)//选择最小的空闲容量
				{	if(Granularity<=load[nWave][m][l]) break;
					temp=Granularity-load[nWave][m][l];
					if(temp<remain_load) remain_load=temp;
				}
				if(l!=j) break;
				if(temp_traffic[m][k]>remain_load)
				{	for(l=i;l<j;l++)
						load[nWave][m][l]+=remain_load;
					temp_traffic[m][k]-=remain_load;
				}
			}				
		}
		else 
		{
			for(m=0;m<nTraffics;m++)
			{
				for(l=i;l<nNodes;l++)
				{
					if(Granularity<=load[nWave][m][l]) break;
					temp=Granularity-load[nWave][m][l];
					if(temp<remain_load) remain_load=temp;
				}
				if(l!=nNodes) break;
				for(l=0;l<j;l++)	
				{
					if(Granularity<=load[nWave][m][l]) break;
					temp=Granularity-load[nWave][m][l];
					if(temp<remain_load) remain_load=temp;
				}
				if(l!=j) break;
				if(temp_traffic[m][k]>remain_load)
				{
					for(l=i;l<nNodes;l++)
						load[nWave][m][l]+=remain_load;
					for(l=0;l<j;l++)
						load[nWave][m][l]+=remain_load;
					temp_traffic[m][k]-=remain_load;
				}
			}
		}
	}
  }
}

void search_split_ring(int p,int g, int min_Waves)//当M组业务分叉后都能被装入时才装入
{	int g1,l,i,j,i1,k,k1,tempNodes,nextNodes,length, m,temp,ADMnumber,ADM[16];
	if(max_split>(1.6*min_Waves)) return;
	ADMnumber=0;
	for(l=0;l<nNodes;l++)	ADM[l]=0;
	for(l=0;l<nNodes;l++)
		if(ring[nWave][l])  {ADM[ADMnumber]=l; ADMnumber++;}
	for(length=(ADMnumber-1);length>0;length--)//searching for the longest length at first
	{	for(tempNodes=0;tempNodes<ADMnumber;tempNodes++)
		{	for(g1=g+1;g1<NVars;g1++)
			{	k=pop[p][g1];
				i=I[k];j=J[k];				
				for(m=0;m<nTraffics;m++)   //是否m组数据都是零
					{if(temp_traffic[m][k]) break;}
				if(m==nTraffics) continue;  //是则提前结束
				if(i==ADM[tempNodes])
				{	if(tempNodes+length>=ADMnumber) nextNodes=(tempNodes+length-ADMnumber);
					else nextNodes=tempNodes+length;
					if(ADM[tempNodes]<ADM[nextNodes]&&(j>ADM[nextNodes]||j<i))//源节点小于目标节点
					{	for(m=0;m<nTraffics;m++)//当m组业务同时满足时
						{	for(temp=i;temp<ADM[nextNodes];temp++)
							if((temp_traffic[m][k]+load[nWave][m][temp])>Granularity)
								break;
							if(temp!=ADM[nextNodes]) break;
						}
						if(m==nTraffics)
						{	for(m=0;m<nTraffics;m++)
							{	for(l=i;l<ADM[nextNodes];l++)
									load[nWave][m][l]+=temp_traffic[m][k];
								i1=ADM[nextNodes];
								k1=K[i1][j];
								split_list[m][listpoint]=k1;
								split_list[m][listpoint+1]=temp_traffic[m][k];
								temp_traffic[m][k]=0;
							}
							listpoint+=2;
							max_split++;
							//if(max_split>=min_Waves) return;
						}
					}
					if(ADM[tempNodes]>ADM[nextNodes]&&j>ADM[nextNodes]&&j<i)//源节点大于目标节点
					{	for(m=0;m<nTraffics;m++)
						{	for(temp=i;temp<nNodes;temp++)
								if((temp_traffic[m][k]+load[nWave][m][temp])>Granularity)
									break;
							if(temp!=nNodes)  break;
						}
						if(m==nTraffics)
						{	for(m=0;m<nTraffics;m++)
							{	for(temp=0;temp<ADM[nextNodes];temp++)
									if((temp_traffic[m][k]+load[nWave][m][temp])>Granularity)
										break;
								if(temp!=ADM[nextNodes]) break;
							}
							if(m==nTraffics)
							{	for(m=0;m<nTraffics;m++)
								{	for(l=i;l<nNodes;l++)
										load[nWave][m][l]+=temp_traffic[m][k];
									for(l=0;l<ADM[nextNodes];l++)
										load[nWave][m][l]+=temp_traffic[m][k];
									i1=ADM[nextNodes];
									k1=K[i1][j];
									split_list[m][listpoint]=k1;
									split_list[m][listpoint+1]=temp_traffic[m][k];
									temp_traffic[m][k]=0;
								}						
								listpoint+=2;
								max_split++;
								//if(max_split>=min_Waves) return;
							}
						}
					}// end of if(ADM[tempNodes]>ADM[nextNodes]&&j>ADM[nextNodes]&&j<i)
				}//end of if(i==ADM[tempNodes])
			}// end of for(tempNodes=0;tempNodes<ADMnumber;tempNodes++) for(g1=g+1;g1<NVars;g1++)
		}//if(listpoint>240) printf("wrong with listpoint!! %d", listpoint);
	}//for(length=(ADMnumber-1);length>0;length--)
}


void load_count(int m)
 {
 	 int i, j, k, l;
	 for(i=0; i<nNodes; i++)
	 {
		in_load[i]=0;
		out_load[i]=0;
		line_load[i]=0;
	 }
	 for(l=0; l<NVars/2; l++)
	 {
	    i=I[l]; j=J[l];
	 in_load[j]+=traffic[m][l];
	 out_load[i]+=traffic[m][l];
	 for(k=i; k<j; k++)
	 line_load[k]+=traffic[m][l];
	 }
 	 for(l=NVars/2; l<NVars; l++)
	 {
	    i=I[l]; j=J[l];
	 in_load[j]+=traffic[m][l];
	 out_load[i]+=traffic[m][l];
	 for(k=i; k<nNodes; k++)
	 line_load[k]+=traffic[m][l];
	 for(k=0; k<j; k++)
	 line_load[k]+=traffic[m][l];
	 }
	 max_line_load[m]=line_load[0];
	 for(i=0; i<nNodes; i++)
	 {
		node_load[m][i]=in_load[i]>out_load[i]? in_load[i]: out_load[i];
		if(max_line_load[m]<line_load[i]) max_line_load[m]=line_load[i];
	 }
 }

 
 /* END */