mydeploy.cpp

利用一个较为成熟的遗传算法基础类库（作者:刘康）

#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include "myDeploy.h"
#include "math.h"

//构造函数
MyDeploy::MyDeploy(int n, int ones) : Genetic(n, ones, WIDTH*LENGTH)
{
}


//计算个体评价函数值，最小化最大分辨误差
double MyDeploy::EvalVal(INDIVIDUAL &ind)
{
	const char *sensor=ind.Chrom.GetGeneStr();
	int length=ind.Chrom.GetLen();
	int w,l; //行和列
	double max,tmp;
	int i,j,k,distance;

	DETECT_VECTOR *grid_t=(DETECT_VECTOR*)grid;

	////////////////////////////////////////////////////////////////////
	/*
	//这部分用于保证区域是完全覆盖的
	memset(grid_t,0,WIDTH*LENGTH);

	//根据节点部署，计算每个网格点的覆盖情况
	for(i=0; i<length; i++){
		if(sensor[i]=='1'){	//此网格点有传感器
			w=i/LENGTH;		//行号
			l=i-w*LENGTH;	//列号
			//能覆盖到的网格点
			//self
			grid[0][0].vector[i]=1;
			//top
			if(w>0) 
				grid[0][0].vector[i-LENGTH]=1;
			//bottom
			if(w<WIDTH-1) 
				grid[0][0].vector[i+LENGTH]=1;
			//left
			if(l>0) 
				grid[0][0].vector[i-1]=1;
			//right
			if(l<LENGTH-1) 
				grid[0][0].vector[i+1]=1;
		}

	}
	
	max=0;
	for(i=0; i<WIDTH*LENGTH; i++){
		max+=grid[0][0].vector[i];
	}
	ind.Val=100;
	if(max!=100) return ind.Val;
	*/
	////////////////////////////////////////////////////////////////////

	//初始化网格点向量
	for(i=0; i<WIDTH*LENGTH; i++){
		memset(grid_t+i,0,WIDTH*LENGTH);
	}

	//根据节点部署，计算每个网格点的检测向量
	for(i=0; i<length; i++){
		if(sensor[i]=='1'){	//此网格点有传感器
			w=i/LENGTH;		//行号
			l=i-w*LENGTH;	//列号
			//检测能覆盖到的网格点，设置其向量
			//self
			grid[w][l].vector[i]=1;
			//top
			if(w>0) 
				grid[w-1][l].vector[i]=1;
			//bottom
			if(w<WIDTH-1) 
				grid[w+1][l].vector[i]=1;
			//left
			if(l>0) 
				grid[w][l-1].vector[i]=1;
			//right
			if(l<LENGTH-1) 
				grid[w][l+1].vector[i]=1;
		}

	}

	//计算任何两个网格点间的分辨误差，取最大的值
	max=0;
	for(i=0; i<WIDTH*LENGTH; i++){
		for(j=i; j<WIDTH*LENGTH; j++){
			distance=0;
			//计算两个网格点检测向量的海明距离
			for(k=0; k<WIDTH*LENGTH; k++){
				distance+=(  ( (*(grid_t+i)).vector[k]) ^ ( (*(grid_t+j)).vector[k])  );
			}
			//cout<<"i="<<i<<", j="<<j<<", dis="<<distance<<endl;
			//计算评价函数值
			int x1,y1,x2,y2;
			y1=i/LENGTH;
			x1=i-y1*LENGTH;
			y2=j/LENGTH;
			x2=j-y2*LENGTH;
			double dis=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
			tmp=dis/(1+K*distance);
			if(tmp>max){
				max=tmp;
				//cout<<"up ("<<x1<<","<<y1<<") <-> ("<<x2<<","<<y2<<")  dis="<<dis<<"  max="<<max<<endl;

			}
		}
	}
	//cout<<max<<endl;
	ind.Val=max;

	return ind.Val;
}

/*
//计算个体评价函数值，达到网格点的最大覆盖
double MyDeploy::EvalVal(INDIVIDUAL &ind)
{
	const char *sensor=ind.Chrom.GetGeneStr();
	int length=ind.Chrom.GetLen();
	int w,l; //行和列
	double max,tmp;
	int i,j,k,distance;

	DETECT_VECTOR *grid_t=(DETECT_VECTOR*)grid;

	//初始化网格点向量
	for(i=0; i<WIDTH*LENGTH; i++){
		memset(grid_t+i,0,WIDTH*LENGTH);
	}

	//根据节点部署，计算每个网格点的覆盖情况
	for(i=0; i<length; i++){
		if(sensor[i]=='1'){	//此网格点有传感器
			w=i/LENGTH;		//行号
			l=i-w*LENGTH;	//列号
			//能覆盖到的网格点
			//self
			grid[0][0].vector[i]=1;
			//top
			if(w>0) 
				grid[0][0].vector[i-LENGTH]=1;
			//bottom
			if(w<WIDTH-1) 
				grid[0][0].vector[i+LENGTH]=1;
			//left
			if(l>0) 
				grid[0][0].vector[i-1]=1;
			//right
			if(l<LENGTH-1) 
				grid[0][0].vector[i+1]=1;
		}

	}
	
	max=0;
	for(i=0; i<WIDTH*LENGTH; i++){
		max+=grid[0][0].vector[i];
	}

	//cout<<max<<endl;
	ind.Val=WIDTH*LENGTH-max;

	return ind.Val;
}
*/