cpp1.cpp

主要包括：物流配送重心选址、车辆调度、定位运输。

# include <stdio.h>
# include <stdlib.h>
# include<conio.h>
# include <time.h>
# include <windows.h>
typedef struct INDIVIDUAL
{
int *lpchrom;
double rVal;
double rFitness;
}INDIVIDUAL,*LPINDIVIDUAL;
const double MAX_DISTANCE=1E+7;
const double MIN_FITNESS=1E-5;
FILE *fpIn,*fpOut,*fpOut1;
int RandRange(int nMin,int nMax)
{
int nrand;
nrand=rand();
return(nrand*(nMax-nMin)/RAND_MAX+nMin);
}
int RandDist(int nMin,int nMax,int *lpdist)
{
int i,j,n;
BOOL fsame=FALSE;
n=nMax-nMin+1;
for(i=0;i<n;i++)
{
lpdist[i]=RandRange(nMin,nMax+1);
while(lpdist[i]<nMin|| lpdist[i]>nMax)
lpdist[i]=RandRange(nMin,nMax+1);
while(1)
{
fsame=FALSE;
for(j=0;j<i;j++)
{
if(lpdist[j]==lpdist[i])
{
fsame=TRUE;
break;
}
}
if(!fsame)
break;
lpdist[i]=RandRange(nMin,nMax+1);
while(lpdist[i]<nMin||lpdist[i]>nMax)
lpdist[i]=RandRange(nMin,nMax+1);
}
}
return TRUE;
}
BOOL GAInitIndividual(LPINDIVIDUAL lpIndividual,int n)
{
if(!lpIndividual)
return FALSE;
lpIndividual->lpchrom=(int*)calloc(n+1,sizeof(int));
if(!lpIndividual->lpchrom)
return FALSE;
lpIndividual->rVal=0.0;
lpIndividual->rFitness=0.0;
return TRUE;
}
void GADestroyIndividual(LPINDIVIDUAL lpIndividual)
{
if(lpIndividual->lpchrom)
{
free(lpIndividual->lpchrom);
lpIndividual->lpchrom=NULL;
}
}
void GASelectionOperator(INDIVIDUAL pop[],INDIVIDUAL newpop[],int npop,int n)
{
double sum,rfitness;
int i,p,j,k;
static unsigned t;
sum=0.0;
for(i=0;i<npop;i++)
sum+=pop[i].rFitness;
if(t==0)
t=time(NULL);
t+=1024;
rand();
srand(t);
rand();
rand();
for(j=0;j<npop;j++)
{
p=RandRange(0,100);
i=0;
rfitness+=pop[i].rFitness;
while(p>(int)(rfitness/sum*100))
{
i++;
rfitness+=pop[i].rFitness;
}
newpop[j].rFitness=pop[i].rFitness;
newpop[j].rVal=pop[i].rVal;
for(k=0;k<n;k++)
newpop[j].lpchrom[k]=pop[i].lpchrom[k];
}
}
void GACrossoverOperator(INDIVIDUAL pop[],int npop,int n,double pc)
{
int i,j,k;
int*index;
int point,temp,p1,p2,p;
static unsigned t=0;
index=(int*)calloc(npop,sizeof(int));
if(t==0)
t=time(NULL);
t+=1024;
rand();
srand(t);
rand();
rand();
for(i=0;i<npop;i++)
index[i]=i;
for(i=0;i<npop;i++)
{
point=RandRange(0,npop-i-1);
temp=index[i];
index[i]=index[point+i];
index[point+i]=temp;
}
for(i=0;i<npop-1;i+=2)
{
p=RandRange(0,100);
if(p<(int)(pc*100))
{
p1=RandRange(0,n);
p2=RandRange(0,n);
if(p1>p2)
{
temp=p1;
p1=p2;
p2=temp;
}
p1+=1;
if(p1>=p2)
continue;
for(j=p1;j<p2;j++)
{
for(k=0;k<p1;k++)
{
if(pop[index[index[i]]].lpchrom[k]==pop[index[i+1]].lpchrom[j])
pop[index[i]].lpchrom[k]=pop[index[i]].lpchrom[j];
if(pop[index[i+1]].lpchrom[k]==pop[index[i]].lpchrom[j])
pop[index[i+1]].lpchrom[k]=pop[index[i+1]].lpchrom[j];
}
for(k=p2;k<n;k++)
{
if(pop[index[index[i]]].lpchrom[k]==pop[index[i+1]].lpchrom[j])
pop[index[i]].lpchrom[k]=pop[index[i]].lpchrom[j];
if(pop[index[i+1]].lpchrom[k]==pop[index[i]].lpchrom[j])
pop[index[i+1]].lpchrom[k]=pop[index[i+1]].lpchrom[j];
}
}
for(j=p1;j<p2;j++)
{
temp= pop[index[i]].lpchrom[j];
pop[index[i]].lpchrom[j]=pop[index[i+1]].lpchrom[j];
pop[index[i+1]].lpchrom[j]=temp;
}
}
}
free(index);
}
void GAMutationOperator(INDIVIDUAL pop[],int npop,int n,double pm)
{
int i,p,p1,p2,temp;
static unsigned t=0;
if(t==0)
t=time(NULL);
t+=1024;
rand();
srand(t);
rand();
rand();
for(i=0;i<npop;i++)
{
p=RandRange(0,100);
if(p<(int)(pm*100))
{
p1=RandRange(0,n);
p2=RandRange(0,n);
temp=pop[i].lpchrom[p1];
pop[i].lpchrom[p1]=pop[i].lpchrom[p2];
pop[i].lpchrom[p2]=temp;
}
}
}
BOOL GAChrom2Path(int l,int*d,int k,int*b,int*lpchrom,int*lppath)
{
int n,kk,m;
int i;
BOOL bValid;
int*dz,*bb,*ip;
n=k*l;
dz=(int*)calloc(l,sizeof(int));
bb=(int*)calloc(k,sizeof(int));
ip=(int*)calloc(k,sizeof(int));
for(i=0;i<1;i++)
dz[i]=0;
for(i=0;i<k;i++)
bb[i]=b[i];
for(i=0;i<k;i++)
ip[i]=l;
for(i=0;i<n;i++)
{
kk=(lpchrom[i]-l)/l+l;
m=lpchrom[i]-(lpchrom[i]-l)/l*l;
if(dz[m-l]==0)
{
if(dz[m-l]<=bb[kk-l])
{
dz[m-l]=l;
bb[kk-l]=d[m-l];
lppath[(kk-1)*l+ip[kk-l]-l]=m;
ip[kk-l]++;
}
}
} 
bValid=TRUE;
for(i=0;i<l;i++)
{
if(dz[i]==0)
{
bValid=FALSE;
break;
}
}
free(dz);
free(bb);
free(ip);
return bValid;
}
BOOL GAFindFeasibleChrom(int l,int d[],int k,int*b,int*lpchrom)
{
int*lppath,i,n,*ic,*s;
BOOL bValid;
static unsigned t=0;
n=k*l;
lppath=(int*)calloc(n,sizeof(int));
if(!lppath)
return FALSE;
ic=(int*)calloc(n,sizeof(int));
if(!ic)
return FALSE;
s=(int*)calloc(n,sizeof(int));
if(!s)
return FALSE;
bValid=FALSE;
while(bValid==FALSE)
{
for(i=0;i<n;i++)
lpchrom[i]=0;
if(t==0)
t=time(NULL);
else
t+=1024;
rand();
srand(t);
rand();
rand();
RandDist(l,n,ic);
t+=1024;
srand(t);
rand();
rand();
RandDist(l,n,s);
for(i=0;i<n;i++)
lpchrom[ic[i]-1]=s[i];
bValid=GAChrom2Path(l,d,k,b,lpchrom,lppath);
}
free(ic);
free(s);
free(lppath);
return TRUE;
}
double EvaluatePath(int k,int l,int*lppath,double*lpdist)
{
int i,j,ll;
double val;
ll=l+l;
val=0.0;
for(i=0;i<k;i++)
{
//Center to the last warehouse
val+=lpdist[0+lppath[i*l]];
j=l;
while(lppath[i*l+j]>0)
{
val+=lpdist[lppath[i*l+j-1]*ll+lppath[i*l+j]];
j++;
}
//the last warehouse to center
val+=lpdist[0+lppath[i*l+j-1]];
}
return val;
}
double EvaluateChrom(int l,int*d,int k,int*b,int*lpchrom,double*lpdist)
{
int*lppath;
lppath=(int*)calloc(k*l,sizeof(int));
if(GAChrom2Path(l,d,k,b,lpchrom,lppath))
return EvaluatePath(k,l,lppath,lpdist);
return MAX_DISTANCE;
}
void GAGenerateInitialPop(INDIVIDUAL pop[],int npop,int l,int*d,int k,int*b)
{
int i;
for(i=0;i<npop;i++)
{
GAInitIndividual(&(pop[i]),k*l);
GAFindFeasibleChrom(l,d,k,b,pop[i].lpchrom);
}
}
void GADestroyPop(INDIVIDUAL pop[],int npop)
{
int i;
for(i=0;i<npop;i++)
GADestroyIndividual(&(pop[i]));
}
void GAEvaluatePop(INDIVIDUAL pop[],int npop,int l,int*d,int k,int *b,double *lpdist)
{
int i;
for(i=0;i<npop;i++)
{
pop[i].rVal=EvaluateChrom(l,d,k,b,pop[i].lpchrom,lpdist);
pop[i].rFitness=1.0/pop[i].rVal;
}
}
void GAGenerateNextPop(INDIVIDUAL pop[],int npop,int n,double pc,double pm)
{
LPINDIVIDUAL newpop;
int  i,j;
newpop=( LPINDIVIDUAL)calloc(npop,sizeof(INDIVIDUAL));
for(i=0;i<npop;i++)
GAInitIndividual(&(newpop[i]),n);
GASelectionOperator(pop,newpop,npop,n);
for(i=0;i<npop;i++)
{
pop[i].rFitness=newpop[i].rFitness;
pop[i].rVal=newpop[i].rVal;
for(j=0;j<n;j++)
{
pop[i].lpchrom[j]=newpop[i].lpchrom[j];
}
}
GACrossoverOperator(pop,npop,n,pc);
GAMutationOperator(pop,npop,n,pm);
for(i=0;i<npop;i++)
GADestroyIndividual(&(newpop[i]));
free(newpop);
}
INDIVIDUAL indBest={NULL,0,0};
void GAPerformEvolution(INDIVIDUAL pop[],int npop,int l,int *d,int k,int *b,double *lpdist)
{
int i,ibest,iworst,n;
BOOL bfirst=FALSE;
n=k*l;
if(indBest.lpchrom==NULL)
{
indBest.lpchrom=(int*)calloc(n,sizeof(int));
indBest.rFitness=0.0;
indBest.rVal=0.0;
bfirst=TRUE;
}
ibest=iworst=0;
for(i=1;i<npop;i++)
{
if(pop[i].rFitness>pop[ibest].rFitness)
ibest=i;
if(pop[i].rFitness<pop[iworst].rFitness)
iworst=i;
}
if(pop[ibest].rFitness>indBest.rFitness)
{
indBest.rFitness=pop[ibest].rFitness;
indBest.rVal= pop[ibest].rVal;
for(i=0;i<n;i++)
indBest.lpchrom[i]=pop[ibest].lpchrom[i];
}
if(!bfirst)
{
pop[iworst].rFitness=indBest.rFitness;
pop[iworst].rVal= indBest.rVal;
for(i=0;i<n;i++)
pop[iworst].lpchrom[i]=indBest.lpchrom[i];
for(i=1;i<npop;i++)
{
if(pop[i].rFitness<MIN_FITNESS)
{
GAFindFeasibleChrom(l,d,k,b,pop[i].lpchrom);
pop[i].rVal=EvaluateChrom(l,d,k,b,pop[i].lpchrom,lpdist);
pop[i].rFitness=1.0/pop[i].rVal;
}
}
}
}
void OutputTextReport(INDIVIDUAL pop[],int npop,int n,int igen)
{
int i;
double sum,ave;
sum=0.0;
for(i=0;i<npop;i++)
sum+=pop[i].rFitness;
ave=sum/npop;
fprintf(fpOut,"\n====================\n");
fprintf(fpOut,"gen=％d,avg=％lf,best=％0.21f\n",igen,ave,indBest.rVal);
for(i=0;i<n;i++)
{
fprintf(fpOut,"％ld\t",indBest.lpchrom[i]);
}
}
void OutputPop(INDIVIDUAL pop[],int npop,int n,int igen)
{
int i,j;
fprintf(fpOut1,"\n==========================\n");
fprintf(fpOut1, "gen=％d\n",igen);
for(i=0;i<npop;i++)
{
fprintf(fpOut1,"\n");
for(j=0;j<n;j++)
{
fprintf(fpOut1,"％ld\t",pop[i].lpchrom[j]);
}
fprintf(fpOut1,"\n");
}
}
void main()
{
char szlnFile[]="vrp.in";
char szOutFile[]="vrp.out";
char szOutFile1[]="vrp.out1";
int npop,ngen,igen;
double pc,pm;
int l,*d,k,*b,bb,*lppath,ll;
int i,j;
double *lpdist;
LPINDIVIDUAL pop;
BOOL bValid;
fpIn=fopen(szlnFile,"r");
printf("Go to here!");
if(!fpIn)
{
printf("Cannot open vrp.in for reading!");
return;
}
fpOut=fopen(szOutFile,"w");
if(!fpOut)
{
printf("Cannot open vrp.out for writing!");
return;
}
fpOut1= fopen(szOutFile1,"w");
rewind(fpIn);
//read Population size
fscanf(fpIn, "％ld",&npop);
//read generation count

fscanf(fpIn,"％ld",&ngen);
//read crossover probability
fscanf(fpIn,"％lf",&pc);
//read mutation probability
fscanf(fpIn,"％lf",&pm);
fscanf(fpIn,"％ld",&l);
d=(int*)calloc(l,sizeof(int));
for(i=0;i<l;i++)
{
fscanf(fpIn,"％ld",d+i);

}
fscanf(fpIn,"％ld",&k);
b=(int*)calloc(k,sizeof(int));
fscanf(fpIn,"％ld",&bb);
for(i=0;i<k;i++)
b[i]=bb;
//Read in distances berween warehouses
ll=l+l;
lpdist=(double*)calloc((ll*ll),sizeof(double));
for(i=0;i<ll;i++)
{
for(j=i;j<ll;j++)
{
fscanf(fpIn,"％lf",&(lpdist[i*ll+j]));
lpdist[j*ll+i]=lpdist[i*ll+j];
}
}
pop=(LPINDIVIDUAL)calloc(npop,sizeof(INDIVIDUAL));
igen=0;
GAGenerateInitialPop(pop,npop,l,d,k,b);
GAEvaluatePop(pop,npop,l,d,k,b,lpdist);
GAPerformEvolution(pop,npop,l,d,k,b,lpdist);
OutputPop(pop,npop,k*l,igen);
OutputTextReport(pop,npop,k*l,igen);
while (igen<ngen)
{
igen++;
GAGenerateNextPop(pop,npop,k*l,pc,pm);
GAEvaluatePop(pop,npop,l,d,k,b,lpdist);
GAPerformEvolution(pop,npop,l,d,k,b,lpdist);
OutputPop(pop,npop,k*l,igen);
OutputTextReport(pop,npop,k*l,igen);
}
lppath=(int*)calloc(k*l,sizeof(int));
bValid=GAChrom2Path(l,d,k,b,indBest.lpchrom,lppath);
//fprintf(fpOut);
fprintf(fpOut,"\t");
for(i=0;i<ll;i++)
fprintf(fpOut,"％ld\t\t",i);
for(i=0;i<ll;i++)
{
fprintf(fpOut,"\n");
fprintf(fpOut,"％ld\t",i);
for(j=0;j<ll;j++)
{
fprintf(fpOut,"％0.2lf\t",lpdist[i*ll+j]);
}
}

fprintf(fpOut,"\n");
for(i=0;i<k;i++)
{
fprintf(fpOut,"\n％ld\t",0);
j=0;
while(lppath[i*l+j]>0)
{
fprintf(fpOut,"％ld\t",lppath[i*l+j]);
j++;
}
fprintf(fpOut,"％ld\n",0);
}
free(lppath);
GADestroyPop(pop,npop);
free(pop);
GADestroyIndividual(&indBest);
fclose(fpIn);
fclose(fpOut);
free(d);
free(b);
free(lpdist);
}