查看: 2630|回复: 0

爬山算法

字体大小: 正常放大

1198 主题	4 听众	2977 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

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

步骤 1: 定义目标函数

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

function y = myFunction(x)
* m7 D0 i- U( [- a* N) a0 O& w
y = -x^2 + 4*x;8 e- U+ j+ s' I\\" I1 ?
end

步骤 2: 实现爬山算法

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

function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations)
0 x$ B. v# a( |4 @
currentX = initialX;
currentY = func(currentX);0 ?9 Q t9 m: @+ Q% E9 h
for i = 1:numIterations# S\\" G+ q! C+ ?; `) p; ~
% 尝试在两个方向上移动; R$ a$ B5 Y6 g8 d
newX = [currentX + stepSize, currentX - stepSize];
* Y e, a4 `( |( P! T0 n. z) b& X
newY = [func(newX(1)), func(newX(2))];1 E\\" A) d k. C\\" f, E( P: ~+ \) ?6 B
, o0 m8 K- q8 `1 h
% 找出最好的移动方向\\" s4 t$ N1 F3 P+ O. r
[maxY, idx] = max(newY);
& g/ H2 k1 T/ B' y. S
7 @. n, k4 b* ?! N5 D
% 如果找到了更好的解，则更新当前解
3 F& ?3 G' h9 t7 ` ~+ P4 u
if maxY > currentY
6 Y# O) o/ m& }0 ?6 v3 q& f% R
currentX = newX(idx);' f% m- y9 K, O( v& k& i) g# q
currentY = maxY;! e; j0 m# C4 ?6 i/ }4 p
else
6 K+ u% s2 D, |1 m; S6 E6 A8 e
% 如果没有更好的解，结束搜索$ M1 }. s5 `- C6 R6 O |$ n
break;2 \3 B% l; }: n4 f
end
2 w0 a6 E V# K4 X8 X6 T/ z\\" T
end
9 f+ a5 a/ O3 }7 Y
bestX = currentX;
- {; D$ E' Q* b8 u I' l7 v
bestY = currentY;
7 h4 k% [: S- R/ g7 y/ H3 Y' t4 D7 Q
end
$ n2 N D$ g6 ~* E. Y1 U* I; C
. \ w% m$ \* {: F- v
% 运行爬山算法4 {# L$ e; k! P; |
initialX = 0; % 初始点) L/ }* M9 a! M, e) y9 M$ c1 O$ R
stepSize = 0.1; % 步长/ k. Q) U) ^* C
numIterations = 100; % 迭代次数4 m. G/ ~. p1 `6 @& @. Q- k; a
[bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations) 
0 x$ B. v# a( |4 @
    currentX = initialX; 
% @  L  I+ t1 i5 `1 v! v2 U( d& B( B
    currentY = func(currentX);0 ?9 Q  t9 m: @+ Q% E9 h

for i = 1:numIterations# S\\" G+ q! C+ ?; `) p; ~

% 尝试在两个方向上移动; R$ a$ B5 Y6 g8 d

newX = [currentX + stepSize, currentX - stepSize]; 
* Y  e, a4 `( |( P! T0 n. z) b& X
        newY = [func(newX(1)), func(newX(2))];1 E\\" A) d  k. C\\" f, E( P: ~+ \) ?6 B

, o0 m8 K- q8 `1 h

% 找出最好的移动方向\\" s4 t$ N1 F3 P+ O. r

[maxY, idx] = max(newY); 
& g/ H2 k1 T/ B' y. S
         
7 @. n, k4 b* ?! N5 D
        % 如果找到了更好的解，则更新当前解 
3 F& ?3 G' h9 t7 `  ~+ P4 u
        if maxY > currentY 
6 Y# O) o/ m& }0 ?6 v3 q& f% R
            currentX = newX(idx);' f% m- y9 K, O( v& k& i) g# q

currentY = maxY;! e; j0 m# C4 ?6 i/ }4 p

else 
6 K+ u% s2 D, |1 m; S6 E6 A8 e
            % 如果没有更好的解，结束搜索$ M1 }. s5 `- C6 R6 O  |$ n

break;2 \3 B% l; }: n4 f

end 
2 w0 a6 E  V# K4 X8 X6 T/ z\\" T
    end 
9 f+ a5 a/ O3 }7 Y
    bestX = currentX; 
- {; D$ E' Q* b8 u  I' l7 v
    bestY = currentY; 
7 h4 k% [: S- R/ g7 y/ H3 Y' t4 D7 Q
end 
$ n2 N  D$ g6 ~* E. Y1 U* I; C
 . \  w% m$ \* {: F- v

% 运行爬山算法4 {# L$ e; k! P; |

initialX = 0; % 初始点) L/ }* M9 a! M, e) y9 M$ c1 O$ R

stepSize = 0.1; % 步长/ k. Q) U) ^* C

numIterations = 100; % 迭代次数4 m. G/ ~. p1 `6 @& @. Q- k; a

[bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

步骤 3: 输出结果

展示算法找到的最优解。

disp(['The maximum value of f(x) is found at x = ', num2str(bestX)]);- p; r# t0 L: h: `\" z! o) o1 N
disp(['The maximum value of f(x) is ', num2str(bestY)]);

复制代码

步骤 4: 可视化

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