group.cpp

用遗传算法求解TSP问题

#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include "group.h"

using namespace std;

Group::Group()
{
	int i,j;
	for (i=0;i<100;i++)
	{
		for (j=0;j<10;j++)
		{
			sequence[i][j]=0;
			roadline[i][j]=0;
		}
	}
	for (i=0;i<10;i++)
	{
		road[i]=i+1;
		temp[i]=0;
	}
	for (i=0;i<10;i++)
	{
		for (j=0;j<10;j++)
		{
			distance[i][j]=0;
		}
	}
	cross_possibility=0.7;
	mutation_possibility=0.005;
}

void Group::get_distance()
{
	int i,j;
	double cood[10][2];
	for (i=0;i<10;i++)
	{
		cood[i][0]=(rand()%100)/100.0;
		cood[i][1]=(rand()%100)/100.0;
	}
	for (i=0;i<10;i++)
	{
		for (j=i;j<10;j++)
		{

			double distancesqu;
			distancesqu=(cood[i][0]-cood[j][0])*(cood[i][0]-cood[j][0])+(cood[i][1]-cood[j][1])*(cood[i][1]-cood[j][1]);
			distance[i][j]=sqrt(distancesqu);
			distance[j][i]=distance[i][j];
		}
	}
}

void Group::initial()
{
	int i,j,k;
	for (i=0;i<100;i++)
	{
		for (j=0;j<10;j++)
		{
			k=(rand()%(10-j))+1;
			sequence[i][j]=k;
		}
	}
}

void Group::get_temp()
{
	int i;
	for (i=0;i<10;i++)
	{
		temp[i]=road[i];
	}
}

void Group::code_to_road()
{
	int i,j,k,number=0,h=0;	
	for (i=0;i<100;i++)
	{
		get_temp();
		for (j=0;j<10;j++)
		{
			number=0;
			h=0;
			do 
			{
				
				if (!(temp[h]==0))
				{
					number++;
				}
				if (number==sequence[i][j])
				{
					k=temp[h];
					temp[h]=0;
				}
				h++;
			} while (number<sequence[i][j]);
			roadline[i][j]=k;
		}
	}
}

void Group::get_roadlinedis()
{
	int i,j,up;
	for (i=0;i<100;i++)
	{
		for (j=0;j<10;j++)
		{
			up=j+1;
			if (j==9)
			{
				up=0;	
			}
			roadlinedis[i]=roadlinedis[i]+distance[j][up];
		}
	}
}

void Group::get_fitness()
{
	int i;
	for (i=0;i<100;i++)
	{
		roadlinedis[i]=10.0/roadlinedis[i];
	}
}


void Group::get_choose_result()
{
	int i,j,k;
	int choose_result[100][10];
	double getsum;
	double percentage[100];

	//srand((unsigned)time(NULL));
	getsum=get_the_sum();
	for (i=0;i<100;i++)
	{
		percentage[i]=roadlinedis[i]/getsum;
	}
	for (i=0;i<100;i++)
	{
		double random;
		random=(rand()%10000)/10000.0;
		j=0;
		do
		{			
			random=random-percentage[j];
			if (random<0)
			{
				for (k=0;k<10;k++)
				{
					choose_result[i][k]=sequence[j][k];
				}
			}
			j=j+1;
		}while (random>0);
	}
	for (i=0;i<100;i++)
	{
		for (j=0;j<10;j++)
		{
			sequence[i][j]=choose_result[i][j];
		}
	}
}

double Group::get_the_sum()
{
	int i;
	double sum=0;
	for (i=0;i<100;i++)
	{
		sum=sum+roadlinedis[i];
	}
	return sum;
}

void Group::get_cross_result()
{
	int i,j;
	double choose;
	int place,tem[10];
	//srand((unsigned)time(NULL));
	for (i=0;i<100;i=i+2)
	{
		choose=(rand()%10000/10000.0);
		if (choose<=cross_possibility)
		{
			place=rand()%10;
			for (j=place+1;j<10;j++)
			{
				tem[j]=sequence[i][j];
				sequence[i][j]=sequence[i+1][j];
				sequence[i+1][j]=tem[j];
			}
		}
	}
}

void Group::get_mutation_result()
{

	int i,tem;
	double choose;
	//srand((unsigned)time(NULL));
	for (i=0;i<100;i++)
	{
		choose=(rand()%10000/10000.0);
		if (choose<=mutation_possibility)
		{
			int place1,place2;
			place1=rand()%10;
			place2=rand()%10;
			tem=roadline[i][place1];
			roadline[i][place1]=roadline[i][place2];
			roadline[i][place2]=tem;
		}
	}
}

double Group::get_the_average()
{
	int i;
	double sum=0;
	for (i=0;i<100;i++)
	{
		sum=sum+roadlinedis[i];
	}
	return sum/100.0;
}

void Group::output()
{
	int i,j;
	for (i=0;i<100;i++)
	{
		for (j=0;j<10;j++)
		{
			cout<<roadline[i][j]<<"  ";
		}
		cout<<"   "<<roadlinedis[i]<<endl;
	}
	cout<<"the average is  : "<<get_the_average()<<endl;
}