查看: 2470|回复: 0

爬山算法

字体大小: 正常放大

1186 主题	4 听众	2922 积分

该用户从未签到

电梯直达

1^#

发表于 2024-4-26 15:44 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

使用爬山算法优化简单的数学函数

假设我们需要找到函数 𝑓(𝑥)=−𝑥^2+4𝑥的最大值。这是一个具有单个局部最大值的简单抛物线函数。

步骤 1: 定义目标函数

首先，定义我们需要优化的函数。在MATLAB中，我们可以创建一个函数来计算给定x值的 𝑓(𝑥)。

function y = myFunction(x)
2 d1 u$ N5 f5 f$ g+ |/ Q7 F1 J( f
y = -x^2 + 4*x;
) r: z5 q! O- M. f; F6 K8 K
end

步骤 2: 实现爬山算法

接着，实现爬山算法。我们从一个随机点开始，然后在每一步尝试移动到一个“邻居”点，如果那里的值更高，就移动到那里。

function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations)! V0 d( u5 _8 I* m6 Y3 c
currentX = initialX;
2 G2 _! c3 l0 j2 K C
currentY = func(currentX);
$ c9 r# C% }! p! b
for i = 1:numIterations ^$ E$ h2 N% U5 O# H! m( R3 t\\" m
% 尝试在两个方向上移动! q6 l1 D$ p! _6 u% F4 j
newX = [currentX + stepSize, currentX - stepSize];
9 i! j- M, a. p I: T1 C! F
newY = [func(newX(1)), func(newX(2))];
) S) M* M, ]0 O\\" c
6 |8 l5 {9 g, [( b\\" b$ ~
% 找出最好的移动方向# u. u: e9 g% p, j7 D4 V( T
[maxY, idx] = max(newY);0 g s2 z* ^# w9 X/ i
, n( v! e/ J4 N3 ?6 n0 x
% 如果找到了更好的解，则更新当前解
7 s5 X6 y) T5 A9 O
if maxY > currentY
3 `/ t# r, Z; F! c' x1 i7 T
currentX = newX(idx);
; P- |- H- E\\" _4 e
currentY = maxY;
! l$ x0 y. l/ q2 e& t
else* e; @! Z; V- [' i7 K
% 如果没有更好的解，结束搜索8 n% x\\" N4 v. K2 E' s& d
break;
5 [- M: a7 @/ r& \' r
end* N& R3 N/ g$ ?
end' f/ U5 S% T R
bestX = currentX; B7 @1 m- F o, c
bestY = currentY;
\\" A4 c3 d+ ]! ]3 M
end3 t1 S' L6 B/ A' j\\" J, B
% i1 f. w3 Y4 k8 Z: j0 e3 E
% 运行爬山算法
% ?0 k+ u/ y5 U' d( X7 M
initialX = 0; % 初始点1 s# n\\" G- t3 U$ J8 m; r3 d
stepSize = 0.1; % 步长. Y0 j m. e! Q* R8 o\\" |
numIterations = 100; % 迭代次数
' u7 X3 D, ?4 j4 Z H
[bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations)! V0 d( u5 _8 I* m6 Y3 c

currentX = initialX; 
2 G2 _! c3 l0 j2 K  C
    currentY = func(currentX); 
$ c9 r# C% }! p! b
    for i = 1:numIterations  ^$ E$ h2 N% U5 O# H! m( R3 t\\" m

% 尝试在两个方向上移动! q6 l1 D$ p! _6 u% F4 j

newX = [currentX + stepSize, currentX - stepSize]; 
9 i! j- M, a. p  I: T1 C! F
        newY = [func(newX(1)), func(newX(2))]; 
) S) M* M, ]0 O\\" c
 6 |8 l5 {9 g, [( b\\" b$ ~

% 找出最好的移动方向# u. u: e9 g% p, j7 D4 V( T

[maxY, idx] = max(newY);0 g  s2 z* ^# w9 X/ i

, n( v! e/ J4 N3 ?6 n0 x

% 如果找到了更好的解，则更新当前解 
7 s5 X6 y) T5 A9 O
        if maxY > currentY 
3 `/ t# r, Z; F! c' x1 i7 T
            currentX = newX(idx); 
; P- |- H- E\\" _4 e
            currentY = maxY; 
! l$ x0 y. l/ q2 e& t
        else* e; @! Z; V- [' i7 K

% 如果没有更好的解，结束搜索8 n% x\\" N4 v. K2 E' s& d

break; 
5 [- M: a7 @/ r& \' r
        end* N& R3 N/ g$ ?

end' f/ U5 S% T  R

bestX = currentX;  B7 @1 m- F  o, c

bestY = currentY; 
\\" A4 c3 d+ ]! ]3 M
end3 t1 S' L6 B/ A' j\\" J, B

% i1 f. w3 Y4 k8 Z: j0 e3 E

% 运行爬山算法 
% ?0 k+ u/ y5 U' d( X7 M
initialX = 0; % 初始点1 s# n\\" G- t3 U$ J8 m; r3 d

stepSize = 0.1; % 步长. Y0 j  m. e! Q* R8 o\\" |

numIterations = 100; % 迭代次数 
' u7 X3 D, ?4 j4 Z  H
[bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

步骤 3: 输出结果

展示算法找到的最优解。

disp(['The maximum value of f(x) is found at x = ', num2str(bestX)]);
`! d' J\" z4 J3 O) O\" m
disp(['The maximum value of f(x) is ', num2str(bestY)]);

复制代码

步骤 4: 可视化

可视化函数和算法找到的最大值点，以更好地理解算法的行为。