爬山算法

2744557306

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

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

. Q" M% o3 O! {& r: y2 @步骤 1: 定义目标函数

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

2. function y = myFunction(x)3 h9 G( w/ D- G; [* k9 m8 a. M% o* L
   
4.     y = -x^2 + 4*x;
   
5. \\" r; B- F\\" |- U, A
6. end

function y = myFunction(x)<font class=\\"jammer\\">3 h9 G( w/ D- G; [* k9 m8 a. M% o* L</font><br />     y = -x^2 + 4*x;<br /> <span style=\\"display:none\\">\\" r; B- F\\" |- U, A</span> end

步骤 2: 实现爬山算法

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

2. function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations)
   
3. % J9 [/ ?. S$ N& _/ b, g
4.     currentX = initialX;! n, c4 P9 ]+ j3 @
   
6.     currentY = func(currentX);7 k, x' w8 ?3 V, N. q$ z
   
8.     for i = 1:numIterations' g$ w$ ^# U% P9 c8 J
   
10.         % 尝试在两个方向上移动1 Q/ _' J. M6 I( f4 A! |' ?, s/ V
    
12.         newX = [currentX + stepSize, currentX - stepSize];
    
13. 0 |4 e# K: G) a* _\\" D
14.         newY = [func(newX(1)), func(newX(2))];
    
15. ; i$ B! E/ O5 V% a! N& b
16. 
    
17. , d: t. k; i7 r$ A. Q) B) ]8 F
18.         % 找出最好的移动方向
    
19. \\" q- o1 B/ u9 o( `1 j& o* q
20.         [maxY, idx] = max(newY);
    
21. 8 H# P; y7 Y/ Z6 _. j3 w( Q9 e
22.         5 s% k) o0 [3 ?3 z2 D, V8 G. u
    
24.         % 如果找到了更好的解，则更新当前解
    
25. + q6 Q- r. b  K! L) A2 ?
26.         if maxY > currentY# z- d2 A2 y) T6 _/ c
    
28.             currentX = newX(idx);
    
29. ! N  o4 ^; d( t2 A; N/ M; d5 j  f
30.             currentY = maxY;
    
31. # ]) y; j* t4 [1 c
32.         else
    
33. / ]6 f; K$ Q* K+ X# Z
34.             % 如果没有更好的解，结束搜索' o. y$ \9 v! G( Q; k
    
36.             break;
    
37. . a6 S- n8 E: \; w\\" D
38.         end7 B5 L1 q/ C3 F8 Z# B. h6 h
    
40.     end
    
41. 3 t% @9 _! \0 D
42.     bestX = currentX;\\" v0 X/ {' H8 T+ F! c- t' d
    
44.     bestY = currentY;
    
45. & D  F8 U+ N/ a6 D4 A  U; U
46. end: S8 R+ d7 Z4 T6 X$ y/ g
    
48. ) P) ^- t4 f5 n. E. H
    
50. % 运行爬山算法9 [( D( G: V) r& \4 B6 ~: U\\" S
    
52. initialX = 0; % 初始点& m0 c- R3 K/ [! h& \. W
    
54. stepSize = 0.1; % 步长
    
55. \\" K9 N# N$ u. \\\" b: r, j
56. numIterations = 100; % 迭代次数, ]; G! K4 ?: z1 G9 s
    
58. [bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations)<br /> <span style=\\"display:none\\">% J9 [/ ?. S$ N& _/ b, g</span>     currentX = initialX;<font class=\\"jammer\\">! n, c4 P9 ]+ j3 @</font><br />     currentY = func(currentX);<font class=\\"jammer\\">7 k, x' w8 ?3 V, N. q$ z</font><br />     for i = 1:numIterations<font class=\\"jammer\\">' g$ w$ ^# U% P9 c8 J</font><br />         % 尝试在两个方向上移动<font class=\\"jammer\\">1 Q/ _' J. M6 I( f4 A! |' ?, s/ V</font><br />         newX = [currentX + stepSize, currentX - stepSize];<br /> <span style=\\"display:none\\">0 |4 e# K: G) a* _\\" D</span>         newY = [func(newX(1)), func(newX(2))];<br /> <span style=\\"display:none\\">; i$ B! E/ O5 V% a! N& b</span> <br /> <span style=\\"display:none\\">, d: t. k; i7 r$ A. Q) B) ]8 F</span>         % 找出最好的移动方向<br /> <span style=\\"display:none\\">\\" q- o1 B/ u9 o( `1 j& o* q</span>         [maxY, idx] = max(newY);<br /> <span style=\\"display:none\\">8 H# P; y7 Y/ Z6 _. j3 w( Q9 e</span>         <font class=\\"jammer\\">5 s% k) o0 [3 ?3 z2 D, V8 G. u</font><br />         % 如果找到了更好的解，则更新当前解<br /> <span style=\\"display:none\\">+ q6 Q- r. b  K! L) A2 ?</span>         if maxY > currentY<font class=\\"jammer\\"># z- d2 A2 y) T6 _/ c</font><br />             currentX = newX(idx);<br /> <span style=\\"display:none\\">! N  o4 ^; d( t2 A; N/ M; d5 j  f</span>             currentY = maxY;<br /> <span style=\\"display:none\\"># ]) y; j* t4 [1 c</span>         else<br /> <span style=\\"display:none\\">/ ]6 f; K$ Q* K+ X# Z</span>             % 如果没有更好的解，结束搜索<font class=\\"jammer\\">' o. y$ \9 v! G( Q; k</font><br />             break;<br /> <span style=\\"display:none\\">. a6 S- n8 E: \; w\\" D</span>         end<font class=\\"jammer\\">7 B5 L1 q/ C3 F8 Z# B. h6 h</font><br />     end<br /> <span style=\\"display:none\\">3 t% @9 _! \0 D</span>     bestX = currentX;<font class=\\"jammer\\">\\" v0 X/ {' H8 T+ F! c- t' d</font><br />     bestY = currentY;<br /> <span style=\\"display:none\\">& D  F8 U+ N/ a6 D4 A  U; U</span> end<font class=\\"jammer\\">: S8 R+ d7 Z4 T6 X$ y/ g</font><br /> <font class=\\"jammer\\">) P) ^- t4 f5 n. E. H</font><br /> % 运行爬山算法<font class=\\"jammer\\">9 [( D( G: V) r& \4 B6 ~: U\\" S</font><br /> initialX = 0; % 初始点<font class=\\"jammer\\">& m0 c- R3 K/ [! h& \. W</font><br /> stepSize = 0.1; % 步长<br /> <span style=\\"display:none\\">\\" K9 N# N$ u. \\\" b: r, j</span> numIterations = 100; % 迭代次数<font class=\\"jammer\\">, ]; G! K4 ?: z1 G9 s</font><br /> [bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

步骤 3: 输出结果

        展示算法找到的最优解。

1. disp(['The maximum value of f(x) is found at x = ', num2str(bestX)]);: l% @1 j5 s& }, Y0 A+ C
   
2. disp(['The maximum value of f(x) is ', num2str(bestY)]);

复制代码

步骤 4: 可视化

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

2. x = 0:0.01:5;( ]2 I8 k7 D* d\\" ~6 x9 U$ A' F
   
4. y = myFunction(x);6 u- J7 v. X7 e9 J4 K
   
6. figure;
   
7. 2 @\\" y7 I2 M% M
8. plot(x, y, 'b-', bestX, bestY, 'ro');. I+ g/ J% h0 ?
   
10. title('Function Optimization using Hill Climbing');
    
11. + F& R: P$ z. T% s1 q6 Z
12. xlabel('x');\\" v# h/ q\\" Q& h/ v
    
14. ylabel('f(x)');
    
15. 6 x0 e& Y; i* ^
16. legend('Function', 'Maximum Point');

x = 0:0.01:5;<font class=\\"jammer\\">( ]2 I8 k7 D* d\\" ~6 x9 U$ A' F</font><br /> y = myFunction(x);<font class=\\"jammer\\">6 u- J7 v. X7 e9 J4 K</font><br /> figure;<br /> <span style=\\"display:none\\">2 @\\" y7 I2 M% M</span> plot(x, y, 'b-', bestX, bestY, 'ro');<font class=\\"jammer\\">. I+ g/ J% h0 ?</font><br /> title('Function Optimization using Hill Climbing');<br /> <span style=\\"display:none\\">+ F& R: P$ z. T% s1 q6 Z</span> xlabel('x');<font class=\\"jammer\\">\\" v# h/ q\\" Q& h/ v</font><br /> ylabel('f(x)');<br /> <span style=\\"display:none\\">6 x0 e& Y; i* ^</span> legend('Function', 'Maximum Point');