mnthtsp.cpp

用模拟退火技术解决旅行商问题.算法中采用了人工智能中比较新的模拟退火算法.

// MnthTsp.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <math.h>
#include "string.h"
#include "iostream.h"
#include "fstream.h"
#include "stdlib.h"
#include "time.h"
#include "stdio.h"
#include "stdafx.h"




int t0,L,s;  //初始值
int city[144][144]; //144个城市
int ipath[143];

bool b;
int path[143];
int sum,newsum,df,lminsum,minsum;
double p,t;
//函数

void initialize();
//void initialize_randomize();
void generate();
int calculate(int s1,int s2);
bool accept(double t,int d);
int calculate_newroad();

int length(int c1,int c2);
   


void main(int argc, char* argv[])
{
    initialize();   //初始化i0= π1 …πn, t0=100, L= 20000,s=0 
    t = t0;
    //将过程及结果写入result.txt文件
    fstream result;
    result.open("result.txt",ios::out);
	result<<"当前总路径:"<<sum<<'/n';

    printf("当前总路径:%d",sum);
    printf("\n");
	minsum = sum;
    while (s != 2)   //停止准则为连续两个Mapkob链路径无变化
	{
        b =0;
		lminsum = sum ;
        
        for(int i=1;i <= L;i++) 
		{
            generate();  //采用2变换法产生新的路径
            newsum = calculate_newroad();
           
            df = calculate(newsum,sum);  //计算df= f(j)-f(i) 的值
            if(accept(t, df))//根据Metropolis准则判断是否接受新的路径
			{
				b= 1;
			    sum = newsum; //newsum作为当前路径
				if(df < 0)
					lminsum = newsum;
				
			}
			
		}

		//result<<"当前总路径:"<<lminsum<<'/n';   //将过程及结果写入result.txt文件

		printf("当前温度是：%f,",t);
        printf("此次迭代最小路径是：%d",lminsum);
		printf("\n");
		if(minsum > lminsum)
			minsum = lminsum;
        t=t * 0.9;  //衰减函数α(t)=0.9 * t 
        if (b == 0) s=s+1; 
        else s=0;
	}
    result<<"计算结果总路径:"<<minsum<<';/n'; 
    result.eof(); //result文件结束
	printf("计算结果总路径:%d\n",minsum);
    return ;
}


void initialize()  //初始化i0= π1 …πn, t0=100, L= 20000,s=0 
{
   
   t0 = 100;
   L = 20000;
   s = 0;
   sum = 0;
   fstream cityroads("距离下三角矩阵.txt",ios::in);
   

   char c;
   cityroads.get(c);
   if(c == -1)
   {
	   cityroads.close();

	   cityroads.open("距离下三角矩阵.txt",ios::out);

	   for(int i = 0; i <144; i++)
	   {
		   for(int j = 0; j <=i; j++)
		   {
	          
			   city[i][j] = rand()%1000; 
		       printf("from %d   to %d : %d \n",i,j,city[i][j]);
               
		       cityroads<<city[i][j]<<" ";
		 
		       city[j][i] = city[i][j];
		 
		      
		   }
		   cityroads<<"\n";
	   }
           cityroads.eof();
		   cityroads.close();
   }
   else
   {
	   cityroads.close();
	   cityroads.open("距离下三角矩阵.txt",ios::in);
	 
	   for(int i = 0; i <144; i++)
           for(int j = 0; j <=i; j++)
		   {
			  cityroads>>city[i][j];
              city[j][i] = city[i][j];
			  
		   }
        cityroads.close();
   }

   for(int k = 0; k <143; k++) //计算初始总路径
   {
	   ipath[k] = length(k,k+1);
	   path[k] = ipath[k];
	   sum += path[k];
   }

   
} 

/*void initialize_randomize() //初始化随机数种子
{
	
}*/

void generate() //采用2变换法产生新的路径
{
    int i,j;

	i = rand()%144;
	j = rand()%144;
	while(i == 0 || j == 0)
	{
		i = rand()%144;
		j = rand()%144;
	}
	path[i-1] = length(i-1,j);
	path[j] = length(j,i+1);
	path[j-1] = length(j-1,i);
	path[i] = length(i,j+1);

}

int calculate_newroad() //计算接受的新路径的长
{
	int s = 0;
    for(int k = 0; k <143; k++)
    {
	    s += path[k];
    }
	return s;
}

int length(int c1,int c2) //计算city1到city2的距离
{
    int l;
	l = city[c1][c2];
	return l;
}

int calculate(int s1,int s2)  //计算df= f(j)-f(i) 的值
{
    int d = s1-s2;
	return d;
}

bool accept(double tem,int d) //根据Metropolis准则判断是否接受新的路径
{
	
    if(d < 0)
		return true;
	else 
	{
		p=exp((double)(-d)/tem) ;
        if( p>=(double)rand()/RAND_MAX )
			return true;
		else 
			return false;
	}
}