对于文章 LQR轨迹跟踪算法Python/Matlab算法实现中的LQR推导的问题，我简单写了一下手稿，不高兴做成公式了：

模拟退火算法(实例分析)–Matlab算法






此篇文章为我一学长(Hong Yilin)所作，我又进行了一些加工，在此只为学习使用。

此篇为模拟退火算法的实例分析，模拟退火算法的理论讲解见上一篇。





题目：我方有一个基地，经度和纬度为（70，40）。假设我方飞机的速度为 1000 公里/小时。

我方派一架飞机从基地出发，侦察完敌方所有目标，再返回原来的基地。在敌方每一目标点的侦察时间不计，

求该架飞机所花费的时间（假设我方飞机巡航时间可以充分长）。

敌方经度纬度如下：

[html] view plain copy
 print?
表1 敌方100城市经纬度  
  
经度  纬度  经度  纬度  经度  纬度  经度  纬度  
53.7121 15.3046 51.1758 0.0322  46.3253 28.2753 30.3313 6.9348  
56.5432 21.4188 10.8198 16.2529 22.7891 23.1045 10.1584 12.4819  
20.1050 15.4562 1.9451  0.2057  26.4951 22.1221 31.4847 8.9640  
26.2418 18.1760 44.0356 13.5401 28.9836 25.9879 38.4722 20.1731  
28.2694 29.0011 32.1910 5.8699  36.4863 29.7284 0.9718  28.1477  
8.9586  24.6635 16.5618 23.6143 10.5597 15.1178 50.2111 10.2944  
8.1519  9.5325  22.1075 18.5569 0.1215  18.8726 48.2077 16.8889  
31.9499 17.6309 0.7732  0.4656  47.4134 23.7783 41.8671 3.5667  
43.5474 3.9061  53.3524 26.7256 30.8165 13.4595 27.7133 5.0706  
23.9222 7.6306  51.9612 22.8511 12.7938 15.7307 4.9568  8.3669  
21.5051 24.0909 15.2548 27.2111 6.2070  5.1442  49.2430 16.7044  
17.1168 20.0354 34.1688 22.7571 9.4402  3.9200  11.5812 14.5677  
52.1181 0.4088  9.5559  11.4219 24.4509 6.5634  26.7213 28.5667  
37.5848 16.8474 35.6619 9.9333  24.4654 3.1644  0.7775  6.9576  
14.4703 13.6368 19.8660 15.1224 3.1616  4.2428  18.5245 14.3598  
58.6849 27.1485 39.5168 16.9371 56.5089 13.7090 52.5211 15.7957  
38.4300 8.4648  51.8181 23.0159 8.9983  23.6440 50.1156 23.7816  
13.7909 1.9510  34.0574 23.3960 23.0624 8.4319  19.9857 5.7902  
40.8801 14.2978 58.8289 14.5229 18.6635 6.7436  52.8423 27.2880  
39.9494 29.5114 47.5099 24.0664 10.1121 27.2662 28.7812 27.6659  
8.0831  27.6705 9.1556  14.1304 53.7989 0.2199  33.6490 0.3980  
1.3496  16.8359 49.9816 6.0828  19.3635 17.6622 36.9545 23.0265  
15.7320 19.5697 11.5118 17.3884 44.0398 16.2635 39.7139 28.4203  
6.9909  23.1804 38.3392 19.9950 24.6543 19.6057 36.9980 24.3992  
4.1591  3.1853  40.1400 20.3030 23.9876 9.4030  41.1084 27.7149  
表1 敌方100城市经纬度

经度  纬度  经度  纬度  经度  纬度  经度  纬度
53.7121 15.3046 51.1758 0.0322  46.3253 28.2753 30.3313 6.9348
56.5432 21.4188 10.8198 16.2529 22.7891 23.1045 10.1584 12.4819
20.1050 15.4562 1.9451  0.2057  26.4951 22.1221 31.4847 8.9640
26.2418 18.1760 44.0356 13.5401 28.9836 25.9879 38.4722 20.1731
28.2694 29.0011 32.1910 5.8699  36.4863 29.7284 0.9718  28.1477
8.9586  24.6635 16.5618 23.6143 10.5597 15.1178 50.2111 10.2944
8.1519  9.5325  22.1075 18.5569 0.1215  18.8726 48.2077 16.8889
31.9499 17.6309 0.7732  0.4656  47.4134 23.7783 41.8671 3.5667
43.5474 3.9061  53.3524 26.7256 30.8165 13.4595 27.7133 5.0706
23.9222 7.6306  51.9612 22.8511 12.7938 15.7307 4.9568  8.3669
21.5051 24.0909 15.2548 27.2111 6.2070  5.1442  49.2430 16.7044
17.1168 20.0354 34.1688 22.7571 9.4402  3.9200  11.5812 14.5677
52.1181 0.4088  9.5559  11.4219 24.4509 6.5634  26.7213 28.5667
37.5848 16.8474 35.6619 9.9333  24.4654 3.1644  0.7775  6.9576
14.4703 13.6368 19.8660 15.1224 3.1616  4.2428  18.5245 14.3598
58.6849 27.1485 39.5168 16.9371 56.5089 13.7090 52.5211 15.7957
38.4300 8.4648  51.8181 23.0159 8.9983  23.6440 50.1156 23.7816
13.7909 1.9510  34.0574 23.3960 23.0624 8.4319  19.9857 5.7902
40.8801 14.2978 58.8289 14.5229 18.6635 6.7436  52.8423 27.2880
39.9494 29.5114 47.5099 24.0664 10.1121 27.2662 28.7812 27.6659
8.0831  27.6705 9.1556  14.1304 53.7989 0.2199  33.6490 0.3980
1.3496  16.8359 49.9816 6.0828  19.3635 17.6622 36.9545 23.0265
15.7320 19.5697 11.5118 17.3884 44.0398 16.2635 39.7139 28.4203
6.9909  23.1804 38.3392 19.9950 24.6543 19.6057 36.9980 24.3992
4.1591  3.1853  40.1400 20.3030 23.9876 9.4030  41.1084 27.7149





分析：


1.实际距离的求解：

设A, B两点的地理坐标分别为(x1,y1), (x2,y2)，过 A, B两点的大圆的劣弧长即为两点的实际距离。


以地心为坐标原点o，以赤道平面为XOY平面，以0度经线圈所在的平面为XOZ平面建立三维直角坐标系。


地球半径为R=6370km。则 A, B两点的直角坐标分别为：


A( R*cos(x1)*cos(y1), R*sin(x1)*cos(y1), R*sin(y1) )     B( R*cos(x2)*cos(y2), R*sin(x2)*cos(y2), R*sin(y2) )



A、B两点实际距离：

d=Rarccos[ cos(x1-x2)*cos(y1)*cos(y2) + sin(y1)*sin(y2) ]。

建立矩阵D，将所有点之间的距离存放进去。


问题转化为从（70，40）出发，走遍所有点，并返回出发点。


2.关于Monte Carlo方法


本文中使用Monte Carlo方法先得到一个较小的sum,和一组S0。


3.算法原理：


设S＝{s1,s2,…,sn}为所有可能的状态所构成的集合， f：S—R为非负代价函数，


即优化问题抽象如下：寻找s*∈S，使得f(s*)＝min f(si) 任意si∈S 


具体步骤：

(1)给定一较高初始温度T，随机产生初始状态S

(2)按一定方式，对当前状态作随机扰动，产生一个新的状态S’

              S’＝S＋sign(η).δ (其中δ为给定的步长， η为[－1,1]的随机数 )

     计算Δ＝f(S’)－f(S)

(3)若Δ<0，则令S＝S’，转第(5)步

(4)若Δ≤0，则以概率exp(－Δ/T)接受S’，即S＝S’

    具体操作：产生一个在[0，1]上服从均匀分布的随机数x，若x<exp(－Δ/T)，则S＝S;否则S保持不变

(5)按一定方式降温，使T≤Ti， 如： ＝αTi，习惯上取α∈(0.8，0.9999)

(6)检查退火是否结束

     是——转向第(7)步

     否——转向第(2)步

(7)以当前Si作为最优解输出


注：1、结束标志：温度是否小于某一阀值(循环次数)f的值变化是否明显

        2、初始温度的高低：下降是否充分慢对结果有影响



4.算法详述：


首先给定一个初始温度TO 和该优化问题的一个初始解 x(0)，并由 x(0)生成下一个解 x’∈ N(x(0))，是否接受x’作为一个新解x(1)依赖于下面概率：

                                 

换句话说，如果生成的解 的函数值比前一个解的函数值更小，则接受x(1)=x ‘作为一个新解。否则以概率作为一个新解。


以此类推，在温度T_i下，经过很多次的转移之后，降低温度T_i，得到T(i+1)<T(i)。在T(i+1)下重复上述过程。因此整个优化过程就是不断寻找新解和缓慢降温的交替过程。最终的解是对该问题寻优的结果。


在得到初始解之后，可以用2变换法，即交换两个点之间的路线。设定T0为1，以0.001为降温幅度，选择终止温度为e=10-30。运行代码，得到可行解，时间为43小时左右




算法：


[plain] view plain copy
 print?
function Simulated_AnneALIng()  
%算法：模拟退火算法(Simulated AnneALIng)  
  
%敌方经度纬度数据见 sj.txt  
  
%% 清空  
clc,clear;  
%% 坐标转换，计算距离  
load sj.txt %加载敌方100个目标的数据，数据按照表格中的位置保存在纯文本文件 sj.txt 中  
x=sj(:,1:2:8) ; x=x(:);%将4列变成1列  
y=sj(:,2:2:8) ; y=y(:);  
sj=[x y];  
d1=[70,40] ; sj=[d1;sj;d1] ;   
sj1=sj;  
sj=sj*pi/180;   
n=length(sj);  
d=zeros(n);   %距离矩阵 d  
for i=1:n-1  %坐标转换为距离  
     for j=i+1:n  
          temp=cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2));  
          d(i,j)=6370*acos(temp);  
     end  
end  
d=d+d’ ; S0=[] ; Sum=inf;  
%% 设定初始解（MonteCarlo法）  
for j=1:1000    
     S=[1,1+randperm(n-2),n]; temp=0;    %用randperm函数随机打乱2到(n-2)之间的数  
     for i=1:n-1  
          temp=temp+d(S(i),S(i+1));  
     end  
     if temp<Sum  
          S0=S; Sum=temp;  
     end  
end  
e=0.1^30; L=20000; at=0.999; T=1;%参数设置  
%% 退火过程  
for k=1:L  %产生新解  
    %随机找两个点来交换路线  
     c=2+floor((n-2)*rand(1,2)); c=sort(c);   
     c1=c(1);c2=c(2);  
     df=d(S0(c1-1),S0(c2))+d(S0(c1),S0(c2+1))-d(S0(c1-1),S0(c1))-d(S0(c2),S0(c2+1));%计算代价函数值  
     %接受准则  
     if df<0 %路径更短，接受新解  
         S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:n)];  
         Sum=Sum+df ; T=T*at;%接受并降温  
     elseif exp(-df/T)>rand(1)  %路径没变短，以一定概率接受新解  
         S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:n)];  
         Sum=Sum+df ; T=T*at;  
     end  
     if T<e  
         break;  
     end  
end  
disp([‘最短巡航路径长度：’,num2str(Sum),’km’]);  
disp([‘最短巡航路径时耗：’,num2str(Sum/1000),’h’]);  
  
%% 画图  
hold on  
plot(sj1(1:101,1), sj1(1:101,2), ‘ko’);  
for i=1:101  
    temp=[‘  ’,int2str(i)];  
    text(sj1(i,1), sj1(i,2),temp);  
end  
for i=1:101  
    plot(sj1(S0(i:i+1),1)’, sj1(S0(i:i+1),2)’,’k-‘);  
end  
title([‘近似路径如下，巡航路径长度：’,num2str(Sum),’km，’,’时耗：’,num2str(Sum/1000),’h’]);  
hold off  
function Simulated_AnneALIng()
%算法：模拟退火算法(Simulated AnneALIng)

%敌方经度纬度数据见 sj.txt

%% 清空
clc,clear;
%% 坐标转换，计算距离
load sj.txt %加载敌方100个目标的数据，数据按照表格中的位置保存在纯文本文件 sj.txt 中
x=sj(:,1:2:8) ; x=x(:);%将4列变成1列
y=sj(:,2:2:8) ; y=y(:);
sj=[x y];
d1=[70,40] ; sj=[d1;sj;d1] ; 
sj1=sj;
sj=sj*pi/180; 
n=length(sj);
d=zeros(n);   %距离矩阵 d
for i=1:n-1  %坐标转换为距离
     for j=i+1:n
          temp=cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2));
          d(i,j)=6370*acos(temp);
     end
end
d=d+d' ; S0=[] ; Sum=inf;
%% 设定初始解（MonteCarlo法）
for j=1:1000  
     S=[1,1+randperm(n-2),n]; temp=0;    %用randperm函数随机打乱2到(n-2)之间的数
     for i=1:n-1
          temp=temp+d(S(i),S(i+1));
     end
     if temp<Sum
          S0=S; Sum=temp;
     end
end
e=0.1^30; L=20000; at=0.999; T=1;%参数设置
%% 退火过程
for k=1:L  %产生新解
    %随机找两个点来交换路线
     c=2+floor((n-2)*rand(1,2)); c=sort(c); 
     c1=c(1);c2=c(2);
     df=d(S0(c1-1),S0(c2))+d(S0(c1),S0(c2+1))-d(S0(c1-1),S0(c1))-d(S0(c2),S0(c2+1));%计算代价函数值
     %接受准则
     if df<0 %路径更短，接受新解
         S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:n)];
         Sum=Sum+df ; T=T*at;%接受并降温
     elseif exp(-df/T)>rand(1)  %路径没变短，以一定概率接受新解
         S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:n)];
         Sum=Sum+df ; T=T*at;
     end
     if T<e
         break;
     end
end
disp(['最短巡航路径长度：',num2str(Sum),'km']);
disp(['最短巡航路径时耗：',num2str(Sum/1000),'h']);

%% 画图
hold on
plot(sj1(1:101,1), sj1(1:101,2), 'ko');
for i=1:101
    temp=['  ',int2str(i)];
    text(sj1(i,1), sj1(i,2),temp);
end
for i=1:101
    plot(sj1(S0(i:i+1),1)', sj1(S0(i:i+1),2)','k-');
end
title(['近似路径如下，巡航路径长度：',num2str(Sum),'km，','时耗：',num2str(Sum/1000),'h']);
hold off

MATLAB算法技巧和实现斐波那契数列

这篇博客主要说一下自己在算法设计课上用matlab做的两道算法题，题目解起来都比较简单，但是需要些技巧。 

 公倍数的应用 

 斐波那契数列的应用


题目要求

题目一:公倍数的应用

  心里想好一个1~100之间的整数x，将它分别除以3，5，7并得到3个余数。把这三个余数输入计算机，计算机能马上猜出这个数

题目二:斐波那契数列的应用

  斐波那契数列有如下特点：a1,a2已知  a(n)=a(n-1)+a(n-2)  n>=3 

  例题：楼梯上有n阶台阶，上楼时可以一步上1阶，也可以一步上2阶，编写算法计算共有多少种不同的上楼梯方法

解题思路

问题一，问题一可以将该数转换为d=70*a+21*b+15*c的乘积，主要是利用了他们的公倍数性质。

详细数学模型解释： 

 1）不难理解当s=u+3*v+3*w时，s除以3的余数与u除以3的余数是一样的。 

 2）对s=cu+3*v+3*w，当c除以3余数为1的数时, s除以3的余数与u除以3的余数也是一样的。证明如下：c 除以 3余数为1，记c=3*k+1，则s=u+3*k*u+3*v+3*w，由1)的结论，上述结论正确。记a，b，c分别为所猜数据d除以3，5，7后的余数，则d=70*a+21*b+15*c。为问题的数学模型，其中70称作a的系数，21称作b的系数,15称作c的系数。

问题二，就单纯是递归问题，编者对于递归也不太熟悉，正在逐步探索中。

数学模型： 

此问题如果按照习惯，从前向后思考，也就是从第一阶开始，考虑怎么样走到第二阶、第三阶、第四阶……，则很难找出问题的规律；而反过来先思考“到第n阶有哪几种情况？”，答案就简单了，只有两种情况： 

      1）  从第n-1阶到第n阶； 

      2）  从第n-2阶到第n阶。 

   记n阶台阶的走法数为f(n)，则 

   f(n)= 1                  n=1 

  f(n)=2              n=2 

  f(n-1)+f(n-2)       n>2

代码实现

主文件：main.m

%made by Canlong
%%
%编写算法完成下面给余猜谜的游戏
%心里想好一个1~100之间的整数x，将它分别除以3，5，7并得到3个余数。把这三个余数输入计算机，计算机能马上猜出这个数。
%方法一：穷举法
disp('方法一：穷举法')
num1 = input('请输入第一个数：');
num2 = input('请输入第二个数：');
num3 = input('请输入第三个数：'); 
for i=1:100
    if rem(i,3)==num1 && rem(i,5)==num2 && rem(i,7)==num3  
       fprintf('该数为：%d \n',i); 
    end
end

%%
%方法二，建模.
disp('方法二，建模.');
num1 = input('请输入第一个数：');
num2 = input('请输入第二个数：');
num3 = input('请输入第三个数：'); 
d=70*num1+21*num2+15*num3;
while d>105
   d = d-105 ;
end
fprintf('该数为：%d \n',d);

%%
%斐波那契数列的应用
%斐波那契数列有如下特点：a1,a2已知  a(n)=a(n-1)+a(n-2)  n>=3
%例题：楼梯上有n阶台阶，上楼时可以一步上1阶，也可以一步上2阶，编写算法计算共有多少种不同的上楼梯方法
%楼梯阶数
n=10;
disp('如果楼梯阶数为10，上楼梯的方法数，解得：');
fprintf('f(%d)为：%d \n',n,f(n));



函数文件：f.m

%输入n为阶梯数，a为返回的阶梯数
%made by Canlong
function a=f(n)
    if n==1
         a=1;
         return;
    end
    if n==2
         a=2;
         return
    else
         a=f(n-1)+f(n-2);
         return
    end
end

运行结果

在MATLAB R2015b软件下运行得到：



总结

  太久没用matlab写代码了，对于matlab很多语法很多都不熟悉了，写到函数那里还以为return 数值会直接返回数值，原来matlab的函数，是通过某个变量来返回值的，不能直接return 数值，如function a=f(n)中的a就是用来接受返回数值的，要返回数值的函数一定要对a进行赋值。这一点上与java等语言不太类似。

求解很多多自变量的问题时，需要用到遗传算法，我们以标准遗传算法为例，举例说明如何实现x、y两个自变量的遗传算法的实现。其实在之前的文章

遗传算法的进一步探究—多目标优化_数学建模matlab算法(七)

以及

遗传算法的进一步探究—多目标优化_数学建模matlab算法(七)

中，我们举例的问题，就是多自变量的，这里，我们再次，探究一下。

假设我们要求解一个二元函数f(x,y)的最大值，它的自变量是x和y。下面我们还是应用谢菲尔德大学的遗传算法工具箱来求解。



全部matlab代码如下：
clc
clear all
close all
%% 画出函数图
figure(1);
lbx=-2;ubx=2; %函数自变量x范围【-2,2】
lby=-2;uby=2; %函数自变量y范围【-2,2】
ezmesh('y*sin(2*pi*x)+x*cos(2*pi*y)',[lbx,ubx,lby,uby],50);   %画出函数曲线
hold on;
%% 定义遗传算法参数
NIND=40;        %个体数目
MAXGEN=50;      %最大遗传代数
PRECI=20;       %变量的二进制位数
GGAP=0.95;      %代沟
px=0.7;         %交叉概率
pm=0.01;        %变异概率
trace=zeros(3,MAXGEN);                        %寻优结果的初始值
FieldD=[PRECI PRECI;lbx lby;ubx uby;1 1;0 0;1 1;1 1];                      %区域描述器
Chrom=crtbp(NIND,PRECI*2);                      %初始种群
%% 优化
gen=0;                                  %代计数器
XY=bs2rv(Chrom,FieldD);                 %计算初始种群的十进制转换
X=XY(:,1);Y=XY(:,2);
ObjV=Y.*sin(2*pi*X)+X.*cos(2*pi*Y);        %计算目标函数值
while gen<MAXGEN
   FitnV=ranking(-ObjV);                              %分配适应度值
   SelCh=select('sus',Chrom,FitnV,GGAP);              %选择
   SelCh=recombin('xovsp',SelCh,px);                  %重组
   SelCh=mut(SelCh,pm);                               %变异
   XY=bs2rv(SelCh,FieldD);               %子代个体的十进制转换
   X=XY(:,1);Y=XY(:,2);
   ObjVSel=Y.*sin(2*pi*X)+X.*cos(2*pi*Y);             %计算子代的目标函数值
   [Chrom,ObjV]=reins(Chrom,SelCh,1,1,ObjV,ObjVSel); %重插入子代到父代，得到新种群
   XY=bs2rv(Chrom,FieldD);
   gen=gen+1;                                             %代计数器增加
   %获取每代的最优解及其序号，Y为最优解,I为个体的序号
   [Y,I]=max(ObjV);
   trace(1:2,gen)=XY(I,:);                       %记下每代的最优值
   trace(3,gen)=Y;                               %记下每代的最优值
end
plot3(trace(1,:),trace(2,:),trace(3,:),'bo');                            %画出每代的最优点
grid on;
plot3(XY(:,1),XY(:,2),ObjV,'bo');  %画出最后一代的种群
hold off
%% 画进化图
figure(2);
plot(1:MAXGEN,trace(3,:));
grid on
xlabel('遗传代数')
ylabel('解的变化')
title('进化过程')
bestZ=trace(3,end);
bestX=trace(1,end);
bestY=trace(2,end);
fprintf(['最优解:\nX=',num2str(bestX),'\nY=',num2str(bestY),'\nZ=',num2str(bestZ),'\n'])


求解结果如下：