TSP.zip_C TSP_tsp_人工智能算法_智能算法对比

// TSP.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "stdlib.h" #include "math.h" #include "time.h" #define M 7 //结点个数 #define N 8 //种群个数 #define GEN 1000 //进化代数 #define GEN1 50 //最优解没有改进代数 #define GEN2 200 //平均适应度未改变代数 #define PChange 0.5 //变异概率 #define PCross 0.1 //交叉概率 int currentGEN; //当前代数 int currentOptimization; //当前最优代数 int currentGEN2; //平均适应度对应代数 double averageWeight; //平均适应度值 int changNumber=(int)ceil(PChange*N); int crossNumber=(int)ceil(PCross*N); //int changNumber=1; //int crossNumber=1; int selectNumber=N-changNumber-crossNumber*2; int newNode[N][M+1]; int optimization[M+1]; //最优解 int optimizationCost; //最优适应度 int nodes[N][M+1] = //所有结点 { { 1,5,3,4,6,7,2,1 }, { 1,3,5,2,6,7,4,1 }, { 1,2,5,3,6,7,4,1 }, { 1,4,3,5,6,7,2,1 }, { 1,3,4,6,7,5,2,1 }, { 1,2,4,5,6,7,3,1 }, { 1,4,5,6,7,3,2,1 }, { 1,3,4,2,6,7,5,1 } }; int weight[N]; //所有结点的适应度 int randBuf[N]; //随即序列 //定义路径长度 int cost[M][M] = {/* { 0, 100, 125, 100, 75 }, { 100, 0, 50, 75, 125 }, { 125, 50, 0, 100, 125 }, { 100, 75, 125, 0, 50 }, { 75, 125, 125, 50, 0 } */ { 0, 100, 125, 100, 75, 40, 20 }, { 100, 0, 50, 75, 125, 35, 20 }, { 125, 50, 0, 100, 125, 20, 60 }, { 100, 75, 125, 0, 50, 35, 40 }, { 75, 125, 125, 50, 0, 15, 50 }, { 40, 35, 20, 35, 15, 0, 40 }, { 20, 20, 60, 40, 50, 40, 0 } }; void initGen(int n); //初始化种群 int termination(); //是否满足停止规则。满足：0 不满足：1 void calculate(); //计算适应值 void produce(); //产生下一代 void getRand(); //产生随机数 void selectFunction(); //执行select操作 void crossFunction(); //执行cross操作 void changeFunction(); //执行change操作 int currentNewNode; //新一代结点下标 int currentNode; //当前可以使用的序列下标 int main(int argc, char* argv[]) { printf("Hello, this is a test of TSP\n"); int i=0; //初始化种群 initGen(GEN1); while ( termination() ) { //计算最优值 calculate(); produce(); } printf("Current GenNum is %d\n",currentGEN); /* printf("Current Gen is (%d,%d,%d,%d,%d,%d)\n", optimization[0], optimization[1], optimization[2], optimization[3], optimization[4], optimization[5] ); */ printf("Current Gen is ("); for (i=0;i<M+1;i++) printf("%d ",optimization[i]); printf(")\n"); printf("The optimization is %d\n",optimizationCost); printf("OK!\n"); return 0; } void initGen(int n) { srand( (unsigned)time( NULL ) ); //设置随机数种子 currentGEN=0; optimizationCost=10000; currentOptimization=-1; currentGEN2=0; averageWeight=0; } int termination() { //完成预定代数 if (currentGEN==GEN) return 0; if (currentGEN-currentOptimization==GEN1) return 0; if (currentGEN-currentGEN2==GEN2) return 0; return 1; } void calculate() { int i,j,k; for (i=k=0;i<N;i++) { for (j=0;j<M;j++) { k+=cost[nodes[i][j]-1][nodes[i][j+1]-1]; } weight[i]=k; k=0; } //选择最优适应度解 for (i=0;i<N;i++) { if (weight[i] < optimizationCost) { for (j=0;j<M+1;j++) { optimization[j]=nodes[i][j]; } optimizationCost=weight[i]; currentOptimization=currentGEN; } } //平均适应度 double s; for (i=0,s=0;i<N;i++) { s+=weight[i]; } if (s/N != averageWeight) { averageWeight=s/N; currentGEN2=currentGEN; } } //产生下一代结点 void produce() { int i,j,k; currentNode=0; currentNewNode=0; getRand(); //change changeFunction(); //cross crossFunction(); //select selectFunction(); for (i=0;i<N;i++) { for (j=0;j<M+1;j++) { nodes[i][j]=newNode[i][j]; } } currentGEN++; for (i=0;i<N;i++) { printf("Gen %d:\t",i); for (j=0;j<M+1;j++) { printf("%d ",nodes[i][j]); } printf("\n"); } printf("--------------------------------------\n"); } //产生N个(0--(N-1))随机数 void getRand() { int i,j,k; for (i=0;i<N;i++) randBuf[i]=-1; for (i=0;i<N;i++) { lab: k=rand()%N; for (j=0;j<i;j++) { if (randBuf[j]==k) { goto lab; } } randBuf[i]=k; } } void changeFunction() { int i,j,k,s; int tempArray[M+1]; for (i=0;i<changNumber;i++) { int sub; sub=randBuf[currentNode++]; //对原sub代执行变异操作 //获取要处理的结点 for (j=0;j<M+1;j++) tempArray[j]=nodes[sub][j]; lab2: j=rand()%M; //第j位变异 k=rand()%M+1; if ( j==0 ||j==M || k==1 || k==tempArray[j] ) goto lab2; for (s=0;s<M+1;s++) { if (tempArray[s] == k) { tempArray[s]=tempArray[j]; break; } } tempArray[j]=k; //第j位变异为k for (k=0;k<M+1;k++) newNode[currentNewNode][k]=tempArray[k]; currentNewNode++; if (tempArray[0]!=1) { printf("Change error and j is %d\n",j); exit(0); } } } void crossFunction() { int i,j,k,s; int tempArray1[M+1],tempArray2[M+1]; for (i=0;i<crossNumber;i++) { int sub1,sub2; sub1=randBuf[currentNode++]; sub2=randBuf[currentNode++]; //获取要处理的结点 for (i=0;i<M+1;i++) { tempArray1[i]=nodes[sub1][i]; tempArray2[i]=nodes[sub2][i]; } j=rand()%(M-1)+1; //从第j位开始交叉 for (s=j;s<M+1;s++) { k=tempArray1[s]; tempArray1[s]=tempArray2[s]; tempArray2[s]=k; } //交叉后去除重复数字 for (i=1;i<j;i++) { lab3: for (s=1;s<M+1;s++) { if (i==s) continue; if (tempArray1[i]==tempArray1[s]) { k=rand()%M+1; tempArray1[i]=k; goto lab3; } } lab4: for (s=1;s<M+1;s++) { if (i==s) continue; if (tempArray2[i]==tempArray2[s]) { k=rand()%M+1; tempArray2[i]=k; goto lab4; } } } for (i=0;i<M+1;i++) { newNode[currentNewNode][i]=tempArray1[i]; newNode[currentNewNode+1][i]=tempArray2[i]; } currentNewNode+=2; if (tempArray1[0]!=1 || tempArray2[0]!=1) { printf("Cross error\n"); exit(0); } } } void selectFunction() { int i,j,k,s; int sub; for (i=0;i<selectNumber;i++) { sub=randBuf[currentNode++]; for (j=0;j<M+1;j++) { newNode[currentNewNode][j]=nodes[sub][j]; } currentNewNode++; } }