#include "stdafx.h"
#include "stdio.h" //标准输入输出库
#include "stdlib.h" //标准函数库
#include "time.h"
#include "iostream.h"
#include "iomanip.h"
#include "math.h" //数学函数库
#define MAX 1 //设定求最大适应值
#define MIN 2
#define CHROMLENGTH 15 //染色体32313133353236313431303231363533e78988e69d8331333262383665长度，注意编码变化时，要随时修改
#define MAXNUM 1000
#define Cmax 30 //估计最大值
#define Cmin 0 //估计最小值
int PopSize = 150; //每代最大个体数
int FunctionMode = MIN;
double m_fPc = 0.9; //交叉概率
double m_fPm = 0.009; //变异概率
int MaxGeneration = 20; //最大世代数
int d[150][15]; //找到染色体并拷贝到这个数组中
int s[150][15];
int generation; //世代数
int Best_Index; //最好个体下标
int Worst_Index; //最坏个体下标
struct individual //定义个体数据结构
{
double chrom[CHROMLENGTH+1]; //染色体
double value; //函数值
double fitness; //适应度
};
struct individual
BestIndividual; //当代最佳个体
struct individual
WorstIndividual;
struct individual
Group[150]; //种群
double Random(double Low, double High)//本函数实现随机产生Low-High之间的实数 .意思：随机
{
return((double)rand()/RAND_MAX)*(High-Low)+Low;
}
double Max(double a, double b)
{
if(a>=b) return a;
else return b;
}
void GenerateInitialPopulation()//种群初始化，二进制编码初始化其中'1'表示路径顶点在最短路径中,'0'则反之
{
int i,j;
for(i = 0; i < PopSize; i++)
{
for(j = 1; j < CHROMLENGTH-2; j++)
{
Group[i].chrom[j] = (int)(Random(1,10)<6)?'':'';
}
Group[i].chrom[CHROMLENGTH-1] = '';
Group[i].chrom[0] = '';
}
}
void CalculateObjectValue() //计算个体值
{
int i,j,l;
int a[15][15]=
{{0, 3, 5, MAXNUM,MAXNUM,MAXNUM,MAXNUM,4, MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM},
{MAXNUM,0, MAXNUM,9, 5, MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,4, MAXNUM,MAXNUM,MAXNUM,MAXNUM},
{MAXNUM,MAXNUM,0, 4, 3, MAXNUM,MAXNUM,MAXNUM,5, MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM},
{MAXNUM,MAXNUM,MAXNUM,0, MAXNUM,1, 5, MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,2, MAXNUM,MAXNUM},
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,0, 8, 4, MAXNUM,MAXNUM,6, MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM},
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0, MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,2, MAXNUM,4, MAXNUM},
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0, MAXNUM,MAXNUM,MAXNUM,MAXNUM,9, MAXNUM,6, MAXNUM},
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,1, MAXNUM,MAXNUM,0, 7, MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM},
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,4, 4, MAXNUM,0, 2, MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM},
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0, MAXNUM,5, MAXNUM,7, MAXNUM},
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0, MAXNUM,1 ,MAXNUM,MAXNUM},
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0, MAXNUM,MAXNUM,2 },
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0 ,2, 3 },
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0, 1 },
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0 },};
for(i=0; i < PopSize; i++)
{
for(l=0; l
{ if(Group[i].chrom[l]!=0)
{
d[i][l]=a[0][l];
s[i][l]=0;
}
}
d[i][0]=0;
s[i][0]=1;
}
for(i=0; i < PopSize; i++)
{
for(l=0; l
{
int u=0; //
for(j=0; j
{
if(!s[i][j]&&Group[i].chrom[j]=='')
{
u=j;
}
s[i][u]=1;
for(int w=0; w
if(!s[i][w]&&Group[i].chrom[w]=='')
{
d[i][w]=d[i][u]+a[u][w];
}
}
}
Group[i].value = d[i][14];
}
}
void CalculateFitnessValue()//根据优化函数值计算出个体适应度
{
int i;
double temp;
for(i=0; i
{
if(FunctionMode==MAX) //求最大值情况
{
if((Group[i].value + Cmin) > 0.0)
{
temp=Cmin + Group[i].value;
}
else
{
temp=0.0;
}
}
else if(FunctionMode==MIN) //求最小值情况
{
if(Group[i].value
{
temp=Cmax-Group[i].value;
}
else
{
temp=0.0;
}
}
Group[i].fitness=temp;
}
}
void FindBestAndWorstIndividual()//从当前群体中找出适应度最好和最差个体
{
int i;
double sum = 0.0;
Best_Index = 0;
Worst_Index = 0;
BestIndividual = Group[0];
WorstIndividual = Group[0];
for(i = 1; i < PopSize; i++)
{
if(Group[i].fitness > BestIndividual.fitness) //适应度高为更优秀个体
{
BestIndividual = Group[i];
Best_Index = i;
}
else if(Group[i].fitness < WorstIndividual.fitness)
{
WorstIndividual = Group[i];
Worst_Index = i;
}
sum += Group[i].fitness;
}
}
void SelectionOperator()//采用比例选择算子产生新群体
{
int i, index;
double p,sum = 0.0;
struct individual *NewGroup = new struct individual[PopSize];
double *cfitness = new double[PopSize]; //存每个个体的概率
for(i = 0; i < PopSize; i++)
{
sum += Group[i].fitness ;
}
for(i = 0; i < PopSize; i++)
{
cfitness[i] = Group[i].fitness/sum;
}
for(i = 1; i < PopSize; i++) //计算累计概率
{
cfitness[i] = cfitness[i-1] + cfitness[i];
}
int temp=0;
for(i = 1; i < PopSize; i++)
{
if(cfitness[temp] > cfitness[i])
temp = i;
}
for(i = 0; i < PopSize; i++) //轮盘赌选择
{
p = (double)(rand()%1000)/1000.0;
index = 0;
while(p > cfitness[index])
{
index++;
}
if(index >= 10)
{
NewGroup[i] = Group[temp];
}
else
{
NewGroup[i] = Group[index];
}
}
//将最好个体复制下来,不参与进化
Group[Best_Index] = Group[Best_Index];
for(i = 0; i < PopSize; i++)
{
if(i != Best_Index)
Group[i] = NewGroup[i];
}
delete []cfitness;
delete []NewGroup;
}
void CrossoverOperator()//采用单点交叉方法产生新群体
{
int i,j;
int index;
int point, temp;
double p;
char ch;
for(i=0; i
{
index=i;
}
for(i=0; i
{
point = (int)Random(0,PopSize-i);
temp=index;
index = point+i;
index = temp;
} //对当前个体进行随机排序
for(i=0; i
{
p=rand()%1000/1000.0;
if(p < m_fPc)
{
point = (int)Random(0,CHROMLENGTH-1)+1;
for(j = point; j
{
if(Group[index].value
{
ch = (int)Group[index].chrom[j];
Group[index].chrom[j]=Group[index+1].chrom[j];
Group[index+1].chrom[j] = ch;
}
}
}
}
}
void MutationOperator()//随机产生变异位，进行染色体基因位的变异
{
int i,j;
double p;
for(i = 0; i < PopSize; i++)
{
if(i != Best_Index) //保证当前最优个体不参与进化
{
for(j = 0;j < CHROMLENGTH; j++)
{
p = rand()%1000/1000.0;
if(p < m_fPm)
{
if(Group[i].value
{
Group[i].chrom[j] = (Group[i].chrom[j]==0)?1:0;
}
}
}
}
}
}
void PerformEvolution()//用当前最好个体代替最差个体
{
Group[Worst_Index] = BestIndividual;
}
void OutPut()//输出计算结果
{
cout<
for(int k=0;k
{
cout<
}
cout<
cout<
cout<
for(int j=0; j
{
cout<
}
cout<
cout<
cout<
cout<
}
void main(void)
{
generation = 0; //意思：一代，代
GenerateInitialPopulation(); //二进制编码初始化'1'表示路径顶点在最短路径中。意思：最初的群体
CalculateObjectValue(); //计算优化函数值. 意思：计算个体值
CalculateFitnessValue(); //根据优化函数值计算出个体适应度
FindBestAndWorstIndividual(); //从当前群体中找出适应度最好和最差个体
while(generation < MaxGeneration)
{
generation++;
SelectionOperator(); //采用比例选择算子产生新群体。意思：选择
CrossoverOperator(); //采用单点交叉方法产生新群体。意思：交叉
MutationOperator(); //随机产生变异位，进行染色体基因位的变异。意思：突变操作
CalculateObjectValue(); //计算个体值。意思：计算个体值
CalculateFitnessValue(); //根据优化函数值计算出个体适应度。意思：适应度
FindBestAndWorstIndividual(); //从当前群体中找出适应度最好和最差个体。意思：个体
PerformEvolution(); //用当前最好个体代替最差个体。意思：实行进化
}
OutPut(); //输出计算结果
}