一维搜索：0.618法

2024-01-03 03:08

文章标签 搜索一维 0.618

本文主要是介绍一维搜索：0.618法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

0.618法又叫黄金分割法，适用于单峰函数，可以不连续。

1.算法步骤

(1) 置初始区间 $[a_1,b_1]$ 及精度要求 $L>0$ ,计算试探点 $\lambda_1$ 和 $\mu_1$ ，计算函数值 $f(\lambda_1)$ 和 $f(\mu_1)$ 。计算公式为 $λ 1 = a 1 + 0.382 (b 1 - a 1), μ 1 = a 1 + 0.618 (b 1 - a 1)$ $\lambda_1=a_1+0.382(b_1-a_1),\mu_1=a_1+0.618(b_1-a_1)$
(2) 若 $b_k-a_k<L$ ,则停止计算。否则，当 $f(\lambda_k)>f(\mu_k)$ 时，转步骤（3）；当 $f(\lambda_k)\leq f(\mu_k)$ 时，转步骤(4)。
(3) 置 $a_{k+1}=\lambda_k,b_{k+1}=b_k,\lambda_{k+1}=\mu_k,\mu_{k+1}=a_{k+1}+0.618(b_{k+1}-a_{k+1})$ 计算函数值 $f(\mu_{k+1})$ 转步骤(5)。
(4) 置 $a_{k+1}=a_k,b_{k+1}=\mu_k,\mu_{k+1}=\lambda_k,\lambda_{k+1}=a_{k+1}+0.382(b_{k+1}-a_{k+1})$ 计算函数值 $f(\lambda_{k+1})$ 转步骤(5)。
(5) 置 $k:=k+1$ ,返回步骤(2)。

2.代码示例
1.测试函数：

clc,clear
func = @(x) 2*x.^2 - x - 1; % 创建函数句柄
a1 = -1;
b1 = 1;
L = 0.01;
tic
[x state] = goldenRatio(func,a1,b1,L); %求解最小值
toc
% 画图展示
x = a1:0.01:b1;
y = 2*x.^2 - x - 1;
axis([-2 2 -10 10])
for k = 1:size(state,1)
figure(1)
plot(x,y,'b'); hold on 
plot(state(k,[1 2]),func(state(k,[1 2])),'ro'); hold off
axis([-2 2 -4 4])
pause(0.4);
end

2.算法函数：

% goldenRatio 黄金分割法
%   - 优点：不要求函数可微，且每次迭代只需计算一个函数值，计算量小，程序简单
%   - 缺点：收敛速度慢
% Inputs:
%   - func  要计算的函数的函数句柄
%   - L > 0 精度
%   - a1    搜索区间下限
%   - b1    搜索区间上限
% Outputs:
%   - res     返回func(x)的最小值
%   - state   返回每次迭代的[a_k b_k lambda_k mu_k f1 f2] function [res,state] = goldenRatio(func,a1,b1,L)
%初始化
a_k = a1; 
b_k = b1;
lambda_k = a1 + 0.382*(b1 - a1);
mu_k = a1 + 0.618*(b1 - a1);
f1 = func(lambda_k);
f2 = func(mu_k);count = 1;
while(true)%实际使用时可以去掉state和count，因为会影响运行速度state(count,:) = [a_k b_k lambda_k mu_k f1 f2]; count = count + 1;if(b_k - a_k < L) break;endif(f1 > f2)a_k = lambda_k;%b_k = b_k; lambda_k = mu_k;mu_k = a_k + 0.618*(b_k - a_k);f1 = f2;f2 = func(mu_k);else%a_k = a_k;b_k = mu_k;mu_k = lambda_k;lambda_k = a_k + 0.382*(b_k - a_k);f2 = f1;f1 = func(lambda_k);end
end
res = 0.5*(a_k + b_k);
end