sa.cpp

用C语言写的人工智能算法中的模拟退火算法

#include "datastruct.h"
#include "sa.h"
#include "headfile.h"

//子函数
//1.起始温度的选择
double inition_tempreture(city_list M)
{
	int i=2;
	int j=3;
	double t;
	double tempreture;
	city_list L;
	int count=0;
	double tempreture_min=999999;
	double tempreture_max=-999999;
	count=count_list(M);
	while(i<count)
	{
		j=i+1;
		while(j<=count)
		{
			L=create_neirghborList(M,i,j);
			tempreture=sum_distance(L);
			if(tempreture>tempreture_max)  tempreture_max=tempreture;
			if(tempreture<tempreture_min)  tempreture_min=tempreture;
			j++;
		}
		i++;
	}
	tempreture=tempreture_max-tempreture_min;
	cout<<"最大的温度: "<<tempreture_max<<endl;
	cout<<"最小的温度: "<<tempreture_min<<endl;
	t=K*tempreture;
	return t;
}
//2.求距离之和
double distance(city_list M,city_list N)//每个解的距离之和
{
	double total=0;
	double x;
	x=(M->x-N->x)*(M->x-N->x)+(M->y-N->y)*(M->y-N->y);
	total=sqrt(x);    
	return total;
}
//3.产生新的领域解
city_list create_neirghborList(city_list M,int num1,int num2)
{
	int i=1;
	int j=1;
    city_list p,p1,p2,p2_pre,p1_pre,pp1,pp2;
    
	if(M==NULL) return NULL;
	if(num1==1)
	{
		cout<<"随即产生数错误(fei 1)"<<endl;
		return  NULL;
	}
	
	p=copy(M);
	p1=p2=p;
	
	while(i<num1)//第一个随机产生的数的指针位置
	{
		i++;
		p1=p1->next;
		
	}
	
	while(j<num2)//第二个随机产生数的指针位置
	{
		j++;
		p2=p2->next;
	}
    
	p1_pre=pp1=p;  //找第一个的前一个位置
	while(pp1->next!=p1)
		pp1=pp1->next;
	p1_pre=pp1;
	
    p2_pre=pp2=p;  //找第二个的前一个位置
	while(pp2->next!=p2)
		pp2=pp2->next;
	p2_pre=pp2;

	if(p1->next==p2)
	{
		p1->next=p2->next;
		p2->next=NULL;
		p2->next=p1;
		p1_pre->next=p2;
	}
	else
	{
		p1_pre->next=p1->next;//断p1
		p1->next=NULL;
		p1->next=p2->next;//接p1
		p2->next=p1;
		p2_pre->next=p1;//断 p2
		p2->next=NULL;
		p2->next=p1_pre->next;//接p2
		p1_pre->next=p2;
	}
	return p;
}

//4.随机产生
int  create_num()
{
	int x=0;
	do
	{
		srand( (unsigned)time(NULL) );     //srand()函数产生一个以当前时间开始的随机种子
	    x=(rand()%100)%LEN;
	}while(x==0||x==1);
	return x;
}

//5.求一个解的总的距离之和
double sum_distance(city_list L)
{
	double sum=0;
	city_list p,p_pre;
	if(L==NULL) return NULL;
	p=L->next;
	p_pre=L;
	while(p!=NULL)
	{
		sum=sum+distance(p_pre,p);
		p_pre=p;
		p=p->next;
	}
	return sum;
}

//6.SA算法
void SA(city_list L,city_list &Q)
{
	double tempreture=0;
	int count=20;
	int num1,num2,temp;
	city_list  cur_city_list,new_city_list;
	int x;
	int flag=0;
	cur_city_list=L;
	tempreture=inition_tempreture(cur_city_list);//初始温度
	cout<<"初始温度:"<<tempreture<<endl;
	int NUM1=0;
	
	do
	{
		count=50;
		while(count>0)
		{
			NUM1++;
			count--;
			do
			{
				num1=create_num();
				num2=create_num();
				if(num2>num1) 
				{
					temp=num1;
					num1=num2;
					num2=temp;
				}
			}while(num1==num2);
			
			new_city_list=create_neirghborList(cur_city_list,num1,num2);
			x=test_Metropolis(tempreture,cur_city_list,new_city_list);
			if(x==1) 
			{
				flag=0;
			    cur_city_list=new_city_list;
			}
			else
			{
				flag=1;
				free(new_city_list);
				break;
			}
			if(sum_distance(cur_city_list)<sum_distance(Q))
			{
				free(Q);
				Q=copy(cur_city_list);
				cout<<"找到最优解的迭代次数:"<<NUM1<<endl;
				cout<<"最优解:"<<sum_distance(Q)<<endl;
			}

		}

		cout<<"温度:"<<tempreture<<endl;
		if((flag==1)&&(count==0))  break;
		if(tempreture<0.001)  break;
		tempreture=tempreture*0.95;			
	}while(1);

	cout<<"总循环次数："<<NUM1<<endl;
	
	print(Q);
}

//7.接受准则
int test_Metropolis(double tempreture,city_list cur_city_list,city_list new_city_list)
{
	double n_new_city_list,n_cur_city_list;
	double left,right;
	int x;
	n_new_city_list=sum_distance(new_city_list);
	n_cur_city_list=sum_distance(cur_city_list);
	if(n_new_city_list<n_cur_city_list)
		x=1;
	else
	{
		left=exp(-((double)(n_new_city_list-n_cur_city_list)/tempreture));
		right=0.0;
		while(right==0.0||right==1.0)
		{
			srand( (unsigned)time(NULL) );     //srand()函数产生一个以当前时间开始的随机种子
			right=(double)(rand()%100)/100.0;		
		}
		if(left>right) x=1;
		else
			x=0;
	}
	return x;
}

//计算链表的长度
int count_list(city_list L)
{
	int i=0;
	city_list p;
	p=L;
	while(p!=NULL)
	{
		i++;
		p=p->next;
	}
	return i;
}
//copy函数
city_list copy(city_list L)
{
	city_list p,q,new_node,M;
	p=L;
    if(p!=NULL)
	{
		new_node=(city_list)malloc(sizeof(city));
		new_node->x=p->x;
		new_node->y=p->y;
		new_node->next=NULL;
		M=new_node;
		q=M;
		p=p->next;
	}
	else
		return NULL;

	while(p!=NULL)
	{
		new_node=(city_list)malloc(sizeof(city));
		new_node->x=p->x;
		new_node->y=p->y;
		new_node->next=NULL;
		q->next=new_node;
		q=q->next;
		p=p->next;
	}
	return M;
}
//打印函数
void print(city_list L)
{
	city_list p;
	p=L;
	while(p!=NULL)
	{
		cout<<p->x<<"     "<<p->y<<endl;
		p=p->next;
	}
}