#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#define cities 10 //城市的个数
#define MAXX 100//迭代次数
#define pc 0.8 //交配概率
#define pm 0.05 //变异概率
#define num 10//种群的大小
int bestsolution;//最优染色体
int distance[cities][cities];//城市之间的距离
struct group //染色体的结构
{
int city[cities];//城市的顺序
int adapt;//适应度
double p;//在种群中的幸存概率
}group[num], grouptemp[num];
void groupproduce();//产生初始种群
void pingjia();//评价函数
void init();//初始化城市之间的距离
void xuanze();//选择
void jiaocha();//交叉
void bianyi();//变异
int main(int argc, char* argv[])
{
int i, j, t;
int count = 0;
init();
groupproduce();
pingjia();//初始种群评价
printf("\n");
t = 0;
while (t++<MAXX) //MAXX是迭代次数
{
count++;
printf("当前迭代次数%d次\n", t);
xuanze();
printf("***交叉***\n");
jiaocha();
printf("***变异***\n");
bianyi();
printf("***迭代一次的交叉变异后的评价***\n");
pingjia();
}
printf("\n");
printf("当前总迭代次数%d\n", count);
//最终种群的评价
printf("\n输出最终的种群评价\n");
for (i = 0; i<num; i++)
{
for (j = 0; j<cities; j++)
{
printf("%4d", group[i].city[j]);
}
printf(" adapt:%4d, p:%.4f\n", group[i].adapt, group[i].p);
}
printf("最优解为%d号染色体\n", bestsolution);
system("pause");
return 0;
}
//随机产生cities个城市之间的相互距离
void init()
{
int i, j;
memset(distance, 0, sizeof(distance));
srand((unsigned)time(NULL));
for (i = 0; i<cities; i++)
{
for (j = i + 1; j<cities; j++)
{
distance[i][j] = rand() % 100;
distance[j][i] = distance[i][j];
}
}
//打印距离矩阵
printf("城市的距离矩阵如下\n");
for (i = 0; i<cities; i++)
{
for (j = 0; j<cities; j++)
printf("%4d", distance[i][j]);
printf("\n");
}
}
//产生初始种群
void groupproduce()
{
int i, j, t, k, flag;
for (i = 0; i<num; i++) //初始化
for (j = 0; j<cities; j++)
group[i].city[j] = -1; //?
srand((unsigned)time(NULL));
for (i = 0; i<num; i++)
{
//产生10个不相同的数字 ,每行每列产生不相同的10个数字
for (j = 0; j<cities;)
{
t = rand() % cities; //数字在[0,10)之间
flag = 1;
for (k = 0; k<j; k++)
{
if (group[i].city[k] == t)
{
flag = 0;
break;
}
}
if (flag)
{
group[i].city[j] = t;
j++;
}
}
}
//打印种群基因
printf("初始的种群\n");
for (i = 0; i<num; i++)
{
for (j = 0; j<cities; j++)
printf("%4d", group[i].city[j]);
printf("\n");
}
printf("\n");
}
//评价函数,找出最优染色体
void pingjia()
{
int i, j;
int n1, n2;
int sumdistance, biggestsum = 0;
double biggestp = 0;
/**************************************************/
for (i = 0; i<num; i++)
{
sumdistance = 0;
for (j = 1; j<cities; j++)
{
n1 = group[i].city[j - 1];
n2 = group[i].city[j];
sumdistance += distance[n1][n2];
}
group[i].adapt = sumdistance; //每条染色体的路径总和
biggestsum += sumdistance; //种群的总路径
}
/***************************************************
n1,n2打的值不同,且都在0到9之间,所以distance[n1][n2]
是指城市n1到n2的距离。所以第二个for循环求的的结果是每条染色体
的路径和。
***************************************************/
//计算染色体的幸存能力,路径越短生存概率越大
for (i = 0; i<num; i++)
{
group[i].p = 1 - (double)group[i].adapt / (double)biggestsum;
biggestp += group[i].p;//种群总的生存率
}
for (i = 0; i<num; i++)
group[i].p = group[i].p / biggestp; //在种群中的幸存概率,总和为1 ,每条染色体的生存率
//求最佳路径
bestsolution = 0;
for (i = 0; i<num; i++)
if (group[i].p>group[bestsolution].p)
bestsolution = i;
//打印适应度
for (i = 0; i<num; i++)
printf("染色体%d的路径之和与生存概率分别为%4d %.4f\n\n", i, group[i].adapt, group[i].p);
printf("当前种群的最优染色体是%d号染色体\n", bestsolution);
}
//选择
void xuanze()
{
int i, j, temp;
double gradient[num];//梯度概率
double xuanze[num];//选择染色体的随机概率
int xuan[num];//选择了的染色体
//初始化梯度概率 为0
for (i = 0; i<num; i++)
{
gradient[i] = 0.0;
xuanze[i] = 0.0;
}
/*************************这是什么原理?****************/
gradient[0] = group[0].p;
for (i = 1; i<num; i++)
gradient[i] = gradient[i - 1] + group[i].p;
/*******************************************/
srand((unsigned)time(NULL));
//随机产生染色体的存活概率 ,每次运行结果不一样的
for (i = 0; i<num; i++)
{
xuanze[i] = (rand() % 100);//产生的伪随机数在[0,100)
xuanze[i] /= 100;
}
//选择能生存的染色体
for (i = 0; i<num; i++)
{
for (j = 0; j<num; j++)
{
if (xuanze[i]<gradient[j]) //选择标准吧?
{
xuan[i] = j; //第i个位置存放第j个染色体
break;
}
}
}
//拷贝种群
for (i = 0; i<num; i++)
{
grouptemp[i].adapt = group[i].adapt;
grouptemp[i].p = group[i].p;
for (j = 0; j<cities; j++)
grouptemp[i].city[j] = group[i].city[j];
}
//数据更新 ,选择之后的适应值,生存率,种群的更新
for (i = 0; i<num; i++)
{
temp = xuan[i];
group[i].adapt = grouptemp[temp].adapt;
group[i].p = grouptemp[temp].p;
for (j = 0; j<cities; j++)
group[i].city[j] = grouptemp[temp].city[j];
}
//用于测试
/*printf("<------------------------------->\n");
for(i=0;i<num;i++)
{
for(j=0;j<cities;j++)
printf("%4d",group[i].city[j]);
printf("\n");
printf("染色体%d的路径之和与生存概率分别为%4d %.4f\n\n",i,group[i].adapt,group[i].p);
}*/
}
/************************************************************************/
/***交叉,对每个染色体产生交叉概率,满足交叉率的染色体进行交叉 ***********
本问题进行的交叉操作时交换节点两侧的基因,并将每条染色体的重复基因进行
处理,处理方法:
举个例子:
染色体1: 98 45671 320
染色体2: 87 14032 965
备注:中间间隔是断点
交换后的染色体:
染色体1: 87 45671 965
染色体2: 98 14032 320
处理染色体1后的结果:
染色体1: 83 45671 902
染色体2: 98 14032 320
处理染色体2后的结果:
染色体1: 83 45671 902
染色体2: 98 14032 710
看程序更易理解,参考链接:http://blog.csdn.net/mylovestart/article/details/8977005#cpp
******************************************************************************************/
void jiaocha()
{
int i, j, k, kk;
int t;//参与交叉的染色体的个数
int point1, point2, temp;//交叉断点
int pointnum;
int temp1, temp2;
int map1[cities], map2[cities];
double jiaochap[num];//染色体的交叉概率
int jiaochaflag[num];//染色体的可交叉情况
for (i = 0; i<num; i++)//初始化
jiaochaflag[i] = 0;
//随机产生交叉概率
srand((unsigned)time(NULL));
for (i = 0; i<num; i++)
{
jiaochap[i] = (rand() % 100);
jiaochap[i] /= 100;
//测试
//printf("%f\n", jiaochap[i]);
}
//确定可以交叉的染色体数目
t = 0; //t是参与交叉的染色体数
for (i = 0; i<num; i++)
{
if (jiaochap[i]<pc)//pc=0.8
{
jiaochaflag[i] = 1;
t++;
}
}
t = t / 2 * 2; //t必须为偶数个染色体在这里保证t大于等于2个染色体
//随机产生0-9之间的交叉断点
srand((unsigned)time(NULL));
temp1 = 0;
//temp1号染色体和temp2染色体交叉
for (i = 0; i<t / 2; i++)
{
point1 = rand() % cities;//断点1,范围是[0,10)
point2 = rand() % cities;//断点2
for (j = temp1; j<num; j++)
if (jiaochaflag[j] == 1)
{
temp1 = j;
break;
}
for (j = temp1 + 1; j<num; j++)
if (jiaochaflag[j] == 1)
{
temp2 = j;
break;
}
//进行基因交叉
if (point1>point2) //保证point1<=point2
{
temp = point1;
point1 = point2;
point2 = temp;
}
//交换中间段的基因
for (k = point1; k <= point2; k++)
{
temp = group[temp1].city[k];
group[temp1].city[k] = group[temp2].city[k];
group[temp2].city[k] = temp;
}
//初始化数组map1,map2的值为-1
memset(map1, -1, sizeof(map1));
memset(map2, -1, sizeof(m
遗传算法求解基本TSP问题C++
需积分: 19 11 浏览量
2017-05-11
14:34:36
上传
评论 3
收藏 1.06MB ZIP 举报
baidu_38409727
- 粉丝: 0
- 资源: 3
最新资源
- Wireshark-4.2.4-x64.zip
- 2022年11月软件设计师上
- 基于VB+ACCESS教学管理系统(参考文献+源代码).zip
- 一个工具的流程图 demo
- EMC3080的用于连接FogCloud的固件
- 基于VB+Access酒店客房管理系统(源代码+参考文献+报告).zip
- 应用笔记LAT1244+奇怪的NRST+管脚异常复位问题
- SEMI标准的解释说明
- tensorflow-2.8.2-cp37-cp37m-manylinux2010-x86-64.whl
- tensorflow-rocm-2.12.0.560-cp311-cp311-manylinux2014-x86-64.whl
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈