TSP问题的遗传算法实验报告

TSP问题的遗传算法实验报告

一实验题目

TSP问题的遗传算法实现

二实验目的

1熟悉和掌握遗传算法的基本概念和基本思想；

2加深对遗传算法的理解，理解和掌握遗传算法的各个操作算子；

3理解和掌握利用遗传算法进行问题求解的基本技能。

三实验要求

1 以10/30个结点的TSP问题为例,用遗传算法加以求解；

2 掌握遗传算法的基本原理、各个遗传操作和算法步骤；

3 能求出问题最优解，若得不出最优解，请分析原因；

4 要求界面显示每次迭代求出的局部最优解和最终求出的全局最优解。

四数据结构

请说明染色体个体和群体的定义方法。

typedef struct{

int colony[POPSIZE][CITY_NUM+1];//城市种群,默认出发城市编号为0，则城市编号的最后一个城市还应该为0 每CITY_NUM个城市的排列组合为一个染色体double fitness[POPSIZE];// 路径适应值

double Distance[POPSIZE];//路径实际长度

int BestRooting[CITY_NUM+1];//最优城市路径序列

double BestFitness;//最优路径适应值

double BestValue;//最优路径长度

}TSP,*PTSP;

五实验算法

1 说明算法中对染色体的编码方法，适应度函数定义方法；

染色体的编码方法：0～9一个排列组合为一条染色体。

适应度函数的定义方法：取路径长度的倒数。

void CalFitness(PTSP city,int m)

{

int i,j,t=0;

int start,end;

for(i=0;i

{//求适应值

city->Distance[i]=0;

for(j=1;j<=CITY_NUM;j++)

{

start=city->colony[i][j-1];end=city->colony[i][j];

city->Distance[i]=city->Distance[i]+CityDistance[start][end];

}

city->fitness[i]=N/(city->Distance[i]);

}

｝

2 采用的选择、交叉、变异操作算子的具体操作；

void Select(PTSP city)

{//选择算子

int i,j;

double sum=0,r,t;

double p[POPSIZE],q[POPSIZE+1];

int copey[POPSIZE][CITY_NUM+1];

q[0] = 0;

for (i=0;i

sum+=city->fitness[i];

for (i=0;i

{

p[i] = city->fitness[i]/sum;

q[i+1] = q[i]+p[i];

}

for (i=0;i

{

t = rand()%(10000);

r = t/10000;

for (j=0;j

if (r<=q[j+1])

{

*copey[i] = *city->colony[j];

break;

}

}

for (i=0;i

*city->colony[i] = *copey[i];

}

void AOX(PTSP city,int n,int m)//改进启发式算法

{

int A[CITY_NUM-1],B[CITY_NUM-1];

int i,j;

int k=1+CROSS_NUM,t=1+CROSS_NUM;

for (i=0;i

{

A[i] = city->colony[n][i+1];

B[i] = city->colony[m][i+1];

}

for (i=3;i

{

city->colony[n][i-2] = B[i];

city->colony[m][i-2] = A[i];

}

for (i=0;i

{

for (j=0;j

if (A[i] == B[j+3])

break;

if (j == CROSS_NUM)

city->colony[n][k++] = A[i];

for (j=0;j

if (B[i] == A[j+3])

break;

if (j == CROSS_NUM)

city->colony[m][t++] = B[i];

}

}

int check1(int r[],int n)//判重

{

int i;

for (i=0;i

if (r[i] == r[n])

{

return true;

}