采用遗传算法和模拟退火算法解决VLSI中的布局优化问题

/*11 no soft! Search3212.c --- Searching Process */ #include "allhead.h" #include <sys/times.h> #include <math.h> /* #define max(a,b) ((a>b)?(a):(b)) */ /* global */ extern MODULE *ModuleListHead; extern int InstanceNum; extern STATUS *Status ; extern INSTANCE *InstanceList[MAXMODULE+1]; extern NET *NetListHead; extern int *PSoftNum; extern float *PLowBound; extern float *PUpBound; extern int SoftNum; extern float R; extern int fitflag; /* add by lxb */ struct CHROMOSOME; CHROMOSOME *ch; double r_soft[17]; extern void GetArea(); extern float GetWireLength(); extern void OutputResult(); typedef struct tagUNIT{ int n; struct tagUNIT * link; } UNIT; int Constrain(Status,k,j) STATUS *Status; int k,j; { INSTANCE *Inst=InstanceList[MAXMODULE+1]; double ck; r_soft[1]=1.1,r_soft[2]=1/1.1,r_soft[3]=1.2,r_soft[4]=1/1.2,r_soft[5]=1.3,r_soft[6]=1/1.3,r_soft[7]=1.4,r_soft[8]=1/1.4,r_soft[9]=1.5,r_soft[10]=1/1.5,r_soft[11]=1.6,r_soft[12]=1/1.6,r_soft[13]=1.7,r_soft[14]=1/1.7,r_soft[15]=1.8,r_soft[16]=1/1.8; ck=(InstanceList[j]->Width/InstanceList[j]->Height)*r_soft[k]*r_soft[k]; if((ck>PLowBound[j])||(ck<PUpBound[j])) return 1; else return 0; } int Find(p,key) int *p; int key; { int m; for(m=0;m<SoftNum;m++) { if(key==PSoftNum[m]) return 1; } return 0; } int initial(x) int x; { int i,num; FILE *fp; fp=fopen("str33.txt","r"); if (fp==NULL) return 0; else { fscanf(fp,"%d",&num); if (num == InstanceNum) { fscanf(fp,"%f",&R); for(i=1;i<=InstanceNum;i++) fscanf(fp,"%d%d%d%d%d",&ch[x].Seq[i],&ch[x].Order1[i],&Status->Rotate[i],&Status->Reflect[i],&Status->Softblock[i]); for(i=1;i<=InstanceNum*2+1;i++) fscanf(fp,"%d",&ch[x].Order2[i]); return 1; } else return 0; } } /******************************************** //生成长度为num的由1,2,...,num随机构成 //的序列,并返回其指针 *********************************************/ int RandSeq(seq) int *seq; { UNIT units[MAXMODULE+1]; UNIT * pUnit; int ran; int i, j; for(i=0; i<InstanceNum; i++){ units[i].n = i; units[i].link = units+i+1; } units[InstanceNum].n = InstanceNum; units[InstanceNum].link = NULL; for(i=0; i<InstanceNum; i++){ pUnit = units; ran = rand()%(InstanceNum-i); for(j=0; j<ran; j++) pUnit = pUnit->link; seq[i] = pUnit->link->n; pUnit->link = pUnit->link->link; } return 1; } /******************************************** // 判断长度为num的数组a和数组b是否相等 // 相等则返回true,否则返回false *********************************************/ int Equequal_al(equal_a,equal_b,num) int *equal_a; int *equal_b; int num; { int i; for(i=0; i<num; i++) if(equal_a[i] != equal_b[i]) return 0; return 1; } /******************************************** // “确定性”法计算适应值为F[]的染色体数组 // 各个染色体的被选中次数st[] *********************************************/ int Determinacy(determincy_F,st,determincy_size) double *determincy_F; int *st; int determincy_size; { double *de; int *sn; double sumF = 0; int sumst = 0; int i, j; double td; int ti; de = (double*)malloc(determincy_size*sizeof(double)); sn = (int*)malloc(determincy_size*sizeof(int)); for (i=0; i<determincy_size; i++) { sn[i] = i; sumF += determincy_F[i]; } for (i=0; i<determincy_size; i++) { st[i] = (int)(determincy_size*determincy_F[i]/sumF); sumst += st[i]; de[i] = determincy_size*determincy_F[i]/sumF - st[i]; } for (i=0; i<determincy_size; i++){ for (j=determincy_size-1; j>i; j--){ if (de[j] > de[j-1]){ td = de[j-1]; de[j-1] = de[j]; de[j] = td; ti = sn[j-1]; sn[j-1] = sn[j]; sn[j] = ti; } } } for (i=0; i<determincy_size-sumst; i++) st[sn[i]]++; free(sn); free(de); return 1; } /******************************************** // “轮盘赌”法计算适应值为F[]的染色体数组 // 各个染色体的被选中次数st[] *********************************************/ /* void Roulette(double* & F, int* & st, int N){ double * p = new double[N]; double sumF = 0; double s = 0; double r; int i, j; for (i=0; i<N; i++) { sumF += F[i]; st[i] = 0; } for (i=0; i<N; i++){ p[i] = F[i]/sumF; } for (i=0; i<N; i++){ r = (double)rand()/RAND_MAX; s = 0; j = 0; while (s < r) { s += p[j]; j ++; } st[j-1] ++; } delete[] p; } */ /******************************************** // 根据规模为N的染色体种群ch中 // 各个体适应值F[]获得新种群 *********************************************/ int Selection(selection_F, selection_size) double *selection_F; int selection_size; { int i, j; int *e = (int*)malloc(selection_size*sizeof(int)); Determinacy(selection_F, e, selection_size); /* for (i=0; i<selection_size; i++) printf("%f %d ", selection_F[i], e[i]); printf("\n"); */ i = 0, j = 0; for (i=0; i<selection_size; i++){ while (e[i] > 1){ while(e[j] > 0) j++; CopySeq(ch[j].Seq, ch[i].Seq, InstanceNum+1); CopySeq(ch[j].Order1, ch[i].Order1, InstanceNum+1); CopySeq(ch[j].Order2, ch[i].Order2, 2*InstanceNum+1); e[i] --; e[j] ++; } } free(e); return 1; } /******************************************** // 复制长度为num的数组b到数组a *********************************************/ int CopySeq(copyseq_a, copyseq_b, copyseq_num) int *copyseq_a; int *copyseq_b; int copyseq_num; { int i; for(i=0; i<copyseq_num; i++) copyseq_a[i] = copyseq_b[i]; return 1; } /******************************************** // 以pc为概率对规模为size的染色体种群ch // 实行交叉 *********************************************/ int Crossover(pc, crossover_size) double pc; int crossover_size; { int i, j; int cp; int Type; float r; for (i=0; i<crossover_size; i++){ r = (rand()%100000)/100000.0; if (r < pc){ for (j=i+1; j<crossover_size; j++){ r = (rand()%100000)/100000.0; if (r < pc) { Type = rand()%6; switch(Type) { case 0: cp = rand()%InstanceNum+1; SeqCross(ch[i].Seq, ch[j].Seq, InstanceNum+1, cp); break; case 1: cp = rand()%InstanceNum+1; ExchangeSeq(ch[i].Order1+cp, ch[j].Order1+cp, InstanceNum+1-cp); break; case 2: cp = rand()%InstanceNum+1; ExchangeSeq(ch[i].Order1+cp, ch[j].Order1+cp, InstanceNum+1-cp); break; case 3: cp = rand()%InstanceNum+1; ExchangeSeq(ch[i].Order1+cp, ch[j].Order1+cp, InstanceNum+1-cp); break; case 4: cp = rand()%(2*InstanceNum)+1; ExchangeSeq(ch[i].Order2+cp, ch[j].Order2+cp, 2*InstanceNum+1-cp); break; case 5: cp = rand()%(2*InstanceNum)+1; ExchangeSeq(ch[i].Order2+cp, ch[j].Order2+cp, 2*InstanceNum+1-cp); break; } break; } } i = j; } } return 1; } /******************************************** // 交换长度为num的数组a[],b[]的值 *********************************************/ int ExchangeSeq(exchangeseq_a, exchangeseq_b, num) int *exchangeseq_a; int *exchangeseq_b; int num; { int temp; int i; for (i=0; i<num; i++){ temp = exchangeseq_a[i]; exchangeseq_a[i] = exchangeseq_b[i]; exchangeseq_b[i] = temp; } return 1; } /******************************************** // 对长度为num，交叉位为cp的两个整数序列编码 // a[]和b[]进行“常规交叉” *********************************************/ int SeqCross(seqcross_a, seqcross_b, seqcross_num, cp) int *seqcross_a; int *seqcross_b; int seqcross_num; int cp; { int i, j, k; int ta[MAXMODULE+1]; int tb[MAXMODULE+1]; CopySeq(ta, seqcross_a, seqcross_num); CopySeq(tb, seqcross_b, seqcross_num); for (i=cp; i<seqcross_num; i++){ /* 获得交叉后的a[] *