爬山算法

2744557306

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

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

步骤 1: 定义目标函数

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

2. function y = myFunction(x)% t+ a0 R7 }1 k( m% G  P4 J' ~+ b
   
4.     y = -x^2 + 4*x;
   
5. \\" ]& ~0 G9 S% e* w+ [
6. end

function y = myFunction(x)<font class=\\"jammer\\">% t+ a0 R7 }1 k( m% G  P4 J' ~+ b</font><br />     y = -x^2 + 4*x;<br /> <span style=\\"display:none\\">\\" ]& ~0 G9 S% e* w+ [</span> end

步骤 2: 实现爬山算法

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

2. function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations)
   
3. / d5 o$ X, h5 f
4.     currentX = initialX;\\" m8 K5 G$ {; U8 |( }\\" t
   
6.     currentY = func(currentX);
   
7. ) ?\\" }2 i/ k' o/ k% G3 v! L# a: \
8.     for i = 1:numIterations
   
9. - c2 F0 e# \: H
10.         % 尝试在两个方向上移动
    
11. * @. \( F* o1 g
12.         newX = [currentX + stepSize, currentX - stepSize];
    
13. * I5 B: c# H  ^
14.         newY = [func(newX(1)), func(newX(2))];  n! |  Y( f0 s  K/ Y( K
    
16. 1 Z3 t5 C1 O# F) q1 ~
    
18.         % 找出最好的移动方向
    
19. , x$ g8 W# z- W\\" k1 C
20.         [maxY, idx] = max(newY);; I3 s7 v8 z( u+ @; i
    
22.         7 u, i0 L, x) b, M) C! S1 u/ P) z
    
24.         % 如果找到了更好的解，则更新当前解3 l. R+ w5 @7 |- H* L8 j
    
26.         if maxY > currentY
    
27. 1 O2 q( s4 v0 a) t% k6 K6 ]! @
28.             currentX = newX(idx);
    
29. 5 o' F7 Q' R4 g* H9 Z, f/ M6 f
30.             currentY = maxY;7 H7 z6 X/ ?. W# b
    
32.         else
    
33.   B4 M/ |6 o# g8 |* I2 J
34.             % 如果没有更好的解，结束搜索
    
35. ! v2 U! M/ l/ s! i4 H
36.             break;2 n  H* r9 k3 D+ ~  V
    
38.         end, w/ \$ `/ u3 {! o8 s3 [
    
40.     end
    
41. 3 }2 C4 P. f* E9 I! d3 v( {
42.     bestX = currentX;- t8 t1 I9 Y; Z  Y
    
44.     bestY = currentY;9 z, z  t/ w; x' W
    
46. end
    
47. 0 _( p5 k) U5 ?' k8 D
48. 
    
49. 7 E\\" w5 f& F3 x# \3 j+ I
50. % 运行爬山算法
    
51. 8 S; ~3 g2 `9 w$ G3 [$ N9 {
52. initialX = 0; % 初始点8 h. e& e: O; ]) K! j; _7 L
    
54. stepSize = 0.1; % 步长0 b: r& e' d9 C- W1 z1 c7 K8 U: D
    
56. numIterations = 100; % 迭代次数
    
57. # z) X, [; m; ?
58. [bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations)<br /> <span style=\\"display:none\\">/ d5 o$ X, h5 f</span>     currentX = initialX;<font class=\\"jammer\\">\\" m8 K5 G$ {; U8 |( }\\" t</font><br />     currentY = func(currentX);<br /> <span style=\\"display:none\\">) ?\\" }2 i/ k' o/ k% G3 v! L# a: \</span>     for i = 1:numIterations<br /> <span style=\\"display:none\\">- c2 F0 e# \: H</span>         % 尝试在两个方向上移动<br /> <span style=\\"display:none\\">* @. \( F* o1 g</span>         newX = [currentX + stepSize, currentX - stepSize];<br /> <span style=\\"display:none\\">* I5 B: c# H  ^</span>         newY = [func(newX(1)), func(newX(2))];<font class=\\"jammer\\">  n! |  Y( f0 s  K/ Y( K</font><br /> <font class=\\"jammer\\">1 Z3 t5 C1 O# F) q1 ~</font><br />         % 找出最好的移动方向<br /> <span style=\\"display:none\\">, x$ g8 W# z- W\\" k1 C</span>         [maxY, idx] = max(newY);<font class=\\"jammer\\">; I3 s7 v8 z( u+ @; i</font><br />         <font class=\\"jammer\\">7 u, i0 L, x) b, M) C! S1 u/ P) z</font><br />         % 如果找到了更好的解，则更新当前解<font class=\\"jammer\\">3 l. R+ w5 @7 |- H* L8 j</font><br />         if maxY > currentY<br /> <span style=\\"display:none\\">1 O2 q( s4 v0 a) t% k6 K6 ]! @</span>             currentX = newX(idx);<br /> <span style=\\"display:none\\">5 o' F7 Q' R4 g* H9 Z, f/ M6 f</span>             currentY = maxY;<font class=\\"jammer\\">7 H7 z6 X/ ?. W# b</font><br />         else<br /> <span style=\\"display:none\\">  B4 M/ |6 o# g8 |* I2 J</span>             % 如果没有更好的解，结束搜索<br /> <span style=\\"display:none\\">! v2 U! M/ l/ s! i4 H</span>             break;<font class=\\"jammer\\">2 n  H* r9 k3 D+ ~  V</font><br />         end<font class=\\"jammer\\">, w/ \$ `/ u3 {! o8 s3 [</font><br />     end<br /> <span style=\\"display:none\\">3 }2 C4 P. f* E9 I! d3 v( {</span>     bestX = currentX;<font class=\\"jammer\\">- t8 t1 I9 Y; Z  Y</font><br />     bestY = currentY;<font class=\\"jammer\\">9 z, z  t/ w; x' W</font><br /> end<br /> <span style=\\"display:none\\">0 _( p5 k) U5 ?' k8 D</span> <br /> <span style=\\"display:none\\">7 E\\" w5 f& F3 x# \3 j+ I</span> % 运行爬山算法<br /> <span style=\\"display:none\\">8 S; ~3 g2 `9 w$ G3 [$ N9 {</span> initialX = 0; % 初始点<font class=\\"jammer\\">8 h. e& e: O; ]) K! j; _7 L</font><br /> stepSize = 0.1; % 步长<font class=\\"jammer\\">0 b: r& e' d9 C- W1 z1 c7 K8 U: D</font><br /> numIterations = 100; % 迭代次数<br /> <span style=\\"display:none\\"># z) X, [; m; ?</span> [bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

步骤 3: 输出结果

        展示算法找到的最优解。

1. disp(['The maximum value of f(x) is found at x = ', num2str(bestX)]);
   ) q  ]6 S: O8 h6 \. k: Q
2. disp(['The maximum value of f(x) is ', num2str(bestY)]);

复制代码

步骤 4: 可视化

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

2. x = 0:0.01:5;
   
3. 9 k* Q: D! D6 z! j* G) B
4. y = myFunction(x);
   
5. . |; [% I$ X0 a3 i+ o: U% Q
6. figure;2 g( V( w9 K& z$ j) s
   
8. plot(x, y, 'b-', bestX, bestY, 'ro');
   
9. # _: o2 l1 y) Q# w, X8 |2 Q
10. title('Function Optimization using Hill Climbing');( A6 g- j# {, g' m
    
12. xlabel('x');
    
13. 5 O) b1 j4 ^1 |' o
14. ylabel('f(x)');1 z2 S% h  V! ^) s- v9 ~  O& S) n4 b! ?\\" C
    
16. legend('Function', 'Maximum Point');

x = 0:0.01:5;<br /> <span style=\\"display:none\\">9 k* Q: D! D6 z! j* G) B</span> y = myFunction(x);<br /> <span style=\\"display:none\\">. |; [% I$ X0 a3 i+ o: U% Q</span> figure;<font class=\\"jammer\\">2 g( V( w9 K& z$ j) s</font><br /> plot(x, y, 'b-', bestX, bestY, 'ro');<br /> <span style=\\"display:none\\"># _: o2 l1 y) Q# w, X8 |2 Q</span> title('Function Optimization using Hill Climbing');<font class=\\"jammer\\">( A6 g- j# {, g' m</font><br /> xlabel('x');<br /> <span style=\\"display:none\\">5 O) b1 j4 ^1 |' o</span> ylabel('f(x)');<font class=\\"jammer\\">1 z2 S% h  V! ^) s- v9 ~  O& S) n4 b! ?\\" C</font><br /> legend('Function', 'Maximum Point');

; y9 f$ G. R( P  ?, _" q7 K) n# U% t