查看: 2582|回复: 0

爬山算法

字体大小: 正常放大

1192 主题	4 听众	2946 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

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

步骤 1: 定义目标函数

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

function y = myFunction(x)/ ~# n T9 }# e; h
y = -x^2 + 4*x;1 h4 u: u/ W$ x$ V d) G
end

步骤 2: 实现爬山算法

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

function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations)# d\\" d6 {( N+ U' s }\\" \5 y9 }: x; M
currentX = initialX;! S- ^3 N- S4 P& D5 v3 u$ V+ h: Y
currentY = func(currentX);; A4 @$ \6 E4 K+ @* [
for i = 1:numIterations) l& [\\" i- F5 r# c
% 尝试在两个方向上移动
( X/ C) J2 D\\" z! @ V# r
newX = [currentX + stepSize, currentX - stepSize];
g( ]* [0 G i# z
newY = [func(newX(1)), func(newX(2))];9 A( o' `; a r7 s5 b/ Q% |
8 n. A* [% }4 w1 ~
% 找出最好的移动方向5 e& P ]) o% c
[maxY, idx] = max(newY);
* |4 x$ M5 U\\" T0 E5 D4 y- r/ S/ s
, p. M$ p9 E. \1 _- N& `# T& o
% 如果找到了更好的解，则更新当前解
, G\\" ^) ^1 N( j: _/ o8 c5 w1 K- m6 ~
if maxY > currentY
3 S9 m5 o; @+ p. R9 g
currentX = newX(idx);
0 [\\" h+ _: J1 H, F$ [2 X
currentY = maxY;
9 A, m8 s! K( s; a. T, y, a
else
3 T6 }% _* z5 `8 H: s
% 如果没有更好的解，结束搜索
. c2 h. z: A% D/ F. @2 o4 i
break;/ M\\" | V' \' y* U# C; B
end
7 H\\" ^0 ]- w0 Z$ j6 B' H
end. e0 ?, E% r) \2 ^3 y
bestX = currentX;
+ q\\" F$ _2 p! b) o+ ]9 Y+ `% a f
bestY = currentY;
( w9 h. _! T, Y. ` |
end2 Z% ]# w/ d+ w) G; n5 O# [
# ^% m F3 v1 p0 @5 Q: G1 a3 z
% 运行爬山算法
+ Q8 O% I# ?& C\\" g
initialX = 0; % 初始点% I. Q* D4 Q2 e# F& u, {
stepSize = 0.1; % 步长
/ T6 L2 X\\" }2 k
numIterations = 100; % 迭代次数7 L# L1 B5 S4 z* C, `
[bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations)# d\\" d6 {( N+ U' s  }\\" \5 y9 }: x; M

currentX = initialX;! S- ^3 N- S4 P& D5 v3 u$ V+ h: Y

currentY = func(currentX);; A4 @$ \6 E4 K+ @* [

for i = 1:numIterations) l& [\\" i- F5 r# c

% 尝试在两个方向上移动 
( X/ C) J2 D\\" z! @  V# r
        newX = [currentX + stepSize, currentX - stepSize]; 
  g( ]* [0 G  i# z
        newY = [func(newX(1)), func(newX(2))];9 A( o' `; a  r7 s5 b/ Q% |

8 n. A* [% }4 w1 ~

% 找出最好的移动方向5 e& P  ]) o% c

[maxY, idx] = max(newY); 
* |4 x$ M5 U\\" T0 E5 D4 y- r/ S/ s
         
, p. M$ p9 E. \1 _- N& `# T& o
        % 如果找到了更好的解，则更新当前解 
, G\\" ^) ^1 N( j: _/ o8 c5 w1 K- m6 ~
        if maxY > currentY 
3 S9 m5 o; @+ p. R9 g
            currentX = newX(idx); 
0 [\\" h+ _: J1 H, F$ [2 X
            currentY = maxY; 
9 A, m8 s! K( s; a. T, y, a
        else 
3 T6 }% _* z5 `8 H: s
            % 如果没有更好的解，结束搜索 
. c2 h. z: A% D/ F. @2 o4 i
            break;/ M\\" |  V' \' y* U# C; B

end 
7 H\\" ^0 ]- w0 Z$ j6 B' H
    end. e0 ?, E% r) \2 ^3 y

bestX = currentX; 
+ q\\" F$ _2 p! b) o+ ]9 Y+ `% a  f
    bestY = currentY; 
( w9 h. _! T, Y. `  |
end2 Z% ]# w/ d+ w) G; n5 O# [

# ^% m  F3 v1 p0 @5 Q: G1 a3 z
% 运行爬山算法 
+ Q8 O% I# ?& C\\" g
initialX = 0; % 初始点% I. Q* D4 Q2 e# F& u, {

stepSize = 0.1; % 步长 
/ T6 L2 X\\" }2 k
numIterations = 100; % 迭代次数7 L# L1 B5 S4 z* C, `

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

步骤 3: 输出结果

展示算法找到的最优解。

disp(['The maximum value of f(x) is found at x = ', num2str(bestX)]);
6 E* ]; r\" M% M4 T
disp(['The maximum value of f(x) is ', num2str(bestY)]);

复制代码

步骤 4: 可视化

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

x = 0:0.01:5;
/ R: Z/ C2 N8 D( U
y = myFunction(x);
8 H k4 L/ @% {: g
figure;
' G. V0 [4 l9 ]; l% e
plot(x, y, 'b-', bestX, bestY, 'ro');\\" ?$ x) y6 o6 g( H+ j1 g8 v
title('Function Optimization using Hill Climbing');6 J) ?. M8 f6 ?' h6 f6 _$ b& f
xlabel('x');
0 l& {0 }; ]1 R# b S
ylabel('f(x)');5 F/ _) l2 W; S# r; q
legend('Function', 'Maximum Point');