//遗传算法考察
/*通过C++语言的运用遗传算法解决TSP问题 */
//日期:2009-06-12
//编译:潘跃聪
#include <math.h>
#include <iostream>
#include <time.h>
using namespace std;
#define PopSize 50 //种群类DNA个数
#define MaxGens 200 // 最大代数
#define N 20 // 问题规模
#define PC 0.8 // 交叉概率
#define PM 0.01 // 突变概率
int city[N];
int begin_city=0; //出发城市
double r[N][N]={
0, 1, 4, 6, 8, 1, 3, 7, 2, 9, 7, 3, 4, 5, 8, 9, 2, 8, 2, 8,
1, 0, 7, 5, 3, 8, 3, 4, 2, 4, 4, 6, 2, 8, 2, 9, 4, 5, 2, 1,
4, 7, 0, 3, 8, 3, 7, 9, 1, 2, 5, 8, 1, 8, 9, 4, 7, 4, 8, 4,
6, 5, 3, 0, 3, 1, 5, 2, 9, 1, 3, 5, 7, 3, 4, 7, 3, 4, 5, 2,
8, 3, 8, 3, 0, 2, 3, 1, 4, 6, 3, 8, 4, 5, 2, 8, 1, 7, 4, 7,
1, 8, 3, 1, 2, 0, 3, 3, 9, 5, 4, 5, 2, 7, 3, 6, 2, 3, 7, 1,
3, 3, 7, 5, 3, 3, 0, 7, 5, 9, 3, 4, 5, 9, 3, 7, 3, 2, 8, 1,
7, 4, 9, 2, 1, 3, 7, 0, 1, 3, 4, 5, 2, 7, 6, 3, 3, 8, 3, 5,
2, 2, 1, 9, 4, 9, 5, 1, 0, 1, 3, 4, 7, 3, 7, 5, 9, 2, 1, 7,
9, 4, 2, 1, 6, 5, 9, 3, 1, 0, 3, 7, 3, 7, 4, 9, 3, 5, 2, 5,
7, 4, 5, 3, 3, 4, 3, 4, 3, 3, 0, 5, 7, 8, 4, 3, 1, 5, 9, 3,
3, 6, 8, 5, 8, 5, 4, 5, 4, 7, 5, 0, 8, 3, 1, 5, 8, 5, 8, 3,
4, 2, 1, 7, 4, 2, 5, 2, 7, 3, 7, 8, 0, 5, 7, 4, 8, 3, 5, 3,
5, 8, 8, 3, 5, 7, 9, 7, 3, 7, 8, 3, 5, 0, 8, 3, 1, 8, 4, 5,
8, 2, 9, 4, 2, 3, 3, 6, 7, 4, 4, 1, 7, 8, 0, 4, 2, 1, 8, 4,
9, 9, 4, 7, 8, 6, 7, 3, 5, 9, 3, 5, 4, 3, 4, 0, 4, 1, 8, 4,
2, 4, 7, 3, 1, 2, 3, 3, 9, 3, 1, 8, 8, 1, 2, 4, 0, 4, 3, 7,
8, 5, 4, 4, 7, 3, 2, 8, 2, 5, 5, 5, 3, 8, 1, 1, 4, 0, 2, 6,
2, 2, 8, 5, 4, 7, 8, 3, 1, 2, 9, 8, 5, 4, 8, 8, 3, 2, 0, 4,
8, 1, 4, 2, 7, 1, 1, 5, 7, 5, 3, 3, 3, 5, 4, 4, 7, 6, 4, 0,
} ;
int generation; // 当前代数
int CurBest; // 最优个体
struct GenoType
{
int gene[N]; // 城市序列
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[MaxGens];//种群换代记录
//函数声明
void initialize();//初始化
void evaluate();//评价函数
void Find_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 = N;
int rand10 = (((double) rand()/(double) RAND_MAX) * RANGE_MAX + RANGE_MIN);
return rand10;
}
/*初始化种群*/
void initialize()
{
int matrix[N];
int x1,x2;
//生成一个定值序列 ，0点为开始点
for(int i=1; i<N; i++)
matrix[i]=i;
for(int j=0;j<PopSize;j++)
{
population[j].gene[0]=begin_city; //gene[0]表示出发城市，i表示城市次序
for( i=0;i<N;i++) //N次交换足以产生各种结果了
{
x1=0; x2=0;
while(x1==0)
x1=IntGenerate();
while(x2==0)
x2=IntGenerate();
swap(&matrix[x1],&matrix[x2]);
}
for(int i=1;i<N;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<N;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 Find_the_best() //
{
int mem,i;
CurBest=0;
for(mem=1;mem<PopSize;mem++)
if(population[mem].fitness<population[CurBest].fitness) // 一次冒泡找出最优
CurBest=mem;
//找到最优个体后，将其存储起来
for(i=0;i<N;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<N;i++)
population[PopSize].gene[i]=population[best_mem].gene[i];
population[PopSize].fitness=population[best_mem].fitness;
}
else
{
for(i=0;i<N;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<PC)
{
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<PM)
{
x1=0;
x2=0;
while(x1==0)
x1=IntGenerate();
while(x2==0)
x2=IntGenerate();
swap(&population[i].gene[x1],&population[i].gene[x2]);
}
