__2017-12-11 如一模式识别研究

如一模式识别研究

基本数学知识>>遗传算法解决TSP问题

转自:http://blog.csdn.net/yeruby/article/details/13161853

读了原作者mylovestart用遗传算法实现的tsp问题,学习了ga算法。

原文链接:http://blog.csdn.net/mylovestart/article/details/8977005#cpp

但发现原作者mylovestart的jiaopei()函数写的有问题,交叉后要确保每个城市有且仅走了一次,修改了jiaopei()的代码如下:

[cpp] view plaincopyprint?

//交配,对每个染色体产生交配概率,满足交配率的染色体进行交配

void jiaopei()

{

int i,j,k,kk;

int t;//参与交配的染色体的个数

int point1,point2,temp;//交配断点

int pointnum;

int temp1,temp2;

int map1[cities],map2[cities];

double jiaopeip[num];//染色体的交配概率

int jiaopeiflag[num];//染色体的可交配情况

int kkk,flag=0;

//初始化

for(i=0;i

{

jiaopeiflag[i]=0;

}

//随机产生交配概率

srand((unsigned)time(NULL));

for(i=0;i

{

jiaopeip[i]=(rand()%100);

jiaopeip[i]/=100;

}

//确定可以交配的染色体

t=0;

for(i=0;i

{

if(jiaopeip[i]

{

jiaopeiflag[i]=1;

t++;

}

}

t=t/2*2;//t必须为偶数

//产生t/2个0-9交配断点

srand((unsigned)time(NULL));

temp1=0;

//temp1号染色体和temp2染色体交配

for(i=0;i

{

point1=rand()%cities;//交配点1

point2=rand()%cities;//交配点2

//选出一个需要交配的染色体1

for(j=temp1;j

{

if(jiaopeiflag[j]==1)

{

temp1=j;

break;

}

}

//选出另一个需要交配的染色体2与1交配

for(j=temp1+1;j

{

if(jiaopeiflag[j]==1)

{

temp2=j;

break;

}

}

//进行基因交配

if(point1>point2) //保证point1<=point2

{

temp=point1;

point1=point2;

point2=temp;

}

//初始化

memset(map1,-1,sizeof(map1));

memset(map2,-1,sizeof(map2));

//断点之间的基因产生映射

for(k=point1;k<=point2;k++)

{

map1[group[temp1].city[k]]=group[temp2].city[k];

map2[group[temp2].city[k]]=group[temp1].city[k];

}

//断点两边的基因互换

for(k=0;k

{

temp=group[temp1].city[k];

group[temp1].city[k]=group[temp2].city[k];

group[temp2].city[k]=temp;

}

for(k=point2+1;k

{

temp=group[temp1].city[k];

group[temp1].city[k]=group[temp2].city[k];

group[temp2].city[k]=temp;

}

printf("处理冲突---------------------\n");

//处理染色体1产生的冲突基因

for(k=0;k

{

for(kk=point1;kk<=point2;kk++)

{

if(group[temp1].city[k]==group[temp1].city[kk])

{

group[temp1].city[k]=map1[group[temp1].city[k]];

//find

for(kkk=point1;kkk<=point2;kkk++)

{

if(group[temp1].city[k]==group[temp1].city[kkk])

{

flag=1;

break;

}

}

if(flag==1)

{

kk=point1-1;

flag=0;

}

else

{

flag=0;

break;

}

}

}

}

for(k=point2+1;k

{

for(kk=point1;kk<=point2;kk++)

{

if(group[temp1].city[k]==group[temp1].city[kk])

{

group[temp1].city[k]=map1[group[temp1].city[k]];

//find

for(kkk=point1;kkk<=point2;kkk++)

{

if(group[temp1].city[k]==group[temp1].city[kkk])

{

flag=1;

break;

}

}

if(flag==1)

{

kk=point1-1;

flag=0;

}

else

{

flag=0;

break;

}

}

}

}

//处理2染色体产生的冲突基因

for(k=0;k

{

for(kk=point1;kk<=point2;kk++)

{

if(group[temp2].city[k]==group[temp2].city[kk])

{

group[temp2].city[k]=map2[group[temp2].city[k]];

//find

for(kkk=point1;kkk<=point2;kkk++)

{

if(group[temp2].city[k]==group[temp2].city[kkk])

{

flag=1;

break;

}

}

if(flag==1)

{

kk=point1-1;

flag=0;

}

else

{

flag=0;

break;

}

}

}

}

for(k=point2+1;k

{

for(kk=point1;kk<=point2;kk++)

{

if(group[temp2].city[k]==group[temp2].city[kk])

{

group[temp2].city[k]=map2[group[temp2].city[k]];

//find

for(kkk=point1;kkk<=point2;kkk++)

{

if(group[temp2].city[k]==group[temp2].city[kkk])

{

flag=1;

break;

}

}

if(flag==1)

{

kk=point1-1;

flag=0;

}

else

{

flag=0;

break;

}

}

}

}

temp1=temp2+1;

}

}

之后自己又试了50+的城市的数据,效果不太理想,希望过后自己可以再改进一下选择函数,让每次最优的个体可以保留下来。

评论留言区

:
  

作者: 游客 ; *
评论内容: *
带*号为必填项目

如一模式识别更新提示

matlab在图像处理方面的应用有更新

如一模式识别 友情链接

关于本站作者     chinaw3c     mozilla