模拟退火算法

对于退火算法,查了不少资料,大概清楚了基本原理,并带有例题进行讲解

模拟退火算法,是现代优化算法的一种,主要是用于解决组合优化问题,求解出全局最优解,就是求解在众多解中能满足目标函数式的解。

算法基本原理:

大家可以先看一下如下的两个博客

 

1.大白话解析模拟退火算法

2.模拟退火算法

这里他们从爬山算法开始介绍,写出爬山算法的局限性,只能查找到局部最优,然后再拓展到退火算法,引出在进行选择时,可以按照一定概率选择有潜在价值的不是局部最优的选择。另外他们的伪代码中都有一个问题Y(i+1)=Y(i);也就是状态跳转的语句有问题。

3.模拟退火算法中的退火策略研究

这篇论文是讲解退火算法中关于T=T*a也就是a的变化率的探讨,可以让大家更加了解退火算法的含义

 

以飞机侦察目标地最终返回的旅行商问题,退火算法只要分为以下几步

问题描述:我方的一架飞机从基地起飞,要侦察附近区域的100个目标地,并返回到基地,不考虑在目标地上的侦察时间,求解出飞机花费的最少时间,并且确定侦察路线。

1.解空间的确立

在固定起点终点,也就是基地的基础上,确定飞行方案,这里的100!种选择,这也是解空间

2.确立初始解

也就是从哪个点入手,开始进行退火操作,这里可以用蒙特卡洛法确立合适的初始解,关于蒙特卡洛法会在影子技术结束后补充学习

3.构造目标函数

就是表示出侦察路线的总长度

4.迭代

也就是在这是对方案不断进行选择,和对选择方法进行适当修正

4.1 新解产生

就是在当前方案的情况下,进行一些微调整,产生出一个新的解,也就是一个马尔代夫过程,马尔代夫过程是现在这个状态完全依赖于前一个状态,和之前的起始状态,或其他状态无关

4.2  比较这两个方案

作差,或依据做的微调简化处理进行作差

4.3  接受准则

就是做出选择,如果新的方案用时更少,就选择新的方案 如果不是就需要进行潜能的判断,潜能这个词是我自己编的,哈哈,具体的判断方法就是将           exp(-f/T)与[0,1]间的随机数比较大于等于时接受

4.4  降温

因为每一次都是越接近最优值的,所以对于T需要改变进行降温从而更加稳定不会再那么轻易选择那些看不清的潜能了,具体的降温就是将T=a*T,a一般都是在0.95左右

5.结束

迭代的终止条件就是温度降到终止温度了,其最终结果就是为最优解

这就是退火算法的具体步骤。下面有关于这个飞机侦察的这个题目的具体代码,可以参考。还有一篇不错的博客如果还不是很清楚,可以看看   手把手教会你模拟退火算法

 

要想真正灵活的掌握这个算法,还需要多多练习,之后有机会也想真正把握它的精髓。

路线模型的代码
clc,clear
sj0=load('sj.txt');%加载100个目标数据,数据按照表格中的位置保存在纯文本文件sj.txt中‘
x=sj0(:,[1:2:8]);x=x(:);
y=sj0(:,[2:2:8]);y=y(:);
sj=[x y];d1=[70,40];
sj=[d1;sj;d1];sj=sj*pi/180;%角度化成弧度
d=zeros(102);%距离矩阵d初始化
for i=1:101
 for j=i+1:102
 d(i,j)=6370*acos(cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2)));
 end
end
d=d+d';
path=[];longth=inf;%巡航路径及长度初始化
rand('state',sum(clock));

for j=1:1000%求较好的初始解(蒙特卡洛)
 path0=[1 1 + randperm(100),102];temp=0;
 for i =1:101
 temp =temp+d(path0(i),path0(i+1));
 end
 if temp<long
 path=path0;long=temp;
 end
end

e=0.1^30;L=20000;at=0.999;t=1;
for k=1:L%退火过程
 c=2+floor(100*rand(1,2));%产生新解
 c=sort(c);c1=c(1);c2-c(2);
 %计算代价函数值的增量
 df=d(path(c1-1),path(c2))+d(path(c1),path(c2+1))-d(path(c1-1),path(c1))-d(path(c2),path(c2+1));
 if df<0
 %接受准则
 path=[path(1:c1-1),path(c2:-1:c1),path(c2+1:102)];long=long+df;
 elseif exp(-df/T)>=rand
 path=[path(1:c1-1),path(c2:-1:c1),path(c2+1:102)];long=long+df;
 end
 T=T*at;
 if T<e
 break;
 end
end

path,long%long输出巡航路径及路径长度
xx=sj(path,1);yy=sj(path,2);
plot(xx,yy,'-*')%画出巡航路径
模型数据

sj.txt

对于文中存在疑问的,或有什么问题,博主很希望能够相互交流

数模算法

是数模学习的另外一个模块

主要是对论文用到的算法进行详细讲解,主要讲解从算法原理,算法步骤,代码工具,及算法应用这几步。算法应用在建模算法中,是最为关键的部分,如何灵活的应用各类算法是重中之重,这才是算法学习的关键处,之前的原理的讲解就是希望能对算法有深入的理解,从而更加灵活的应用算法,对于算法的应用的主要还是回归论文中,所以这部分内容不会写在这里,会标明是具体的那篇论文。

算法名称                                              涉及论文

1.模拟退火算法                                 2015国赛A题(1)

2.麦夸特算法                                     2015国赛A题(2)

1002 A+B for Polynomials (25)

题目:

https://www.patest.cn/contests/pat-a-practise/1002

大概描述:

就是将多项式A,B相加,其中的数字表示项数,系数及指数,并且对输出也有要求,最后不为空格,且按照指数由大到小排序

使用语言:

C

解题思想:

采用的是将多项式A,B的指数用两个10个单位的数组进行存储,他们的系数都放在一个数组中,这个数组的长度为20,然后依次取出数组中的指数查找他之后的是否具有相同的,有相同的,就把指数变为-1,从而失效,最终得到相加后的指数组和系数组。悲剧就在此时发生,他的结果要求按照指数由大到小输出。于是又将之前的结果进行排序。代码变得复杂了。其实在有了思路后我在网上也搜了,还有其他的思路且更为简便。就是直接构造一个长为最大指数的数组,对号入座,也省去排序的尴尬。

题目得分:

17(待重做)

提交次数:

3

做题时间:

大半天

具体代码如下:

#include<stdio.h>
//悲剧scanf的用法都记不清了

void budlesort (int* a,float* b,int key){
 int i=0;int j=0;int m;float n;
 for(i=0;i<key;i++){
 for(j=key-1;j>i;j--){
 if(a[j-1]<a[j]){
 m=a[j-1];
 a[j-1]=a[j];
 a[j]=m;
 n=b[j-1];
 b[j-1]=b[j];
 b[j]=n;
 }

 }

 }



}
int main(){
 int a[10]={0};
 int b[10]={0};
 float c[20]={0};
 int k1=0;int i=0;int key1=0;int key2=0;int key3=0;
 int k2=0;int j=0;int aa=0;int bb=0; int fin[20]={0};
 scanf("%d",&k1);
 // printf("OOOk\n");
 for(i=0;i<k1;i++){
 scanf("%d",&a[i]);
 scanf("%f",&c[i]);
 // printf("****");
 }
 //printf("*************************************");

 scanf("%d",&k2);
 //printf("OOOk\n");
 for(i=0;i<k2;i++){
 scanf("%d",&b[i]);
 scanf("%f",&c[i+10]);
 //printf("****");
 }
 // printf("*************************************"); printf("\n");
 /* for(i=0;i<k1;i++){
 printf("%d ",a[i]);
 }
 printf("\n");
 for(i=0;i<k2;i++){
 printf("%d ",b[i]);
 } printf("\n");
 for(i=0;i<20;i++){
 printf("%f",c[i]);
 }
*/
 for(i=0;i<k1;i++){
 for(j=i+1;j<k1;j++){
 if(a[i]==a[j]){
 c[i]+=c[j];
 a[j]=-1;
 }
 }
 for(j=0;j<k2;j++){
 if(a[i]==b[j]){
 c[i]+=c[j+10];
 b[j]=-1;
 }
 }
 }
 /* printf("\n");
 for(i=0;i<k1;i++){
 printf("%d ",a[i]);
 }
 printf("\n");
 for(i=0;i<k2;i++){
 printf("%d ",b[i]);
 } printf("\n");
 for(i=0;i<20;i++){
 printf("%f",c[i]);
 }
 */
 for(i=0;i<k2;i++){
 for(j=i+1;j<k2;j++){
 if(b[i]==b[j]&&b[i]!=-1){
 c[i+10]+=c[j+10];
 b[j]=-1;
 }
 }
 }

 for(i=0;i<k1;i++){
 if(a[i]!=-1){
 key1++;
 }
 }
 for(i=0;i<k2;i++){
 if(b[i]!=-1){
 key1++;
 }
 }

 printf("%d ",key1);
 for(i=0;i<k1;i++){

 /*if(a[i]!=-1){
 printf("%d ",a[i]);
 printf("%.1f",c[i]);key2++;
 if(key2!=key1)
 printf(" ");
 }*/
 if(a[i]!=-1){
 fin[aa++]=a[i];
 c[bb++]=c[i];
 }
 }
 for(i=0;i<k2;i++){
 /*if(b[i]!=-1){
 printf("%d ",b[i]);
 printf("%.1f",c[i+10]);
 key2++;
 if(key2!=key1)
 printf(" ");
 }
 */
 if(b[i]!=-1){
 fin[aa++]=b[i];
 c[bb++]=c[i+10];
 }
 }
budlesort (fin,c,key1);
 for(i=0;i<key1;i++){
 printf("%d ",fin[i]);
 printf("%.1f",c[i]);
 if(i<key1-1)
 printf(" ");
 }



 return 0;
}

 

新的编码(25分)

#include<stdio.h>
void adda(int sign,float data,float a[]){
 int i=0;
 for(;i<=1000;i++){
 if(i==sign){
 a[i]=a[i]+data;
 break;
 }
 }


}
int main(){
float a[1001]={0};
int k=0;float data=0;int numb=0,sign=0;int i=0;int y=0,n=0;
int t=0;
for(;y<2;y++){
scanf("%d",&k);
for(i=0;i<k;i++){
 scanf("%d",&sign);
 scanf("%f",&data);
 adda(sign,data,a);

}
}

for(i=0;i<1001;i++){
 if(a[i]!=0){
 n++;
 }

}


printf("%d",n);
if(n!=0)
 printf(" ");
for(i=1000;i>=0;i--){
 if(a[i]!=0){
 printf("%d ",i);
 t++;
 printf("%.1f",a[i]);
 if(t!=n)
 printf(" ");
 }

}
return 0;
}

数模历程

  对于数模的学习主要围绕两个比赛:全国大学生数学建模(CUMCM)和美国大学生数学建模竞赛(MCM/ICM),主要的学习方法就是借助比赛中的优秀论文进行学习,分析。望能学习处理问题的相关思路和数学方法。会将将论文进行专题性质的探讨以及优秀论文中出现的一些算法进行详尽研究。

  数学建模,一直觉得是很神奇的,让我们更加理性的,真实的看待这个世界。每个建立的模型,都相当于一个黑盒子,它是由各类数学方法,思想构建的,当你输入相关的因素或将它置于一个适合它的环境,它给你,你之前看不到的,或是不久的未来。仿佛创造出一个新的工具,可以看清未来的一角。(我不管我就喜欢瞎bb)

     得儿,驾

1001 A+B Format (20)

题目:

https://www.patest.cn/contests/pat-a-practise/1001

大概描述:

就是将在-1000000到1000000内的两数相加,并且按照-199,820/199,820/1,199820的格式输出

使用语言:

C

解题思想:

将结果的每一位拆分到数组中存储(由于有一些时间没有用c语言编程了,可能对于c语言使用的不够灵活)

题目得分:

20

提交次数:

3

做题时间:

30分钟

具体代码如下:

#include<stdio.h>
int clength(int m){
 int i=0;
 if(m==0)
 return i;
 do{
 m=m/10;
 i++;
 }while(m!=0);
 // printf("i=%d",i);
 return i;

}

int main(){
int a=0; int b=0;int c=0;int d=0;
int i=0;int zu[7]={0};int j=0;
scanf("%d %d",&a,&b);
c=a+b;
d=clength(c);
if(c<0){
 j=1;
 c=-c;
}
if(c==0){
 printf("0");
 return 0;
}

for(i=d-1;i>=0;i--){
 zu[i]=c%10;
 c=c/10;
}

if(j==1)
 printf("-");

for(i=0;i<d;i++){
 if((i==d-3||i==d-6)&&i!=0)
 printf(",");
 printf("%d",zu[i]);
// printf("*%d",i);
}
 return 0;

}