//———————基于遗传算法的带容量限制的p中位问题——————//
//————————华中科技大学 管理学院 信管专业————————//
//——————————————作者：WRX————————————//
#include <iostream>
# include <cstdlib>
# include <iomanip>
# include <fstream>
# include <iomanip>
# include <cmath>
# include <cstring>
# include <ctime>
# define N 12 //需求点个数
# define P 3 //设施点个数
# define PopulationSize 500 //种群规模
# define Multiply 500 //繁殖次数
# define Crossing 0.8 //交叉概率
# define Variation 0.1 //变异概率
using namespace std;
struct genotype//定义结构体
{
int gene[N]; //gene[i]的值表示i点获得满足的设施点的下标（设施点编号-1）
int facility[P]; //facility[j]的值表示设施点的下标（设施点的编号-1）
double Z; //解对应的目标函数值
double area; //选取染色体的概率
double scale; //染色体在轮盘上的刻度（累积概率）
int tag; //tag=0表示染色体解不符合容量限制，tag=1表示染色体解符合容量限制
};
struct genotype population[PopulationSize+1]; //染色体数组
struct genotype newpopulation[PopulationSize]; //用于更新代内染色体的数组
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int RandomInt(int low,int high)//生成一个随机整数，使其落在[low,high]之间 √
{
int add,randomint;
add = rand()%(high-low);
randomint=low+add;
return (randomint);
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void Value(int (*distance)[N],int *demand)//计算代内各染色体（解）的目标函数值 √
{
genotype *p;
for( int i = 0;i < PopulationSize; i++ ) //遍历代内所有染色体
{
p = &population[i]; //p指向代内的第i个染色体
for( int j = 0;j < N; j++ ) //计算每个染色体（解）的目标函数值
p->Z += distance[j][ p->gene[j] ]*demand[j]; //函数值=ΣΣdij*ni（xij=1已隐含在p->gene[j]中满足）
}
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void Limit(int *Q,int *demand)//判断各染色体是否符合容量限制
{
int service[P];
for( int i = 0;i < PopulationSize; i++ ) //遍历代内所有染色体解，对每个解i
{
population[i].tag = 1; //初始化假设均为可行解
for( int j = 0;j < P; j++ ) //遍历所有服务站j 并判断是否超出容量
{
service[j] = 0; //初始化服务站服务量
for( int k = 0;k < N; k++ ) //遍历需求点
if( population[i].gene[k] == population[i].facility[j] )// 计数服务站j提供服务的量
service[j] += demand[k];
if( service[j] > Q[population[i].facility[j]] )//只要有一个服务站超出容量限制，就更改染色体解的tag
population[i].tag = 0;
}
}
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void SelectBest()//寻找并记录最优解染色体到population[PopulationSize]
{
int best=PopulationSize;
for( int i = 0;i < PopulationSize; i++ ) //遍历代内染色体寻找最优函数值
{
if ( population[i].Z < population[PopulationSize].Z && population[i].tag == 1 )//找出符合容量限制的最优染色体解
{
best = i; //用best记录当前最优染色体解的下标
population[PopulationSize].Z = population[i].Z; //用population[PopulationSize]记录当前最优染色体的函数值
}
}
if(best!=PopulationSize)//更新最优解记录到population[poulationSize]
{
for ( int i = 0;i < N; i++ )
population[PopulationSize].gene[i] = population[best].gene[i];
for ( int i = 0;i < P; i++ )
population[PopulationSize].facility[i] = population[best].facility[i];
}
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void Init(int (*distance)[N],int *demand) //生成初代染色体函数 √
{
int n,flag,min;
struct genotype *p;
for(int i=0;i<PopulationSize;i++)//生成初代染色体
{
p=&population[i]; //p指向代内的第i个染色体
for(int j=0;j<P;j++) //随机生成P个设施点
{
int k=0;
if(j==0)
p->facility[j]=RandomInt(0,N-1); //第一个设施从1-N各需求点中随机选择
else
{
p->facility[j]=RandomInt(0,N-1); //第j个设施从1-N各需求点中随机选择
while(k<j)
{
if(p->facility[j]==p->facility[k]) //若j与之前设施点重复，重新生成一个设施点
{
p->facility[j]=RandomInt(0,N-1);
k=0;
}
else k++;
}
}
}
for( int m = 0;m < N; m++ ) //初始化每个需求点的对应服务设施
{
for( int q = 0;q < P; q++ )//对每个设施点
{
n = p->facility[q]; //用n记录设施点的下标
if(q==0) //假设每个点到第一个设施点的距离最近
{
min = distance[m][n];
flag = n;
}
else
{
if(distance[m][n]<min) //更新每个需求点对应的最近的设施点距离
{
min = distance[m][n];
flag = n; //记录离需求点最近的设施点下标
}
}
}
p->gene[m]=flag; //让离需求点最近的设施点作为该需求点的供给
}
}
Value(distance,demand);//初始化初代染色体的目标函数值
population[PopulationSize].Z=RAND_MAX;//假设初代不寻找最优值直接当作极劣
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void Select()//对染色体进行模拟环境选择的轮盘筛选（以较大概率选出较好的解）√
{
double sum,p;
sum=0.0; //sum表示整个圆盘的面积
for( int i = 0;i < PopulationSize; i++ )//求整个圆盘的面积
if(population[i].tag == 1) //只有符合容量限制的解才画入圆盘
sum += ( 1 - population[i].Z );
for( int i = 0; i < PopulationSize; i++ ) //计算代内每个染色体被选中的概率
if(population[i].tag == 1) //判断是否符合容量限制，若符合
population[i].area=(1-population[i].Z)/sum; // Z越小解越优，被选中的概率越大，在圆盘上所占的面积越大
else //若不符合容量限制，不放在轮盘上
population[i].area=0;
population[0].scale = population[0].area; //以第一个染色体（解）做0点
for ( int i = 1; i < PopulationSize; i++ ) //计算各染色体（解）在圆盘上的刻度
population[i].scale = population[i-1].scale + population[i].area; //计算第k个染色体在轮盘上的刻度scale（累积概率）
for (int i = 0; i < PopulationSize; i++ )//选出比较能够适应环境的染色体（以较大概率选择较优解）
{
p = rand()/(RAND_MAX+1.0); //随机旋转轮盘，p是轮盘的指针
if ( p < population[0].scale && population[0].tag == 1 )
newpopulation[i] = population[0];
else
{
for (int j = 1; j < PopulationSize; j++ )//找到指针对应选中的合法染色体j
{
if ( population[j-1].scale < p && p <= population[j].scale && population[j].tag == 1)
newpopulation[i] = population[j]; //选中染色体j进行保留
}
}
}
for ( int i = 0; i < PopulationSize; i++ )//环境筛选后，更新代内染色体
population[i] = newpopulation[i];
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void Change(int one,int another)//染色体交换基因（交叉) √
{
int cut,temp;
cut=RandomInt(0,N-1); //随机选择交叉点cut
for(int i=0;i<cut;i++) //两个染色体交换0到cut-1的基因
{
temp=population[one].gene[i];
population[one].gene[i] = population[another].gene[i];
population[another].gene[i] = temp;
}
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void Cross()//代内染色体随机交叉函数 √
{
int i,flag=0;
double p;
for(int j =
