sa.cpp

蚁群算法解决车辆最优路径问题

// Sa.cpp: implementation of the Sa class.
//
//////////////////////////////////////////////////////////////////////

#include "Sa.h"
#include <math.h>
#include <time.h>
#include <stdlib.h>

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

Sa::Sa(int subDim)
{
	dim = subDim;
	x=new int [dim];
	xBest=new int [dim];
	t=new int [dim];

	times=0;
	bestTime=0;
}

Sa::~Sa()
{
	delete []x;
	x = NULL;
	delete []xBest;
	xBest = NULL;
	delete []t;
	t = NULL;

}

void Sa::Exchange(int m)
{
    //师兄说的方法，代内也要循环！
	int temp;
	for(int exchange_time=0; exchange_time<dim; exchange_time++)
		t[exchange_time]=x[exchange_time];

		temp=t[m];
		t[m]=t[m+1];
		t[m+1]=temp;

		fitnessNew = CalFit_sa(t);
}

extern double T;

void Sa::Evaluate()
{
	//决定到底采取还是不采取;
	double Fit_diff;
	Fit_diff=fitnessNew-fitness;
	
	double rate=exp(-Fit_diff/T); 
	//rate是什么东东？
	double r;
	r=rand()/double(RAND_MAX);

	if(Fit_diff<0||r<rate)
	{
		int copy_time;
		for(copy_time=0; copy_time<dim; copy_time++)
			x[copy_time]=t[copy_time];
	    fitness=fitnessNew;

		//更新最优值；
		if (fitness < fitnessBest)
		{
			for(copy_time=0; copy_time<dim; copy_time++)
				xBest[copy_time] = x[copy_time];
			fitnessBest = fitness;
			bestTime = times;
		}
	}
}

double Sa::CalFit_sa(int *order)
{
	double distance_chart[9][9] = {{0,4,6,7.5,9,20,10,16,8},
									{4,0,6.5,4,10,5,7.5,11,10},
									{6,6.5,0,7.5,10,10,7.5,7.5,7.5},
									{7.5,4,7.5,0,10,5,9,9,15},
									{9,10,10,10,0,10,7.5,7.5,10},
									{20,5,10,5,10,0,7,9,7.5},
									{10,7.5,7.5,9,7.5,7,0,7,10},
									{16,11,7.5,9,7.5,9,7,0,10},
									{8,10,7.5,15,10,7.5,10,10,0}};//0~8,9个点，0位发货点

	double f6 = 0;

	f6 = f6 + distance_chart[0][order[0]];//从原点出发

	for(int s=1; s<dim; s++)//dim是sa的数据成员
	{
        f6 = f6 +distance_chart[order[s]][order[s-1]];//由于distance_chart是0~8,所以原来order[s]-1,order[s-1]-1就不用-1了 	
	}

	f6 = f6 + distance_chart[order[dim-1]][0];
	return f6;//f6最后存储的是某条走完dim个城市回发货点的目标函数值(环状)
}