📄 ga_tsp.cpp
字号:
/*********************************************************************/
/* 通过C++语言的并行遗传算法解决TSP问题 */
/*********************************************************************/
//vision：1.6
//data:2008-06-05
//author:Alan Jiang
#include <math.h>
#include <iostream>
#include <time.h>
using namespace std;
//算法配置，可更改
#define PopSize 50 //种群类DNA个数
#define MaxGens 200 // 最大代数
#define NumVars 10 // 问题规模
#define PXCross 0.8 // 交叉概率
#define PMutation 0.15 // 突变概率
//#define Numprocs 4 //动用处理器数
int city[NumVars];
int begin_city=0; //更改出发城市
double r[NumVars][NumVars]={
0, 1, 4, 6, 8, 1, 3, 7, 2, 9,
1, 0, 7, 5, 3, 8, 3, 4, 2, 4,
4, 7, 0, 3, 8, 3, 7, 9, 1, 2,
6, 5, 3, 0, 3, 1, 5, 2, 9, 1,
8, 3, 8, 3, 0, 2, 3, 1, 4, 6,
1, 8, 3, 1, 2, 0, 3, 3, 9, 5,
3, 3, 7, 5, 3, 3, 0, 7, 5, 9,
7, 4, 9, 2, 1, 3, 7, 0, 1, 3,
2, 2, 1, 9, 4, 9, 5, 1, 0, 1,
9, 4, 2, 1, 6, 5, 9, 3, 1, 0
} ;
int generation; // 当前代数
int CurBest; // 最优个体
struct GenoType
{
int gene[NumVars]; // 城市序列
double fitness; // 当前城市序列对应的适应值
double rfitness; // 传统的适应率
double cfitness; // 轮盘对应的起始区间值
};
struct ResultType
{
double best_val; //最佳适应度
double avg; //平均适应度
double stddev; //标准差
};
GenoType population[PopSize+1]; // 种群
GenoType newpopulation[PopSize+1]; //新种群
//ResultType result[Numprocs][MaxGens];//种群换代记录
ResultType result[MaxGens];//种群换代记录
//函数声明
void initialize();//初始化
void evaluate();//评估函数
void keep_the_best();//找出最优
void elitist();//
void select();//选择
void crossover();//交叉
void mutate();//变异
void report();//报告
int IntGenerate();//产生一个城市节点
void swap(int *,int *);//交换两值
/*******************************************************/
/* 交换两个值 */
/*******************************************************/
void swap(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
/*********************************************/
/* 产生一个0到10的数，作为城市编号 */
/*********************************************/
int IntGenerate()
{
int RANGE_MIN = 0;
int RANGE_MAX = NumVars;
int rand10 = (((double) rand()/(double) RAND_MAX) * RANGE_MAX + RANGE_MIN);
return rand10;
}
/*******************************************************/
/* 初始化种群 */
/*******************************************************/
void initialize()
{
int matrix[NumVars];
int x1,x2;
//生成一个定值序列 ，0点为开始点，无需改变
for(int i=1; i<NumVars; i++)
matrix[i]=i;
for(int j=0;j<PopSize;j++)
{
population[j].gene[0]=begin_city; //gene[0]表示出发城市，i表示城市次序
for(int i=0;i<NumVars;i++) //NumVars次交换足以产生各种结果了
{
x1=0; x2=0;
while(x1==0)
x1=IntGenerate();
while(x2==0)
x2=IntGenerate();
swap(&matrix[x1],&matrix[x2]);
}
for(i=1;i<NumVars;i++)
population[j].gene[i]=matrix[i];
}
}
/**************************************************************/
/* 评估函数：计算出该种群的适应性 */
/**************************************************************/
void evaluate()
{
int current_city=begin_city;
int next_city;
for(int mem=0;mem<PopSize;mem++)
{
population[mem].fitness=0;
for(int i=1;i<NumVars;i++)
{
next_city=population[mem].gene[i];
population[mem].fitness += r[current_city][next_city];
current_city=next_city;
}
population[mem].fitness += r[current_city][begin_city];
}
}
/******************************************************************/
/* 找出该代种群中的最优个体，并将其存储. */
/******************************************************************/
void keep_the_best() // Add population[PopSize]=population[0] before this function, it will be OK!
{
int mem,i;
CurBest=0;
for(mem=1;mem<PopSize;mem++)
if(population[mem].fitness<population[CurBest].fitness) // 一次冒泡找出最优
CurBest=mem;
//找到最优个体后，将其存储起来
for(i=0;i<NumVars;i++)
population[PopSize].gene[i]=population[CurBest].gene[i];
population[PopSize].fitness=population[CurBest].fitness;
}
/***************************************************************************/
/* 择优函数：将当代中的最优及最差个体保存下来， */
/* 如果新种群中最优个体优于父代中最优个体，则将其保存下来； */
/* 否则，将当代中最差个体替换为父代中最优个体 */
/***************************************************************************/
void elitist() //择优函数
{
int i;
double best,worst;
int best_mem,worst_mem;
best=population[0].fitness;
worst=population[0].fitness;
//冒泡比较两个个体中的适应度，并可能选择较大的放入worst_mem和较小的放入best_mem
for(i=0;i<PopSize-1;++i)
{
if(population[i].fitness<population[i+1].fitness)
{
if(population[i].fitness<=best)
{
best=population[i].fitness;
best_mem=i;
}
if(population[i+1].fitness>=worst)
{
worst=population[i+1].fitness;
worst_mem=i+1;
}
}
else
{
if(population[i].fitness>=worst)
{
worst=population[i].fitness;
worst_mem=i;
}
if(population[i+1].fitness<=best)
{
best=population[i+1].fitness;
best_mem=i+1;
}
}
//end 冒泡
}
/*如果新种群中最优个体优于父代中最优个体，则将其保存下来；*/
/* 否则，将当代中最差个体替换为父代中最优个体 */
if(best<=population[PopSize].fitness)
{
for(i=0;i<NumVars;i++)
population[PopSize].gene[i]=population[best_mem].gene[i];
population[PopSize].fitness=population[best_mem].fitness;
}
else
{
for(i=0;i<NumVars;i++)
population[worst_mem].gene[i]=population[PopSize].gene[i];
population[worst_mem].fitness=population[PopSize].fitness;
}
}
//轮盘赌算法根据轮盘赌算法来选择复制的个体
void select()
{
int mem,i,j;
double sum=0.0;
double p;
double x[PopSize];
for(mem=0;mem<PopSize;mem++)
sum+=population[mem].fitness;
/* 由于此处选择应是fitness越小越好，
而传统的轮盘赌算法为适应值越大越好，顾需将其做一个转换*/
for(mem=0;mem<PopSize;mem++)
x[mem]=sum-population[mem].fitness;
sum=0.0;
//求得传统适应总值
for(mem=0;mem<PopSize;mem++)
sum+=x[mem];
//求得适应率
for(mem=0;mem<PopSize;mem++)
population[mem].rfitness=x[mem]/sum;
//求得轮盘对应的各个区间
population[0].cfitness=population[0].rfitness;
for(mem=1;mem<PopSize;mem++)
{
population[mem].cfitness=population[mem-1].cfitness+population[mem].rfitness;
}
//通过轮盘来选择是否保留该个体
for(i=0;i<PopSize;i++)
{
p=rand()%1000/1000.0;
if(p<population[0].cfitness)
newpopulation[i]=population[0];
else
{
for(j=0;j<PopSize;j++)
if(p>=population[j].cfitness && p<population[j+1].cfitness)
newpopulation[i]=population[j+1];
}
}
//将新种群中的个体复制到原种群中
for(i=0;i<PopSize;i++)
population[i]=newpopulation[i];
}
/***************************************************************/
/* 交叉遗传：实质为将一段路径‘串’逆序 */
/***************************************************************/
void crossover()
{
int i,j;
int min,max,flag;
double x;
for(i=0;i<PopSize;i++)
{
x=rand()%1000/1000.0;
if(x<PXCross)
{
min=0;
max=0;
while(min==0)
min=IntGenerate();
while(max==0)
max=IntGenerate();
if(max<min)
{
int temp;
temp=max;
max=min;
min=temp;
}
flag=max;
for(j=min;j<=(max+min)/2;j++)
{
swap(&population[i].gene[j],&population[i].gene[flag]);
flag=flag-1;
}
}
}
}
/**************************************************************/
/* 变异函数：将种群中两个位置的节点值互换 */
/**************************************************************/
//变异操作
void mutate()
{
int i;
double x;
int x1,x2;
for(i=0;i<PopSize;i++)
{
x=(int)rand()%1000/1000.0;
if(x<PMutation)
{
x1=0;
x2=0;
while(x1==0)
x1=IntGenerate();
while(x2==0)
x2=IntGenerate();
swap(&population[i].gene[x1],&population[i].gene[x2]);
}
}
}
/***************************************************************/
/* 报告函数：将进化过程记录在输出文件中 */
/***************************************************************/
//void report(int my_id)
void report()
{
int i;
double best_val; //最佳适应度
double avg; //种群平均适应度
double stddev; //种群适应度标准差
double sum_square; //适应度的平方和
double square_sum;
double sum; //适应度总和
sum=0.0;
sum_square=0.0;
for(i=0;i<PopSize;i++)
{
sum+=population[i].fitness;
sum_square+=population[i].fitness*population[i].fitness;
}
avg=sum*1.0/(1.0*PopSize);
square_sum=avg*avg*PopSize;
stddev=sqrt((sum_square-square_sum)/(PopSize-1));
best_val=population[PopSize].fitness;
result[generation-1].best_val = best_val;
result[generation-1].avg = avg;
result[generation-1].stddev = stddev;
}
/**************************************************************/
/* 主函数：每一代都通过交叉、变异之后，通过评估函数评估， */
/* 然后选择最好的个体，直至最大代数 */
/**************************************************************/
int main()
{
int i;
int ierr,myid,numprocs;
/*MPI_Init(ierr);
MPI_Comm_rank(MPI_COMM_WORLD,myid);
MPI_Comm_size(MPI_COMM_WORLD,numprocs);
if(myid == 0)
{*/
cout<<" ***************************************\n";
cout<<" ★ 欢迎使用本遗传算法程序 ★\n";
cout<<" ***************************************\n\n";
cout<<" 本程序用于求 TSP 问题, 有"<<NumVars<<"个城市\n BEGIN:\n\n";
cout<<" 经演化得出结果：\n";
cout<< "\nGeneration Number | Best Value | Average Fitness | Standard Deviation\n";
// }
generation = 0;
srand( (unsigned)time( NULL ) );
initialize();
evaluate();
keep_the_best();
while(generation<MaxGens)
{
generation++;
select();
crossover();
mutate();
//report(my_id);
report();
evaluate(); //?
elitist();
}
for(i = 0 ; i < MaxGens ; i++)
{
cout<<" "<<i+1<<" "<<result[i].best_val<<" "<<result[i].avg<<" "<<result[i].stddev<<endl;
}
/*if(myid == 0)
{*/
cout<<"\n\n 进化完成\n";
cout<<"\n 最佳路径: \n";
cout<<"城市1 = "<<begin_city<<endl;;
for (i = 1; i < NumVars; i++)
{
cout<<"城市"<<i<<" = "<<population[PopSize].gene[i]<<endl;
}
cout<<"最佳适应值为"<<population[PopSize].fitness<<endl;;
cout<<("\n\n 本遗传算法程序执行完毕!\n\n");
cout<<"总进化时间为:"<<(double)clock()/1000<<"秒\n";
/* }
MPI_Finalize(ierr);*/
system("pause");
return 0;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -