📄 sga.cpp
字号:
//////////////////////////////////
//
// 实验三： 基本sga遗传算法
// 解安徽省17市TSP问题
// 姓名：饶玉佳 学号：E200602075
//
//
#include <stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<conio.h>
#define LENGTH 17 //染色体长度17,代表17个城市
#define POPSIZE 500
double distance[LENGTH][LENGTH];//城市之间的距离矩阵
double cityposition[LENGTH][2]={//城市的相对坐标
{1089.66, 541.02},//淮北0
{538.48, 594.36},//亳州1
{1191.26, 774.70},//宿州2
{1409.70, 1257.30},//蚌埠3
{558.80, 1259.84},//阜阳4
{1209.04, 1465.58},//淮南5
{1358.90, 1973.58},//合肥6
{929.64 , 2059.94},//六安7
{1965.96, 2319.02},//芜湖8
{2166.62, 2580.64},//宣城9
{1473.20, 2776.22},//池州10
{1226.82, 2865.12}, //安庆11
{1661.16, 2603.50},//铜陵12
{1971.04, 3403.60},//黄山13
{1673.86, 2156.46},//巢湖14
{2006.60, 2075.18},//马鞍山15
{1920.24, 1681.48}//滁州16
};
int popsize ; //种群大小
int maxgeneration; //最大世代数
double pcross = 0.0; //交叉率
double pmutation = 0.0; //变异率
double sumfitness; //种群个体适应值累计
struct individual //定义染色体个体结构体
{
int chrom[LENGTH]; //定义染色体二进制表达形式
double fitness; //染色体的适应值
};
int generation; //当前执行的世代数
int best_index; //本世代最好的染色体索引序号
struct individual bestindividual; //最佳染色体个体
struct individual currentbest; //当前最好的染色体个体 currentbest
int bestgeneration; //当前最好染色体个体产生的代数
struct individual oldpop[POPSIZE];//种群数组
struct individual newpop[POPSIZE];//新种群数组
/* 随机数发生器使用的静态变量 */
static double oldrand[55];
static int jrand;
static double rndx2;
static int rndcalcflag;
//函数声明
void printline(FILE *);
void caldistancematrix(FILE *ffp);//设定城市距离矩阵
void initialoldpop(FILE *ffp); //ok-初始化当代种群
void generatenextpop(FILE *ffp); //产生下一代种群
void evaluateoldpop(); //评价种群
void calculateobjectfitness(); //计算种群适应度
void findbestindividual(); //寻找最好的染色体个体
int select(); //选择操作
//将p中移除掉q中位置在j1，j2之间的元素，其余元素前移，返回剩下元素的数量
int searchanddelete(int *p,int* q,int j1,int j2);
void crossover(int *,int *,int *,int *,FILE *ffp); //交叉操作
void mutation(int *); //变异操作
void input(); //输入接口
void outputtextreport(FILE *ffp); //每代输出文字报告
void report(FILE *ffp);//输出最终结果报告
//以下为一些随机数相关函数
void advance_random();
int flip(double);int rnd(int, int);
void randomize();
double randomnormaldeviate();
float randomperc();float rndreal(float,float);
void warmup_random(float);
void main() //主函数
{
int i;
FILE *fp;
//打开文本文件
if((fp= fopen("test1.txt","w+"))==NULL)
{
printf("Can not open file!\n");
}
fprintf(fp,"本程序为使用基本SGA求解tsp问题\n");
generation=0; //初始化generation当前执行的代
input(); //初始化种群大小、交叉率、变异率
randomize(); // 初始化随机数发生器
caldistancematrix(fp);//设定城市距离矩阵
initialoldpop(fp); //产生初始化种群
evaluateoldpop();
while(generation<maxgeneration) //小于最大世代数,执行循环体
{
generation++;
generatenextpop(fp); //生成子代种群(A.选择; B.交叉; C.变异)
for(i = 0 ; i < popsize ; i++)
{
oldpop[i]=newpop[i];
}
evaluateoldpop(); //评价新生子代种群
outputtextreport(fp); //输出当前子代种群统计报告
}
report(fp);//输出最终报告
fclose(fp);
printf("计算结果已经输出到test1.txt文件中。");
getch();
}
void printline(FILE *ffp)
{
fprintf(ffp,"\n*************************************************************\n");
}
void caldistancematrix(FILE *ffp)//设定城市距离矩阵
{
int i,j;
for(i=0;i<LENGTH;i++)
for(j=0;j<LENGTH;j++)
//求城市i,j之间的距离存放在distance[i][j]
{
distance[i][j]=sqrt( pow( cityposition[i][0]-cityposition[j][0] ,2) +
pow( cityposition[i][1]-cityposition[j][1] ,2) );
}
}
void initialoldpop(FILE *ffp) //种群初始化,对种群中每条染色体,生成0-16的不重复序列
{
int i,j,k,m;
srand( (unsigned)time( NULL ) );
for (i=0;i<popsize; i++)
{
//对oldpop[i]染色体生成随机序列
int a[LENGTH] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
j =LENGTH;
m=0;
while(j > 0)
{
k =rand();
k%=j;
oldpop[i].chrom[m]=a[k];
a[k]=a[j-1]; // 把最后一个拷贝到刚生成的位置
m++;
j--;
}
}
}
void generatenextpop(FILE *ffp) //生成下一代
{
int mate1,mate2,j=0;
do{
//挑选交叉配对
mate1=select();
mate2=select();
crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,newpop[j].chrom,newpop[j+1].chrom,ffp);
mutation(newpop[j].chrom);
mutation(newpop[j+1].chrom);
j=j+2;
}
while(j<(popsize-1));
}
void evaluateoldpop() //评价种群
{
calculateobjectfitness(); //计算种群个体的适应度
findbestindividual(); //找到最好和最差的染色体个体
}
void calculateobjectfitness() //计算染色体个体适应值
{
int i,j;
for(i=0;i<popsize;i++)
{
oldpop[i].fitness=0.0;
for(j=0;(j+1)<LENGTH;j++)
oldpop[i].fitness+=distance[oldpop[i].chrom[j]][oldpop[i].chrom[j+1]];
oldpop[i].fitness+=distance[oldpop[i].chrom[LENGTH-1]][0];
}
}
void findbestindividual( ) //求最佳个体
{
int i;
sumfitness=0.0;
bestindividual=oldpop[0];
best_index=0;
sumfitness=+oldpop[0].fitness;
for (i=1;i<popsize; i++)
{
if (oldpop[i].fitness<bestindividual.fitness) //依次比较,找出最佳个体
{
bestindividual=oldpop[i];
best_index=i;
}
sumfitness+=oldpop[i].fitness; // 存放种群总体适应值
}//for
if (generation==0)
{
currentbest=bestindividual; //第一代最好的暂时存放在currentbest
bestgeneration=0;
}
if(bestindividual.fitness<currentbest.fitness)//第n代最好的，通过比较小于以往最好个体的话，暂时存放在currentbest
{
currentbest=bestindividual;
bestgeneration=generation;
}
}
//将p[]中移除掉q[]中位置在j1，j2之间的元素，其余元素前移，返回剩下元素的数量
int searchanddelete(int *p,int* q,int j1,int j2)
{
int num=LENGTH;
int i,j;
for(j=j1;j<j2;j++)
for(i=0;i<num;i++)
{ if(q[j]==p[i])
{
while((i+1)<num)
{
p[i]=p[i+1];
i++;
}
num--;//删除一个元素，计数器减一
}
}
num=LENGTH-(j2-j1);//计算剩下元素的数目
return num;
}
int select() //轮盘赌选择
{
float randomperc();
double sum,pick;
int i;
pick=randomperc(); //产生[0，1]上随机数
sum=0.0;
if(sumfitness!=0)
{
for(i=0;(sum<pick)&&(i<popsize);i++)
sum+=oldpop[i].fitness/sumfitness;
}
else
i=rnd(1,popsize);
return(i-1);
}
void crossover(int *parent1,int *parent2,int *child1,int *child2,FILE *ffp) //ox交叉算法
{
int i,j;
int jcross1,jcross2;//交叉位置
int temp;
int num1,num2;
int temp1[LENGTH],temp2[LENGTH];//分别作为暂存parent1,parent2的数组
for(i=0;i<LENGTH;i++)
{
temp1[i]=parent1[i];
temp2[i]=parent2[i];
}
if(flip(pcross))
{
//在1和LENGTH-1之间随机产生两个交叉位置值
jcross1=-1;
jcross2=-1;
while(jcross1==jcross2)
{
jcross1=rand()%(LENGTH-1)+1;
jcross2=rand()%(LENGTH-1)+1;
}
if(jcross1>jcross2)
{
temp=jcross1;
jcross1=jcross2;
jcross2=temp;
}
//将切割点之间的元素复制到后代的切割点之间
j=jcross1;
while(j<jcross2)
{
child1[j]=temp1[j];
child2[j]=temp2[j];
j++;
}
//将parent2中,除掉child1中位置在jcross1，jcross2之间的元素，其余元素前移，返回剩下元素的数量
num1=searchanddelete(temp2,child1,jcross1,jcross2);
//将parent1中,除掉child2中位置在jcross1，jcross2之间的元素，其余元素前移，返回剩下元素的数量
num2=searchanddelete(temp1,child2,jcross1,jcross2);
//将去掉多余元素的parent2中值复制到child1中，避开jcross1，jcross2之间的元素
j=0;i=0;
while(j<jcross1)
{
child1[j]=temp2[i];
i++;
j++;
}
j=jcross2;//数组下标避开jcross1，jcross2之间的元素
while(i<num1)
{
child1[j]=temp2[i];
i++;
j++;
}
//将去掉多余元素的parent1中值复制到child2中，避开jcross1，jcross2之间的元素
j=0;i=0;
while(j<jcross1)
{
child2[j]=temp1[i];
i++;
j++;
}
j=jcross2;//数组下标避开jcross1，jcross2之间的元素
while(i<num2)
{
child2[j]=temp1[i];
i++;
j++;
}
}//if
else
{
for(i=0;i<LENGTH;i++)
{
child1[i]=temp1[i];
child2[i]=temp2[i];
}
}
}
void mutation(int *child) //变异是在染色体上随机地选择两点，交换其编码
{
int i;
int j1,j2,temp;
for(i=0;i<LENGTH;i++)
{
if (flip(pmutation))
{
j1=rand()%(LENGTH-1)+1;
j2=rand()%(LENGTH-1)+1;
temp=child[j1];
child[j1]=child[j2];
child[j2]=temp;
}
}
}
void input() //数据输入
{
printf("初始化全局变量:\n");
printf(" 种群大小(50-500偶数)：");
scanf("%d", &popsize); //输入种群大小，必须为偶数
if((popsize%2) != 0)
{
printf( " 种群大小已设置为偶数\n");
popsize++;
}
printf(" 最大世代数(100-300)："); //输入最大世代数
scanf("%d", &maxgeneration);
printf(" 交叉率(0.2-0.99)："); //输入交叉率
scanf("%lf", &pcross);
printf(" 变异率(0.001-0.1)："); //输入变异率
scanf("%lf", &pmutation);
}
void outputtextreport(FILE *ffp)//数据输出
{
int i;
printline(ffp);
fprintf(ffp,"\n\t当前世代=%d\n",generation);
fprintf(ffp,"本世代最好的染色体为:\n");
for(i=0;i<LENGTH;i++)
fprintf(ffp," %d-",bestindividual.chrom[i]);
fprintf(ffp,"\n总长度（相对长度）为%6.1f",currentbest.fitness);
}
void report(FILE *ffp)
{
int i;
fprintf(ffp,"\n");
fprintf(ffp," 统计结果: ");
fprintf(ffp,"\n");
fprintf(ffp,"\n种群数：%d", popsize);
fprintf(ffp,"\n最大世代数：%d", maxgeneration);
fprintf(ffp,"\n交叉率：%5.1f", pcross);
fprintf(ffp,"\n变异率：%5.1f", pmutation);
fprintf(ffp,"\n最终求得tsp问题的最短路径解");
fprintf(ffp,"产生于%d代",bestgeneration);
fprintf(ffp,"\n其染色体编码为：");
for( i = 0 ; i < LENGTH ; i++ )
fprintf(ffp," %d-",currentbest.chrom[i]);
fprintf(ffp,"\n总长度（相对长度）为%6.1f",currentbest.fitness);
fprintf(ffp,"\n");
}
void advance_random() // 产生55个随机数
{
int j1;
double new_random;
for(j1 = 0; j1 < 24; j1++)
{
new_random = oldrand[j1] - oldrand[j1+31];
if(new_random < 0.0) new_random = new_random + 1.0;
oldrand[j1] = new_random;
}
for(j1 = 24; j1 < 55; j1++)
{
new_random = oldrand [j1] - oldrand [j1-24];
if(new_random < 0.0) new_random = new_random + 1.0;
oldrand[j1] = new_random;
}
}
int flip(double prob) //以一定概率产生0或1
{
if(randomperc() <= prob)
return(1);
else
return(0);
}
void randomize() /* 设定随机数种子并初始化随机数发生器 */
{
float randomseed;
int j1;
for(j1=0; j1<=54; j1++)
oldrand[j1] = 0.0;
jrand=0;
do
{
printf("请输入随机数种子[0-1]:\n");
scanf("%f",&randomseed);
}
while((randomseed < 0.0) || (randomseed > 1.0));
warmup_random(randomseed);
}
double randomnormaldeviate() // 产生随机标准差
{
double t, rndx1;
if(rndcalcflag)
{ rndx1 = sqrt(- 2.0*log((double) randomperc()));
t = 6.2831853072 * (double) randomperc();
rndx2 = rndx1 * sin(t);
rndcalcflag = 0;
return(rndx1 * cos(t));
}
else
{
rndcalcflag = 1;
return(rndx2);
}
}
float randomperc() //与库函数random()作用相同, 产生[0,1]之间一个随机数
{
jrand++;
if(jrand >= 55)
{
jrand = 1;
advance_random();
}
return((float) oldrand[jrand]);
}
int rnd(int low,int high) //在整数low和high之间产生一个随机整数
{
int i;
if(low >= high)
i = low;
else
{
i = ((int)randomperc() * (high - low + 1)) + low;
if(i > high) i = high;
}
return(i);
}
void warmup_random(float random_seed) //初始化随机数发生器
{
int j1, ii;
double new_random, prev_random;
oldrand[54] = random_seed;
new_random = 0.000000001;
prev_random = random_seed;
for(j1 = 1 ; j1 <= 54; j1++)
{
ii = (21*j1)%54;
oldrand[ii] = new_random;
new_random = prev_random-new_random;
if(new_random<0.0) new_random = new_random + 1.0;
prev_random = oldrand[ii];
}
advance_random();
advance_random();
advance_random();
jrand = 0;
}⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -