?? hcsa.cpp
字號:
/******************************************/
/* 2006.10.25 */
/*** V1.0 ***/
/******************************************/
#include <iostream.h> // cout
#include <fstream> // ifstream / ofstream
#include <stdlib.h> // rand()
#include <stdio.h>
#include <math.h>
#include <iomanip.h> // set weight of output
#include <time.h> // time()
using namespace std;
const int HHH=5; //程序執行次數
const int N=101; // cities' number
const int NB=150; // 產生的個體數
const int TTT=1000; // generations
//const int NC=100; //被選擇的最優個體數
//const int nc=20; //加入的新個體數
//const int NN=50; //克隆大小參數
//const int exchange=50; //第親合度的抗體每exchange代允許替換
//const int exchange_max=500;
const float optDis =629;
//float delta=100; //克隆選擇操作概率中的參數
//int K_max=10; //點變異次數
int temp1;
float discross; //交叉值
// att532= 27686 berlin52= 7542 bier127= 118282 ch130= 6110 ch150= 6528
// eil51=426 eil76= 538 eil101=629 fl1400= 20127
// kroA100= 21282 kroB100= 22141 kroc100= 20749 kroD100= 21294 kroE100= 22068
// kroA150= 26524 kroB150= 26130 kroA200= 29368 kroB200= 29437
// lin105= 14379 lin318= 42029
// pr107= 44303 pr124= 59030 pr136= 96772 pr152= 73682
// pcb442= 50778
// rat195= 2323 rd100= 7910 st70= 675 tsp225= 3919
float C[N][2]; // coordinate of cities
int I[N];
float Sum_Dis;
//int q[NC];
float tempDis;
float MaxDis=pow(10,50);
int Itemp1[N],Itemp3[N],Itemp4[N];
//float p[NC]; //克隆選擇操作概率
int randN;
float times,times_s,times_a; //時間計數器
int jumpC=0;
int GC=0;
float PDA=0.0,PDA_s=0.0,PDA_a=0.0; //平均最優結果
int ccci=0;
int r1, r2,label=0; //opt-2參數
float test1,test2,test3,test4,testdelta;//opt2參數
int position1,position2,m1,m2,m3,m4; //mutateRange參數
float mr1,mr2,mr3,mr4,mr5,mr6,mr7,mr8,mrdelta; //mutateRange參數
int intDis;
clock_t tstart, tend;
//ifstream city("eil51.txt"); // ******************** 3
//ifstream city("berlin52.txt");
//ifstream city("st70.txt");
//ifstream city("eil76.txt");
//ifstream city("rd100.txt");
ifstream city("eil101.txt");
//ifstream city("lin105.txt");
//ifstream city("pr107.txt");
//ifstream city("gr120.txt");
//ifstream city("pr124.txt");
//ifstream city("bier127.txt");
//ifstream city("ch130.txt");
//ifstream city("pr136.txt");
//ifstream city("ch150.txt");
//ifstream city("pr152.txt");
//ifstream city("rat195.txt");
//ifstream city("tsp225.txt");
//ifstream city("a280.txt");
//ifstream city("lin318.txt");
//ifstream city("pcb442.txt");
//ifstream city("att532.txt");
//ifstream city("pr1002.txt");
//ifstream city("fl1400.txt");
//ifstream city("pr2392.txt");
//ifstream city("pla7397.txt");
//ifstream city("kroA100.txt");
//ifstream city("kroA150.txt");
//ifstream city("kroA200.txt");
//ifstream city("kroB100.txt");
//ifstream city("kroB150.txt");
//ifstream city("kroB200.txt");
//ifstream city("kroC100.txt");
//ifstream city("kroD100.txt");
//ifstream city("kroE100.txt");
//ofstream result("result.txt");
//ofstream disF("disF.txt");
//ofstream csamatlab("csamatlab.txt");
//ofstream compuTime("compuTime.txt");
//ofstream itF("iteration.txt");
//ofstream generation("generation old.xls",ios::app);
ofstream fR("101cities.txt",ios::app);
struct rec
{
int A[N]; // index of cities in visiting ways
float Distance;
};
void cityinput();
void intDisF(); //整數求距離
void intdisMR(); //整數求距離
void randRange();
void dis(); // distance of all citis with one certain consquence
void mutateRange();
void disMR();
void sortIndex();
void matlab();
void cross();
void selfc(); // self crossover
void jump();
float dis2p(int,int);
void diversity(); // hold diveristy of antibody
void sortDis();
void newCross();
void opt2();
void GSX();
void quick_struct(rec* rr[], int );
void qs_struct(rec* rr[], int, int);
double round(double, unsigned); //取整函數
struct rec* point[NB]; //定義結構指針數組,分別指向結構體數組
void main()
{
struct rec antibody[NB]; //保存個體
// struct rec antibody_c[NC][NN];//保存克隆體
// struct rec antibody_c_b[NC]; //保存最好的克隆體
// struct rec antibody_cross; //保存最好的交叉體
struct rec antibody_cross[NB];
// int antibody_temp;
/* int counter=0;
int gama=0.1;
int nc=0;
nc=NC*gama;
*/
srand((unsigned)time(NULL));
cityinput();
for(int count=0; count<HHH; count++){ //程序執行次數
tstart=clock();
for(int i=0; i<NB; i++) //隨機產生抗體I[NB]
{
randRange();
intDisF();
for(int j=0; j<N; j++)
{
antibody[i].A[j]=I[j];
}
antibody[i].Distance=intDis;
point[i]=&antibody[i]; //定義結構指針數組,分別指向結構體數組
}
quick_struct(point,NB);
for(int cci=0; cci<TTT; cci++ ) //generation
{
for(i=0;i<NB;i++)
{
int i1;
if(i==NB-1) i1=0; else i1=i+1;
for(int k=0;k<N;k++)
{
Itemp3[k]=antibody[i].A[k];
Itemp4[k]=antibody[i1].A[k];
}
GSX();
intdisMR();
antibody_cross[i].Distance =intDis;
for(k=0;k<N;k++)
{
antibody_cross[i].A[k]=Itemp1[k];
}
for(k=0;k<N;k++)
{
Itemp1[k]= antibody_cross[i].A[k];
}
mutateRange();
if(mrdelta<0)
antibody_cross[i].Distance=antibody_cross[i].Distance+ mrdelta;
if(antibody_cross[i].Distance<antibody[i].Distance)
{
antibody[i]=antibody_cross[i];
}
}
}//generations
quick_struct(point,NB);
tend = clock();
times=(tend-tstart)/1000.0;
PDA=(antibody[0].Distance/*/sqrt(10)*/-optDis)/optDis*100;
fR<<times<<" "<<antibody[0].Distance<<" "<<PDA<<"%"<<endl;
// itF << NG << " " << NCS << " "<<(tend-tstart)/1000.0 <<" "<< currOD <<" "<<currIOD << endl <<endl;
// fR << NG << " " << " "<<(tend-tstart)/1000.0 <<" "<< mT/(cci+1.0)
// << " "<< Distance[0] <<" "<<(Distance[0] - optDis)/optDis <<" "<< mDis/(cci+1.0)
// << " " <<(mDis/(cci+1.0) - optDis)/optDis <<endl;
// compuTime <<"Computational time: " << (tend-tstart)/1000.0 << endl;
times_s+=times;
PDA_s+=PDA;
}//程序執行次數
PDA_a=PDA_s/HHH;
times_a=times_s/HHH;
fR<<"RE:SHM=0.5:0.5"<<endl;
// fR<<"N:"<<N<<" "<<"NB:"<<NB<<" "<<"NC:"<<NC<<" "<<"nc:"<<nc<<" "<<"NN:"<<NN<<" "<<"TTT:"<<TTT<<" "<<"delta:"<<delta<<" "<<"k:"<<exchange<<endl;
fR<<"前"<<HHH<<"次平均時間："<<times_a<<" "<<"平均距離："<<PDA_a<<endl;
fR<<" "<<endl;
}//main
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// save coordinates in C[N][2]
void cityinput()
{
float temp1;
for(int i=0; i<N; i++)
{
city >> temp1;
city >> temp1;
C[i][0] = temp1;
city >> temp1;
C[i][1] = temp1;
}
}
// randomly range cities
void randRange()
{
int temp1;
float temp2=1;
int iT[N]; // save the generated random index of cities
//result << endl;
for(int i1=0; i1<N; i1++)
{
iT[i1] = N+1;
}
for(int i=0; i<N; i++)
{
do
{
temp1 = rand()%N;
temp2 =1;
for(int i2=0; i2<=i; i2++)
{
temp2 = temp2*(temp1-iT[i2]);
}
}
while(temp2 == 0);
iT[i] = temp1;
I[i] = iT[i];
//result << I[i]+1 <<" ";
}
//result << endl;
}
// mutate sequence
void mutateRange()
{
int temp11;
do
{
position1=rand()%N;
position2=rand()%N;
}
while(position1==position2);
if(position1==N-1) m1=0;
else m1=position1+1;
if(position1==0) m2=N-1;
else m2=position1-1;
if(position2==N-1) m3=0;
else m3=position2+1;
if(position2==0) m4=N-1;
else m4=position2-1;
mr5=dis2p(Itemp1[position1],Itemp1[m1]);
mr6=dis2p(Itemp1[position1],Itemp1[m2]);
mr7=dis2p(Itemp1[position2],Itemp1[m3]);
mr8=dis2p(Itemp1[position2],Itemp1[m4]);
mr1=dis2p(Itemp1[position2],Itemp1[m1]);
mr2=dis2p(Itemp1[position2],Itemp1[m2]);
mr3=dis2p(Itemp1[position1],Itemp1[m3]);
mr4=dis2p(Itemp1[position1],Itemp1[m4]);
mrdelta=mr1+mr2+mr3+mr4-mr5-mr6-mr7-mr8;
if( position1-position2==1 || position2-position1==N-1) //position1和position2相鄰
mrdelta=mr4+mr1-mr5-mr8;
if(position2-position1==1 || position1-position2==N-1)
mrdelta=mr2+mr3-mr6-mr7;
temp11 = Itemp1[position1];
Itemp1[position1] = Itemp1[position2];
Itemp1[position2] = temp11;
}
float dis2p(int m, int n)
{
float Dis = 0.0;
Dis += (C[m][0] - C[n][0])*(C[m][0] - C[n][0])+(C[m][1] - C[n][1])*(C[m][1] - C[n][1]);
intDis =round(sqrt(Dis),0);
return(intDis);
}
//***************** GSX ********************//
//
// input Itemp3[N], Itemp4[N]
// output Itemp1[N]
//
//*******************************************//
void GSX()
{
int x=0, y=0, z=0,x1,y1;//位置
int tx = 0;
int pp1,pp2,pp;
z = rand() % N; // generate the city z randomly;
// result << "random z = " << z << endl; //060922
for(int k=0;k<N;k++)
{
Itemp1[k]=0;
}
for(int p=0;p<N;p++)
{
pp1=0;
pp2=0;
pp=0;
Itemp1[p]=z;
for(int i=0; i<N; i++)
{
if(Itemp3[i] == z)
{x = i;}
if(Itemp4[i] == z)
{y = i;}
}
if(x==N-1) x1=0; else x1=x+1;
if(y==N-1) y1=0; else y1=y+1;
if(dis2p(Itemp3[x],Itemp3[x1])<=dis2p(Itemp4[y],Itemp4[y1]))
z=Itemp3[x1];
else
z=Itemp4[y1];
for(int j=0;j<=p;j++)
{
if(Itemp3[x1]==Itemp1[j]) pp1=1;
if(Itemp4[y1]==Itemp1[j]) pp2=1;
}
if(pp1==1 && pp2==0) z=Itemp4[y1];
if(pp1==0 && pp2==1) z=Itemp3[x1];
if(pp1==1 && pp2==1)
{
for(int k=0;k<N;k++)
{
for(int j=0;j<=p;j++)
{
if(k==Itemp1[j]) pp=1;
}
if(0==pp)
{
tempDis=MaxDis;
if(dis2p(Itemp1[p],k)<tempDis)
{
tempDis=dis2p(Itemp1[p],k);
z=k;
}
}
pp=0;
}
}
}
}
/*The Quicksort*/
void quick_struct(rec* rr[], int count)
{
qs_struct(rr,0,count-1);
}
void qs_struct(rec* rr[], int left, int right)
{
register int i,j;
float x;
struct rec temp;
i=left; j=right;
x=point[(left+right)/2]->Distance;
do
{
while((point[i]->Distance<x) && (i<right)) i++;
while((x<point[j]->Distance) && (j>left)) j--;
if(i<=j)
{
temp=*point[i];
*point[i]=*point[j];
*point[j]=temp;
i++; j--;
}
}while(i<=j);
if(left<j) qs_struct(point, left,j);
if(i<right) qs_struct(point,i,right);
}
void opt2()
{
int tempC[N];
float L1=0.0;
float L2=0.0;
do
{
r1 = rand()%(N-1); // firstly, put this sentence outer the loop, when r1 = N-1, run into trouble
r2 = rand()%(N-1);
}while(r2-r1 < 2);
//if (dis2p(r1,r1+1)+dis2p(r2,r2+1) < dis2p(r1,r2)+dis2p(r1+1,r2+1))
test1=dis2p(Itemp1[r1],Itemp1[r2]); //after
test2=dis2p(Itemp1[r1+1],Itemp1[r2+1]);
test3=dis2p(Itemp1[r1],Itemp1[r1+1]);//before
test4=dis2p(Itemp1[r2],Itemp1[r2+1]);
testdelta=test3+test4-test1-test2;
// if ((dis2p(Itemp1[r1],Itemp1[r2])+dis2p(Itemp1[r1+1],Itemp1[r2+1])) < (dis2p(Itemp1[r1],Itemp1[r1+1])+dis2p(Itemp1[r2],Itemp1[r2+1])))
if(testdelta>=0)
{
label=1;
for(int i=0; i<=r1; i++)
{
tempC[i] = Itemp1[i];
}
for(i=r1+1; i<=r2; i++)
{
tempC[i] = Itemp1[r2-(i-r1-1)];
}
for(i=r2+1; i<=N-1; i++)
{
tempC[i] = Itemp1[i];
}
for (i=0; i<N; i++)
{
Itemp1[i] = tempC[i];
}
}
else
label=0;
}//opt-2
void intdisMR()
{
intDis = 0.0;
float temp22 = 0.0;
int i1,i2;
int i0= Itemp1[0],iN = Itemp1[N-1];
for(int i=0; i<N-1; i++)
{
temp22 = 0.0;
i1 = Itemp1[i];
i2 = Itemp1[i+1];
for(int j=0; j<2; j++)
{
temp22 += ((C[i1][j])-(C[i2][j]))*((C[i1][j])-(C[i2][j]));
}
temp22 = sqrt(temp22);
temp22 = round(temp22,0);
intDis += temp22;
}
intDis = intDis +round(sqrt(((C[i0][0])-(C[iN][0]))*((C[i0][0])-(C[iN][0])) + ((C[i0][1])-(C[iN][1]))*((C[i0][1])-(C[iN][1]))),0);
}
void intDisF()
{
intDis = 0.0;
float temp22 = 0.0;
int i1,i2;
int i0= I[0],iN = I[N-1];
for(int i=0; i<N-1; i++)
{
temp22 = 0.0;
i1 = I[i];
i2 = I[i+1];
for(int j=0; j<2; j++)
{
temp22 += ((C[i1][j])-(C[i2][j]))*((C[i1][j])-(C[i2][j]));
}
temp22 = sqrt(temp22);
temp22 = round(temp22,0);
intDis += temp22;
}
intDis = intDis +round( sqrt(((C[i0][0])-(C[iN][0]))*((C[i0][0])-(C[iN][0])) + ((C[i0][1])-(C[iN][1]))*((C[i0][1])-(C[iN][1]))), 0);
}
double round(double num, unsigned precision)
{
double pow = 1.0;
for(int i=0; i < precision; ++i)
pow *= 10;
if(num > 0) //正數
return int(num * pow + .5) / pow;
return int(num * pow - .5) / pow; //負數
}?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -