sa.dpr

模拟退火算法求解TSP问题.求解TSP问题的模拟退火算法

program TSPSA(Input,Output);
type
	TIndex=Longint;
	TData=Extended;
const
	CityNum=144;
	{$I data.pas}
	Temperature=300;
	DiminishedRate=0.9;
	MarkovLength=10000;
	Diminish_T_num=20000;
	AIM=100;

procedure GenerateNext(var Path:TPath;x,y:TIndex);
begin
	if x<y then 
		Reverse(Path,x,y-x+1)
	else x>y then
	begin
		Reverse(Path,1,y);
		Reverse(Path,x,High(Path)-x);
	end;
end;
function CalculateTotalDistance(Path:TPath):TData;
var
	i:TIndex;
begin
	Result:=0;
	for i:=1 to CityNum-1 do
		Result:=Result+Distance(Path[i],Path[i+1]);
end;
procedure Anneal;
begin
	InitialPath(CurrentPath);
	CurrentDist:=CalculateTotalDistance(CurrentPath);
	BestPath:=CurrentPath;
	BestDist:=CurrentDist;
	while true do
	begin
		CurrentPath:=BestPath;
		CurrentDist:=BestDist;
		for i:=1 to MarkovLength do
		begin
			repeat
				xCity:=Random(CityNum)+1;
				yCity:=Random(CityNum)+1;
			until xCity<>yCity;
			Distinction:=
			if Distinction<0 then
			begin
				Diminish_Times:=0;
				AIM:=0;
			end
			else if Exp(-Distinction/Temperature)>Random then
			begin
				Inc(Diminish_T_Num);
				GenerateNext(CurrentPath,x,y);
				CurrentDist:=CalculateTotalDistance(CurrentPath);
			end
			else
				Inc(Diminish_T_Num);
			if CurrentDist<BestDist then
			begin
				BestPath:=CurrentPath;
				BestDist:=CurrentDist;
			end;
			if AIM=AIM_Limit then
			begin
				Writeln(BestDist);
				Exit;
			end;
			if diminish_t_num>Diminish_T_num then
			begin
				aim++;
				Break;
			end;
		end;
		Temperature:=Temperature*DiminishedRate;
	end;
end;
begin
	Main;
end.