“模拟退火”算法是源于对热力学中退火过程的模拟，在某一给定初温下，通过缓慢下降温度参数，使算法能够在多项式时间内给出一个近似最优解。退火与冶金学上的‘退火’相似，而与冶金学的淬火有很大区别，前者是温度缓慢下降，后者是温度迅速下降。
“模拟退火”的原理也和金属退火的原理近似：我们将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。
你真幸福。我刚刚编了一个模拟退火算法，计算旅行商问题：注意：一共三个文件，第一个是主程序，下面两个是子函数。% for d=1:50 %循环10次发现最小路径为4.115，循环50次有3次出现4.115
T_max=80 %input('please input the start temprature')
T_min=0.001 %input('please input the end temprature')
iter_max=100%input('please input the most interp steps on the fit temp')
s_max=100 %input('please input the most steady steps ont the fit temp')
T=T_max
load .\address.txt
order1=randperm(size(address,1))'%生成初始解。
figure(1)
plot(address(order1,1),address(order1,2),'*r-')
title('随机产生的路径')
totaldis1=distance(address,order1)
for n=1:size(address,1)
text(address(n,1)+0.01,address(n,2),num2str(n))%标号
end
text(0.9,0.9,num2str(totaldis1))
figure(2)
while T>=T_min
iter_num=1
s_num=1
plot(T,totaldis1,'r.')
hold on
while iter_num<iter_max&s_num<s_max
order2=exhgpath(order1) %随机交换两个城市位置
totaldis2=distance(address,order2)
R=rand
DeltaDis=totaldis2-totaldis1 %新的距离-原来的距离
if DeltaDis<0
order1=order2
totaldis1=totaldis2 %新距离小，无条件接受
elseif (exp((totaldis1-totaldis2)/(T))>R)%%%%本算法最核心的思想：以一定概率接受坏的结果，防止局部最优
order1=order2
totaldis1=totaldis2
else s_num=s_num+1
end
iter_num=iter_num+1
end
T=T*0.99
end
set(gca,'xscale','log')%或者使用semilogx，有相同效果
xlabel('退火温度')ylabel('总距离')
order1
totaldis1
figure(3)
plot(address(order1,1),address(order1,2),'*b-')
title('最终路径')
for n=1:size(address,1)
text(address(n,1)+0.01,address(n,2),num2str(n))%标号
end
text(0.9,0.9,num2str(totaldis1))
dstc(d)=totaldis1
% end
——————————————————————————————
function y=exhgpath(order)
while 1
b=size(order,1)
r=unidrnd(b,1,2)
if r(1)-r(2)~=0
break
end
end
b=order(r(2))
order(r(2))=order(r(1))
order(r(1))=b
y=order
------------------------------------------------------------
function y=distance(address,order)
nmb=size(address,1)
y=0
for i=1:nmb-1
y=y+sqrt((address(order(i+1),1)-address(order(i),1))^2+(address(order(i+1),2)-address(order(i),2))^2)
end
y=y+sqrt((address(order(i+1),1)-address(order(1),1))^2+(address(order(i+1),2)-address(order(1),2))^2)
遗传算法求解f(x)=xcosx+2的最大值其中在尺度变换部分应用到了类似模拟退火算法部分，所有变量均使用汉语拼音很好懂
//中国电子科技集团公司
//第一研究室
//呼文韬
//hu_hu605@163.com
//随机初始种群
//编码方式为格雷码
//选择方法为随机遍历
//采用了精英保存策略
//采用了自适应的交叉率和变异率
//采用了与模拟退火算法相结合的尺度变换
//采用了均匀交叉法
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <iostream.h>
#include <iomanip.h>
#include <time.h>
#include <windows.h>
#define IM1 2147483563
#define IM2 2147483399
#define AM (1.0/IM1)
#define IMM1 (IM1-1)
#define IA1 40014
#define IA2 40692
#define IQ1 53668
#define IQ2 52774
#define IR1 12211
#define IR2 3791
#define NTAB 32
#define NDIV (1+IMM1/NTAB)
#define EPS 1.2e-7
#define RNMX (1.0-EPS)
#define zhizhenjuli 0.005
#define PI 3.14159265358
#define T0 100000//温度要取得很高才行。
#define zhongqunshu1 200
#define zuobianjie -2000
#define youbianjie 2000
unsigned int seed=0//seed 为种子，要设为全局变量
void mysrand(long int i) //初始化种子
{
seed = -i
}
long a[1]
//double hundun
//double c=4
//设置全局变量
struct individual
{
unsigned *chrom//染色体；
double geti//变量值
double shiyingdu//目标函数的值；
double fitness//变换后的适应度值；
}
individual *zuiyougeti//精英保存策略
int zhongqunshu//种群大小
individual *nowpop//当前代
individual *newpop//新一代
double sumfitness//当代的总适应度fitness
double sumshiyingdu//当代的总适应度shiyingdu
double maxfitness//最大适应度
double avefitness//平均适应度
double maxshiyingdu//最大适应度
double avgshiyingdu//平均适应度
float pc//交叉概率
float pm//变异概率
int lchrom//染色体长度
int maxgen//最大遗传代数
int gen//遗传代数
//函数
int flipc(double ,double )//判断是否交叉
int flipm(double )//判断是否变异
int rnd(int low,int high)//产生low与high之间的任意数
void initialize()//遗传算法初始化
void preselectfitness()//计算sumfiness,avefitness,maxfitness
void generation()
double suijibianli()//产生随机遍历指针
int fuzhi(float )//选择要复制的个体
void crossover(individual ,individual ,individual &,individual &)//交叉
void bianyi(individual &)//变异
void mubiaohanshu(individual &)//计算适应度
void chidubianhuan(individual &)//对shiyingdu进行尺度变换赋给fitness
double ran1(long *)//随机数初始
void bianma(double bianliang,unsigned *p)//编码
double yima(unsigned *p)
void guanjiancanshujisuan()//计算shiyingdu,根据shiyingdu计算sumshiyingdu,对shiyingdu进行尺度变换变成fitness,根据fitness计算sumfitness，avefitness，maxfitness
void jingyingbaoliu()
void glp(int n,int s,int *,int (*)[1],float (*)[1])//glp生成函数
BOOL Exist(int Val, int Num, int *Array)//判断一个数在前面是否出现过
int cmpfitness(const void *p1,const void *p2)
{
float i=((individual *)p1)->shiyingdu//现在是按照"适应度"排序，改成"个体"的话就是按照"个体"排序
float j=((individual *)p2)->shiyingdu
return i<j ? -1:(i==j ? 0:1)//现在是按升序牌排列，将1和-1互换后就是按降序排列
}
void main()
{
initialize()
cout<<zuiyougeti->geti<<" "<<zuiyougeti->shiyingdu<<endl/////////////
for(gen=1gen<maxgengen++)
{ generation()
}
jingyingbaoliu()
cout<<setiosflags(ios::fixed)<<setprecision(6)<<zuiyougeti->geti<<" "<<setiosflags(ios::fixed)<<setprecision(6)<<(zuiyougeti->shiyingdu)<<endl////////////////
delete [] newpop
delete [] nowpop
delete [] zuiyougeti
system("pause")
}
void initialize()
{
int q[zhongqunshu1][1],s=1
float xx[zhongqunshu1][1]//生成的glp用x储存
int h[1]={1}//生成向量
zuiyougeti=new individual//最优个体的生成
zhongqunshu=200//种群数量
nowpop=new individual[zhongqunshu1]//当代
newpop=new individual[zhongqunshu1]//新一代
maxgen=150//最大代数
gen=0//起始代
lchrom=22//基因数量的初始化
mysrand(time(0))//随机数种子
a[0]=seed//随机数种子
//对最优个体的初始化
zuiyougeti->geti=0
zuiyougeti->fitness=0
zuiyougeti->shiyingdu=0
//
glp(zhongqunshu,s,h,q,xx)
//for(int i=0i<zhongqunshu1i++)//产生初始种群
//{
// for(int j=0j<sj++)
// {
// nowpop[i].geti=zuobianjie+(youbianjie-zuobianjie)*xx[i][j]
// }
//}
for(int i=0i<zhongqunshu1i++)//产生初始种群
{
nowpop[i].geti=zuobianjie+(youbianjie-(zuobianjie))*ran1(a)
}
//nowpop[0].geti=999//////////////////////////
guanjiancanshujisuan()
jingyingbaoliu()//精英保留的实现
guanjiancanshujisuan()//计算shiyingdu,根据shiyingdu计算sumshiyingdu,对shiyingdu进行尺度变换变成fitness,根据fitness计算sumfitness，avefitness，maxfitness
}
void jingyingbaoliu() //精英保留的实现
{
individual *zuiyougetiguodu
zuiyougetiguodu=new individual[zhongqunshu1]//建立一个过渡数组
for(int i=0i<zhongqunshui++)//将当代个体复制到过渡数组中
zuiyougetiguodu[i]=nowpop[i]
qsort(zuiyougetiguodu,zhongqunshu1,sizeof(individual),&cmpfitness)//按fitness升序排序
// cout<<"zuiyougetiguodu适应度:"<<zuiyougetiguodu[zhongqunshu1-1].shiyingdu<<endl///////////
// cout<<"zuiyougeti适应度:"<<zuiyougeti->shiyingdu<<endl///////////////////
//system("pause")
if(zuiyougetiguodu[zhongqunshu-1].shiyingdu>zuiyougeti->shiyingdu)
{
*zuiyougeti=zuiyougetiguodu[zhongqunshu1-1]//如果最优个体的fitness比当代最大的fitness小则用当代的代替之
//cout<<"zuiyougetiguodu个体:"<<zuiyougetiguodu[zhongqunshu1-1].geti<<endl/////////////
//cout<<"zuiyougeti个体:"<<zuiyougeti->geti<<endl/////////////
}
else
nowpop[rnd(0,(zhongqunshu1-1))]=*zuiyougeti//否则的话从当代中随机挑选一个用最优个体代替之
delete [] zuiyougetiguodu//释放过渡数组
}
void guanjiancanshujisuan()//计算shiyingdu,根据shiyingdu计算sumshiyingdu,对shiyingdu进行尺度变换变成fitness,根据fitness计算sumfitness，avefitness，maxfitness
{
for(int i=0i<zhongqunshui++)//计算shiyingdu
mubiaohanshu(nowpop[i])
for(i=0i<zhongqunshui++)//对shiyingdu进行尺度变换变成fitness
chidubianhuan(nowpop[i])
preselectfitness()//根据fitness计算sumfitness，avefitness，maxfitness
}
void mubiaohanshu(individual &bianliang)//计算shiyingdu
{
bianliang.shiyingdu=(bianliang.geti*cos(bianliang.geti)+2.0)//目标函数
}
void chidubianhuan(individual &bianliang)//对shiyingdu进行尺度变换变成fitness
{
double T//退火温度
T=T0*(pow(0.99,(gen+1-1)))
double sum=0
for(int j=0j<zhongqunshuj++)
sum+=exp(nowpop[j].shiyingdu/T)
bianliang.fitness=exp(bianliang.shiyingdu/T)/sum//算出fitness
}
void preselectfitness()//根据fitness计算sumfitness，avefitness，maxfitness
{
int j
sumfitness=0
for(j=0j<zhongqunshuj++)
sumfitness+=nowpop[j].fitness
individual *guodu
guodu=new individual[zhongqunshu1]
for(j=0j<zhongqunshuj++)
guodu[j]=nowpop[j]
qsort(guodu,zhongqunshu1,sizeof(individual),&cmpfitness)
maxfitness=guodu[zhongqunshu1-1].fitness
avefitness=sumfitness/zhongqunshu1
delete [] guodu
}
void generation()
{
individual fuqin1,fuqin2,*pipeiguodu,*pipeichi
int *peiduishuzu//用来存放产生的随机配对
pipeiguodu=new individual[zhongqunshu1]
pipeichi=new individual[zhongqunshu1]
peiduishuzu=new int[zhongqunshu1]
int member1,member2,j=0,fuzhijishu=0,i=0,temp=0,tt=0
float zhizhen
//随机遍历的实现
for(zhizhen=suijibianli()zhizhen<1(zhizhen=zhizhen+zhizhenjuli))//设定指针1/66
{
pipeichi[fuzhijishu]=nowpop[fuzhi(zhizhen)]
fuzhijishu++
}
//交叉与变异的实现
//交叉
for(i=0i<zhongqunshu1i++)
{
peiduishuzu[i]=-1
}
for (i=0i<zhongqunshu1i++)
{
temp =rnd(0,zhongqunshu1-1)//产生值在0-zhongqunshu1-1的随机数
while(Exist(temp, i, peiduishuzu))//判断产生的随机数是否已经产生过，如果是，则再产生一个随机数
{
temp =rnd(0,zhongqunshu1-1)
}
//如果没有的话，则把产生的随机数放在peiduishuzu中
*(peiduishuzu+i) = temp
}
for(i=0i<zhongqunshu1-1i=i+2)
{
fuqin1=pipeichi[peiduishuzu[i]]
fuqin2=pipeichi[peiduishuzu[i+1]]
crossover(fuqin1,fuqin2,newpop[i],newpop[i+1])
}
for(j=0j<zhongqunshu1j++)
{
//if(newpop[j].geti<-1000)
//cout<<"个体数值小于下界了"
nowpop[j].geti=newpop[j].geti
}
//
guanjiancanshujisuan()
//变异的实现
for(j=0j<zhongqunshuj++)
{
bianyi(nowpop[j])
}
//
guanjiancanshujisuan()
//精英保留的实现
jingyingbaoliu()
//
guanjiancanshujisuan()
delete [] peiduishuzu
delete [] pipeichi
delete [] pipeiguodu
}
void crossover(individual parent1,individual parent2,individual &child1,individual &child2)//交叉
{
int j
unsigned *panduan
panduan=new unsigned[lchrom]
parent1.chrom=new unsigned[lchrom]
parent2.chrom=new unsigned[lchrom]
child1.chrom=new unsigned[lchrom]
child2.chrom=new unsigned[lchrom]
//cout<<"jiaocha"<<endl///////////////////////
bianma(parent1.geti,parent1.chrom)
bianma(parent2.geti,parent2.chrom)
if(flipc(parent1.fitness,parent2.fitness))
{
for(j=0j<lchromj++)
panduan[j]=rnd(0,1)
//for(j=0j<lchromj++)////////////////
// {
// cout<<panduan[j]/////////////
// }
// cout<<endl////////////////
// system("pause")////////////////
for(j=0j<lchromj++)
{
if(panduan[j]==1)
child1.chrom[j]=parent1.chrom[j]
else
child1.chrom[j]=parent2.chrom[j]
}
for(j=0j<lchromj++)
{
if(panduan[j]==0)
child2.chrom[j]=parent1.chrom[j]
else
child2.chrom[j]=parent2.chrom[j]
}
//for(j=0j<lchromj++)////////////////
//{
// cout<<child1.chrom[j]/////////////
// }
//cout<<endl////////////////
// system("pause")////////////////
child1.geti=yima(child1.chrom)
child2.geti=yima(child2.chrom)
delete [] child2.chrom
delete [] child1.chrom
delete [] parent2.chrom
delete [] parent1.chrom
delete [] panduan
}
else
{
for(j=0j<lchromj++)
{
child1.chrom[j]=parent1.chrom[j]
child2.chrom[j]=parent2.chrom[j]
}
child1.geti=yima(child1.chrom)
child2.geti=yima(child2.chrom)
delete [] child2.chrom
delete [] child1.chrom
delete [] parent2.chrom
delete [] parent1.chrom
delete [] panduan
}
}
void bianyi(individual &child)//变异
{
child.chrom=new unsigned[lchrom]
//cout<<"变异"<<endl
bianma(child.geti,child.chrom)
for(int i=0i<lchromi++)
if(flipm(child.fitness))
{
if(child.chrom[i]=0)
child.chrom[i]=1
else
child.chrom[i]=0
}
child.geti=yima(child.chrom)
delete [] child.chrom
}
void bianma(double bianliang,unsigned *p)//编码
{
unsigned *q
unsigned *gray
q=new unsigned[lchrom]
gray=new unsigned[lchrom]
int x=0
int i=0,j=0
if(bianliang<zuobianjie)///////////////////
{
cout<<"bianliang:"<<bianliang<<endl/////////
system("pause")
}
//cout<<youbianjie-(zuobianjie)<<endl
//system("pause")
x=(bianliang-(zuobianjie))*((pow(2,lchrom)-1)/(youbianjie-(zuobianjie)))
//cout<<x<<endl///////////
if(x<0)
system("pause")///////////
for(i=0i<lchromi++)
{
q[i]=0
p[i]=0
}
i=0
while (x!=0&&(i!=lchrom))
{
q[i]=(unsigned)(x%2)
x=x/2
i++
}
// for(i=0i<lchromi++)//////////////////
// cout<<q[i]///////////////
// cout<<endl///////////
int w=lchrom-1
if(q[w]!=0&&q[w]!=1)
system("pause")
for(j=0j<lchrom&&w>0j++)
{
p[j]=q[w]
w--
}
//cout<<"yuanma"<<endl
//for(j=0j<lchromj++)///////////
// cout<<p[j]////////
//cout<<endl////////////////////
gray[0]=p[0]
for(j=1j<lchromj++)
{
if(p[j-1]==p[j])
gray[j]=0
else if(p[j-1]!=p[j])
gray[j]=1
}
for(j=0j<lchromj++)
p[j]=gray[j]
//cout<<"geleima"<<endl
//for(j=0j<lchromj++)///////////
// cout<<p[j]////////
//cout<<endl////////////////////
//system("pause")///////////
delete [] gray
delete [] q
}
double yima(unsigned *p) //译码
{
int i=0
// for(i=0i<lchromi++)/////////
// {
// cout<<p[i]//////
// }
// cout<<endl/////////
// system("pause")//////////
int x=0
unsigned *q
q=new unsigned[lchrom]
q[0]=p[0]
// cout<<q[0]<<endl//////////////////
// system("pause")//////////
for(int j=1j<lchromj++)
{
if(q[j-1]==p[j])
q[j]=0
else if(q[j-1]!=p[j])
q[j]=1
}
// for(i=0i<lchromi++)//////
// {
// cout<<q[i]//////////
// if(q[i]!=0&&q[i]!=1)
// {
// cout<<q[i]
// system("pause")
// }
// }
// cout<<endl////////
// system("pause")///////////////////
for(i=0i<lchromi++)
x=x+q[i]*pow(2,(lchrom-i-1))
if(x<0)
{
cout<<"译码出错1"<<endl
system("pause")
}
//cout<<"x:"<<x<<endl
double bianliang
//cout<<pow(2,22)<<endl
//cout<<2000*x<<endl
//cout<<(x*(2000/(pow(2,22)-1)))<<endl
bianliang=(x*((youbianjie-(zuobianjie))/(pow(2,lchrom)-1)))+zuobianjie
if(bianliang<zuobianjie)
{
cout<<"译码出错2"<<endl
system("pause")
}
delete [] q
return bianliang
}
double ran1(long *idum)
{
int j
long k
static long idum2=123456789
static long iy=0
static long iv[NTAB]
float temp
if (*idum <= 0)
{
if (-(*idum) <1) *idum=1
else *idum = -(*idum)
idum2=(*idum)
for (j=NTAB+7j>=0j--)
{
k=(*idum)/IQ1
*idum=IA1*(*idum-k*IQ1)-k*IR1
if (*idum <0) *idum += IM1
if (j <NTAB) iv[j] = *idum
}
iy=iv[0]
}
k=(*idum)/IQ1
*idum=IA1*(*idum-k*IQ1)-k*IR1
if (*idum <0) *idum += IM1
k=idum2/IQ2
idum2=IA2*(idum2-k*IQ2)-k*IR2
if (idum2 <0) idum2 += IM2
j=iy/NDIV
iy=iv[j]-idum2
iv[j] = *idum
if (iy <1) iy += IMM1
if ((temp=AM*iy) >RNMX) return RNMX
else return temp
}
double suijibianli()//随机遍历
{
double i=ran1(a)
while(i>zhizhenjuli)
{
i=ran1(a)
}
//cout<<i<<endl//////////////
return i
}
int fuzhi(float p)//复制
{
int i
double sum=0
if(sumfitness!=0)
{
for(i=0(sum<p)&&(i<zhongqunshu)i++)
sum+=nowpop[i].fitness/sumfitness
}
else
i=rnd(1,zhongqunshu1)
return(i-1)
}
int rnd(int low, int high) /*在整数low和high之间产生一个随机整数*/
{
int i
if(low >= high)
i = low
else
{
i =(int)((ran1(a) * (high - low + 1)) + low)
if(i >high) i = high
}
return(i)
}
int flipc(double p,double q)//判断是否交叉
{
double pc1=0.9,pc2=0.6
if((p-q)>0)
{
if(p>=avefitness)
{
pc=pc1-(pc1-pc2)*(p-avefitness)/(maxfitness-avefitness)
}
else
pc=pc1
}
else
{
if(q>=avefitness)
{
pc=pc1-(pc1-pc2)*(q-avefitness)/(maxfitness-avefitness)
}
else
pc=pc1
}
if(ran1(a)<=pc)
return(1)
else
return(0)
}
int flipm(double p)//判断是否变异
{
double pm1=0.001,pm2=0.0001
if(p>=avefitness)
{
pm=(pm1-(pm1-pm2)*(maxfitness-p)/(maxfitness-avefitness))
}
else
pm=pm1
if(ran1(a)<=pm)
return(1)
else
return(0)
}
void glp(int n,int s,int *h,int (*q)[1],float (*xx)[1])//glp
{
int i=0,j=0
//求解q
for(i=0i<ni++)
{
for(j=0j<sj++)
{
*(*(q+i)+j)=((i+1)*(*(h+j)))%n
}
}
i=n-1
for(j=0j<sj++)
{
*(*(q+i)+j)=n
}
//求解x
for(i=0i<ni++)
{
for(j=0j<sj++)
{
*(*(xx+i)+j)=(float)(2*(*(*(q+i)+j))-1)/(2*n)
}
}
}
BOOL Exist(int Val, int Num, int *Array)//判断一个数是否在一个数组的前Num个数中
{
BOOL FLAG = FALSE
int i
for (i=0i<Numi++)
if (Val == *(Array + i))
{
FLAG = TRUE
break
}
return FLAG
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）