• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

航迹规划——模拟退火算法

人工智能 懒小象 2209次浏览 0个评论

模拟退火算法简介

模拟退火是一种通用概率算法,可来在固定时间内寻求在一个大的搜寻空间内找到的最优解,也可以用来求解函数最优解。模拟退火是S. Kirkpatrick, C. D. Gelatt和M. P. Vecchi在1983年所发明。而V. Černý在1985年也独立发明此算法。   在这里不讲解模拟退火算法的基础知识,重点对模拟退火算法的两种应用程序做解析,需要了解基础知识的可以参考文章最后的参考资料。  


 

模拟退火算法流程图

  模拟退火算法流程图  
航迹规划——模拟退火算法  


 

模拟退火算法Matlab程序

求解函数最优解

  变量声明初始化  

clear  
clc  
%生成初始解  
sol_new2=1;%(1)解空间(初始解)  
sol_new1=2-sol_new2^2;  
sol_current1 = sol_new1;   
sol_best1 = sol_new1;  
sol_current2 = sol_new2;   
sol_best2 = sol_new2;  
E_current = inf;  
E_best = inf;  

  退火算法参数设置  

rand('state',sum(clock)); %初始化随机数发生器  
t=90; %初始温度  
tf=89.9; %结束温度  
a = 0.99; %温度下降比例  

  主循环  

while t>=tf%(7)结束条件  
    for r=1:100 %退火次数  
        %产生随机扰动(3)新解的产生  
        sol_new2=sol_new2+rand*0.2;  
        sol_new1=2-sol_new2^2;  
        %检查是否满足约束  
        if sol_new1^2-sol_new2>=0 && -sol_new1-sol_new2^2+2==0 && sol_new1>=0 &&sol_new2>=0  
        else  
            sol_new2=rand*2;  
            sol_new1=2-sol_new2^2;  
            continue;  
        end  
        %退火过程  
        E_new=sol_new1^2+sol_new2^2+8;%(2)目标函数  
        if E_new<E_current%(5)接受准则  
                E_current=E_new;  
                sol_current1=sol_new1;  
                sol_current2=sol_new2;  
                if E_new<E_best  
                    %把冷却过程中最好的解保存下来  
                    E_best=E_new;  
                    sol_best1=sol_new1;  
                    sol_best2=sol_new2;  
                end  
        else  
                if rand<exp(-(E_new-E_current)/t)%(4)代价函数差  
                    E_current=E_new;  
                    sol_current1=sol_new1;  
                    sol_current2=sol_new2;  
                else  
                    sol_new1=sol_current1;  
                    sol_new2=sol_current2;  
                end  
        end  
        plot(r,E_best,'.')  
        hold on  
    end  
    t=t*a;%(6)降温  
end  

  显示结果  

disp('最优解为:')  
disp(sol_best1)  
disp(sol_best2)  
disp('目标表达式的最小值等于:')  
disp(E_best)  

 

运行结果如图

 
航迹规划——模拟退火算法   通过运行结果可以直观的看出最后程序的结果趋近于最优解,在这里最多退火100次,多次迭代后结果会更好。  

求解二维空间最优路径

  程序初始化,设置50个需要访问的点  

clc, clear
% 设置处理点的数量
N = 50;
M = zeros(N, 2);
% 产生100个位置不同的点
M(:, 1) = randperm(N);
M(:, 2) = randperm(N);

  计算两点之间的距离  

% 初始化距离矩阵
d = zeros(N);
% 统计每两个点之间的距离
for i=1:N-1
    for j=i+1:N
        d(i, j) = sqrt((M(i,1)-M(j,1))*(M(i,1)-M(j,1)) + (M(i,2)-M(j,2))*(M(i,2)-M(j,2)));
    end
end

  for循环生成的两点之间的距离思路为  

  1. 先计算(1,2),(1,3),(1,4)……(1,N)的距离存在二维数组d中。
  2. 计算(2,3),(2,4)(2,5)……(2,N)的距离存在二维数组d中。
  3. 计算(3,4)(3,5),(3,6)……(3,N)的距离存在二维数组d中。
  4. ……
  5. 计算(N-1,N)的距离存在二维数组d中,结束。

  此时d中存的数据为上三角矩阵,因为(1,2)和(2,1)的距离是一样的,因此将d中的数据扩充。  

d = d + d';

  通过打乱50个坐标点的链接顺序,多次计算其总路线长度,得出近似最优解。目的是为了和退火算法比较。  

% 初始化路径及路线长度
path = zeros(1, N);
length = inf;
% 先确定一个比较好的初始解
for i=1:1000
    path0 = randperm(N); % randperm 1-N 乱序排列
    temp = 0;
    for j=1:N-1
        temp = temp + d(path0(j) , path0(j+1));
    end
    if temp < length
       length = temp;
       path = path0;
    end
end
length
subplot(1, 2, 1)
plot(M(path, 1), M(path, 2), '-o');
title("Initial Solution");

  退火算法求解50个坐标点的最优路径 初始化参数  

% 设置模拟退火的参数
e = 0.1^30; % 结束温度
L = 20000; % 退火次数
at = 0.999; % 温度下降比例
T = 1; % 初始温度

  主循环  

for k = 1:L
    % 产生新解
    c = floor(rand(1, 2)*(N-2)) + 2; % floor 比它小的最大整数   
    c = sort(c);
    c1 = c(1);
    c2 = c(2);
    change = 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 change < 0
        path = [path(1:c1-1), path(c2:-1:c1), path(c2+1: N)];
        length = length + change;
    elseif exp(-change/T) >= rand % 接受条件
        path = [path(1:c1-1), path(c2:-1:c1), path(c2+1: N)];
        length = length + change;
    end
    T = T * at;
    if T < e
        break;
    end
end

  输出结果对比  

length
subplot(1, 2, 2)
plot(M(path, 1), M(path, 2), '-*');
title("Simulte Anneal Solution");
hold off

  产生新解的思路

  1. 随机生成两个数,A,B。
  2. 将A,B之间的序列调换。

 
航迹规划——模拟退火算法  

  1. 计算变化量。
  2. 总路长比之前解短的话保留结果,总路长比之前解长的话按接受条件exp(-change/T) >= rand接收。
  3. 满足终止条件后推出循环。

 

运行结果

 
航迹规划——模拟退火算法   从上图可以很明显的看出模拟退火算法比初始的最优解效果好,通过最后输出的总路径长度也可以看出模拟退火算法比初始的最优解效果好N倍~  


 

Marlab 完整代码

  两个代码在一起放着哦,大家注意看下哦 模拟退火算法Matlab程序二合一下载链接  


 

参考资料

优化算法——模拟退火算法


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明航迹规划——模拟退火算法
喜欢 (0)

您必须 登录 才能发表评论!

加载中……