基于遗传算法的带容量限制的P-median设施选址问题.zip

//———————基于遗传算法的带容量限制的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 =