fuzzy-vrp-2.cpp
来自「车辆行驶路线优化（Vehicle Routing Problem）」· C++ 代码 · 共 707 行
CPP
707 行
#include<math.h>
#include<iostream.h>
#include<utlab.h>
#define popsize 40
#define node 11
#define vehicle 4
#define S 15.
int x[popsize][node+1]; //染色体 popsize个
int y[popsize][vehicle+1]; //染色体 popsize个
double t[popsize][vehicle+1]; //染色体 popsize个
int x_tmp[popsize][node+1]; //染色体 popsize个,转轮临时放置
int y_tmp[popsize][vehicle+1]; //染色体 popsize个,转轮临时放置
double t_tmp[popsize][vehicle+1]; //染色体 popsize个,转轮临时放置
int d[node+1][node+1]=
{ 0, 18, 14, 14, 21, 21, 15, 22, 21, 28, 24, 14,
18, 0, 20, 34, 49, 55, 49, 65, 57, 49, 50, 22,
14, 20, 0, 15, 31, 41, 43, 56, 55, 52, 56, 35,
14, 34, 15, 0, 16, 28, 36, 46, 51, 51, 58, 44,
21, 49, 31, 16, 0, 16, 32, 37, 48, 52, 62, 54,
21, 55, 41, 28, 16, 0, 21, 21, 36, 43, 54, 55,
17, 49, 43, 36, 32, 21, 0, 15, 16, 22, 34, 41,
22, 65, 56, 46, 37, 21, 15, 0, 21, 33, 44, 56,
21, 57, 55, 51, 48, 36, 16, 21, 0, 13, 24, 43,
28, 49, 52, 51, 52, 43, 22, 33, 13, 0, 11, 32,
24, 50, 56, 58, 62, 54, 34, 44, 24, 11, 0, 36,
14, 22, 35, 44, 54, 55, 41, 56, 43, 32, 36, 0,
};
int tw[node+1][2]=
{0, 0,
90, 370,
80, 180,
100, 190,
130, 360,
80, 300,
70, 440,
100, 320,
20, 120,
100, 250,
50, 260,
80, 120,
};
int tt[node+1][node+1][3]=
{
0,0,0, 25,50,75, 5,10,15, 25,50,75, 7,15,23, 25,50,75, 25,50,75, 12,25,38, 7,15,23, 25,50,75, 10,20,30, 25,50,75,
25,50,75, 0,0,0, 20,40,60, 5,10,15, 25,50,75, 17,35,53, 7,15,23, 20,40,60, 20,40,60, 7,15,23, 22,45,68, 5,10,15,
5,10,15, 20,40,60, 0,0,0, 20,40,60, 7,15,23, 17,35,53, 20,40,60, 15,30,45, 5,10,15, 22,45,68, 12,25,38, 17,35,53,
25,50,75, 5,10,15, 20,40,60, 0,0,0, 22,45,68, 15,30,45, 2,5,8, 17,35,53, 22,45,68, 5,10,15, 22,45,68, 15,30,45,
7,15,23, 25,50,75, 7,15,23, 22,45,68, 0,0,0, 17,35,53, 22,45,68, 7,15,23, 10,20,30, 22,45,68, 7,15,23, 17,35,53,
25,50,75, 17,35,53, 17,35,53, 15,30,45, 17,35,53, 0,0,0, 15,30,45, 12,25,38, 17,35,53, 15,30,45, 15,30,45, 5,10,15,
25,50,75, 7,15,23, 20,40,60, 2,5,8, 22,45,68, 15,30,45, 0,0,0, 17,35,53, 20,40,60, 5,10,15, 20,40,60, 15,30,45,
12,25,38, 20,40,60, 15,30,45, 17,35,53, 7,15,23, 12,25,38, 17,35,53, 0,0,0, 17,35,53, 20,40,60, 5,10,15, 5,10,15,
7,15,23, 20,40,60, 5,10,15, 22,45,68, 10,20,30, 17,35,53, 20,40,60, 17,35,53, 0,0,0, 20,40,60, 12,25,38, 17,35,53,
25,50,75, 7,15,23, 22,45,68, 5,10,15, 22,45,68, 15,30,45, 5,10,15, 20,40,60, 20,40,60, 0,0,0, 22,45,68, 17,35,53,
10,20,30, 22,45,68, 12,25,38, 22,45,68, 7,15,23, 15,30,45, 20,40,60, 5,10,15, 12,25,38, 22,45,68, 0,0,0, 15,30,45,
25,50,75, 5,10,15, 17,35,53, 15,30,45, 17,35,53, 5,10,15, 15,30,45, 5,10,15, 17,35,53, 17,35,53, 15,30,45, 0,0,0,
};
int rdint(int l,int r)//生成l-r的随机整数
{
double x;
int a;
x=myu(l,r+0.99);
a=int(floor(x));
return(a);
}
void init(int dis0)//初始化数据
{
int i,j,k,w,nm;
double counter=0.;
int ct;
int distance(int m);
double dist;
int tt[node+1];
int te;
int judge;
for(i=1;i<=node;i++)
tt[i]=0;
for(i=0;i<popsize;i++)
{
nm=0;
dist=1000.;
while((dist>dis0))
{
for(k=1;k<=node;k++)
tt[k]=0;
j=1;
while(j<=node)
{
te=rdint(1,node);
judge=1;
for(k=1;k<=node;k++)
if(tt[k]==te)
judge=judge*0;
if(judge==1)
{
x[i][j]=te;
tt[j]=te;
j++;
}
else
continue;
}
//以上初始化x.
for(k=1;k<vehicle;k++)
{
y[i][k]=rdint(0,node);
}
//sort
for(j=1; j<vehicle; j++)
for(k=j+1; k<vehicle; k++)
if(y[i][j] > y[i][k])
{
w = y[i][k];
y[i][k] = y[i][j];
y[i][j] = w;
}
y[i][0]=0;
y[i][vehicle]=node;
//以上初始化y
for(k=1;k<=vehicle;k++)
{
t[i][k]=double(rdint(30.,120.));
}
//以上初始化t
dist=distance(i);
nm++;
}
system("cls");
counter=double(i)/popsize*100;
ct=floor(counter);
cout<<"Initializing..."<<ct<<"%"<<endl;
}
system("cls");
cout<<"Initializing...100%"<<endl;
}
void chrom(int a)
{
double cr(int );
int distance(int );
int j;
cout<<endl;
cout<<"x["<<a<<"]="<<endl;
for(j=1;j<=node;j++)
cout<<x[a][j]<<" ";
cout<<endl;
cout<<"y["<<a<<"]="<<endl;
for(j=0;j<=vehicle;j++)
cout<<y[a][j]<<" ";
cout<<endl;
cout<<"t["<<a<<"]="<<endl;
for(j=0;j<=vehicle;j++)
cout<<t[a][j]<<" ";
cout<<endl;
cout<<"cr = "<<cr(a)<<" dist= "<<distance(a)<<endl;
}
void crossover(int a, int b)
{
int i;
double c;
c=myu(0,1);
double tp;
int yp;
for(i=1;i<=vehicle;i++)
{
tp =c*t[a][i]+(1-c)*t[b][i];
t[b][i]=t[a][i]*(1-c)+t[b][i]*c;
t[a][i]=tp;
}//crossover t[a], t[b]
for(i=1;i<=vehicle;i++)
{
yp=y[a][i];
y[a][i]=y[b][i];
y[b][i]=yp;
}//crossover y.
}//crossover tested.
double min(double a, double b)
{
if (a>b)
return b;
else return a;
}
double max(double a, double b)
{
if (a<b)
return b;
else return a;
}
void mutation(int a, int dis0)
{
int i,j,k, n1, n2, nn, xx, w, tm;
double M;
void map(int a, int b);
void bmap(int a, int b);
int distance(int);
double cr(int m);
double dt[vehicle+1];
tm=0;
M=1.;
map(a,a);
mutatet: n1=rdint(1,node);
n2=rdint(1,node);
if(n1>n2)
{
nn=n1;
n1=n2;
n2=nn;
}
for(i=n1;i<=n2;i++)
{
nn=rdint(i,n2);
xx=x[a][i];
x[a][i]=x[a][nn];
x[a][nn]=xx;
}
//mutate x
n1=rdint(1,vehicle-1);
n2=rdint(1,vehicle-1);
if(n1>n2)
{
nn=n1;
n1=n2;
n2=nn;
}
for(i=n1;i<=n2;i++)
{
y[a][i]=rdint(0,node);
}
for(j=1; j<vehicle; j++)
for(k=j+1; k<vehicle; k++)
if(y[a][j] > y[a][k])
{
w = y[a][k];
y[a][k] = y[a][j];
y[a][j] = w;
}
//mutate y
dt[0]=0.;
for(i=1;i<=vehicle;i++)
{
dt[i]=myu(0.,60.) - 30.;
}
for(i=1;i<=vehicle;i++)
{
if(dt[i]>=0.)
t[a][i]=min(460., t[a][i] + dt[i]*M);
else
t[a][i]=max(10., t[a][i] + dt[i]*M);
}
if(distance(a)<=dis0)
;
else if(tm<6)
{
bmap(a,a);
M=myu(0.,M);
tm++;
goto mutatet;
}
else bmap(a,a);
//mutate t;
}
int distance(int m)//the m-th chrom's distance
{
int dis=0;
int i,j;
for(i=0;i<node;i++)
dis+=d[x[m][i]][x[m][i+1]];
dis+=d[x[m][11]][0];
for(j=1;j<vehicle;j++)
{
if(y[m][j]!=y[m][j-1])
{
dis+=d[x[m][y[m][j]]][0];
dis+=d[x[m][y[m][j]+1]][0];
dis-=d[x[m][y[m][j]]][x[m][y[m][j]+1]];
}
}
return dis;
}
void map(int a, int b) // original a-->temp b duplicate chrom.
{
int i;
for(i=0;i<=node;i++)
x_tmp[b][i]=x[a][i];
for(i=0;i<=vehicle;i++)
{
y_tmp[b][i]=y[a][i];
t_tmp[b][i]=t[a][i];
}
}
void bmap(int a, int b) // temp a--> original b duplicate chrom.
{
int i;
for(i=0;i<=node;i++)
x[b][i]=x_tmp[a][i];
for(i=0;i<=vehicle;i++)
{
y[b][i]=y_tmp[a][i];
t[b][i]=t_tmp[a][i];
}
}
double cr(int m) //Cr{ai<fi<bi, i=1,2,...,n} for the m-th chrom.
{
int N=3000;
int i,j,k;
int jg=1;
double eps=0.2;
double tf=0.;
double mu[node+1]; //membership functions
double miu;
double mu1=0.;
double mu2=0.; //membership function for right and wrong
int v[node+1];
double f[node+1];
int counter=0;
//为xi编号，表示到达的vehicle。
k=0;
for(i=1;i<=vehicle;i++)
{
if(y[m][i]!=y[m][i-1])
{
for(j=k+1;j<=y[m][i];j++)
v[j]=i;
k=j-1;
}
else ;
}
v[0]=0;
x[m][0]=0;
for(i=0;i<(N-20);i++)
{
//generate rd number
for(j=1;j<=node;j++)
{
if(v[j]!=v[j-1])
{
tf=myu(tt[0][x[m][j]][0],tt[0][x[m][j]][2]);
mu[j]=triangle(tf,tt[0][x[m][j]][0],tt[0][x[m][j]][1],tt[0][x[m][j]][2]);
f[j]=t[m][v[j]]+tf;
}
else
{
tf=myu(tt[x[m][j-1]][x[m][j]][0],tt[x[m][j-1]][x[m][j]][2]);
mu[j]=triangle(tf,tt[x[m][j-1]][x[m][j]][0],tt[x[m][j-1]][x[m][j]][1],tt[x[m][j-1]][x[m][j]][2]);
f[j]=max(f[j-1],tw[x[m][j-1]][0])+S+tf;
}
}
mu[0]=1.;
miu=1.;
for(j=1;j<=node;j++)
miu=min(miu,mu[j]);
jg=1;
for(j=1;j<=node;j++)
if((f[j]<tw[x[m][j]][0])||(f[j]>tw[x[m][j]][1]))
jg=0;
else ;
//judge
if(jg==1)
mu1=max(mu1,miu);
else
mu2=max(mu2,miu);
}
for(;i<N;i++)
{
//generate rd number
for(j=1;j<=node;j++)
{
if(v[j]!=v[j-1])
{
tf=myu(tt[0][x[m][j]][1]-eps,tt[0][x[m][j]][1]+eps);
mu[j]=triangle(tf,tt[0][x[m][j]][0],tt[0][x[m][j]][1],tt[0][x[m][j]][2]);
f[j]=t[m][v[j]]+tf;
}
else
{
tf=myu(tt[x[m][j-1]][x[m][j]][1]-eps,tt[x[m][j-1]][x[m][j]][1]+eps);
mu[j]=triangle(tf,tt[x[m][j-1]][x[m][j]][0],tt[x[m][j-1]][x[m][j]][1],tt[x[m][j-1]][x[m][j]][2]);
f[j]=max(f[j-1],tw[x[m][j-1]][0])+S+tf;
}
}
mu[0]=1.;
miu=1.;
for(j=1;j<=node;j++)
miu=min(miu,mu[j]);
//miu is the membership function of the i-th sample
jg=1;
for(j=1;j<=node;j++)
if((f[j]<tw[x[m][j]][0])||(f[j]>tw[x[m][j]][1]))
jg=0;
else ;
//judge
if(jg==1)
mu1=max(mu1,miu);
else
mu2=max(mu2,miu);
}
double cre;
cre=0.5*(1.+mu1-mu2);
return (cre);
}
void GAforcr(int dis0,double pc, double pm)
{
double r;
int c=0;
int i,j,k,N,times;
int cross[2];
double ob[popsize];
double fit[popsize];
double sumob;
int best;
double bestob;
int xb[node+1];
int yb[vehicle+1];
double tb[vehicle+1]; //save the best
for(i=0;i<=node;i++)
xb[i]=x[0][i];
for(i=0;i<=vehicle;i++)
{
yb[i]=y[0][i];
tb[i]=t[0][i];
}
bestob=cr(0);
best=0;
N=500;
for(i=0;i<popsize;i++)
fit[i]=0.;
for(times=0;times<N;times++)
{
//crossover
for(i=0;i<popsize;i++)
{
r=myu(0.,1.);
if(r<pc)
{
cross[c]=i;
c++;
}
if(c==2)
{
map(cross[0],cross[0]);
map(cross[1],cross[1]);
crossover(cross[0],cross[1]);
if(distance(cross[0])>dis0)
{
bmap(cross[0],cross[0]);
}
if(distance(cross[1])>dis0)
{
bmap(cross[1],cross[1]);
}
c=0;
}
}
//mutation
for(i=0;i<popsize;i++)
{
r=myu(0.,1.);
if(r<pm)
{
map(i,i);
mutation(i,dis0);
}
}
//objective value
for(i=0;i<popsize;i++)
{
ob[i]=cr(i);
}
sumob=0.;
for(i=0;i<popsize;i++)
{
sumob=sumob+ob[i];
}
//fitness
fit[0]=ob[0]/sumob;
for(i=1;i<popsize;i++)
{
fit[i]=fit[i-1]+(ob[i]/sumob);
}
//roulette wheel
for(i=0;i<popsize;i++)
{
r=myu(0., fit[popsize-1]);
for(k=0;k<popsize-1;k++)
{
if(r<=fit[0])
{
map(0,i);
}
else if((r>fit[k])&&(r<=fit[k+1]))
{
map(k+1,i); //duplicate to temp
}
else
;
}
//getchar();
}
for(i=0;i<popsize;i++)
{
bmap(i,i); //duplicate back
}
k=0;r=0.;
for(i=0;i<popsize;i++)
{
if(r<cr(i))
{
r=cr(i);
k=i;
}
}
if(r>bestob)
{
best=k;
for(j=0;j<=node;j++)
xb[j]=x[k][j];
for(j=0;j<=vehicle;j++)
{
yb[j]=y[k][j];
tb[j]=t[k][j];
}
bestob=r;
for(j=0;j<=node;j++)
x[0][j]=xb[j];
for(j=0;j<=vehicle;j++)
{
y[0][j]=yb[j];
t[0][j]=tb[j];
}
}
else
{
for(j=0;j<=node;j++)
x[0][j]=xb[j];
for(j=0;j<=vehicle;j++)
{
y[0][j]=yb[j];
t[0][j]=tb[j];
}
}
cout<<"generate: "<<times<<endl;
cout<<"maxob= "<<bestob<<endl;
chrom(0);
cout<<endl;
}
cout<<"pc= "<<pc<<" pm= "<<pm<<endl;
}
void main()
{
int dis0=285;
cout<<"enter dis0 (285) "; cin>>dis0;
double pc,pm;
cout<<"enter pc ";
cin>>pc;
cout<<"enter pm ";
cin>>pm;
cout<<"Enter to start: "<<endl;
getchar();
init(dis0);
GAforcr(dis0,pc,pm);
getchar();
}
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?