查看: 2471|回复: 0

爬山算法

字体大小: 正常放大

1186 主题	4 听众	2922 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

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

步骤 1: 定义目标函数

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

function y = myFunction(x)
, ^; [4 l$ g) U
y = -x^2 + 4*x;
! P z7 ], ]& m2 \9 \* X0 t\\" M
end

步骤 2: 实现爬山算法

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

function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations)
6 @$ B! w& D* t, k( ]' Z& e
currentX = initialX;) _* I9 H6 R' L- h
currentY = func(currentX);
3 t% l6 @* h, O! n3 I) ?# |
for i = 1:numIterations
B/ J! f% A, M1 l; r
% 尝试在两个方向上移动
; {4 S6 u9 c8 x) ?: k$ [
newX = [currentX + stepSize, currentX - stepSize];
# R6 P\\" M. n& \% B. v
newY = [func(newX(1)), func(newX(2))];: F& q7 \) k8 w) n* d
6 w5 o! Q3 H% x# c
% 找出最好的移动方向
8 V y3 W6 v2 \- m7 Z
[maxY, idx] = max(newY);5 Q8 H2 c3 |4 m, q/ Y1 ~4 S
# F3 l. H4 D6 P1 u: Z9 ~, T
% 如果找到了更好的解，则更新当前解
* r$ Q4 {3 N7 F
if maxY > currentY\\" W% M5 a% j8 l8 H7 l' p/ i
currentX = newX(idx);
$ R* X\\" d' t- O
currentY = maxY;
* C5 j2 g7 ~7 K
else0 t\\" B3 K% \0 a, J/ f1 |
% 如果没有更好的解，结束搜索
break;
( @4 g! ]& X$ t- O: R. | d8 e! S4 F
end( O2 F2 a6 E7 W; q0 I! U; T
end* ~* W+ K ^4 |: S, ^2 {3 P# g1 ~
bestX = currentX;: f* S& t p3 a0 x1 h
bestY = currentY;* b9 N) g% }% ?7 R0 Y1 S. T# n
end
* P$ ~0 O' n8 f8 ^: n4 p
$ S0 o) z$ g1 @0 ? k: b
% 运行爬山算法8 C; n5 C8 h' U/ `/ W4 U; o
initialX = 0; % 初始点
& H' F4 ^+ A\\" d. W0 M
stepSize = 0.1; % 步长# _) W/ w+ R6 _6 {: I/ @
numIterations = 100; % 迭代次数
6 m' r& ~; L* G: O6 s
[bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations) 
6 @$ B! w& D* t, k( ]' Z& e
    currentX = initialX;) _* I9 H6 R' L- h

currentY = func(currentX); 
3 t% l6 @* h, O! n3 I) ?# |
    for i = 1:numIterations 
  B/ J! f% A, M1 l; r
        % 尝试在两个方向上移动 
; {4 S6 u9 c8 x) ?: k$ [
        newX = [currentX + stepSize, currentX - stepSize]; 
# R6 P\\" M. n& \% B. v
        newY = [func(newX(1)), func(newX(2))];: F& q7 \) k8 w) n* d

6 w5 o! Q3 H% x# c

% 找出最好的移动方向 
8 V  y3 W6 v2 \- m7 Z
        [maxY, idx] = max(newY);5 Q8 H2 c3 |4 m, q/ Y1 ~4 S

# F3 l. H4 D6 P1 u: Z9 ~, T

% 如果找到了更好的解，则更新当前解 
* r$ Q4 {3 N7 F
        if maxY > currentY\\" W% M5 a% j8 l8 H7 l' p/ i

currentX = newX(idx); 
$ R* X\\" d' t- O
            currentY = maxY; 
* C5 j2 g7 ~7 K
        else0 t\\" B3 K% \0 a, J/ f1 |

% 如果没有更好的解，结束搜索 
$ f' [  i+ L9 y) }1 q+ T. P4 p( N\\" z0 {
            break; 
( @4 g! ]& X$ t- O: R. |  d8 e! S4 F
        end( O2 F2 a6 E7 W; q0 I! U; T

end* ~* W+ K  ^4 |: S, ^2 {3 P# g1 ~

bestX = currentX;: f* S& t  p3 a0 x1 h

bestY = currentY;* b9 N) g% }% ?7 R0 Y1 S. T# n

end 
* P$ ~0 O' n8 f8 ^: n4 p
 $ S0 o) z$ g1 @0 ?  k: b

% 运行爬山算法8 C; n5 C8 h' U/ `/ W4 U; o

initialX = 0; % 初始点 
& H' F4 ^+ A\\" d. W0 M
stepSize = 0.1; % 步长# _) W/ w+ R6 _6 {: I/ @

numIterations = 100; % 迭代次数 
6 m' r& ~; L* G: O6 s
[bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

步骤 3: 输出结果

展示算法找到的最优解。

disp(['The maximum value of f(x) is found at x = ', num2str(bestX)]);
! x\" i3 j- c `8 b* c' |
disp(['The maximum value of f(x) is ', num2str(bestY)]);

复制代码

步骤 4: 可视化

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