?? fuzzy-fla-1.cpp
字號:
// Hybrid Intelligent Algorithm (Stochastic Simulation + GA)
// facility location-allocation problem
# include <iostream.h>
# include <conio.h>
# include <math.h>
# include <stdlib.h>
# include <stdio.h>
# include <time.h>
const int POP_SIZE=30;
const int GEN=1000; //gen is generation
const int N=6; //N is the output number
const int M=1;
const int size = 100;
const int samplenumber=10000;
const int integralnumber=2000;
const int customer=8; //顧客數目
const int facility=3; //需要選擇地址的設備數目
const int TYPE=-1;
double CHROMOSOME[POP_SIZE+1][N+1]; //decision variable
double OBJECTIVE[POP_SIZE+1][M+1]; //optimal cost
double q[POP_SIZE+1]; //evaluation function
double eval[POP_SIZE];
double l=0.08;
double P_MUTATION=0.4;
double P_CROSSOVER=0.5;
double aa[17];
//-----------------------------------------------------------------------------
double matrix[size][size],xx[size]; //單純型算法
int a[size];
int m=24,n=11,s,type=0;
int indexe,indexl,indexg;
void Jckxj()
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<s;j++)
if(matrix[i][j]==1&&a[j]==1){
xx[j]=matrix[i][s];
j=s;
}
for(i=0;i<s;i++)
if(a[i]==0) xx[i]=0;
}
int Rj()
{
int i;
for(i=0;i<s;i++)
if(fabs(matrix[n][i])>=0.000001)
if(matrix[n][i]<0) return 0;
return 1;
}
int Min()
{
int i,temp=0;
double min=matrix[n][0];
for(i=1;i<s;i++)
if(min>matrix[n][i]){
min=matrix[n][i];
temp=i;
}
return temp;
}
void JustArtificial()
{
int i;
for(i=m+indexe+indexl;i<s;i++)
if(fabs(xx[i])>=0.000001){
//printf("No Answer\n");
return;
}
}
int Check(int in)
{
int i;
double max1=-1;
for(i=0;i<n;i++)
if(fabs(matrix[i][in])>=0.000001&&max1<matrix[i][s]/matrix[i][in])
max1=matrix[i][s]/matrix[i][in];
if(max1<0)
return 1;
return 0;
}
int SearchOut(int *temp,int in)
{
int i;
double min=10000;
for(i=0;i<n;i++)
if(fabs(matrix[i][in])>=0.000001&&(matrix[i][s]/matrix[i][in]>=0)&&min>matrix[i][s]/matrix[i][in]){
min=matrix[i][s]/matrix[i][in];
*temp=i;
}
for(i=0;i<s;i++)
if(a[i]==1&&matrix[*temp][i]==1)
return i;
return 0;
}
void Mto(int in,int temp)
{
int i;
for(i=0;i<=s;i++)
if(i!=in)
matrix[temp][i]=matrix[temp][i]/matrix[temp][in];
matrix[temp][in]=1;
}
void Be(int temp,int in)
{
int i,j;
double c;
for(i=0;i<=n;i++){
c=matrix[i][in]/matrix[temp][in];
if(i!=temp)
for(j=0;j<=s;j++)
matrix[i][j]=matrix[i][j]-matrix[temp][j]*c;
}
}
void Achange(int in,int out)
{
int temp=a[in];
a[in]=a[out];
a[out]=temp;
}
void Print()
{
int i,k,temp=0;
for(i=0;i<n;i++){
for(k=temp;k<s;k++)
if(a[k]==1){
temp=k+1;
k=s;
}
}
}
void Merge(double nget[][size],double nlet[][size],double net[][size],double b[])
{
int i,j;
for(i=0;i<n;i++){
for(j=m;j<m+indexe;j++)
if(nget[i][j-m]!=-1) matrix[i][j]=0;
else matrix[i][j]=-1;
for(j=m+indexe;j<m+indexe+indexl;j++)
if(nlet[i][j-m-indexe]!=1) matrix[i][j]=0;
else matrix[i][j]=1;
for(j=m+indexe+indexl;j<s;j++)
if(net[i][j-m-indexe-indexl]!=1) matrix[i][j]=0;
else matrix[i][j]=1;
matrix[i][s]=b[i];
}
for(i=m;i<m+indexe+indexl;i++)
matrix[n][i]=0;
for(i=m+indexe+indexl;i<s;i++)
matrix[n][i]=size;
matrix[n][s]=0;
}
void ProcessA()
{
int i;
for(i=0;i<m+indexe;i++)
a[i]=0;
for(i=m+indexe;i<s;i++)
a[i]=1;
}
void Input(double b[],int code[])
{
int i=0,j=0;
cin>>m>>n;
for(i=0;i<n;i++){
cin>>b[i]>>code[i];
for(j=0;j<m;j++)
cin>>matrix[i][j];
}
do{
cin>>type;
}while(type!=0&&type!=1);
for(i=0;i<m;i++)
cin>>matrix[n][i];
if(type==1)
for(i=0;i<m;i++)
matrix[n][i]=-matrix[n][i];
}
void Xartificial()
{
int i,j,k;
if(indexg!=0){
for(i=m+indexe+indexl;i<s;i++){
for(j=0;j<n;j++)
if(matrix[j][i]==1){
for(k=0;k<=s;k++)
matrix[n][k]=matrix[n][k]-matrix[j][k]*size;
j=n;
}
}
}
}
void Process(double c[][size],int row,int vol)
{
int i;
for(i=0;i<n;i++)
if(i!=row) c[i][vol]=0;
}
void Sstart(double b[],int code[])
{
int i;
for(i=0;i<size;i++)
{
xx[i]=0;
a[i]=0;
}
double nget[size][size],nlet[size][size],net[size][size];
indexe=indexl=indexg=0;
for(i=0;i<n;i++){
if(code[i]==0){nlet[i][indexl++]=1; Process(nlet,i,indexl-1);}
if(code[i]==1){ net[i][indexg++]=1; Process(net,i,indexg-1); }
if(code[i]==2){
net[i][indexg++]=1;
nget[i][indexe++]=-1;
Process(net,i,indexg-1); Process(nget,i,indexe-1);
}
}
s=indexe+indexl+indexg+m;
Merge(nget,nlet,net,b);
ProcessA();
Xartificial();
}
void Simplix()
{
int in,out,temp=0;
while(1){
Jckxj();
Print();
if(!Rj()) in=Min();
else {
if(indexg!=0) JustArtificial();
return;
}
if(Check(in)){
matrix[n][s]=0;
return;
}
out=SearchOut(&temp,in);
Mto(in,temp);
Be(temp,in);
Achange(in,out);
}
}
//-----------------------------------------------------------------------------------------
double myu(double a, double b) //a,b之間的隨機數 均勻分布
{
double y;
y = (double)rand( )/(RAND_MAX);
return (a+(b-a)*y);
}
double trapezoidal(double x, double a, double b, double c, double d) //梯形模糊變量
{
if(a<x&&x<b) return (x-a)/(b-a);
if(b<=x&&x<=c) return 1;
if(c<x&&x<d) return (x-d)/(c-d);
return 0;
}
int constraint_check(double x[N+1]) //選址范圍是0～100
{
for(int i=1;i<=N;i++)
if(x[i]>100||x[i]<0)
return 0;
return 1;
}
double fuzzymean(double f[], double mu[], int samplenumber) //計算模糊變量的期望
{
int i,k;
double Expect=0, left=9999, right=-9999, b1,b2,r;
for(i=1;i<=samplenumber;i++) {
if(left>f[i]) left=f[i];
if(right<f[i]) right=f[i];
}
for(k=1; k<=integralnumber; k++) {
r=myu(left,right);
b1=0;
b2=0;
if(r>=0) {
for(i=1; i<=samplenumber; i++) {
if(f[i]>=r&&b1<mu[i]) b1 = mu[i];
if(f[i]<r&&b2<mu[i]) b2 = mu[i];
}
Expect = Expect+(b1+1-b2)/2.0;
}
else {
for(i=1; i<=samplenumber; i++) {
if(f[i]<=r&&b1<mu[i]) b1 = mu[i];
if(f[i]>r&&b2<mu[i]) b2 = mu[i];
}
Expect = Expect-(b1+1-b2)/2.0;
}
}
return Expect*(right-left)/integralnumber+((left>0)?left:0)+((right<0)?right:0);
}
void Init_GA( ) //決策變量初始化
{
double x[N+1];
int i,j;
for(i=1; i<=POP_SIZE; i++)
{
mark:
x[1] = myu(0, 100);
x[2] = myu(0, 100);
x[3] = myu(0, 100);
x[4] = myu(0, 100);
x[5] = myu(0, 100);
x[6] = myu(0, 100);
if(constraint_check(x)==0)
goto mark;
for(j=1; j<=N; j++)
CHROMOSOME[i][j] = x[j];
}
}
double simulation(double x[]) //模糊模擬
{
int i,j,k;
double f[samplenumber+1],mu[samplenumber+1];
for(i=1; i<=samplenumber; i++)
{
for(k=0;k<size;k++)
for(j=0;j<size;j++)
matrix[k][j]=0;
for(k=0;k<8;k++)
{
for(j=3*k;j<3*k+3;j++)
{
matrix[k][j]=1;
}
}
for(k=8;k<11;k++)
{
for(j=k-8;j<24;)
{
matrix[k][j]=1;
j=j+3;
}
}
aa[1]=28;aa[2]=18;aa[3]=74;aa[4]=74 ;
aa[5]=70;aa[6]=72;aa[7]=60;aa[8]=36;
aa[9]=42;aa[10]=50;aa[11]=34;aa[12]=6;
aa[13]=18;aa[14]=98;aa[15]=50;aa[16]=40;
double b[customer+facility]; //所有顧客的隨機需求
double v=1;
mu[i]=v;
b[0]=myu(14, 17); //第一個顧客的模糊需求
v=trapezoidal(b[0], 14, 15, 16,17);
if(v<mu[i])
mu[i]=v;
b[1]=myu(13, 18);
v=trapezoidal(b[1], 13, 14, 16,18);
if(v<mu[i])
mu[i]=v;
b[2]=myu(12, 16);
v=trapezoidal(b[2], 12, 14, 15,16);
if(v<mu[i])
mu[i]=v;
b[3]=myu(17, 20);
v=trapezoidal(b[3], 17, 18, 19,20);
if(v<mu[i])
mu[i]=v;
b[4]=myu(21, 26);
v=trapezoidal(b[4], 21,23,24,26);
if(v<mu[i])
mu[i]=v;
b[5]=myu(24,28);
v=trapezoidal(b[5], 24,25,26,28);
if(v<mu[i])
mu[i]=v;
b[6]=myu(13, 16);
v=trapezoidal(b[6], 13,14, 15, 16);
if(v<mu[i])
mu[i]=v;
b[7]=myu(12, 17);
v=trapezoidal(b[7], 12, 14, 16,17);
if(v<mu[i])
mu[i]=v;
b[8]=70,b[9]=80,b[10]=90;
int code[11];
for(j=0;j<8;j++)
code[j]=1;
code[8]=code[9]=code[10]=0;
for(k=0;k<8;k++)
{
for(j=3*k;j<3*k+3;j++)
{
matrix[n][j]=sqrt((x[1+j%3]-aa[1+k])*(x[1+j%3]-aa[1+k])+(x[4+j%3]-aa[9+k])*(x[4+j%3]-aa[9+k]));
}
}
Sstart(b, code);
Simplix();
f[i] = -matrix[n][s];
}
double opti;
opti=fuzzymean(f,mu,samplenumber);
return opti;
}
void objectives()
{
double x[N+1];
int i,j;
time_t t1, t2;
time(&t1);
for(i=1; i<=POP_SIZE; i++)
{
for(j=1;j<=N;j++)
{
x[j] = CHROMOSOME[i][j];
}
OBJECTIVE[i][1] = simulation(x);
}
time(&t2);
printf("time = %f \n",difftime(t2,t1));
for(i=1; i<=POP_SIZE; i++)
OBJECTIVE[i][0]= OBJECTIVE[i][1];
}
void evaluation(int gen)
{
double a;
int i, j, k, label;
objectives();
if(gen==0)
{
for(k=0; k<=M; k++)
OBJECTIVE[0][k]=OBJECTIVE[1][k];
for(j = 1; j <= N; j++)
CHROMOSOME[0][j]=CHROMOSOME[1][j];
}
for(i=0; i<POP_SIZE; i++)
{
label=0; a=OBJECTIVE[i][0];
for(j=i+1; j<=POP_SIZE; j++)
if((TYPE*a)<(TYPE*OBJECTIVE[j][0]))
{
a=OBJECTIVE[j][0];
label=j;
}
if(label!=0)
{
for(k=0; k<=M; k++)
{
a=OBJECTIVE[i][k];
OBJECTIVE[i][k]=OBJECTIVE[label][k];
OBJECTIVE[label][k]=a;
}
for(j=1; j<=N; j++)
{
a=CHROMOSOME[i][j];
CHROMOSOME[i][j]=CHROMOSOME[label][j];
CHROMOSOME[label][j]=a;
}
}
}
}
static void selection()
{
double r, temp[POP_SIZE+1][N+1];
int i, j, k;
for(i=1; i<=POP_SIZE; i++) {
r=myu(0, q[POP_SIZE]);
for(j=0; j<=POP_SIZE; j++) {
if(r<=q[j]) {
for(k=1; k<=N; k++) temp[i][k]=CHROMOSOME[j][k];
break;
}
}
}
for(i=1; i<=POP_SIZE; i++)
for(k=1; k<=N; k++)
CHROMOSOME[i][k]=temp[i][k];
}
static void crossover()
{
int i, j, jj, k, pop;
double r, x[N+1], y[N+1];
pop=POP_SIZE/2;
for(i=1; i<=pop; i++) {
if(myu(0,1)>P_CROSSOVER) continue;
j=(int)myu(1,POP_SIZE);
jj=(int)myu(1,POP_SIZE);
r=myu(0,1);
for(k=1; k<=N; k++) {
x[k]=r*CHROMOSOME[j][k]+(1-r)*CHROMOSOME[jj][k];
y[k]=r*CHROMOSOME[jj][k]+(1-r)*CHROMOSOME[j][k];
}
if(constraint_check(x)==1)
{
for(k=1; k<=N; k++) CHROMOSOME[j][k]=x[k];
}
if(constraint_check(y)==1)
{
for(k=1; k<=N; k++) CHROMOSOME[jj][k]=y[k];
}
}
}
static void mutation(void)
{
int i, j, k;
double x[N+1], y[N+1], infty, direction[N+1];
double INFTY=10, precision=0.0001;
for(i=1; i<=POP_SIZE; i++) {
if(myu(0,1)>P_MUTATION) continue;
for(k=1; k<=N; k++) x[k] = CHROMOSOME[i][k];
for(k=1; k<=N; k++)
if(myu(0,1)<0.5) direction[k]=myu(-1,1);
else direction[k]=0;
infty=myu(0,INFTY);
while(infty>precision) {
for(j=1; j<=N; j++) y[j]=x[j]+infty*direction[j];
if(constraint_check(y)==1) {
for(k=1; k<=N; k++) CHROMOSOME[i][k]=y[k];
break;
}
infty=myu(0,infty);
}
}
}
void main( )
{
FILE *fp;
srand((unsigned int)time(NULL));
int i;
double a;
fp=fopen("OLAEVM.txt","a+");
q[0]=0.05; a=0.05;
for(i=1; i<=POP_SIZE; i++)
{a=a*0.95; q[i]=q[i-1]+a;}
Init_GA();
objectives();
evaluation(0);
for(i=1; i<=GEN; i++)
{
selection();
crossover();
mutation();
objectives( );
evaluation(i);
fprintf(fp,"%d %f\n",i,OBJECTIVE[0][0]);
cout<<i<<endl;
cout<<OBJECTIVE[0][0]<<endl;
}
for(i=1;i<=N;i++)
fprintf(fp,"%f\n",CHROMOSOME[0][i]);
fprintf(fp,"%f\n",OBJECTIVE[0][0]);
fclose(fp);
getch();
}?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -