genetic.cpp

毕业设计论文~~要的来看啊~~~ 很完整的

// Genetic.cpp: implementation of the CGenetic class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "GA.h"
#include "Genetic.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

//genetic.cpp: implementation of the genetic class, task class and agent class
#include <stdlib.h>
#include "genetic.h"
#include <time.h>
#include "agents.h"

#include "genetic.h"
#include "time.h"
#include "stdio.h"


// Construction/Destruction

CGenetic::CGenetic() 
{
	popsize = 20; //初始种群数量
	length = 30; //基因长度，代表agent的个数
	sumfitness = 0; //整体适应度
	cs_flag = NULL;
	oldpop = NULL;
	newpop = NULL;
	temppop = NULL;
}

CGenetic::CGenetic(int number, //种群数量
				 int len, //agent长度
				 int gen, //遗传代数
				 float c_p, //交叉率
				 float m_p, //变异率
				 CAgents *re_agents, //当前agents
				 CTasks* re_tasks, //当前tasks
				 int task_number,
				 int cond) //条件
{
	int i;
	
	//初始化成员函数
	m_subtask  = task_number; //
	condition = cond;
	r_flag = 0; 
	a_t = re_agents; 
	r_tasks = re_tasks;
	popsize = number;
	length = len;
	gen_number = gen;
	p_cross = c_p;
	p_mutation = m_p;
	sumfitness = 0;
	elitist.fitness = 0;

	for(i=0; i<len; i++) 
		elitist.chrom[i] = 0;

	cs_flag = new int[task_number+1]; //任务标志
	oldpop = new struct individual[popsize];
	newpop = new struct individual[popsize];
	temppop = new struct individual[popsize];

	i = 0;
	while(elitist.fitness==0 && i <20) // 初始化种群，尽量确保最优解fitness非0
	{
		initpop();
		i ++;
	}
	
}

CGenetic::~CGenetic()
{
	delete [] cs_flag;
	delete [] oldpop;
	delete [] newpop;
	delete [] temppop;
	cs_flag = NULL;
	oldpop = NULL;
	newpop = NULL;
	temppop = NULL; 
}

void CGenetic::init(int number, //种群数量
					int len, //agent长度
					int gen, //遗传代数
					float c_p, //交叉率
					float m_p, //变异率
					CAgents *re_agents, //当前agents
					CTasks* re_tasks, //当前tasks
					int task_number,
					int cond) //条件
{
	int i;
	
	//初始化成员函数
	m_subtask  = task_number; //
	condition = cond;
	r_flag = 0; 
	a_t = re_agents; 
	r_tasks = re_tasks;
	popsize = number;
	length = len;
	gen_number = gen;
	p_cross = c_p;
	p_mutation = m_p;
	sumfitness = 0;
	elitist.fitness = 0;
	
	for(i=0; i<len; i++) 
		elitist.chrom[i] = 0;
	
	cs_flag = new int[task_number+1]; //任务标志
	oldpop = new struct individual[popsize];
	newpop = new struct individual[popsize];
	temppop = new struct individual[popsize];
	
	i = 0;
	while(elitist.fitness==0 && i <20) // 初始化种群，尽量确保最优解fitness非0
	{
		initpop();
		i ++;
	}
	
}


int CGenetic::select() // 选择操作,采用赌轮法
{
	double rand1, partsum;
	int j;
	partsum = 0;
	j = 0;

	rand1 = (float)rand()/RAND_MAX*sumfitness; //随概率取适应度值

	do
	{
		partsum += oldpop[j].fitness;
		j ++;
	}while(partsum<rand1 && (j<popsize)); //找到该概率个体

	return j-1; //返回被选中的个体编号
} 

int CGenetic::crossover(char* parent1, char* parent2, int j_n) //交叉操作
{ //非简单交叉，交叉过程中伴随变异
	int j, jcross;

	if(flip(p_cross)) //概率< p_cross
	{
		jcross = rand() % length; //随机cross长度
	}
	else jcross = length; //整个长度
	
	if(jcross != length) //交叉
	{
		for(j=0; j<jcross; j++) // <jcross段不交叉
		{
			newpop[j_n].chrom[j] = mutation(parent1[j]); 
			newpop[j_n+1].chrom[j] = mutation(parent2[j]);
		}
		
		for(j=jcross; j<length; j++) // 从jcross后段交叉
		{
				newpop[j_n].chrom[j] = mutation(parent2[j]);
				newpop[j_n+1].chrom[j] = mutation(parent1[j]);
		}
	}
	else //不交叉
	{
		for(j=0; j<length; j++) 
		{
			newpop[j_n].chrom[j] = mutation(parent1[j]);
			newpop[j_n+1].chrom[j] = mutation(parent2[j]);
		}
	}

	newpop[j_n].xsite = jcross;
	newpop[j_n+1].xsite = jcross;

	return 1; // 始终为true
} 


int CGenetic::mutation(char ch) // 变异
{
	int mutate;
	int mchar;
	mutate = flip(p_mutation); 

	if(mutate) //概率<p_mutation,则取基因反
	{
		mchar = get_random(0, m_subtask-1); // rand【0，m_subtask-】
		if (mchar >= ch) mchar += 1;
		ch = mchar;
	}
	return ch;
} 

int CGenetic::initpop()//群体初始化 
{
	int i, j;
	for(i=0; i<popsize; i++)
	{
		for(j=0; j<length; j++)
		{
			oldpop[i].chrom[j] = rand()%(m_subtask+1);
		}
		oldpop[i].parent1 = 0;
		oldpop[i].parent2 = 0;
		oldpop[i].xsite = 0;
		oldpop[i].fitness = fitness_v(oldpop[i].chrom);
	} 
	
	statistics(oldpop); //计算适应度
	return 1;
}


int CGenetic::get_random(int min, int max) //返回0 ~ max-min之间的随机值
{
	return (rand()%(max-min+1)); 
}


void CGenetic::statistics(individual *pop) //统计个体适应度和群体适应度
{
	int i;
	float min; //非0适应度的 最小值
	min = 0.01f;

	for(i=0; i<popsize; i++)
	{
		if(pop[i].fitness == 0) pop[i].fitness = min;
		sumfitness += pop[i].fitness;
	}
	//为维持群体的多样性，使每个个体的适应度都大于0	 
} 

int CGenetic::flip(float prob)//伯努利实验,返回概率事件
{
	float ppp;
	ppp = (float)((rand()%3002)/3000.00);
	if(ppp < prob) return 1;
	else return 0;
} 


void CGenetic::generation()//产生新一代的群体
{
	int mate1, mate2, j;

	int min_no; //联盟中适应度最小的个体的序号

	//int hamm_distance；//汉姆距离

	float min; 

	int i, k, no;
	//temppop = oldpop;
	memcpy(temppop, oldpop, sizeof(struct individual)* popsize);
	for(i=0; i<popsize; i++)
	{
		no = select(); // 赌轮选择
		//替换种群
		oldpop[i].fitness = temppop[no].fitness;
		for(k=0; k<length; k++)
		{
			oldpop[i].chrom[k] = temppop[no].chrom[k];		
		}
	}
	
	sort(oldpop); //重新排序
	j = 0;
	do
	{
		//mate1 = select(); mate2 = select();
		mate1 = j; mate2 = j+1; //采用邻接法，强强结合
		crossover(oldpop[mate1].chrom, oldpop[mate2].chrom, j); //交叉
		newpop[j].parent1 = mate1;
		newpop[j].parent2 = mate2;

		newpop[j].fitness = fitness_v(newpop[j+1].chrom); //计算
		j += 2;
	}while(j < popsize);
	
	statistics(newpop); //计算新一代的适应度

	//以下为最佳保留法

	//查找适应度最小个体
	min = newpop[0].fitness;
	min_no = 0;
	for(j=1; j<popsize; j++) 
	{
		if(newpop[j].fitness < min)
		{
			min = newpop[j].fitness;
			min_no = j;
		}
	}
	//将适应度最小个体用最佳个体替换
	newpop[min_no].fitness = elitist.fitness;
	for(j=0; j<length; j++)
	{
		newpop[min_no].chrom[j] = elitist.chrom[j];
	}	 
}


float CGenetic::fitness_v(char *p) //适应度评估函数
{
	int (*sum_a)[MAX_NUM]; //agent 联盟能力向量总和数组；
	int *cost; //agent 联盟代价变量
	float min; //非0适应值的最小值
	int *flag; //标志是当前联盟是否可行
	int aflag; //至少有一个可用的任务
	int j, k;
	float t_fitness;

	min = 0.01f; 
	t_fitness = 0.0f;
	
	sum_a = new int[m_subtask+1][MAX_NUM]; //分配一个二维表
	cost = new int[m_subtask+1]; 
	flag = new int[m_subtask+1];

	for(j=1; j<m_subtask+1; j++)
	{
		cost[j] = 0; //初始代价为0
		flag[j] = 1; //初始化标志为1
		for (k=0; k<a_t->m_abilityNum; k++) //初始化能力向列表为0
		{
			sum_a[j][k] = 0;
		}
	}

	aflag = 0;
	
	for(j=0; j<length; j++)
	{
		if(p[j]) //不为0
		{
			for(k=0; k<a_t->m_abilityNum; k++)	//计算agent联盟的能力向量二维表
				sum_a[p[j]][k] += a_t->m_agentList[j].ability[k];
			cost[p[j]] += a_t->m_agentList[j].cost;//计算agent联盟的代价 
		}
	}
	//对agent联盟结构 vs 任务能力向量表
	for(j=1; j<m_subtask+1; j++) 
	{
		for (k=0; k<a_t->m_abilityNum; k++)
		{
			if (sum_a[j][k] < r_tasks->m_taskList[j].need_ability[k])
			{
				flag[j] = 0;
				break;
			}
		}
		if (flag[j] == 1)
		{
			aflag = 1;
		}
	}
	
	if(aflag == 1) //若agnet联盟的能力大于或等于某个task所需能力 
	{
		float sumcost = 0.0f;
		float sumprofit = 0.0f;
		for(j=1; j<m_subtask+1; j++)
		{
			if (flag[j]) //该任务可行，则累积t_fitness
			{
				//sumcost += cost[j];
				//sumprofit += r_tasks->m_taskList[j].profit;
				t_fitness +=  ((float) r_tasks->m_taskList[j].profit /cost[j]); 
			//	t_fitness +=  ((float) r_tasks->m_taskList[j].profit*3-cost[j]);

			}
		}

		//t_fitness = sumprofit / sumcost;

		//找到更优解，则更新elitist
		if (t_fitness > elitist.fitness) 
		{
			elitist.fitness = t_fitness;
			for (j=1; j<m_subtask+1; j++)
			{
				cs_flag[j] = flag[j];
				for (k=0; k<length; k++)
				{
					elitist.chrom[k] = p[k];
				}
			}
		}
		//检查条件
		if (condition == 0)
		{
			r_flag = 1;
			return t_fitness;
		}
	}

	delete [] sum_a;
	delete [] cost;

	return t_fitness;
} 



void CGenetic::sort(individual *pop)//个体排序 
{
	int i, j, k;
	individual temp;
	for(i=0; i<popsize; i++) //选择排序，按个体适应度从高到低
		for(j=i+1; j<popsize; j++)
		{
			if(pop[j].fitness > pop[i].fitness) //交换
			{
				temp.fitness = pop[i].fitness;
				for(k=0; k<length; k++)
					temp.chrom[k] = pop[i].chrom[k];

				pop[i].fitness = pop[j].fitness;
				for(k=0; k<length; k++)
					pop[i].chrom[k] = pop[j].chrom[k];

				pop[j].fitness = temp.fitness;
				for(k=0; k<length; k++)
					pop[j].chrom[k] = temp.chrom[k];
			}
				
		}
}