//———————基于遺傳算法的帶容量限制的p中位問題——————//?
//————————華中科技大學?管理學院?信管專業————————//
//——————————————作者：WRX————————————//?
#include?
#?include?
#?include?
#?include?
#?include?
#?include?
#?include?
#?include?

#?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?lowint?high）//生成一個隨機整數，使其落在[lowhigh]之間??√?
{?
	int?addrandomint;
????
	add?=?rand（）%（high-low）;
	randomint=low+add;?

	return?（randomint）;
}


////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////?
void?Value（int?（*distance）[N]int?*demand）//計算代內各染色體（解）的目標函數值?√?
{
	genotype?*p;
	for（?int?i?=?0;i?	{
		p?=?&population[i];										?//p指向代內的第i個染色體?
		for（?int?j?=?0;j?			p->Z?+=?distance[j][?p->gene[j]?]*demand[j];	?????//函數值=ΣΣdij*ni（xij=1已隱含在p->gene[j]中滿足）?		
	}
}?

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////?
void?Limit（int?*Qint?*demand）//判斷各染色體是否符合容量限制?
{
	int?service[P];
	for（?int?i?=?0;i?	{
		population[i].tag?=?1;					//初始化假設均為可行解?
		for（?int?j?=?0;j?		{
			service[j]?=?0;						//初始化服務站服務量?
			for（?int?k?=?0;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?		{
	????	if?（?population[i].Z?	???		?{
	??		????best?=?i;										/